Conditional Random Fields: Global Normalisation for Sequence Labels

Score the whole output

Let \(e_t(j,x)\) score label \(j\) at position \(t\) and \(A_{ij}\) score a transition from label \(i\) to label \(j\). Include start and end scores explicitly in an implementation. Ignoring those boundary terms in the notation,

where \(Z(x)=\sum_{y'\in\mathcal Y(x)}e^{s(x,y')}\) sums over the allowed sequences. Unlike an HMM, the CRF does not need a generative probability distribution for the input words. The emission scores may come from hand-built features or a neural encoder.

Local interactions among labels do not require local input features. An encoder can inspect the full sentence before emitting each position’s scores. Keep those two kinds of dependency separate.

A partition function is a weighted path sum

In log space, define the forward value

where \(\operatorname{LSE}(z)=\log\sum_i e^{z_i}\). After adding any end scores, a final log-sum-exp gives \(\log Z(x)\). The same chain with maximum in place of log-sum-exp gives Viterbi decoding and needs backpointers to reconstruct labels.

Log-sum-exp can be evaluated as \(m+\log\sum_i e^{z_i-m}\) with \(m=\max_i z_i\). This retains the exact sum algebra while avoiding unnecessarily large exponentials.

A tiny globally normalised example

For two positions and labels A/B, suppose the complete path scores are AA=2, AB=1, BA=0 and BB=1. Then

AA wins, but it does not have probability one. If AB is the gold path, its negative log likelihood is \(\log Z-1\approx1.627\). Training must raise AB relative to all competing paths, not merely increase an isolated token’s score.

The gradient compares observed and expected features

For a feature-linear score \(s_\theta(x,y)=\theta^\top f(x,y)\), the negative log-likelihood gradient is

The partition function supplies the model expectation. Forward–backward computes the necessary position and transition marginals efficiently. A feature appearing in the gold sequence more often than the model expects receives pressure to increase its weight.

This formula also explains why dropping the partition term is not a harmless shortcut: it removes the competition against alternative outputs and changes the learning problem.

Encode legal entity transitions

In a specified BIO convention, an I-ORG label cannot freely start a sequence or follow an incompatible entity type. Set illegal transition scores to negative infinity or otherwise exclude those paths consistently. The same allowed set should define both training normalisation and decoding if the intended model is a constrained CRF.

Padding introduces a second boundary problem. A masked position should not contribute emissions, transitions or the wrong final-state score. Test sequences of length one, empty masked tails and different batch lengths on a tiny enumerated example before trusting a vectorised implementation.

When structured decoding helps

A CRF can fix locally inconsistent label combinations, but it cannot recover a missing entity boundary from arbitrary features by guarantee. Compare a token classifier and a structured head using the same encoder and span-level evaluation. This isolates the contribution of sequence structure from the representation underneath it.

Global normalisation also avoids the particular local-normalisation behaviour associated with label bias in locally normalised sequence models. It does not mean that every CRF is automatically calibrated or robust outside its training domain.

References

1. Lafferty, McCallum and Pereira. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. ICML, 2001.
2. Sutton and McCallum. An Introduction to Conditional Random Fields. 2012.