Conditional Random Fields: Discriminative Sequence Labeling with Rich Features

Hidden Markov Models brought probabilistic reasoning to sequence labeling, but their generative formulation imposes strong constraints. Each observation depends only on its corresponding hidden state, forcing independence assumptions that conflict with the overlapping, correlated features that make natural language rich and complex. When you see the word "bank," its context matters enormously: preceding words, suffixes, capitalization patterns, surrounding punctuation. HMMs struggle to incorporate such features without violating their independence assumptions.

Conditional Random Fields (CRFs) emerged as a direct response to these limitations. By modeling the conditional probability of labels given observations rather than their joint distribution, CRFs can incorporate arbitrary overlapping features without worrying about dependencies between them. This discriminative approach has become the foundation of modern sequence labeling, powering named entity recognition, POS tagging, and countless other NLP tasks.

This chapter develops CRFs from first principles. We'll examine why HMMs fall short, derive the CRF formulation mathematically, implement feature functions, and build working CRF taggers. By the end, you'll understand not just how to use CRFs but why they work so well for sequence labeling.

Before diving into CRFs, let's understand the fundamental distinction between generative and discriminative approaches to classification. This distinction explains why CRFs exist and what problems they solve.

Hidden Markov Models are generative. They model how sequences are produced: first, a hidden state is generated according to transition probabilities, then an observation is emitted according to emission probabilities. For a sequence of observations $\mathbf{x} = (x_1, x_2, \ldots, x_n)$ and labels $\mathbf{y} = (y_1, y_2, \ldots, y_n)$, an HMM models the joint probability of observations and labels:

where:

• $\mathbf{x} = (x_1, x_2, \ldots, x_n)$: the sequence of $n$ observations (e.g., words in a sentence)
• $\mathbf{y} = (y_1, y_2, \ldots, y_n)$: the sequence of $n$ labels (e.g., POS tags or entity types)
• $P(y_1)$: the initial state probability (probability of starting with label $y_1$)
• $P(y_t | y_{t-1})$: the transition probability from label $y_{t-1}$ to label $y_t$
• $P(x_t | y_t)$: the emission probability of observing $x_t$ given label $y_t$

The first product captures transition probabilities (how states follow each other), and the second captures emission probabilities (how each state generates its observation). To predict labels for new observations, we apply Bayes' rule:

where:

• $P(\mathbf{y} | \mathbf{x})$: the posterior probability of label sequence $\mathbf{y}$ given observations $\mathbf{x}$
• $P(\mathbf{x}, \mathbf{y})$: the joint probability computed by the HMM formula above
• $P(\mathbf{x})$: the marginal probability of the observations, obtained by summing $P(\mathbf{x}, \mathbf{y})$ over all possible label sequences

This generative formulation imposes a critical constraint: the observation $x_t$ can only depend on its own label $y_t$, not on other observations or labels. This independence assumption enables tractable inference but limits expressiveness.

Consider tagging the word "bank" in context. A good tagger should consider:

• The word itself: "bank"
• The previous word: "river" suggests location, "investment" suggests organization
• The next word: "account" suggests financial meaning
• Capitalization: "Bank" at sentence start vs. "bank" mid-sentence
• Word suffixes: "-ing," "-tion," "-ly" carry grammatical information
• Surrounding punctuation: quotation marks might indicate names

These features overlap and interact. The suffix "-ing" combined with a preceding auxiliary verb strongly suggests a verb tag. Capitalization plus a preceding determiner suggests a proper noun. HMMs cannot naturally express such feature combinations because each observation must be generated independently from its label alone.

In an HMM, we could only condition on the previous tag, not the previous word. The rich contextual features visible in the data cannot be exploited directly.

CRFs take a fundamentally different approach. Instead of modeling how observations are generated, they directly model the probability of a label sequence given the observations:

This conditional formulation has a crucial advantage: since we condition on $\mathbf{x}$, we don't need to model the distribution of observations. Features of $\mathbf{x}$ can overlap arbitrarily, interact in complex ways, and depend on any part of the input sequence. The model only needs to learn which label sequences are likely given the observed features.

The figure illustrates the fundamental difference. In HMMs, arrows point from hidden states to observations, reflecting the generative process. In CRFs, observations condition the labels, and features can connect any observation to any label. This reversal of direction is not merely notational; it fundamentally changes what the model can represent.

