Forward-backward algorithm
Dr Sohail Iqbal
Outline
• Forward and backward probability
• Expected counts and update formulae
• Let’s break this into Forward, Backward,
and Complete Picture with Dynamic
programing!
HMM
• A HMM is a tuple ( S , , , A, B) :
– A set of states S={X1, X2, …, XN}.
– A set of output symbols Σ={w1, …, wM}.
– Initial state probabilities
= { i }
– State transition prob: A={aij}.
– Symbol emission prob: B={bijk}
• State sequence: X1…XT+1
• Output sequence: o1…oT
Constraints
N
i =1
i =1
N
a ij =1
j =1
M
a b
k j
ij ijk =1
b
k =1
ijk =1
White Boarding
Forward and backward
Algorithm Steps
If X0, X1, … , Xn are the hidden states and
Y0, Y1, …. Yn are the observed states then
We need to compute: P(Y= Y0, Y0, Y1)
Forward Backward Algorithm
(Pseudocode)
Code source:
https://en.wikipedia.org/wiki/Forward%E2%80%93backward_algorithm
• Python example
• [edit]
• Given HMM (just like in Viterbi algorithm) represented in the Python programming language:
• 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}, }
• We can write the implementation of the forward-backward algorithm like this:
• def fwd_bkw(observations, states, start_prob, trans_prob, emm_prob, end_st): """Forward–backward algorithm.""" # Forward
part of the algorithm fwd = [] for i, observation_i in enumerate(observations): f_curr = {} for st in states: if i == 0: # base case
for the forward part prev_f_sum = start_prob[st] else: prev_f_sum = sum(f_prev[k] * trans_prob[k][st] for k in states) f_curr[st]
= emm_prob[st][observation_i] * prev_f_sum fwd.append(f_curr) f_prev = f_curr p_fwd = sum(f_curr[k] * trans_prob[k][end_st]
for k in states) # Backward part of the algorithm bkw = [] for i, observation_i_plus in enumerate(reversed(observations[1:] +
(None,))): b_curr = {} for st in states: if i == 0: # base case for backward part b_curr[st] = trans_prob[st][end_st] else:
b_curr[st] = sum(trans_prob[st][l] * emm_prob[l][observation_i_plus] * b_prev[l] for l in states) bkw.insert(0,b_curr) b_prev =
b_curr p_bkw = sum(start_prob[l] * emm_prob[l][observations[0]] * b_curr[l] for l in states) # Merging the two parts posterior
= [] for i in range(len(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
•
Be Ready for Quiz
Helpful links
• https://www.youtube.com/watch?v=9-sPm4CfcD0&list=PLM8wYQRetTxBkdvBtz-
gw8b9lcVkdXQKV&index=6
• https://www.youtube.com/watch?v=G7FIQ9fXl6U
Questions?
Thank You!
