learn.ifs.name

N-gram Language Models

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

22 cards in “3.1 N-grams” · whole deck

3.1 N-grams

  1. Why can’t we estimate \(P(w \mid h)\) for a long history \(h\) by directly counting \(C(h\,w)/C(h)\)?
    Language is creative: most long histories (whole sentences) never occur, or occur too rarely, even on the entire web, so the counts are zero or unreliable.
  2. What does the notation \(w_{1:n-1}\) (or \(w_{<n}\)) mean?
    The sequence \(w_1, w_2, \ldots, w_{n-1}\): all words before \(w_n\).
  3. State the chain rule of probability for a word sequence.
    \(P(w_{1:n}) = P(w_1)P(w_2 \mid w_1)P(w_3 \mid w_{1:2})\cdots P(w_n \mid w_{1:n-1}) = \prod_{k=1}^{n} P(w_k \mid w_{1:k-1})\)
  4. Why doesn’t the chain rule by itself solve language modeling?
    It turns the joint probability into a product of conditional probabilities, but we still have no way to estimate \(P(w_n \mid w_{1:n-1})\) for long histories.
  5. What approximation does a bigram model make?
    \(P(w_n \mid w_{1:n-1}) \approx P(w_n \mid w_{n-1})\): e.g. P(blue | The water of Walden Pond is so beautifully) ≈ P(blue | beautifully).
  6. What is the Markov assumption?
    That the probability of a future unit depends only on a limited recent past (for a bigram, only the previous word), not on the whole history.
  7. What is the general n-gram approximation of the next-word probability?
    \(P(w_n \mid w_{1:n-1}) \approx P(w_n \mid w_{n-N+1:n-1})\): condition only on the previous \(N-1\) words.
    The water of Walden Pond isso beautifully?trigram: last N−1 = 2 wordsignored
  8. How does a bigram model compute the probability of a whole sentence?
    \(P(w_{1:n}) \approx \prod_{k=1}^{n} P(w_k \mid w_{k-1})\)
  9. What is maximum likelihood estimation (MLE) for n-gram probabilities?
    Get counts from a corpus and normalize them to lie between 0 and 1 (dividing by a total count so they sum to 1). The resulting parameters maximize the likelihood of the training set.
  10. What is the MLE bigram estimate, and why can its denominator be a unigram count?
    \(P(w_n \mid w_{n-1}) = \frac{C(w_{n-1} w_n)}{C(w_{n-1})}\). The sum of counts of all bigrams starting with \(w_{n-1}\) equals the count of \(w_{n-1}\) itself.
  11. Why do we add <s> and </s> to each sentence when training a bigram model?
    <s> gives the first word a context. </s> makes the model a true probability distribution over sentences of all lengths; without it, probabilities would sum to one separately for each sentence length.
  12. From the corpus <s> I am Sam </s>, <s> Sam I am </s>, <s> I do not like green eggs and ham </s>, compute P(I | <s>), P(am | I) and P(Sam | am).
    P(I | <s>) = 2/3 ≈ .67 (two of three sentences start with I); P(am | I) = 2/3 ≈ .67 (I occurs 3 times, twice followed by am); P(Sam | am) = 1/2 (am occurs twice, once followed by Sam).
  13. Give the general MLE n-gram estimate.
    \(P(w_n \mid w_{n-N+1:n-1}) = \frac{C(w_{n-N+1:n-1}\, w_n)}{C(w_{n-N+1:n-1})}\)
  14. What is a relative frequency?
    The observed frequency of a sequence divided by the observed frequency of its prefix: the MLE estimate.
  15. If Chinese occurs 400 times in a million-word corpus, what is its MLE probability, and in what sense is it “best”?
    400/1,000,000 = .0004. It isn’t the best estimate for every context, but it is the probability that makes 400 occurrences in a million words most likely.
  16. What do you notice about a bigram count matrix built from even a well-chosen set of words?
    Most cells are zero: n-gram counts are very sparse.
  17. How do you compute P(<s> i want english food </s>) with a bigram model?
    Multiply the bigram probabilities: P(i | <s>) · P(want | i) · P(english | want) · P(food | english) · P(</s> | food).
  18. What kinds of facts do bigram statistics capture?
    Syntactic facts (after eat comes a noun or adjective; after to, a verb), task facts (assistant queries often start with I), and even cultural facts (people ask for Chinese food more than English food).
  19. Why are LM probabilities stored and computed as log probabilities?
    Multiplying many probabilities ≤ 1 causes numerical underflow. Adding logs is equivalent to multiplying: \(p_1 p_2 p_3 = \exp(\log p_1 + \log p_2 + \log p_3)\).
  20. How do trigram models handle the beginning of a sentence?
    With extra pseudo-words: the first trigram uses two start symbols, e.g. P(I | <s> <s>).
  21. What is the infini-gram (∞-gram) project?
    n-grams of any length, computed quickly at inference time from enormous corpora using suffix arrays, instead of precomputing huge count tables.
  22. What techniques make large n-gram models efficient?
    Quantizing probabilities to 4–8 bits, storing words as 64-bit hashes, special data structures like reverse tries, pruning (count thresholds or entropy-based pruning), and toolkits like KenLM that use sorted arrays and merge sorts.

Source