Forward–backward algorithm: Difference between revisions

Revision as of 02:19, 3 September 2016

Revision as of 20:56, 27 September 2016

Line 24:

We transform the probability distributions related to a given [[hidden Markov model]] into matrix notation as follows.

The transition probabilities <math>\mathbf{P}(X_t\mid X_{t-1})</math> of a given random variable <math>X_t</math> representing all possible states in the hidden Markov model will be represented by the matrix <math>\mathbf{T}</math> where the rowcolumn index <math>i</math> will represent the target state and the columnrow index <math>j</math> represents the start state. A transition from row-vector state <math>\mathbf{\pi_t}</math> to the incremental row-vector state <math>\mathbf{\pi_{t+1}}</math> is written as <math>\mathbf{\pi_{t+1}} = \mathbf{\pi_{t}} \mathbf{T}</math>. The example below represents a system where the probability of staying in the same state after each step is 70% and the probability of transitioning to the other state is 30%. The transition matrix is then:

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

Line 40:

</math>

provides the probabilities for observing events given a particular state. In the above example, event 1 will be observed 90% of the time if we are in state 1 while event 2 has a 10% probability of occurring in this state. In contrast, event 1 will only be observed 20% of the time if we are in state 2 and event 2 has an 80% chance of occurring. Given aan statearbitrary row-vector describing the state of the system (<math>\mathbf{\pi}</math>), the probability of observing event j is then:

:<math>\mathbf{P}(O = j)=\sum_{i} \pi_i b_{i,j}</math>

This can be represented in matrix form by multiplying the state row-vector (<math>\mathbf{\pi}</math>) by an observation matrix (<math>\mathbf{O_j} = \mathrm{diag}(b_{*,o_j})</math>) containing only diagonal entries. Each entry is the probability of the observed event given each state. Continuing the above example, an observation of event 1 would be:

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

Line 52:

</math>

This allows us to calculate the unnormalized probabilities associated with transitioning to a new state and<math>\mathbf{\pi observing the'}</math> given that we observe event 1 as:

:<math>

\mathbf{f_{0:1}\pi '} = \mathbf{\pi} \mathbf{O_1}

</math>

The probability vector that results contains entries indicating the unnormalized probability of transitioning to each state and observing the given event. This processWe can benow carriedspecify forwardthis withprocess additionalto our series of observations. usingAssuming that our initial state vector is the equilibrium state vector, <math>\mathbf{\pi_{eq}}</math>, we begin with:

:<math>

\mathbf{f_{0:t0}} = \mathbf{T\pi_{eq}} \mathbf{O_tT} \mathbf{f_{0:t-1}O_t}

</math>

This process can be carried forward with additional observations using:

:<math>

\mathbf{f_{0:t}} = \mathbf{f_{0:t-1}} \mathbf{T} \mathbf{O_{o(t)}}

</math>

Line 67 ⟶ 73:

:<math>

\mathbf{f_{0:t}}(i) = \mathbf{P}(o_1, o_2, \dots, o_t, X_t=x_i | \mathbf{\pipi_{eq}} )

</math>

Line 73 ⟶ 79:

:<math>

\mathbf{\hat{f}_{0:t}} = c_t^{-1}\ \mathbf{Tf_{0:t-1}} \mathbf{O_tT} \mathbf{\hatO_{f}_{0:o(t-1)}}

</math>