Conditional Random Fields (2001) › Theoretical Foundations and Inference

Part of what made CRFs so influential was the solid theoretical foundation they provided for structured prediction. They brought together ideas from probability theory, optimization, and dynamic programming into an elegant and principled framework.

The conditional probability formulation meant that CRFs normalized over the entire space of possible label sequences for a given input. This global normalization ensured that the model produced valid probability distributions, where all the probabilities for different possible labelings summed to exactly one. This contrasted with some earlier approaches that made local normalization decisions and could produce inconsistent global probability assignments.

The feature-based representation provided remarkable flexibility. In principle, any computable function that examines the input sequence and proposed output sequence can serve as a feature. This means researchers can incorporate insights from linguistics, domain knowledge about their specific task, or patterns observed in data analysis. The model structure itself does not constrain what features can be used, only requiring that each feature can be evaluated for any input-output pair.

Practical applications must find the most likely label sequence efficiently despite an exponentially large space of possible sequences. Fortunately, the sequential structure that CRFs assume allows for efficient inference using dynamic programming algorithms. The Viterbi algorithm, which had been used for decades in speech recognition and other sequence modeling problems, can find the optimal labeling in time proportional to the length of the sequence rather than exponential in that length. This computational tractability makes CRFs practical even for long sequences.

Training a CRF involves finding the feature weights that maximize the conditional likelihood of the correct labelings in the training data. This optimization problem is convex, meaning it has a single global optimum without local optima that might trap training algorithms. Standard optimization methods can reliably find good solutions, though the computation can be expensive for large datasets due to the need to compute the partition function during training.