Forward algorithm

The forward algorithm (also forward algorithm , forward procedure ) uses so-called forward variables to calculate the probability of a specific observation for a given hidden Markov model . He uses the programming method of dynamic programming .

Markov model

The Markov model is defined as , 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 matrix of transition probabilities ,
• ${\displaystyle B}$ the matrix of the emission probabilities,
• ${\displaystyle \pi }$ the initial distribution for the possible initial states,

designated.

Task and forward variables

Given a word . The forward 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 forward variables are used for this. This stores the probability of having observed the prefix at the time and of being in the state : ${\displaystyle \alpha _{t}(i)}$ ${\displaystyle 1\leq t\leq T}$ ${\displaystyle o_{1}o_{2}\ldots o_{t}}$ ${\displaystyle s_{i}\in S}$

${\displaystyle \alpha _{t}(i)=P(o_{1}o_{2}\ldots o_{t};q_{t}=s_{i}|\lambda )}$

functionality

The forward variables, and thus also the overall probability, can be calculated recursively:

initialization

${\displaystyle \alpha _{1}(i)=\pi _{i}\cdot b_{i}(o_{1}),\qquad 1\leq i\leq \left|S\right|}$

Recursion

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

Termination

${\displaystyle P({\boldsymbol {o}}|\lambda )=\sum _{j=1}^{|S|}\alpha _{T}(j)}$

complexity

The algorithm requires operations and offers an efficient method for calculating the probability sought. The memory requirement lies in , since all are stored in a matrix to achieve the polynomial runtime . ${\displaystyle O(|S|^{2}\cdot T)}$ ${\displaystyle O(|S|\cdot T)}$ ${\displaystyle \alpha _{t}(i)}$ ${\displaystyle |S|\times T}$

If the intermediate results of for are not required after the end of the recursion, then the memory requirement is reduced to , since two column vectors of length are sufficient to store and in each recursion step. ${\displaystyle \alpha _{t}(i)}$ ${\displaystyle t<T}$ ${\displaystyle O(|S|)}$ ${\displaystyle |S|}$ ${\displaystyle \alpha _{t-1}(i)}$ ${\displaystyle \alpha _{t}(i)}$

Other uses

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

In addition, knowledge of this enables the determination of the probability of having been in the state when observing at a fixed point in time , 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

• Backward algorithm
• Viterbi algorithm
• Baum-Welch algorithm

literature

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

Web links

• EG Schukat-Talamazzini: Special pattern analysis systems (PDF, 1.3 MB) Lecture in WS 2012/13 at the University of Jena. Chapter 5 Slide 32ff.