AI: The Viterbi algorithm

Find the single most likely story behind a sequence of observations.

What to build

A program that finds the most likely sequence of hidden states in a hidden Markov model.

Requirements

  • The input format is that of the filtering exercise, with the same prior convention. The best path into each state is extended day by day using max; ties go to the state that comes first in the list, both for the previous state and for the final state.
  • Print the most likely states separated by spaces, then probability P with six decimal places: the joint probability of that sequence and the observations.

Input

The same as the filtering exercise.

Output

Two lines.

Constraints

At most 10 states and 50 observations.

Example

Input:

Rain Dry
U N
0.7 0.3
0.3 0.7
0.9 0.1
0.2 0.8
0.5 0.5
U U

Output:

Rain Rain
probability 0.283500

Why it works

The best path into a state today must extend the best path into some state yesterday, so keeping only the best path per state is enough, and it takes time linear in the number of days.

Examples

Example 1 · Input
Rain Dry
U N
0.7 0.3
0.3 0.7
0.9 0.1
0.2 0.8
0.5 0.5
U U
Expected output
Rain Rain
probability 0.283500
Example 2 · Input
Rain Dry
U N
0.7 0.3
0.3 0.7
0.9 0.1
0.2 0.8
0.5 0.5
N N
Expected output
Dry Dry
probability 0.224000

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Day 1: best[s] = (Σ over r of prior[r] T[r][s]) × E[s][obs₁]. Later days: best[s] = E[s][obs] × max over r of best[r] T[r][s].

Hint 2

Remember, for every day and state, which previous state gave the max; when equal, keep the earlier state in the list.

Solution

Show one correct solution (try it yourself first)
states = input().split()
symbols = input().split()
n = len(states)
T = [list(map(float, input().split())) for _ in range(n)]
E = [dict(zip(symbols, map(float, input().split()))) for _ in range(n)]
prior = list(map(float, input().split()))
seen = input().split()
best = [sum(prior[r] * T[r][s] for r in range(n)) * E[s][seen[0]] for s in range(n)]
paths = [[s] for s in range(n)]
for obs in seen[1:]:
    new_best, new_paths = [], []
    for s in range(n):
        came_from = 0
        for r in range(1, n):
            if best[r] * T[r][s] > best[came_from] * T[came_from][s]:
                came_from = r
        new_best.append(best[came_from] * T[came_from][s] * E[s][obs])
        new_paths.append(paths[came_from] + [s])
    best, paths = new_best, new_paths
last = 0
for s in range(1, n):
    if best[s] > best[last]:
        last = s
print(" ".join(states[s] for s in paths[last]))
print(f"probability {best[last]:.6f}")

Lesson: Hidden Markov models →