Forward–backward algorithm: Difference between revisions

Revision as of 06:51, 14 October 2008

Revision as of 16:41, 24 October 2008

Line 35:

We can describe the backward computation <math>\mathbf{b_{k+1:t}}</math> that starts at the end of the sequence in a similar manner. Let the end of the sequence be described by the index k, starting at 0. Therefore running from k down to t=0 and calculating each backward probability can be described by the following formula:

<math>\mathbf{b_{k+1:t}} = \alpha(\mathbf{T}\mathbf{O_{k+1}}\mathbf{b_{k+2t}})\times\mathbf{f_{1:t}}</math>

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, thought the procedure is required earlier.

Line 83:

Now that we have defined the forward probabilities, we continue to compute the backward probabilities. Again the matrices appear in the order as in the backward formula above.

=> Someone should recompute the final results because the formula for the backward message was previously wrong and was corrected in the following equations, but not the final matrix.

<math>

\mathbf{b_{5:5}} = \alpha(\begin{pmatrix} 0.7 & 0.3 \\ 0.3 & 0.7 \end{pmatrix}\begin{pmatrix}0.9 & 0.0 \\ 0.0 & 0.2 \end{pmatrix}\begin{pmatrix}1.0000 & 1.0000 \end{pmatrix})\times \begin{pmatrix}0.8673 & 0.1326 \end{pmatrix}=\alpha\begin{pmatrix}0.5984 & 0.0543\end{pmatrix}=\begin{pmatrix}0.9168 & 0.0831 \end{pmatrix}

</math>

<math>

\mathbf{b_{4:5}} = \alpha(\begin{pmatrix} 0.7 & 0.3 \\ 0.3 & 0.7 \end{pmatrix}\begin{pmatrix}0.9 & 0.0 \\ 0.0 & 0.2 \end{pmatrix}\begin{pmatrix}0.9168 & 0.0831 \end{pmatrix})\times \begin{pmatrix}0.7308 & 0.2691 \end{pmatrix}=\alpha\begin{pmatrix}0.7308 & 0.2691\end{pmatrix}=\begin{pmatrix}0.8593 & 0.1407 \end{pmatrix}

</math>

<math>

\mathbf{b_{3:5}} = \alpha(\begin{pmatrix} 0.7 & 0.3 \\ 0.3 & 0.7 \end{pmatrix}\begin{pmatrix}0.1 & 0.0 \\ 0.0 & 0.8 \end{pmatrix}\begin{pmatrix}0.8593 & 0.1407 \end{pmatrix})\times \begin{pmatrix}0.1906 & 0.8093 \end{pmatrix}=\alpha\begin{pmatrix}0.0178 & 0.0845\end{pmatrix}=\begin{pmatrix}0.1739 & 0.8260 \end{pmatrix}

</math>

<math>

\mathbf{b_{2:5}} = \alpha(\begin{pmatrix} 0.7 & 0.3 \\ 0.3 & 0.7 \end{pmatrix}\begin{pmatrix}0.9 & 0.0 \\ 0.0 & 0.2 \end{pmatrix}\begin{pmatrix}0.1739 & 0.8260 \end{pmatrix})\times \begin{pmatrix}0.8834 & 0.1165 \end{pmatrix}=\alpha\begin{pmatrix}0.1405 & 0.0189\end{pmatrix}=\begin{pmatrix}0.8814 & 0.1185 \end{pmatrix}

</math>

<math>

\mathbf{b_{1:5}} = \alpha(\begin{pmatrix} 0.7 & 0.3 \\ 0.3 & 0.7 \end{pmatrix}\begin{pmatrix}0.9 & 0.0 \\ 0.0 & 0.2 \end{pmatrix}\begin{pmatrix}0.8814 & 0.1185 \end{pmatrix})\times \begin{pmatrix}0.8182 & 0.1818 \end{pmatrix}=\alpha\begin{pmatrix}0.4600 & 0.0462\end{pmatrix}=\begin{pmatrix}0.9087 & 0.0912 \end{pmatrix}

</math>