Hierarchical Softmax详解

一直对词向量不太懂,直到看了word2vec 中的数学原理详解后才恍然大悟,本文就对对其中的Hierarchical Softmax做一个总结。

Continuous Bag of Words

连续词袋模型假设基于某中心词在文本序列前后的背景词来生成该中心词。在文本序列“the”、 “man”、“loves”、“his”和“son”里,以“loves”作为中心词,且背景窗口大小为 2 时,连续词袋模型关心的是,给定背景词“the”、“man”、“his”和“son”生成中心词“loves”的条件概率,也就是

网络结构

$\mathcal C$ 表示语料,$\text { Context }$ 表示词 $w$ 的上下文,即 $w$ 周边词的集合。

image

上图给出了 CBOW 模型的网络结构,它包括三层: 输入层、投影层和输出层。

  • 输入层:$\text { Context } ( w )$ 中的2c个词的词向量 $V(\text {Context}(w)_1),V(\text {Context}(w)_2),\cdots,V(\text {Context}(w)_{2c}) \in R^m$,这里 $m$ 表示词向量的长度。
  • 投影层: 将输入层的 $2c$ 个向量做求和累加,即 $\mathbf{\mathbf{x}}_{w} = \sum_{i=1}^{2c}{V(\text {Context}(w)_i)} \in R^m$。
  • 输出层:输出层对应一棵二叉树,它是以语料中出现过的词当叶子结点,以各词在语料中出现的词频当权重构造出来的 Huffman 树,在这颗 Huffman 树中,叶子结点共 $N=|D|$ 个,分别对应词典 $D$ 中的词。

总结一下,对比神经概率语言模型的网络图和CBOW模型的结构图,可知道:

  • (从输入层到投影层的操作)前者是通过拼接,后者通过累加求和。比如输入的是三个四维词向量 $(1,2,3,4),(9,6,11,8),(5,10,7,12)$,那么我们 word2vec 映射后的词向量就是 $(15,18,21,24)$。
  • (隐藏层)前者有隐藏层,后者无隐藏层。
  • (输出层)前者是线性结构,后者是树形结构。

传统的神经网络语言模型时模型的大部分计算集中在神经网络的隐藏层和输出层之间的矩阵向量运算,以及输出层上的 softmax 归一化运算。而从上面的对比中可见,CBOW 模型对这些复杂度高的地方有针对性的进行了改变,首先去掉了隐藏层,其次输出层改用了 Huffman树。

其实霍夫曼树的所有内部节点就类似之前神经网络隐藏层的神经元,其中,根节点的词向量对应投影后的词向量,而所有叶子节点就类似于之前神经网络softmax输出层的神经元,叶子节点的个数就是词汇表的大小。在霍夫曼树中,隐藏层到输出层的softmax映射不是一下子完成的,而是沿着霍夫曼树一步步完成的,因此这种softmax取名为”Hierarchical softmax”。

为下面讨论方便,我们先引入若干相关记号。考虑 Huffman 树种的某个叶子结点,假设它对应词典$D$ 中的词 $w$,记

  • $p^w$:从根结点出发到达 $w$ 对应叶子结点的路径。
  • $l^w$: 路径 $p^w$ 中包含结点的个数。
  • $p_1^{w},p_2^{w},\cdots,p_{l^{w}}^{w}$路径 $p_1^w$ 中的 $l^w$ 个结点,其中 $p_1^{w}$ 表示根结点,$p_{l^{w}}^{w}$ 表示词 $w$ 对应的结点。
  • $d_2^{w},d_3^{w},\cdots,d_{l^{w}}^{w} \in \{0,1\}$:词 $w$ 的 Huffman编码,它由 $l^w - 1$ 位编码构成,$d_j^w$ 表示路径 $p^w$ 中第 $j$ 个结点对应的编码(根结点不对应编码)
  • $\theta_1^{w},\theta_2^{w},\cdots,\theta_{l^{w} - 1}^{w} \in R^m$:路径 $p^w$ 中非叶子结点对应的向量,$\theta_j^w$ 表示路径 $p^w$ 中第 $j$ 个非叶子结点对应的向量

下面以一个简单的例子来进一步说明一下:

句子为“我喜欢观看巴西足球世界杯”,分词后为“我 喜欢 观看 巴西 足球 世界杯”,假设根据语料库,分别统计分词后的各个词的频率,构建Huffman树如下图所示:

image

梯度计算

那么在 CBOW 模型的网络结构下,如何利用向量 $\mathbf{\mathbf{x}}_{w} \in R^m$ 以及 Huffman 树来定义条件概率函数 $P(w | \text {Context}(w))$ 呢?

考虑上面的”足球”的例子,从根节点出发到达”足球”这个叶子结点,中间共经历了 4 次分支(每条红色的边对应一次分支),而每一次分支都可视为进行一次二分类。

既然是从二分类的角度来考虑问题,那么对于每一个非叶子结点,就需要为其左右孩子结点指定一个类别,即哪个是正类(标签为 1),哪个是负类(标签为 0)。我们采用了二元逻辑回归的方法,即规定沿着左子树走,那么就是负类(霍夫曼树编码1),沿着右子树走,那么就是正类(霍夫曼树编码0)。判别正类和负类的方法是使用sigmoid函数,即:

