Conditional Random Fields
CRFs are discriminative models for structured prediction that score whole label sequences given the full input.
Modeling structure discriminatively
A conditional random field (CRF) predicts a structured output, most often a label sequence, by modeling p(y | x) directly rather than the joint p(x, y). Unlike a hidden Markov model, it does not model how the inputs are generated, which frees it to use rich, overlapping features of the entire input without worrying about their dependencies.
The linear-chain form
The most common variant is the linear-chain CRF, which scores a label sequence as a normalized exponential of a sum of feature functions over adjacent label pairs and the input: p(y | x) = (1/Z(x)) exp( sum_t sum_k w_k f_k(y_{t-1}, y_t, x, t) ). The partition function Z(x) sums over all label sequences and is computed efficiently by a forward-backward pass.
Training and inference
Training maximizes the conditional log-likelihood, whose gradient is the difference between observed feature counts and model-expected feature counts; the expectations come from forward-backward. Because the objective is convex in the weights, gradient methods reach the global optimum. At prediction time, the Viterbi algorithm finds the highest-scoring label sequence.
Why discriminative helps
Generative models must explain the inputs, which can waste capacity and force independence assumptions among features. CRFs sidestep this by conditioning on the input, so features such as capitalization, word shape, gazetteer membership, and neighboring words can overlap freely. This made linear-chain CRFs the standard for named-entity recognition and part-of-speech tagging before, and often layered on top of, neural encoders.
- Convex training objective yields a global optimum
- Handles arbitrary, overlapping input features
- Regularize weights to control overfitting
- A CRF output layer still improves many neural taggers
General CRFs extend beyond chains to trees and grids, but exact inference is only tractable when the graph is simple; otherwise approximate inference is required.