Sequence Labeling for Parts of Speech and Named Entities

18.5 Conditional random fields

1. Why are HMMs awkward for adding features like capitalization or suffixes?
   As generative models, all knowledge must be encoded in \(P(\text{tag} \mid \text{tag})\) and \(P(\text{word} \mid \text{tag})\); adding arbitrary features cleanly is hard. Log-linear models handle arbitrary features, but logistic regression isn’t a sequence model.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 18, §18.5, p. 414
2. What is a conditional random field (CRF)?
   A discriminative sequence model: a log-linear model assigning a probability to an entire tag sequence given the entire input, \(p(Y \mid X) = \frac{\exp\sum_k w_kF_k(X, Y)}{Z(X)}\), like a giant sequential multinomial logistic regression.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 18, §18.5, p. 414
3. How does an HMM’s computation of the best tag sequence differ from a CRF’s?
   The HMM uses Bayes’ rule and the likelihood, \(\arg\max_Y p(X \mid Y)p(Y)\); the CRF computes the posterior \(p(Y \mid X)\) directly, aggregating local log-linear feature scores and normalizing globally.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 18, §18.5, pp. 414–415
4. What are global and local features in a CRF?
   Global features \(F_k(X, Y)\) are properties of the whole input and output sequences, computed as sums of local features at each position: \(F_k(X, Y) = \sum_i f_k(y_{i-1}, y_i, X, i)\).
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 18, §18.5, p. 415
5. What defines a linear-chain CRF, and why does it matter?
   Each local feature may use only the current tag \(y_i\), the previous tag \(y_{i-1}\), the whole input \(X\) and the position \(i\). This permits efficient Viterbi and forward-backward algorithms; general CRFs allow distant output dependencies but need harder inference.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 18, §18.5, p. 415
6. Give examples of linear-chain CRF features for POS tagging.
   \(\mathbb{1}\{x_i = \text{the}, y_i = \text{DET}\}\), \(\mathbb{1}\{y_i = \text{PROPN}, x_{i+1} = \text{Street}, y_{i-1} = \text{NUM}\}\), \(\mathbb{1}\{y_i = \text{VERB}, y_{i-1} = \text{AUX}\}\); generated automatically from templates like \(\langle y_i, x_i\rangle\), \(\langle y_i, y_{i-1}\rangle\), \(\langle y_i, x_{i-1}, x_{i+2}\rangle\).
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 18, §18.5, p. 416
7. What are word shape features?
   Abstract letter patterns for unknown words: lowercase → x, uppercase → X, digits → d, punctuation kept (I.M.F. → X.X.X., DC10-30 → XXdd-dd). Short word shape collapses repeated character types (DC10-30 → Xd-d, Well → Xx).

   word	shape	short shape
   well-dressed	xxxx-xxxxxxx	x-x
   DC10-30	XXdd-dd	Xd-d
   L’Occitane	X’Xxxxxxxx	X’Xx

   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 18, §18.5, p. 416
8. Besides word shape, what features help a CRF with unknown words?
   Prefixes and suffixes (e.g. all of length ≤ 2 for POS, ≤ 4 for NER).
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 18, §18.5, p. 416
9. How are CRF feature weights tied to sentences of different lengths?
   Each local feature is summed over the sentence into a global feature, and weights attach to the fixed set of \(K\) global features, so the parameter set is the same for any sentence length. Rare features (count < 5) are usually cut off.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 18, §18.5, p. 417
10. What features does a feature-based NER system use?
    Word identity and neighbors, embeddings, POS of the word and neighbors, gazetteer membership, prefixes and suffixes, word shape and short word shape of the word and neighbors.
    • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 18, §18.5, p. 417
11. What is a gazetteer?
    A list of place names (often millions of entries with geographic and political information), used as a binary feature; similar lists exist for person names, companies and products.
    • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 18, §18.5, p. 417
12. How is the best tag sequence found with a CRF?
    \(\hat{Y} = \arg\max_Y\sum_i\sum_k w_kf_k(y_{i-1}, y_i, X, i)\) (exp and \(Z(X)\) don’t affect the argmax), using Viterbi because each step depends only on the previous tag.
    • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 18, §18.5, p. 418
13. How does the CRF Viterbi recursion differ from the HMM’s?
    The transition and emission probabilities are replaced by the sum of weighted features (in log space): \(v_t(j) = \max_i\, v_{t-1}(i) + \sum_k w_kf_k(y_{t-1}, y_t, X, t)\).
    • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 18, §18.5, p. 419
14. How are CRFs trained?
    Like logistic regression: stochastic gradient descent maximizing the log-likelihood of the training corpus, with a CRF version of the forward-backward algorithm computing the derivatives, plus L1 or L2 regularization.
    • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 18, §18.5, p. 419