Conditional random fields (CRFs)

Summary

A CRF is a discriminative, undirected graphical model that defines $p (y ∣ x)$ over a structured output $y$ (e.g. a label sequence), scoring entire labelings jointly through feature functions over cliques, most commonly a linear-chain CRF that couples adjacent labels.

CRFs are the classic answer to structured prediction: when your outputs are interdependent (the label of token $t$ depends on token $t - 1$ ), independent per-token softmax classification is wrong because it can produce illegal or incoherent label sequences (e.g. an I-PER tag right after an O tag in BIO tagging). A CRF layer fixes this by modeling transitions.

They remain interview-relevant because:

A linear-chain CRF on top of a BiLSTM or transformer encoder was the standard NER / POS / chunking architecture and still appears in production sequence taggers.
CRF vs HMM is the cleanest way to show you understand generative vs discriminative modeling of sequences.
The training objective is a clean example of a globally-normalized log-likelihood with a forward-algorithm partition function.

The model

A linear-chain CRF scores a full label sequence $y = (y_{1}, \dots, y_{T})$ given input $x$ :

p (y ∣ x) = \frac{1}{Z ( x )} exp (t \sum ψ_{t} (y_{t}, x) + t \sum A (y_{t - 1}, y_{t})),

where $ψ_{t}$ is the emission / unary score (how well label $y_{t}$ fits position $t$ , often the logits from a neural encoder), $A (y_{t - 1}, y_{t})$ is a learned transition score between adjacent labels, and

Z (x) = y^{'} \sum exp (\dots)

is the partition function: a sum over all $∣ V ∣^{T}$ possible labelings. $Z$ couples the whole sequence through global normalization. Per-token softmax instead normalizes each position locally and independently.

Learning objective

Transition scores can overturn the locally best labels

Derivation

the token emissions stay fixed. Softmax takes each column's maximum and cannot penalize the invalid O → I-PER pair. The CRF adds a learned score for each adjacent-label transition, compares complete paths, and selects B-PER → I-PER in this example. The forward algorithm sums the exponentiated scores of all paths to compute Z; Viterbi finds the highest-scoring path.

Check: Why does the locally preferred O-to-I-PER path lose after transition scoring?

Read it this way: Local emissions favor AA, but its transition penalty is -5. Globally, AB or BA scores 3 and beats AA at -1.
Does the path with the best local emissions still win after its transition penalty?

Training and inference

The partition function looks intractable ( $∣ V ∣^{T}$ terms) but factorizes over the chain:

Training: maximize $lo g p (y ∣ x)$ . The gradient needs $Z (x)$ and the marginals, both computed by the forward algorithm (the same dynamic program as HMM forward-backward) in $O (T ∣ V ∣^{2})$ .
Decoding: find $ar g max_{y} p (y ∣ x)$ with the Viterbi algorithm, also $O (T ∣ V ∣^{2})$ .

So a CRF reuses exactly the forward-backward and Viterbi machinery, but on a discriminatively trained, globally normalized model.

CRF vs HMM vs softmax tagger

	Models	Normalization	Features
HMM	$p (x, y)$ generative	local (per emission/transition)	tied to generative story
MEMM	$p (y ∣ x)$ , per-step	local (per step) → label bias	rich, but biased
Linear-chain CRF	$p (y ∣ x)$	global (one $Z$ per sequence)	rich, no label bias
Independent softmax	$\prod_{t} p (y_{t} ∣ x)$	local, independent	no transition modeling

The CRF’s global normalization is what cures the label-bias problem of MEMMs (locally normalized models that can’t redistribute probability mass once committed at a step).

The neural CRF (BiLSTM-CRF / Transformer-CRF)

In modern systems the encoder (BiLSTM or transformer) produces the emission scores $ψ_{t}$ , and a small learned transition matrix $A$ sits on top. The whole stack is trained end-to-end with the CRF negative log-likelihood. The encoder captures rich context; the CRF enforces valid, coherent label transitions. This combination reliably beats a softmax-per-token head on tasks with strong output structure (NER, slot filling).

What an interviewer expects you to say

State that a CRF models $p (y ∣ x)$ over the whole sequence, with emission + transition scores and a global partition function $Z$ .
Explain why it beats independent softmax: it models label dependencies / transitions and avoids illegal sequences.
Know that training uses the forward algorithm (for $Z$ ) and decoding uses Viterbi, both $O (T ∣ V ∣^{2})$ .
Place it on the generative-vs-discriminative map (HMM is the generative cousin) and mention the label-bias problem CRFs fix relative to MEMMs.
Bonus: the BiLSTM-CRF / encoder-CRF pattern (neural encoder for emissions, CRF layer for structure).

Common confusions

“CRF = HMM.” HMM is generative and locally normalized; CRF is discriminative and globally normalized. CRFs can use arbitrary, overlapping input features.
“You need a CRF whenever you tag sequences.” Only when output structure matters. With a strong contextual encoder (large transformer), the marginal gain of a CRF head shrinks because the encoder already captures most dependencies, but it still helps enforce hard constraints.
“The partition function is intractable.” For a chain it’s an $O (T ∣ V ∣^{2})$ forward pass. It’s only intractable for general (loopy) graph structures.
“CRFs are obsolete.” The CRF layer is still a standard, cheap way to enforce coherent label sequences on top of any encoder.