Conditional Random Fields (CRF)

Unlike generative models (e.g., Hidden Markov Models) that model the joint probability P(X, Y), CRFs directly model the conditional probability P(Y|X) of a label sequence given an observation sequence. This eliminates the need to model complex dependencies in the input features, allowing the model to focus exclusively on the decision boundary. By conditioning on the entire observation sequence, a CRF can incorporate overlapping, non-independent features of the input without violating statistical assumptions.

The most common CRF architecture for NER is the linear-chain CRF, which models a first-order Markov dependency between adjacent output labels. This structure defines an undirected graphical model where each label Yi is connected to the observation sequence X and to its immediate neighbors Yi-1 and Yi+1. This captures transition constraints—for example, an I-ORG tag cannot follow a B-PER tag—enforcing valid BIO label sequences during decoding.

A defining characteristic of CRFs is that they compute a global partition function Z(X) that sums over all possible label sequences. This ensures the model produces a properly normalized probability distribution over entire sequences, not just local decisions. Unlike Maximum Entropy Markov Models (MEMMs), which normalize per-state and suffer from the label bias problem, CRFs avoid favoring states with fewer outgoing transitions, leading to more robust sequence-level predictions.

CRFs can incorporate arbitrary, overlapping feature functions without independence assumptions. Feature templates can capture:

• Token-level features: word identity, prefixes/suffixes, capitalization patterns, part-of-speech tags
• Contextual features: surrounding word windows, conjunctions of multiple attributes
• Label transition features: co-occurrence patterns between adjacent labels This flexibility made CRFs the dominant NER approach before deep learning, and they remain powerful when combined with neural feature extractors.

At inference time, CRFs use the Viterbi algorithm—a dynamic programming method—to find the single most probable label sequence. The algorithm recursively computes the maximum score path to each state at each position, storing backpointers to reconstruct the optimal sequence. This guarantees a globally optimal solution in O(T × S²) time, where T is sequence length and S is the number of states, ensuring that predicted label sequences respect learned transition constraints.

CRFs are trained by maximizing the conditional log-likelihood of the correct label sequence given the observations. The gradient involves the difference between the empirical feature counts from the training data and the expected feature counts under the current model distribution. Computing these expectations requires running the forward-backward algorithm to calculate marginal probabilities over all possible label paths, making training computationally intensive but statistically principled.