Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Viterbi Algorithm › Backpointer Tracking

Michael BrenndoerferUpdated April 28, 202510 min read

Language AI HandbookAll chapters

Part 6 of 67Sequence Labeling

Chapter 41Viterbi Algorithm › Backpointer Tracking

Reading section 4 of 12 · Backpointer Tracking · 10 minSection 4 of 12 · 10 min

Section 4 of 12 · 10 min read

Viterbi Algorithm › Backpointer TrackingOne section · Sections in this chapter4 / 12 ↓

Sections in this chapter12

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

The Viterbi recurrence gives us the score of the best path to each state, but we've lost something in the process: which path achieved that score? At each step, we took the maximum over predecessors, keeping only the winning score. To reconstruct the actual optimal sequence, we need to remember which predecessor won at each cell.

The Need for BackpointersLink Copied

Think of it this way: when we compute $V_3(\text{NOUN})$ , we're answering "what's the best path probability ending at NOUN at position 3?" But we're not recording "and that path came through VERB at position 2." Without this information, when we finish computing the entire trellis, we'll know that the best final state is (say) NOUN with score 0.0073, but we won't know the sequence of states that led there.

The solution is elegantly simple: alongside each score, store the predecessor that achieved it. We call this a backpointer because it points backward to the previous state in the optimal path.

Formalizing BackpointersLink Copied

The backpointer $B_i(s)$ records which predecessor state $s'$ maximized the score when computing $V_i(s)$ :

