Use the Viterbi dynamic program on a 2-state weather HMM (Rainy/Sunny) to decode the most-likely hidden-state path for the observations clean, clean, walk; print the path and its probability.

Answer

states = ['Rainy', 'Sunny'] start = {'Rainy': 0.6, 'Sunny': 0.4} trans = { 'Rainy': {'Rainy': 0.7, 'Sunny': 0.3}, 'Sunny': {'Rainy': 0.4, 'Sunny': 0.6}, } emit = { 'Rainy': {'walk': 0.1, 'shop': 0.4, 'clean': 0.5}, 'Sunny': {'walk': 0.6, 'shop': 0.3, 'clean': 0.1}, } obs = ['clean', 'clean', 'walk'] V = [{}] back = [{}] for s in states: V[0][s] = start[s] * emit[s][obs[0]] back[0][s] = None for t in range(1, len(obs)): V.append({}); back.append({}) for s in states: best_prev, best_p = None, -1.0 for ps in states: p = V[t - 1][ps] * trans[ps][s] * emit[s][obs[t]] if p > best_p: best_p, best_prev = p, ps V[t][s] = best_p back[t][s] = best_prev last = max(states, key=lambda s: V[-1][s]) prob = V[-1][last] path = [last] for t in range(len(obs) - 1, 0, -1): last = back[t][last] path.insert(0, last) print(f"viterbi path: [{', '.join(path)}] p={prob:.3f}")