1. N-gram 模型

1.1 N-gram 模型介绍

\(\text{N-gram}\) 是一种基于统计语言模型的算法，用于预测文本中的单词，其中 \(\text{N}\) 一般指的是序列中的单词数量。其基本思想是将文本内容进行大小为 \(\text{N}\) 的滑动窗口操作来计算概率。

例如：

当 \(\text{N}=1\) 时，模型被称为"unigram"，即单词被当作独立的个体来考虑。
当 \(\text{N}=2\) 时，模型被称为"bigram"，此时考虑的是两个连续单词的序列。
当 \(\text{N}=3\) 时，称为"trigram"，考虑的就是连续三个单词的序列。

1.2 链式法则

假设有一个由 \(m\) 个单词组成的序列（句子），其概率定义为：

\[P(w_1, w_2, \dots , w_m) \]

其中 \(w_i\) 表示序列中的单词，\(i = 1, 2, \dots , m\)。

我们都知道条件概率公式：

\[P(B | A) = \frac{P(A, B)}{P(A)} \]

可以将条件概率改写为：

\[P(A, B) = P(A)P(B|A) \]

由此可以推广到 \(m\) 个变量的情况，也就是此时\(m\) 个单词组成的序列的情况：

\[P(w_1, w_2, \dots , w_m) = P(w_1)P(w_2|w_1)P(w_3|w_1,w_2)\dots P(w_m|w_1, \dots, w_{m-1}) \]

这就是 链式法则。一个由 \(m\) 个单词组成的句子概率表示可以化简为如下形式：

\[P(w_1, w_2, \dots , w_m) = \prod_{i=1}^{m}P(w_i | w_1, w_2, \dots, w_{i-1}) \]

1.3 马尔科夫假设

前面由链式法则得到的句子概率表示，显然是难以计算的。所以，我们有必要引入 马尔可夫假设 (\(\text{Markov Assumption}\)).

对于一个句子的概率 \(P(w_1, w_2, \dots , w_m)\) ，一般的链式法则需要考虑到最开始的单词，而马尔科夫假设 只考虑前面的 \(k\) 个有限数量的单词。我们可以令 \(k = n - 1\)，因此有如下形式化表示：

\[P(w_i | w_1, w_2, \dots, w_{i-1}) \approx P(w_i|w_{i-n+1}, \dots, w_{i-1}) \]

由此，我们可以得到一元模型，二元模型，三元模型的定义：

当 \(\text{N}=1\) 时，即一元模型（unigram model）：

\[P(w_1, w_2, \dots, w_m) = \prod_{i=1}^m P(w_i) \]
当 \(\text{N}=2\) 时，即二元模型（bigram model）：

\[P(w_1, w_2, \dots, w_m) = \prod_{i=1}^m P(w_i|w_{i-1}) \]
当 \(\text{N}=3\) 时，即三元模型（trigram model）：

\[P(w_1, w_2, \dots, w_m) = \prod_{i=1}^m P(w_i|w_{i-2}, w_{i-1}) \]

以此类推，可以扩展到四元模型，五元模型。

2. N-gram 概率计算

2.1 极大似然估计

极大似然估计（\(\text{Maximum Likelihood Estimation，MLE}\)）是统计学中用于从样本数据估计模型参数的一种方法。也称为最大似然估计。

对于 \(\text{N-gram}\) 概率计算问题，我们通过从语料库中获取计数并将计数归一化以使它们位于 0 和 1 之间来获得 \(\text{N-gram}\) 模型参数的 \(\text{MLE}\) 估计。

我们以一元语法模型为例，一个二元组的概率可表示为：

\[P(w_i | w_{i - 1}) = \frac{C(w_{i-1}, w_i)}{C(w_{i-1})} \]

其中 \(C\) 表示统计的个数。

推广到 \(\text{N-gram}\) 的情况：

