“噪声对比估计”杂谈:曲径通幽之妙
By 苏剑林 | 2018-06-13 | 175779位读者 |说到噪声对比估计,或者“负采样”,大家可能立马就想到了Word2Vec。事实上,它的含义远不止于此,噪音对比估计(NCE, Noise Contrastive Estimation)是一个迂回但却异常精美的技巧,它使得我们在没法直接完成归一化因子(也叫配分函数)的计算时,就能够去估算出概率分布的参数。本文就让我们来欣赏一下NCE的曲径通幽般的美妙。
注:由于出发点不同,本文所介绍的“噪声对比估计”实际上更偏向于所谓的“负采样”技巧,但两者本质上是一样的,在此不作区分。
问题起源 #
问题的根源是难分难舍的指数概率分布~
指数族分布 #
在很多问题中都会出现指数族分布,即对于某个变量$\boldsymbol{x}$的概率$p(\boldsymbol{x})$,我们将其写成
$$p(\boldsymbol{x}) = \frac{e^{G(\boldsymbol{x})}}{Z}\tag{1}$$
其中$G(\boldsymbol{x})$是$\boldsymbol{x}$的某个“能量”函数,而$Z=\sum_{\boldsymbol{x}} e^{G(\boldsymbol{x})}$则是归一化常数,也叫配分函数。这种分布也称为“玻尔兹曼分布”。
在机器学习中,指数族分布的主要来源有两个。第一个来源是softmax:我们做分类预测时,通常最后都会将全连接层的结果用softmax激活,这就是一个离散的、有限个点的玻尔兹曼分布了;第二个则是来源于最大熵原理:当我们引入某个特征并且已经能估算出特征的期望时,最大熵模型告诉我们其分布应该是特征的指数形式。(参考《“熵”不起:从熵、最大熵原理到最大熵模型(二)》。)
难算的配分函数 #
总的来说,指数族分布是非常实用的一类分布,不论是机器学习、数学还是物理领域,都能够碰见它。然而,它却有一个比较大的问题:不容易算,准确来说是配分函数不容易算。
具体来说,不好算的原因可能有两个。一个是计算量太大,比如语言模型(包括Word2Vec)的场景,因为要通过上下文来预测当前词的分布情况,这就需要对几十万甚至几百万项(取决于词表大小)进行求和来算归一化因子,这种情况下不是不能算,而是计算量大到难以承受了;另一种情况是根本算不出来~比如假设$p(x)=\frac{e^{-ax^2-bx^4}}{Z}$那么就有
$$Z = \int e^{-ax^2-bx^4} dx\tag{2}$$
这积分根本就没法简单地算出来呀,更不用说更加复杂的函数了。现在我们也许能从这个角度感受到为什么高斯分布那么常用了,因为,因为,因为,换个分布就没法算下去了...
在机器学习中,如果只是分类、预测,那么归一化因子算不算出来都无所谓,因为我们只要相对比较取出最大的那个。但是在预测之前,我们还面临着训练的问题,也就是参数估计,具体来说,$G(\boldsymbol{x})$其实是含有一些未知参数$\boldsymbol{\theta}$的,准确来说要写成$G(\boldsymbol{x};\boldsymbol{\theta})$,那么概率分布就是
$$p(\boldsymbol{x})=\frac{e^{G(\boldsymbol{x};\boldsymbol{\theta})}}{Z(\boldsymbol{\theta})}\tag{3}$$
我们要从$\boldsymbol{x}$的样本中推算出$\boldsymbol{\theta}$来,通常我们会用最大似然,但是不算出$Z(\boldsymbol{\theta})$来我们就没法算似然函数,也就没法做下去了。
NCE登场 #
非常幸运的是,NCE诞生了,它成功地绕开了这个困难。对于配分函数算不出来的情形,它提供了一种算下去的可能性;对于配分函数计算量太大的情形,它还提供了一种降低计算量的方案。
变成二分类问题 #
NCE的思想很简单,它希望我们将真实的样本和一批“噪声样本”进行对比,从中发现真实样本的规律出来。
具体来说,能量还是原来的能量$G(\boldsymbol{x};\boldsymbol{\theta})$,但这时候我们不直接算概率$p(\boldsymbol{x})$了,因为归一化因子很难算。我们去算
$$p(1|\boldsymbol{x})=\sigma\Big(G(\boldsymbol{x};\boldsymbol{\theta})-\gamma\Big)=\frac{1}{1+e^{-G(\boldsymbol{x};\boldsymbol{\theta})+\gamma}}\tag{4}$$
这里的$\boldsymbol{\theta}$还是原来的待优化参数,而$\gamma$则是新引入的要优化的参数。
然后,NCE的损失函数变为
$$\mathop{\text{argmin}}_{\boldsymbol{\theta},\gamma} - \mathbb{E}_{\boldsymbol{x}\sim \tilde{p}(\boldsymbol{x})}\log p(1|\boldsymbol{x})- \mathbb{E}_{\boldsymbol{x}\sim U(\boldsymbol{x})}\log p(0|\boldsymbol{x})\tag{5}$$
其中$\tilde{p}(\boldsymbol{x})$是真实样本,$U(\boldsymbol{x})$是某个“均匀”分布或者其他的、确定的、方便采样的分布。
说白了,NCE的做法就是将它转化为二分类问题,将真实样本判为1,从另一个分布采样的样本判为0。
等价于原来分布 #
现在的问题是,从$(5)$式估算出来的$\boldsymbol{\theta}$,跟直接从$(3)$式的最大似然估计(理论上是可行的)出来的结果是不是一样的。
答案是基本一样的。我们将$(5)$式中的loss改写为
$$-\int \tilde{p}(\boldsymbol{x})\log p(1|\boldsymbol{x}) d\boldsymbol{x}- \int U(\boldsymbol{x})\log p(0|\boldsymbol{x})d\boldsymbol{x}\tag{6}$$
因为$\tilde{p}(\boldsymbol{x})$和$U(\boldsymbol{x})$都跟参数$\boldsymbol{\theta},\gamma$没关,因此将loss改为下面的形式,不会影响优化结果
$$\begin{aligned}&\int \big(\tilde{p}(\boldsymbol{x})+U(\boldsymbol{x})\big) \left(\tilde{p}(1|\boldsymbol{x}) \log \frac{\tilde{p}(1|\boldsymbol{x})}{p(1|\boldsymbol{x})} + \tilde{p}(0|\boldsymbol{x})\log \frac{\tilde{p}(0|\boldsymbol{x})}{p(0|\boldsymbol{x})}\right)d\boldsymbol{x}\\
=&\int \big(\tilde{p}(\boldsymbol{x})+U(\boldsymbol{x})\big) KL\Big(\tilde{p}(y|\boldsymbol{x})\Big\Vert p(y|\boldsymbol{x})\Big) d\boldsymbol{x}\end{aligned}\tag{7}$$
其中
$$\tilde{p}(1|\boldsymbol{x})=\frac{\tilde{p}(\boldsymbol{x})}{\tilde{p}(\boldsymbol{x})+U(\boldsymbol{x})}\tag{8}$$
$(7)$式是KL散度的积分,而KL散度非负,那么当“假设的分布形式是满足的、并且充分优化”时,$(7)$式应该为0,从而我们有$\tilde{p}(y|\boldsymbol{x})= p(y|\boldsymbol{x})$,也就是
$$\frac{\tilde{p}(\boldsymbol{x})}{\tilde{p}(\boldsymbol{x})+U(\boldsymbol{x})}=\tilde{p}(1|\boldsymbol{x})=p(1|\boldsymbol{x})=\sigma\Big(G(\boldsymbol{x};\boldsymbol{\theta})-\gamma\Big)\tag{9}$$
从中可以解得
$$\begin{aligned}\tilde{p}(\boldsymbol{x})=&\frac{p(1|\boldsymbol{x})}{p(0|\boldsymbol{x})}U(\boldsymbol{x})\\
=&\exp\Big\{G(\boldsymbol{x};\boldsymbol{\theta})-\gamma\Big\}U(\boldsymbol{x})\\
=&\exp\Big\{G(\boldsymbol{x};\boldsymbol{\theta})-\big(\gamma-\log U(\boldsymbol{x})\big)\Big\}\end{aligned}\tag{10}$$
如果$U(\boldsymbol{x})$取均匀分布,那么$U(\boldsymbol{x})$就只是一个常数,所以最终的效果表明$\gamma - \log U(\boldsymbol{x})$起到了$\log Z$的作用,而分布还是原来的分布$(3)$,$\boldsymbol{\theta}$还是原来的$\boldsymbol{\theta}$。
这就表明了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的《词向量和语言模型》。
基于同样的为了降低计算量的需求,后来Google的Word2Vec也用上了负采样技巧,在很多任务下,它还比基于Huffman Softmax的效果要好,尤其是那个“词类比(word analogy)”实验。这里边的奥妙,我们马上就来分析。
Word2Vec #
现在我们落实到Word2Vec来分析一些事情。以Skip Gram模型为例,Word2Vec的目标是
$$p(w_j|w_i)=\frac{e^{\langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle}}{Z_i}\tag{11}$$
其中$\boldsymbol{u}_i, \boldsymbol{v}_j$都是待优化参数,代表着中心词和上下文的两套不同的词向量空间。显然地,这里的问题就是归一化因子计算量大,其中应对方案有Huffman Softmax和负采样。这里我们不关心Huffman Softmax,只需要知道它就是原来标准Softmax的一种近似就行了。我们来看负采样的,Word2Vec将优化目标变为了:
$$\mathop{\text{argmin}}_{\boldsymbol{u},\boldsymbol{v}} - \mathbb{E}_{w_j\sim \tilde{p}(w_j|w_i)}\log \sigma\Big(\langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle\Big) - \mathbb{E}_{w_j\sim \tilde{p}(w_j)}\log \Big[1-\sigma\Big(\langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle\Big)\Big]\tag{12}$$
这个式子看着有点眼花,总之它就是表达了“语料出现的Skip Gram视为正样本,随机采样的词作为负样本”的意思。
首先最明显的是,$(12)$式相比$(4),(5)$式,少引入了$\gamma$这个训练参数,或者就是说默认了$\gamma=0$,这允许吗?据说确实有人做过对比实验,结果显示训练出来的$\gamma$确实在0上下浮动,因此这个默认操作基本上是合理的。
其次,对于负样本,Word2Vec可不是“均匀地采样每一个词”,而是按照每个词本身的总词频来采样的。这样一来,$(10)$式就变成了
$$\tilde{p}(w_j|w_i)=\frac{p(1|w_i, w_j)}{p(0|w_i, w_j)}p(w_j)=e^{\langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle}\tilde{p}(w_j)\tag{13}$$
也就是说,最终的拟合效果是
$$\log \frac{\tilde{p}(w_j|w_i)}{\tilde{p}(w_j)} = \langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle\tag{14}$$
大家可以看到,左边就是两个词的互信息!本来我们的拟合目标是两个词的内积等于条件概率$\tilde{p}(w_j|w_i)$(的对数),现在经过负采样的Word2Vec,两个词的内积就是两个词的互信息。
现在大概就可以解释为什么Word2Vec的负采样会比Huffman Softmax效果要好些了。Huffman Softmax只是对Softmax做了近似,它本质上还是在拟合$\tilde{p}(w_j|w_i)$,而负采样技巧则是在拟合互信息$\log\frac{\tilde{p}(w_j|w_i)}{\tilde{p}(w_j)}$。我们之后,Word2Vec是靠词的共现来反应词义的,互信息比条件概率$\tilde{p}(w_j|w_i)$更能反映词与词之间“真正的”共现关系。换言之,$\tilde{p}(w_j|w_i)$反映的可能是“我认识周杰伦,周杰伦却不认识我”的关系,而互信息反映的是“你认识我,我也认识你”的关系,后者更能体现出语义关系。
我之前构造的另一个词向量模型《更别致的词向量模型(三):描述相关的模型》中也表明了,基于互信息出发构造的模型,能理论上解释“词类比(word analogy)”等很多实验结果,这也间接证实了,基于互信息的“Skip Gram + 负采样”组合,是Word2Vec的一个绝佳组合。所以,根本原因不是Huffman Softmax和负采样本身谁更优的问题,而是它们的优化目标就已经不同。
列车已到终点站 #
本文的目的是介绍NCE这种精致的参数估算技巧,指出它可以在难以为完成归一化时来估算概率分布中的参数,原则上这是一种通用的方法,而且很可能,在某些场景下它是唯一可能的方案。
最后我们以Word2Vec为具体例子进行简单的分析,谈及了使用NCE时的一些细节问题,并且顺带解释了负采样为什么好的这个问题~
相关链接:《词嵌入系列博客Part2:比较语言建模中近似softmax的几种方法》
转载到请包括本文地址:https://spaces.ac.cn/archives/5617
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Jun. 13, 2018). 《“噪声对比估计”杂谈:曲径通幽之妙 》[Blog post]. Retrieved from https://spaces.ac.cn/archives/5617
@online{kexuefm-5617,
title={“噪声对比估计”杂谈:曲径通幽之妙},
author={苏剑林},
year={2018},
month={Jun},
url={\url{https://spaces.ac.cn/archives/5617}},
}
November 8th, 2020
苏神你好,我这里不是很明白
“本来我们的拟合目标是两个词的内积等于条件概率$p\hat{~}(w_j |w_i)$(的对数)”
本来的拟合目标是$p(w_j | w_i) = \frac{e^{(u_i,v_j)}}{Z_i}$, 变换一下:
$log[p(w_j | w_i)Z_i] = (u_i,v_j)$, 可以看到,拟合的是$log[p(w_j | w_i)Z_i]$而不是$logp(w_j | w_i)$, 请问为什么这里的$Z_i$可以呢?
$Z_i$可以忽略呢?
实验观测得到最终对于任意的$i$,$Z_i$其实都差不多,所以$\langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle$只不过相当于$\log p(w_j|w_i)$的线性函数,所以可以这样描述。
其实也不需要什么实验,$\langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle$是一个二元函数,$\log[p(w_j | w_i)Z_i]=\log p(w_j | w_i) + \log Z_i$的$\log p(w_j | w_i)$是二元函数,$\log Z_i$只是一元函数,那么肯定是二元函数占主导,所以说$\langle \boldsymbol{u}_i, \boldsymbol{v}_j\rangle$拟合得失$\log p(w_j | w_i)$。
要注意我们要做的是直观理解,不是严密推导。
November 27th, 2020
苏神你好,问一下比较弱智的问题,请问一下(11)中$w_i$是中心词,$u_i$是不是中心词的词向量表示。
是的
December 26th, 2020
楼主,您好,这篇文章很经典,读了很多遍了,可是有些问题还是没想明白,希望您帮我释疑一下,虽然举了一个w2v的例子,但是我的疑问还是存在。非常感谢。
我们的目的是解决超大规模的多分类问题中的指数分布中的配分函数的问题。也可以认为是求解多分类问题中的参数θ,那现在就定一个标准。就用MLP来解决超大规模(假设10000分类)的图像多分类问题,效果好坏暂且不表,至少思路是可行的,然后用NCE的思路来求解网络中的θ参数,这是前提,我的问题是:
1. 既然是多分类问题(比如本例的10000分类),那么p(x)的输出应该是10000个类别的概率。根据NCE的思路求解出来的θ该怎么理解呢?或者说有了θ,该怎么来做多分类呢?
2. 如果根据NCE二分类的思路(公式5)来求解,前一部分很好理解,就是从我们的训练集采样,那么U(x)该怎么定义?
总结一下,1,根据NCE公式求出θ,怎么运用θ,怎么理解θ?2,本例中的多分类问题,U(x)该怎么定义?谢谢您
你可以理解为NCE是训练普通softmax的一种近似方式。
普通softmax就是内积然后softmax的,所以多分类的话,依然是特征向量跟所有类别向量做内积,得到logits后降序排列。
NCE是训练普通softmax的一种近似方式,这句话很好理解。p(x)=e^g(x)/Z应该是某个类别的概率。如果我们的θ训练好了,代入到公式中求概率,应该是有多少个类别就有多少个概率吧。从softmax到NCE的推理好理解。用NCE把θ训练出来后再推回到softmax好像就推不回去了呢
对于softmax来说,$\boldsymbol{x}$是类别,有多少个类别就有多少个$G(\boldsymbol{x};\boldsymbol{\theta})$,都算出来,然后算一下
$$p(\boldsymbol{x})=\frac{e^{G(\boldsymbol{x};\boldsymbol{\theta})}}{\sum_{\boldsymbol{x}} e^{G(\boldsymbol{x};\boldsymbol{\theta})}}$$
我的建议是:如果有什么看不明白的,多看几遍,10遍甚至100遍,必要时手抄几遍也行。你问出这个问题,就说明只是你觉得你懂了,实际上没弄明白,似懂非懂的状态。不是每一行似乎都能看明白了就是看懂了,能完全不看它然后把它默下来才是真的懂。
舒神,受教了。您太厉害了。
December 8th, 2021
公式(6)下写p~(x)和U(x)都跟参数θ,γ没关,但是为什么公式(10)p~(x)又写成了与参数θ,γ有关的形式?原谅我比较菜。
$\tilde{p}(\boldsymbol{x})$是跟参数无关啊,但是学好$p(1|\boldsymbol{x})$之后,可以用它来(近似)表达出$\tilde{p}(\boldsymbol{x})$。
February 8th, 2022
苏老师您好!看了您的讲解我对NCE理解更深,谢谢您。但我才疏学浅,有个问题想请教您,在一些对比学习论文当中,比如个体判别《Unsupervised Feature Learning via Non-Parametric Instance Discrimination》在使用NCE时并没有使用逻辑回归模型,而是在将softmax的Z看作常数,噪音分布为均匀分布,然后直接带入5式计算。这样的方法,如果按照10式的计算最终形式还是一种逻辑回归,当然,也是一种二分类模型。所以我的问题是,直接使用论文方法和您采用逻辑回归方法两者的关系是什么呢,之后我在看CPC论文的时候InfoNCE,作者是采用了NCE的一种变体,将softmax应用在少量的数据上,代码使用交叉熵计算,好像和二分类几乎无关了。
1、我有点看不懂,“在将softmax的Z看作常数,噪音分布为均匀分布,然后直接带入5式计算”这不就是逻辑回归的做法?为什么说它“并没有使用逻辑回归模型”?
2、InfoNCE是另一种利用变分法估计互信息的思路,跟这里的二分类确实不一样了,而且InfoNCE理论上效率更高。
是我理解错了,谢谢老师!
June 15th, 2022
第7个式子实在是难懂啊
可以说是拼凑出来的恒等变换而已。
April 12th, 2023
苏神好,有一个疑问恳请解答!
推导出NCE最终带有常数项 $\gamma-logU(x)$,把他与$logZ$归一化常数联系到了一起,我们有什么理由相信这个结果就是$Z$吗?
归一化因子是唯一的。
April 16th, 2023
nce这篇paper最开始的目标应该是做pdf密度估计的,那么式子(10)中我们得到了$\hat{p}(x)$数据pdf的一种估计形式,那么是不是我们得有$logU(x)$的解析形式才能得到这个估计的实际值呢?
$U(\boldsymbol{x})$本身就是假设为比较简单的、已知概率密度的分布。