A conditional random field (CRF) is a class of statistical modeling methods used for structured prediction in pattern recognition and machine learning. Unlike a classifier that predicts a label for a single sample without considering neighboring samples, a CRF can take context into account by modeling predictions as a graphical model that represents dependencies between them. The graph structure depends on the application: for example, in natural language processing, linear chain CRFs are popular, where each prediction depends only on its immediate neighbors; in image processing, the graph typically connects locations to nearby or similar locations to enforce consistent predictions.
CRFs are discriminative undirected probabilistic graphical models. Formally, given observations \(\boldsymbol{X}\) and random variables \(\boldsymbol{Y}\) indexed by vertices \(V\) of a graph \(G=(V,E)\), the pair \((\boldsymbol{X},\boldsymbol{Y})\) is a conditional random field if each variable \(\boldsymbol{Y}_v\), conditioned on \(\boldsymbol{X}\), obeys the Markov property with respect to the graph: its probability depends only on its neighbors in \(G\), not on other variables. This means the nodes are divided into two disjoint sets, observed variables \(\boldsymbol{X}\) and output variables \(\boldsymbol{Y}\), and the conditional distribution \(p(\boldsymbol{Y}|\boldsymbol{X})\) is modeled.
Applications
CRFs are widely used for labeling or parsing sequential data in natural language processing and biological sequences. Common tasks include part-of-speech tagging, shallow parsing, named entity recognition, gene finding, and peptide critical functional region finding. In computer vision, CRFs are applied to object recognition and image segmentation, where spatial context helps produce coherent labels. For example, in image segmentation, a CRF can enforce that neighboring pixels with similar colors receive the same label.
Inference
For general graphs, exact inference in CRFs is intractable, similar to Markov random fields. However, special cases allow exact solutions. If the graph is a chain or a tree, message passing algorithms yield exact results, analogous to the forward-backward and Viterbi algorithms used for hidden Markov models. If the CRF contains only pairwise potentials and the energy is submodular, combinatorial max-flow min-cut algorithms provide exact solutions. When exact inference is impossible, approximate methods include loopy belief propagation, alpha expansion, mean field inference, and linear programming relaxations.
Parameter Learning
Learning the parameters \(\theta\) is typically done by maximum likelihood estimation of \(p(Y_i|X_i;\theta)\). If all nodes have exponential family distributions and all nodes are observed during training, the optimization problem is convex and can be solved using gradient descent or quasi-Newton methods such as L-BFGS. If some variables are unobserved, inference must be performed for those variables, and because exact inference is intractable in general graphs, approximations are used.
Relation to Other Models
CRFs are related to hidden Markov models (HMMs) but are discriminative, modeling the conditional distribution directly rather than the joint distribution. This allows CRFs to incorporate arbitrary, overlapping features of the observations without independence assumptions. In sequence modeling, a linear chain CRF is a special case where the graph is a chain, making inference efficient. CRFs have been influential in Natural language processing and Computer vision, and remain relevant in modern Machine learning pipelines, though deep learning methods have largely replaced them in many applications. However, CRFs are sometimes combined with Neural network models, such as in neural CRFs for sequence labeling, where a neural network computes features and a CRF layer models dependencies.