Lafferty 2001 Conditional Random Fields

Citation

John Lafferty, Fernando Pereira, and Andrew McCallum. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of ICML.

Online version

An online version of this paper is available [1].

Summary

This paper introduces Conditional Random Fields as sequential classification model.

Drawbacks with HMMs and MeMMs

The paper points out the some of main drawbacks in generative models such as HMMs and in discriminative ones such as Maximum Entropy Markov Models:

• HMMs don't allow the addition of overlapping arbitrary features of the observations.

• MeMMs are normalized locally over each observation, and hence suffer from the Label Bias problem, where the transitions going out from a state compete only against each other, as opposed to all the other transitions in the model.

Mathematical Definition of CRFs

The paper then introduces Conditional Random Fields as a model that addresses both of these problems, and defines them formally:

The probability P(Y/X) of a state sequence Y given an observation sequence X is:

where y|S is the set of components of y associated with the vertices in subgraph S, and features $f_{k}$ and $g_{k}$ are given and fixed CRFs can be conceptualized as:

Parameter Estimation for CRFs

The paper provides two methods to perform parameter estimation (training) for CRFs, both based on improved iterative scaling. These methods differ in how they keep track of the total feature count T(x,y):

• Algorithm S does so by using a "slack feature":

• Algorithm T keeps track of partial T totals.

Algorithm S may converge slowly if the longest training observation sequence is very long. If the length of the observation sequences and the number of active features varies greatly, algorithm T converges substantially faster. One iteration of either Algorithm S or Algorithm T has roughly the same time and space complexity as the Baum-Welch training algorithm for HMMs. Both are guaranteed to converge.

Experiments

The authors performs three different types of experiments:

• They generate synthetic data from an HMM, and use this data to train a CRF and an MeMM with the same structures. They find that the CRF error is 4.6% and the MeMM error is 42%, thus proving that the CRF solves the label bias problem encountered by the MeMM.

• They generate synthetic data using a mix of first-order and second-order HMMs, and train first-order HMM, MeMM and CRF models on this data, without using any overlapping features. They find that CRFs perform the best, thus showing their robustness to incorrect modeling assumptions. The addition of overlapping features substantially improves the performance of CRFs and MeMMs

• Finally, they perform POS tagging on a subset of the Penn Treebank, using an HMM, MeMM and a CRF. They repeat this both without and with orthographic features. Without orthographic features, the HMM outperforms the MeMM and the CRF outperforms the HMM, while with them, the MeMM and CRF both significantly outperform HMMs, and the CRF still remains the best.

Conclusion

The authors conclude that CRFs offer the following significant advantages: discriminative training, combination of arbitrary, overlapping features from both the past and future; efficient training and decoding based on dynamic programming; and parameter estimation guaranteed to find the global optimum. Their main disadvantage is the slow convergence of the training algorithm compared to MeMMs and HMMs.

Related papers

The Sha 2003 shallow parsing with conditional random fields paper uses a simpler version of CRFs called linear-chain CRFs ,that model the states as being a chain, to perform NP (Noun Phrase) chunking. It also compares different methods of training CRFs, such as CG, L-BFGS, GIS etc.