NLP教程(1)-词向量、SVD分解与Word2Vec

ShowMeAI研究中心

作者：韩信子@ShowMeAI

教程地址：http://www.showmeai.tech/tutorials/36

本文地址：http://www.showmeai.tech/article-detail/230

声明：版权所有，转载请联系平台与作者并注明出处

收藏ShowMeAI查看更多精彩内容

词向量、SVD分解与Word2vec

本系列为斯坦福CS224n《自然语言处理与深度学习(Natural Language Processing with Deep Learning)》的全套学习笔记，对应的课程视频可以在 这里 查看。

NLP介绍与词向量初步

ShowMeAI为CS224n课程的全部课件，做了中文翻译和注释，并制作成了GIF动图！点击 这里 查看“第1讲-NLP介绍与词向量初步”的课件注释与带学解读。更多资料获取方式见文末。

引言

CS224n是顶级院校斯坦福出品的深度学习与自然语言处理方向专业课程，核心内容覆盖RNN、LSTM、CNN、transformer、bert、问答、摘要、文本生成、语言模型、阅读理解等前沿内容。

本篇笔记对应斯坦福CS224n自然语言处理专项课程的第1个知识板块：NLP与词向量。首先介绍了自然语言处理(NLP)的概念及其面临的问题，进而介绍词向量和其构建方法（包括基于共现矩阵降维和Word2Vec）。

内容要点

• 自然语言处理/Natural Language Processing(NLP)
• 词向量/Word Vectors
• SVD矩阵分解
• Skip-gram
• 负例采样
• transformer
• CBOW
• 层次化softmax
• Word2Vec

1.自然语言处理介绍

1.1 自然语言处理的特别之处

人类的语言有什么特别之处？人类语言是一个专门用来表达意义的系统，语言文字是上层抽象表征，NLP与计算机视觉或任何其他机器学习任务都有很大的不同。

大多数单词只是一个语言学以外的符号：单词是一个映射到所指(signified 想法或事物)的能指(signifier)。例如，“rocket”一词指的是火箭的概念，因此可以引申为火箭的实例。当我们使用单词和字母来表达符号时，也会有一些例外，例如“whoompaa”的使用。

最重要的是，这些语言的符号可以被编码成几种形式：声音、手势、文字等等，然后通过连续的信号传输给大脑；大脑本身似乎也能以一种连续的方式对这些信号进行解码。人们在语言哲学和语言学方面做了大量的工作来概念化人类语言，并将词语与其参照、意义等区分开来。

❐ Natural language is a discrete离散的 / symbolic符号的 / categorical分类的 system.

1.2 自然语言处理任务

自然语言处理有不同层次的任务，从语言处理到语义解释再到语篇处理。自然语言处理的目标是通过设计算法使得计算机能够“理解”语言，从而能够执行某些特定的任务。不同的任务的难度是不一样的：

1) 简单任务

• 拼写检查 Spell Checking
• 关键词检索 Keyword Search
• 同义词查找 Finding Synonyms

2) 中级任务

• 解析来自网站、文档等的信息

3) 复杂任务

• 机器翻译 Machine Translation
• 语义分析 Semantic Analysis
• 指代消解 Coreference
• 问答系统 Question Answering

1.3 如何表征词汇

在所有的NLP任务中，第一个也是可以说是最重要的共同点是我们如何将单词表示为任何模型的输入。在这里我们不会讨论早期的自然语言处理工作是将单词视为原子符号 atomic symbols。

为了让大多数的自然语言处理任务能有更好的表现，我们首先需要了解单词之间的相似和不同。有了词向量，我们可以很容易地将其编码到向量本身中。

（本部分内容也可以参考ShowMeAI的对吴恩达老师课程的总结文章深度学习教程 | 自然语言处理与词嵌入）

2.词向量

使用词向量编码单词， $N$ 维空间足够我们编码语言的所有语义，每一维度都会编码一些我们使用语言传递的信息。

简单的one-hot向量无法给出单词间的相似性，我们需要将维度 $\left | V \right |$ 减少至一个低纬度的子空间，来获得稠密的词向量，获得词之间的关系。

