Forward–backward algorithm: Difference between revisions

Revision as of 01:57, 18 July 2013

Revision as of 00:12, 1 August 2013

Line 140:

==Example ==

This example takes as its basis the umbrella world in [[#RusselNorvig03RussellNorvig03|RusselRussell & Norvig 2003 pp. 540]] in which we would like to infer the weather given observation of a man either carrying or not carrying an umbrella. We assume two possible states for the weather: state 1 = rain, state 2 = no rain. We assume that the weather has a 70% chance of staying the same each day and a 30% chance of changing. The transition probabilities are then:

:<math>\mathbf{T} = \begin{pmatrix}

Line 282:

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^2 \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^2 \log T)\, </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 [[#RusselNorvig03RussellNorvig03|RusselRussell & Norvig 2003 pp. 552]].

==Pseudocode==

Line 403:

*{{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}}

*{{cite book | author = Eugene Charniak|title = Statistical Language Learning|publisher = MIT Press|address = Cambridge, Massachusetts|year = 1993|isbn=978-0-262-53141-2}}

<cite id=RusselNorvig03RussellNorvig03>

*{{cite book | author = Stuart Russell and Peter Norvig|title = Artificial Intelligence A Modern Approach 2nd Edition|publisher = Pearson Education|address = Upper Saddle River, New Jersey|year = 2003|isbn=0-13-080302-2 | unused_data = ISBN status = May be invalid – please double check}}