> For the complete documentation index, see [llms.txt](https://deemolover.gitbook.io/log-os/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://deemolover.gitbook.io/log-os/theory/language-processing/chapter-3-n-gram-language-models/3.1-n-grams.md).

# 3.1 N-Grams

**DEF** Our task is calculating $$P(w|h)$$ , where $$w$$ is a word and $$h$$ is a text history. For example $$P(\mathrm{apple}|\mathrm{I\ have\ an})$$ . To formalize the problem, treat every word in a sequence as a random variable $$X\_i$$ . The probability of $$X\_i$$ taking on a value $$w\_i$$ is written as $$P(X\_i=w\_i)$$ . $$w\_1^n$$ represents a sequence of N words $$w\_1\dots w\_n$$ . $$P(w\_1,\dots,w\_n)$$ represents the joint probability $$P(X\_1=w\_1,\dots,X\_n=w\_n)$$ .

* So we have $$P(w\_1^n) = \prod \_{k=1}^nP(w\_k|w\_1^{k-1})$$
* 这一条件概率难以统计获得，因为自然语言的特质就是要不断产生新文本，相同的文字序列几乎不可能重复出现。

**LM** **bigram** model makes the following approximation (**Markov** assumption): $$P(w\_n|w\_1^{n-1}) \approx P(w\_n|w\_{n-1})$$

* As a generalization, in **n-gram:** $$P(w\_n|w\_1^{n-1}) \approx P(w\_n|w\_{n-N+1}^{n-1})$$

  and in **trigram** model N takes on the value of 3.

  * To estimate the probability, we use **maximum likelihood estimation / MLE**. We count its frequency and **normalize** it to a value between 0 and 1: $$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)}$$
  * For the general case of MLE n-gram parameter estimation: $$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})}$$
* How do we understand MLE?
* If a word occurs k times in a corpus of size n, then MLE p=k/n is the probability that makes it **most likely** that the word will occur k times in a corpus of size n. (may be under assumption that all words in a corpus take on values independently?)