Forward–backward algorithm: Difference between revisions

Revision as of 13:57, 31 October 2012

Revision as of 00:11, 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: while belief propagation takes O(n) time and O(n) memory, the island algorithm takes O(n log n) time and O(log n) memory. On a computer with an unlimited number of processors, this can be reduced to O(n) total time, while still taking only O(log n) 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>

Several enhancements are known to the general forward–backward algorithm which allow for computations to take place in constant space. In addition, as it grows, 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]].

Several enhancements are known to the general forward–backward algorithm which allow for computations to take place in constant space. In addition, as it grows, 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]].

==Pseudocode==

Line 389 ⟶ 391:

* [[Viterbi algorithm]]

* [[BCJR algorithm]]

== References==

{{reflist}}

* [[Lawrence Rabiner|Lawrence R. Rabiner]], A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. ''Proceedings of the [[IEEE]]'', 77 (2), p.&nbsp;257–286, February 1989. [http://dx.doi.org/10.1109/5.18626 10.1109/5.18626]

*{{cite journal |author=Lawrence R. Rabiner, B. H. Juang|title=An introduction to hidden Markov models|journal=IEEE ASSP Magazine |month=January |pages=4–15 |year=1986}}