0x02 Hierarchical Softmax

原因

无论是CBOW模型还是Skip-gram模型, 输出层都是预测出一个单词. 由于语料库中词语的数量巨大, 因此直接使用softmax输出预测结果是几乎不可行的. 所以需要使用Hierarchical Softmax方法对输出层结构进行优化.

霍夫曼树

Hierarchical Softmax结构使用霍夫曼树来进行优化, 有必要了解霍夫曼树的原理.

霍夫曼树的构建过程如下:

输入: $n$ 个结点(这里每个结点代表一个单词), 对应的权值向量为 $(w_1, w_2, \cdots, w_n)$
输出: 霍夫曼树
过程
- 将所有的 $n$ 个结点每一个看成一棵树, 共有 $n$ 棵树, 每棵树的结点都只有一个. 组成森林
- 在森林中选取根节点权值最小的两棵树进行合并, 得到一棵新的树. 原来的两棵树分别作为新书的左右子树, 新树的根节点权重为左右子树的根节点权重之和. 然后将原来的两棵树删除
- 重复上一步, 直到只有一棵树为止

霍夫曼树的特点: 权重高的叶子结点靠近根节点, 编码值较短; 权重低的远离根节点, 编码值较长. 因此整体的编码效率会提高.

霍夫曼树应用于word2vec

将霍夫曼树应用在投影层(Projection Layer)到输出层之间, 用霍夫曼树的结构代替了softmax层的映射. 避免了计算字典中所有单词的softmax概率, 在每个结点只需要判断左右两个行进方向, 沿着树一直走到样本单词对应的叶子结点, 整体结构示例如下:

这种霍夫曼树形状的神经网络结构为:

非叶子结点相当于一个神经元, 有自身的参数向量, 长度与设定的词嵌入向量的长度相同. 二分类决策输出0或1, 0表示选择左子树, 1表示选择右子树.
每个叶子结点代表语料库中的一个单词, 因此叶子结点的数量就是语料库词汇表中单词的数量.
每个结点(除了根节点, 包括非叶子结点和叶子结点)都可以用0和1唯一地编码
投影层到输出层不是一下完成的, 而是沿着树一步步完成的, 结果的路径对应着一个结点的编码序列

Hierarchical Softmax模型的梯度计算

引入符号

$w$ : 中心词
$x_w$ : 中心词对应的参数向量
$p^w$ : 从根节点出发到达词 $w$ 对应的叶子结点的路径
$l^w$ : 路径 $p^w$ 中包含的结点个数, 也即是层数
$p_1^w,p_2^w,\cdots,p_{l^w}^w$ : 路径 $p^w$ 中包含的结点
$d_2^w,\cdots,d_{l^w}^w$ : $d^w_j\in\{0,1\},\ j=1,2,\cdots,l^w$ , $d^w_j$ 表示路径 $p^w$ 中第 $j$ 个结点对应的编码(根节点无编码)
$\theta^w_1,\theta^w_2,\cdots,\theta^w_{l^{w-1}}$ : 路径 $p^w$ 中对应的非叶子结点的参数向量

对于每个非叶子结点, 判断下一步的行进方向. 由于每个非叶子结点都是一个神经元, 因此每个神经元都会进行感知机+sigmoid激活函数的操作, 即:

$P(+) = \sigma(x_w^T\theta) = \frac{1}{1+e^{-x_w^T\theta}}$

因此对应一个 $(w,\ \text{Context}(w))$ 样本, 对应的条件概率(似然函数)为:

$p(w|\text{Context}(w))=\prod\limits_{j=2}^{l^w}p(d^w_j|x_w,\theta^w_{j-1})$

从根节点到叶子结点经历了 $l^{w-1}$ 个结点. 而其中的每一项都是一个逻辑回归:

$p(d^w_j|x_w,\theta^w_{j-1}) = \begin{cases} \sigma(x_w^T\theta^w_{j-1}), \quad & d^w_j=0 \\ 1- \sigma(x_w^T\theta^w_{j-1}), \quad & d^w_j=1 \end{cases}$

用逻辑回归常用的形式, 写在一起有:

