Estimating Transition Posteriors from Forward-Backward Messages

From Smoothed States to Smoothed Transitions

Smoothing gives the posterior probability of a hidden state at one time, given the entire observation sequence. Many questions require more detail: which state transition most likely occurred between two consecutive observations, or how many times a particular transition is expected to occur? The relevant quantity is the posterior probability of an adjacent pair of states. It combines the information before the pair, the transition and observation at the next time, and the information after the pair.

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space, and let $(X_n)_{1\le n\le T}$ be a hidden Markov model with finite state space $S$. The hidden chain has initial distribution $\pi$ and transition matrix $P=(p_{ij})$, where $p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)$. Each row of $P$ sums to $1$. Conditional on the hidden states, the observations $Y_1,\ldots,Y_T$ are independent, and the conditional distribution of $Y_n$ depends only on $X_n$.

For a discrete observation model, write $g_n(i)=\mathbb{P}(Y_n=y_n\mid X_n=i)$. For observations with densities, take a common dominating measure for the observation distributions and let $g_n(i)$ be the conditional density at the observed value $y_n$. The formulas below apply to either case: likelihoods and messages are probabilities in the discrete case and density-based likelihoods in the continuous case. In the density case, posterior formulas are understood as a version of the conditional distribution, at observation values where the densities are defined and the sequence likelihood is positive and finite.

Definition: The forward message $\alpha_n(i)$ is the likelihood of the observations through time $n$, together with $X_n=i$. The backward message $\beta_n(i)$ is the likelihood of observations after time $n$, conditional on $X_n=i$. The sequence likelihood $L$ is the likelihood of all the observations. Assume $L>0$ and finite.

\alpha_n(i)=\mathbb{P}(Y_{1:n}=y_{1:n},X_n=i),\qquad \beta_n(i)=\mathbb{P}(Y_{n+1:T}=y_{n+1:T}\mid X_n=i),\qquad L=\mathbb{P}(Y_{1:T}=y_{1:T}),

When observations have densities, each occurrence of a probability involving observed values in these definitions is replaced by its corresponding joint or conditional density. For the terminal time, the empty future contributes no additional likelihood, so $\beta_T(i)=1$. The forward and backward recursions are $\alpha_1(i)=\pi_i g_1(i)$, $\alpha_{n+1}(j)=g_{n+1}(j)\sum_i\alpha_n(i)p_{ij}$, and $\beta_n(i)=\sum_jp_{ij}g_{n+1}(j)\beta_{n+1}(j)$.

Theorem (Adjacent-state posterior): For $1\le n<T$ and $i,j\in S$, the posterior probability of the adjacent hidden-state pair is $$ \xi_n(i,j)=\mathbb{P}(X_n=i,X_{n+1}=j\mid Y_{1:T}=y_{1:T}) =\frac{\alpha_n(i)p_{ij}g_{n+1}(j)\beta_{n+1}(j)}{L}. $$ For density-based messages, this ratio gives the corresponding conditional posterior, wherever the density-based likelihood is positive and finite. For each $n$, $\sum_{i,j\in S}\xi_n(i,j)=1$.

Proof. In the discrete case, fix $i,j$. The joint likelihood of all observations and the event $X_n=i,X_{n+1}=j$ factors into three pieces. The observations through time $n$ and the event $X_n=i$ contribute $\alpha_n(i)$. Given $X_n=i$, the transition to $j$ contributes $p_{ij}$; the observation at time $n+1$ contributes $g_{n+1}(j)$. Conditional on $X_{n+1}=j$, the later observations contribute $\beta_{n+1}(j)$. The Markov property and conditional independence of the observations therefore give $\mathbb{P}(Y_{1:T}=y_{1:T},X_n=i,X_{n+1}=j)=\alpha_n(i)p_{ij}g_{n+1}(j)\beta_{n+1}(j)$. Dividing by the positive likelihood $L$ gives the asserted conditional probability. The same factorization of joint and conditional densities gives the density-based formula. To check normalization, sum the numerators over $i,j$. For each $j$, $\sum_i\alpha_n(i)p_{ij}$ is the forward contribution into state $j$; multiplying by $g_{n+1}(j)\beta_{n+1}(j)$ and summing over $j$ gives $L$, by the forward recursion followed by the backward decomposition of the remaining likelihood. Thus $\sum_{i,j}\xi_n(i,j)=L/L=1$. $\square$

The denominator is not an arbitrary scaling constant. It is the same full-sequence likelihood obtained from the messages: $L=\sum_i\alpha_n(i)\beta_n(i)$ for any $n$, and also $L=\sum_{i,j}\alpha_n(i)p_{ij}g_{n+1}(j)\beta_{n+1}(j)$. These equalities provide useful checks on a computation.

Worked Calculations

Worked Example: One Posterior Transition

