Smoothing Hidden States with Forward-Backward Messages

Why Combine Forward and Backward Information?

At time $t$, the hidden state is not observed directly. If observations have arrived only through time $t$, the forward calculation gives the distribution of the current hidden state using the available past. But when the full sequence is observed, later observations also provide information about the state at time $t$. Smoothing incorporates both sources: the observations up to $t$ and the observations after $t$.

Let $T$ be a positive integer. Consider a hidden Markov model on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with hidden states $(X_t)_{1\le t\le T}$ in a finite state space $S$, and observations $(Y_t)_{1\le t\le T}$ in a finite alphabet $\mathcal{Y}$. The initial distribution is the row vector $\pi$, the transition matrix is $P=(p_{ij})$, and $g_i(y)=\mathbb{P}(Y_t=y\mid X_t=i)$ is the emission probability. Conditional on the hidden states, the observations are independent, and each observation's distribution depends only on its corresponding state. We assume the model probabilities are defined for every state and observation under consideration.

Definition: For a fixed observed sequence $y_{1:T}=(y_1,\ldots,y_T)$ with positive probability, the smoothed state probability at time $t$ is $\gamma_t(i)=\mathbb{P}(X_t=i\mid Y_1=y_1,\ldots,Y_T=y_T)$. The forward message is $\alpha_t(i)=\mathbb{P}(Y_1=y_1,\ldots,Y_t=y_t,X_t=i)$. The backward message is $\beta_t(i)=\mathbb{P}(Y_{t+1}=y_{t+1},\ldots,Y_T=y_T\mid X_t=i)$, with $\beta_T(i)=1$.

The sequence likelihood is $L=\mathbb{P}(Y_1=y_1,\ldots,Y_T=y_T)$. The forward recursion starts with $\alpha_1(i)=\pi_i g_i(y_1)$ and continues by summing over the preceding state, then including the current emission. The backward recursion starts from $\beta_T(i)=1$ and sums over the next state, including its transition and emission. In formulas, for $t<T$,

\alpha_{t+1}(j)=g_j(y_{t+1})\sum_{i\in S}\alpha_t(i)p_{ij}, \qquad \beta_t(i)=\sum_{j\in S}p_{ij}g_j(y_{t+1})\beta_{t+1}(j).

These messages summarize different parts of the data. The forward message includes the observed past and the state at $t$; the backward message accounts for the remaining observations conditional on that state. Their product can therefore be normalized to obtain the posterior probability of the state.

The Forward-Backward Smoothing Identity

Theorem (Smoothing identity): For a finite-state hidden Markov model and an observed sequence $y_{1:T}$ with likelihood $L>0$, the smoothed probabilities satisfy, for every $t\in\{1,\ldots,T\}$ and $i\in S$, $$ \gamma_t(i)=\frac{\alpha_t(i)\beta_t(i)}{L}, \qquad L=\sum_{k\in S}\alpha_t(k)\beta_t(k). $$

Proof. Fix $t$ and $i$. By the definition of conditional probability, the numerator of $\mathbb{P}(X_t=i\mid Y_1=y_1,\ldots,Y_T=y_T)$ is the joint probability of the full observation sequence and $X_t=i$. The Markov property and conditional independence of the observations split this joint probability at time $t$: the probability of the observations through $t$ together with $X_t=i$ is $\alpha_t(i)$, and the conditional probability of all later observations given $X_t=i$ is $\beta_t(i)$. Thus the joint probability is $\alpha_t(i)\beta_t(i)$. Dividing by $L>0$ gives the first identity. Summing the joint probability over the mutually exclusive and exhaustive states $i\in S$ gives the probability $L$ of the full observation sequence, so $L=\sum_{k\in S}\alpha_t(k)\beta_t(k)$. This also shows that the normalized probabilities sum to one. $\square$

This identity applies at the endpoints as well. At $t=T$, $\beta_T(i)=1$, so smoothing is just the normalized final forward message. At earlier times, the backward message generally changes the posterior because it contributes evidence from observations after $t$. If $L=0$, conditioning on the observed sequence is not defined by the usual conditional-probability ratio, so the smoothing formula cannot be used.

Worked Example: Smoothing Every State in a Three-Observation Sequence

Let $S=\{1,2\}$, with initial distribution $\pi=(\tfrac12,\tfrac12)$ and transition matrix

P= \begin{bmatrix} \tfrac34&\tfrac14\\ \tfrac13&\tfrac23 \end{bmatrix}.

The first row sums to $\tfrac34+\tfrac14=1$, and the second to $\tfrac13+\tfrac23=1$. For observation $a$, let $g_1(a)=\tfrac34$ and $g_2(a)=\tfrac14$; for observation $b$, let $g_1(b)=\tfrac14$ and $g_2(b)=\tfrac34$. These probabilities sum to one for each state. Take $y_{1:3}=(a,b,a)$.