3.基于SVD降维的词向量

（关于降维算法可以阅读ShowMeAI的机器学习教程文章图解机器学习 | 降维算法详解，也可以通过ShowMeAI的机器学习实战文章机器学习实战 | 机器学习特征工程最全解读关于降维的python应用方法）

基于词共现矩阵与SVD分解是构建词嵌入(即词向量)的一种方法。

• 我们首先遍历一个很大的数据集和统计词的共现计数矩阵 $X$
• 然后对矩阵 $X$ 进行SVD分解得到 $USV^T$
• 再然后我们使用 $U$ 的行来作为字典中所有词的词向量

接下来我们讨论一下矩阵 $X$ 的几种选择。

3.1 词-文档矩阵

最初的解决方案是基于词-文档共现矩阵完成的。我们猜想相关连的单词在同一个文档中会经常出现：

• 例如，“banks”，“bonds”，“stocks”，“moneys”等等，出现在一起的概率会比较高
• 但是，“banks”，“octopus”，“banana”，“hockey”不大可能会连续地出现

我们根据这个情况来建立一个Word-Document矩阵， $X$ 是按照以下方式构建：遍历数亿的文档和当词 $i$ 出现在文档 $j$ ，我们对 $X_{ij}$ 加一。

这显然是一个很大的矩阵 $\mathbb{R}^{ \left | V \right | \times M}$ ，它的规模是和文档数量 $M$ 成正比关系。因此我们可以尝试更好的方法。

3.2 基于滑窗的词共现矩阵

全文档统计是一件非常耗时耗力的事情，我们可以进行调整对一个文本窗内的数据进行统计，计算每个单词在特定大小的窗口中出现的次数，得到共现矩阵 $X$ 。

下面为一个简单示例，我们基于滑窗（前后长度为1）对文本进行共现矩阵的构建。

• I enjoy flying.
• I like NLP.
• I like deep learning.

基于滑窗的词共现矩阵

❐ 使用单词共现矩阵：

生成维度为 $\left | V \right |\times \left | V \right |$ 的共现矩阵 $X$ 在 $X$ 上应用SVD从而得到 $X = USV^T$ 选择 $U$ 前 $k$ 行得到 $k$ 维的词向量 $\frac{\sum_{i=1}^{k} \sigma_i}{\sum_{i=1}^{ \left | V \right |} \sigma_i}$表示第一个 $k$ 维包含的方差量

3.3 应用SVD对共现矩阵降维

• 我们对矩阵 $X$ 使用SVD，观察奇异值(矩阵 $S$ 上对角线上元素)，根据方差百分比截断，留下前 $k$ 个元素：

• 然后取子矩阵 $U_{1: \left | V \right |, 1:k}$ 作为词嵌入矩阵。这就给出了词汇表中每个词的 $k$ 维表示。

对矩阵 $X$ 使用SVD：

对矩阵 X 使用SVD

通过选择前 $k$ 个奇异向量来降低维度：

通过选择前 k 个奇异向量来降低维度

前面提到的方法给我们提供了足够的词向量来编码语义和句法(part of speech)信息，但也带来了一些问题：

• 矩阵的维度会经常发生改变(经常增加新的单词和语料库的大小会改变)
• 矩阵会非常的稀疏，因为很多词不会共现
• 矩阵维度一般会非常高 $\approx 10^6 \times 10^6$
• 需要在 $X$ 上加入一些技巧处理来解决词频的极剧的不平衡

❐ 基于SVD的方法的计算复杂度很高( $m \times n$ 矩阵的计算成本是 $O({mn}^2)$ )，并且很难合并新单词或文档。

对上述讨论中存在的问题存在以下的解决方法：

• 忽略功能词，例如“the”，“he”，“has”等等
• 使用ramp window，即根据文档中单词之间的距离对共现计数进行加权
• 使用皮尔逊相关系数并将负计数设置为 $0$ ，而不是只使用原始计数

❐ 基于计数的方法可以有效地利用统计量，但下述基于迭代的方式可以在控制复杂度的情况下有效地在大语料库上构建词向量。

4.迭代优化算法 - Word2Vec

