Backtracking and Worked Viterbi Decoding

From Viterbi Scores to a State Sequence

The Viterbi recursion computes the best score of a path ending in each possible hidden state. Those scores alone do not display the whole maximizing path. To recover it, each update records which preceding state attained the maximum; after the last observation, the stored pointers are followed backward. This distinction matters in applications where the result must be an interpretable sequence, such as a sequence of hidden regimes, labels, or biological states.

Let \((X_n,Y_n)_{n\ge1}\) be a hidden Markov model on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). The hidden state \(X_n\) takes values in the finite set \(S=\{1,\ldots,K\}\), and the observation \(Y_n\) takes values in a finite categorical alphabet \(\mathcal{Y}\). The initial distribution is the row vector \(\pi\), the transition matrix is \(A=(a_{ij})\), and \(b_j(y)=\mathbb{P}(Y_n=y\mid X_n=j)\) is the emission probability. Each row of \(A\) sums to \(1\), and for each state \(j\), \(\sum_{y\in\mathcal{Y}}b_j(y)=1\). Given observations \(y_{1:T}=(y_1,\ldots,y_T)\), the joint probability of a state path \(x_{1:T}\) and those observations is

\mathbb{P}(X_{1:T}=x_{1:T},Y_{1:T}=y_{1:T}) =\pi_{x_1}b_{x_1}(y_1)\prod_{n=2}^{T}a_{x_{n-1}x_n}b_{x_n}(y_n).

When the observations have positive probability, a path maximizing this joint probability also maximizes the conditional probability of the path given the observations: the denominator \(\mathbb{P}(Y_{1:T}=y_{1:T})\) is the same positive number for every path. The Viterbi score \(\delta_n(j)\) is the maximum joint probability of the observations through time \(n\) and a path ending at state \(j\). For \(n\ge2\), define a predecessor pointer \(\psi_n(j)\) to be a state attaining the maximum in the update. If there is a tie, choose the smallest-index maximizing state, so the stored pointer is deterministic. There is no predecessor pointer at time \(1\).

Definition: The traceback starts by choosing a terminal state \(x_T^*\) with largest \(\delta_T(j)\). It then sets \(x_{n-1}^*=\psi_n(x_n^*)\) for \(n=T,T-1,\ldots,2\). The resulting sequence \(x_{1:T}^*\) is the decoded Viterbi path. If all terminal scores are zero, the observation sequence has zero probability under the model, and conditional decoding is not defined.

Why Following the Pointers Works

The recursion and pointer rule are

\delta_1(j)=\pi_jb_j(y_1),\qquad \delta_n(j)=b_j(y_n)\max_{i\in S}\{\delta_{n-1}(i)a_{ij}\},\qquad \psi_n(j)\in\mathop{\rm arg\,max}_{i\in S}\{\delta_{n-1}(i)a_{ij}\}.

The Viterbi recursion is the established score calculation. The key point here is that the pointer stores the state at time \(n-1\), not a state at time \(n\), and not a complete path. The next result makes the pointer interpretation precise.

Lemma (Meaning of a predecessor pointer): For any \(n\ge2\) and state \(j\), if \(\delta_n(j)>0\), then \(\psi_n(j)\) is the state at time \(n-1\) on a maximizing path whose time-\(n\) state is \(j\).

Proof. At time \(n\), any path ending at \(j\) has a preceding state \(i\). Its joint probability through time \(n\) equals its probability through time \(n-1\), multiplied by \(a_{ij}b_j(y_n)\). For a fixed \(i\), the largest possible probability through time \(n-1\) is \(\delta_{n-1}(i)\), by the definition of the score. Thus the best path ending at \(j\) through state \(i\) has probability \(\delta_{n-1}(i)a_{ij}b_j(y_n)\). Since \(\delta_n(j)>0\), its maximum is positive, so at least one maximizing predecessor has positive score and positive transition probability. The emission factor \(b_j(y_n)\) is common to every predecessor. Therefore a predecessor maximizing \(\delta_{n-1}(i)a_{ij}\), namely \(\psi_n(j)\), gives a maximizing path ending at \(j\). The deterministic tie rule selects one such predecessor when there is more than one. \(\square\)

Theorem (Correctness of traceback): Suppose the observation sequence has positive probability. Choosing any state with maximal terminal score and following its stored pointers backward produces a state sequence that maximizes the joint probability of the observations and the state sequence.

