from collections import defaultdict
states = ("Rainy", "Sunny")
observations = ("Walk", "Shop", "Clean")
start_probability = {"Rainy": 0.6, "Sunny": 0.4}
transition_probability = {
"Rainy": {"Rainy": 0.7, "Sunny": 0.3},
"Sunny": {"Rainy": 0.4, "Sunny": 0.6},
}
emission_probability = {
"Rainy": {"Walk": 0.1, "Shop": 0.4, "Clean": 0.5},
"Sunny": {"Walk": 0.6, "Shop": 0.3, "Clean": 0.1},
}
def compute(obs, states, start_p, trans_p, emit_p):
v = [{} for _ in range(len(obs))]
path = defaultdict(list)
for state in states:
v[0][state] = start_p[state] * emit_p[state][obs[0]]
path[state].append(state)
for t in range(1, len(obs)):
for y1 in states:
max_prob = -1
for y0 in v[t - 1]:
nprob = v[t - 1][y0] * trans_p[y0][y1] * emit_p[y1][obs[t]]
if nprob > max_prob:
max_prob = nprob
max_state = y0
v[t][y1] = max_prob
newpath = []
for state1 in path[max_state]:
newpath.append(state1)
newpath.append(y1)
path[y1] = newpath
prob = -1
for y1 in states:
if v[len(obs) - 1][y1] > prob:
prob = v[len(obs) - 1][y1]
state = y1
return path[state]
if __name__ == "__main__":
max_path = compute(observations, states, start_probability,
transition_probability, emission_probability)
print(max_path)