Forward–backward algorithm: Difference between revisions

Revision as of 04:53, 28 February 2009

Revision as of 23:38, 2 March 2009

Line 1:

In [[computer science]], the '''forward-backward algorithm''' is a [[dynamic programming]]an [[algorithm]] for computing the [[probability]] of a particular observation sequence. It operates in the context of [[hidden Markov model]]s.

==Overview ==

Line 39:

Note that we use the non-transposed matrix of <math>\mathbf{T}</math> and that the order of the terms has changed. Also note that as a final product we have not a usual matrix multiplication, but a point product. This operation multiplies each value in one matrix with the corresponding value of the other. Finally note that the description in [[#RusselNorvig03|Russel & Norvig 2003 pp. 550]] excludes the point product, though the procedure is required earlier.

The third and final step involves the computation of smoothed probabilities <math>\mathbf{svtsv_k}</math>. These are the point product of the backward and forward probabilities for each tk. Therefore the formularformula is defined as:

<math>\mathbf{sv_tsv_k} = \alpha\mathbf{b_{k+1:t}}\times\mathbf{f_{1:k}}</math>

The example in the following section will show numerically the calculation of these matrices.