C.2 Kneser–Ney 折扣 - SLP3 中文翻译

Kneser–Ney 折扣（Kneser and Ney, 1995）在绝对折扣的基础上，以一种更精细的方式处理低阶一元语法分布。假设我们正在对二元语法模型和一元语法模型做插值，请考虑预测下面句子的下一个词：

I can’t see without my reading

这里接在后面的词显然更可能是 glasses，而不是 Kong，所以我们希望一元语法模型更偏好 glasses。但事实上，因为 Hong Kong 是一个非常常见的词组，Kong 的整体频率反而更高。标准一元语法模型会给 Kong 分配比 glasses 更高的概率。我们希望捕捉这样的直觉：尽管 Kong 很常见，它却主要只在 Hong Kong 这个短语中出现，也就是主要出现在 Hong 之后；而 glasses 的分布范围要广得多。

换言之，普通的 $P(w)$ 回答“ $w$ 有多大可能出现？”；我们想建立一个可称为 $P_{\text{CONTINUATION}}$ 的一元语法模型，回答“ $w$ 作为一个新续接词出现的可能性有多大？”应当如何估计词 $w$ 在一个此前未见的上下文中作为新续接出现的概率？Kneser–Ney 方法的直觉是：以 $w$ 曾经出现过的不同上下文数量为依据，也就是以它所补全的二元语法类型数量来估计 $P_{\text{CONTINUATION}}$ 。每一种二元语法类型第一次出现时，都是一次新续接。我们的假设是：过去曾在更多上下文中出现的词，将来也更有可能出现在某个新上下文中。词 $w$ 作为新续接出现的次数可以表示为：

P_{\text{CONTINUATION}}(w) \propto \left|\{v:C(vw)>0\}\right|\tag{C.3}

为了把该计数转化为概率，我们用词语二元语法类型的总数进行归一化。综上：

P_{\text{CONTINUATION}}(w) = \frac{\left|\{v:C(vw)>0\}\right|}{\left|\{(u',w'):C(u'w')>0\}\right|}\tag{C.4}

换一种比喻，也可以用曾经出现在 $w$ 之前的词类型数量来表达同一个定义（重复公式 C.3）：

P_{\text{CONTINUATION}}(w) \propto \left|\{v:C(vw)>0\}\right|\tag{C.5}

再用所有词之前出现的词类型总数进行归一化：

P_{\text{CONTINUATION}}(w) = \frac{\left|\{v:C(vw)>0\}\right|}{\sum_{w'}\left|\{v:C(vw')>0\}\right|}\tag{C.6}

因此，一个高频词（如 Kong）若只出现在一种上下文（Hong）中，其续接概率仍然很低。

于是，用于二元语法的插值 Kneser–Ney 平滑最终公式为：

P_{\mathrm{KN}}(w_i\mid w_{i-1}) = \frac{\max(C(w_{i-1}w_i)-d,0)}{C(w_{i-1})} + \lambda(w_{i-1})P_{\text{CONTINUATION}}(w_i)\tag{C.7}

$\lambda$ 是一个归一化常数，用于分配被折扣掉的概率质量：

\lambda(w_{i-1}) = \frac{d}{\sum_v C(w_{i-1}v)}\left|\{w:C(w_{i-1}w)>0\}\right|\tag{C.8}

第一项 $\frac{d}{\sum_v C(w_{i-1}v)}$ 是归一化折扣，其中折扣值 $d$ 满足 $0\leq d\leq 1$ ，已在上一节的绝对折扣中介绍。第二项 $\left|\{w:C(w_{i-1}w)>0\}\right|$ 是能够接在 $w_{i-1}$ 之后的词类型数量，等价地说，也就是被我们折扣的词类型数量；换言之，它表示应用归一化折扣的次数。

一般的递归形式如下：

P_{\mathrm{KN}}(w_i\mid w_{i-n+1:i-1}) = \frac{\max(c_{\mathrm{KN}}(w_{i-n+1:i})-d,0)}{\sum_v c_{\mathrm{KN}}(w_{i-n+1:i-1}v)} + \lambda(w_{i-n+1:i-1})P_{\mathrm{KN}}(w_i\mid w_{i-n+2:i-1})\tag{C.9}

其中，计数 $c_{\mathrm{KN}}$ 的定义取决于我们所统计的是参与插值的最高阶 n 元语法（例如，在三元、二元和一元语法之间插值时的三元语法），还是某个低阶 n 元语法（同一例子中的二元或一元语法）：

c_{\mathrm{KN}}(\cdot)= \begin{cases} \operatorname{count}(\cdot), & \text{最高阶 n 元语法},\\ \operatorname{continuationcount}(\cdot), & \text{低阶 n 元语法}. \end{cases}\tag{C.10}

一个字符串的续接计数（continuation count），就是该字符串曾出现于多少种不同的单词上下文中。

递归终止时，将一元语法与均匀分布进行插值，其中参数 $\epsilon$ 表示空字符串：

P_{\mathrm{KN}}(w) = \frac{\max(c_{\mathrm{KN}}(w)-d,0)}{\sum_{w'}c_{\mathrm{KN}}(w')} + \lambda(\epsilon)\frac{1}{V}\tag{C.11}

若要包含未知词 <UNK>，只需把它作为一个计数为零的普通词表项。因此，它的概率将是经 $\lambda$ 加权的均匀分布 $\frac{\lambda(\epsilon)}{V}$ 。

效果最好的 Kneser–Ney 平滑版本称为修正 Kneser–Ney 平滑（modified Kneser–Ney smoothing），由 Chen 和 Goodman（1998）提出。修正方法不再使用单一的固定折扣值 $d$ ，而是分别为计数为 1、2 以及不小于 3 的 n 元语法使用三个不同的折扣值 $d_1$ 、 $d_2$ 和 $d_{3+}$ 。细节参见 Chen 和 Goodman（1998，第 19 页）或 Heafield 等人（2013）。

Chen, S. F. and J. Goodman. 1998. An empirical study of smoothing techniques for language modeling. Technical Report TR-10-98, Computer Science Group, Harvard University.

Church, K. W. and W. A. Gale. 1991. A comparison of the enhanced Good-Turing and deleted estimation methods for estimating probabilities of English bigrams. Computer Speech and Language, 5:19–54.

Heafield, K., I. Pouzyrevsky, J. H. Clark, and P. Koehn. 2013. Scalable modified Kneser-Ney language model estimation. ACL.

Kneser, R. and H. Ney. 1995. Improved backing-off for M gram language modeling. ICASSP, volume 1.

Ney, H., U. Essen, and R. Kneser. 1994. On structuring probabilistic dependencies in stochastic language modelling. Computer Speech and Language, 8:1–38.