learn.ifs.name

N-gram Language Models

Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 3

15 cards in “3.6 Smoothing, interpolation, and backoff” · whole deck

3.6 Smoothing, interpolation, and backoff

  1. What are “zeros” in n-gram modeling, and why are they a problem?
    n-grams that never occur in training but appear in the test set (“ruby slippers”). They make us underestimate plausible sequences, and if any word has probability 0 the whole test set has probability 0, so perplexity can’t be computed (division by zero).
  2. What is smoothing (discounting)?
    Shaving some probability mass off frequent events and giving it to unseen events, so no plausible n-gram gets zero probability.
  3. What is Laplace (add-one) smoothing for unigrams?
    Add one to every count and adjust the denominator by the vocabulary size \(V\): \(P_{\text{Laplace}}(w_i) = \frac{c_i + 1}{N + V}\).
  4. Give the Laplace-smoothed bigram probability, and explain the denominator.
    \(P(w_n \mid w_{n-1}) = \frac{C(w_{n-1} w_n) + 1}{C(w_{n-1}) + V}\). The denominator is really a sum over all \(V\) bigrams starting with \(w_{n-1}\), each of which got +1.
  5. Where is Laplace smoothing still useful, given that it is too weak for modern n-gram LMs?
    As a baseline that introduces smoothing concepts, and as a practical smoothing method for other tasks like text classification.
  6. What is an adjusted (reconstituted) count \(C^*\)?
    The count that, divided by the original unsmoothed denominator \(C(w_{n-1})\), gives the smoothed probability: \(C^* = \frac{[C(w_{n-1} w_n) + 1]\, C(w_{n-1})}{C(w_{n-1}) + V}\). It shows how much smoothing changed the counts.
  7. What is wrong with add-one smoothing for language modeling?
    It moves far too much probability mass to all the zeros, drastically discounting seen n-grams (e.g. the count of “want to” drops from 608 to 238, and some discounts are 10× larger than others).
  8. What is add-\(k\) smoothing, and how is \(k\) chosen?
    Add a fractional count \(k\) (e.g. 0.5, 0.01) instead of 1: \(P = \frac{C(w_{n-1} w_n) + k}{C(w_{n-1}) + kV}\). \(k\) is tuned on a devset. It still works poorly for language modeling (poor variances, inappropriate discounts).
  9. What is the intuition behind using lower-order n-grams for unseen higher-order ones?
    Less context generalizes better: with no examples of a trigram, use the bigram probability; with no bigram counts, use the unigram.
  10. What is simple linear interpolation?
    Mixing n-gram orders with weights that sum to 1: \(\hat{P}(w_n \mid w_{n-2} w_{n-1}) = \lambda_1 P(w_n) + \lambda_2 P(w_n \mid w_{n-1}) + \lambda_3 P(w_n \mid w_{n-2} w_{n-1})\).
  11. What is interpolation with context-conditioned weights?
    Each \(\lambda\) depends on the preceding context \(w_{n-2:n-1}\), so trigrams built on well-attested bigrams can get more weight.
  12. How are the interpolation weights \(\lambda\) set?
    On a held-out corpus: fix the n-gram probabilities and choose the \(\lambda\)s that maximize the held-out likelihood, e.g. with the EM algorithm.
  13. What is a held-out corpus?
    Additional data held out from training, used to set hyperparameters such as interpolation weights rather than regular counts.
  14. How does backoff differ from interpolation?
    Backoff uses only the highest-order n-gram with nonzero counts, backing off to the (n−1)-gram only when the count is zero. Interpolation always mixes all orders. A correct backoff model must discount higher-order n-grams to reserve mass for lower orders.
  15. What is stupid backoff?
    A simple non-discounted backoff (Brants et al., 2007): if the n-gram count is positive use its relative frequency, otherwise use \(\lambda\) (about 0.4) times the backed-off score, ending in \(\text{count}(w)/N\). It doesn’t produce a true probability distribution, so it is written \(S\) rather than \(P\).

Source