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.

Write the linear-chain CRF potential $P(y \mid x) = \frac{1}{Z(x)}\exp(\sum_t \sum_k \lambda_k f_k(y_{t-1},y_t,x,t))$ and the role of $Z(x)$?

How do CRFs and HMMs differ (discriminative vs generative, overlapping features, normalization)?

What is the label-bias problem? Why do MEMM/HMM suffer from it and how does CRF fix it?

What is the CRF training objective, why is it convex, and which algorithm performs inference?

How is the CRF partition function $Z(x)$ computed, and how does its complexity relate to the HMM forward algorithm?