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

3 Conditional random fields

1. Define a conditional random field.
   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.
   • Lafferty et al., 2001, Conditional Random Fields (Proceedings of the 18th International Conference on Machine Learning (ICML)), §3
2. What form does a linear-chain CRF take?
   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})\).
   • Lafferty et al., 2001, Conditional Random Fields (Proceedings of the 18th International Conference on Machine Learning (ICML)), §3
3. Give an example of a CRF vertex feature.
   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}\).
   • Lafferty et al., 2001, Conditional Random Fields (Proceedings of the 18th International Conference on Machine Learning (ICML)), §3
4. How is an HMM-like CRF constructed, and how does it differ from an HMM?
   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.
   • Lafferty et al., 2001, Conditional Random Fields (Proceedings of the 18th International Conference on Machine Learning (ICML)), §3
5. Compare the graphical structures of HMMs, MEMMs and linear-chain CRFs.

   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.
   • Lafferty et al., 2001, Conditional Random Fields (Proceedings of the 18th International Conference on Machine Learning (ICML)), §3
6. How is a chain CRF written in matrix form, and how is its partition function computed?
   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}\).
   • Lafferty et al., 2001, Conditional Random Fields (Proceedings of the 18th International Conference on Machine Learning (ICML)), §3
7. Why is CRF training attractive in terms of optimization?
   The log-likelihood objective is convex (CRFs share the convexity of general maximum entropy models), so training converges to the global optimum.
   • Lafferty et al., 2001, Conditional Random Fields (Proceedings of the 18th International Conference on Machine Learning (ICML)), §3