Backward algorithm

The backward algorithm (also backward algorithm, backward procedure) uses backward variables to calculate the probability of observing a certain symbol sequence in a given hidden Markov model (HMM). The algorithm uses the programming method of dynamic programming .

Markov model

Given an HMM , where ${\displaystyle \lambda =(S;V;A;B;\pi )}$

• ${\displaystyle S}$ the set of hidden states,
• ${\displaystyle V}$the alphabet of observable symbols,
• ${\displaystyle A}$the transition matrix ,
• ${\displaystyle B}$ the matrix of the emission probabilities,
• ${\displaystyle \pi }$ the initial probability distribution for the possible initial states,

designated.

Task and backward variables

Given a word . The backward algorithm now calculates the probability of actually making the observation in the existing model . ${\displaystyle {\boldsymbol {o}}=o_{1}o_{2}\dots o_{T}\in V^{*}}$ ${\displaystyle P({\boldsymbol {o}}|\lambda )}$ ${\displaystyle \lambda }$ ${\displaystyle {\boldsymbol {o}}}$

The backward variables are used for this; they indicate the probability of observing the suffix if the HMM was in the state at the time : ${\displaystyle \beta _{t}(i)}$ ${\displaystyle o_{t+1}o_{t+2}\ldots o_{T}}$ ${\displaystyle 1\leq t\leq T}$ ${\displaystyle s_{i}\in S}$

${\displaystyle \beta _{t}(i)=P(o_{t+1}o_{t+2}\dotsc o_{T}|q_{t}=s_{i};\lambda )}$

algorithm

The backward variables are determined recursively:

initialization

${\displaystyle \beta _{T}(i)=1,\qquad 1\leq i\leq \left|S\right|}$

Recursion

${\displaystyle \beta _{t}(i)=\sum _{j=1}^{\left|S\right|}b_{j}(o_{t+1})\cdot a_{ij}\cdot \beta _{t+1}(j),\qquad 1\leq i\leq \left|S\right|,\ 1\leq t<T}$

Termination

${\displaystyle P({\boldsymbol {o}}|\lambda )=\sum _{j=1}^{\left|S\right|}\pi _{j}\cdot b_{j}(o_{1})\cdot \beta _{1}(j)}$

complexity

The matrix of all backward variables needs memory, if the intermediate results are no longer used, the space requirement is reduced , since only two columns of length are required to save the values ​​of and in each recursion step. ${\displaystyle O(|S|\cdot T)}$ ${\displaystyle O(|S|)}$ ${\displaystyle |S|}$ ${\displaystyle \beta _{t+1}(i)}$ ${\displaystyle \beta _{t}(i)}$

Lines are totaled for each individual variable , so the runtime is in . ${\displaystyle |S|}$ ${\displaystyle O(|S|^{2}\cdot T)}$

Other uses

The backward variables are required together with the forward variables for the Baum-Welch algorithm to solve the learning problem given with hidden Markov models. ${\displaystyle \beta _{t}(i)}$ ${\displaystyle \alpha _{t}(i)=P(o_{1},o_{2},\ldots ,o_{t},q_{t}=s_{i}|\lambda )}$

In addition, knowledge of this enables the determination of the probability of having been in the state at a fixed point in time when observing , because according to Bayes' theorem: ${\displaystyle {\boldsymbol {o}}}$ ${\displaystyle t}$ ${\displaystyle s_{i}}$

${\displaystyle P(q_{t}=s_{i}|{\boldsymbol {o}};\lambda )={\frac {\alpha _{t}(i)\cdot \beta _{t}(i)}{P({\boldsymbol {o}}|\lambda )}}}$

See also

• Forward algorithm
• Viterbi algorithm
• Baum-Welch algorithm

literature

• Richard Durbin, Sean R. Eddy, Anders Krogh, Graeme Mitchison: Biological sequence analysis. Probabilistic models of proteins and nucleic acids . 11th printing, corrected 10th reprinting. Cambridge University Press, Cambridge et al. 2006, ISBN 0-521-62971-3 , pp. 59-60 .

Web links

• Ernst G. Schukat-Talamazzini: Special pattern analysis systems. (PDF, 1.3 MB). Lecture in the winter semester 2012/2013 at the University of Jena. Chapter 5, slide 34 ff.