神经网络语言建模系列之三：重要性采样

重要性采样（Important Sampling, IS）属于蒙特卡洛（Monte Carlo）方法，被 Bengio and Senecal (2003) 引入到神经网络语言建模中，用于加速神经网络语言模型的训练。重要性采样方法能够减少神经网络语言模型的训练时间，但是效果并不显著，还会导致模型的稳定性下降，并且只能加速模型的训练，无法提升预测阶段的计算速度。

1. 前言

目前，神经网络语言建模（Language Modeling, LM）技术被认为是最优以及最有潜力的语言建模技术，相对于其他传统的语言建模技术，如N-gram语言建模，最大熵语言建模等，具有显著的优势。但是，神经网络语言模型的计算量较大，无论是训练还是预测都非常耗时，成为其在实际应用中最大的障碍。加速神经网络语言模型的计算是神经网络语言建模研究的重要方向之一，并且许多加速算法被提出，其中一类加算法是基于采样技术，而最早被引入的就是重要性采样。在 Hinton (2002) 的启发下， Bengio and Senecal (2003) 研究了多种采样方法在神经网络语言模型上的加速性能，最终利用重要性采样成功地加速了神经网络语言模型的训练。引入重要性采样算法的神经网络语言模型在训练过程中，容易出现发散现象，需要采用合理的策略来调整采样数，保持模型稳定。随后， Bengio and Senecal (2008) 和 Jean et. al. (2015) 改进了重要性采样在神经网络语言模型中的应用。

2. 重要性采样

重要性采样属于蒙特卡洛方法，即基于概率统计的数值计算方法，利用随机采样来拟合目标函数。1946年，美国拉斯阿莫斯国家实验室的三位科学家John von Neumann，Stan Ulam 和 Nick Metropolis共同发明了一种采样算法，被称为蒙特卡洛方法。它的具体定义是：在广场上画一个边长一米的正方形，在正方形内部随意用粉笔画一个不规则的形状，现在要计算这个不规则图形的面积。均匀的向该正方形内撒 $N$ （ $N$ 是一个很大的自然数）个黄豆，随后数数有多少个黄豆在这个不规则几何形状内部，比如说有 $M$ 个，那么，这个奇怪形状的面积便近似于 $M/N$ ，并且 $N$ 越大，计算得到的面积便越精确。在这里我们要假定豆子都在一个平面上，相互之间没有重叠。

采用数学化的语言进行描述，假设求解函数 $f(x)$ 在分布 $p(x)$ 下的期望，即

当函数 $f(x)$ 比较复杂时，直接采用解析方式求解期望比较困难。蒙特卡洛方法，当采样数足够多时，就越接近原始分布，因此函数 $f(x)$ 在分布 $p(x)$ 下的期望可转换为：

其中， $N$ 为采样数，数值越大，结果越接近真实值。

在实际应用中，实际概率分布 $p(x)$ 可能比较复杂，不易直接从实际概率分布进行采样。此时，可以引入于实际概率分布 $p(x)$ 的定义域相同的概率分布 $q(x)$ ，利用概率分布 $q(x)$ 进行采样，该方法就称为重要性采样。利用重要性采样，函数 $f(x)$ 在分布 $p(x)$ 下的期望可改写为：

此处只对重要性采样方法作了简略的介绍，方便读者理解如何通过重要性采样方法来加速神经网络语言模型的训练。如果需要对重要性采样方法进行详细深入的了解学习，还需参考相关的专业资料。

3. 语言模型加速

神经网络语言模型的输出层直接输出的为非归一化的条件概率，因此需要采用Softmax函数对输出进行归一化处理，这也是导致神经网络语言模型的计算量较大的重要因素。神经网络语言模型最终输出的条件概率形如：
其中， $w_t$ 为t时刻的目标词， $h_t$ 为t时刻神经网络隐藏层的输出， $y(w_t,h_t)$ 为 $t$ 时刻输出的非归一化条件概率， $N_v$ 为词典中词的总数。因此，神经网络语言模型可被看作为能量模型的特例，但是是否了解能量模型，并不影响理解重要性采样对神经网络语言模型训练的加速原理。

神经网络语言模型通常采用梯度下降（Gradient Descent, GD）算法进行训练，模型的参数根据反向传播的误差梯度进行更新。在神经网络语言模型中，模型参数的误差梯度由两个部分构成：目标词 $w_t$ 的正面强化部分和以 $P(w_i{\mid}h_t)$ 为权重的其他词 $w_i (i{\neq}t)$ 的负面强化部分，即：

不难看出，正部只涉及目标词，其计算量可以忽略不计。模型的计算量主要集中在负部，因为其他词的数量与词典大小的量级一致，一般为几十万，甚至上百万。如果能够近似地估算出负部的梯度，那么在训练过程中能够极大地减少模型的计算量，这也是利用重要性采样来加速神经网络语言模型的基本思想。

参数梯度的负部可以看做是梯度在分布 $P(w_i{\mid}h_t)$ 下的期望，可以通过采样的方式进行近似，即重要性采样。引入与分布 $P$ 近似的建议分布 $Q$ ，对参数梯度的负部进行近似得到：

其中， $N_s$ 为采样的样本数量。

但为了减少计算量，分布 $P(w_i{\mid}h_t)$ 是需要避免进行计算的，因为计算 $P(w_i{\mid}h_t)$ 需要计算模型的所有输出。为了对分布 $P(w_i{\mid}h_t)$ 进行分析，先对其进行如下转换：

对转换后的分布进行分析， $Z$ 可以看作均匀分布 $1/N_v$ 下的期望，即:

于是再次利用重要性采样，对 $Z$ 进行近似估计，可得：

经过两次重要性采样操作，便可以得到参数梯度的最终近似估计，即：

其中， $W$ 为采样得到的词集合，其大小即为采样数 $N_s$ 。

4. 模型实现

经过上述论述，从理论上证明了重要性采样的可行性。在实际应用中，仍然有许多问题。其中两个主要的问题，一个是选取合适建议分布 $Q$ ，另一个是调节采样的数量，以保证模型的性能，即保证模型的稳定性以及最终的PPL指标。

选择合适的建议分布 $Q$ ，对模型的性能有着重大的影响，建议分布 $Q$ 与目标分布 $P$ 越接近，其效果越好。关于建议分布 $Q$ ，通常有如下几种选择：

Unigram分布

指数Unigram分布

N-gram分布

其中，Unigram分布或者指数Unigram分布是比较常用的分布，比较容易获取，从语言模型的训练数据中直接统计计算即可得到。除了上述采用固定的建议分布外， Bengio and Senecal (2008) 提出了利用模型训练过程的输出，对建议分布进行动态修正，减少建议分布与目标分布的差异。

另外一个重要的问题是采样的样本数的调整。对于重要性采样，如果样本数越充足，其精度就越高，但是如果采样数太大，便失去加速训练的效果。另一方面，随着训练的进行，模型精度越来越高，如果采样数保持不变，重要性采样的精度就会不足，导致模型不稳定，因此需要随着训练的进行，不断增加采样数。 Bengio and Senecal (2003) 提出了评估采样数是否足够的目标函数，在训练阶段根据目标函数对采样数进行检测调整，而 Jean et. al. (2015) 则提出利用验证集，对采样数进行评估调整。

此处，分别引用 Bengio and Senecal (2003) 和 Bengio and Senecal (2008) 的实验结果来说明重要性采样对神经网络语言模型的加速效果，如下表所示：