2
$\begingroup$

Referencing:

https://en.wikipedia.org/wiki/Forward_algorithm

I understand most of the expansion of the forward algorithm, but the very first step is confusing to me:

enter image description here

Why does the joint probability of current and prior emissions and current state, equal to some term of summation over prior states? What does that summation mean? What is it summing over? The t value?

$\endgroup$

2 Answers 2

2
$\begingroup$

That first step is just an instance of the sum rule: \begin{align} P(A = a) = \sum_{b} P(A = a, B = b) \end{align} where the summation is overall possible values of $B$. This is true for any random variables $A$ and $B$, as long as you sum over all possible values of $B$. This rule is actually pretty intuitive when stated in words. Suppose $A=a$ represents the event that it rains tomorrow, and $B$ represents whether or not humans will ever colonize Mars. Then, the sum rule states that the probability that it rains tomorrow is:

  • The probability that it rains tomorrow and humans do eventually colonize Mars, plus
  • The probability that it rains tomorrow and humans do not ever colonize Mars.

For HMMs, the state at each time step is a distinct random variable, and so we could pick any time step to sum over. The forward algorithm chooses to sum over the state of the previous time step because the conditional independence assumptions of HMMs allow the rest of the derivation to proceed conveniently.

You'll encounter the same idea with the backward algorithm, which chooses to sum over the state of the next time step. \begin{align} \beta_t(x_t) = P(y_{t+1,n} | x_t) = \sum_{x_{t+1}} P(y_{t+1:n}, x_{t+1} | x_t) \end{align} where $n$ is the length of the string.

Both of these algorithms together form the forward-backward algorithm for computing the probability of a state at time $t$ conditional on the whole string: \begin{align} P(x_t | y_{1:n}) & = \frac{ P(x_t , y_{1:n}) }{ P( y_{1:n} ) } \\ & = \frac{ P( x_t, y_{1:t} ) P( y_{t+1:n} | x_t) }{ P( y_{1:n} ) } \\ & = \frac{ \alpha_t(x_t) \beta_t(x_t) }{ \sum_{x_n}\alpha_n(x_n) } \end{align}

In short, the Forward-Backward algorithm uses the conditional independence assumptions of HMMs to compute marginals efficiently by picking an order for summing out random variables. It is a special case of the Sum-Product algorithm, which does the same thing for graphical models more generally.

$\endgroup$
5
  • $\begingroup$ In the forward case we have $\alpha_{k}(z_{k})=P(z_{k},x_{1:k})=\sum_{z_{k-1}}P(z_{k},z_{k-1},x_{1:k})$ but in the backward case we have $\beta_{k}(z_{k})=P(x_{k+1:n}|z_{k})=\sum_{z_{k+1}}P(x_{k+1:n},z_{k+1}|z_{k})$ Isn't the forward case suppose to be conditioned on x1:k $\endgroup$
    – raaj
    Dec 1, 2018 at 22:28
  • $\begingroup$ Be careful about the notation; you've just switched the interpretation of $x$. In your post, and in my answer, $x$ is the state. In this comment you've just written, you appear to be using $x$ to refer to the observed string and $z$ to refer to the state. $\endgroup$
    – jkpate
    Dec 1, 2018 at 22:32
  • $\begingroup$ Regardless of notation, the forward case does not condition on either the state or the string. Using the notation from the original post, we have $\alpha_t(x_t) = P( y_{1:t}, x_t)$, with no conditioning. $\endgroup$
    – jkpate
    Dec 1, 2018 at 22:32
  • $\begingroup$ my bad I am referring to the wiki page there, in my expression here z is the state and x is observation $\endgroup$
    – raaj
    Dec 1, 2018 at 22:33
  • $\begingroup$ I have posted a new question to ask this: stats.stackexchange.com/questions/379833/… $\endgroup$
    – raaj
    Dec 1, 2018 at 22:34
1
$\begingroup$

For simplicity say that all the random variables are discrete. Then \begin{align*} P(X_t = x_t , Y_{1:t} = y_{1:t}) &= P(X_t = x_t , X_{t-1} = \text{anything}, Y_{1:t} = y_{1:t}) \\ &= P(X_t = x_t , X_{t-1} \in \bigcup_{x_{t-1}} x_{t-1}, Y_{1:t} = y_{1:t}) \\ &= \sum_{x_{t-1}}P(X_t = x_t , X_{t-1} = x_{t-1}, Y_{1:t} = y_{1:t}). \end{align*} In the last line you are summing over all possible values of $X_{t-1}$. The set of all possible values is sometimes called the state space, or the support. You are allowed to do this because of the third axiom of probability functions/measures: countable additivity.

$\endgroup$
1
  • $\begingroup$ Does that mean that for the summation I have to put only one x t and then do the calculations with all possible x t-1 ? Could you provide a concrete example, please? Thank you! $\endgroup$
    – teoML
    Jul 2 at 8:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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