Word2Vec

论文 | word2vec Parameter Learning Explained

链接 | arxiv.org/abs/1411.27…

作者 | Xin Rong

发布时间 | 2014

1、引言

Mikolov 等人的 word2vec 模型和应用引来极大关注，并且该类单词的向量表示在各种NLP任务中十分有用且被证明具有语义含义，本篇笔记主要目的是：

解释两种Word2Vec模型的参数更新方程：

• 连续词袋模型（continuous bag-of-word CBOW）
• 跳字模型（skip-gram SG）

介绍两种高性能的优化方式：

• 层序softmax（hierarchical softmax）
• 负采样（negative sampling）

2、模型原理讲解

跳字模型

在skip-gram模型中，我们用一个词来预测它在文本序列周围的词，定义中，当前选中的词被称为中心词，邻近的词被称为背景词。例如，给定文本序列”小”,”明”,”爱”,”中”,”国” (白板推导串戏)。设置背景窗口大小为2，那么跳字模型所做的，就是在给定”爱”,生成它邻近词”小”,”明”,”中”,”国”的概率。（此时”爱”是中心词，”小”,”明”,”中”,”国”是背景词），即：

$$P(小,明,中,国|爱)$$

假定在给定中心词的条件下，背景词的生成是独立的，那么上式可改写成

$$P(小|爱)\cdot P(明|爱)\cdot P(中|爱)\cdot P(国|爱)$$

接下来我们给定一些模型定义：

• 假设词典大小为|V|。

• 词典中的每个词与0 到 |V| – 1的整数一一对应，当成词典索引，构建词典索引集$V=\{0,1,\dots ,|V|-1\}$。每一个词对应的那个整数称为该词的索引。

给定一个长度为 $T$ 的文本序列, $t$ 时刻的词为 $w^{(t)}$。当背景窗口大小为 m 时，跳字模型需要最大化给定任一中心词生成背景词的概率：

$$\prod _{t=1}^T\prod _{-m\le j\le m,j\ne 0}P\left(w^{(t+j)}\mid w^{(t)}\right)$$

上式得最大似然估计与最小化以下损失函数等价

$$-\frac{1}{T}\sum _{t=1}^T\sum _{-m\le j\le m,j\ne 0}\log P\left(w^{(t+j)}\mid w^{(t)}\right)$$

我们可以用$v$代表中心词的词向量，$u$ 代表背景词的词向量。换言之，对于词典中一个索引为 $i$ 的词，它本身有两个向量 $v_i$ 和 $u_i$ 进行表示，在计算的过程中，根据其所处的角色不同，选择不同的词向量。词典中所有词的这两种向量正是跳字模型所需要学习的参数。为了将模型参数植入损失函数，我们需要使用模型参数表达损失函数中的中心词生成背景词的概率。假设中心词的概率是相互独立的。给定中心词 $w_c$ 在词典中的索引为 $c$，背景词 $w_0$ 在词典中的索引为 $o$，损失函数中中心词生成背景词的概率可以使用 softmax 函数进行定义：

$$P\left(w_o\mid w_c\right)=\frac{\exp \left({\mathbf{u}}_o^T{\mathbf{v}}_c\right)}{{\sum }_{i\in V}\exp \left({\mathbf{u}}_i^T{\mathbf{v}}_c\right)}$$

当序列长度 $T$ 较大时，我们通常随机采样一个较小的子序列来计算损失函数并使用 SGD 优化该损失函数。通过求导，我们可以计算出上式生成概率的对数关于中心词向量 ${\mathbf{v}}_c$ 的梯度为:

$$\begin{array}{rl}\frac{\partial \log P\left(w_o\mid w_c\right)}{\partial {\mathbf{v}}_c}& =\frac{\partial }{\partial {\mathbf{v}}_c}\log \frac{\exp \left({\mathbf{u}}_o^T{\mathbf{v}}_c\right)}{{\sum }_{i=1}^{|V|}\exp \left({\mathbf{u}}_i^T{\mathbf{v}}_c\right)}\\ & =\underset{1}{\frac{\partial }{\partial {\mathbf{v}}_c}\log \exp \left({\mathbf{u}}_o^T{\mathbf{v}}_c\right)}-\underset{2}{\frac{\partial }{\partial {\mathbf{v}}_c}\log \sum _{i=1}^{|V|}\exp \left({\mathbf{u}}_i^T{\mathbf{v}}_c\right)}\end{array}$$

