Natural-Language-Processing

• How to compute this joint probability of P(its, water, is, so, transparent, that)
• Intuition: use Chain Rule of Bayes

• just count and divide?
  • No. Too many sentences.
• Markov Assumption
  • Simplifying assumption: \[ P(the|\mbox{its water is so transparent that}) \approx P(the|that) \]
  • Or maybe \[ P(the|\mbox{its water is so transparent that}) \approx P(the|transparent\ taht) \]
  • Formally \[ P(w_i|w_1w_2\ldots w_{i-1}) \approx P(w_i)|w_{i-k}\ldots w_{i-1} \]

\[ P(w_1w_2\ldots w_n) \approx \prod\limits_i {P(w_i)} \]

• Condition on the previous word:

\[ P(w_i|w_1w_2\ldots w_{i-1}) \approx P(w_i|w_{i-1}) \]

• We can extend to trigrams, 4-grams, 5-grams
• In general this is an insufficient model of language
  • because language has long-distance dependencies:

  "The computer which I had just put into the machine room on the fifth floor crashed."

• But we can often get away with N-gram models

• MLE

\begin{equation*} P(w_i|w_{i-1}) = \frac{c(w_{i-1}w_i)}{w_{i-1}} \end{equation*}

• More examples: Berkeley Restaurant Project sentences

• We do everything in log space
  • Avoid underflow
  • (also adding is faster than multiplying)

SIRL Google N-gram Release, August 2006 Google Book N-grams

• Extrinsic evaluation
  • Time-consuming
• So
  • sometimes use intrinsic evaluation: perplexity
  • Bad approximation
    • unless the test data looks just like the training data
    • So generally only useful in pilot experiments
  • But is helpful to think about

• The Shannon Game:
  • How well can we predict the next word?
• The best LM is one that best predicts an unseen test set
  • Gives the highest P(sentence)
• Perplexity is the probability of the test set, normalized by the number of words:

\[ PP(W) = P(w_1w_2\ldots w_N)^{-\frac{1}{N}} \]

• Let's suppose a sentence consisting of random digits
• What is the perplexity of this sentence according to a model that assign P=1/10 to each digit?

\[ PP(W) = P(w_1w_2\ldots w_n)^{-\frac{1}{N}} = \frac{1}{10} \] The lower the better.

• Choose a random bigram (<s>, w) according to its probability
• Now choose a random bigram (w, x) according to its probability
• And so on until we choose </s>
• Then string the words together

• N-grams only work well for word prediction if the test corpus looks like the training corpus
  • In real life, it often doesn't
  • We need to train robust models that generalize!
  • One kind of generalization: Zeros!
    • Things that don't ever occur in the training set
      • But occur in the test set

• Bigrams with zero probability
  • mean that we will assign 0 probability to the test set!
• And hence we cannot compute perplexity (can't divide zero)

\[ c^*(w_{n-1}w_n) = \frac{[C(w_{n-1}w_n)+1]\times C(w_{n-1})}{C(w_{n-1})+V} \]

• So add-1 isn't used for N-grams:
  • we'll see better methods
• But add-1 is used to smooth other NLP models
  • For text classification
  • In domains where the number of zeros isn't so huge

\[ P() = \lambda_1 P()\]

• Lambdas conditional on context:

• Intuition used by many smoothing algorithms
  • Good
• Notation: N_c = Frequency of frequency c
  • N_c = the count of things we've seen c times

\[ P^*_{GT}(things with zero frequency)=\frac{N_1}{N} \]

• Unseen (bass or catfish)
  • c = 0
  • MLE p = 0/18 = 0
  • P^*_GT(unseen) = N₁/N = 3/18

• Better estimate for probabilities of lower-order unigrams!
  • Shannon game: I can't see without my reading Francisco?
  • "
• The unigram is useful exactly when we haven't seen this bigram!
• Instead of P(w): "How likely is w"
• P_continuation(w):" How likely is w to appear as a novel continuation?
  • For each word, count the number of bigram types it completes
  • Every bigram type was a novel continuation the first time it was seen

  \[ P_{} \propto |{w_{i-1}:c(w_{i-1},w)>0}| \]

-How many times

• Alternative metaphor: The number of # of word types seen to precede w

\[ P_{KN}(w_i|w_{i-1} = \frac{}{} + \lambda(w_{i-1}P_{Continuation}(w_i)))\]

\[\]

\begin{equation} c_{KN}(\dot) \end{equation}

Continuation count = Number of unique single word contexts for \dot