Viterbi Decoding

Find the most likely sequence of hidden states for an HMM with the Viterbi algorithm.

The model is the same as in the forward algorithm: start probabilities pi, transitions A and emissions B. The forward algorithm sums over all paths. Viterbi takes the maximum instead, and it remembers which previous state gave the maximum so it can trace the best path back at the end:

delta_0[j] = log pi[j] + log B[j, obs[0]]
delta_t[j] = max_i (delta_{t-1}[i] + log A[i, j]) + log B[j, obs[t]]
back_t[j]  = the i that gives that maximum

The best final state is argmax_j delta_{T-1}[j]. Follow back from there to the start to get the path.

Return (path, log_prob): the path as a list of ints, and the log probability of that path together with the observations.

Function signature

def viterbi(pi, A, B, obs):

Example

Input

pi = np.array([0.5, 0.5])
A  = np.array([[0.8, 0.2], [0.3, 0.7]])
B  = np.array([[0.6, 0.3, 0.1], [0.1, 0.4, 0.5]])
viterbi(pi, A, B, [0, 2, 1])

Output

([0, 1, 1], -4.779524)

Reasoning

Symbol 0 is much more likely from state 0, so the path starts there with 0.5 * 0.6 = 0.3. Symbol 2 favours state 1, and moving there costs 0.2 * 0.5. State 1 then stays and emits symbol 1 with 0.7 * 0.4. The path probability is 0.3 * 0.1 * 0.28 = 0.0084, and log(0.0084) = -4.7795. No other of the eight possible paths scores higher.

Constraints and notes

• Work in log space so that long sequences do not underflow.
• When two states give the same maximum, take the lower state index.
• Zero probabilities give log(0) = -inf, which is fine inside a max.