苏剑林作者

“噪声对比估计”杂谈:曲径通幽之妙

作者丨苏剑林

单位丨广州火焰信息科技有限公司

研究方向丨NLP,神经网络

个人主页丨kexue.fm

说到噪声对比估计,或者“负采样”,大家可能立马就想到了 Word2Vec。事实上,它的含义远不止于此,噪音对比估计(NCE, Noise Contrastive Estimation)是一个迂回但却异常精美的技巧,它使得我们在没法直接完成归一化因子(也叫配分函数)的计算时,就能够去估算出概率分布的参数。本文就让我们来欣赏一下 NCE 的曲径通幽般的美妙。 

注:由于出发点不同,本文所介绍的“噪声对比估计”实际上更偏向于所谓的“负采样”技巧,但两者本质上是一样的,在此不作区分。

问题起源

问题的根源是难分难舍的指数概率分布。

指数族分布

在很多问题中都会出现指数族分布,即对于某个变量 x 的概率 p(x),我们将其写成:

其中 G(x) 是 x 的某个“能量”函数,而则是归一化常数,也叫配分函数。这种分布也称为“玻尔兹曼分布”。

机器学习中,指数族分布的主要来源有两个。第一个来源是 softmax:我们做分类预测时,通常最后都会将全连接层的结果用 softmax 激活,这就是一个离散的、有限个点的玻尔兹曼分布了;第二个则是来源于最大熵原理:当我们引入某个特征并且已经能估算出特征的期望时,最大熵模型告诉我们其分布应该是特征的指数形式。

难算的配分函数

总的来说,指数族分布是非常实用的一类分布,不论是机器学习、数学还是物理领域,都能够碰见它。然而,它却有一个比较大的问题:不容易算,准确来说是配分函数不容易算。

具体来说,不好算的原因可能有两个。一个是计算量太大,比如语言模型(包括 Word2Vec)的场景,因为要通过上下文来预测当前词的分布情况,这就需要对几十万甚至几百万项(取决于词表大小)进行求和来算归一化因子,这种情况下不是不能算,而是计算量大到难以承受了。

另一种情况是根本算不出来,比如假设,那么就有:

这积分根本就没法简单地算出来呀,更不用说更加复杂的函数了。现在我们也许能从这个角度感受到为什么高斯分布那么常用了,因为,因为,因为,换个分布就没法算下去了……

机器学习中,如果只是分类、预测,那么归一化因子算不算出来都无所谓,因为我们只要相对比较取出最大的那个。但是在预测之前,我们还面临着训练的问题,也就是参数估计,具体来说,G(x) 其实是含有一些位置参数 θ 的,准确来说要写成 G(x;θ),那么概率分布就是:

我们要从 x 的样本中推算出 θ 来,通常我们会用最大似然,但是不算出 Z(θ) 来我们就没法算似然函数,也就没法做下去了。

NCE登场

非常幸运的是,NCE 诞生了,它成功地绕开了这个困难。对于配分函数算不出来的情形,它提供了一种算下去的可能性;对于配分函数计算量太大的情形,它还提供了一种降低计算量的方案。 

变成二分类问题

NCE 的思想很简单,它希望我们将真实的样本和一批“噪声样本”进行对比,从中发现真实样本的规律出来。 

具体来说,能量还是原来的能量 G(x;θ),但这时候我们不直接算概率 p(x) 了,因为归一化因子很难算。我们去算:

这里的 θ 还是原来的待优化参数,而 γ 则是新引入的要优化的参数

然后,NCE 的损失函数变为:

其中 p̃(x) 是真实样本,U(x) 是某个“均匀”分布或者其他的、确定的、方便采样的分布。 

说白了,NCE 的做法就是将它转化为二分类问题,将真实样本判为 1,从另一个分布采样的样本判为 0

等价于原来分布 

现在的问题是,从 (5) 式估算出来的 θ,跟直接从 (3) 式的最大似然估计(理论上是可行的)出来的结果是不是一样的。 

答案是基本一样的。我们将 (5) 式中的 loss 改写为:

因为 p̃(x) 和 U(x) 都跟参数 θ,γ 没关,因此将 loss 改为下面的形式,不会影响优化结果:

