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

v1 · 2026-08-30 · History

Domain-specific #

1870

Origin domain

computer science

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.

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) — more general patterns this builds on

• 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 paths (2) — routes to 2 parentless roots

• Forward–Backward Algorithm → Algorithm → Function (Mapping)

Show alternative path (1)

Neighborhood in Abstraction Space

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

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

• Hidden Markov model — 0.86
• Particle Filter — 0.85
• Schrödinger Equation — 0.83
• Pseudorandom Number Generator — 0.82
• Doob Decomposition Theorem — 0.81

Computed from structural-signature embeddings · 2026-09-08