Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data

Sequence labeling is one of the most fundamental tasks in NLP: given a sentence, assign a tag to every word. Is "bank" a noun or a verb? Is "Washington" a person or a place? The answer depends on context — and crucially, on what the neighboring tags are.

Before CRFs, two approaches dominated:

Hidden Markov Models are generative: they model the joint probability P(x, y) of observations and labels. But HMMs make a strong independence assumption — each observation depends only on its own label. This means you can't use features like "the previous word is 'the'" or "this word is capitalized AND the next word is a verb." Real language is full of such overlapping, correlated cues.

Maximum Entropy Markov Models (MEMMs) fix the feature problem: they're discriminative and can use arbitrary features. But they introduce a worse problem — label bias. Because each state normalizes its outgoing transitions independently, states with fewer successors effectively ignore the input. Imagine a highway exit with only one ramp: no matter what the road sign says, you take that ramp. The model's predictions become disconnected from the actual observations.

The key insight of CRFs is deceptively simple: instead of making a local decision at each position and normalizing per state, define a single score for the entire label sequence and normalize once over all possible label sequences. This is the difference between a locally normalized model (MEMM) and a globally normalized model (CRF).

A CRF defines the conditional probability of a label sequence y given an observation sequence x as:

Think of it like a panel of judges scoring an ice skating routine. An HMM judge scores each element in isolation. An MEMM judge watches the full routine but writes each score on a separate card that's immediately finalized. A CRF judge watches the full routine, writes a single score for the whole performance, and that score reflects how well all the elements fit together.

The power of CRFs lies in their feature functions. Each feature function $f_k(y_{t-1}, y_t, \mathbf{x}, t)$ is a binary or real-valued function that captures a specific pattern. For example:

• "Is the current word capitalized AND the label is PROPER-NOUN?" → 1 or 0
• "Is the previous label DETERMINER and the current label NOUN?" → 1 or 0
• "Does the current word end in '-ing' AND the label is VERB?" → 1 or 0
• "Is the current word in a gazetteer of city names AND the label is LOCATION?" → 1 or 0

Each feature has a learned weight $\lambda_k$. Positive weights encourage patterns; negative weights discourage them. The total score for a label sequence is the weighted sum of all features fired across all positions — and the partition function Z(x) ensures these scores become valid probabilities.

This is exactly what makes CRFs strictly more powerful than HMMs for feature-rich tasks: you can throw in any feature you can compute from the input, without worrying about independence assumptions.

The label bias problem is subtle but devastating. In an MEMM, each state normalizes its outgoing transition probabilities to sum to 1. This sounds harmless, but consider a state with only one outgoing transition: that transition gets probability 1.0 no matter what the observation is. The model literally cannot use the input to change its mind at that state.

More generally, states with fewer outgoing transitions have an unfair advantage: their probability mass doesn't get split as many ways. The result is that the globally optimal path can be dominated by these "low-branching" states, even when the input evidence strongly contradicts them.

CRFs solve this by removing per-state normalization entirely. The score of a label sequence is an unnormalized sum of feature weights; only the final division by Z(x) turns scores into probabilities. Every transition competes against every other possible label sequence globally, so no state can hoard probability mass.

There is a clean parallel between pairs of models. Logistic regression is the discriminative counterpart of Naive Bayes: both handle single classifications, but logistic regression models P(y|x) directly while Naive Bayes models the joint P(x,y).

CRFs extend this parallel to sequences. An HMM is Naive Bayes stretched over a chain: generative, with independence assumptions. A linear-chain CRF is logistic regression stretched over a chain: discriminative, with no independence assumptions on the input.

Just as logistic regression consistently outperforms Naive Bayes when you have enough data, CRFs consistently outperform HMMs on feature-rich sequence labeling tasks.

The partition function $Z(\mathbf{x})$ is the denominator that turns raw scores into valid probabilities. It sums the exponentiated scores over every possible label sequence:

Think of the partition function as a normalizing constant that answers: "across every conceivable way to label this sentence, what is the total unnormalized weight?" Once you know that total, you can say what fraction belongs to any particular labeling.

Computing Z(x) efficiently is essential: it appears in both the probability computation and the gradient during training. The forward algorithm builds it up position by position, reusing intermediate results — each position needs only the accumulated scores from the previous position, times the local potential.

Two inference problems matter in CRFs:

1. Computing marginals — "what is the probability that position t has label j?" This is needed for the gradient during training. The forward-backward algorithm, a message-passing scheme over the linear chain, solves this in O(T × L²) time.

2. Finding the best sequence — "which complete label sequence has the highest probability?" The Viterbi algorithm answers this, again in O(T × L²). It's the same dynamic programming idea: walk forward through the chain, and at each position keep only the best-scoring partial path ending in each label. Then trace back to recover the full best sequence.

Both algorithms are direct adaptations of the HMM versions. The only difference is the potential functions: HMMs use $P(x_t|y_t) \times P(y_t|y_{t-1})$, while CRFs use $\exp(\sum_k \lambda_k f_k(y_{t-1}, y_t, \mathbf{x}, t))$.

CRF training maximizes the conditional log-likelihood of the correct label sequences in the training data. For a training pair $(\mathbf{x}, \mathbf{y})$, the objective is:

The gradient takes a clean, intuitive form: $\frac{\partial \mathcal{L}}{\partial \lambda_k} = \underbrace{\sum_t f_k(y_{t-1}, y_t, \mathbf{x}, t)}_{\text{observed count}} - \underbrace{\sum_t \sum_{y', y''} f_k(y', y'', \mathbf{x}, t)\, P(y', y'' | \mathbf{x})}_{\text{expected count}}$ This is a recurring theme in machine learning: the gradient pushes the model's expected statistics toward the empirical statistics. Training converges when the model's predictions match reality on average.

The original paper used iterative scaling for optimization; modern implementations use L-BFGS or stochastic gradient descent, which converge much faster in practice.

CRFs became the dominant approach for structured prediction in NLP for well over a decade. Almost every winning system for named entity recognition, part-of-speech tagging, shallow parsing, and information extraction from 2001 to 2015 used a CRF — either standalone with handcrafted features, or as an output layer on top of neural feature extractors.

The BiLSTM-CRF architecture deserves special mention. By feeding learned neural representations from a bidirectional LSTM into a CRF output layer, researchers got the best of both worlds: deep features from the neural network and consistent sequential predictions from the CRF. This architecture dominated NER benchmarks for years.

Beyond NLP, CRFs extended to computer vision — most notably in DeepLab, where a CRF refines pixel-level predictions from a CNN to produce sharp, coherent segmentation boundaries. In bioinformatics, CRFs model gene structure and protein secondary structure.

Even in the era of large language models, the CRF idea lives on. Whenever a system needs structured, consistent output labels — not just independent per-token predictions — the CRF principle of global normalization remains relevant.