神经网络中的负采样

对于绝大多数的有监督学习，神经网络的训练过程其实就是不断地调整网络权重的过程。最常用的方法就是back-propagation。然而，对于庞大的神经网络而言，反向更新权重并不是一件容易的事情，这个时候我们就需要用到负采样（negative sampling）的技术。在这篇博客，我将简单地介绍一下负采样的作用以及两种比较著名的负采样方法。

为什么需要负采样

当前对于绝大多数的神经网络而言，更新参数使用的都是反向传播（back propagation）的方式。这意味着，对于那些结果与标签值的不一致的节点，都需要做反向传播，更新权重。字面说可能很难理解，这里我使用Skip-Gram来做讲解，通过计算来说明负采样的必要性。

Skip-Gram的输出和输出都是one-hot编码的向量，假设我们的词典的size是10000，即输入的向量是10000维的向量，然后嵌入成400维的向量，这样隐层就有400个节点，输出层也是一个10000维的向量。我们重点关注隐层-输出层这里的权重，这里总共有$400 * 10000 = 4,000,000$个权重。也就是说，如果我们不做任何改进的话，每一次的训练都需要更新$4,000,000$个权重。显然，这样大量的计算会极大地拖慢训练的速度。

为了提升训练的速度，减少更新权重的数量，我们就需要对节点进行负采样。首先来了解两个概念postive word和negative word。positive word指的是在输出向量中期待为1的那个节点，negative word指的是在输出向量中期待为0的节点。在Skip-Gram中，输出向量一般只有一个位置为1，其余的9999个位置都为0。负采样的目的就是在negative word中，找出一部分节点进行权重的更新，而不需要全部都更新。比如我们找5个negative word节点，最后，我们更新的节点就是1个positive word + 5个negative word节点，总共是6个节点。在这种情况下，需要更新的权重数量是$6 * 400 = 2400$，相比起前面计算的$4,000,000$，是不是少了很多！

负采样的方式

知道了为什么要做负采样之后，我们就要考虑如何去做好这个采样。一般来说采样讲求随机性，尽可能公平地选择每一个节点。同时我们还必须兼顾效率，采样的计算复杂度也是非常重要的。

Unigram Table

核心思想：某个词被选中的概率和它出现的次数有关。

这个方法非常好理解，非常符合直观逻辑。如果一个词出现的越多，我们就认为它被选择的概率会比较大。在word2vec论文中，提出了一个非常神奇的采样公式：
$$
P(w_i) = \frac{f(w_i)^{3/4}}{\sum^n_{j=0}(f(w_j)^{3/4})}
$$

Alias Table

在介绍Alias Table前，先来看看Unigram Table有什么不足之处。每次取样的时候，先产生一个$[0,1]$的随机数$c$，然后顺序遍历Unigram Table，找到第一个大于$c$的数所对应的下标，即是采样的类别。这种方法的复杂度是$O(N)$，如果使用二分搜索，复杂度降至$O(log N)$。

Alias Table就是为了继续降低复杂度而引进的方法，它的单次采样复杂度为$O(1)$。接下来我们来看一下它是怎么做的。

假设我们有4个类别的数据，其概率分布为：$\frac{1}{2},\frac{1}{3}, \frac{1}{12}, \frac{1}{12}$。
每个类别的概率乘上类别数，使得总和为4，结果为：$2, \frac{4}{3},\frac{1}{3},\frac{1}{3}$。以1为分界，划分为两类：一类是大于1的，另一类是小于1的。
通过拼凑，使得每一个类别都为1，且每一个类别只能有两种类别，所以我们需要从最少的开始补，保证较少的通过一次拼凑就能满足。
1. 将第1列拿$\frac{2}{3}$给第3列，结果为：$\frac{4}{3}, \frac{4}{3},1,\frac{1}{3}$
2. 将第1列拿$\frac{2}{3}$给第4列，结果为：$\frac{2}{3}, \frac{4}{3},1,1$
3. 将第2列拿$\frac{1}{3}$给第1列，结果为：$1,1,1,1$
4. 完成拼凑
最后，就得到了两个数组：Probability Table和Alias Table
- Probability Table：指的是某一类落在原类型的概率，即自己类别组成1的部分。以上述的为例，应该为： $[\frac{2}{3}, 1, \frac{1}{3}, \frac{1}{3}]$
- Alias Table：用于指明某一类别的其他组成类别。前面提到，每一个类别只能有两种类别，一个是自己，另一个则是通过拼凑补过来的类别。所以这个表就是用来指明拼凑过来的那个类别。以上述的为例，应该为：$[2, 0, 1, 1]$
每一次采样，首先随机选取某一个类别$k$，然后随机产生一个$[0,1]$的随机数$c$，首先比较$Prob[k]$和$c$的大小，如果$Prob[k] > c$，那么说明原有类别所占比例比较大，采样$k$，否则，说明拼凑的类别所占比例大，采样$Alias[k]$。可以看出，采样过程中全部都是下标访问，复杂度是$O(1)$，因此这个方法应用很广。