We've established that HMMs struggle with overlapping features because their generative structure demands independence between observations. Now we need a mathematical framework that preserves the sequential structure of HMMs while escaping their independence constraints. The solution lies in a family of models called log-linear models, which CRFs extend to sequences.

This section builds the CRF formulation step by step. We'll start with log-linear models for single classification decisions, then extend them to sequences, and finally examine the feature functions that give CRFs their expressive power. By the end, you'll see how CRFs elegantly solve the problems we identified with HMMs.

Before tackling sequences, let's understand how log-linear models work for a single classification decision. The core idea is beautifully simple: instead of modeling how observations are generated, we directly score how well each possible label fits the observed input.

Consider classifying a single word. We want to compute $P(y | \mathbf{x})$, the probability of label $y$ given input features $\mathbf{x}$. A log-linear model builds this probability in three steps:

1. Extract features: Define functions $f_k(\mathbf{x}, y)$ that measure relevant properties of the input-label pair
2. Compute a score: Sum the weighted features to get an overall "compatibility score" for each label
3. Normalize to probabilities: Convert scores to probabilities using the exponential function and normalization

This yields the fundamental log-linear equation:

Let's unpack each component:

• $f_k(\mathbf{x}, y)$: the $k$-th feature function, which extracts a property of the input-output pair. These are the building blocks of the model, returning real numbers (often 0 or 1 for binary features).
• $\lambda_k$: the weight for feature $f_k$, learned from training data. Positive weights encourage labels where the feature fires; negative weights discourage them.
• $\sum_k \lambda_k f_k(\mathbf{x}, y)$: the total score for assigning label $y$ to input $\mathbf{x}$. This is just a weighted sum of features.
• $\exp(\cdot)$: the exponential function transforms scores into positive values, ensuring we can interpret results as probabilities.
• $Z(\mathbf{x}) = \sum_{y'} \exp\left( \sum_k \lambda_k f_k(\mathbf{x}, y') \right)$: the partition function, which sums over all possible labels to normalize the distribution.

The partition function $Z(\mathbf{x})$ deserves special attention. It ensures that probabilities sum to 1 by computing the total "mass" across all possible labels. For single classification with a small label set, computing $Z$ is trivial. But as we'll see, computing $Z$ for sequences becomes the central computational challenge of CRFs.

Why is this formulation powerful? Because feature functions can capture any aspect of the input-output relationship. Unlike HMMs, where each observation depends only on its label, log-linear models can incorporate overlapping, interacting features without any independence assumptions.

Notice what happened here. Three features fired for the word "running": the word itself, its suffix, and the preceding word. Each feature contributed to the scores for different labels, and the model combined them through weighted summation. The suffix -ing combined with prev_word=is provides strong evidence for VERB, and the learned weights reflect this intuition. The model assigned VERB a probability of over 99% by combining multiple overlapping features, something an HMM could never do.

The log-linear model handles single classification decisions elegantly. But sequence labeling requires something more: we need to model entire sequences of labels, where each label might depend on its neighbors. How do we extend the log-linear framework to sequences while preserving its ability to use arbitrary features?

The answer is the linear-chain CRF. The key insight is to treat the entire label sequence as a single structured output, then score it using features that can look at adjacent labels and any part of the input. Instead of independently classifying each position, we score complete label sequences and find the one with the highest probability.

For a sequence of observations $\mathbf{x} = (x_1, \ldots, x_n)$ and labels $\mathbf{y} = (y_1, \ldots, y_n)$, the linear-chain CRF defines:

This formula looks similar to the single-classification case, but with a crucial difference: we now sum over positions in the sequence, and feature functions examine pairs of adjacent labels. Let's break it down:

• $\sum_{t=1}^{n}$: We accumulate scores across all positions in the sequence
• $f_k(y_{t-1}, y_t, \mathbf{x}, t)$: Each feature function now takes four arguments

The four arguments to feature functions are the heart of CRF expressiveness:

This design is deliberate. By including both $y_{t-1}$ and $y_t$, features can model label-label dependencies like HMM transitions. By including the entire sequence $\mathbf{x}$ rather than just $x_t$, features can examine context: the previous word, the next word, or even words further away. The position $t$ enables features that behave differently at sequence boundaries.

The partition function for sequences presents a computational challenge:

