Viterbi Decoding as Joint MAP Inference

Decoding a Complete Hidden Path

In a hidden Markov model, the observed sequence is available but the states that generated it are not. One possible goal is to identify the single complete state sequence that is most probable after seeing all the observations. This is a joint inference question: the candidate is an entire path, and its probability accounts for the initial state, every transition, and every emission. Viterbi decoding names this maximum a posteriori path objective; here we formulate the objective and its log-probability version.

Let $(\Omega,\mathcal{F},\mathbb{P})$ be a probability space. Let $(X_t)_{t=1}^T$ be a hidden Markov chain with finite state space $S$, initial distribution $\pi^{(0)}$ written as a row vector, and row-stochastic transition matrix $P=(p_{ij})$. Thus $\sum_{j\in S}p_{ij}=1$ for every $i\in S$. Let $(Y_t)_{t=1}^T$ take values in a finite observation alphabet $\mathcal{Y}$. Given the hidden states, the observations are conditionally independent, and the distribution of $Y_t$ depends on the path only through $X_t$. Write $b_i(y)=\mathbb{P}(Y_t=y\mid X_t=i)$, so $\sum_{y\in\mathcal{Y}}b_i(y)=1$.

Fix an observed sequence $y_{1:T}=(y_1,\ldots,y_T)$ with $\mathbb{P}(Y_{1:T}=y_{1:T})>0$. This positive-probability condition makes conditioning on the observed sequence well-defined. A candidate hidden path is $x_{1:T}=(x_1,\ldots,x_T)\in S^T$. The HMM assumptions give its joint probability with the observations as

\mathbb{P}(X_{1:T}=x_{1:T},Y_{1:T}=y_{1:T}) = \pi^{(0)}_{x_1}b_{x_1}(y_1) \prod_{t=2}^{T}p_{x_{t-1}x_t}b_{x_t}(y_t).

Definition: A joint maximum a posteriori (joint MAP) path for the observed sequence $y_{1:T}$ is any path $x_{1:T}^{*}\in S^T$ that maximizes $\mathbb{P}(X_{1:T}=x_{1:T}\mid Y_{1:T}=y_{1:T})$ over all $x_{1:T}\in S^T$. There may be more than one maximizing path.

Why the Objective Can Be Written as a Product

The complete path has one initial-state factor, one emission factor for each observation, and one transition factor for each pair of successive states. A zero factor makes the whole path probability zero: for example, a path beginning in a state with zero initial probability, or using a transition with probability zero, is impossible under the model. It is useful to retain such paths in the candidate set but assign them zero probability rather than silently excluding them.

Proposition: If $\mathbb{P}(Y_{1:T}=y_{1:T})>0$, the joint MAP paths are exactly the paths maximizing $$ w(x_{1:T};y_{1:T}) = \pi^{(0)}_{x_1}b_{x_1}(y_1) \prod_{t=2}^{T}p_{x_{t-1}x_t}b_{x_t}(y_t). $$

Proof. For every candidate path, the definition of conditional probability gives $\mathbb{P}(X_{1:T}=x_{1:T}\mid Y_{1:T}=y_{1:T})= \mathbb{P}(X_{1:T}=x_{1:T},Y_{1:T}=y_{1:T})/\mathbb{P}(Y_{1:T}=y_{1:T})$. The denominator is positive by assumption and is the same for every candidate path. Dividing all candidate joint probabilities by the same positive number preserves every comparison, including ties. By the HMM factorization, the numerator is $w(x_{1:T};y_{1:T})$. Thus precisely the paths maximizing $w$ maximize the conditional probability. $\square$

This result separates two quantities that are easy to confuse. The joint path probability includes the observation sequence and the proposed path; the conditional path probability is that joint probability divided by the probability of the observations. The denominator matters when reporting posterior probabilities, but not when choosing a maximizing path. If the observation sequence has probability zero, this conditional-probability argument does not apply; one must not treat division by zero as a valid decoding rule.

Log Scores for Comparing Paths

Products of many probabilities can become very small. Taking logarithms changes the product into a sum, which is more convenient for calculation and avoids multiplying a long list of tiny numbers. Define $\log 0=-\infty$. For a path with positive weight, its log score is

\ell(x_{1:T};y_{1:T}) = \log \pi^{(0)}_{x_1} +\log b_{x_1}(y_1) +\sum_{t=2}^{T} \bigl(\log p_{x_{t-1}x_t}+\log b_{x_t}(y_t)\bigr).