First compute the forward messages. At time 1, $\alpha_1(1)=\tfrac12\cdot\tfrac34=\tfrac38$ and $\alpha_1(2)=\tfrac12\cdot\tfrac14=\tfrac18$. For time 2, the predicted masses before the emission are $\tfrac38\cdot\tfrac34+\tfrac18\cdot\tfrac13=\tfrac{31}{96}$ for state 1 and $\tfrac38\cdot\tfrac14+\tfrac18\cdot\tfrac23=\tfrac{17}{96}$ for state 2. Including observation $b$,

\alpha_2(1)=\tfrac{31}{96}\cdot\tfrac14=\tfrac{31}{384}, \qquad \alpha_2(2)=\tfrac{17}{96}\cdot\tfrac34=\tfrac{51}{384}.

Before the final emission, the predicted masses are $\tfrac{31}{384}\cdot\tfrac34+\tfrac{51}{384}\cdot\tfrac13=\tfrac{161}{1536}$ and $\tfrac{31}{384}\cdot\tfrac14+\tfrac{51}{384}\cdot\tfrac23=\tfrac{167}{1536}$. Including observation $a$ gives $\alpha_3(1)=\tfrac{483}{6144}$ and $\alpha_3(2)=\tfrac{167}{6144}$. Hence $L=\tfrac{483+167}{6144}=\tfrac{325}{3072}>0$.

Now work backward. The terminal messages are $\beta_3(1)=\beta_3(2)=1$. For time 2, the next observation is $a$, so

\beta_2(1)=\tfrac34\cdot\tfrac34+\tfrac14\cdot\tfrac14=\tfrac58, \qquad \beta_2(2)=\tfrac13\cdot\tfrac34+\tfrac23\cdot\tfrac14=\tfrac5{12}.

For time 1, the next observation is $b$. Therefore $\beta_1(1)=\tfrac34\cdot\tfrac14\cdot\tfrac58+\tfrac14\cdot\tfrac34\cdot\tfrac5{12}=\tfrac{25}{128}$, and $\beta_1(2)=\tfrac13\cdot\tfrac14\cdot\tfrac58+\tfrac23\cdot\tfrac34\cdot\tfrac5{12}=\tfrac{25}{96}$.

Normalize the products at each time. At time 1, the two products are $\tfrac38\cdot\tfrac{25}{128}=\tfrac{225}{3072}$ and $\tfrac18\cdot\tfrac{25}{96}=\tfrac{100}{3072}$. Their sum is $\tfrac{325}{3072}=L$, so $\gamma_1=(\tfrac9{13},\tfrac4{13})$. At time 2, the products are $\tfrac{31}{384}\cdot\tfrac58=\tfrac{155}{3072}$ and $\tfrac{51}{384}\cdot\tfrac5{12}=\tfrac{170}{3072}$; dividing by $L$ gives $\gamma_2=(\tfrac{31}{65},\tfrac{34}{65})$. At time 3, divide $(\tfrac{483}{6144},\tfrac{167}{6144})$ by $L=\tfrac{650}{6144}$, giving $\gamma_3=(\tfrac{483}{650},\tfrac{167}{650})$.

Check: At each time the posterior entries sum to one: $\tfrac9{13}+\tfrac4{13}=1$, $\tfrac{31}{65}+\tfrac{34}{65}=1$, and $\tfrac{483}{650}+\tfrac{167}{650}=1$. The unnormalized products at time 1 also sum to the independently computed forward likelihood $\tfrac{325}{3072}$.

Filtering Is Not Smoothing

The filtered distribution at time $t$ conditions only on observations through $t$, whereas the smoothed distribution conditions on the entire sequence. In the notation above, filtering normalizes $\alpha_t(i)$ by $\sum_k\alpha_t(k)$; smoothing instead multiplies by $\beta_t(i)$ before normalizing. The difference is not a technicality: future observations can make a state more or less plausible at an earlier time.

Worked Example: A Future Observation Changes an Earlier Posterior

Use the same model and observations as in the preceding example. At time 1, the forward masses are $(\tfrac38,\tfrac18)$, whose sum is $\tfrac12$. Thus the filtered probabilities are $(\tfrac34,\tfrac14)$. But the backward messages are $(\tfrac{25}{128},\tfrac{25}{96})$, so the smoothed probabilities, after multiplying and normalizing, are $(\tfrac9{13},\tfrac4{13})$.

