import json
def normalize_dist(dist):
total = sum(dist.values())
return { k: float(dist[k])/total for k in list(dist.keys()) }
def normalize(d):
for key, dist in d.items():
d[key] = normalize_dist(dist)
def normalize_hmm(start_p, trans_p, emit_p):
normalize(trans_p)
normalize(emit_p)
return normalize_dist(start_p)
def viterbi(obs, states, start_p, trans_p, emit_p):
V = [{}]
path = {}
# normalize or renormalize all distributions in the hmm
start_p = normalize_hmm(start_p, trans_p, emit_p)
# Initialize base cases (t == 0)
for y in states:
V[0][y] = start_p[y] * emit_p[y][obs[0]]
path[y] = [y]
# Run Viterbi for t > 0
for t in range(1,len(obs)):
V.append({})
newpath = {}
for y in states:
(prob, state) = max([(V[t-1][y0] * trans_p[y0][y] * emit_p[y][obs[t]], y0) for y0 in states])
V[t][y] = prob
newpath[y] = path[state] + [y]
# Don't need to remember the old paths
path = newpath
print_dptable(V, obs)
(prob, state) = max([(V[len(obs) - 1][y], y) for y in states])
return (prob, path[state])
# Helps visualize the steps of Viterbi.
def print_dptable(V, obs=[]):
print(" ", end=' ')
if len(obs) > 0:
for i in range(len(V)): print("%7s" % obs[i], end=' ')
print()
for i in range(len(V)): print("%7d" % i, end=' ')
print()
for y in list(V[0].keys()):
print("%.5s: " % y, end=' ')
for t in range(len(V)):
print("%.7s" % ("%f" % V[t][y]), end=' ')
print()
def print_hmm(start_p, trans_p, emit_p):
print("Start probability:")
print(json.dumps(start_p, indent=4))
print("Transition probability:")
print(json.dumps(trans_p, indent=4))
print("Emission probability:")
print(json.dumps(emit_p, indent=4))
states = ('A', 'N')
start_probability = {'A': 0.25, 'N': 0.75}
transition_probability = {
'A' : {'A': 0, 'N': 1.0},
'N' : {'A': 0.5, 'N': 0.5},
}
emission_probability = {
'A' : {'clown': 0, 'killer': 0, 'problem': 0, 'crazy': 1.0},
'N' : {'clown': 0.4, 'killer': 0.3, 'problem': 0.3, 'crazy': 0.0},
}
observations = ('killer', 'crazy', 'clown', 'problem')
print("input:", observations)
print()
start_probability = normalize_hmm(start_probability, transition_probability, emission_probability)
print(print_hmm(start_probability, transition_probability, emission_probability))
print()
(prob, path) = viterbi(observations, states, start_probability, transition_probability, emission_probability)
print()
print("best path prob:", prob)
print("best path:", path)
input: ('killer', 'crazy', 'clown', 'problem') Start probability: { "A": 0.25, "N": 0.75 } Transition probability: { "A": { "A": 0.0, "N": 1.0 }, "N": { "A": 0.5, "N": 0.5 } } Emission probability: { "A": { "clown": 0.0, "killer": 0.0, "problem": 0.0, "crazy": 1.0 }, "N": { "clown": 0.4, "killer": 0.3, "problem": 0.3, "crazy": 0.0 } } None killer crazy clown problem 0 1 2 3 A: 0.00000 0.11250 0.00000 0.00000 N: 0.22500 0.00000 0.04500 0.00675 best path prob: 0.00675 best path: ['N', 'A', 'N', 'N']
states = ('A', 'N')
start_probability = {'A': 0.25, 'N': 0.75}
transition_probability = {
'A' : {'A': 0.1, 'N': 0.9},
'N' : {'A': 0.5, 'N': 0.5},
}
emission_probability = {
'A' : {'clown': 0.01, 'killer': 0.01, 'problem': 0.01, 'crazy': 1.0 - (0.01*3)},
'N' : {'clown': 0.3, 'killer': 0.3, 'problem': 0.3, 'crazy': 0.1},
}
observations = ('killer', 'crazy', 'clown', 'problem')
print("input:", observations)
print()
start_probability = normalize_hmm(start_probability, transition_probability, emission_probability)
print(print_hmm(start_probability, transition_probability, emission_probability))
print()
(prob, path) = viterbi(observations, states, start_probability, transition_probability, emission_probability)
print()
print("best path prob:", prob)
print("best path:", path)
input: ('killer', 'crazy', 'clown', 'problem') Start probability: { "A": 0.25, "N": 0.75 } Transition probability: { "A": { "A": 0.1, "N": 0.9 }, "N": { "A": 0.5, "N": 0.5 } } Emission probability: { "A": { "clown": 0.01, "killer": 0.01, "problem": 0.01, "crazy": 0.97 }, "N": { "clown": 0.30000000000000004, "killer": 0.30000000000000004, "problem": 0.30000000000000004, "crazy": 0.10000000000000002 } } None killer crazy clown problem 0 1 2 3 A: 0.00250 0.10912 0.00010 0.00014 N: 0.22500 0.01125 0.02946 0.00442 best path prob: 0.004419562499999999 best path: ['N', 'A', 'N', 'N']
states = ('V', 'N')
start_probability = {'V': 0.25, 'N': 0.75}
transition_probability = {
'N' : {'V': 0.4, 'N': 0.6},
'V' : {'V': 0.6, 'N': 0.4},
}
emission_probability = {
'N' : {'time': 0.6, 'flies': 0.3, 'can': 0.1},
'V' : {'time': 0.2, 'flies': 0.1, 'can': 0.7},
}
observations = ('time', 'flies', 'can')
print("input:", observations)
print()
start_probability = normalize_hmm(start_probability, transition_probability, emission_probability)
print(print_hmm(start_probability, transition_probability, emission_probability))
print()
for i in range(1,len(observations)+1):
(prob, path) = viterbi(observations[:i], states, start_probability, transition_probability, emission_probability)
print()
print("best path prob:", prob)
print("best path:", path)
print()
input: ('time', 'flies', 'can') Start probability: { "V": 0.25, "N": 0.75 } Transition probability: { "N": { "V": 0.4, "N": 0.6 }, "V": { "V": 0.6, "N": 0.4 } } Emission probability: { "N": { "time": 0.6000000000000001, "flies": 0.30000000000000004, "can": 0.10000000000000002 }, "V": { "time": 0.2, "flies": 0.1, "can": 0.7 } } None time 0 V: 0.05000 N: 0.45000 best path prob: 0.44999999999999996 best path: ['N'] time flies 0 1 V: 0.05000 0.01800 N: 0.45000 0.08100 best path prob: 0.08100000000000002 best path: ['N', 'N'] time flies can 0 1 2 V: 0.05000 0.01800 0.02268 N: 0.45000 0.08100 0.00486 best path prob: 0.02268 best path: ['N', 'N', 'V']
states = ('V', 'N')
start_probability = {'V': 0.25, 'N': 0.75}
transition_probability = {
'V' : {'V': 0.5, 'N': 0.5},
'N' : {'V': 0.5, 'N': 0.5},
}
emission_probability = {
'V' : {'time': 0.1, 'flies': 0.1, 'can': 0.8},
'N' : {'time': 0.5, 'flies': 0.4, 'can': 0.1},
}
observations = ('time', 'flies', 'can')
print("input:", observations)
print()
start_probability = normalize_hmm(start_probability, transition_probability, emission_probability)
print(print_hmm(start_probability, transition_probability, emission_probability))
print()
for i in range(1,len(observations)+1):
(prob, path) = viterbi(observations[:i], states, start_probability, transition_probability, emission_probability)
print()
print("best path prob:", prob)
print("best path:", path)
print()
input: ('time', 'flies', 'can') Start probability: { "V": 0.25, "N": 0.75 } Transition probability: { "V": { "V": 0.5, "N": 0.5 }, "N": { "V": 0.5, "N": 0.5 } } Emission probability: { "V": { "time": 0.1, "flies": 0.1, "can": 0.8 }, "N": { "time": 0.5, "flies": 0.4, "can": 0.1 } } None time 0 V: 0.02500 N: 0.37500 best path prob: 0.375 best path: ['N'] time flies 0 1 V: 0.02500 0.01875 N: 0.37500 0.07500 best path prob: 0.07500000000000001 best path: ['N', 'N'] time flies can 0 1 2 V: 0.02500 0.01875 0.03000 N: 0.37500 0.07500 0.00375 best path prob: 0.030000000000000006 best path: ['N', 'N', 'V']
states = ('N', 'V', 'P')
observations = ('british', 'left','waffles','on','falkland','islands')
start_probability = {'N': 10, 'V': 1, 'P': 1}
transition_probability = {
'N' : {'N': 1, 'V': 1, 'P': 1},
'V' : {'N': 1, 'V': 1, 'P': 1},
'P' : {'N': 10, 'V': 1, 'P': 1},
}
emission_probability = {
'N' : {'british': 5, 'left': 5, 'waffles': 10, 'on': 1, 'falkland': 5, 'islands': 5},
'V' : {'british': 1, 'left': 10, 'waffles': 5, 'on': 1, 'falkland': 1, 'islands': 1},
'P' : {'british': 1, 'left': 1, 'waffles': 1, 'on': 10, 'falkland': 1, 'islands': 1},
}
print("input:", observations)
print()
start_probability = normalize_hmm(start_probability, transition_probability, emission_probability)
print(print_hmm(start_probability, transition_probability, emission_probability))
print()
(prob, path) = viterbi(observations, states, start_probability, transition_probability, emission_probability)
print()
print("best path prob:", prob)
print("best path:", path)
input: ('british', 'left', 'waffles', 'on', 'falkland', 'islands') Start probability: { "N": 0.8333333333333334, "V": 0.08333333333333333, "P": 0.08333333333333333 } Transition probability: { "N": { "N": 0.3333333333333333, "V": 0.3333333333333333, "P": 0.3333333333333333 }, "V": { "N": 0.3333333333333333, "V": 0.3333333333333333, "P": 0.3333333333333333 }, "P": { "N": 0.8333333333333334, "V": 0.08333333333333333, "P": 0.08333333333333333 } } Emission probability: { "N": { "british": 0.16129032258064516, "left": 0.16129032258064516, "waffles": 0.3225806451612903, "on": 0.03225806451612903, "falkland": 0.16129032258064516, "islands": 0.16129032258064516 }, "V": { "british": 0.05263157894736842, "left": 0.5263157894736842, "waffles": 0.2631578947368421, "on": 0.05263157894736842, "falkland": 0.05263157894736842, "islands": 0.05263157894736842 }, "P": { "british": 0.06666666666666667, "left": 0.06666666666666667, "waffles": 0.06666666666666667, "on": 0.6666666666666666, "falkland": 0.06666666666666667, "islands": 0.06666666666666667 } } None british left waffles on falkland islands 0 1 2 3 4 5 N: 0.13440 0.00722 0.00253 0.00002 0.00007 0.00000 V: 0.00438 0.02358 0.00206 0.00004 0.00000 0.00000 P: 0.00555 0.00298 0.00052 0.00056 0.00000 0.00000 best path prob: 4.071654010877667e-06 best path: ['N', 'V', 'N', 'P', 'N', 'N']
def forward(obs, states, start_p, trans_p, emit_p):
V = [{}]
# normalize or renormalize all distributions in the hmm
start_p = normalize_hmm(start_p, trans_p, emit_p)
# Initialize base cases (t == 0)
for y in states:
V[0][y] = start_p[y] * emit_p[y][obs[0]]
# Run Viterbi for t > 0
for t in range(1,len(obs)):
V.append({})
for y in states:
V[t][y] = sum([V[t-1][y0] * trans_p[y0][y] * emit_p[y][obs[t]] for y0 in states])
print_dptable(V, obs)
return sum([V[len(obs) - 1][y] for y in states])
states = ('A', 'N')
start_probability = {'A': 0.75, 'N': 0.25}
transition_probability = {
'A' : {'A': 0.3, 'N': 0.7},
'N' : {'A': 0.5, 'N': 0.5},
}
emission_probability = {
'A' : {'clown': 0.01, 'killer': 0.01, 'problem': 0.01, 'crazy': 1.0 - (0.01*3)},
'N' : {'clown': 0.4, 'killer': 0.3, 'problem': 0.3-0.0001, 'crazy': 0.0001},
}
observations = ('killer', 'crazy', 'clown', 'problem')
print(observations)
prob = forward(observations, states, start_probability, transition_probability, emission_probability)
print("prob:", prob)
print()
observations = ('crazy', 'crazy', 'killer', 'problem')
print(observations)
prob = forward(observations, states, start_probability, transition_probability, emission_probability)
print("prob:", prob)
print()
('killer', 'crazy', 'clown', 'problem') killer crazy clown problem 0 1 2 3 A: 0.00750 0.03855 0.00011 0.00005 N: 0.07500 0.00000 0.01079 0.00164 prob: 0.0016976228740537495 ('crazy', 'crazy', 'killer', 'problem') crazy crazy killer problem 0 1 2 3 A: 0.72750 0.21171 0.00063 0.00022 N: 0.00002 0.00005 0.04446 0.00680 prob: 0.007025567097488936
states = ('A', 'N')
start_probability = {'A': 0.5, 'N': 0.5}
transition_probability = {
'A' : {'A': 0.5, 'N': 0.5},
'N' : {'A': 0.5, 'N': 0.5},
}
emission_probability = {
'A' : {'clown': 1, 'killer': 1, 'problem': 1, 'crazy': 1},
'N' : {'clown': 1, 'killer': 1, 'problem': 1, 'crazy': 1},
}
observations = ('killer', 'crazy', 'clown', 'problem')
print(observations)
prob = forward(observations, states, start_probability, transition_probability, emission_probability)
print("prob:", prob)
print()
observations = ('crazy', 'crazy', 'killer', 'problem')
print(observations)
prob = forward(observations, states, start_probability, transition_probability, emission_probability)
print("prob:", prob)
print()
('killer', 'crazy', 'clown', 'problem') killer crazy clown problem 0 1 2 3 A: 0.12500 0.03125 0.00781 0.00195 N: 0.12500 0.03125 0.00781 0.00195 prob: 0.00390625 ('crazy', 'crazy', 'killer', 'problem') crazy crazy killer problem 0 1 2 3 A: 0.12500 0.03125 0.00781 0.00195 N: 0.12500 0.03125 0.00781 0.00195 prob: 0.00390625
print(4**4)
print(0.00390625 * 256)
256 1.0