CS345, Machine Learning
Prof. Alvarez

The Forward-Backward Algorithm

This algorithm addresses the issue of estimating the parameters of a Hidden Markov Model (HMM) that are most likely to generate an observed sequence y₁...y_k of output values. The underlying topology of the HMM is assumed to be known in advance. The objective is to find the values of the state transition probabilities and the output probabilities for each state for which the likelihood of the observed output sequence is maximized. The forward-backward algorithm may be viewed as an Expectation Maximization (EM) approach to this problem.

Key Quantities

The forward-backward algorithm iteratively updates probability estimates using pseudo-counts associated with a given output sequence y₁...y_k. The key target quantities are the following:

P*(i,s',s) = P(y₁...y_k observed AND i-th state transition is s--> s')
c(s --> s') = sum from i=0 to i=k of P*(i, s', s)

Notice that c is defined in terms of P*. In turn, P* can be computed from intermediate quantities alpha_i(s) and beta_i(s) defined as follows:

alpha_i(s) = P(y₁...y_i observed AND i-th state is s)
beta_i(s) = P(y_i+1...y_k observed AND i-th state is s)

In fact, we have:

P*(i,s',s) = alpha_i(s)*p_s'<--s*q(y_i+1 | s'<--s)*beta_i+1(s')

The forward-backward algorithm updates the alphas and betas and then computes maximum likelihood estimates for P* and c using the preceding expressions. See the pseudocode below.

Forward-Backward Algorithm Pseudocode

Iterate the following stages until the termination condition is met:

Forward stage

Initialize alpha₀(start state) = 1, and alpha₀(s) = 0 for all other states s
Repeat for each i from 0 up to k-1:
For each state s: alpha_i+1(s) = sum_{all states s'} alpha_i(s')*p_s,s'*q(y_i+1 | s <-- s')

Backward stage

Initialize beta_k(s) = 1 for all states s
Repeat for each i from k down to 1:
For each state s: beta_i-1(s) = sum_{all states s'} p_s',s*q(y_i | s' <-- s)*beta_i(s')

Parameter updating

Define
P*(i, s', s) = alpha_i(s)*p_s',s*q(y_i+1 | s' <-- s)*beta_i+1(s')
and
c(s',s) = sum_i=0...k-1 P*(i,s',s)
Then update the HMM parameters using the following maximum likelihood estimates:
p_s',s = c(s',s) / sum_{all states s'' leaving s} c(s'',s)
q(y | s' <-- s) = sum_{each i=0...k-1 such that y_i=y} P*(i,s',s) / c(s',s)