第一部分推导

$$\frac{\partial }{\partial {\mathbf{v}}_c}\log \exp \left({\mathbf{u}}_o^T{\mathbf{v}}_c\right)=\frac{\partial }{\partial {\mathbf{v}}_c}{\mathbf{u}}_o^T{\mathbf{v}}_c={\mathbf{u}}_{\mathbf{o}}$$

第二部分推导

$$\begin{array}{rl}\frac{\partial }{\partial {\mathbf{v}}_c}\log \sum _{i=1}^{|V|}\exp \left({\mathbf{u}}_i^T{\mathbf{v}}_c\right)& =\frac{1}{{\sum }_{i=1}^{|V|}\exp \left({\mathbf{u}}_i^T{\mathbf{v}}_c\right)}\cdot \frac{\partial }{\partial {\mathbf{v}}_c}\sum _{x=1}^{|V|}\exp \left({\mathbf{u}}_x^T{\mathbf{v}}_c\right)\\ & =\frac{1}{A}\cdot \sum _{x=1}^{|V|}\frac{\partial }{\partial {\mathbf{v}}_c}\exp \left({\mathbf{u}}_x^T{\mathbf{v}}_c\right)\\ & =\frac{1}{A}\cdot \sum _{x=1}^{|V|}\exp \left({\mathbf{u}}_x^T{\mathbf{v}}_c\right)\frac{\partial }{\partial {\mathbf{v}}_c}{\mathbf{u}}_x^T{\mathbf{v}}_c\\ & =\frac{1}{{\sum }_{i=1}^{|V|}\exp \left({\mathbf{u}}_i^T{\mathbf{v}}_c\right)}\sum _{x=1}^{|V|}\exp \left({\mathbf{u}}_x^T{\mathbf{v}}_c\right){\mathbf{u}}_x\\ & =\sum _{x=1}^{|V|}\frac{\exp \left({\mathbf{u}}_x^T{\mathbf{v}}_c\right)}{{\sum }_{i=1}^{|V|}\exp \left({\mathbf{u}}_i^T{\mathbf{v}}_c\right)}{\mathbf{u}}_x\\ & =\sum _{x=1}^{|V|}P\left(w_x\mid w_c\right){\mathbf{u}}_x\end{array}$$

综上所述

$$\frac{\partial \log P\left(w_o\mid w_c\right)}{\partial {\mathbf{v}}_c}={\mathbf{u}}_o-\sum _{j\in V}P\left(w_j\mid w_c\right){\mathbf{u}}_j$$

通过上面计算得到梯度后，我们可以使用随机梯度下降来不断迭代模型参数 ${\mathbf{v}}_c$ 。其它模型参数 ${\mathbf{u}}_o$ 的迭代方式同理可得。最终，对于词典中任一索引为 $i$ 的词，我们均得到该词作为中心词和背景词的两组词向量 ${\mathbf{v}}_i$ 和 ${\mathbf{u}}_i$

时间复杂度Q = C × ( D + D × log 2 ( V )), 其中C为window size，V为词典大小，D为每个词设置的维度。通过反向传播优化，每次更新当前的词向量。可见，相比NNLM，word2vec主要是减少了hidden layer，并且引入log-linear classifier(也就是hierarchical softmax)，大大减少了训练的计算量。

连续词袋模型

连续词袋模型与跳字模型类似。与跳字模型最大的不同是，连续词袋模型是用一个中心词在文本序列周围的词来预测中心词。简单的说就是，跳字模型是用中心词预测周围的词；连续词袋模型是用周围的词预测中心词。例如，给定文本 “小”,”明”,”爱”,”中”,”国”，连续词袋模型所关心的是，邻近词 “小”,”明”,”中”,”国” 一起生成中心词 “爱” 的概率
连续词袋模型需要最大化由背景词生成任一中心词的概率:

$$\prod _{t=1}^{T}P\left(w^{(t)}\mid w^{(t-m)},\dots ,w^{(t-1)},w^{(t+1)},\dots ,w^{(t+m)}\right)$$

上式得最大似然估计与最小化以下损失函数等价

$$-\sum _{t=1}^T\log P\left(w^{(t)}\mid w^{(t-m)},\dots ,w^{(t-1)},w^{(t+1)},\dots ,w^{(t+m)}\right)$$