This sum ranges over all possible label sequences $\mathbf{y}'$. With $K$ labels and sequence length $n$, there are $K^n$ possible sequences. For a modest vocabulary of 10 labels and a 20-word sentence, that's $10^{20}$ sequences, far too many to enumerate. Fortunately, the linear-chain structure enables efficient computation through dynamic programming, which we'll explore in the next section.

We've seen that CRFs score sequences using weighted sums of feature functions. But what exactly are these features, and how do we design them? This is where CRFs truly shine: feature functions can capture virtually any pattern you can imagine, from simple word-label associations to complex contextual dependencies.

Feature functions fall into two main categories, each serving a distinct purpose in the model.

State Features: Linking Observations to LabelsLink Copied

State features capture the relationship between observations and labels. They answer the question: "Given what I observe at this position, which label is most appropriate?"

Consider a feature that fires when the word "bank" appears with the label NOUN:

The notation $\mathbf{1}[\cdot]$ denotes the indicator function, which returns 1 if the condition is true and 0 otherwise. The product of two indicators returns 1 only when both conditions hold. So this feature "fires" (returns 1) precisely when:

• The current word is "bank", AND
• The current label is NOUN

If the learned weight $\lambda_k$ is positive, this feature increases the score for labeling "bank" as NOUN. If negative, it discourages that labeling. The training process learns these weights from data.

But state features aren't limited to the current word. Because feature functions receive the entire observation sequence $\mathbf{x}$, they can examine context:

• Previous word: Does "river" precede this word? (suggests location)
• Next word: Does "account" follow? (suggests financial meaning)
• Suffixes: Does the word end in "-ing"? (suggests verb)
• Capitalization: Is the word capitalized mid-sentence? (suggests proper noun)

This flexibility is what HMMs lack. In an HMM, the observation "bank" can only depend on its own label. In a CRF, the feature for "bank" can simultaneously consider the previous word, the next word, and any other contextual signal.

Transition Features: Modeling Label DependenciesLink Copied

Transition features capture patterns in how labels follow each other. They answer: "Given the previous label, which labels are likely to come next?"

Consider a feature for the common grammatical pattern where nouns follow determiners:

This feature fires when a NOUN follows a DET, capturing patterns like "the cat" or "a dog." A positive weight encourages this transition; a negative weight would discourage it.

Transition features serve a similar role to HMM transition probabilities, but with an important difference: they can also incorporate observations. A feature like "NOUN follows DET when the current word is capitalized" combines transition and observation information in ways HMMs cannot express.

Look at the variety of information captured by these features. For a single word "fox" at position 2, we extract:

• Word identity: The word itself and its lowercase form
• Morphological properties: Two-character and three-character suffixes and prefixes
• Capitalization: Whether the word starts with an uppercase letter
• Context: The previous word ("quick") and next word ("jumps")
• Label transition: The pattern of moving from ADJ to NOUN

Each of these features will have a learned weight. During training, the model discovers which features are predictive: perhaps words ending in "-ly" strongly indicate adverbs, or capitalized words following "the" often indicate proper nouns. The power lies in combining many weak signals into a strong prediction.

Having built up the CRF formulation, it's illuminating to see how it relates to HMMs. This comparison reveals that HMMs are actually a special case of CRFs with a restricted feature set.

An HMM has two types of parameters:

1. Transition probabilities $P(y_t | y_{t-1})$: How likely is each label given the previous label?
2. Emission probabilities $P(x_t | y_t)$: How likely is each observation given its label?

We can express these as CRF features:

The correspondence is precise: if we set the CRF weight for transition_ADJ_NOUN to $\log P(\text{NOUN} | \text{ADJ})$ and the weight for emission_fox_NOUN to $\log P(\text{fox} | \text{NOUN})$, the CRF assigns the same relative probabilities to label sequences as the HMM.

But here's the crucial insight: CRFs can do everything HMMs can do, and more. While an HMM is limited to these two feature types, a CRF can add:

• Features that examine the previous word (not just the previous label)
• Features that look at the next word
• Features based on word suffixes, prefixes, or character patterns
• Features that combine multiple signals (e.g., "capitalized word after a determiner")
• Features that span multiple positions

The HMM is a CRF with its hands tied. By removing the generative constraints, CRFs unlock the full power of discriminative modeling for sequences. This is why CRFs consistently outperform HMMs on sequence labeling tasks: they can leverage the same information HMMs use, plus arbitrarily more.