其中 $\mathbf{\mathbf{x}}_{w}$ 是当前内部节点的词向量,而 $\theta$ 则是我们需要从训练样本求出的逻辑回归的模型参数,显然它与非叶子结点一一对应。被划分为左子树而成为负类的概率为 $P(−)=1−P(+)$。

将每个分支看做一次二分类,每一次分类就产生一个概率,将这些概率乘起来,就是我们所需要的 $P(w | \text {Context}(w))$:

其中

那么对于某一个目标输出词w,其最大似然为:

在 word2vec 中,由于使用的是随机梯度上升法,所以并没有把所有样本的似然乘起来得到真正的训练集最大似然,仅仅每次只用一个样本更新梯度,这样做的目的是减少梯度计算量。这样我们可以得到 $w$ 的对数似然函数L如下:

要得到模型中 $w$ 词向量和内部节点的模型参数 $\theta_{j-1}^w$, 我们使用梯度上升法即可。我们将中括号中的部分记作 $\mathcal {L}(w,j)$,求模型参数 $\theta_{j-1}^w$ 的梯度:

于是,$\theta_{j-1}^{w}$ 的更新公式可写为:

同样的方法,可以求出 $\mathbf{\mathbf{x}}_w$ 的梯度表达式如下:

我们的最终目的是要求词典 $D$ 中每个词的词向量,而这里的 $\mathbf{x}_w$ 表示的是 $\text { Context } ( w )$ 中各词词向量的累加。那么如何利用 $\frac{\partial \mathcal {L}(w,j)}{\partial \mathbf{x}_{w}}$ 来对 $V(\overline{w}),\overline{w} \in \text {Context}(w)$ 进行更新呢?word2vec 中的做法很简单,直接取

即把 $\sum_{j=2}^{l^{w}}{\frac{\partial \mathcal {L}(w,j)}{\partial \mathbf{x}_{w}}}$ 贡献到 $\text { Context } ( w )$ 中每一个词的词向量上,这点就很好理解了,既然 $\mathbf{x}_w$ 本身就是 $\text { Context }$ 中各词词向量的累加,求完梯度后当然要将其反向传播到每个分量上去。

下面以样本 $(\text {Context}(w),w)$ 为例,给出 CBOW 模型中采用随机梯度上升法更新各参数的伪代码:

image

Skip Gram

跳字模型假设基于某个词来生成它在文本序列周围的词。举个例子,假设文本序列是“the”、“man”、“loves”、“his”和“son”。以“loves”作为中心词,设背景窗口大小为 2。跳字模型所关心的是,给定中心词“loves”,生成与它距离不超过 2 个词的背景词“the”、“man”、“his”和“son”的条件概率,即

假设给定中心词的情况下,背景词的生成是相互独立的,那么上式可以改写成

网络结构

skip-gram 模型与 cbow 模型的推导过程大同小异,所以推导过程中的记号保持含义一致。

image

从图中可以看出 skip-gram 中共包含三部分:输入层、映射层、输出层。

  • 输入层:只含当前样本中心词的词向量,$v(w) \epsilon R^{m}$。
  • 映射层:其实在 Skip-Gram 中这个层是多余的,用公式表达为 $v(w)\rightarrow v(w)$。
  • 输出层:和 CBOW 类似,输出层也是一颗 haffman 树,如果计算梯度的时候需要做 Hierarchical Softmax。

梯度计算

对于skip-Gram模型而言,已知的是当前词语 $w$,需要对w的周围上下文预测 $P(\text {Context}(w)|w)$,假设 $\text { Context } ( w )$ 中各词语相对独立,即:

所以:

根据上式,可得最大似然函数为:

同样,为下面梯度锥导方便起见,将三重求和符号下花括号里的内容简记为$\mathcal { L } ( w , u , j )$,即

接下来利用梯度上升法对其进行优化。

首先考虑 $\mathcal { L } ( w, u , j )$ 对于 $\theta_{j-1}^u$ 的梯度计算。

于是,$\theta_{j-1}^u$ 的更新公式可写为:

接下来考虑 $\mathcal { L } ( w , u , j )$ 关于 $\mathbf { v } ( w )$ 的梯度。可以得到

于是 $\mathbf { v } ( w )$ 的更新公式可写为:

直接贴算法流程了:

$
UPDATE_SKIPGRAM_HIERARCHICAL\,SOFTMAX(W_{t})\\for \quad W \quad in \quad (W_{t-c}…,W_{t-1},W_{t+1}…,W_{t+c})\\\qquad neu1e=0\\\qquad for \quad i=0 \quad to \quad len(W_{t}.Code)-1\\\qquad\qquad f=\sigma(W\theta_{i})\\\qquad\qquad g=(1-code-f)\cdot LearningRate\\\qquad\qquad neu1e=neu1e+g\cdot\theta_{i}\\\qquad\qquad \theta_{i}=\theta_{i}+g\cdot W\\\qquad W=W+neule
$

参考

[1]. word2vec 中的数学原理详解
[2]. Word2Vec源码解析

持续技术分享,您的支持将鼓励我继续创作!