Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Conditional Random Fields › CRF Inference with the Viterbi Algorithm

Michael BrenndoerferUpdated May 6, 20253 min read

Language AI HandbookAll chapters

Part 6 of 67Sequence Labeling

Chapter 42Conditional Random Fields › CRF Inference with the Viterbi Algorithm

Reading section 5 of 13 · CRF Inference with the Viterbi Algorithm · 3 minSection 5 of 13 · 3 min

Section 5 of 13 · 3 min read

Conditional Random Fields › CRF Inference with the Viterbi AlgorithmOne section · Sections in this chapter5 / 13 ↓

Sections in this chapter13

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

Training gives us feature weights. Inference finds the most likely label sequence for new observations:

\mathbf{y}^* = \arg\max_{\mathbf{y}} P(\mathbf{y} | \mathbf{x}) = \arg\max_{\mathbf{y}} \sum_{t=1}^{n} \sum_k \lambda_k f_k(y_{t-1}, y_t, \mathbf{x}, t)

where:

$\mathbf{y}^*$ : the optimal label sequence we want to find
$\arg\max_{\mathbf{y}}$ : "the value of $\mathbf{y}$ that maximizes" the following expression
$P(\mathbf{y} | \mathbf{x})$ : the conditional probability of label sequence $\mathbf{y}$ given observations $\mathbf{x}$
The double sum computes the total score for a candidate label sequence

The second equality holds because the partition function $Z(\mathbf{x})$ is constant for a given input. Since $P(\mathbf{y} | \mathbf{x}) = \frac{1}{Z(\mathbf{x})} \exp(\text{score})$ , and the exponential function is monotonically increasing, maximizing the probability is equivalent to maximizing the unnormalized score. The Viterbi algorithm, which you may know from HMMs, efficiently finds this maximum-scoring path.

In[17]:

Code

def viterbi_decode(words, labels, feature_weights, templates):
    """
    Find the most likely label sequence using the Viterbi algorithm.

    Args:
        words: list of words
        labels: list of possible labels
        feature_weights: dict of feature name to weight
        templates: list of feature templates

    Returns:
        best_path: list of labels for each position
        best_score: score of the best path
    """
    n = len(words)
    K = len(labels)
    label_to_idx = {label: i for i, label in enumerate(labels)}

    # viterbi[t, y] = max score of paths ending in y at position t
    viterbi = np.full((n, K), -np.inf)
    # backpointer[t, y] = label at t-1 on best path to y at t
    backpointer = np.zeros((n, K), dtype=int)

    # Initialize
    for y_idx, y in enumerate(labels):
        features = extract_features(words, 0, "<START>", y, templates)
        score = sum(
            feature_weights.get(f, 0.0) * v for f, v in features.items()
        )
        viterbi[0, y_idx] = score

    # Recurrence
    for t in range(1, n):
        for y_idx, y in enumerate(labels):
            best_score = -np.inf
            best_prev = 0

            for y_prev_idx, y_prev in enumerate(labels):
                features = extract_features(words, t, y_prev, y, templates)
                score = sum(
                    feature_weights.get(f, 0.0) * v for f, v in features.items()
                )
                candidate_score = viterbi[t - 1, y_prev_idx] + score

                if candidate_score > best_score:
                    best_score = candidate_score
                    best_prev = y_prev_idx

            viterbi[t, y_idx] = best_score
            backpointer[t, y_idx] = best_prev

    # Find best final label
    best_final_idx = np.argmax(viterbi[n - 1, :])
    best_score = viterbi[n - 1, best_final_idx]

    # Backtrack to find path
    path_indices = [best_final_idx]
    for t in range(n - 1, 0, -1):
        path_indices.append(backpointer[t, path_indices[-1]])
    path_indices.reverse()

    best_path = [labels[i] for i in path_indices]
    return best_path, best_score


# Decode our example sentence
predicted_labels, score = viterbi_decode(
    sample_sentence, example_labels, example_weights, simple_templates
)

Out[18]:

Console

Viterbi Decoding Results:
==================================================
Sentence: ['The', 'quick', 'fox', 'jumps']

Best label sequence:
--------------------------------------------------
  The        → DET
  quick      → ADJ
  fox        → NOUN
  jumps      → VERB

Path score: 15.0000

The Viterbi algorithm has the same $O(nK^2)$ complexity as the forward algorithm. At each position, it tracks the best path to each label rather than summing all paths. Backpointers record which previous label led to the best score, enabling reconstruction of the optimal sequence.