我们可以用 $\mathbf{v}$ 和 $\mathbf{u}$ 分别代表背景词和中心词的向量（注意符号和跳字模型相反，这能确保公式相似）。给定中心词 $w_c$ 在词典中的索引为 $c$ ，背景词 $w_{o_1},\dots ,w_{o_{2m}}$ 在词典中的索引为 $o_1,\dots ,o_{2m}$ ，损失函数中的背景词生成中心词的概率可以使用 softmax 函数定义为

$$P\left(w_c\mid w_{o_1},\dots ,w_{o_{2m}}\right)=\frac{\exp \left[{\mathbf{u}}_c^T\left({\mathbf{v}}_{o_1}+\dots +{\mathbf{v}}_{o_{2m}}\right)/(2m)\right]}{{\sum }_{j\in V}\exp \left[{\mathbf{u}}_j^T\left({\mathbf{v}}_{o_1}+\dots +{\mathbf{v}}_{o_{2m}}\right)/(2m)\right]}$$

同样，当序列长度 $T$ 较大时，我们通常随机采样一个较小的子序列来计算损失函数，并使用随机梯度下降优化该损失函数，通过微分，我们可以计算出上式生成概率的对数关于任一背景词向量 ${\mathbf{v}}_{o_i}(i=1,\dots ,2m)$ 的梯度为:

$$\frac{\partial \log P\left(w_c\mid w_{o_1},\dots ,w_{o_{2m}}\right)}{\partial {\mathbf{v}}_{o_i}}=\frac{1}{2m}\left({\mathbf{u}}_c-\sum _{j\in V}\frac{\exp \left({\mathbf{u}}_j^T{\mathbf{v}}_c\right)}{{\sum }_{i\in V}\exp \left({\mathbf{u}}_i^T{\mathbf{v}}_c\right)}{\mathbf{u}}_j\right)$$

而上式与下式等价:

$$\frac{\partial \log P\left(w_c\mid w_{o_1},\dots ,w_{o_{2m}}\right)}{\partial {\mathbf{v}}_{o_i}}=\frac{1}{2m}\left({\mathbf{u}}_c-\sum _{j\in V}P\left(w_j\mid w_c\right){\mathbf{u}}_j\right)$$

3、优化方法

可以看到，无论是跳字模型还是连续词袋模型，每一步梯度计算的开销与词典 $V$ 的大小呈正相关。显然，当词典较大时，这种训练方法的计算开销会很大。所以使用上述训练方法在实际中是由难度的。我们可以使用近似的方法来计算这些梯度，从而减小计算开销。常用的近似训练法包括负采样和层序 softmax

负采样

其本质是反向传播训练时只更新一部分权重，降低计算量。

以跳字模型为例讨论负采样。词典 $V$ 的大小之所以会在目标函数中出现，是因为中心词 $w_c$ 生成背景词 $w_o$ 的概率 $P\left(w_o\mid w_c\right)$ 使用了 softmax，而 softmax 考虑到了背景词可能是词典中任意词，并体现在了 softmax 的分母上
我们不妨换个角度，假设中心词 $w_c$ 生成背景词 $w_o$ 由以下两个互相独立的联合事件组成来近似：

1. 中心词 $w_c$ 和背景词 $w_o$ 同时出现在该训练数据窗口
2. 中心词 $w_c$ 和噪声词不同时出现在该训练数据窗口
   • 中心词 $w_c$ 和第 1 个噪声词 $w_1$ 不同时出现在训练数据窗口 (噪声词 $w_1$ 按噪声词分布 $P(w)$ 随机生成)
   • …
   • 中心词 $w_c$ 和第 $K$ 个噪声词 $w_k$ 不同时出现在训练数据窗口（噪声词 $w_K$ 按噪声词分布 $P(w)$ 随机生成)

我们可以使用 $\sigma (x)=\frac{1}{1+\exp (-x)}$ 函数来表达中心词 $w_c$ 和背景词 $w_o$ 同时出现在训练数据窗口的概率:

$$P\left(D=1\mid w_o,w_c\right)=\sigma \left({\mathbf{u}}_o^T,{\mathbf{v}}_c\right)$$

那么，中心词 $w_c$ 生成背景词 $w_o$ 的对数概率可以近似为

$$\log P\left(w_o\mid w_c\right)=\log \left[P\left(D=1\mid w_o,w_c\right)\prod _{k=1,w_k\sim P(w)}^{K}P\left(D=0\mid w_k,w_c\right)\right]$$

