Problem：使用softmax时，目标类太多（数万级以上，典型NLP环境），训练时logits的计算量太大，导致使用极大似然估计的时间代价令人难以忍受；下面探讨如何有效解决这个问题（下文中特征向量有时简称样本）。
总体思路：当一个训练样本由)
构成时，其中
是特征向量（上下文），
是类（词汇）集合
的某子类。我们想学习一个兼容函数)
，它表示给定一个特征向量（上下文）
与类（中心词）
的兼容性（类的概率）。“全面”的训练方法如softmax和logistic回归要求对每个样本的每个类
计算。当
很大时，其运算代价将高到难以进行。“候选采样”训练方法涉及构造一个训练任务，其每个训练样本为，我们仅需要对小的候选类集
计算。典型地，候选集
是目标类 与随机选择样本的（其它）类
的并集:
。随机选择的
也许会或也许不会依赖于和（或）。训练算法以神经网络的形式进行，表示F(x,y)的层通过从损失函数后向传播误差训练。
几种候选采样方法：计算
)
时，如果是采样出的目标类
是多集（重复），则累加相同的每个目标类条件概率
假定我们有一个单label问题，每个训练样本)
由特征向量（上下文）和目标类（中心词）
构成；令)
表示给定特征向量，目标类是的概率；我们想训练函数产生softmax logits，也就是给定特征时类的相对对数概率：%20%5Cleftarrow%20%20log(P(y%7Cx))%20%2B%20K(x)%20%20%5C%5C)
，其中)
是不依赖于的任意函数，相对对数概率说明
与
方式训练时得到logits并不相同，相差一个样本的函数，但这并不影响最终的最大后验概率预测；
%EF%BC%8C%E6%88%91%E4%BB%AC%E5%B0%86%E9%9C%80%E8%A6%81%E5%AF%B9%E6%AF%8F%E4%B8%AAy%20%5Cin%20L%E8%AE%A1%E7%AE%97F(x_%7Bi%7D%2Cy)%7D)
，如果非常大，那么这个代价是非常昂贵的。在sampled softmax训练中，对每个训练样本，我们按照选择的采样函数)
采样类得到一个小集合
，每个类以概率)
独立地包含在中。
%3D%5Cprod_%7By%20%5Cin%20S%7DQ(y%7Cx_%7Bi%7D)%20%5Cprod_%7By%20%5Cin%20(L-S)%7D(1-Q(y%7Cx_%7Bi%7D))%20%20%5Ctag%7B1%7D)
我们创建候选集合，它包含目标类和采样类:
,训练的任务是确定给定集合，其中的哪个类是目标类。对于中的每个类，我们想计算后验概率，给定和，目标类的概率，称之为)
,应用贝叶斯公式
%3DP(t_%7Bi%7D%3Dy%2CC_%7Bi%7D%7Cx_%7Bi%7D)%2FP(C_%7Bi%7D%7Cx_%7Bi%7D)%0A%5C%5C%20%3D%20P(t_%7Bi%7D%3Dy%7Cx_%7Bi%7D)P(C_%7Bi%7D%7Ct_%7Bi%7D%3Dy%2Cx_%7Bi%7D)%2FP(C_%7Bi%7D%7Cx_%7Bi%7D)%0A%5C%5C%20%3D%20P(y%7Cx_%7Bi%7D)P(C_%7Bi%7D%7Ct_%7Bi%7D%3Dy%2Cx_%7Bi%7D)%2FP(C_%7Bi%7D%7Cx_%7Bi%7D)%20%20%20%20%5Ctag%7B2%7D)
现在计算)
，注意到为了使其发生，（也许会也许不会包含）必须包含的所有其他元素且一定不能包含任何不在中任何类，因此
%3DP(y%7Cx_%7Bi%7D)%0A%20%5Cprod_%7By%5E%7B%2B%7D%20%5Cin%20C_%7Bi%7D%20-%20%5Cleft%5C%7B%20y%20%5Cright%5C%7D%20%7DQ(y%5E%7B%2B%7D%7Cx_%7Bi%7D)%0A%5Cprod_%7By%5E%7B-%7D%20%5Cin%20(L-C_%7Bi%7D)%7D(1-q(y%5E%7B-%7D%7Cx_%7Bi%7D))%20%5C%20%5C%20%2F%20P(C_%7Bi%7D%7Cx_%7Bi%7D)%20%20%0A%5C%5C%20%3D%5Cfrac%7BP(y%7Cx_%7Bi%7D)%7D%7BQ(y%7Cx_%7Bi%7D)%7D%0A%5Cprod_%7By%5E%7B%2B%7D%20%5Cin%20C_%7Bi%7D%20%7DQ(y%5E%7B%2B%7D%7Cx_%7Bi%7D)%0A%5Cprod_%7By%5E%7B-%7D%20%5Cin%20(L-C_%7Bi%7D)%7D(1-q(y%5E%7B-%7D%7Cx_%7Bi%7D))%20%20%5C%20%5C%20%2F%20P(C_%7Bi%7D%7Cx_%7Bi%7D)%20%20%0A%5C%5C%20%3D%5Cfrac%7BP(y%7Cx_%7Bi%7D)%7D%7BQ(y%7Cx_%7Bi%7D)%7D%20%5C%20%5C%20%2FK(x_%7Bi%7D%2C%20C_%7Bi%7D)%20%5Ctag%7B3%7D)
这里%20)
是一个并不依赖于的函数。因此
)%3Dlog(P(y%7Cx_%7Bi%7D))-log(Q(y%7Cx_%7Bi%7D))%20%2B%20K%5E%7B%5Cprime%7D(x_%7Bi%7D%2CC_%7Bi%7D)%20%20%5Ctag%7B4%7D)
这是相对logits， 应该feed到
，因为我们试着训练来近似))
，我们采用神经网络输出减去))
，然后传递结果到softmax分类器（预测哪个候选是正确的），因此softmax分类器输入为
%3DF(x%2Cy)-log(Q(y%7Cx))%20%20%5Ctag%7B5%7D)
，后向传播此分类器的梯度训练
得到我们想要的。%20)
在计算softmax时可以消去，因此不必带入式中。
训练时，对于每个样本)
，按照采样目标类构成，只需计算这些类别对应的logits，即%5Cbig%5C%7D_%7By%20%5Cin%20C_%7Bi%7D%7D%20)
，然后以为目标类构造one-hot向量其长度为
,通过softmax和交叉熵计算得到损失函数)%7D%7B%5Csum_%7By%20%5Cin%20C_%7Bi%7D%7D%7Bexp(G(x_%7Bi%7D%2Cy))%7D%7D%3D-G(x_%7Bi%7D%2Ct_%7Bi%7D)%2Blog(%5Csum_%7By%20%5Cin%20C_%7Bi%7D%7D%7Bexp(G(x_%7Bi%7D%2Cy))%7D)%20%20%5C%5C)
；预测时，则对所有类计算并使用softmax；
%7D)
每个训练样本由一个特征向量（上下文）和一个小的Multiset目标类（中心词）构成，实践中或许是一个集合甚至是一个单类，但为了更一般化，这里使用multiset。以%3A%3DE(T(y)%7Cx))
表示给定样本的所有目标类中每个类的期望数，我们想训练函数近似对数期望数：
%20%5Cleftarrow%20log(P(y%7Cx))%20%5Ctag%7B1%7D)
对于每个样本，我们采样出目标类构成multiset。实践上，挑选一个集合或许是有意义的，但这里使用multiset以更具一般性。我们的采样算法也许会也许不会依赖，但不需要依赖。我们构造一个候选multiset，它包含目标类和采样的目标类的总和
。我们的训练任务是从采样的目标类中区分真正的目标类，对的每个元素，我们有一个正的训练元样本，对的每个元素，我们有一个负的训练元样本。
根据我们的采样算法，我们引入%3A%3D%20E(S(y)%7Cx)))
表示采样的目标类集合中的一个特定类的期望数。如果从不含有重复类，那么这是一个概率。那么给定，来自
对
的胜率对数（即logit）为：
%20%3D%20log%5Cfrac%7BP(y%7Cx)%7D%7BQ(y%7Cx)%7D%3Dlog(P(y%7Cx))-log(Q(y%7Cx))%20%5Ctag%7B2%7D)
其中第一项，是我们想训练估计的；在模型中有一个层表示F(x,y)，增加第二项)%20)
到其中(解析地计算)，然后将结果传给logistic回归损失函数(对于输入,如果
则label为正，如果
则label为负)；因此logisitc回归的输入为
%3D%20F(x%2Cy)-log(Q(y%7Cx))%20%20%5Ctag%7B3%7D)
这个logistic 回归的作用是对样本而言，要求神经网络训练能够使得真实目标类与采样目标类完全分开。
训练时，对每个样本)
，按照采样函数采样出目标类构造负样本)
；对每个样本需要计算
个交叉熵损失函数，即
个正损失得到))%7D)
，
个负损失得到))%7D)
，总损失函数为))%7D%20%2B%20%5Csum_%7By%20%5Cin%20S_%7Bi%7D%7D%7Blog(1%2Bexp(G(x_%7Bi%7D%2Cy)))%7D%20%5Cbig%5C%7D%20%5C%5C)
；预测时，对所有类使用并归一化；
负采样是NCE的一个简单变种，在训练过程中并不从网络输出中减去，即logit不是-log(Q(y%7Cx)))
而是，
%3DF(x%2Cy)%20%20%5C%5C)
这样我们回归的目标是)-log(Q(y%7Cx))%3Dlog(%5Cfrac%7BP(y%7Cx)%7D%7BQ(y%7Cx)%7D))
，可以看出这并不是样本的对数似然，而是对的点互信息
，因此负采样技术仅能应用与特定任务中，在该任务中训练的目标依赖于采样分布。典型的应用场景是词向量嵌入，此时%3DQ(y))
表示词汇的先验分布（实践中又采用了指数化并重新归一化分布），而%7D%7BQ(y%7Cx)%7D))
表达了上下文给中心词带来的信息增量（因为有了你，我现在增量了多少），优化信息增量比优化信息量（因为你，我现在存量多少）更具有意义；负采样方法不用来预测，因为学习的参数不是原来的极大样本集似然目标下的参数；
噪声对比估计、负采样方法是允许采样集包含真实目标类的，但是如果采样的softmax方法一样，采样的logistic是不允许采样集中包含真实目标类的，其它一如与NCE相同；因此我们的输入logit仍然是不变的，
%3D%20F(x%2Cy)-log(Q(y%7Cx))%20%20%5C%5C)
但是回归的目标是判断是来自还是
，那么就近似了%7D%7B1-P(y%7Cx)%7D))
，
)%3D-log(1%2Bexp(-F(x%2Cy))))
注意这里学习的的参数，跟原始softmax学习得到的参数是不一样的，预测时需使用上式进行归一化；
以上方法中若不依赖于，则称之为环境无关的采样，但是需要指出环境依赖的采样（Hard negative）对于训练模型是非常有用的，当然采样的代价也是巨大的；环境无关的采样，使得我们可以对所有训练样本使用通用的采样类，在batch训练环境下，我们可以更细化为每个batch使用相同的采样类。
