Forward–backward algorithm: Difference between revisions

Revision as of 12:46, 10 April 2013

Revision as of 20:20, 10 April 2013

Line 320:

def fwd_bkw(x, states, a_0, a, e, end_st):

L = len(x)

fwd = []

# Run forward

for l, x_i in enumerate(x):

fwd = []

f_prev = {}

# forward part of the algorithm

f_curr = {}

for li, x_i in enumerate(x):

fwdf_curr = []{}

for st in states:

if i == 0:

# base case for the forward part

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[lk]*a[lk][end_st] for k in states)

bkw = []

b_prev = {}

# backward part of the algorithm

# Run bkw

for i, x_i_plus in enumerate(reversed(x[1:]+(None,))):

p_bkw = sum(a_0[1] * e[l][x[1]] * b_curr[0] for l in= states){}

for st in states:

if i == 0:

# base case for backward part

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)

# merging the two parts

posterior = {}

for st in states:

posterior[st] = [fwd[i][st]*bkw[i][st]/p_fwd for i in xrangerange(L)]

assert p_fwd == p_bkw

return fwd, bkw, posterior

</source>

Line 362 ⟶ 380:

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>