Proof. Positive probability of the observations means that at least one state path has positive joint probability, so \(\max_j\delta_T(j)>0\). Choose \(x_T^*\) attaining this maximum. By the lemma, the pointer \(\psi_T(x_T^*)\) gives a preceding state on a maximizing path ending at \(x_T^*\). Apply the lemma again at time \(T-1\), and continue down to time \(2\). At every step the score is positive: a positive score at time \(n\) requires a maximizing predecessor with positive score at time \(n-1\) and a positive transition and emission factor. Consequently each pointer on this traceback identifies a valid maximizing prefix. At time \(1\), the score is \(\pi_{x_1^*}b_{x_1^*}(y_1)\); extending that prefix by the recorded transitions and emissions gives joint probability \(\delta_T(x_T^*)\). No path can have a larger probability, because its terminal state has score at most \(\max_j\delta_T(j)\). Hence the traced path is globally maximizing. \(\square\)

A Complete Categorical-Emission Calculation

Worked Example: Traceback for Three Observations

Consider states \(S=\{1,2\}\), symbols \(\mathcal{Y}=\{x,y\}\), initial distribution \(\pi=(\tfrac12,\tfrac12)\), transition matrix \(A\), and emissions as follows. Decode the observation sequence \((x,y,y)\).

A=\begin{bmatrix}\tfrac34&\tfrac14\\[2pt]\tfrac14&\tfrac34\end{bmatrix}, \qquad \begin{array}{c|cc} &x&y\\ \hline 1&\tfrac45&\tfrac15\\ 2&\tfrac15&\tfrac45 \end{array}

Check the probability rows first. The transition row sums are \(\tfrac34+\tfrac14=1\) and \(\tfrac14+\tfrac34=1\). The emission sums are \(\tfrac45+\tfrac15=1\) in state \(1\) and \(\tfrac15+\tfrac45=1\) in state \(2\). The initial probabilities sum to \(\tfrac12+\tfrac12=1\).

Initialize at \(n=1\). Multiply each initial probability by the probability of observing \(x\) in that state:

\delta_1(1)=\tfrac12\cdot\tfrac45=\tfrac25,\qquad \delta_1(2)=\tfrac12\cdot\tfrac15=\tfrac1{10}.

Update at \(n=2\), where \(y_2=y\). For destination state \(1\), the two predecessor contributions before multiplying by its emission are \(\tfrac25\cdot\tfrac34=\tfrac3{10}\) and \(\tfrac1{10}\cdot\tfrac14=\tfrac1{40}\). Since \(\tfrac3{10}=\tfrac{12}{40}>\tfrac1{40}\), the pointer is \(\psi_2(1)=1\), and \(\delta_2(1)=\tfrac15\cdot\tfrac3{10}=\tfrac3{50}\). For destination state \(2\), the contributions are \(\tfrac25\cdot\tfrac14=\tfrac1{10}\) and \(\tfrac1{10}\cdot\tfrac34=\tfrac3{40}\). Since \(\tfrac1{10}=\tfrac4{40}>\tfrac3{40}\), the pointer is \(\psi_2(2)=1\), and \(\delta_2(2)=\tfrac45\cdot\tfrac1{10}=\tfrac2{25}\).

Update at \(n=3\), again with \(y_3=y\). For destination \(1\), the predecessor contributions are \(\tfrac3{50}\cdot\tfrac34=\tfrac9{200}\) and \(\tfrac2{25}\cdot\tfrac14=\tfrac2{100}=\tfrac4{200}\). Thus \(\psi_3(1)=1\) and \(\delta_3(1)=\tfrac15\cdot\tfrac9{200}=\tfrac9{1000}\). For destination \(2\), they are \(\tfrac3{50}\cdot\tfrac14=\tfrac3{200}\) and \(\tfrac2{25}\cdot\tfrac34=\tfrac6{100}=\tfrac{12}{200}\). Thus \(\psi_3(2)=2\) and \(\delta_3(2)=\tfrac45\cdot\tfrac6{100}=\tfrac6{125}\).

The terminal comparison is \(\tfrac6{125}=\tfrac{48}{1000}>\tfrac9{1000}\), so \(x_3^*=2\). Trace backward: \(x_2^*=\psi_3(2)=2\), then \(x_1^*=\psi_2(2)=1\). The decoded path is \((1,2,2)\).

Check by direct substitution. The joint probability for \((1,2,2)\) and \((x,y,y)\) is \(\tfrac12\cdot\tfrac45\cdot\tfrac14\cdot\tfrac45\cdot\tfrac34\cdot\tfrac45\). Multiplying in order gives \(\tfrac25\), then \(\tfrac1{10}\), then \(\tfrac2{25}\), then \(\tfrac3{50}\), then \(\tfrac6{125}\), exactly the terminal score. The other terminal score \(\tfrac9{1000}\) is smaller, in agreement with the recursion and the theorem.

Ties and Zero-Probability States

Worked Example: A Tie with a Deterministic Rule

