Forward–Backward Algorithm¶

Two dynamic-programming passes combine past-observation and future-observation likelihood messages to compute every hidden-state smoothing marginal in a chain model.

Version: v2 · 2026-09-19 · History
Domain-specific #: 1870
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering

Core Idea¶

The forward–backward algorithm is an exact dynamic-programming procedure for posterior smoothing in a finite-state hidden Markov model (HMM) or an equivalent chain-structured probabilistic model. A forward pass summarizes the joint probability of the observations up to each position and the current hidden state. A backward pass summarizes the likelihood of all later observations conditional on that same state. Multiplying the two messages and normalizing gives the posterior marginal of every hidden state conditioned on the entire observation sequence.

How would you explain it like I'm…

Clues From Both Sides

Pretend you can't see the weather, but you can see whether your friend carried an umbrella each day. To guess if it rained on Tuesday, you use clues from the days before Tuesday and clues from the days after. The Forward–Backward Algorithm is a clever way to collect clues going forward and going backward, then put them together for every single day.

The Two-Way Clue Collector

Sometimes something is hidden, like the weather, and we only see clues, like umbrellas. The hidden thing changes from day to day following chances, and each day's clue depends on that day's hidden state. The Forward–Backward Algorithm first walks forward through the days, keeping a running summary of the clues so far. Then it walks backward, keeping a summary of the clues still to come. Combining both summaries for a day gives the chance of each hidden state that day, using all the clues.

HMM Posterior Smoothing

A hidden Markov model has hidden states that change step by step with transition probabilities, and each state produces an observation with emission probabilities. The Forward–Backward Algorithm finds, for every time step, the probability of each hidden state given the entire observation sequence. This is called smoothing. The forward pass computes the probability of the observations so far together with the current state. The backward pass computes the probability of the future observations given that state. Multiplying the two and normalizing gives the answer. This works because, once you know the current state, the past and future observations are independent. That avoids adding up over every possible sequence of states, which would take exponentially long.

The Forward–Backward Algorithm is an exact dynamic-programming method for posterior smoothing in a finite-state hidden Markov model or an equivalent chain-structured model. The forward messages are αₜ(x) = P(y₁..yₜ, Xₜ = x), and the backward messages are βₜ(x) = P(yₜ₊₁..y_T | Xₜ = x). Both are computed recursively using the transition and emission probabilities. The posterior marginal is P(Xₜ = x | y₁..y_T) ∝ αₜ(x)βₜ(x). The key structural fact is conditional separation: given Xₜ, observations before and after t are independent under the HMM factorization. This replaces an exponential sum over all state paths with two sweeps of reusable sum-product messages, linear in sequence length. The defining output is the set of all-time posterior marginals, not just any procedure run in two directions. The same message computation appears inside Baum–Welch training, but the core operation here is smoothing.

Scope of Application¶

The algorithm applies to discrete HMM smoothing in speech recognition, part-of-speech tagging, biological sequence annotation, communication-channel decoding, regime inference, and other finite latent-state time series. Rabiner's tutorial established the standard engineering treatment in speech recognition. Cambridge's treatment of HMM applications distinguishes forward, backward, Viterbi, BCJR, and Baum–Welch procedures while showing their shared state-space setting.

The same sum-product structure applies to chain factor graphs with finite or tractable state spaces. Kschischang, Frey, and Loeliger show how factor-graph message passing computes marginals of factored global functions, placing forward–backward inside a broader exact sum-product family on trees.

Clarity¶

For a \(K\)-state HMM, define

\[ \alpha_t(j)=P(o_{1:t},X_t=j). \]

Then

\[ \alpha_1(j)=\pi_jb_j(o_1),\qquad \alpha_t(j)=b_j(o_t)\sum_{i=1}^{K}\alpha_{t-1}(i)a_{ij}. \]

The backward message is

\[ \beta_t(i)=P(o_{t+1:T}\mid X_t=i), \]

Manages Complexity¶

Brute-force smoothing sums over \(K^T\) hidden-state sequences. Forward–backward reuses partial sums and requires \(O(TK^2)\) arithmetic for dense transitions. Storing all forward messages and sweeping backward gives all marginals in \(O(TK)\) memory; variants trade recomputation for memory.

The abstraction separates model design from inference plumbing. Once initial, transition, and emission factors are supplied, the same two-pass machinery produces sequence likelihoods, state marginals, and adjacent-state expectations.

Abstract Reasoning¶

The observation likelihood is

\[ P(o_{1:T})=\sum_i\alpha_T(i) =\sum_i\alpha_t(i)\beta_t(i) \]

for every \(t\). Equality across positions is an implementation invariant. If differently scaled messages are combined without compensating scale factors, this identity fails.

For adjacent-state posterior probabilities,

\[ \xi_t(i,j)= \frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{P(o_{1:T})}. \]

Knowledge Transfer¶

The algorithm transfers literally across HMM application domains because the state labels and emissions change while the chain factorization remains. A hidden phoneme, genomic region, weather regime, or communication symbol can use the same recursions.

It also transfers to trellises and chain factor graphs through semiring language: sum-product computes marginals, max-product computes best assignments, and other algebraic operations compute related quantities. That generalization is useful only when the operation and normalization semantics are stated.

Relationships to Other Abstractions¶

Current abstraction Forward–Backward Algorithm Domain-specific

Parents (1) — outgoing typed relations

Forward–Backward Algorithm is a kind of Algorithm Prime

Forward–Backward Algorithm is a strict specialization of prime:algorithm: it defines inputs, finite recursive steps, termination after two passes, and posterior-marginal outputs.

Hierarchy path (1) — routes to 1 parentless root

Forward–Backward Algorithm → is a kind of Algorithm → presupposes, conditional Function (Mapping)

Neighborhood in Abstraction Space¶

Forward–Backward Algorithm sits in a sparse region of the domain-specific corpus (80^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25