Forward–backward algorithm: Difference between revisions

Revision as of 02:12, 16 October 2016

Revision as of 13:40, 15 February 2017

Line 327:

We can write implementation like this:

<source lang="python">

def fwd_bkw(xobservations, states, a_0start_prob, atrans_prob, eemm_prob, end_st):

L = len(x)

fwd = []

f_prev = {}

# forward part of the algorithm

for i, x_iobservation_i in enumerate(xobservations):

f_curr = {}

for st in states:

if i == 0:

# base case for the forward part

prev_f_sum = a_0start_prob[st]

else:

prev_f_sum = sum(f_prev[k]*atrans_prob[k][st] for k in states)

f_curr[st] = eemm_prob[st][x_iobservation_i] * prev_f_sum

fwd.append(f_curr)

f_prev = f_curr

p_fwd = sum(f_curr[k] *a trans_prob[k][end_st] for k in states)

bkw = []

b_prev = {}

# backward part of the algorithm

for i, x_i_plusobservation_i_plus in enumerate(reversed(xobservations[1:]+(None,))):

b_curr = {}

for st in states:

if i == 0:

# base case for backward part

b_curr[st] = atrans_prob[st][end_st]

else:

b_curr[st] = sum(atrans_prob[st][l] *e emm_prob[l][x_i_plusobservation_i_plus] * b_prev[l] for l in states)

bkw.insert(0,b_curr)

b_prev = b_curr

p_bkw = sum(a_0start_prob[l] * eemm_prob[l][xobservations[0]] * b_curr[l] for l in states)

# merging the two parts

posterior = []

for i in range(Llen(observations)):

posterior.append({st: fwd[i][st] * bkw[i][st] / p_fwd for st in states})

assert p_fwd == p_bkw

return fwd, bkw, posterior