For a direct check, the smoothed state-1 probability is $(\tfrac38\cdot\tfrac{25}{128})/(\tfrac{325}{3072})=\tfrac{225}{325}=\tfrac9{13}$; the state-2 probability is $(\tfrac18\cdot\tfrac{25}{96})/(\tfrac{325}{3072})=\tfrac{100}{325}=\tfrac4{13}$. The future observations change the earlier state-1 probability from $\tfrac34$ to $\tfrac9{13}$. The two distributions differ because they answer different conditional-probability questions.

Message Scaling and a Second Calculation

For long sequences, products of probabilities can become numerically very small. The smoothing identity is unchanged if, at a fixed time $t$, every forward message value is multiplied by the same positive constant and every backward message value is multiplied by another positive constant: the common product factor cancels when the products are normalized. In an implementation, scaling must be applied consistently to the messages being combined. The example below illustrates the identity using short exact calculations and also shows that the posterior denominator agrees with the likelihood.

Worked Example: A Two-Time Posterior with Exact Fractions

Let $\pi=(\tfrac13,\tfrac23)$ and $P=\begin{bmatrix}\tfrac12&\tfrac12\\\tfrac14&\tfrac34\end{bmatrix}$. The rows sum to $\tfrac12+\tfrac12=1$ and $\tfrac14+\tfrac34=1$. Suppose the observed symbols are $x,y$, with $g_1(x)=\tfrac23$, $g_2(x)=\tfrac13$, $g_1(y)=\tfrac14$, and $g_2(y)=\tfrac34$. For each state, the probabilities of $x$ and $y$ sum to one.

The first forward message is $\alpha_1(1)=\tfrac13\cdot\tfrac23=\tfrac29$ and $\alpha_1(2)=\tfrac23\cdot\tfrac13=\tfrac29$. At time 2, the predicted masses are $\tfrac29\cdot\tfrac12+\tfrac29\cdot\tfrac14=\tfrac16$ and $\tfrac29\cdot\tfrac12+\tfrac29\cdot\tfrac34=\tfrac5{18}$. Including $y$, we get $\alpha_2(1)=\tfrac1{24}$ and $\alpha_2(2)=\tfrac5{24}$. Thus $L=\tfrac14>0$.

Since $\beta_2(1)=\beta_2(2)=1$, the time-2 posterior is $(\tfrac{1}{24}/\tfrac14,\tfrac{5}{24}/\tfrac14)=(\tfrac16,\tfrac56)$. At time 1, $\beta_1(1)=\tfrac12\cdot\tfrac14+\tfrac12\cdot\tfrac34=\tfrac12$, while $\beta_1(2)=\tfrac14\cdot\tfrac14+\tfrac34\cdot\tfrac34=\tfrac58$. The products are $\tfrac29\cdot\tfrac12=\tfrac19$ and $\tfrac29\cdot\tfrac58=\tfrac5{36}$. Their sum is $\tfrac4{36}+\tfrac5{36}=\tfrac14=L$, so the time-1 posterior is $(\tfrac{1/9}{1/4},\tfrac{5/36}{1/4})=(\tfrac49,\tfrac59)$.

Check: Both posterior vectors sum to one: $\tfrac16+\tfrac56=1$ and $\tfrac49+\tfrac59=1$. Also, the sum of the time-1 forward-backward products equals the final forward likelihood, as required.

Common Errors and a Practical Check

A common mistake is to normalize the forward message and call the result the smoothed posterior. In the first example, this gives the time-1 value $\tfrac34$ for state 1. That is a valid filtered probability, but it is not the smoothed probability: the backward message must also be included, giving $\tfrac9{13}$. Another error is to divide each product $\alpha_t(i)\beta_t(i)$ by a different denominator. For a fixed time, the denominator is the same sum over all states, and by the theorem it equals the likelihood $L$.

For a reliable calculation, check the transition rows sum to one, compute the forward and backward messages with the specified boundary values, verify that $\sum_i\alpha_t(i)\beta_t(i)=L$ at the time being checked, and confirm that the smoothed probabilities sum to one. These checks catch arithmetic mistakes and clarify whether the desired quantity conditions on the past alone or on the full observation sequence.

Check Your Understanding

Use the definitions and identities above to answer each question.

In a hidden Markov model, which observations are used in a filtered probability at time $t$, and which are used in a smoothed probability?
Why must the observation sequence have positive likelihood before the smoothing identity can be applied as a conditional probability?
Suppose at a fixed time the products $\alpha_t(i)\beta_t(i)$ are $\tfrac18$, $\tfrac14$, and $\tfrac18$ for three states. Find the smoothing denominator and the three posterior probabilities.
At the final time $T$, what is the backward message, and how does the smoothing formula simplify?
If all forward messages at one fixed time are multiplied by the same positive constant, why do the normalized smoothed probabilities at that time remain unchanged?