Forward algorithm definition
We use the forward algorithm to calculate the probability of a T long observation sequence;
![[Formula]](http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/graphics/5.2_1.gif)
where each of the y is one of the observable set. Intermediate probabilities (
′s) are calculated recursively by first calculating for all states at t=1.
![[Formula]](http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/graphics/5.2_2.gif)
is calculated for each state;
![[Formula]](http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/graphics/5.2_3.gif)
that is, the product of the appropriate observation probability and the sum over all possible routes to that state, exploiting recursion by knowing these values already for the previous time step. 数据挖掘研究院
Finally the sum of all partial probabilities gives the probability of the observation, given the HMM, 
.
![[Formula]](http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/forward_algorithm/graphics/5.2_4.gif)
To recap, each partial probability (at time t > 2) is calculated from all the previous states. 数据挖掘研究院
Using the `weather′ example, the diagram below shows the calculation for at t = 2 for the cloudy state. This is the product of the appropriate observation probability b and the sum of the previous partial probabilities multiplied by the transition probabilities . 数据挖掘研究院
