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

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.

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.

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.

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).

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.

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.

A finite-state model branches at r into a path for rib (state 1) and one for rob (state 4). On input r i b, both states 1 and 4 have a single outgoing transition, so state 4 must pass on all its mass though it has rarely seen i: the two paths stay about equally likely regardless of the observations, and whichever word was slightly more frequent in training always wins.

Changing the state structure, e.g. collapsing states 1 and 4 to delay branching (determinization, not always possible and can explode combinatorially); or starting fully connected and letting training find structure, which discards valuable prior structural knowledge.

It must score whole state sequences at once, letting some transitions “vote” more strongly than others depending on the observations: score mass isn’t conserved, and transitions can amplify or dampen the mass they receive.

Let \(G = (V, E)\) be a graph indexing the label variables \(\mathbf{Y} = (Y_v)_{v \in V}\). \((\mathbf{X}, \mathbf{Y})\) is a CRF if, conditioned on \(\mathbf{X}\), each \(Y_v\) obeys the Markov property with respect to \(G\): \(p(Y_v \mid \mathbf{X}, Y_w, w \neq v) = p(Y_v \mid \mathbf{X}, Y_w, w \sim v)\). It is a random field globally conditioned on the observations.

By the Hammersley–Clifford theorem, with edge features \(f_k\) and vertex features \(g_k\): \(p_\theta(\mathbf{y} \mid \mathbf{x}) \propto \exp\big(\sum_{e,k} \lambda_k f_k(e, \mathbf{y}|_e, \mathbf{x}) + \sum_{v,k} \mu_k g_k(v, \mathbf{y}|_v, \mathbf{x})\big)\), normalized by an observation-dependent \(Z(\mathbf{x})\).

A Boolean \(g_k\) true if word \(X_i\) is upper case and tag \(Y_i\) is “proper noun”. Features need not fully specify a state or observation, and can look at any part of \(\mathbf{x}\).

With one feature per label pair \((y', y)\) and one per label–observation pair \((y, x)\); their weights \(\lambda_{y',y}\), \(\mu_{y,x}\) play the role of log transition and emission probabilities. But CRFs normalize per observation sequence, \(Z(\mathbf{x})\), giving conditional rather than joint distributions, and can add arbitrary observation features.

HMM: labels generate observations (directed). MEMM: each label conditioned on the previous label and observation, normalized per state. CRF: an undirected chain over labels, globally conditioned on all observations.

For each position define \(M_i(y', y \mid \mathbf{x}) = \exp(\Lambda_i(y', y \mid \mathbf{x}))\) from the edge and vertex features there. Then \(p(\mathbf{y} \mid \mathbf{x}) = \prod_i M_i(y_{i-1}, y_i \mid \mathbf{x}) / Z(\mathbf{x})\) and \(Z(\mathbf{x}) = (M_1 M_2 \cdots M_{n+1})_{\text{start}, \text{stop}}\), computed directly for the given \(\mathbf{x}\).

The log-likelihood objective is convex (CRFs share the convexity of general maximum entropy models), so training converges to the global optimum.

By maximizing conditional log-likelihood with improved iterative scaling variants. Algorithm S adds a global “slack” feature making the total feature count constant; Algorithm T tracks partial feature totals per sequence and converges faster when lengths vary. Expectations come from forward–backward vectors \(\alpha_i = \alpha_{i-1} M_i\), \(\beta_i = M_{i+1} \beta_{i+1}\).

Its slack constant \(S\) is proportional to the longest training sequence length, so each iteration takes very small steps.

Roughly as costly in time and space as one Baum–Welch iteration for HMMs, because expectations are computed with forward–backward recursions over the chain.

With identical topology and only symbol-identity features, the CRF erred about 5% of the time while the MEMM erred about 42%, failing to discriminate the two branches: a direct demonstration of label bias.

Data came from HMMs mixing first- and second-order dependencies; as data became more second-order, all first-order models erred more. CRFs typically beat MEMMs by a wide margin, HMMs beat MEMMs, and CRFs beat HMMs on mostly second-order data: CRFs are more robust to inaccurate modelling assumptions.

With the same tag–word and tag–tag parameters, HMM beat MEMM (label bias) and CRF beat HMM. Adding orthographic features (capitalization, numbers, hyphens, suffixes like -ing, -ed, -tion) helped MEMMs and CRFs greatly, especially on out-of-vocabulary words.

Initialize the CRF with the trained MEMM’s parameters; it then converged in about 1,000 iterations, while training from all-zero parameters had not converged after 2,000.

Training with AdaBoost’s exponential loss over whole sequences (using forward–backward for feature expectations), feature selection and induction (adapting Della Pietra et al.’s methods), and tree-structured or grammar-like CRFs (analogues of stochastic context-free grammars).

They are the first to combine conditional modelling with the global normalization of random fields: earlier work either built generative exponential models with hard normalization (Rosenfeld) or local conditional models (Berger et al., Ratnaparkhi, MEMMs) that can suffer from label bias.