Content deleted Content added
m →Example |
→Performance: Linking. |
||
Line 286:
==Performance ==
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^2 \log T) </math> memory. Furthermore, it is possible to invert the process model to obtain an <math>O(S)</math> space, <math>O(S^2 T)</math> time algorithm, although the inverted process may not exist or be [[ill-conditioned]].<ref>{{cite journal |last1=Binder |first1=John |last2=Murphy |first2=Kevin |last3=Russell |first3=Stuart |title=Space-efficient inference in dynamic probabilistic networks |journal=Int'l, Joint Conf. On Artificial Intelligence |date=1997 |url=https://www.cs.ubc.ca/~murphyk/Papers/ijcai97.pdf |access-date=8 July 2020}}</ref>
| |||