The Evaluation Problem and the Forward Algorithm next up previous
Next: The Decoding Problem and Up: Three basic problems of Previous: Three basic problems of

The Evaluation Problem and the Forward Algorithm

We have a model tex2html_wrap_inline2698 and a sequence of observations tex2html_wrap_inline2682 , and tex2html_wrap_inline2684 must be found. We can calculate this quantity using simple probabilistic arguments. But this calculation involves number of operations in the order of tex2html_wrap_inline2704 . This is very large even if the length of the sequence, T is moderate. Therefore we have to look for an other method for this calculation. Fortunately there exists one which has a considerably low complexity and makes use an auxiliary variable, tex2html_wrap_inline2708 called forward variable.

The forward variable is defined as the probability of the partial observation sequence tex2html_wrap_inline2710 , when it terminates at the state i. Mathematically,


Then it is easy to see that following recursive relationship holds.




Using this recursion we can calculate


and then the required probability is given by,


The complexity of this method, known as the forward algorithm is proportional to tex2html_wrap_inline2728 , which is linear wrt T whereas the direct calculation mentioned earlier, had an exponential complexity.

In a similar way we can define the backward variable tex2html_wrap_inline2732 as the probability of the partial observation sequence tex2html_wrap_inline2734 , given that the current state is i. Mathematically ,


As in the case of tex2html_wrap_inline2708 there is a recursive relationship which can be used to calculate tex2html_wrap_inline2732 efficiently.




Further we can see that,


Therefore this gives another way to calculate tex2html_wrap_inline2684 , by using both forward and backward variables as given in eqn. 1.7.


Eqn. 1.7 is very useful, specially in deriving the formulas required for gradient based training.

Narada Warakagoda
Fri May 10 20:35:10 MET DST 1996

Home Page