If any factor in the path weight is zero, its log score is $-\infty$. Since the set of paths $S^T$ is finite, a maximum exists whenever at least one path has positive weight. The assumption that the observations have positive probability guarantees just that: the probability of the observations is a finite sum of nonnegative path-and-observation probabilities, so a positive sum must contain at least one positive term.

Theorem: For a finite-state HMM and a fixed observation sequence with positive probability, the joint MAP paths are exactly the paths maximizing $\ell(x_{1:T};y_{1:T})$. Paths with zero joint probability have score $-\infty$ and cannot maximize.

Proof. For positive path weights $u$ and $v$, the logarithm is strictly increasing, so $u>v$ if and only if $\log u>\log v$, and $u=v$ if and only if $\log u=\log v$. A zero path weight is smaller than every positive path weight, and its score is $-\infty$, smaller than the finite logarithm of every positive weight. At least one positive path exists by the preceding finite-sum argument. Therefore replacing each path weight by its log score preserves the maximizing paths and their ties. $\square$

For continuous-valued observations, the same comparison is made using the observation densities in place of the emission probabilities, provided the joint density of the observed sequence is positive and the chosen conditional distribution is defined by that density. The examples below use categorical observations, so all factors are probabilities.

Worked Example: Comparing Four Complete Paths

Let $S=\{A,B\}$, $\pi^{(0)}=(\tfrac23,\tfrac13)$, and $P=\begin{bmatrix}\tfrac34&\tfrac14\\\tfrac13&\tfrac23\end{bmatrix}$. The first row sums to $\tfrac34+\tfrac14=1$, and the second to $\tfrac13+\tfrac23=1$. The observation alphabet is $\{a,b\}$, with $b_A(a)=\tfrac45$, $b_A(b)=\tfrac15$, $b_B(a)=\tfrac15$, and $b_B(b)=\tfrac45$; each state’s emission probabilities sum to $1$. For observations $(a,b)$, find the joint MAP path.

There are four candidate paths. Their joint weights, obtained by multiplying the initial, first emission, transition, and second emission factors, are

\begin{aligned} w(AA;a,b)&=\tfrac23\cdot\tfrac45\cdot\tfrac34\cdot\tfrac15=\tfrac{2}{25},\\ w(AB;a,b)&=\tfrac23\cdot\tfrac45\cdot\tfrac14\cdot\tfrac45=\tfrac{8}{75},\\ w(BA;a,b)&=\tfrac13\cdot\tfrac15\cdot\tfrac13\cdot\tfrac15=\tfrac{1}{225},\\ w(BB;a,b)&=\tfrac13\cdot\tfrac15\cdot\tfrac23\cdot\tfrac45=\tfrac{8}{225}. \end{aligned}

Using denominator $225$, these weights are respectively $\tfrac{18}{225}$, $\tfrac{24}{225}$, $\tfrac{1}{225}$, and $\tfrac{8}{225}$. Their sum is $\tfrac{51}{225}=\tfrac{17}{75}>0$, the probability of observing $(a,b)$. Thus the posterior path probabilities are the four weights divided by $\tfrac{17}{75}$, and $AB$ is the unique maximizer. In particular, its posterior probability is $(\tfrac{8}{75})/(\tfrac{17}{75})=\tfrac{8}{17}$.

Log-score check. The four scores are $\log(\tfrac{2}{25})$, $\log(\tfrac{8}{75})$, $\log(\tfrac{1}{225})$, and $\log(\tfrac{8}{225})$. Since $\tfrac{8}{75}=\tfrac{24}{225}$ exceeds each of $\tfrac{18}{225}$, $\tfrac{1}{225}$, and $\tfrac{8}{225}$, its logarithm is largest as well. The conditional probability check confirms that this is the same path selected by the joint objective.

Worked Example: A Zero Transition Gives a Negative-Infinite Score

Let $\pi^{(0)}=(\tfrac12,\tfrac12)$ and $P=\begin{bmatrix}\tfrac12&\tfrac12\\0&1\end{bmatrix}$. The first row sums to $\tfrac12+\tfrac12=1$, and the second to $0+1=1$. Let the emissions be $b_A(a)=\tfrac34$, $b_A(b)=\tfrac14$, $b_B(a)=\tfrac14$, and $b_B(b)=\tfrac34$; each state’s two emission probabilities sum to $1$. For observations $(a,b)$, compare all four paths.

