Forward-Backward

Summary

This is a dynamic programming algorithm, used in Hidden Markov Models to efficiently compute the state posteriors over all the hidden state variables.

These values are then used in Posterior Decoding, which simply chooses the state with the highest posterior marginal for each position in the sequence.

The forward-backward algorithm can be computed in linear time, where as, a brute force algorithm that checks all possible state sequences would be exponential over the length of the sequence.

Problem description

Posterior decoding consists in picking the highest state posterior for each position in the sequence:

${\hat {y}}^{*}=argmax_{y_{1},\dots ,y_{N}}\gamma _{i}(y_{i})$

where $\gamma _{i}$ is the state posterior for position $i$ . The state posterior is given by:

$\gamma _{i}(s_{l})=P_{\theta }(y_{i}=s_{1}|{\bar {x}})$

where $P_{\theta }(y_{i}=s_{1}|{\bar {x}})$ is sequence posterior of all possible state sequences where the position $i$ is the state $s_{l}$ .

The sequence posterior $P_{\theta }({\bar {y}}|{\bar {x}})$ for a given sequence ${\bar {y}}$ is defined as:

$P_{\theta }({\bar {y}}|{\bar {x}})={\frac {P_{\theta }({\bar {x}},{\bar {y}})}{\sum _{\bar {y}}P_{\theta }({\bar {x}},{\bar {y}})}}$

$P_{\theta }({\bar {x}},{\bar {y}})$ is calculated as the product of all node potentials $\phi (s_{l})$ of the nodes in the sequence, corresponding to the state observation parameters for the state $s_{l}$ , and the transition potentials $\phi (s_{1},s_{n})$ of the transition in the sequence, corresponding to the translation parameters. These potentials are estimated during the training process of Hidden Markov Models. As an example the sequence in red in the following figure would be calculated as $\phi _{1}(r)\phi _{!}(r,s)\phi _{2}(s)\phi _{2}(s,s)\phi _{3}(s)\phi _{3}(s,s)\phi _{4}(s)$ .

Thus, to calculate all \gamma_2(r), for instance, we would need to sum the sequence posteriors for the sequences r r r r, s r r r, r r s r, s r s r, r r r s, s r r s, r r s s and s r s s. A brute force algorithm would compute the sequence posteriors separately. This would mean that the number of computations to calculate a single potential would be in the order of $(number\ of\ possible\ states)^{(number\ of\ states\ in\ the\ sequence)}$ .