Content deleted Content added
copied pseudo code from talk page |
|||
Line 114:
The brute force procedure for the solution of this problem is the generation of all possible sequences of observed events and hidden states with their probabilities using the two transition matrices. The joint probability of two sequences, given the model, is calculated by multiplying the corresponding probabilities. The brute force procedure has [[time complexity]] <math> O(T \cdot N^T) </math>, where <math>T</math> is the length of sequences and <math>N</math> is the number of symbols in the state alphabet. This is intractable for realistic problems, as the number of possible hidden node sequences typically is extremely high. However, the forward-backward algorithm has time complexity <math> O(N^2 T)\, </math>.
Several enhancements are known to the general forward-backward algorithm which allow for computations to take place in constant space. In addition, as t grows, algorithms have been developed to compute <math>\mathbf{f_{1:t+1}}</math> efficiently through online smoothing such as the fixed-lag smoothing algorithm [[#RusselNorvig03|Russel & Norvig 2003 pp. 552]].
==Pseudo code==
<code><pre>
ForwardBackward(guessState, sequenceIndex):
if sequenceIndex is past the end of the sequence, return 1
if (guessState, sequenceIndex) has been seen before, return saved result
result = 0
for each neighboring state n:
result = result + (transition probability from guessState to n given observation element at sequenceIndex)*ForwardBackward(n, sequenceIndex+1)
save result for (guessState, sequenceIndex)
return result
</pre></code>
==See also==
| |||