Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data

1 Introduction

1. What are conditional random fields (CRFs)?
   Discriminative probabilistic models for segmenting and labeling sequence data that define a single globally normalized conditional distribution \(p(\mathbf{y} \mid \mathbf{x})\) over whole label sequences, relaxing the independence assumptions of HMMs and avoiding the label bias problem of MEMMs.
   • Lafferty et al., 2001, Conditional Random Fields (Proceedings of the 18th International Conference on Machine Learning (ICML)), §1
2. Why is it hard for generative models like HMMs to use rich features of the observations?
   A generative model defines a joint probability, so it must model the observations themselves; that requires enumerating observation sequences, typically as atomic units (words), and strict independence assumptions. Multiple interacting features or long-range dependencies make inference intractable.
   • Lafferty et al., 2001, Conditional Random Fields (Proceedings of the 18th International Conference on Machine Learning (ICML)), §1
3. What advantages do conditional models of label sequences have?
   They don’t spend modelling effort on the observations, which are fixed at test time anyway; the label probabilities can depend on arbitrary, non-independent features of the whole observation sequence (words and characters, layout, past and future observations) without modelling their distribution.
   • Lafferty et al., 2001, Conditional Random Fields (Proceedings of the 18th International Conference on Machine Learning (ICML)), §1
4. What is a maximum entropy Markov model (MEMM)?
   A conditional sequence model in which each source state has an exponential (maxent) model giving a distribution over next states given the current observation features (McCallum et al. 2000).
   • Lafferty et al., 2001, Conditional Random Fields (Proceedings of the 18th International Conference on Machine Learning (ICML)), §1
5. What is the label bias problem?
   In MEMMs and other models with per-state normalized next-state classifiers, transitions out of a state compete only with each other. All probability mass arriving at a state must be passed on (“conservation of score mass”): observations affect where it goes but not how much, biasing toward states with few outgoing transitions; a state with one outgoing transition ignores its observation entirely.
   • Lafferty et al., 2001, Conditional Random Fields (Proceedings of the 18th International Conference on Machine Learning (ICML)), §1
6. What is the critical difference between a CRF and an MEMM?
   An MEMM uses per-state exponential models for next-state probabilities given the current state; a CRF has a single exponential model for the joint probability of the entire label sequence given the observations, so feature weights at different states can be traded off against each other.
   • Lafferty et al., 2001, Conditional Random Fields (Proceedings of the 18th International Conference on Machine Learning (ICML)), §1