n元语法(n gram model)
句子出现的概率
n gram简单来说是用来统计一句话在整个语言中出现的概率：假如我们有一句话“我想吃苹果”，那么先分词：“我/想/吃/苹果”，那么
$$\begin{split} P(我想吃苹果) = P(我,想,吃,苹果) = P(我)P(想|我)P(吃|我,想)P(苹果|我,想,吃) \end{split}$$
推而广之，对于句子 $s=w_1,w_2,...,w_t$
$$\begin{split} P(s)=P(w_1,w_2,...,w_t)=P(w_1)P(w_2|w_1)P(w_3|w_1,w_2)...P(w_t|w_1,w_2,...,w_{t−1}) \end{split}$$
n gram model
假如严格按照上述公式计算句子出现的概率，假设总词汇大小为 N，那么第 t 个词的概率 要考虑 $$ N_{t−1} $$种情况，当 N 较大时，句子长度也较长时，计算量将是一个天文数字。我们需要找到一种办法降低计算量。 而且上述模型参数空间过大，而且数据非常稀疏。
根据马尔科夫假设：当前隐含状态只取决于前一个隐含状态
- 当 n=1 时，称为一元语法，被记为unigram，此时第 i 个词出现的概率与之前的情况完全独立。
- 当 n=2 时，称为二元语法，被称为一阶马尔科夫链，记为bigram，此时第 i 个词出现的概率与它的前一个词有关。
- 当 n=3 时，称为三元语法，被称为二阶马尔科夫链，记作trigram，此时第 i 个词出现的概率与它的前两个词有关。
对于二元语法：
$$\begin{split} P(s)=P(w_1,w_2,...,w_t)≈P(w_1)P(w_2|w_1)P(w3|w_2)...P(w_t|w_{t−1}) \end{split}$$
另外：为了使当 t=1 时上述公式仍然有意义，可以在句子面前加上一个句子起始标记<BOS>，而结尾也可以添加句子结束标记<EOS>。
条件概率的计算
求 $$\begin{split} P(w_t|w_{t−1}) \end{split}$$ 时，可直接计算 $$ w_{t−1}$$, $$ w_t $$ 在语料出现的频率并归一化。
$$ P(w_t|w_{t-1}) = \frac{count(w_{t-1}w_t)}{\sum_{w_t}count(w_{t-1}w_t)} $$
对于语料 S：{ “我想吃苹果”, "他想吃橘子", "我想吃蓝莓" }
对于句子“他想吃苹果”在语料 S 中出现的概率为：
$$\begin{split}
P(他想吃苹果) = P(他,想,吃,苹果) ≈ P(他|
由语料可知：
$$\begin{multline}
P(他|
$$\begin{multline} P(想|他) = \frac{1}{1} \end{multline}$$
$$\begin{multline} P(吃|想) = \frac{1}{1} \end{multline}$$
$$\begin{multline} P(苹果|吃) = \frac{1}{3} \end{multline}$$
$$\begin{multline}
P(
所以：
$$\begin{matrix}
P(他|
平滑处理
零概率问题
假如有词 A 和 B，而在语料中词 A B 从未连续存在过，那么 $$\begin{matrix} P(A|B) = 0 \end{matrix}$$ ，而如果 A 和 B 确实有同时出现的情况，那么P(A|B)概率为0显然不够准确。
平滑(smoothing)技术
最简单的办法是引入先验概率（加法平滑算法），即假设每种组合至少存在一次：
$$ P(w_t|w_{t-1}) = \frac{1 + count(w_{t-1}w_t)}{|V| + \sum_{w_t}count(w_{t-1}w_t)} $$
这里用 $$\begin{matrix} |V| \end{matrix}$$ 来表示词汇表中单词的个数。
其它平滑算法
- Good-Turing估计法
- Katz平滑法
- Jelinek-Mercer平滑法
- 绝对值减法
- Kneser-Ney平滑法
- 贝叶斯平滑法
Original link：https://izhangzhihao.github.io//2018/01/27/n-gram-model/