B_i(s) = \arg\max_{s'} \left[ V_{i-1}(s') \cdot P(s | s') \cdot P(w_i | s) \right]

where:

$B_i(s)$ : the backpointer for state $s$ at position $i$ , storing which predecessor led to the best score
$\arg\max_{s'}$ : returns the state $s'$ (not the value) that maximizes the expression
The expression inside is identical to the Viterbi recurrence

Notice the difference between $\max$ and $\arg\max$ :

$\max$ returns the value: "the best score is 0.042"
$\arg\max$ returns the argument: "the best predecessor is VERB"

We compute both simultaneously: the same computation that finds the maximum score also identifies which predecessor achieved it.

Reconstructing the Path: The Backward PassLink Copied

Once we've filled the entire trellis, we have scores and backpointers for every (position, state) pair. Reconstruction proceeds in three steps:

Step 1: Find the best final state. The optimal path ends at whichever state has the highest score at the final position:

s_n^* = \arg\max_s V_n(s)

where:

$s_n^*$ : the optimal state at the final position $n$
$V_n(s)$ : the Viterbi score at the final position for each state $s$

Step 2: Follow backpointers backward. Starting from $s_n^*$ , we trace back through the stored pointers:

s_i^* = B_{i+1}(s_{i+1}^*)

where:

$s_i^*$ : the optimal state at position $i$
$B_{i+1}(s_{i+1}^*)$ : the backpointer stored at position $i+1$ for state $s_{i+1}^*$ , which tells us which state at position $i$ led to the best path through $s_{i+1}^*$

Each backpointer tells us: "to reach this state optimally, I came from that state." By following this chain, we recover the complete path.

Step 3: Reverse the sequence. Since we traced from position $n$ back to position 1, the recovered sequence is in reverse order. A simple reversal gives us the forward path.

Why Backpointers WorkLink Copied

The beauty of this approach is that backpointers require only $O(n \cdot k)$ additional storage, one pointer per cell in the trellis, and add no complexity to the forward pass (we're already examining all predecessors to compute the maximum). The backward pass is a simple $O(n)$ traversal.

In[8]:

Code

def viterbi_with_backpointers(
    observations, states, start_prob, trans_prob, emit_prob
):
    """
    Viterbi algorithm with backpointer tracking.

    Args:
        observations: List of observed symbols
        states: List of possible hidden states
        start_prob: Dict mapping state -> initial probability
        trans_prob: Dict mapping (prev_state, state) -> transition probability
        emit_prob: Dict mapping (state, observation) -> emission probability

    Returns:
        best_path: List of states forming the optimal path
        best_prob: Probability of the optimal path
    """
    n = len(observations)

    # Initialize Viterbi table and backpointers
    # V[i][s] = best probability of path ending at state s at position i
    V = [{} for _ in range(n)]
    backpointer = [{} for _ in range(n)]

    # Base case: first observation
    for s in states:
        emit = emit_prob.get((s, observations[0]), 1e-10)
        V[0][s] = start_prob.get(s, 1e-10) * emit
        backpointer[0][s] = None

    # Recursive case: fill the trellis
    for i in range(1, n):
        for s in states:
            # Find best predecessor
            best_prev = None
            best_score = 0

            emit = emit_prob.get((s, observations[i]), 1e-10)

            for s_prev in states:
                trans = trans_prob.get((s_prev, s), 1e-10)
                score = V[i - 1][s_prev] * trans * emit

                if score > best_score:
                    best_score = score
                    best_prev = s_prev

            V[i][s] = best_score
            backpointer[i][s] = best_prev

    # Find best final state
    best_final_state = max(states, key=lambda s: V[n - 1][s])
    best_prob = V[n - 1][best_final_state]

    # Backtrack to find the path
    path = [best_final_state]
    current = best_final_state
    for i in range(n - 1, 0, -1):
        current = backpointer[i][current]
        path.append(current)

    path.reverse()
    return path, best_prob

Reading the ImplementationLink Copied

Let's walk through how this code implements the formulas we developed:

Initialization (lines 17-24): We create two data structures: V for Viterbi scores and backpointer for tracking predecessors. Each is a list of dictionaries, one per position.
Base case (lines 26-30): For the first observation, we apply $V_1(s) = P(s) \cdot P(w_1 | s)$ . There's no predecessor, so backpointers are None.
Recursion (lines 32-50): The nested loops implement the recurrence. For each position i and each state s, we examine all predecessors s_prev, compute the score $V_{i-1}(s') \cdot P(s|s') \cdot P(w_i|s)$ , and keep the maximum. We store both the score (V[i][s]) and which predecessor achieved it (backpointer[i][s]).
Termination and backtracking (lines 52-63): We find the state with the highest final score (this is $s_n^* = \arg\max_s V_n(s)$ ), then follow backpointers backward to reconstruct the path.

The implementation uses a small epsilon (1e-10) instead of zero for missing probabilities to avoid numerical issues with exact zeros.

A Worked ExampleLink Copied

Now let's trace through this algorithm on a concrete problem. We'll use a simple HMM for weather inference: given a sequence of observed activities (walking, shopping, cleaning), infer the most likely sequence of weather states (sunny or rainy).

In[9]:

Code

# Simple HMM: weather affects activities
states = ["Sunny", "Rainy"]
observations = ["walk", "shop", "clean"]

# Initial probabilities
start_prob = {"Sunny": 0.6, "Rainy": 0.4}

# Transition probabilities
trans_prob = {
    ("Sunny", "Sunny"): 0.7,
    ("Sunny", "Rainy"): 0.3,
    ("Rainy", "Sunny"): 0.4,
    ("Rainy", "Rainy"): 0.6,
}

# Emission probabilities
emit_prob = {
    ("Sunny", "walk"): 0.6,
    ("Sunny", "shop"): 0.3,
    ("Sunny", "clean"): 0.1,
    ("Rainy", "walk"): 0.1,
    ("Rainy", "shop"): 0.4,
    ("Rainy", "clean"): 0.5,
}

# Run Viterbi
best_path, best_prob = viterbi_with_backpointers(
    observations, states, start_prob, trans_prob, emit_prob
)

The HMM parameters encode two types of knowledge about the weather-activity relationship:

Transition Probabilities $P(s_t | s_{t-1})$ : How likely is each weather state given the previous day's weather?

Transition probability matrix showing weather persistence. Sunny and rainy days both tend to continue (0.7 and 0.6 respectively).
Current State	→ Sunny	→ Rainy
Sunny	0.7	0.3
Rainy	0.4	0.6

Emission Probabilities $P(w | s)$ : How likely is each activity given the current weather?

Emission probability matrix showing activity preferences by weather. Walking strongly indicates sunny weather (0.6 vs 0.1); cleaning strongly indicates rain (0.5 vs 0.1). Shopping is ambiguous.
Weather State	walk	shop	clean
Sunny	0.6	0.3	0.1
Rainy	0.1	0.4	0.5

These tables reveal the model's structure. Weather tends to persist: sunny days have 70% chance of staying sunny, rainy days 60% chance of staying rainy. For activities, walking is a strong indicator of sunny weather, while cleaning suggests rain. Shopping is the most ambiguous activity, slightly favoring rainy days.

Out[10]:

Console

Viterbi Example: Weather from Activities
=======================================================

Observations: ['walk', 'shop', 'clean']
Possible states: ['Sunny', 'Rainy']

Step-by-step computation:
-------------------------------------------------------

Position 0: observing 'walk'
  V[0][Sunny] = P(Sunny) × P('walk'|Sunny)
           = 0.6 × 0.6 = 0.360
  V[0][Rainy] = P(Rainy) × P('walk'|Rainy)
           = 0.4 × 0.1 = 0.040

Position 1: observing 'shop'
  V[1][Sunny] = max over predecessors:
    from Sunny: 0.360 × 0.7 × 0.3 = 0.0756
    from Rainy: 0.040 × 0.4 × 0.3 = 0.0048
  V[1][Rainy] = max over predecessors:
    from Sunny: 0.360 × 0.3 × 0.4 = 0.0432
    from Rainy: 0.040 × 0.6 × 0.4 = 0.0096

-------------------------------------------------------

Optimal path: Sunny → Rainy → Rainy
Path probability: 0.012960

Let's interpret this step-by-step computation:

Position 0 (observing "walk"): We apply the base case formula $V_1(s) = P(s) \cdot P(w_1|s)$ . Sunny scores higher (0.360 vs 0.040) for two reinforcing reasons: the prior favors sunny days (0.6 vs 0.4), and walking is much more likely on sunny days (0.6 vs 0.1).

Position 1 (observing "shop"): Now the recurrence kicks in. For each current state, we consider both possible predecessors:

To reach Sunny: the best predecessor is Sunny (score 0.0756), since we benefit from both the high previous score and a favorable transition (sunny days tend to stay sunny)
To reach Rainy: again the best predecessor is Sunny (score 0.0432), despite the transition penalty, because the previous Sunny score was so much higher than Rainy

The result: The optimal path Sunny → Sunny → Rainy aligns with intuition: walking strongly suggests good weather, shopping is ambiguous (slightly favoring rain), and cleaning strongly suggests rain. The algorithm found this without examining all 8 possible paths. It computed only 12 values (2 states × 3 positions × 2 predecessor checks).

Out[11]:

Visualization

Grid showing two rows (Sunny, Rainy) and three columns (walk, shop, clean) with Viterbi scores and the optimal path highlighted in red. — Complete Viterbi trellis for the weather-activity example. Numbers in cells show the Viterbi score V[i][s] at each position. The red path marks the optimal sequence found by backtracking from the highest-scoring final state. Dashed gray arrows show the backpointers used for path reconstruction.