（本部分内容也可以参考ShowMeAI的对吴恩达老师课程的总结文章 深度学习教程 | 自然语言处理与词嵌入）

Word2Vec是一个迭代模型，该模型能够根据文本进行迭代学习，并最终能够对给定上下文的单词的概率对词向量进行编码呈现，而不是计算和存储一些大型数据集(可能是数十亿个句子)的全局信息。

这个想法是设计一个模型，该模型的参数就是词向量。然后根据一个目标函数训练模型，在每次模型的迭代计算误差，基于优化算法调整模型参数（词向量），减小损失函数，从而最终学习到词向量。

大家知道在神经网络中对应的思路叫“反向传播”，模型和任务越简单，训练它的速度就越快。

❐ 基于迭代的方法一次捕获一个单词的共现情况，而不是像SVD方法那样直接捕获所有的共现计数。

已经很多研究者按照这个思路测试了不同的方法。Collobert et al., 2011 设计的模型首先将每个单词转换为向量。对每个特定的任务(命名实体识别、词性标注等等)，他们不仅训练模型的参数，同时也训练单词向量，计算出了非常好的词向量的同时取得了很好的性能。

一个非常有效的方法是Word2Vec。Word2Vec是google开源的软件包，包含以下核心内容：

• 两个算法：continuous bag-of-words(CBOW)和skip-gram

- **CBOW**是根据中心词周围的上下文单词来预测该词的词向量
- **skip-gram**则相反，是根据中心词预测周围上下文的词的概率分布。

• 两个训练方法：negative sampling和hierarchical softmax

- **Negative sampling**通过抽取负样本来定义目标
- **hierarchical softmax**通过使用一个有效的树结构来计算所有词的概率来定义目标

❐ Word2Vec依赖于语言学中一个非常重要的假设「分布相似性」，即相似的词有相似的上下文。

4.1 语言模型

我们先来了解一下语言模型。从一个例子开始：

我爱学习自然语言处理技术

一个好的语言模型会给这个句子很高的概率，因为在句法和语义上这是一个完全有效的句子。相似地，句子 自然学习爱处理语言我技术 会得到一个很低的概率，因为这是一个无意义的句子。

在数学上，我们可以称为对给定 $n$ 个词的序列的概率是：

在一元语言模型方法(Unigram model)中，我们假设单词的出现是完全独立的，从而分解概率

严谨一点说，上述假设是不合理的，因为下一个单词是高度依赖于前面的单词序列的。如果使用上述的语言模型，可能会让一个无意义的句子具有很高的概率。所以我们让序列的概率取决于序列中的单词和其旁边的单词的成对概率。我们称之为bigram模型：

确实，只关心邻近单词还是有点简单，大家考虑连续的n个词共现会得到n-gram。但即使使用bigram都可以带来相对unigram显著的提升。考虑在词-词共现矩阵中，共现窗口为 $1$ ，我们基本上能得到这样的成对的概率。但是，这又需要计算和存储大量数据集的全局信息。

既然我们已经理解了如何考虑具有概率的单词序列，那么让我们观察一些能够学习这些概率的示例模型。

4.2 CBOW连续词袋模型

这一方法是把 {"我","爱","学习","自然语言处理"，"技术"} 作为上下文，希望从这些词中能够预测或者生成中心词 学习。这样的模型我们称之为continuous bag-of-words(CBOW)模型。

❐ CBOW是从上下文中预测中心词的方法，在这个模型中的每个单词，我们希望学习两个向量

$v$ (输入向量，即上下文词) $u$ (输出向量，即中心词)

模型输入是one-hot形式的词向量表示。输入的one-hot向量或者上下文我们用 $x^{(c)}$ 表示，输出用 $y^{(c)}$ 表示。在CBOW模型中，因为我们只有一个输出，因此我们把 $y$ 称为是已知中心词的的one-hot向量。

下面我们定义模型的未知参数。我们创建两个矩阵， $\mathcal{V}\in \mathbb{R}^{n\times \left | V \right |}$ 和 $\mathcal{U}\in \mathbb{R}^{ \left | V \right |\times n}$ 。其中：

