2
$\begingroup$

I am studying the the forward-backward algorithm used in Hidden Markov Models. I understand that you are trying to propagate through a sequence (and the available states) to find the most probable state in the model at any given time.

I am however struggling with the following notation (for a forward variable) where the probability of being in state $i$ at time $t$ having observed letters $X^{1} ...X^{t}$ in a model $M(\omega)$ is:

$\alpha_{i}(t) = P(S^t = I,X^{1} ...X^{t}|\omega)$

where the start state is initialized as:

$\alpha_{start}(0) = 1$

which is fine. However where I am struggling is how to compute $\alpha_{i}(t)$ recursively by propagations i.e.

$\alpha_{i}(t+1) = \sum\limits_{j \in S} \alpha_{j}(t)t_{ij}e_{iX^{t+1}} = \sum\limits_{j \in N^{-}(i)} \alpha_{j}(t)t_{ij}e_{iX^{t+1}}$

where $e_{iX^{t}}$ are emissions and $t_{ij}$ are transitions, and $\sum\limits_{j \in N^{-}(i)}$ is the neighbourhood notation which I interpret as instead of state $j$ being in all states, it is found in from the previous state (although correct me if I'm wrong!).

To my eyes this reads as "I can calculate the probability of being in the next state at $t+1$ given the observed sequence by calculating the probability of being in state $j$ at time $t$ having observed the letters $X^{1} ...X^{t}$.

But what I don't understand is........how is $\alpha_{j}(t)$ any different to $\alpha_{i}(t+1)$?

Even more confusing for me is when you propagate through a state where there is no emission observed (imagine flipping a coin but it landing on a small table where if it falls off the emission is not recorded, but the fall is) the equation is modified to:

$\alpha(t+1) = \sum\limits_{j \in N^{-}(i)} \alpha_{j}(t+1)t_{ij}$

where the only explanation for $t+1$ appearing both sides of the equation is because iterating the equation leads to a stable set of values $\alpha_{i}(t+1)$

I know that the Markov property is that the probability of being in a certain state is only dependent on the previous state, but this notation is confusing me.

If anyone could explain this in simple terms (perhaps on an abstract example) then that would be great.

Thanks.

$\endgroup$

1 Answer 1

4
$\begingroup$

I'm not sure this is exactly what you're looking for, but let me see if I can make these things a bit clearer by translating them into a more conventional probability theory notation. Let me know if I've misunderstood your question.

Suppose first that the model didn't have any state transitions, but just a single unknown state $S_{t+1}$ and a single observed signal $X_{t+1}$. Then the posterior distribution over $S_{t+1}$ could be computed by

$$\Pr(S_{t+1} | \;X_{t+1}) \;\propto\; \Pr(X_{t+1}|\;S_{t+1})\Pr(S_{t+1})$$

In a hidden Markov model, however, you have a bit more information than this: You also know that $S_{t+1}$ depends on $S_t$. You therefore want to incorporate this information into your computation of the posterior distribution over $S_{t+1}$.

Since $S_{t}$ is a random variable (whose value you only know probabilistically), you need to do this by marginalization, i.e., by integrating out the uncertainty about $S_{t}$:

\begin{eqnarray} \Pr(S_{t+1}=i\;|\;X_{t+1}) & = & \sum_{j} \Pr(S_{t+1}=i, S_t=j\;|\;X_{t+1}) \\ & \propto & \sum_{j} \Pr(X_{t+1}\ |\;S_{t+1}=i, S_t=j) \Pr(S_{t+1}=i, S_t=j). \end{eqnarray}

Since $S_t$ and $X_{t+1}$ are conditionally independent given $S_{t+1}$, this is equal to

$$ \sum_{j} \Pr(X_{t+1}\ |\;S_{t+1}=i) \Pr(S_{t+1}=i, S_t=j). $$

By the chain rule of probability, we can expand this into

$$ \sum_{j} \Pr(X_{t+1}\ |\;S_{t+1}=i) \Pr(S_{t+1}=i\ |\ S_t=j) \Pr(S_t=j). $$

These three factors are the emission probability, the transition probability, and the previous state probability; or in your notation, entries that you can look up in the tables $e$, $t$, and $\alpha$.

Specifically, the probabilities $\Pr(S_t=j)$ are the values which were computed in the previous step and stored i table entries of the form $\alpha_j(t)$. The posterior probabilities $\Pr(S_{t+1}=i\ |\ X_{t+1})$ which you are computing from this stored information is then filled into new entries of the form $\alpha_i(t+1)$.

About the two other issues you mention:

  1. The neighbourhood relation between states does not have any theoretical significance; it is just included to save computation time by omitting terms for which the transition probability is 0.

  2. When you don't have any emissions, the recursion only involves the state probabilities: $$\Pr(S_{t+1}) = \sum \Pr(S_{t+1}\, |\ S_{t})\Pr(S_{t}).$$ The equation you cite is a shorthand for a method of approximating the stationary distribution of such a Markov chain: Select an arbitrary distribution over $S$, and then keep overwriting it by the posterior distribution that will obtain one time step into the future. If the state space is finite and the state graph is aperiodic and completely connected, then this will converge to a unique stationary distribution, regardless of your starting state.

I hope this helps. Otherwise let me know.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.