Content deleted Content added
→Forward probabilities: clarify re matrices |
No edit summary |
||
Line 296:
return result
</pre>
==Python example==
Given HMM (just like in [[Viterbi algorithm]]) represented in the [[Python programming language]]:
<source lang="python">
states = ('Healthy', 'Fever')
end_state = 'E'
observations = ('normal', 'cold', 'dizzy')
start_probability = {'Healthy': 0.6, 'Fever': 0.4}
transition_probability = {
'Healthy' : {'Healthy': 0.69, 'Fever': 0.3, 'E' = 0.01},
'Fever' : {'Healthy': 0.4, 'Fever': 0.59, 'E' = 0.01},
}
emission_probability = {
'Healthy' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},
}
</source>
We can write implementation like this:
<source lang="python">
def fwd_bkw(x, states, a_0, a, e, end_st):
L = len(x)
fwd = []
# Run forward
for i, x_i in enumerate(x):
f_curr = {}
for st in states:
if i == 0:
# Initialize base fwd cases
prev_f_sum = a_0[st]
else:
prev_f_sum = sum(f_prev[k]*a[k][st] for k in states)
f_curr[st] = e[st][x_i] * prev_f_sum
fwd.append(f_curr)
f_prev = f_curr
p_fwd = sum(f_curr[k]*a[k][end_st] for k in states)
bkw = []
# Run bkw
for i, x_i_plus in enumerate(reversed(x[1:]+(None,))):
b_curr = {}
for st in states:
if i == 0:
# Initialize base bkw cases
b_curr[st] = a[st][end_st]
else:
b_curr[st] = sum(a[st][l]*e[l][x_i_plus]*b_prev[l] for l in states)
bkw.insert(0,b_curr)
b_prev = b_curr
p_bkw = sum(a_0[l] * e[l][x[0]] * b_curr[l] for l in states)
posterior = {}
for st in states:
posterior[st] = [fwd[i][st]*bkw[i][st]/p_fwd for i in xrange(L)]
assert p_fwd = p_bkw
return fwd, bkw, posterior
</source>
The function <code>fwd_bkw</code> takes the following arguments:
<code>x</code> is the sequence of observations, e.g. <code>['normal', 'cold', 'dizzy']</code>;
<code>states</code> is the set of hidden states;
<code>a_0</code> is the start probability;
<code>a</code> are the transition probabilities;
and <code>e</code> are the emission probabilities.
For simplicity of code, we assume that the observation sequence <code>x</code> is non-empty and that <code>a[i][j]</code> and <code>e[i][j]</code> is defined for all states i,j.
In the running example, the forward-backward algorithm is used as follows:
<source lang="python">
def example():
return fwd_bkw(observations,
states,
start_probability,
transition_probability,
emission_probability,
end_state)
for line in example():
print ' '.join(map(str, line))
</source>
==See also ==
| |||