其中:

(7) 式是 KL 散度的积分,而 KL 散度非负,那么当“假设的分布形式是满足的、并且充分优化”时,(7) 式应该为 0,从而我们有 p̃(y|x)=p(y|x),也就是:

从中可以解得:

如果 U(x) 取均匀分布,那么 U(x) 就只是一个常数,所以最终的效果表明 γ−logU(x) 起到了 logZ 的作用,而分布还是原来的分布 (3),θ 还是原来的 θ。

这就表明了 NCE 就是一种间接优化 (3) 式的巧妙方案:看似迂回,实则结果等价,并且 (5) 式的计算量也大大减少,因为计算量就只取决于采样的数目了。

一些插曲

一些跟 NCE 相关的话题,就都放在这里了。 

NCE与负采样简述

NCE 的系统提出是在 2010 年的论文 Noise-contrastive estimation: A new estimation principle for unnormalized statistical models 中,后面训练大规模的神经语言模型基本上都采用 NCE 或者类似的 loss 了。

论文的标题其实就表明了 NCE 的要点:它是“非归一化模型”的一个“参数估计原理”,专门应对归一化因子难算的场景。 

但事实上,“负采样”的思想其实早就被使用了,比如就在 2008 年的 ICML 上,Ronan Collobert 和 Jason Weston 在发表的 A Unified Architecture for Natural Language Processing: Deep Neural Networks with Multitask Learning 中已经用到了负采样的方法来训练词向量。

要知道,那时候距离 Word2Vec 发布还有四五年。关于词向量和语言模型的故事,请参考 licstar 的《词向量和语言模型[1]。 

基于同样的为了降低计算量的需求,后来Google的Word2Vec也用上了负采样技巧,在很多任务下,它还比基于Huffman Softmax的效果要好,尤其是那个“词类比(word analogy)”实验。这里边的奥妙,我们马上就来分析。 

Word2Vec

现在我们落实到 Word2Vec 来分析一些事情。以 Skip Gram 模型为例,Word2Vec 的目标是:

其中 ui,vj 都是待优化参数,代表着上下文和中心词的两套不同的词向量空间。显然地,这里的问题就是归一化因子计算量大,其中应对方案有 Huffman Softmax 和负采样。

这里我们不关心 Huffman Softmax,只需要知道它就是原来标准 Softmax 的一种近似就行了。我们来看负采样的,Word2Vec 将优化目标变为了:

这个式子看着有点眼花,总之它就是表达了“语料出现的 Skip Gram 视为正样本,随机采样的词作为负样本”的意思。 

首先最明显的是,(12) 式相比 (4),(5) 式,少引入了 γ 这个训练参数,或者就是说默认了 γ=0,这允许吗?据说确实有人做过对比实验,结果显示训练出来的 γ 确实在 0 上下浮动,因此这个默认操作基本上是合理的。 

其次,对于负样本,Word2Vec 可不是“均匀地采样每一个词”,而是按照每个词本身的总词频来采样的。这样一来,(10) 式就变成了:

也就是说,最终的拟合效果是:

大家可以看到,左边就是两个词的互信息。本来我们的拟合目标是两个词的内积等于条件概率 p̃(wj|wi)(的对数),现在经过负采样的 Word2Vec,两个词的内积就是两个词的互信息。 

现在大概就可以解释为什么 Word2Vec 的负采样会比 Huffman Softmax 效果要好些了。Huffman Softmax 只是对 Softmax 做了近似,它本质上还是在拟合 p̃(wj|wi),而负采样技巧则是在拟合互信息

我们之后,Word2Vec 是靠词的共现来反应词义的,互信息比条件概率 p̃(wj|wi)更能反映词与词之间“真正的”共现关系。换言之,p̃(wj|wi) 反映的可能是“我认识周杰伦,周杰伦却不认识我”的关系,而互信息反映的是“你认识我,我也认识你”的关系,后者更能体现出语义关系。 

我之前构造的另一个词向量模型《更别致的词向量模型(三):描述相关的模型》[2] 中也表明了,基于互信息出发构造的模型,能理论上解释“词类比(word analogy)”等很多实验结果,这也间接证实了,基于互信息的“Skip Gram + 负采样”组合,是 Word2Vec 的一个绝佳组合。