Let \(S=\{1,2\}\), \(\pi=(\tfrac12,\tfrac12)\), and let every transition probability be \(\tfrac12\), so \(A=\begin{bmatrix}\tfrac12&\tfrac12\\ \tfrac12&\tfrac12\end{bmatrix}\). In both states, let each of the symbols \(u,v\) have emission probability \(\tfrac12\). Each transition row sums to \(\tfrac12+\tfrac12=1\), each emission distribution sums to \(\tfrac12+\tfrac12=1\), and the initial distribution sums to \(1\). Decode observations \((u,v)\), choosing the smallest state whenever there is a tie.

At time \(1\), \(\delta_1(1)=\tfrac12\cdot\tfrac12=\tfrac14\) and \(\delta_1(2)=\tfrac12\cdot\tfrac12=\tfrac14\). At time \(2\), for either destination state, both predecessor products are \(\tfrac14\cdot\tfrac12=\tfrac18\). After multiplying by the destination emission \(\tfrac12\), both destination scores are \(\tfrac1{16}\). The tie rule gives \(\psi_2(1)=1\) and \(\psi_2(2)=1\); the terminal tie rule chooses \(x_2^*=1\). Therefore traceback gives \(x_1^*=\psi_2(1)=1\), and the returned path is \((1,1)\).

Check: Every one of the four paths has joint probability \(\tfrac12\cdot\tfrac12\cdot\tfrac12\cdot\tfrac12=\tfrac1{16}\). Thus \((1,1)\) is a maximizing path, though it is not the only one. The pointer convention makes the output reproducible; it does not make a tied path uniquely more probable.

Worked Example: A Zero Initial Probability

Let \(S=\{1,2\}\), \(\pi=(1,0)\), and \(A=\begin{bmatrix}\tfrac12&\tfrac12\\0&1\end{bmatrix}\). State \(1\) emits \(a,b\) with probabilities \(\tfrac12,\tfrac12\); state \(2\) emits them with probabilities \(\tfrac14,\tfrac34\). Both transition rows sum to \(1\), both emission distributions sum to \(1\), and the initial distribution sums to \(1\). For observations \((b,a)\), compute the scores and traceback.

At time \(1\), \(\delta_1(1)=1\cdot\tfrac12=\tfrac12\), while \(\delta_1(2)=0\cdot\tfrac34=0\). At time \(2\), the observation is \(a\). For destination \(1\), the predecessor products are \(\tfrac12\cdot\tfrac12=\tfrac14\) and \(0\cdot0=0\). Thus \(\delta_2(1)=\tfrac12\cdot\tfrac14=\tfrac18\) and \(\psi_2(1)=1\). For destination \(2\), they are \(\tfrac12\cdot\tfrac12=\tfrac14\) and \(0\cdot1=0\). Thus \(\delta_2(2)=\tfrac14\cdot\tfrac14=\tfrac1{16}\) and \(\psi_2(2)=1\). Since \(\tfrac18>\tfrac1{16}\), the terminal state is \(1\), and the decoded path is \((1,1)\).

Check: The joint probability of path \((1,1)\) and observations \((b,a)\) is \(1\cdot\tfrac12\cdot\tfrac12\cdot\tfrac12=\tfrac18\), matching the terminal score. A path starting in state \(2\) has probability zero because \(\pi_2=0\); it cannot be a positive-probability alternative.

Common Pitfall: Reading a Pointer in the Wrong Direction

A pointer stored at time \(n\) for state \(j\) names the state at time \(n-1\). It is not the state at time \(n\), and it is not a suggestion to move forward. In the first worked example, starting from terminal state \(2\), \(\psi_3(2)=2\) means the state at time \(2\) is \(2\); then \(\psi_2(2)=1\) gives the state at time \(1\). Reading \(\psi_3(2)=2\) as though it identified time \(1\), and then returning \((1,1,2)\), is incorrect. Its joint probability is \(\tfrac12\cdot\tfrac45\cdot\tfrac34\cdot\tfrac15\cdot\tfrac14\cdot\tfrac45=\tfrac3{250}\), less than the decoded path's \(\tfrac6{125}\).

In an implementation, keep the score vector for the current time and store the predecessor index for every destination state and time. Once the final state is selected, a single backward pass through those stored indices reconstructs the path. The score table explains which terminal state wins; the pointer table supplies the sequence. If there are multiple maximizing paths, the chosen tie rule should be applied consistently both when storing predecessors and when selecting the terminal state.

Check Your Understanding

For each question, distinguish score calculation from path reconstruction, and use exact probabilities.

In the three-observation example, what does \(\psi_3(2)=2\) specify, and what does it not specify?
If two predecessor products tie for a destination state, what does the smallest-index rule determine?
Why does a positive terminal score guarantee that traceback can continue to time \(1\)?
For the tie example, verify the joint probability of path \((2,1)\) and observations \((u,v)\).
What does it mean for every terminal Viterbi score to be zero, and why is conditional decoding then undefined?