\[P(w_i|w_{i-n+1}, \dots, w_{i-1}) = \frac{C(w_{i-n+1}, \dots , w_i)}{C(w_{i-n+1}, \dots , w_{i-1}} \]

2.2 典型示例

用二元语法进行概率计算，采用 \(\text{MLE}\) 估计。在计算之间，我们首先需要在每个句子的开头添加一个特殊的符号 \(\text{<s>}\)，为我们提供第一个单词的二元上下文。我们还需要一个特殊的结束符号 \(\text{</s>}\)

注意：

在计算概率时，采用传统的乘法，也许会导致 下溢出(underflow)，此时就需要转换为对数形式进行计算：

\[\text{log}(p_1 \times p_2 \times p_3) = \text{log}p_1 + \text{log}p_2 + \text{log}p_3 \]

即：

\[p_1 \times p_2 \times p_3 = \text{exp}(\text{log}p_1 + \text{log}p_2 + \text{log}p_3) \]

概率（根据定义）小于或等于 1，所以我们相乘的概率越多，乘积就越小。将足够多的 n-gram 相乘会导致数值下溢。通过使用对数概率而不是原始概率，得到的数字并不那么小。

3. 困惑度

困惑度（Perplexity） 是衡量语言模型性能的一种指标，其衡量的是模型预测一个样本序列的能力有多好。适用于评估诸如 \(\text{N-gram}\) 模型、循环神经网络（RNN）以及其他更现代的模型如Transformer和BERT等。

一个好的语言模型是可以最优地预测未遇到过的测试集，使得句子的概率最大化。困惑度是测试集的逆向概率，并由单词总数 N 进行归一化处理。

困惑度有如下公式：

\[\begin{split} \text{PP}(W) &= P(w_1, w_2, \dots, w_N)^{ - \frac{1}{N}} \\ &= \sqrt[N]{\frac{1}{P(w_1, w_2, \dots, w_N)}} \end{split} \]

显然 困惑度越小即则概率越大。

若计算的是一元困惑度，则表示为：

\[\text{PP}(W) = \sqrt[N]{\prod_{i=1}^N \frac{1}{P(w_i)}} \]

若计算的是二元困惑度，则表示为：

\[\text{PP}(W) = \sqrt[N]{\prod_{i=1}^N \frac{1}{P(w_i | w_{i-1})}} \]

在理想情况下，如果模型对每个单词的预测都是完美的，则困惑度为 1。通常情况下，困惑度会大于 1，困惑度值越小表示模型预测能力越好。

4. 平滑方法

在NLP中，数据平滑技术通常用来解决极大似然估计遇到的零概率问题。

4.1 加一平滑

加一平滑（Additive smoothing），也称为拉普拉斯平滑（Laplace smoothing），核心思想是给每个统计单元出现的次数加一，此时便不会有零概率值。

最大似然估计如下：

\[P_{\text{MLE}}(w_i | w_{i-1}) = \frac{C(w_i, w_{i-1})}{w_{i-1}} \]

经过加一平滑后，变为：

\[P_{\text{Add-1}}(w_i | w_{i-1}) = \frac{C(w_i, w_{i-1}) + 1}{C(w_{i-1}) + |V|} \]

其中 \(|V|\) 为词汇表大小，也就是模型考虑的不同的词的数量。

不过，拉普拉斯平滑方法比较粗糙，尤其是在词汇量很大或者数据集很大的时候，每次都增加一个单位可能会导致概率估计偏向于不太准确。

4.2 线性插值平滑

线性插值平滑（Interpolation smoothing）基本思想就是利用低元N-grams模型对高元N-grams模型进行线性插值。

\[P_{\text{Int}}(w_i | w_{i-1}, w_{i-2}) = \lambda_3 P_{\text{MLE}}(w_i | w_{i-1}, w_{i-2}) + \lambda_2 P_{\text{MLE}}(w_i | w_{i-1}) + \lambda_1 P_{\text{MLE}}(w_i) \]

\[\lambda_3 + \lambda_2 + \lambda_1 = 1, \quad 0 \le \lambda_i \le 1 \]

4.3 回退平滑

回退算法（Katz smoothing）又称为 Back-off 回退。当有足够计数时，使用N元语法；否则使用N-1，N-2，… ，bigrams, unigrams。

\[P_{\text{Katz}} = \begin{cases} d_{w_{i-n+1}\cdots w_i}\frac{C(w_{i-n+1}\dots w_i)}{C(w_{i-n+1}\dots w_{i-1})}, & \text{if}\; C(w_{i-n+1}\dots w_i) > k \\ \alpha_{w_{i-n+1}\cdots w_i}P_{\text{Katz}}(w_i | w_{i-n+2}\dots w_{i-1}) & \text{else} \end{cases} \]

其中 \(\alpha\) 和 \(d\) 为归一化参数，保证 \(\sum P_{\text{Katz}} = 1\)。\(k\) 一般选择为0，也可以选其它的值。