Linear-Chain CRF

A linear-chain CRF is a discriminative probabilistic model for sequence labeling that models the conditional probability $P(y \mid x)$ directly rather than the joint $P(x, y)$. Given observations $x$, the probability of a label sequence $y$ is

where $f_k$ are feature functions (transition features $f_k(y_{t-1},y_t,x,t)$ and state features $f_l(y_t,x,t)$ under one index) that may combine arbitrary overlapping observation features; the partition function $Z(x) = \sum_y \exp(\cdot)$ sums over all label sequences to normalize the distribution. Parameters $\lambda$ are learned by maximizing the conditional log-likelihood with L2 regularization — a convex objective — and decoding the best sequence uses Viterbi.

POS tagging, named-entity recognition, segmentation, and shallow parsing; interviews frequently contrast CRFs with HMMs and probe the label-bias problem.

HMMs are generative — they must model the observation distribution with conditionally independent outputs and cannot use overlapping features; more seriously, the locally normalized transitions of HMM/MEMM cause label bias: probability mass is normalized at each state, gets “sucked” toward states with fewer outgoing transitions, and favors low-branching paths. CRFs eliminate label bias through global normalization by $Z(x)$, allow rich overlapping features over the observation context, and their convex conditional objective guarantees a global optimum; the cost is iterative training (e.g. L-BFGS / gradient ascent), computing $Z(x)$ during inference, and slower training than HMMs.

Test Your Knowledge: Practice Questions for "Linear-Chain CRF"

Single choice pitfall questions with instant feedback and mistake tracking.