Content deleted Content added
Line 286:
The brute-force procedure for the solution of this problem is the generation of all possible <math>N^T</math> state sequences and calculating the joint probability of each state sequence with the observed series of events. This approach 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>.
An enhancement to the general forward-backward algorithm, called the [[Island algorithm]], trades smaller memory usage for longer running time, taking <math> O(N^2 T \log T)\, </math> time and <math> O(N \log T)\, </math> memory. On a computer with an unlimited number of processors, this can be reduced to <math> O(N^2 T)\, </math> total time, while still taking only <math> O(N
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 [[#RussellNorvig10|Russell & Norvig 2010 Figure 15.6 pp. 580]].
| |||