假设噪声词 $w_k$ 在词典中的索引为 $i_k$ ， 上式可改写为

$$\log P\left(w_o\mid w_c\right)=\log \frac{1}{1+\exp \left(-{\mathbf{u}}_o^T{\mathbf{v}}_c\right)}+\sum _{k=1,w_k\sim P(w)}^K\log \left[1-\frac{1}{1+\exp \left(-{\mathbf{u}}_{i_k}^T{\mathbf{v}}_c\right)}\right]$$

因此，有关中心词 $w_c$ 生成背景词 $w_o$ 的损失函数是

$$-\log P\left(w_o\mid w_c\right)=-\log \frac{1}{1+\exp \left(-{\mathbf{u}}_o^T{\mathbf{v}}_c\right)}-\sum _{k=1,w_k\sim P(w)}^K\log \frac{1}{1+\exp \left({\mathbf{u}}_{i_k}^T{\mathbf{v}}_c\right)}$$

现在，训练中每一步的梯度计算开销不再与词典大小相关，而与 $K$ 线性相关。当 $K$ 取较小的常数时， 负采样的每一步梯度计算开销也较小。
同理，也可以对连续词袋模型进行负采样。有关背景词 $w^{(t-m)},\dots ,w^{(t-1)},w^{(t+1)},\dots ,w^{(t+m)}$
生成中心词 $w_c$ 的损失函数

$$-\log P\left(w^{(t)}\mid w^{(t-m)},\dots ,w^{(t-1)},w^{(t+1)},\dots ,w^{(t+m)}\right)$$

在负采样中可以近似为

$$-\log \frac{1}{1+\exp \left[-{\mathbf{u}}_c^T\left({\mathbf{v}}_{o_1}+\dots +{\mathbf{v}}_{o_{2m}}\right)/(2m)\right]}-\sum _{k=1,w_k\sim P(w)}^K\log \frac{1}{1+\exp [{\mathbf{u}}_{i_k}^T\left({\mathbf{v}}_{o_1}+\dots +{\mathbf{v}}_{o_{2m}}\right)/(2m)]}$$

层序 softmax

首先，不要被名字误解，我个人认为这个和softmax没任何关系。

层序 softmax 利用了二叉树。树的每个叶子节点代表着词典 $V$ 中的每个词。每个词 $w_i$ 对应的词向量为 $v_i$。我们以下图为例，来描述层序 softmax 的工作机制

设 $L(w)$ 为从二叉树根节点到代表词 $w$ 的叶子节点的路径上的节点数，并设 $n(w,i)$ 为该路径上第 $i$ 个节点，该节点的向量为 ${\mathbf{u}}_{n(w,j)}$ 。以上图为例， $L\left(w_3\right)=4$ 。那么，跳字模型和连续词袋模型所需要计算的任意词 $w_i$ 生成词 $w$ 的概率为:

$$P\left(w\mid w_i\right)=\prod _{j=1}^{L(w)-1}\sigma \left([n(w,j+1)=\mathrm{left}\mathrm{child}(n(w,j))]\cdot {\mathbf{u}}_{n(w,j)}^T{\mathbf{v}}_i\right)$$

其中，如果 $x$ 为真， $[x]=1$ ；反之 $[x]=-1$
由于 $\sigma (x)+\sigma (-x)=1，w_i$ 生成词典中任何词的概率之和为 1 :

$$\sum _{w=1}^{V}P\left(w\mid w_i\right)=1$$

上面公式可能比较抽象，下面举个具体的例子，计算 $w_i$ 生成 $w_3$ 的概率，由于在二叉树中由根到 $w_3$ 的路径需要向左、向右、再向左地遍历，所以得到

$$P\left(w_3\mid w_i\right)=\sigma \left({\mathbf{u}}_{n\left(w_3,1\right)}^T{\mathbf{v}}_i\right)\cdot \sigma \left(-{\mathbf{u}}_{n\left(w_3,2\right)}^T{\mathbf{v}}_i\right)\cdot \sigma \left({\mathbf{u}}_{n\left(w_3,3\right)}^T{\mathbf{v}}_i\right)$$

由此，我们就可以使用随机梯度下降在跳字模型和连续词袋模型中不断迭代计算词典中所有词向量 $\mathbf{v}$ 和 非叶子节点的向量 $\mathbf{u}$ 。每次迭代的计算开销由 $O(|V|)$ 降为二叉树的高度 $O(\log |V|)$，即为树的高度。
最后一个问题，层序 softmax 的二叉树是如何建立的?

