6.4.3. Forward Algorithm

The Forward Algorithm and Mini-Forward

In Markov Models, inference over time is performed using the mini-forward algorithm, which propagates a belief distribution forward using only the transition model. Given a belief distribution at time t, the mini-forward update computes the belief at time t+1 by marginalizing over the previous state:
$B^{\prime }(X_{t+1})={\sum }_{x_t}P(X_{t+1}\mid x_t)B(x_t).$
This operation accounts only for time elapse and assumes no new evidence is observed between timesteps. As such, mini-forward applies to standard Markov chains where states are directly observable.

Hidden Markov Models (HMMs) extend this setting by introducing evidence variables $E_t$ that are probabilistically generated from hidden states $X_t$. Because new observations arrive at each timestep, belief propagation must incorporate both state transitions and observations. This leads to the forward algorithm, which generalizes mini-forward by adding an observation update.

The forward algorithm maintains the belief state
$B(X_t)=P(X_t\mid e_{1:t}),$
the posterior distribution over the hidden state given all evidence observed so far. Each iteration consists of two conceptually distinct steps:

1. Time elapse update (prediction):
   $B^{\prime }(X_{t+1})={\sum }_{x_t}P(X_{t+1}\mid x_t)B(x_t),$
   which is identical in form to the mini-forward algorithm.
2. Observation update (correction):
   $B(X_{t+1})\propto P(e_{t+1}\mid X_{t+1})B^{\prime }(X_{t+1}),$
   which incorporates the new evidence using the emission (sensor) model. Normalization is typically deferred until the end of the update, since the proportionality constant is shared across states.