Solving Problem 1: The Evaluation Problem

One method is to use the law of total probability and condition on all possible state sequences, I, of length T: P(O|$\lambda$) = $\sum_{I}^{}$P(O| I,$\lambda$)×P(I|$\lambda$). The probability of a given sequence of states is simple: P(I|$\lambda$) = $\pi_{I_{1}}^{}$×a_{I1, I2}×...×a_{IT - 1, IT}. The probability of a given observation sequence given a state sequence is also simple: P(O| I,$\lambda$) = b_I1(O₁)×...×b_IT(O_T). But the number of state sequences is exponential, so this is a poor method.

The standard approach is to use the forward-backward procedure, which takes advantage of the Markov property, namely that the path to a state is irrelevant to the future behavior of the process after being in that state. First we define

$$\alpha_{t}^{}$$(j) = P(O₁,..., O_t, I_t = j|$$\lambda$$),

which is the probability of the process producing the first t observations and of ending up in state j at time t. P(O|$\lambda$) is easily calculated from $\alpha_{T}^{}$.

To see this, we first apply the chain rule and get $\alpha_{t}^{}$(j) = P(I_t = j|$\lambda$)×P(O₁,..., O_t| I_t = j,$\lambda$). Next we note that the law of total probability tells us that

P(O₁,... O_t|$$\lambda$$) = $$\sum_{j\in Q}^{}$$$$\left[\vphantom{ P(O_{1},\ldots ,O_{t}\vert I_{t}=j,\lambda )\times P(I_{t}=j\vert\lambda )}\right.$$P(O₁,..., O_t| I_t = j,$$\lambda$$)×P(I_t = j|$$\lambda$$)$$\left.\vphantom{ P(O_{1},\ldots ,O_{t}\vert I_{t}=j,\lambda )\times P(I_{t}=j\vert\lambda )}\right]$$ = $$\sum_{j\in Q}^{}$$$$\alpha_{t}^{}$$(j)

which becomes P(O|$\lambda$) = $\sum_{j\in Q}^{}$$\alpha_{T}^{}$(j) when we want the entire observation considered.

Moverover, $\alpha_{T}^{}$ is easily calculated iteratively:

1. $$\alpha_{1}^{}$$(i) = $$\pi_{i}^{}$$×b_i(O₁)

2. $$\alpha_{t+1}^{}$$(i) = $$\left[\vphantom{ \sum _{j\in Q}\alpha _{t}(j)\times a_{j,i}}\right.$$$$\sum_{j\in Q}^{}$$$$\alpha_{t}^{}$$(j)×a_{j, i}$$\left.\vphantom{ \sum _{j\in Q}\alpha _{t}(j)\times a_{j,i}}\right]$$×b_i(O_{t + 1})

Notice that calculating P(O|$\lambda$) requires on the order of N×T calculations using $\alpha_{T}^{}$ as compared to requiring an exponential number of calculations.

$\alpha_{t}^{}$ represents the forward part, and $\beta_{t}^{}$ represents the backward part. Let

$$\beta_{t}^{}$$(j) = P(O_{t + 1}, O_{t + 2},..., O_T| I_t = j,$$\lambda$$),

which is the probability of the process being in state j at time t and also of producing the observations from time t + 1 to T.

We can also use $\beta$ to determine P(O|$\lambda$).

P(O₁,..., O_T|$$\lambda$$) = P(O₁|$$\lambda$$)×P(O₂,..., O_T| O₁,$$\lambda$$).

First we calculate P(O₁|$\lambda$):

P(O₁|$$\lambda$$) = $$\sum_{j\in Q}^{}$$$$\left[\vphantom{ P(O_{1}\vert I_{1}=j,\lambda )\times P(I_{1}=j\vert\lambda )}\right.$$P(O₁| I₁ = j,$$\lambda$$)×P(I₁ = j|$$\lambda$$)$$\left.\vphantom{ P(O_{1}\vert I_{1}=j,\lambda )\times P(I_{1}=j\vert\lambda )}\right]$$ = $$\sum_{j\in Q}^{}$$$$\left[\vphantom{ b_{j}(O_{1})\times \pi _{j}}\right.$$b_j(O₁)×$$\pi_{j}^{}$$$$\left.\vphantom{ b_{j}(O_{1})\times \pi _{j}}\right]$$.

Next, we calculate P(O₂,..., O_T| O₁,$\lambda$):

P(O₂,..., O_T| O₁,$$\lambda$$) = $$\sum_{j\in Q}^{}$$$$\left[\vphantom{ P(O_{2},\ldots ,O_{T}\vert O_{1},I_{1}=j,\lambda )\times P(I_{1}=j\vert\lambda )}\right.$$P(O₂,..., O_T| O₁, I₁ = j,$$\lambda$$)×P(I₁ = j|$$\lambda$$)$$\left.\vphantom{ P(O_{2},\ldots ,O_{T}\vert O_{1},I_{1}=j,\lambda )\times P(I_{1}=j\vert\lambda )}\right]$$.

But once we condition on I₁ = j then we can ignore the conditions O₁ because knowing the obsevation produced at time 1 gives us no more information once we know the state at time 1. Thus, we get the simplification

P(O₂,..., O_T| O₁,$$\lambda$$) = $$\sum_{j\in Q}^{}$$$$\left[\vphantom{ P(O_{2},\ldots ,O_{T}\vert I_{1}=j,\lambda )\times P(I_{1}=j\vert\lambda )}\right.$$P(O₂,..., O_T| I₁ = j,$$\lambda$$)×P(I₁ = j|$$\lambda$$)$$\left.\vphantom{ P(O_{2},\ldots ,O_{T}\vert I_{1}=j,\lambda )\times P(I_{1}=j\vert\lambda )}\right]$$ = $$\sum_{j\in Q}^{}$$$$\left[\vphantom{ \beta _{1}(j)\times \pi _{j}}\right.$$$$\beta_{1}^{}$$(j)×$$\pi_{j}^{}$$$$\left.\vphantom{ \beta _{1}(j)\times \pi _{j}}\right]$$.

Putting these together, we get

P(O₁,..., O_T|$$\lambda$$) = $$\sum_{j\in Q}^{}$$$$\left[\vphantom{ b_{j}(O_{1})\times \pi _{j}}\right.$$b_j(O₁)×$$\pi_{j}^{}$$$$\left.\vphantom{ b_{j}(O_{1})\times \pi _{j}}\right]$$×$$\sum_{j\in Q}^{}$$$$\left[\vphantom{ \beta _{1}(j)\times \pi _{j}}\right.$$$$\beta_{1}^{}$$(j)×$$\pi_{j}^{}$$$$\left.\vphantom{ \beta _{1}(j)\times \pi _{j}}\right]$$.

$\beta_{t}^{}$ is also calculated easily.

1. $$\beta_{T}^{}$$(i) = 1

2. $$\beta_{t}^{}$$(i) = $$\sum_{j\in Q}^{}$$a_{i, j}×b_j(O_{t + 1})×$$\beta_{t+1}^{}$$(j)

There are a few useful quantities that we can calculate with $\alpha$ and $\beta$ that we now note.