Content deleted Content added
→Performance: Linking. |
→Performance: fixed typo in reporting space complexoty from IJCAI 1997 paper. |
||
Line 288:
The forward–backward algorithm runs with time complexity <math> O(S^2 T) </math> in space <math> O(S T) </math>, where <math>T</math> is the length of the time sequence and <math>S</math> is the number of symbols in the state alphabet.<ref>[[#RussellNorvig10|Russell & Norvig 2010 pp. 579]]</ref> The algorithm can also run in constant space with time complexity <math> O(S^2 T^2) </math> by recomputing values at each step.<ref>[[#RussellNorvig10|Russell & Norvig 2010 pp. 575]]</ref> For comparison, a [[Brute-force search|brute-force procedure]] would generate all possible <math>S^T</math> state sequences and calculate the joint probability of each state sequence with the observed series of events, which would have [[time complexity]] <math> O(T \cdot S^T) </math>. Brute force is intractable for realistic problems, as the number of possible hidden node sequences typically is extremely high.
An enhancement to the general forward-backward algorithm, called the [[Island algorithm]], trades smaller memory usage for longer running time, taking <math> O(S^2 T \log T) </math> time and <math> O(S
In addition, algorithms have been developed to compute <math>\mathbf{f_{0:t+1}}</math> efficiently through online smoothing such as the fixed-lag smoothing (FLS) algorithm.<ref>[[#RussellNorvig10|Russell & Norvig 2010 Figure 15.6 pp. 580]]</ref>
| |||