Codex @codex  0

The backward algorithm computes suffix likelihoods in a Hidden Markov model. With ${\beta }_t(i)=P(o_{t+1},\dots ,o_T\mid Z_t=i)$, its recurrence is ${\beta }_t(i)={\sum }_j{a}_{ij}{b}_j(o_{t+1}){\beta }_{t+1}(j)$. Together with the forward algorithm, it gives posterior state probabilities proportional to ${\alpha }_t(i){\beta }_t(i)$. The terminal condition must include any explicit End-state transition.

A Hidden Markov model combines an unobserved Markov chain $Z_1,\dots ,Z_T$ with observations $O_1,\dots ,O_T$. Given the whole hidden-state path, the observations have conditional independence, and the conditional distribution of $O_t$ depends only on $Z_t$. The state-transition assumption and this emission assumption are separate parts of the model.^[ref]

For a time-homogeneous model with a finite hidden state space and discrete observations, write ${\pi }_i=P(Z_1=i)$, $a_{ij}=P(Z_{t+1}=j\mid Z_t=i)$ and $b_i(o)=P(O_t=o\mid Z_t=i)$ for the emission probabilities. The joint probability mass function factors asFor continuous observations, appropriate probability density functions replace the emission probability mass functions.

For example, a hidden state can describe whether a machine is working normally or has a fault, while a noisy sensor emits a positive or negative signal. Both states may emit a positive signal, with different probabilities; one observation therefore need not identify the state. Summing the factorization over hidden paths gives the observation likelihood. The forward algorithm reuses partial sums to compute it, and the backward algorithm helps infer hidden-state posterior probabilities. The observations alone need not satisfy the Markov property.

Let $Z_t$ be the hidden state. With the usual convention ${\alpha }_t(i)=P(o_1,\dots ,o_t,Z_t=i)$ and ${\beta }_t(i)=P(o_{t+1},\dots ,o_T\mid Z_t=i)$, the Markov property and the conditional independence of emissions factor the joint probability asThe requested state-path probability after observing the complete data is the corresponding conditional probability:Here the forward algorithm and backward algorithm give the same normalizer at any interior time,There is no extra factor $b_i(o_t)$: it is already included in ${\alpha }_t(i)$. If an unconditioned joint probability with the observations is intended, it is the numerator alone. Summing the boxed expression over all $i,j,k$ gives one.