The partition function $Z(\mathbf{x})$ is the computational challenge of CRFs. It sums over all possible label sequences, and with $K$ labels and sequence length $n$, there are $K^n$ such sequences. For $K=10$ labels and $n=20$ words, that's $10^{20}$ sequences, far too many to enumerate.

Fortunately, the linear-chain structure enables efficient computation via dynamic programming. The forward algorithm computes $Z(\mathbf{x})$ in $O(nK^2)$ time, similar to the forward algorithm for HMMs.

The key idea is to define a forward variable $\alpha_t(y)$ that accumulates scores for all partial label sequences ending in label $y$ at position $t$:

where:

• $\alpha_t(y)$: the forward variable at position $t$ for label $y$
• $\mathbf{y}_{1:t-1}$: all possible label assignments for positions 1 through $t-1$
• The sum aggregates scores over all ways to reach label $y$ at position $t$
• The constraint $y_t = y$ fixes the label at position $t$

Intuitively, $\alpha_t(y)$ represents the total "mass" of all paths that end in label $y$ at position $t$. The crucial insight is that we can compute $\alpha_t(y)$ recursively from the previous position:

where:

• $y'$: iterates over all possible labels at position $t-1$
• $\alpha_{t-1}(y')$: the forward variable from the previous position
• $\exp\left( \sum_k \lambda_k f_k(y', y, \mathbf{x}, t) \right)$: the score for transitioning from $y'$ to $y$ at position $t$

This recurrence says: to compute the total score of paths ending in $y$ at position $t$, sum over all possible previous labels $y'$, multiplying the score of reaching $y'$ by the score of the transition from $y'$ to $y$.

Once we've computed forward variables for all positions, the partition function is simply the sum over all labels at the final position:

where the sum is over all possible labels $y$ at the final position $n$. This works because every complete label sequence must end with some label at position $n$.

The forward variables show how probability mass accumulates through the sequence. At position 0, "The" has high scores for DET due to the matching feature weight. As we move through the sequence, the algorithm combines emission scores (how well each word matches each label) with transition scores (how likely each label sequence is). The log partition function aggregates all possible paths, enabling probability computation. Higher values indicate more probable label assignments at each position.

The forward algorithm exploits the linear-chain structure: at each position, we only need to consider transitions from labels at the previous position. This reduces the exponential enumeration to polynomial computation.

Throughout CRF computations, we work in log space. Multiplying many probabilities (or exponentials of scores) quickly leads to numerical underflow. By using the log-sum-exp operation, we maintain numerical stability:

where:

• $x_i$: the $i$-th value we want to sum (in our case, log-scores for different label sequences)
• $\max_i(x_i)$: the maximum value among all $x_i$
• $e^{x_i - \max_i(x_i)}$: the exponentiated value after subtracting the maximum

This identity is mathematically exact but numerically superior. The trick works because subtracting the maximum ensures that at least one term in the sum equals $e^0 = 1$, while all other terms are less than 1. This prevents both overflow (from exponentiating large positive numbers) and underflow (from exponentiating large negative numbers).

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

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.

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.

Now let's build a practical CRF tagger using the sklearn-crfsuite library, which provides an efficient implementation with all the features we've discussed.

Now let's train the CRF model:

Even with minimal training data, the CRF correctly identifies person names (Tim Cook, with B-PER and I-PER tags) and organizations (Amazon as B-ORG). The model generalizes from the training examples by learning that capitalized words following patterns similar to training entities are likely named entities. Let's examine what features it learned to value:

The feature weights reveal what patterns the CRF learned to associate with each entity type. High positive weights indicate strong evidence for that label. Features like word.istitle (capitalization) and specific word forms from the training data carry the most weight, which aligns with our intuition that named entities are typically capitalized and follow predictable patterns.

CRFs also learn transition patterns between labels. Let's examine them:

The transition weights show strong preferences for valid BIO sequences. Transitions from B-tags to their corresponding I-tags have high positive weights, encouraging entity continuation. Transitions between different entity types (like B-PER to I-ORG) are penalized with negative weights, enforcing the constraint that I-tags must follow their matching B-tag.

The transition weights reveal what the model learned about valid sequences. High positive weights between B-TYPE and I-TYPE labels encourage entity continuation. Negative weights for invalid transitions (like B-PER to I-LOC) discourage label sequences that violate BIO constraints.

Let's build a more complete NER system using a larger dataset. We'll use the CoNLL-2003 format, a standard for NER evaluation.

Now let's define richer features for NER and train a CRF: