The forward algorithm

How likely is what we saw?

Suppose we saw the moves Small, Large, Large. How likely is that sequence under our model? We could list every hidden path (Calm-Calm-Calm, Calm-Calm-Stormy, and so on), compute each path's probability and add them up. With $K$ states and $T$ days that is $K^{T}$ paths, far too many. The forward algorithm does the same sum in $T\cdot K^{2}$ steps by reusing work. It keeps a number $\alpha_t(j)$: the probability of the first $t$ observations and of being in state $j$ on day $t$.

Read the recursion in words: to be in state $j$ today, you came from some state $i$ yesterday (sum over $i$ with the transition chance), and then today's state produced today's observation. Dividing $\alpha_t$ by its total gives the filtered probabilities, your belief about today's state given the data up to today. One practical problem: multiplying many small numbers gives numbers that shrink toward zero and underflow. So at each step we divide by the total $c_t$ and keep it. The log of the data probability is then simply the sum of $\ln c_t$.

• Forward algorithm: sum over all hidden paths in $T\cdot K^{2}$ steps instead of $K^{T}$.
• Filtered probabilities: normalise $\alpha_t$ to get your belief about today's state from data up to today.
• Scaling: divide by $c_t$ each step and add up $\ln c_t$ to avoid underflow.

Lab · what's graded

• The first forward value15 pts
• The total of day one10 pts
• Filtered after two days15 pts
• The probability of the sequence15 pts
• The log-likelihood10 pts
• What the forward algorithm saves10 pts
• Match the vocabulary10 pts
• Why the values are rescaled15 pts