Viterbi Paths Versus Pointwise Posterior Decoding

Two Different Questions About a Hidden Path

After observing a sequence, there are at least two natural ways to report the hidden states. One is to select the single entire path with the largest posterior probability. The other is to select, at each time separately, the state with the largest posterior probability at that time. These procedures can give different sequences because the first compares probabilities of complete paths, while the second compares probabilities of individual states.

Let \((X_n)_{n\ge1}\) be a hidden Markov model on a finite state space \(S\), with initial distribution \(\pi\), transition matrix \(P=(p_{ij})\), and observations \(Y_1,\ldots,Y_T\). The transition matrix is row-stochastic: \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for each \(i\). Conditional on the hidden states, the observations are independent, and the likelihood of observation \(y_n\) in state \(i\) is denoted \(g_i(y_n)\). The observation likelihoods may be probability masses or densities; assume the observed sequence has positive marginal likelihood, so its posterior distribution is defined.

The posterior probability of a complete path is its joint likelihood divided by the marginal likelihood of the observations. That denominator is the same for every path. Thus maximizing the joint likelihood is exactly the same as maximizing the posterior probability of the whole path. In contrast, \(\gamma_n(i)\) sums the posterior probabilities of all paths that pass through state \(i\) at time \(n\). It is not the probability of one particular path.

Proof. Write \(X_{1:T}=(X_1,\ldots,X_T)\) and let \(z_{1:T}\) be any proposed decoded sequence. Under whole-sequence zero-one loss, the loss is \(0\) if \(X_{1:T}=z_{1:T}\) and \(1\) otherwise. Its posterior expectation is \(1-\mathbb{P}(X_{1:T}=z_{1:T}\mid Y_{1:T}=y_{1:T})\). Minimizing this quantity is therefore equivalent to maximizing the posterior probability of the entire path, which is the Viterbi objective.

For Hamming loss, the number of errors is \(\sum_{n=1}^{T}\mathbf{1}_{\{X_n\ne z_n\}}\). By linearity of conditional expectation, its posterior expectation is \(\sum_{n=1}^{T}\mathbb{P}(X_n\ne z_n\mid Y_{1:T}=y_{1:T})=\sum_{n=1}^{T}(1-\gamma_n(z_n))\). Each summand depends only on \(z_n\); hence the sum is minimized by choosing \(z_n\) to maximize \(\gamma_n(z_n)\) at every time. If there are ties, any maximizing state at each time is optimal for this loss. The two criteria optimize different quantities, so their optimizers need not agree. \(\square\)

A Case Where the Decoded Sequences Differ

The next example computes all path weights, then sums them to obtain the smoothed probabilities. The transition and emission probabilities are valid, but an intermediate observation strongly favors one state while persistence in the chain favors paths that remain in the same state.

This example shows why the path with the largest joint posterior probability need not use the most probable state at every time. A state’s smoothed probability collects weight from many paths. The Viterbi criterion instead compares each path’s weight individually.

When Pointwise Decoding Does Agree with Viterbi

Agreement is guaranteed in a useful special case: if the hidden states are conditionally independent given the observations, the posterior probability of a path factors into its one-time posterior probabilities. Maximizing the product can then be done separately at each time. The example below has a transition matrix with identical rows, so each new hidden state is drawn independently of the previous one.

Proof. Conditional independence gives \(\mathbb{P}(X_{1:T}=x_{1:T}\mid Y_{1:T}=y_{1:T})=\prod_{n=1}^{T}\gamma_n(x_n)\). For any path \(x_{1:T}\), each factor satisfies \(\gamma_n(x_n)\le\max_{i\in S}\gamma_n(i)\). Multiplying these nonnegative inequalities gives \(\prod_n\gamma_n(x_n)\le\prod_n\max_i\gamma_n(i)\). A path that chooses a maximizing state at every time attains the right-hand side, so it maximizes the path posterior. If a factor maximum is zero, every state has zero posterior at that time, which would contradict the assumption that the observed sequence has a defined posterior distribution; thus the maximizing choices have positive posterior probability. \(\square\)

Ties, Constraints, and a Common Mistake

Pointwise decoding is a rule for selecting states at each time; it does not, by itself, enforce that adjacent selected states can follow one another under the transition matrix. When posterior maxima tie, the chosen combination can even have posterior probability zero. In such cases, it is important to distinguish the set of pointwise-optimal sequences from the set of valid paths with positive posterior probability.

Common mistake. It is incorrect to say that the Viterbi path must be obtained by taking the most probable state at each time. In the first worked example, that calculation gives \(101\), whereas the largest individual path weight belongs to \(000\). The correction is to compute or recursively maximize complete-path weights for Viterbi decoding; use the smoothed probabilities when the target is minimum posterior expected Hamming loss.

Both summaries can be useful, but they answer different questions. A Viterbi path is appropriate when the decision is about the entire hidden sequence being exactly correct. Pointwise posterior decoding is appropriate when errors are counted one time point at a time. If the application requires a valid path and uses a timewise loss, independent pointwise choices may need an additional constrained optimization step; that changes the decision problem and should be stated explicitly.