• $n$ 是嵌入空间的任意维度大小
• $\mathcal{V}$ 是输入词矩阵，使得当其为模型的输入时， $\mathcal{V}$ 的第 $i$ 列是词 $w_i$ 的 $n$ 维嵌入向量，定义这个 $n \times 1$ 的向量为 $v_i$
• 相似地， $\mathcal{U}$ 是输出词矩阵。当其为模型的输入时， $\mathcal{U}$ 的第j行是词 $w_{j}$ 的 $n$ 维嵌入向量。我们定义 $\mathcal{U}$ 的这行为 $u_j$
• 注意实际上对每个词 $w_i$ 我们需要学习两个词向量(即输入词向量 $v_i$ 和输出词向量 $u_i$ )。

❐ 首先我们对CBOW模型作出以下定义：

$w_i$ ：词汇表 $V$ 中的单词 $i$ $\mathcal{V}\in \mathbb{R}^{n\times \left | V \right |}$ ：输入词矩阵 $v_i$ ： $\mathcal{V}$ 的第 $i$ 列，单词 $w_i$ 的输入向量表示 $\mathcal{U}\in \mathbb{R}^{ \left | V \right |\times n}$ ：输出词矩阵 $u_i$ ： $\mathcal{U}$ 的第 $i$ 行，单词 $w_i$ 的输出向量表示

我们将这个模型分解为以下步骤：

• ① 我们为大小为 $m$ 的输入上下文词汇，生成one-hot词向量 $(x^{(c-m)}, \cdots ,x^{(c-1)},x^{(c+1)}, \cdots ,x^{(c+m)}\in \mathbb{R}^{ \left | V \right |})$
• ② 我们基于上述one-hot输入计算得到嵌入词向量 $(v_{c-m}=\mathcal{V}x^{(c-m)},v_{c-m+1}=\mathcal{V}x^{(c-m+1)},\cdots ,v_{c+m}=\mathcal{V}x^{(c+m)}\in \mathbb{R}^{n})$ 。
• ③ 对上述的词向量求平均值 $\widehat{v}=\frac{v_{c-m}+v_{c-m+1}+ \cdots +v_{c+m}}{2m}\in \mathbb{R}^{n}$ 。
• ④ 计算分数向量 $z = \mathcal{U}\widehat{v}\in \mathbb{R}^{ \left | V \right |}$ 。相似的词对向量的点积值大，这会令相似的词更为靠近，从而获得更高的分数。
• ⑤ 将分数通过softmax转换为概率 $\widehat{y}=softmax(z)\in \mathbb{R}^{ \left | V \right |}$ 。
• ⑥ 我们希望生成的概率 $\widehat{y} \in \mathbb{R}^{ \left | V \right |}$ 与实际的概率 $y \in \mathbb{R}^{ \left | V \right |}$ （实际是one-hot表示）越接近越好（我们后续会构建交叉熵损失函数并对其进行迭代优化）。

❐ 这里softmax是一个常用的函数。它将一个向量转换为另外一个向量，其中转换后的向量的第 $i$ 个元素是 $\frac{e^{\widehat{y}_i}}{\sum_{k=1}^{ \left | V \right |}e^{\widehat{y}_k}}$ 。

因为该函数是一个指数函数，所以值一定为正数。通过除以 $\sum_{k=1}^{ \left | V \right |}e^{\widehat{y}_k}$ 来归一化向量(使得 $\sum_{k=1}^{ \left | V \right |}\widehat{y}_k=1$ )得到概率。

下图是CBOW模型的计算图示：

CBOW模型的计算图示

如果有 $\mathcal{V}$ 和 $\mathcal{U}$ ，我们知道这个模型是如何工作的，那我们如何更新参数，学习这两个矩阵呢？和所有的机器学习任务相似，我们会构建目标函数，这里我们会使用交叉熵 $H(\widehat{y}, y)$ 来构建损失函数，它也是信息论里提的度量两个概率分布的距离的方法。

（关于交叉熵可以参考ShowMeAI的图解AI数学基础教程中文章图解AI数学基础 | 信息论）