$p(d^w_j|x_w,\theta^w_{j-1})=[\sigma(x_w^T\theta^w_{j-1})]^{1 - d^w_j}[1-\sigma(x_w^T\theta^w_{j-1})]^{d^w_j}$

对于一个中心词 $w$ 求最大似然:

$\mathcal{L}=\log \prod_{j=2}^{l_w}P(d_j^w|x_w, \theta_{j-1}^w) = \sum\limits_{j=2}^{l_w} ((1-d_j^w) \log [\sigma(x_w^T\theta_{j-1}^w)] + d_j^w \log[1-\sigma(x_w^T\theta_{j-1}^w)])$

求最大似然, 对每个样本, 带入偏导数表达式求得函数在该参数上的增长梯度, 使用梯度上升法更新参数. 这里有两个参数:

每个结点的参数向量 $\theta^w_{j-1}$ , 求得偏导数为:
$\begin{aligned} \frac{\partial L}{\partial \theta_{j-1}^w} & = (1-d_j^w)\frac{(\sigma(x_w^T\theta_{j-1}^w)(1-\sigma(x_w^T\theta_{j-1}^w)}{\sigma(x_w^T\theta_{j-1}^w)}x_w - d_j^w \frac{(\sigma(x_w^T\theta_{j-1}^w)(1-\sigma(x_w^T\theta_{j-1}^w)}{1- \sigma(x_w^T\theta_{j-1}^w)}x_w \\ & = (1-d_j^w)(1-\sigma(x_w^T\theta_{j-1}^w))x_w - d_j^w\sigma(x_w^T\theta_{j-1}^w)x_w \\& = (1-d_j^w-\sigma(x_w^T\theta_{j-1}^w))x_w \end{aligned}$
单词 $w$ 对应的嵌入参数向量 $x_w$ , 这就是我们最终需要的单词对应的词向量. 求得到偏导数为
$\frac{\partial L}{\partial x_w} = \sum\limits_{j=2}^{l_w}(1-d_j^w-\sigma(x_w^T\theta_{j-1}^w))\theta_{j-1}^w$

关于Hierarchical Softmax结构还有几点需要注意的地方:

作为一个层级形式的神经网络结构, 与平常使用的结构(DNN)不同的地方是, 每一层神经元的输出结果都是一个标量, 用作选择下一步前进的方法, 而不是产生向量继续输入到这个结点的子树中去
因此每个结点的输入也就不是上层的结果, 而都是输入层单词 $w$ 对应的嵌入参数向量 $x_w$ , 整个路径中的所有神经元的输入都是这个向量

基于Hierarchical Softmax的CBOW模型

CBOW模型结合Hierarchical Softmax中需要注意的部分.

定义上下文的单侧窗口大小为 $c$ , 对于每个中心词, 其前面的 $c$ 个词和后面的 $c$ 个词都作为CBOW模型的输入.

从输入层到隐藏层的映射为对中心词 $w$ 周围的 $2c$ 个词的词向量求和并平均, 也可以只求和不平均, 并没有什么区别, 因此在最后梯度上升时的学习率与这里求平均可以结合在一起. 因此得到:

$x_w=\sum\limits_{i=1}^{2c}x_i$

然后通过梯度上升法来更新 $\theta^w_{j-1}$ 和 $x_w$ , 这里的 $x_w$ 向量是 $2c$ 个单词之和. 更新形式为:

$\theta_{j-1}^w = \theta_{j-1}^w + \eta (1-d_j^w-\sigma(x_w^T\theta_{j-1}^w))x_w$

$x_w= x_w +\eta \sum\limits_{j=2}^{l_w}(1-d_j^w-\sigma(x_w^T\theta_{j-1}^w))\theta_{j-1}^w \;(i =1,2..,2c)$

其中的 $\eta$ 就是学习率.

整体总结如下:

输入: 训练语料样本, 上下文单侧窗口长度 $c$ , 学习率 $\eta$
输出: 所有词 $w$ 的词向量 $x_w$ ; 非叶子结点参数 $\theta$
过程
- 基于语料建立霍夫曼树, 主要是根据词频
- 随机初始化所有词的词向量, 所有非叶子结点的参数向量
- 对于训练集中的每一个样本 $(w,\ \text{Context}(w))$ , 使用梯度上升法进行求解. 这里的 $\text{Context}(w)$ 不是一个单词, 而是中心词 $w$ 附近的 $2c$ 个上下文单词
  - 中间变量 $e=0$
  - $x_w=\sum\limits_{i=1}^{2c}x_i$
  - $\text{for } j =2 \text{ to } l^w$ , 计算:
    $f = \sigma(x_w^T\theta_{j-1}^w)$
    $g = (1-d_j^w-f)\eta$
    $e = e + g\theta_{j-1}^w$
    $\theta_{j-1}^w= \theta_{j-1}^w + gx_w$
  - 对于 $\text{Context}(w)$ 中包含的每一个词对应的词向量 $x_i,\quad i=1,2,\cdots,2c$ 进行相同的更新:
    $x_i = x_i + e$
- 梯度收敛则停止迭代, 否则继续循环上一步

基于Hierarchical Softmax的Skip-Gram模型

Skip-gram只是逆转了CBOW的因果关系而已, 对于CBOW, 我们对 $p(w|\text{Context}(w))$ 进行最大似然, 对于Skip-Gram就要对 $p(\text{Context}(w)|w)$ 进行最大似然了:

$p(\text{Context}(w)|w)=\prod\limits_{u\in{\text{Context(w)}}}p(u|w)$

即求中心词 $w$ 和上下中每一个词 $u$ 的条件概率. 这点与CBOW不同. CBOW是将上下文中所有的词加和起来与中心词产生条件概率, 相当于是两个词之间的关系. 而Skip-gram中是中心词与上下文中每一个词的关系, 因此计算要多一层对上下文词的循环.

另外由于CBOW的条件概率为 $p(w|\text{Context}(w))$ , 是上下文词预测中心词, 所以每一轮梯度上升中更新的是上下文中所有词的词向量. Skip-gram的条件概率为 $p(\text{Context}(w)|w)$ , 是中心词预测上下文词, 那么对于上下午中的所有词, 更新的都是中心词 $w$ 对应的词向量 $x_w$ . 这样在迭代的过程可能出现不均衡的现象.

从期望条件概率 $p(u|w)$ 的角度来讲, 上下文是相互的, 因此对于 $u$ 和 $w$ 两个词来说, 相互的条件概率是相同的, 因此就可以转换为对条件概率 $p(w|u)$ 期望最大. 这样我们就可以跟CBOW模型一样, 在一个中心词样本中, 对所有上下文词对应的向量进行更新了. 区别只在于多了一个对于上下文词的循环层.

因此整个过程总结如下:

输入: 训练语料样本, 上下文单侧窗口长度 $c$ , 学习率 $\eta$
输出: 所有词 $w$ 的词向量 $x_w$ ; 非叶子结点参数 $\theta$
过程:
- 基于语料建立霍夫曼树, 主要是根据词频
- 随机初始化所有词的词向量, 所有非叶子结点的参数向量
- 对于训练集中的每一个样本 $(w,\ \text{Context}(w))$ , 使用梯度上升法进行求解. 这里的 $\text{Context}(w)$ 不是一个单词, 而是中心词 $w$ 附近的 $2c$ 个上下文单词
  - $\text{for } i =1 \text{ to } 2c$ , 即对上下文中的每个词:
    中间变量 $e=0$
    $\text{for } j =2 \text{ to } l^w$ , 计算:
    $f = \sigma(x_w^T\theta_{j-1}^w)$
    $g = (1-d_j^w-f)\eta$
    $e = e + g\theta_{j-1}^w$
    $\theta_{j-1}^w= \theta_{j-1}^w + gx_w$
    $x_i = x_i + e$
- 梯度收敛则停止迭代, 否则继续循环上一步

参考

word2vec原理推导与代码分析

word2vec原理(二) 基于Hierarchical Softmax的模型

上一页0x01 word2vec算法原理下一页0x03 Negative Sampling

最后更新于4年前

这有帮助吗？