In [29]:
# from https://en.wikipedia.org/wiki/Viterbi_algorithm
import numpy as np
np.set_printoptions(precision=4)
np.set_printoptions(suppress=True)
obs_strings = ('normal', 'cold', 'dizzy',
'normal', 'normal', 'dizzy', 'normal', 'cold', 'normal',
'cold', 'dizzy', 'cold', 'cold', 'dizzy',
'cold', 'cold', 'cold', 'cold', 'cold',
'dizzy', 'cold', 'cold', 'dizzy')
state_strings = ('Healthy', 'Fever')
start_p_strings = {'Healthy': 0.6, 'Fever': 0.4}
trans_p_strings = {
'Healthy' : {'Healthy': 0.7, 'Fever': 0.3},
'Fever' : {'Healthy': 0.4, 'Fever': 0.6}
}
emit_p_strings = {
'Healthy' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6}
}
S = len(state_strings)
T = len(obs_strings)
O = len(emit_p_strings[list(emit_p_strings.keys())[0]])
print('S', S, 'T', T, 'O', O)
Y = np.zeros((T,), dtype=np.int32)
# X = [None for i in range(T)]
X = np.zeros((T,), dtype=np.int32)
# S = states
s_by_name = {}
for s, state in enumerate(state_strings):
s_by_name[state] = s
output_strings = []
for output_string in emit_p_strings[list(emit_p_strings.keys())[0]]:
output_strings.append(output_string)
o_by_name = {}
for o, output in enumerate(output_strings):
o_by_name[output] = o
for i, obs in enumerate(obs_strings):
Y[i] = o_by_name[obs]
bestProb = np.zeros((S, T), dtype=np.float32)
bestState = np.zeros((S, T), dtype=np.float32)
Pi = np.zeros((S,), dtype=np.float32)
for state_name, p in start_p_strings.items():
s = s_by_name[state_name]
Pi[s] = p
trans = np.zeros((S, S), dtype=np.float32)
emit = np.zeros((S, O), dtype=np.float32)
for state, probs in trans_p_strings.items():
s = s_by_name[state]
for target, prob in probs.items():
s_next = s_by_name[target]
trans[s][s_next] = prob
for state, probs in emit_p_strings.items():
s = s_by_name[state]
for output, prob in probs.items():
o = o_by_name[output]
emit[s][o] = prob
print('trans', trans)
print('emit', emit)
for s in range(S):
bestProb[s, 0] = Pi[s] * emit[s][Y[0]]
bestState[s, 0] = 0
print('bestProb', bestProb)
for t in range(1, T):
# o = Y[t]
for s in range(S):
best_s = -1
best_prob = 0
for s_next in range(S):
this_prob = bestProb[s_next][t - 1] * trans[s_next][s]
if this_prob > best_prob:
best_prob = this_prob
best_s = s_next
bestProb[s][t] = emit[s][Y[t]] * best_prob
bestState[s][t] = best_s
print('bestProb', bestProb)
print('bestState', bestState)
Z = np.zeros((T,), dtype=np.float32)
# Z[T - 1] = np.argmax(bestProb[:, T-1])
X[T - 1] = np.argmax(bestProb[:, T-1])
for t in range(T - 1, 0, -1):
print('t', t)
X[t - 1] = bestState[X[t], t]
print(X)
for t, s in enumerate(X):
print(t, state_strings[s], obs_strings[t])