在离散情况下，使用交叉熵可以直观地得出损失函数的公式

上面的公式中， $y$ 是one-hot向量。因此上面的损失函数可以简化为：

$c$ 是正确词的one-hot向量的索引。如果我们精准地预测 $\widehat{y}_{c}=1$ ，可以计算此时 $H(\widehat{y}, y)=-1\,log(1)=0$ 。因此，对于完全准确的预测，我们不会面临任何惩罚或者损失。

我们考虑一个相反的情况，预测非常差并且标准答案 $\widehat{y}_{c}=0.01$ 。进行相似的计算可以得到损失函数值 $H(\widehat{y}, y)=-1\,log(0.01)=4.605$ ，这表示目前损失较大，和标准答案差距较大。

从上面的例子可以看出，对于概率分布，交叉熵为我们提供了一个很好的距离度量。因此我们的优化目标函数公式为：

我们使用SGD（随机梯度下降）来更新所有相关的词向量 $u_{c}$ 和 $v_j$ 。

（关于SGD等优化算法可以参考ShowMeAI的对吴恩达老师课程的总结文章深度学习教程 | 神经网络优化算法）

❐ 当 $\widehat{y} = y$ 时， $\widehat{y} \mapsto H(\widehat{y}, y)$ 为最小值。如果我们找到一个 $\widehat{y}$ 使得 $H(\widehat{y}, y)$ 接近最小值，那么 $\widehat{y} \approx y$ 。这意味着我们的模型非常善于根据上下文预测中心词！

❐ 为了学习向量(矩阵 $U$ 和 $V$ )，CBOW定义了一个损失函数，衡量它在预测中心词方面的表现。然后，我们通过更新矩阵 $U$ 和 $V$ 随机梯度下降来优化损失函数。

❐ SGD对一个窗口计算梯度和更新参数： $\mathcal{U}_{new} \leftarrow \mathcal{U}_{old} -\alpha \nabla_{\mathcal{U}} J$ $\mathcal{V}_{old} \leftarrow \mathcal{V}_{old}-\alpha \nabla_{\mathcal{V}} J$

4.3 Skip-Gram模型

Skip-Gram模型与CBOW大体相同，但模型对于输入输出 $x$ 和 $y$ 进行了交换，即CBOW中的 $x$ 现在是 $y$ ， $y$ 现在是 $x$ 。输入的one-hot向量(中心词)我们表示为 $x$ ，输出向量为 $y^{(j)}$ 。我们定义的 $\mathcal{V}$ 和 $\mathcal{U}$ 是和CBOW一样的。

❐ Skip-Gram模型：在给定中心词的情况下预测周围的上下文词。

下面我们来具体拆解一下Skip-Gram模型，首先我们定义一些符号标记

• $w_i$ ：词汇表 $V$ 中的单词 $i$
• $\mathcal{V}\in \mathbb{R}^{n\times \left | V \right |}$ ：输入词矩阵
• $v_i$ ： $\mathcal{V}$ 的第 $i$ 列，单词 $w_i$ 的输入向量表示
• $\mathcal{U}\in \mathbb{R}^{ \left | V \right |\times n}$ ：输出词矩阵
• $u_i$ ： $\mathcal{U}$ 的第 $i$ 行，单词 $w_i$ 的输出向量表示

Skip-Gram的工作方式可以拆解为以下步骤：

• ① 生成中心词的one-hot向量 $x\in \mathbb{R}^{ \left | V \right |}$
• ② 我们对中心词计算得到词嵌入向量 $v_{c}=\mathcal{V}x\in \mathbb{R}^{ \left | V \right |}$
• ③ 生成分数向量 $z = \mathcal{U}v_{c}$
• ④ 将分数向量转化为概率， $\widehat{y}=softmax(z)$ 注意 $\widehat{y}_{c-m},\cdots,\widehat{y}_{c-1},\widehat{y}_{c+1},\cdots,\widehat{y}_{c+m}$ 是每个上下文词出现的概率
• ⑤ 我们希望我们生成的概率向量匹配真实概率 $y^{(c-m)}, \cdots ,y^{(c-1)},y^{(c+1)}, \cdots ,y^{(c+m)}$ ，one-hot向量是实际的输出