所以,根本原因不是 Huffman Softmax 和负采样本身谁更优的问题,而是它们的优化目标就已经不同。

列车已到终点站

本文的目的是介绍 NCE 这种精致的参数估算技巧,指出它可以在难以为完成归一化时来估算概率分布中的参数,原则上这是一种通用的方法,而且很可能,在某些场景下它是唯一可能的方案。

最后我们以 Word2Vec 为具体例子进行简单的分析,谈及了使用 NCE 时的一些细节问题,并且顺带解释了负采样为什么好的这个问题。

推荐、解读、讨论和报道人工智能前沿论文成果的学术平台。

入门噪音对比估计机器学习
2
相关数据
神经网络技术
Neural Network

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

分类问题技术
Classification

分类问题是数据挖掘处理的一个重要组成部分,在机器学习领域,分类问题通常被认为属于监督式学习(supervised learning),也就是说,分类问题的目标是根据已知样本的某些特征,判断一个新的样本属于哪种已知的样本类。根据类别的数量还可以进一步将分类问题划分为二元分类(binary classification)和多元分类(multiclass classification)。

高斯分布技术
Gaussian distribution

正态分布是一个非常常见的连续概率分布。由于中心极限定理(Central Limit Theorem)的广泛应用,正态分布在统计学上非常重要。中心极限定理表明,由一组独立同分布,并且具有有限的数学期望和方差的随机变量X1,X2,X3,...Xn构成的平均随机变量Y近似的服从正态分布当n趋近于无穷。另外众多物理计量是由许多独立随机过程的和构成,因而往往也具有正态分布。

机器学习技术
Machine Learning

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

语言模型技术
Language models

语言模型经常使用在许多自然语言处理方面的应用,如语音识别,机器翻译,词性标注,句法分析和资讯检索。由于字词与句子都是任意组合的长度,因此在训练过的语言模型中会出现未曾出现的字串(资料稀疏的问题),也使得在语料库中估算字串的机率变得很困难,这也是要使用近似的平滑n元语法(N-gram)模型之原因。

似然函数技术
Likelihood function

在数理统计学中,似然函数是一种关于统计模型中的参数的函数,表示模型参数中的似然性。 似然函数在统计推断中有重大作用,如在最大似然估计和费雪信息之中的应用等等。“ 似然性”与“或然性”或“概率”意思相近,都是指某种事件发生的可能性,但是在统计学中,“似然性”和“或然性”或“概率”又有明确的区分。

损失函数技术
Loss function

在数学优化,统计学,计量经济学,决策理论,机器学习和计算神经科学等领域,损失函数或成本函数是将一或多个变量的一个事件或值映射为可以直观地表示某种与之相关“成本”的实数的函数。

最大似然估计技术
Maximum Likelihood Estimation

极大似然估计是统计学中用来估计概率模型参数的一种方法

最大熵模型技术
Maximum Entropy Modeling

最大熵原理是概率模型学习的一个准则:学习概率模型时,在所有可能的概率模型(分布)中,熵最大的模型是最好的模型。 应用最大熵原理得到的模型就是最大熵模型。

神经语言模型技术
Neural Network Language Models

语言模型是估计单词序列的联合概率函数,比如给一个长度为m的单词序列,通过使用语言模型,可以获得这m个单词分布的概率P(W1,...,Wm)。对于许多的自然语言处理的应用,可以估计不同短语的概率是极具应用价值的。语言模型可以应用于语音识别,机器翻译,语音标记,解析,手写识别,信息检索等领域。

参数技术
parameter

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

噪音技术
Noise

噪音是一个随机误差或观测变量的方差。在拟合数据的过程中,我们常见的公式$y=f(x)+\epsilon$中$\epsilon$即为噪音。 数据通常包含噪音,错误,例外或不确定性,或者不完整。 错误和噪音可能会混淆数据挖掘过程,从而导致错误模式的衍生。去除噪音是数据挖掘(data mining)或知识发现(Knowledge Discovery in Database,KDD)的一个重要步骤。

Ronan Collobert人物
Ronan Collobert

推荐文章