Let $S=\{1,2\}$, with initial distribution $\pi=(\tfrac12,\tfrac12)$, and $P=\begin{bmatrix}\tfrac34&\tfrac14\\\tfrac14&\tfrac34\end{bmatrix}$. Both rows sum to $1$: $\tfrac34+\tfrac14=1$ in each row. The observation alphabet is $\{a,b\}$, with probabilities $g(a|1)=\tfrac34$, $g(a|2)=\tfrac14$, $g(b|1)=\tfrac14$, and $g(b|2)=\tfrac34$. Observe $Y_1=a,Y_2=b$. Compute the posterior distribution of $(X_1,X_2)$.

The forward message at time $1$ is $\alpha_1(1)=\tfrac12\cdot\tfrac34=\tfrac38$ and $\alpha_1(2)=\tfrac12\cdot\tfrac14=\tfrac18$. Since there are no later observations, $\beta_2(1)=\beta_2(2)=1$. The four unnormalized pair likelihoods, in state-pair order $(1,1),(1,2),(2,1),(2,2)$, are

\begin{aligned} (1,1):&\quad \tfrac38\cdot\tfrac34\cdot\tfrac14=\tfrac9{128},& (1,2):&\quad \tfrac38\cdot\tfrac14\cdot\tfrac34=\tfrac9{128},\\ (2,1):&\quad \tfrac18\cdot\tfrac14\cdot\tfrac14=\tfrac1{128},& (2,2):&\quad \tfrac18\cdot\tfrac34\cdot\tfrac34=\tfrac9{128}. \end{aligned}

Thus $L=\tfrac9{128}+\tfrac9{128}+\tfrac1{128}+\tfrac9{128}=\tfrac{28}{128}=\tfrac7{32}$. Dividing each numerator by $L$ gives $\xi_1(1,1)=\tfrac9{28}$, $\xi_1(1,2)=\tfrac9{28}$, $\xi_1(2,1)=\tfrac1{28}$, and $\xi_1(2,2)=\tfrac9{28}$. They sum to $\tfrac{28}{28}=1$. As a marginal check, the posterior probability $X_1=1$ is $\tfrac9{28}+\tfrac9{28}=\tfrac9{14}$, and the posterior probability $X_2=1$ is $\tfrac9{28}+\tfrac1{28}=\tfrac5{14}$.

Worked Example: Two Adjacent Pairs in a Three-Observation Sequence

Use the same two-state transition and observation probabilities as above, and observe $Y_1=a,Y_2=b,Y_3=a$, with $\pi=(\tfrac12,\tfrac12)$. The transition rows still each sum to $\tfrac34+\tfrac14=1$ and $\tfrac14+\tfrac34=1$. Compute both adjacent-pair posterior tables.

The forward values at time $1$ are $(\tfrac38,\tfrac18)$. Before multiplying by the time-2 emission probabilities, the predicted state weights are $\tfrac38\cdot\tfrac34+\tfrac18\cdot\tfrac14=\tfrac{10}{32}=\tfrac5{16}$ for state 1, and $\tfrac38\cdot\tfrac14+\tfrac18\cdot\tfrac34=\tfrac6{32}=\tfrac3{16}$ for state 2. The emission probabilities for $b$ are $(\tfrac14,\tfrac34)$, so $\alpha_2=(\tfrac5{64},\tfrac9{64})$.

At time 3, the predicted weights are $\tfrac5{64}\cdot\tfrac34+\tfrac9{64}\cdot\tfrac14=\tfrac{24}{256}=\tfrac3{32}$ and $\tfrac5{64}\cdot\tfrac14+\tfrac9{64}\cdot\tfrac34=\tfrac{32}{256}=\tfrac18$. Multiplication by the $a$ emission probabilities $(\tfrac34,\tfrac14)$ gives $\alpha_3=(\tfrac9{128},\tfrac4{128})$, and therefore $L=\tfrac{13}{128}$.

For the backward messages, $\beta_3=(1,1)$. Using the time-3 emission probabilities, $\beta_2(1)=\tfrac34\cdot\tfrac34+\tfrac14\cdot\tfrac14=\tfrac58$, and $\beta_2(2)=\tfrac14\cdot\tfrac34+\tfrac34\cdot\tfrac14=\tfrac38$. At time 1, using the time-2 emission probabilities, $\beta_1(1)=\tfrac34\cdot\tfrac14\cdot\tfrac58+\tfrac14\cdot\tfrac34\cdot\tfrac38=\tfrac{24}{128}=\tfrac3{16}$, and $\beta_1(2)=\tfrac14\cdot\tfrac14\cdot\tfrac58+\tfrac34\cdot\tfrac34\cdot\tfrac38=\tfrac{32}{128}=\tfrac14$. The likelihood check is $\tfrac38\cdot\tfrac3{16}+\tfrac18\cdot\tfrac14=\tfrac{13}{128}$, agreeing with the forward calculation.

For $n=1$, the four numerators $\alpha_1(i)p_{ij}g_2(j)\beta_2(j)$, using common denominator $1024$, are $45,27,5,27$ in the pair order $(1,1),(1,2),(2,1),(2,2)$. Their sum is $104/1024=13/128=L$. For $n=2$, the numerators $\alpha_2(i)p_{ij}g_3(j)\beta_3(j)$, also with denominator $1024$, are $45,5,27,27$, whose sum is again $104/1024=L$. Dividing by $L=104/1024$, the posterior tables are