和CBOW模型一样，我们需要生成一个目标函数来评估这个模型。与CBOW模型的一个主要的不同是我们引用了一个朴素的贝叶斯假设来拆分概率。这是一个很强(朴素)的条件独立假设。换而言之，给定中心词，所有输出的词是完全独立的(即公式1至2行)

通过这个目标函数（损失函数），我们可以计算出与未知参数相关的梯度，并且在每次迭代中通过SGD来更新它们。

注意：

• 其中 $H(\widehat{y},y_{c-m+j})$ 是向量 $\widehat{y}$ 的概率和one-hot向量 $y_{c-m+j}$ 之间的交叉熵。

❐ 只有一个概率向量 $\widehat{y}$ 是被计算的。Skip-Gram对每个上下文单词一视同仁：该模型计算每个单词在上下文中出现的概率，而与它到中心单词的距离无关。

下图为Skip-Gram模型的计算图示：

Skip-Gram模型的计算图示

4.4 负例采样

我们再回到需要优化的目标函数上，我们发现在词表很大的情况下，对 $\left | V \right |$ 的求和计算量是非常大的。任何的更新或者对目标函数的评估都要花费 $O( \left | V \right |)$ 的时间复杂度。一个简单的想法是不去直接计算，而是去求近似值。

❐ 因为softmax标准化要对对所有分数求和，CBOW和Skip Gram的损失函数J计算起来很昂贵！

在每一个训练的时间步，我们不去遍历整个词汇表，而仅仅是抽取一些负样例。我们对噪声分布 $P_n(w)$ “抽样”，这个概率是和词频的排序相匹配的。

Mikolov在论文《Distributed Representations of Words and Phrases and their Compositionality》中提出了负采样。虽然负采样是基于Skip-Gram模型，但实际上是对一个不同的目标函数进行优化。

考虑一组词对 $(w,c)$ ，这组词对是训练集中出现过的中心词和上下文词吗？我们通过 $P(D=1\mid w,c)$ 表示 $(w,c)$ 在语料库出现过， $P(D=0\mid w,c)$ 表示 $(w,c)$ 在语料库中没有出现过。

这是一个二分类问题，我们基于sigmoid函数建模：

❐ sigmoid函数是softmax的二分类版本，可用于建立概率模型： $\sigma(x)=\frac{1}{1+e^{-x}}$

sigmoid函数

现在，我们建立一个新的目标函数，如果中心词和上下文词确实在语料库中，就最大化概率 $P(D=1\mid w,c)$ ，如果中心词和上下文词确实不在语料库中，就最大化概率 $P(D=0\mid w,c)$ 。

（这就是逻辑回归对于二分类的处理思路，相关内容可以参考ShowMeAI的机器学习教程文章图解机器学习 | 逻辑回归算法详解）

我们对这两个概率采用一个简单的极大似然估计的方法(这里我们把 $\theta$ 作为模型的参数，在我们的例子是 $\mathcal{V}$ 和 $\mathcal{U}$ )

这里最大化似然函数等同于最小化负对数似然：

注意 $\widetilde{D}$ 是“假的”或者“负的”语料。例如我们有句子类似 自然学习爱处理语言我技术，这种无意义的句子出现时会得到一个很低的概率。我们可以从语料库中随机抽样词汇构建负样例 $\widetilde{D}$ 。

对于Skip-Gram模型，我们对给定中心词 $c$ 来观察的上下文单词 $c-m+j$ 的新目标函数为

对CBOW模型，我们对给定上下文向量 $\widehat{v}=\frac{v_{c-m}+v_{c-m+1}+ \cdots +v_{c+m}}{2m}$ 来观察中心词 $u_{c}$ 的新的目标函数为：

在上面的公式中， $\{\widetilde{u}_{k}\mid k=1, \cdots ,K\}$ 是从 $P_{n}(w)$ 中抽样的词汇。关于计算选择某个词作为负样本的概率，可以使用随机选择。但论文作者给出了如下效果更好的公式：

