Ngram

• Count up the frequency and divide (use maximum likelihood estimation or MLE):

  • $P_{ML}(x_i | x_{i-n+1} ,..., x_{i-1}) := \frac {c(x_{i-n+1,...,x_i})}{c(x_{i-n+1},...,x_{i-1})}$

  • Example: $$P(you | i\ love) := \frac {c(i\ love\ you)}{c(i\ love)}$$
  • More Generally: $$P(w_1^n) = P(w_1)P(w_2 | w_1)P(w_3|w_1^2)…P(w_n|w_1^{n-1}) = \prod_{i=1}^{n} P(w_i|w_1^{i-1})$$

• For N-gram

  • Next Word: $$P(w_n|w_1^{n-1}) \approx P(w_n|w_{n-N+1}^{n-1}) = \frac {C(w_{n-N+1}^{n-1}w_n)}{C(w_{n-N+1}^{n-1})}$$
  • prob of sentence: $$P(w_1^n) \approx \prod_{i=1}^{n} P(w_i|w_{i-1}…w_{i-N+1})$$

• For Bigram

  • prob of sentence: $$P(w_1^n) \approx \prod_{i=1}^{n} P(w_i|w_{i-1})$$
  • Next Word: $$P(w_n|w_{n-1}) = \frac {C(w_{n-1}w_n)}{\sum_w C(w_{n-1} w)} = \frac {C(w_{n-1}w_n)}{C(w_{n-1})}$$

More →