The weights are $w(AA)=\tfrac12\cdot\tfrac34\cdot\tfrac12\cdot\tfrac14=\tfrac{3}{64}$; $w(AB)=\tfrac12\cdot\tfrac34\cdot\tfrac12\cdot\tfrac34=\tfrac{9}{64}$; $w(BA)=\tfrac12\cdot\tfrac14\cdot0\cdot\tfrac14=0$; and $w(BB)=\tfrac12\cdot\tfrac14\cdot1\cdot\tfrac34=\tfrac{3}{32}=\tfrac{6}{64}$. The observation likelihood is $\tfrac{3+9+0+6}{64}=\tfrac{18}{64}=\tfrac{9}{32}>0$. Hence $AB$ is the unique MAP path, with posterior probability $(\tfrac{9}{64})/(\tfrac{18}{64})=\tfrac12$.

The corresponding scores are $\log(\tfrac{3}{64})$, $\log(\tfrac{9}{64})$, $-\infty$, and $\log(\tfrac{6}{64})$. The zero transition makes $BA$ impossible, not merely unlikely. Comparing the positive weights shows $\tfrac{9}{64}>\tfrac{6}{64}>\tfrac{3}{64}$, so the log scores also select $AB$.

Worked Example: One Observation and the Initial-State Factor

Let $S=\{A,B\}$, $\pi^{(0)}=(\tfrac1{10},\tfrac9{10})$, and $P=\begin{bmatrix}\tfrac12&\tfrac12\\\tfrac13&\tfrac23\end{bmatrix}$. The transition rows sum to $\tfrac12+\tfrac12=1$ and $\tfrac13+\tfrac23=1$. Observe a single symbol $y$, with $b_A(y)=\tfrac9{10}$ and $b_B(y)=\tfrac15$. These are valid emission probabilities, for example by assigning the complementary symbol probabilities $\tfrac1{10}$ and $\tfrac45$ in states $A$ and $B$, respectively. Find the MAP state path.

For the length-one paths, the joint weights are $w(A;y)=\tfrac1{10}\cdot\tfrac9{10}=\tfrac9{100}$ and $w(B;y)=\tfrac9{10}\cdot\tfrac15=\tfrac{18}{100}$. The observation probability is $\tfrac{27}{100}>0$, so the posterior probabilities are $\tfrac9{27}=\tfrac13$ for $A$ and $\tfrac{18}{27}=\tfrac23$ for $B$. Thus $B$ is the unique MAP path. The log scores, $\log(\tfrac9{100})$ and $\log(\tfrac{18}{100})$, give the same ordering.

A Common Mistake: Dropping the Initial Probability

In the last example, comparing emission probabilities alone would select $A$, because $\tfrac9{10}>\tfrac15$. That comparison is not the joint MAP objective: it omits the initial-state factor. Including that factor gives $\tfrac1{10}\cdot\tfrac9{10}=\tfrac9{100}$ for $A$, but $\tfrac9{10}\cdot\tfrac15=\tfrac{18}{100}$ for $B$. Therefore $B$, not $A$, has the higher posterior probability after observing $y$. The correction is to include every factor that varies across candidate paths: the initial distribution, emissions, and transitions. In a fixed observation sequence the observation likelihood is common to all paths, but the path-dependent initial and transition factors are not.

The log formulation is the same objective expressed on a different scale. It does not change the model or discard factors: each probability factor becomes a log term, and a zero factor becomes $-\infty$. For long sequences this additive form is convenient, but the task remains to maximize over complete paths. The formulation alone does not specify how to search efficiently; the central point here is what quantity any valid decoding calculation must maximize.

Check Your Understanding

For each question, distinguish the path’s joint weight from its conditional probability and account for zero-probability factors.

Why does dividing every path weight by the observation likelihood leave the set of maximizing paths unchanged?
If a candidate path contains a transition with probability zero, what are its joint weight and log score?
In the first worked example, verify that the four joint weights sum to the stated observation likelihood.
In the one-observation example, which path would be selected by emission probability alone, and which by the joint MAP objective?
What condition on the observed sequence is needed to interpret the objective as a conditional probability?

Viterbi Decoding as Joint MAP Inference

What You'll Learn