公式中， $f(w_i)$ 代表语料库中单词 $w_i$ 出现的频率。上述公式更加平滑，能够增加低频词的选取可能。

4.5 层次化Softmax

Mikolov 在论文《Distributed Representations of Words and Phrases and their Compositionality》中提出了 hierarchical softmax（层次化softmax），相比普通的softmax这是一种更有效的替代方法。在实际中，hierarchical softmax 对低频词往往表现得更好，负采样对高频词和较低维度向量表现得更好。

❐ Hierarchical softmax 使用一个二叉树来表示词表中的所有词。树中的每个叶结点都是一个单词，而且只有一条路径从根结点到叶结点。在这个模型中，没有词的输出表示。相反，图的每个节点(根节点和叶结点除外)与模型要学习的向量相关联。单词作为输出单词的概率定义为从根随机游走到单词所对应的叶的概率。计算成本变为 $O(log ( \left | V \right |))$ 而不是 $O( \left | V \right |)$ 。

在这个模型中，给定一个向量 $w_i$ 的下的单词 $w$ 的概率 $p(w\mid w_i)$ ，等于从根结点开始到对应w的叶结点结束的随机漫步概率。这个方法最大的优势是计算概率的时间复杂度仅仅是 $O(log( \left | V \right |))$ ，对应着路径的长度。

❐ 下图是 Hierarchical softmax 的二叉树示意图：

Hierarchical Softmax 二叉树示意图

让我们引入一些概念。令 $L(w)$ 为从根结点到叶结点 $w$ 的路径中节点数目。例如，上图中的 $L(w_2)$ 为3。我们定义 $n(w,i)$ 为与向量 $v_{n(w,i)}$ 相关的路径上第 $i$ 个结点。因此 $n(w,1)$ 是根结点，而 $n(w,L(w))$ 是 $w$ 的父节点。现在对每个内部节点 $n$ ，我们任意选取一个它的子节点，定义为 $ch(n)$ (一般是左节点)。然后，我们可以计算概率为

其中

这个公式看起来非常复杂，我们来展开讲解一下。

• 首先，我们将根据从根节点 $(n(w,1))$ 到叶节点 $(w)$ 的路径的形状（左右分支）来计算相乘的项。如果我们假设 $ch(n)$ 一直都是 $n$ 的左节点，然后当路径往左时 $[n(w,j+1)=ch(n(w,j))]$ 的值返回1，往右则返回0。
• 此外， $[n(w,j+1)=ch(n(w,j))]$ 提供了归一化的作用。在节点 $n$ 处，如果我们将去往左和右节点的概率相加，对于 $v_{n}^{T}v_{w_i}$ 的任何值则可以检查， $\sigma(v_{n}^{T} v_{w_i})+\sigma(-v_{n}^{T} v_{w_i})=1$ 。归一化也保证了 $\sum_{w=1}^{ \left | V \right |}P(w\mid w_i)=1$ ，和普通的softmax是一样的。
• 最后我们计算点积来比较输入向量 $v_{w_i}$ 对每个内部节点向量 $v_{n(w,j)}^{T}$ 的相似度。下面我们给出一个例子。以上图中的 $w_2$ 为例，从根节点要经过两次左边的边和一次右边的边才到达 $w_2$ ，因此

我们训练模型的目标是最小化负的对数似然 $-log\,P(w\mid w_i)$ 。不是更新每个词的输出向量，而是更新更新二叉树中从根结点到叶结点的路径上的节点的向量。

该方法的速度由构建二叉树的方式确定，并将词分配给叶节点。Mikolov在论文《Distributed Representations of Words and Phrases and their Compositionality》中使用的是哈夫曼树，在树中分配高频词到较短的路径。

5.基于python gensim工具库构建词向量

在python中可以很简单地基于Gensim工具库构建和使用词向量，提供了most_similar、doesnt_match等应用API。我们可以对most_similar进行封装，输出三元组的类比结果，代码如下

model = KeyedVectors.load_word2vec_format(word2vec_glove_file)
model.most_similar('banana')
def analogy(x1, x2, y1):
    result = model.most_similar(positive=[y1, x2], negative=[x1])
    return result[0][0]