这里的二叉树是Huffman 树，权重是语料库中 word 出现的频率。

简单说明下霍夫曼树的构建方法，计算出词典中所有词的词频作为节点的权重，首先将权重最小的两个节点合并，父节点的权重为两个叶子节点的值之和，之后再在剩下的节点(之前合并的两个节点不在这里考虑中，用他们合并的父节点代替)里选最小的两个重复以上操作，当直到只有一个节点停止迭代。

这样做的好处是，词频高的词会离根节点近，模型实际计算的时候大大减少运算量。

4、代码实现

基于Skip-gram的word2vec

仅乞丐版实现QWQ，理解思想最重要,想要一键体验可以点击这里哦

import paddle
import numpy as np
import paddle.optimizer as optimizer
import paddle.io as Data
import paddle.nn as nn

# 初始化简易句子
sentences = ["panda like one", "monkey hate three", "horse undrink milk", "He is tall and strong", 
             "She sings beautifully", "movie was thrilling", " weather is warm and sunny", "music is upbeat"]

sentence_list = " ".join(sentences).split() # ['jack', 'like', 'dog', 'jack', 'like', 'cat', 'animal',...]
vocab = list(set(sentence_list))
word2idx = {w:i for i, w in enumerate(vocab)}
vocab_size = len(vocab)
word2idx

# model parameters
C = 2 # window size
batch_size = 8
m = 2 # word embedding dim

skip_grams = []
for idx in range(C, len(sentence_list) - C):
    center = word2idx[sentence_list[idx]]
    context_idx = list(range(idx - C, idx)) + list(range(idx + 1, idx + C + 1))
    context = [word2idx[sentence_list[i]] for i in context_idx]

    for w in context:
        skip_grams.append([center, w])
len(skip_grams)

def make_data(skip_grams):
    input_data = []
    output_data = []
    for a, b in skip_grams:
        input_data.append(np.eye(vocab_size)[a])
        output_data.append(b)
        
    return input_data, output_data

input_data, output_data = make_data(skip_grams)
input_data, output_data = paddle.to_tensor(input_data), paddle.to_tensor(output_data)
# TensorDataset 可以用来对 tensor 进行打包，就好像 python 中的 zip 功能。该类通过每一个 tensor 的第一个维度进行索引。
dataset = Data.TensorDataset([input_data, output_data])
loader = Data.DataLoader(dataset, batch_size=batch_size, shuffle=True)

def createParameter(dim1, dim2):
    x = paddle.randn([dim1, dim2], dtype="float32")
    param = paddle.create_parameter(shape=x.shape,
    dtype=str(x.numpy().dtype),
    default_initializer=paddle.nn.initializer.Assign(x))
    param.stop_gradient = True
    return param

class Word2Vec(nn.Layer):
    
    def __init__(self) -> None:
        super(Word2Vec, self).__init__()
        self.W = createParameter(vocab_size, m)
        self.V = createParameter(m, vocab_size)

    def forward(self, X):
        # X : [batch_size, vocab_size]
        hidden = paddle.mm(X, self.W) # [batch_size, m]
        output = paddle.mm(hidden, self.V) # [batch_size, vocab_size]
        return output
    
# 定义损失函数和优化器
model = Word2Vec()
loss_fn = nn.CrossEntropyLoss()
optim = optimizer.Adam(parameters=model.parameters(), learning_rate=1e-3)

# 训练
for epoch in range(10000):
    for i, (batch_x, batch_y) in enumerate(loader):
        batch_x = batch_x
        batch_y = batch_y
        pred = model(batch_x)
        loss = loss_fn(pred, batch_y)

        if (epoch + 1) % 5000 == 0:
            print(epoch + 1, i, loss.item())

        optim.clear_grad()
        loss.backward()
        optim.step()
      
    
# 由于定义的tensor为二维，故可以展示最后的结果在图上
import matplotlib.pyplot as plt
for i, label in enumerate(vocab):
  W, WT = model.parameters()
  x,y = float(W[i][0]), float(W[i][1])
  plt.scatter(x, y)
  plt.annotate(label, xy=(x, y), xytext=(5, 2), textcoords='offset points', ha='right', va='bottom')
plt

参考资料

• Word2Vec – mathor (wmathor.com)

• 深入浅出Word2Vec原理解析 – 知乎 (zhihu.com)