A different question from the best path
The existing language-model lesson derives the forward likelihood and the Viterbi best path. Here we ask for the posterior distribution of a state at a particular time, using the entire observation sequence. This is smoothing: it is different from filtering using only observations so far, and from choosing one most probable complete path.
Use a finite hidden-state set , a nonempty observation sequence with , initial probabilities , transition probabilities and emission probabilities . As in the existing lesson, the model specifies a first-order state chain and conditionally independent emissions given the states. The initial probabilities and each transition and emission row are probability distributions.
Prefix and suffix quantities
Definition 11.1.1
(Forward and backward values)
The forward value of state at time is the probability of the observation prefix together with that state:
The backward value sums the model's transition and emission products over all possible suffix state sequences that start from state at time :
The empty suffix (at ) has weight one. Both quantities satisfy one-step recurrences:
Write for the likelihood of the whole sequence.
When , is the conditional probability of the later observations given that state. The suffix-product definition also specifies the value when that state has zero probability, without conditioning on a null event.
Theorem 11.1.2
(Smoothing identities)
For every and state ,
and for and states ,
If , the smoothed posteriors are
and they are consistent: and .
Proof
(Splitting every path at time t)
Fix . In the joint model, every compatible full path factors into a prefix ending at and a suffix beginning with a transition out of . Summing the products over the two sets of choices gives . At this reads , so summing over gives .
For , partition by the adjacent states , . The path weight factors into the prefix up to , the single step , and the suffix after , which gives the stated joint probability. Dividing by gives and .
For consistency, the backward recurrence gives , and the forward recurrence gives . Dividing by gives the two marginalization identities.
Proof X-ray
Where the factorization is used
The model assumptions enter only in one place: the weight of a full path is a product of one initial factor and, for each step, a transition factor and an emission factor. Cut that product at time . The factors that involve form the prefix, and the factors that involve form the suffix. The two groups share exactly one variable, . That is why must be fixed first, and it is the only reason the double sum over prefixes and suffixes separates into a product of two sums.
The key move is therefore the distributive law: sum over the prefix and over the suffix independently, so that exponentially many paths are replaced by two vectors of length . The argument closes because makes the case the definition of , and each recurrence is the same cut moved by one step.
Two things are not claimed. First, the argument says nothing about independence of the hidden states given the observations: the identity holds for each fixed separately, and the joint posterior of several times is not the product of the . Second, the only place a hypothesis beyond the model is needed is the final division, which requires .
If , these conditional posteriors are not defined by the ratio. For example, if every state assigns zero probability to an observed token, every full path has zero observation probability. Replacing by a uniform vector would be an additional convention, not the stated posterior.
A two-state calculation
Worked example 11.1.3
(Smoothing in a two-state model)
Take states , initial row , transition matrix
and emission probabilities , , , . For observations , forward and backward values are
Thus
For comparison, filtering at time one uses only and gives ; the later observation changes its smoothed probability to .
Counterexample mode
Marginal modes need not be the best path
Here the most probable state at time one is and at time two is , so selecting each marginal mode yields with posterior probability . The complete path has posterior probability and is more likely. Maximizing marginals separately is therefore not Viterbi decoding, even though all four transitions in this example are possible.
Worked example 11.1.4
(A single observation: smoothing equals filtering)
Use the same model with the one-symbol sequence (). Then and , so and
There is no later observation, so smoothing coincides with filtering, and there are no pair posteriors because is impossible. This is the boundary case of the recurrences.
Worked example 11.1.5
(A state excluded by the evidence)
Keep the initial row and , but change the emission of state to , , and keep , . For observations :
The backward values are and , . Hence
The observation is impossible in state , so state has smoothed probability zero at time two even though it has positive prior probability. As a check, and , which sum to .
Common mistakes
Common mistake
(Treating smoothed marginals as independent)
In the two-state calculation, , but the posterior probability of the path is . The marginals describe one time at a time; the joint posterior over several times needs the pair terms (and, for longer paths, the full chain factorization).
Common mistake
(Normalizing with a prefix total)
At time , the sum is a filtering constant, not . In the two-state calculation , whereas . Dividing by would give numbers that do not sum to one. The smoothing denominator is always the whole-sequence likelihood .
Cost and exercises
For dense transitions and constant-time arithmetic, computing all forward and backward values takes time. Storing all forward values and a rolling backward vector permits state posteriors to be emitted in reverse time using stored values; emitting every itself has output size. Long products may underflow in floating point; a scaling or log-sum-exp implementation must preserve the normalization consistently.
Quick check
(What is ?)
Think about which observations come after time .
Solution · Answer
: the suffix is empty, so there are no later observations to generate and the empty product is one.
Quick check
(In the two-state example with observations , what is ?)
Read the entry of the matrix in row , column .
Solution · Answer
.
Quick check
(In the two-state example, sum the first column of . Which smoothed posterior should it equal?)
Sum over the earlier state .
Solution · Answer
: summing over gives the posterior of state at time two.
Quick check
(Can the formula for be evaluated if ?)
Look at the denominator.
Solution · Answer
No. The formula is a ratio with denominator , and has no value; conditioning on an observation event of probability zero is not defined by this ratio.