analogy('japan', 'japanese', 'australia')
model.doesnt_match("breakfast cereal dinner lunch".split())

6.拓展阅读

Word2Vec Tutorial - The Skip-Gram Model

6.1 任务示例

我们将训练一个带有单个隐藏层的简单神经网络来执行某个任务，但是我们实际上并没有将这个神经网络用于我们训练它的任务。相反，目标实际上只是学习隐藏层的权重，这实际上是我们试图学习的“单词向量”。这一技巧也在无监督的特征学习常用。训练一个auto-encoder从而在隐藏层中压缩输入向量并在输出层将隐藏层向量解压缩得到输入向量。训练完成后，去除输出层，只是用隐藏层。

下图是从源文本中抽取样本的过程

从源文本中抽取样本的过程

下图是网络架构图

网络架构图

如果两个不同的单词具有非常相似的“上下文”(即它们周围可能出现的单词是相似的)，那么我们的模型需要为这两个单词输出非常相似的结果。网络为这两个单词输出类似的上下文预测的一种方式是判断单词向量是否相似。因此，如果两个单词具有相似的上下文，那么我们的网络就会为这两个单词学习相似的单词向量！

• Efficient Estimation of Word Representations in Vector Space(original word2vec paper)
• Distributed Representations of Words and Phrases and their Compositionality (negative sampling paper)

7.参考资料

• 本教程的在线阅读版本
• 《斯坦福CS224n深度学习与自然语言处理》课程学习指南
• 《斯坦福CS224n深度学习与自然语言处理》课程大作业解析
• 【双语字幕视频】斯坦福CS224n | 深度学习与自然语言处理(2019·全20讲)
• Stanford官网 | CS224n: Natural Language Processing with Deep Learning

NLP系列教程文章

• NLP教程(1)- 词向量、SVD分解与Word2vec
• NLP教程(2)- GloVe及词向量的训练与评估
• NLP教程(3)- 神经网络与反向传播
• NLP教程(4)- 句法分析与依存解析
• NLP教程(5)- 语言模型、RNN、GRU与LSTM
• NLP教程(6)- 神经机器翻译、seq2seq与注意力机制
• NLP教程(7)- 问答系统
• NLP教程(8)- NLP中的卷积神经网络
• NLP教程(9)- 句法分析与树形递归神经网络

斯坦福 CS224n 课程带学详解

• 斯坦福NLP课程 | 第1讲 - NLP介绍与词向量初步
• 斯坦福NLP课程 | 第2讲 - 词向量进阶
• 斯坦福NLP课程 | 第3讲 - 神经网络知识回顾
• 斯坦福NLP课程 | 第4讲 - 神经网络反向传播与计算图
• 斯坦福NLP课程 | 第5讲 - 句法分析与依存解析
• 斯坦福NLP课程 | 第6讲 - 循环神经网络与语言模型
• 斯坦福NLP课程 | 第7讲 - 梯度消失问题与RNN变种
• 斯坦福NLP课程 | 第8讲 - 机器翻译、seq2seq与注意力机制
• 斯坦福NLP课程 | 第9讲 - cs224n课程大项目实用技巧与经验
• 斯坦福NLP课程 | 第10讲 - NLP中的问答系统
• 斯坦福NLP课程 | 第11讲 - NLP中的卷积神经网络
• 斯坦福NLP课程 | 第12讲 - 子词模型
• 斯坦福NLP课程 | 第13讲 - 基于上下文的表征与NLP预训练模型
• 斯坦福NLP课程 | 第14讲 - Transformers自注意力与生成模型
• 斯坦福NLP课程 | 第15讲 - NLP文本生成任务
• 斯坦福NLP课程 | 第16讲 - 指代消解问题与神经网络方法
• 斯坦福NLP课程 | 第17讲 - 多任务学习(以问答系统为例)
• 斯坦福NLP课程 | 第18讲 - 句法分析与树形递归神经网络
• 斯坦福NLP课程 | 第19讲 - AI安全偏见与公平
• 斯坦福NLP课程 | 第20讲 - NLP与深度学习的未来