Forward-backward algorithm

The forward-backward algorithm is a simple but effective method to find the transition probability matrix T given a sequence of observations o₁, o₂, ..., o_t. The first step is called the forward phase, and consists of determining the probability of a sequence of observations P(o₁, o₂, ..., o_{Sequence Length}|A, B). This piece of information can be directly useful if we need to know the likelihood of a sequence and it's necessary, together with the backward phase, to estimate the structure (A and B) of the underlying HMM.

Both algorithms are based on the concept of dynamic programming, which consists of splitting a complex problem into sub-problems that can be easily solved, and reusing the solutions to solve more complex steps in a recursive/iterative fashion. For further information on this, please refer to Dynamic Programming and Markov Process, Ronald A. Howard, The MIT Press.