引言
在自然语言处理（NLP）领域，语言模型是预测词序列概率的核心工具。其中，n-gram模型因其简单性和有效性而被广泛应用。n-gram模型通过分析词序列中前n-1个词来预测下一个词的出现概率。然而，由于训练语料的有限性，许多n-gram在训练集中未曾出现，导致数据稀疏问题。这使得直接使用最大似然估计（MLE）计算的概率不可靠，因为未出现的n-gram会被赋予零概率。为了解决这一问题，平滑技术被引入，旨在调整n-gram的概率估计，使未见的n-gram也能获得一定的概率值。
Kneser-Ney平滑是一种先进的平滑方法，以其在处理大数据集时的优异表现而闻名。它通过利用低阶n-gram的信息来平滑高阶n-gram的概率估计，从而更准确地反映语言的统计特性。本文将详细介绍Kneser-Ney平滑的原理、数学推导、实现方法，并通过一个简单示例展示其应用，最后讨论其优缺点及与其他平滑技术的比较。
n-gram语言模型与数据稀疏问题
n-gram语言模型
n-gram语言模型基于马尔可夫假设，即一个词的出现仅依赖于它前面的n-1个词。形式上，给定词序列
(
w
1
,
w
2
,
…
,
w
m
)
( w_1, w_2, \ldots, w_m)
(w1,w2,…,wm)，其联合概率可以表示为：
P
(
w
1
,
w
2
,
…
,
w
m
)
=
∏
i
=
1
m
P
(
w
i
∣
w
i
−
n
+
1
,
…
,
w
i
−
1
)
P(w_1, w_2, \ldots, w_m) = \prod_{i=1}^m P(w_i | w_{i-n+1}, \ldots, w_{i-1})
P(w1,w2,…,wm)=i=1∏mP(wi∣wi−n+1,…,wi−1)
其中，条件概率
P
(
w
i
∣
w
i
−
n
+
1
,
…
,
w
i
−
1
)
P(w_i | w_{i-n+1}, \ldots, w_{i-1})
P(wi∣wi−n+1,…,wi−1)通常通过最大似然估计（MLE）计算：
P
(
w
i
∣
w
i
−
n
+
1
,
…
,
w
i
−
1
)
=
C
(
w
i
−
n
+
1
,
…
,
w
i
)
C
(
w
i
−
n
+
1
,
…
,
w
i
−
1
)
P(w_i | w_{i-n+1}, \ldots, w_{i-1}) = \frac{C(w_{i-n+1}, \ldots, w_i)}{C(w_{i-n+1}, \ldots, w_{i-1})}
P(wi∣wi−n+1,…,wi−1)=C(wi−n+1,…,wi−1)C(wi−n+1,…,wi)
这里，
C
(
⋅
)
C(\cdot)
C(⋅) 表示n-gram在训练语料中的出现次数。
数据稀疏问题
由于训练语料的有限性，许多潜在的n-gram在训练集中未出现，即
C
(
w
i
−
n
+
1
,
…
,
w
i
)
=
0
C(w_{i-n+1}, \ldots, w_i) = 0
C(wi−n+1,…,wi)=0。这导致MLE将这些n-gram的概率估计为零，使得模型在预测未见过的词序列时失效。平滑技术的目标是通过重新分配概率质量，确保未出现的n-gram也能获得非零的概率估计。
Kneser-Ney平滑原理
Kneser-Ney平滑是一种基于折扣和回退的平滑方法，通过从高阶n-gram的计数中减去一个固定的折扣值，并将减去的概率质量分配给低阶n-gram。其核心思想是利用低阶n-gram的分布特性来改进高阶n-gram的概率估计。
高阶n-gram的概率估计
对于一个n-gram
w
i
−
n
+
1
,
…
,
w
i
w_{i-n+1}, \ldots, w_i
wi−n+1,…,wi，Kneser-Ney平滑的概率估计公式为：
P
KN
(
w
i
∣
w
i
−
n
+
1
,
…
,
w
i
−
1
)
=
max
(
C
(
w
i
−
n
+
1
,
…
,
w
i
)
−
d
,
0
)
C
(
w
i
−
n
+
1
,
…
,
w
i
−
1
)
+
λ
(
w
i
−
n
+
1
,
…
,
w
i
−
1
)
P
KN
(
w
i
∣
w
i
−
n
+
2
,
…
,
w
i
−
1
)
P_{\text{KN}}(w_i | w_{i-n+1}, \ldots, w_{i-1}) = \frac{\max(C(w_{i-n+1}, \ldots, w_i) – d, 0)}{C(w_{i-n+1}, \ldots, w_{i-1})} + \lambda(w_{i-n+1}, \ldots, w_{i-1}) P_{\text{KN}}(w_i | w_{i-n+2}, \ldots, w_{i-1})
PKN(wi∣wi−n+1,…,wi−1)=C(wi−n+1,…,wi−1)max(C(wi−n+1,…,wi)−d,0)+λ(wi−n+1,…,wi−1)PKN(wi∣wi−n+2,…,wi−1)
其中：
- 是折扣参数，通常介于0和1之间，用于从计数中减去固定的概率质量。
-
λ
(
w
i
−
n
+
1
,
…
,
w
i
−
1
)
\lambda(w_{i-n+1}, \ldots, w_{i-1})
λ(wi−n+1,…,wi−1)是归一化因子，确保概率之和为1，计算公式为：
λ
(
w
i
−
n
+
1
,
…
,
w
i
−
1
)
=
d
C
(
w
i
−
n
+
1
,
…
,
w
i
−
1
)
⋅
N
1
(
w
i
−
n
+
1
,
…
,
w
i
−
1
∙
)
\lambda(w_{i-n+1}, \ldots, w_{i-1}) = \frac{d}{C(w_{i-n+1}, \ldots, w_{i-1})} \cdot N_1(w_{i-n+1}, \ldots, w_{i-1} \bullet)
λ(wi−n+1,…,wi−1)=C(wi−n+1,…,wi−1)d⋅N1(wi−n+1,…,wi−1∙)
其中，
N
1
(
w
i
−
n
+
1
,
…
,
w
i
−
1
∙
)
N_1(w_{i-n+1}, \ldots, w_{i-1} \bullet)
N1(wi−n+1,…,wi−1∙) 表示以
w
i
−
n
+
1
,
…
,
w
i
−
1
w_{i-n+1}, \ldots, w_{i-1}
wi−n+1,…,wi−1开头的n-gram中，出现次数为1的n-gram的数量。
低阶n-gram的概率估计
对于最低阶的unigram，Kneser-Ney平滑采用一种独特的估计方法：
P
KN
(
w
i
)
=
N
(
∙
w
i
)
N
P_{\text{KN}}(w_i) = \frac{N(\bullet w_i)}{N}
PKN(wi)=NN(∙wi)
其中：
-
N
(
∙
w
i
)
N(\bullet w_i)
N(∙wi)表示w
i
w_i
wi 作为bigram结尾时，不同前缀词的数量。 -
N
N
N 是所有bigram类型的总数。
这种方法强调词在不同上下文中的“多样性”，而不是其在语料中的总频次，从而更合理地分配概率。
Kneser-Ney平滑示例
下面通过一个简单示例说明Kneser-Ney平滑的计算过程。
示例语料
假设有一个小型语料库，包含以下句子：
- I like to eat apples.
- I like to eat bananas.
- He likes to eat apples.
我们将计算bigram “like to” 的Kneser-Ney平滑概率，假设折扣参数
d
=
0.5
d = 0.5
d=0.5。
计算步骤
1. 计算计数
-
C
(
“like to”
)
=
2
C(\text{“like to”}) = 2
C(“like to”)=2（在第一句和第二句中出现） -
C
(
“like”
)
=
2
C(\text{“like”}) = 2
C(“like”)=2（在第一句和第二句中”like”作为前缀）
2. 高阶项计算
max
(
C
(
“like to”
)
−
d
,
0
)
C
(
“like”
)
=
max
(
2
−
0.5
,
0
)
2
=
1.5
2
=
0.75
\frac{\max(C(\text{“like to”}) – d, 0)}{C(\text{“like”})} = \frac{\max(2 – 0.5, 0)}{2} = \frac{1.5}{2} = 0.75
C(“like”)max(C(“like to”)−d,0)=2max(2−0.5,0)=21.5=0.75
3. 低阶项计算
计算
P
KN
(
“to”
)
P_{\text{KN}}(\text{“to”})
PKN(“to”)：
-
N
(
∙
“to”
)
N(\bullet \text{“to”})
N(∙“to”)：在语料中，“to” 作为bigram的结尾，其前缀词有 “like” 和 “likes”，因此N
(
∙
“to”
)
=
2
N(\bullet \text{“to”}) = 2
N(∙“to”)=2。 - 假设所有bigram类型总数
N
=
10
N = 10
N=10（实际应统计得出，此处为简化假设）。 - 则：
P
KN
(
“to”
)
=
N
(
∙
“to”
)
N
=
2
10
=
0.2
P_{\text{KN}}(\text{“to”}) = \frac{N(\bullet \text{“to”})}{N} = \frac{2}{10} = 0.2
PKN(“to”)=NN(∙“to”)=102=0.2
4. 计算归一化因子
λ
(
“like”
)
\lambda(\text{“like”})
λ(“like”)
-
N
1
(
“like”
∙
)
N_1(\text{“like”} \bullet)
N1(“like”∙)：以 “like” 开头的bigram中，“like to” 出现2次，假设无其他单次出现的bigram，则N
1
(
“like”
∙
)
=
0
N_1(\text{“like”} \bullet) = 0
N1(“like”∙)=0。但为示例完整性，假设存在 “like something” 出现1次，则N
1
(
“like”
∙
)
=
1
N_1(\text{“like”} \bullet) = 1
N1(“like”∙)=1。 - 则：
λ
(
“like”
)
=
d
C
(
“like”
)
⋅
N
1
(
“like”
∙
)
=
0.5
2
⋅
1
=
0.25
\lambda(\text{“like”}) = \frac{d}{C(\text{“like”})} \cdot N_1(\text{“like”} \bullet) = \frac{0.5}{2} \cdot 1 = 0.25
λ(“like”)=C(“like”)d⋅N1(“like”∙)=20.5⋅1=0.25
5. 组合计算
P
KN
(
“to”
∣
“like”
)
=
0.75
+
0.25
⋅
0.2
=
0.75
+
0.05
=
0.8
P_{\text{KN}}(\text{“to”} | \text{“like”}) = 0.75 + 0.25 \cdot 0.2 = 0.75 + 0.05 = 0.8
PKN(“to”∣“like”)=0.75+0.25⋅0.2=0.75+0.05=0.8
因此，bigram “like to” 的Kneser-Ney平滑概率为0.8。
Kneser-Ney平滑的优缺点
优点
- 低阶信息利用：通过回退机制有效利用低阶n-gram，改善未见n-gram的概率估计。
- 大数据集表现：在大规模语料上，Kneser-Ney平滑通常比其他方法获得更低的困惑度（perplexity）。
缺点
- 参数选择复杂：折扣参数
d
d
d 需要通过交叉验证等方法确定，增加了计算成本。 - 实现难度：相比简单的平滑技术（如拉普拉斯平滑），其实现更为复杂。
与其他平滑方法的比较
常见的平滑方法包括：
- 拉普拉斯平滑：为每个n-gram计数加1，简单但对大数据集效果有限。
- Good-Turing平滑：调整低频n-gram计数，适用于小数据集，但在高阶n-gram中可能不稳定。
- Witten-Bell平滑：基于回退，与Kneser-Ney类似，但在低阶概率估计上有所不同。
研究表明，Kneser-Ney平滑在语音识别、机器翻译等任务中表现优于上述方法。
总结
Kneser-Ney平滑通过折扣和回退机制，有效解决了n-gram模型中的数据稀疏问题。其在自然语言处理中的广泛应用得益于其对低阶信息的巧妙利用和在大数据集上的优异性能。尽管实现复杂，但其显著的性能提升使其成为语言建模领域的关键技术。
参考文献
- Chen, S. F., & Goodman, J. (1999). An empirical study of smoothing techniques for language modeling. Computer Speech & Language, 13(4), 359-394.
- Jurafsky, D., & Martin, J. H. (2020). Speech and Language Processing (3rd ed.). Prentice Hall.
- Kneser, R., & Ney, H. (1995). Improved backing-off for m-gram language modeling. Proceedings of ICASSP, 181-184.