自然语言处理 - 文本数值化 - Word Embedding - 层次Softmax 与负采样

基础知识

哈夫曼树
轮盘采样

简化方法

层次 Softmax (Hierarchical Softmax )
负采样 (Negative Sampling)

基础知识
- 哈夫曼树
  
  哈夫曼树是一颗二叉树，该树的带权路径长度最小，是最优二叉树。
  
  哈夫曼树的构建比较简单，如下：
  
  输入：权值为 $(w_1,w_2,...w_n)$ 的 n 个节点
  输出：对应的霍夫曼树
  1. 将 $(w_1,w_2,...w_n)$ 看做 n 棵单结点树；
  2. 在森林中选择 根节点 权值最小的两棵树合并成新树，这两颗树分别作为新树的左右子树。新树的根节点权重为左右子树的根节点权重之和。
  3. 将之前的根节点权值最小的两棵树从森林删除，并把新树加入森林。
  4. 重复步骤2）和3）直到森林里只有一棵树为止。
  1. 如果将二叉树的左路径标为 0，右路径标为 1，那么一个元素的从根节点开始，寻找该元素的路径就可以用0,1 表示，就构成了哈夫曼编码，如图：
    
    那么元素 1 的编码为：000
    元素 8 的编码为：1
- 轮盘采样
  
  轮盘中大小不同面积的扇形区域对应不同结果：
  
  所中奖金额的概率与其所占扇形面积大小对应。
简化方法

在语料库中，词量非常庞大，倘若有 10000 维，那么最终输出层要计算 10000 维的Softmax。为了简化计算，常用的方法有层次 Softmax 以及负采样。
- 层次 Softmax (Hierarchical Softmax )
  
  层次 Softmax 应用了哈夫曼树的思想，元素对应词，元素的权值对应词出现的频率，那么出现越频繁的词越接近哈夫曼树的根节点，其搜索的频率也越频繁。所以根据词频构建哈夫曼树。
  
  那么哈夫曼树中的 0,1 路径又是如何得到的呢？答案就是 Sigmoid 函数。
  
  $\sigma(x;θ)=\frac{1}{1+e^{-z}}， z=x^Tθ+b$
  
  Sigmoid 函数的取值范围为 (0, 1)，刚好可以用来进行 0,1 输出，哈夫曼树是二叉树，那么每次进行路径选择可视为一个二分类，那么就变成了多次二分类，称为层次 Softmax.
  
  对于当前词的上下文词，经过计算到投影层后，进入层次 Softmax。将上下文词向量的结果求和取平均，将结果推给 Sigmoid 函数。
  
  在最终输出层，便用到了词在哈夫曼树根节点走向目标叶子结点的搜索路径。对于每一次决策左右，都是由 Sigmoid 计算得到的，而 Sigmoid 计算的结果都可以视为概率，那么我们可以将路径的概率相乘，计算最大似然，得到损失函数：
  
  $L(x_i;θ) = \prod_{j=2}^{l_i} [\sigma(x_i;θ)] ^{1-y_j}[1-\sigma(x_i;θ)]^{y_j}$
  
  其中 $l_i$ 为该词的搜索路径。
  
  之后就可以像求解 Logistic 回归一样进行反向传播了。
- 负采样 (Negative Sampling)
  
  在层次 Softmax 中，如果要查询一个比较生僻的词，那么路径会非常长，搜索的深度也非常深。
  
  搜索深度非常深的原因是，语料库中的词多，如果有 10000 个不重复词，那么哈夫曼树的深度则为 10000，而我们想要搜索的只有一个或滑动窗口大小个词，所以我们要对不相关的词进行精简。
  
  精简的方法为负采样。
  
  负采样的思想用一句话来描述：将真实词看作正类，将非真实词看作负类，在负类中进行采样，获取一部分样本。那么由此，原本的 10000 分类或者 10000 规模的层次Softmax 变成了二分类。
  
  负采样的实现方法用到了**轮盘算法的思想，只不过将轮盘的原型展开，变为一条线。
  
  将非真实词的负样本空间看作一条长度为 1 的线段，各个词在线段中占有一段长度，其长度对应词的词频。而后随机产生一个 (0,1) 的数，这个数在哪个词线段的区间内，这个词就被加入到采样的样本中。
  ‘’
  假设随机产生一个数：0.66，066 ∈ (0.55, 0.95)，所以词 “中国” 被选出，以此类推，进行多次实验，最终得到一定数量的负样本，而后利用 Sigmoid 函数进行二分类。