Forward–backward algorithm: Difference between revisions

Revision as of 00:11, 7 November 2012

Revision as of 00:14, 7 November 2012

Line 280:

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:, whiletaking belief propagation takes<math> O(n)N^2 timeT and\log O(nT) memory\, the</math> islandtime algorithmand takes<math> O(nN^2 \log nT)\, time and O(log n)</math> memory. On a computer with an unlimited number of processors, this can be reduced to <math> O(nN^2 T)\, </math> total time, while still taking only <math> O(N^2 \log nT)\, </math> memory.<ref>J. Binder, K. Murphy and S. Russell. Space-Efficient Inference in Dynamic Probabilistic Networks. Int'l, Joint Conf. on Artificial Intelligence, 1997.</ref>

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 [[#RusselNorvig03|Russel & Norvig 2003 pp. 552]].