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 Pwith 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
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
Rain Rain probability 0.283500
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
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}")