\bigl(\xi_1(i,j)\bigr)_{i,j} =\frac1{104}\begin{bmatrix}45&27\\5&27\end{bmatrix}, \qquad \bigl(\xi_2(i,j)\bigr)_{i,j} =\frac1{104}\begin{bmatrix}45&5\\27&27\end{bmatrix}.

Each table sums to $1$. The column sums of the first table are $(\tfrac{50}{104},\tfrac{54}{104})$; these equal the row sums of the second table, as required for the posterior distribution of $X_2$. This is a useful check that adjacent-pair calculations agree at their shared time point.

Posterior Transition Counts

Proposition: Define $N_{ij}=\sum_{n=1}^{T-1}\mathbf{1}_{\{X_n=i,X_{n+1}=j\}}$, the number of transitions from $i$ to $j$ in the hidden path. Then $$ \mathbb{E}[N_{ij}\mid Y_{1:T}=y_{1:T}] =\sum_{n=1}^{T-1}\xi_n(i,j). $$

Proof. For each time $n$, the indicator $\mathbf{1}_{\{X_n=i,X_{n+1}=j\}}$ has conditional expectation $\xi_n(i,j)$ given the observations, by the definition of conditional probability (or its density-based posterior version). Since $N_{ij}$ is the finite sum of these indicators, linearity of conditional expectation gives $\mathbb{E}[N_{ij}\mid Y_{1:T}=y_{1:T}]=\sum_{n=1}^{T-1}\mathbb{E}[\mathbf{1}_{\{X_n=i,X_{n+1}=j\}}\mid Y_{1:T}=y_{1:T}]=\sum_{n=1}^{T-1}\xi_n(i,j)$. No independence among the transition indicators is needed. $\square$

Worked Example: Expected Counts from Pair Posteriors

For the sequence $a,b,a$ in the previous calculation, sum the two posterior tables entry by entry. The expected number of transitions $1\to1$ is $\tfrac{45}{104}+\tfrac{45}{104}=\tfrac{90}{104}=\tfrac{45}{52}$. For $1\to2$, it is $\tfrac{27}{104}+\tfrac5{104}=\tfrac{32}{104}=\tfrac4{13}$. For $2\to1$, it is $\tfrac5{104}+\tfrac{27}{104}=\tfrac{32}{104}=\tfrac4{13}$. For $2\to2$, it is $\tfrac{27}{104}+\tfrac{27}{104}=\tfrac{54}{104}=\tfrac{27}{52}$.

These are conditional expected counts, not necessarily integer-valued counts for any one hidden path. Their sum is $\tfrac{90+32+32+54}{104}=\tfrac{208}{104}=2$, which matches the two transitions in a path of length $T=3$. This total provides a check on the aggregation.

More generally, summing all expected transition counts gives $T-1$, because each time point contributes a pair distribution with total probability $1$. The row sums of $\xi_n$ give the smoothed posterior probabilities of $X_n$; its column sums give those of $X_{n+1}$. These identities connect pair smoothing to state smoothing and can reveal indexing errors in an implementation.

A Common Normalization Error

A frequent mistake is to omit the emission likelihood at time $n+1$, or to divide by a quantity other than the full-sequence likelihood. In the one-transition example, omitting $g_2(j)$ would assign the unnormalized value $\alpha_1(1)p_{11}=\tfrac38\cdot\tfrac34=\tfrac9{32}$ to pair $(1,1)$. The sum of all such incorrectly formed values is $\sum_i\alpha_1(i)\sum_jp_{ij}=\tfrac38+\tfrac18=\tfrac12$, so the resulting normalized value for $(1,1)$ would be $(\tfrac9{32})/(\tfrac12)=\tfrac9{16}$. The correct posterior is $\tfrac9{28}$: including the observed $b$ at time 2 gives numerator $\tfrac9{128}$, and division by the full likelihood $\tfrac{28}{128}$ gives $\tfrac9{28}$. The omitted emission changes the answer because it discards evidence about the state at the second time.

Before interpreting a transition posterior, check that the transition matrix is row-stochastic, that the observation likelihood at the next time is included, and that the denominator is the full sequence likelihood. Then check that each pair table sums to one and that neighboring tables have matching marginals at their shared state time. These checks apply whether the observation likelihoods are probabilities or densities.

Check Your Understanding

Use the definitions and identities above to answer the following questions.

For a pair posterior at time $n$, why does the formula include $g_{n+1}(j)$ rather than $g_n(i)$ as its explicit emission factor?
Show how to obtain the smoothed posterior probability of $X_n=i$ by summing $\xi_n(i,j)$ over $j$.
For a sequence of length $T$, what should the sum of all posterior expected transition counts be, and why?
Explain how the pair-posterior formula is interpreted when observations have densities and exact observed values have probability zero.
In the one-transition example, recompute the posterior probability of $(X_1,X_2)=(2,1)$ from its numerator and the sequence likelihood.

Estimating Transition Posteriors from Forward-Backward Messages

What You'll Learn