自然语言处理与深度学习（1）

—— CS224n 2019年冬课程笔记

第一讲词向量（I）

关键词：Natural Language Processing, Word Vectors, Singular Value Decomposition (SVD), Skip-gram, Continuous Bag of Words (CBOW), Negative Sampling, Hierarchical Softmax, Word2Vec

本讲首先介绍自然语言护理与自然语言处理面对的问题，之后将讨论用以将词表示为向量的相关概念，最后，我们将讨论设计词向量的常见方法。

1 自然语言处理简介

我们首先讨论什么是自然语言处理。

1.1 自然语言处理有何特别之处？

人类（自然）语言有什么特别之处呢？人类语言是一个用于表达含义的体系，并不由任何一种特定的规则生成。因此，自然语言处理与其他机器学习任务（如视觉任务）很不相同。

大多数单词只是语言学之外实体的符号：一个词是可以映射到某一被表示的事物或想法的记号。

例如，“rocket”一词指的是火箭的概念，可以引申为火箭的一个实例。但当我们使用单词或者字母表达符号时，会有一些例外，例如“Whooompaa”。除此之外，语言符号可以用不同形式编码:声音、手势、字体等，这些符号通过连续的信号传递给大脑，而大脑本身也似乎以连续的方式编码。（语言哲学和语言学已经做了大量的工作来概念化人类语言，并将词语与其指称、意义等区分开来。）

1.2 自然语言处理任务举例

从语音处理到语义解释和语篇处理，自然语言处理的具有不同的任务层次。而自然语言处理的目标是设计一种能够让计算机“理解”自然语言从而能够执行某些任务的算法。按照任务的难度可以有下面几类：

简单级别

拼写检查 (Spell Checking)
关键词搜索 (Keyword Search)
寻找同义词 (Finding Synonyms)

中等级别

网站、文件等信息解析

困难级别

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

1.3 如何表示单词

自然语言处理最基本的问题是如何将单词表示为我们模型的输入。许多早期自然语言处理任务将单词视为原子符号。而为了更好地完成大多数自然语言处理任务，我们首先需要对单词之间的相似性和差异性有一些概念。利用距离测量如Jaccard, Cosine, Euclidean，词向量（word vectors）能够将单词与单词间的相似性和差异性编码。

2 词向量

英文中大约有 1,300 万单词，但是它们彼此之间是完全没有联系的吗？猫科动物和猫，旅馆和汽车旅馆？我认为并不。因此我们希望能够将单词编码为某个“词空间”中的点。这一点至关重要，其中最显而易见的一个原因是可能存在某个 $N$ 维空间（$N << 1,300 \text{万}$）足以编码我们所有的语义。每个维度都会编码我们表达的一些意义，例如，语义维可能会表明时态、单复数、性别等。

让我们来看看我们的第一个向量，也可以说是最简单的一个，one-hot vector：

我们将每一个单词表示为一个 $\mathbb{R}^{|V| \times 1}$ 维只有 1 位为 1，其余位均为 0 的向量。因此 $|V|$ 是我们词典的大小，该类型编码中的词向量表示如下：

$w^{\text {aardvark}}=\left[ \begin{array}{c}{1} \\ {0} \\ {0} \\ {\vdots} \\ {0}\end{array}\right], w^{a}=\left[ \begin{array}{c}{0} \\ {1} \\ {0} \\ {\vdots} \\ {0}\end{array}\right], w^{a t}=\left[ \begin{array}{c}{0} \\ {0} \\ {1} \\ {\vdots} \\ {0}\end{array}\right], \dots ,w^{z e b r a}=\left[ \begin{array}{c}{0} \\ {0} \\ {0} \\ {\vdots} \\ {1}\end{array}\right]$

我们将每个单词表示为一个完全独立的实体。但是正如我们前面讨论过的，这种词向量没有给我们任何关于相似的信息，例如：

$\left(w^{h o t e l}\right)^{T} w^{m o t e l}=\left(w^{h o t e l}\right)^{T} w^{c a t}=0$

因此也许我们可以试着把这个空间的大小从 $R | V |$ 缩小到更小的维度从而找到一个子空间来编码单词之间的关系。

3 奇异值分解方法（SVD Based Model）

对于这一类寻找词嵌入（word embeddings，也称作词向量的方法），我们首先在一个大数据集上遍历，以某种矩阵 $X$ 的形式计算词汇同时出现的次数，之后对矩阵 $X$ 进行奇异值分解得到 $USV^T$。然后我们就可以使用 $U$ 的每一行作为所有单词的词嵌入。接下来让我们讨论矩阵 $X$ 的一些选择。

3.0 奇异值分解（补充）

对奇异值分解较熟悉或者暂且不想探究过多可暂时跳过本小节。

1 特征值与特征向量

特征值与特征向量定义如下：

$A x=\lambda x$

其中，$A$ 是一个 $n \times n$ 的矩阵，$x$ 是一个 $n$ 维向量，则我们称满足上式的 $\lambda$ 是矩阵 $A$ 的一个特征值，而 $x$ 是矩阵 $A$ 的特征值 $\lambda$ 所对应的特征向量。

求出特征值和特征向量之后，我们可以对矩阵 $A$ 进行特征分解。如果我们求出了矩阵 $A$ 的 $n$ 个特征值 $\lambda_{1} \leq \lambda_{2} \leq \ldots \leq \lambda_{n}$，以及这 $n$ 个特征值所对应的特征向量 $\left\{\vec{u_{1}}, \vec{u_{2}}, \dots \vec{u_{n}}\right\}$，如果这 $n$ 个特征向量线性无关，那么矩阵 $A$ 就可以用下式的特征分解表示：

$A = USU^{-1}$

其中，$U$ 是这 $n$ 个特征向量所张成的 $n \times n$ 维矩阵，而 $S$ 为这 $n$ 个特征值为主对角线的 $n \times n $ 维矩阵。

$\begin{align}A U & = A\left(\vec{u}_{1}, \vec{u}_{2}, \ldots, \vec{u}_{n}\right) \\ & = \left(\lambda_{1} \vec{u}_{1}, \lambda_{2} \vec{u}_{2}, \dots, \lambda_{n} \vec{u}_{n}\right) \\ & = \left(\vec{u}_{1}, \vec{u}_{2}, \ldots, \vec{u}_{n}\right) \left[ \begin{array}{ccc}{\lambda_{1}} & {\cdots} & {0} \\ {\vdots} & {\ddots} & {\vdots} \\ {0} & {\cdots} & {\lambda_{n}}\end{array}\right] \\ & \Rightarrow A U=U S \Rightarrow A=U S U^{-1} \end{align}$

一般我们会将 $U$ 的这 $n$ 个特征向量标准化，即满足：$ \left|\vec{u_{i}}\right|_{2}=1$，或者说 $\vec{u_{i}}^{T} \vec{u_{i}}=1$ 。此时 $U$ 的 $n$ 个特征向量为标准正交基，满足 $U^{T} U=I$，即 $U^{T}=U^{-1}$。这样我们的特征分解表达式可以写成：

$A = USU^{T}$

注意到要进行特征分解，矩阵 $A$ 必须为方阵。那么如果 $A$ 不是方阵，该如何进行分解呢？这就要用到 SVD —— 奇异值分解。

2 奇异值分解

SVD 也是对矩阵进行分解，但是和特征分解不同，SVD 并不要求要分解的矩阵为方阵。假设我们的矩阵 $A$ 为一个 $m \times n$ 的矩阵，那么我们定义矩阵 $A$ 的 SVD 为：

$A=U S V^{T}$

其中，$U$ 是一个 $m \times m$ 的矩阵，$S$ 是一个 $m \times n$ 的矩阵，除了主对角线上的元素以外全为 0 ，主对角线上的每个元素都称为奇异值，$V$ 是一个 $n \times n $ 的矩阵。$U$ 和 $V$ 满足：$U^{T} U=I, V^{T} V=I$。

3.1 词-文档矩阵（Word-Document Matrix）

作为我们的第一次尝试，我们可以假设，相关的单词经常出现在相同的文档中。例如，”banks”, “bonds”, “stocks”, “money”等很可能一起出现，但是 “banks”, “octopus” (章鱼), “banana”, “hockey” 很大可能不会同时出现。我们利用这一事实可以构造词-文档矩阵 $X$：

循环十数亿的文章，单词 $i$ 每次出现在文章 $j$ 时，我们将 $X_{ij}$ 加 1 。

显然这是一个很大的矩阵 ($\mathbb{R}^{|V| \times M}$)，并且该矩阵与文章的数量 $M$ 成比例。因此，我们可以找到更好的方法。

3.2 窗口共现矩阵（Window based Co-occurrence Matrix）

在此方法中，我们计算每个单词在特定大小的窗口中出现的次数。以下面为例，假设语料库只包含三个句子，窗口大小为1：

I enjoy flying.
I like NLP
I like deep learning

那么我们得到的矩阵为：

$X=\begin{array}{@{}@{}@{}@{}@{}c@{}@{}} &I&like&enjoy&deep&learning&NLP&flying&. \\ \left.\begin{array} {c} I\\like\\enjoy\\deep\\learning\\NLP\\flying\\. \end{array}\right[ & \begin{array}{c} 0 \\ 2 \\ 1\\ 0 \\0 \\0 \\0 \\0 \end{array} & \begin{array}{c} 2 \\ 0 \\ 0 \\ 1 \\0 \\ 1 \\ 0\\ 0\end{array} & \begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\0 \\ 0 \\ 1\\ 0\end{array} & \begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \\1 \\ 0 \\ 0\\ 0\end{array} & \begin{array}{c} 0 \\ 0 \\ 0 \\ 1 \\0 \\ 0 \\ 0\\ 1\end{array} & \begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \\0 \\ 0 \\ 0\\ 1\end{array} & \begin{array}{c} 0 \\ 0 \\ 1 \\ 0 \\0 \\ 0 \\ 0\\ 1\end{array} & \begin{array}{c} 0 \\ 0 \\ 0 \\ 0 \\1 \\ 1 \\ 1\\ 0\end{array} & \left.\begin{array}{c} \\ \\ \\ \\ \\ \\ \\ \\\end{array}\right] \end{array}$

3.3 对共现矩阵进行奇异值分解

我们在矩阵 $X$ 上执行 SVD 得到 $USV^T$ ，选择 $U$ 的前 $k$ 列作为 $k$ 维词空间（降维）。

其中 $k$ 的选择方式如下：

$\frac{\sum_{i=1}^{k} \sigma_{i}}{\sum_{i=1}^{|V|} \sigma_{i}}$

满足某一设定的值。

之后，我们将矩阵 $U_{1 :|V|, 1: k}$ 作为我们的词嵌入矩阵。这将给每一个单词一个 $k$ 维的词向量表示。

这两种方法都给我们提供了足够的词向量来编码语义和句法信息（如词性分析），但却存在一些其他问题:

矩阵维度经常变动（新单词频繁加入时，语料库的大小会改变）。
矩阵非常稀疏（大多数单词不会同时出现）。
矩阵通常维度很高（$\approx 10^{6} \times 10^{6}$）。
训练成本高（执行 SVD）。
需要对矩阵 $X$ 进行一些处理来避免单词频率差异过大。

存在的一些解决方案有：

忽视一些功能性词，例如：”he”, “the”, “has” 等
应用一个不规则窗口 —— 根据文档中单词之间的距离来计算共现次数
使用Pearson相关系数并将原始计数设置为负数

但正如我们将在下一节中看到的，基于迭代的方法以一种优雅得多的方式解决了其中的许多问题。

4 基于迭代的方法（Iteration Based Methods）—— Word2vec

让我们尝试一种新的方法。相比于计算存储一个庞大数据集（可能有数十亿个句子）的整体信息，我们可以尝试创建一个模型，它能够一次学习一个迭代，并最终能够根据给定上下文得到一个单词的概率。

这种方法的思想是设计一个参数是词向量的模型，之后，按照一定的目标训练该模型。在每次迭代中，我们运行模型，评估错误，并通过惩罚导致错误的模型参数进行更新。这样我们就学习到了词向量。这个思想被称为反向传播（back-propagating），最早可以追溯到 1986 年。模型和任务越简单，训练速度越快。

一些尝试已经被测试过。 [Collobert et al., 2011] 设计了一些第一步是将词转化为向量的自然语言处理模型。对于每种特定的任务，例如命名实体识别（Named Entity Recognition），词性标注（Part-of-Speech tagging）等，他们除了训练模型的参数同时也训练词向量，显著提升了模型效果。

本节中，我们将会讲述一种更加简单，先进可行的方法 —— word2vec [Mikolov et al., 2013] 。Word2vec 是一个包含如下内容的包：

两个算法：continuous bag-of-words (CBOW) 和 skip-gram。CBOW 根据一系列词向量中的上下文来预测中心词。而 Skip-gram 刚好相反，根据一个中心词来预测上下文单词的分布。
两种训练方式：negative sampling 和 hierarchical softmax。

4.1 语言模型（Unigrams, Bigrams 等）

首先，我们需要创建一个为一系列单词分配概率的模型。以下面句子为例：

"The cat jumped over the puddle."

一个好的语言模型会给这个句子一个很高的概率，因为不管是在语义还是语法上都是一个完整且有意义的句子。相似的，句子 “stock boil fish is toy” 应该有一个较低的概率，因为这句话没有意义。数学上我们可以计算出包含 $n$ 个单词的句子的概率：

$P\left(w_{1}, w_{2}, \cdots, w_{n}\right)$

我们可以采用一元语言模型（Unigram model）方法，假设单词的出现是完全独立的，那么：

$P\left(w_{1}, w_{2}, \cdots, w_{n}\right)=\prod_{i=1}^{n} P\left(w_{i}\right)$

然而，我们知道这有点可笑，因为下一个单词高度依赖于前一个单词序列。前面举的第二个例子可能得分很高。所以，我们尝试使句子出现的概率取决于每个单词和其相邻单词组成的单词对的概率。我们将这种方法称为二元语言模型（Bigrams）并表示为：

$P\left(w_{1}, w_{2}, \cdots, w_{n}\right)=\prod_{i=2}^{n} P\left(w_{i} | w_{i-1}\right)$

这同样有些天真，因为我们只关心相邻的词对，而不是整个句子，但正如我们将看到的，这种表示方式让我们前进了一步。在一个上下文大小为 1 的词-词矩阵中，我们基本可以获得词对的概率，但是同样地，在一个大型数据集上，这需要大量的计算和存储空间。

4.2 连续词袋模型（CBOW）

一种尝试是将 {“The”、“cat”、“over”、“The”、“puddle”} 作为上下文，并从这些单词中预测或生成中心单词 “jump”。我们称这种类型的模型为：连续词袋模型（CBOW）。

让我们更详细地讨论上述 CBOW 模型。

既然我们已经理解了如何计算词序列概率，让我们研究一些能够学习这些概率的模型。首先，我们设置我们的已知参数 —— 一个由 one-hot 向量矩阵表示的句子。我们将会用 $x^{(c)}$ 表示输入或者其上下文的 one-hot 向量。输出用 $y$ 表示——即中心词的 one-hot 向量。下面，让我们定义模型中的未知量：

我们建立两个矩阵：$\mathcal{V} \in \mathbb{R}^{n \times|V|}$ 和 $\mathcal{U} \in \mathbb{R}^{|V| \times n}$ 。其中，$n$ 是一个任意的量，它定义了我们词嵌入空间的大小。$\mathcal{V}$ 是输入词矩阵，它的第 $i$ 列表示了输入词 $w_i$ 的嵌入向量（大小为 $n \times 1$），我们可以将其记为 $v_i$。类似地，$\mathcal{U}$ 表示输出词矩阵。 $\mathcal{U} $ 的第 $j$ 列表示词 $w_j$ 的嵌入向量（大小为 $n \times 1 $），我们将其记为 $u_j$，它是我们模型的一个输出。所以事实上，我们学习了每个单词 $w_i$ 的两种表示：$v_i$ 和 $u_i$。

模型具体分为如下几步：

我们为输入的上下文（半径为 $m$）生成对应的 one-hot 向量。

$\left(x^{(c-m)}, \ldots, x^{(c-1)}, x^{(c+1)}, \ldots, x^{(c+m)} \in \mathbb{R}^{|V|}\right)$
得到上下文的嵌入词向量。

$( v_{c-m} = \mathcal{V} x^{(c-m)}, v_{c-m+1}=\mathcal{V} x^{(c-m+1)}, \ldots, v_{c+m}=\mathcal{V} x^{(c+m)} \in \mathbb{R}^{n} )$
将上下文的嵌入词向量取均值。

$\hat{v}=\frac{v_{c-m}+v_{c—n t+1}+\ldots+v_{c+m}}{2 m} \in \mathbb{R}^{n}$
生成打分向量。向量点积越高，表示单词越相似。

$z=\mathcal{U} \hat{v} \in \mathbb{R}^{|V|}$
将分数转换为概率（利用 softmax）。

$\hat{y}=\operatorname{softmax}(z) \in \mathbb{R}^{|V|}$
我们希望得到的概率 $\hat{y} \in \mathbb{R}^{|V|}$ 与实际概率 $y \in \mathbb{R}^{|V|}$ 匹配，而实际概率正是实际单词的 one-hot 向量。

补充：

softmax 操作将一个向量转化为了另一个向量，该向量的第 $i$ 个元素为：
$\frac{e^{\hat{y_i}}}{\sum_{k=1}^{|V|} e^{\hat{y}_{k}}}$
这样达到了两个效果：

取指数表示一定为正

正则化

我们已经了解了如果我们知道矩阵 $\mathcal{V}$ 和 $\mathcal{U}$ ，那么我们该如何学习这两个矩阵呢？首先，我们需要一个目标函数。通常，当我们试图从真实概率中学习概率时，我们会借助信息论来测量两个分布之间的距离。这里，我们选择了一种常见的距离/损失指标：交叉熵 $H(\hat{y}, y)$。

从损失函数的公式我们可以直观得到离散情况下使用交叉熵来表示：

$H(\hat{y}, y)=-\sum_{j=1}^{|V|} y_{j} \log \left(\hat{y}_{j}\right)$

对于我们现在的问题， $y$ 是一个 one-hot 向量，因此我们的损失函数可以简化为：

$H(\hat{y}, y)=-y_{i} \log \left(\hat{y}_{i}\right)$

在上式中，$i$ 为正确答案的 one-hot 向量为值为 1 的下标。假如我们的预测是完美的，$\hat{y}_{c}=1$。我们可以计算出：$H(\hat{y}, y)= -1 \log (1)=0$。因此，对于完美预测时，我们没有任何损失或者惩罚。现在让我们假设我们的预测效果很差，$\hat{y}_{c}= 0.01$，那么我们可以计算出：$H(\hat{y}, y)=-1 \log (0.01) \approx 4.605$。通过上述过程，我们不难看出交叉熵能够为我们测量距离提供一种很好的指标。这样我们可以建立起我们的优化目标为：

$\begin{aligned} \text { minimize } J &=-\log P\left(w_{c} | w_{c-m}, \ldots, w_{c-1}, w_{c+1}, \ldots, w_{c+m}\right) \\ &=-\log P\left(u_{c} | \hat{v}\right) \\ &=-\log \frac{\exp \left(u_{c}^{T} \hat{v}\right)}{\sum_{j=1}^{|V|} \exp \left(u_{j}^{T} \hat{v}\right)} \\ &=-u_{c}^{T} \hat{v}+\log \sum_{j=1}^{|V|} \exp \left(u_{j}^{T} \hat{v}\right) \end{aligned}$

我们使用随机梯度下降来更新所有相关的词向量：$u_c$ 和 $v_j$ 即可。

4.3 Skip-Gram 模型

另外一种尝试是创建一个模型：给定一个中心词 “jumped”，预测或生成其周围的单词：”The”, “cat”, “over”, “the”, “puddle”。这里我们称 “jumped” 为上下文。

接下来我们讨论 Skip-Gram 模型。模型的建立过程与 CBOW 很相似，只是 $x$ 和 $y$ 交换了位置。我们的输入 one-hot 向量将会记为：$x$。输出词向量表示为：$y^{j}$。并且，与 CBOW 相同，我们定义矩阵 $\mathcal{V}$ 和 $\mathcal{U}$ 。

同样地，模型的工作流程分为 5 步：

生成输入中心词的 one-hot 向量。

$x \in \mathbb{R}^{|V|}$
得到中心词的嵌入向量。

$v_{c}=\mathcal{V} x \in \mathbb{R}^{n} $
得到分数向量。

$z=\mathcal{U} v_{c}$
将分数向量转换为概率，$\hat{y}=\operatorname{softmax}(z)$。注意 $\hat{y}_{c-m}, \ldots, \hat{y}_{c-1}, \hat{y}_{c+1}, \dots, \hat{y}_{c+m}$ 为每个上下文的概率。
我们期望我们生成的概率向量与真实概率向量匹配，这些概率也正是真实输出的 one-hot 向量。

$y^{(c-m)}, \ldots, y^{(c-1)}, y^{(c+1)}, \ldots, y^{(c+m)}$

类似于 CBOW，我们需要生成模型的目标函数来评估模型。这里的一个关键区别是，我们调用了一个 Naive Bayes 假设来分解概率。如果你以前没有见过这种情况，那么简单地说，这是一个条件独立性假设。换句话说，所有的输出词可以被视为完全独立的。

补充：和 CBOW 模型一样，不考虑词顺序及词的位置对结果的影响。

$\begin{aligned} \text { minimize } J &=-\log P\left(w_{c-m}, \ldots, w_{c-1}, w_{c+1}, \ldots, w_{c+m} | w_{c}\right) \\ &=-\log \prod_{j=0, j \neq m}^{2 m} P\left(w_{c-m+j} | w_{c}\right) \\ &=-\log \prod_{j=0, j \neq m}^{2 m} P\left(u_{c-m+j} | v_{c}\right) \\ &=-\log \prod_{j=0, j \neq m}^{2 m} \frac{\exp \left(u_{c-m+j}^{T} v_{c}\right)}{\sum_{k=1}^{|V|} \exp \left(u_{k}^{T} v_{c}\right)} \\ &=-\sum_{j=0, j \neq m}^{2 m} u_{c-m+j}^{T} v_{c}+2 m \log \sum_{k=1}^{|V|} \exp \left(u_{k}^{T} v_{c}\right) \end{aligned}$

同样利用梯度下降的方法可以对参数进行更新。

4.4 负采样（Negative Sampling）

推荐先看补充材料 2

让我们回过头再看一次上面的目标函数。注意在整个 $|V|$ 上的求和计算是十分昂贵的。我们所做的任何更新或目标函数的评估都将花费 $O(|V|)$ 时间。一个简单的想法是我们可以采用近似的手段。

训练的每一步，我们可以通过只对一些负样本采样来代替循环整个词典。我们从一个噪声分布（$p_n(w)$）中抽样，该分布的概率匹配词典频率的顺序。要将问题的表达式扩展到负采样，我们需要做的就是更新

目标函数
梯度
更新规则。

虽然负抽样是基于 Skip-Gram 模型，但它实际上是在优化一个不同的目标。考虑一个单词，上下文对 $(w, c)$。这一单词-上下文对来自于训练数据吗？我们用 $P(D=1 | w, c)$ 表示 $(w,c)$ 来自语料库的概率。同样的，用 $P(D=0 | w, c)$ 表示其未来自语料库的概率。首先，我们可以通过让 $P(D=1 | w, c)$ 经过 sigmoid 函数：

$P(D=1 | w, c, \theta)=\sigma\left(v_{c}^{T} v_{w}\right)=\frac{1}{1+e^{\left(-v_{c}^{T} v_{w}\right)}}$

这样我们构建了一个新的目标函数，它试图最大化一个单词和上下文在语料库数据中出现的概率(如果它确实存在的话)，或者最大化一个单词和上下文不在语料库数据中出现的概率(如果它确实不存在的话)。我们利用极大似然法来得到这两个概率（其中 $\theta$ 为我们模型的参数，在我们的例子中，即为 $\mathcal{V}$ 和 $\mathcal{U}$ ）。

$\begin{aligned} \theta &=\underset{\theta}{\operatorname{argmax}} \prod_{(w, c) \in D} P(D=1 | w, c, \theta) \prod_{(w, c) \in \tilde{D}} P(D=0 | w, c, \theta) \\ &=\underset{\theta} {\operatorname{argmax}} \prod_{(w, c) \in D} P(D=1 | w, c, \theta) \prod_{(w, c) \in \tilde{D}}(1-P(D=1 | w, c, \theta)) \\ &=\underset{\theta}{\operatorname{argmax}} \sum_{(w, c) \in D} \log P(D=1 | w, c, \theta)+\sum_{(w, c) \in \tilde{D}} \log (1-P(D=1 | w, c, \theta)) \\ &=\underset{\theta}{\operatorname{argmax}} \sum_{(w, c) \in D} \log \frac{1}{1+\exp \left(-u_{w}^{T} v_{c}\right)}+\sum_{(w, c) \in \tilde{D}} \log \left(1-\frac{1}{1+\exp \left(-u_{w}^{T} v_{c}\right)}\right) \\ &=\underset{\theta}{\operatorname{argmax}} \sum_{(w, c) \in D} \log \frac{1}{1+\exp \left(-u_{w}^{T} v_{c}\right)}+\sum_{(w, c) \in \tilde{D}} \log \left(\frac{1}{1+\exp \left(u_{w}^{T} v_{c}\right)}\right) \end{aligned}$

注意，最大化可能性与最小化负对数可能性是一样的:

$J=-\sum_{(w, c) \in D} \log \frac{1}{1+\exp \left(-u_{w}^{T} v_{c}\right)}-\sum_{(w, c) \in \tilde{D}} \log \left(\frac{1}{1+\exp \left(u_{w}^{T} v_{c}\right)}\right)$

注意 $\tilde{D}$ 是一个“错误”或者“负”语料库。我们可能会含有：”stock boil fish is toy” 这样的句子在其中。

不自然的句子出现的概率应该很低，我们可以通过在词典中随机采样生成这样的负样本。

对于 skip-gram 模型，新目标函数应该为：

$-\log \sigma\left(u_{c-m+j}^{T} \cdot v_{c}\right)-\sum_{k=1}^{K} \log \sigma\left(-\tilde{u}_{k}^{T} \cdot v_{c}\right)$

对于 CBOW 模型，新目标函数应该为：

$-\log \sigma\left(u_{c}^{T} \cdot \hat{v}\right)-\sum_{k=1}^{K} \log \sigma\left(-\tilde{u}_{k}^{T} \cdot \hat{v}\right)$

在上式中，$\left\{\tilde{u}_{k} | k=1 \ldots K\right\}$ 是从 $P_n(w)$ 中采样的结果。接下来让我们讨论 $P_n(w)$ 应该是什么。尽管关于最佳近似有很多讨论，但是效果最好的应该是 Unigram 模型提出的 3/4 幂次。原因可以从下面来看出：

$0.9^{3 / 4}=0.92$
$0.09^{3 / 4}=0.16$
$0.01^{3 / 4}=0.032$

这样可以使得低频词出现的概率提升。

4.5 分层 softmax

作者同样指出，分层 softmax 是比普通的 softmax 更有效的一种手段。通常，分层 softmax 在低频词上效果更好，而负采样则在高频词和低维度时效果更高。

分层 softmax 用二叉树表示词典中的所有词。每个叶子节点代表一个单词，并且存在从根节点到每个叶子节点的唯一路径。在这个模型中，没有词的输出表示，相反，每个内部节点都对应了模型需要学习的向量。

在这个模型里，给定向量 $w_i$ 得到单词 $w$ 的概率 $P(w|w_i)$ 等于从根节点到 $w$ 对应的叶子节点随机游走的概率。这种计算方式的主要优势在于降低时间复杂度。

分层 Softmax使用二叉树，每个叶子表示一个单词。单词作为输出单词的概率定义为单词从根到叶的随机游走的概率。计算的复杂度从 $O(|V| )$ 变为了 $O(\log |V|)$。

让我们引入一些符号：

$L(w)$：从 root 到叶子节点 $w$ 路径上的节点数
$n(w, i)$：该路径上的第 $i$ 个节点
$v_{n(w,i)}$：第 $i$ 个节点关联的向量

因此，$n(w,1)$ 表示根节点，$n(w,L(w))$ 表示 $w$ 的父结点。对于每一个中间节点 $n$，我们记其左孩子为 $ch(n)$。那么，我们可以计算概率为：

$P\left(w | w_{i}\right)=\prod_{j=1}^{L(w)-1} \sigma\left([n(w, j+1)=\operatorname{ch}(n(w, j))] \cdot v_{n(w, j)}^{T} v_{w_{i}}\right)$

其中，

$[x]=\left\{\begin{array}{l}{1 \text { if } x \text { is true }} \\ {-1 \text { otherwise }}\end{array}\right.$

并且 $\sigma(\cdot)$ 为 sigmoid function。

接下来，让我们更深入地观察一下这个公式：

首先，我们计算从根节点到叶子节点 $w$ 的路径每个中间节点的点积。由于我们假设所有 $ch(n)$ 均表示左孩子，那么当向左走的时候 $[n(w, j+1)=\operatorname{ch}(n(w, j))]$ 返回 1，反之返回 -1。

此外，$[n(w, j+1)=\operatorname{ch}(n(w, j))]$ 该式也提供了正则化。在节点 $n$，如果我们将去往左右节点的概率相加，那么对于任何的 $v_{n}^{T} v_{w_{i}}$，

$\sigma\left(v_{n}^{T} v_{w_{i}}\right)+\sigma\left(-v_{n}^{T} v_{w_{i}}\right)=1$

同时，就像普通的 softmax 一样，这样的正则化也保证了 $\sum_{w=1}^{|V|} P\left(w | w_{i}\right)=1$。

最后，我们通过点积比较输入向量和每个中间节点的相似度。我们来看下面一个例子，以上图中 $w_2$ 为例，从根节点到达 $w_2$ 必须经过两次左孩子和一次右孩子，那么：

$\begin{aligned} P\left(w_{2} | w_{i}\right) &=p\left(n\left(w_{2}, 1\right), \text { left }\right) \cdot p\left(n\left(w_{2}, 2\right), \text { left }\right) \cdot p\left(n\left(w_{2}, 3\right), \text { right) }\right.\\ &=\sigma\left(v_{n\left(w_{2}, 1\right)}^{T} v_{w_{i}}\right) \cdot \sigma\left(v_{n\left(w_{2}, 2\right)}^{T} v_{w_{i}}\right) \cdot \sigma\left(-v_{n\left(w_{2}, 3\right)}^{T} v_{w_{i}}\right) \end{aligned}$

为了训练这个模型，我们的目标仍然是最小化 $-\log P\left(w | w_{i}\right)$。但是相比于更新每个词的输出向量，我们更新二叉树中在根节点到叶子节点路径上的每个向量值。

该方法的速度由二叉树的构造方法和赋予叶节点单词的方式决定。作者利用二叉霍夫曼树，这样可以分配高频词更短的路径。

补充材料

1. CBOW 模型

参考 word2vec中的CBOW模型。

模型简介

CBOW 模型，中文译为“连续词袋模型”，完成的任务是给定中心词 $w_i$ 的邻域半径内的单词，例如邻域半径为 2 时为：$w_{i-2}$, $w_{i-1}$, $w_{i+1}$, $w_{i+2}$，预测输出单词为该中心词 $w_i$ 的概率，由于没有考虑到词之间的顺序，所以称为词袋模型。模型结构如下：

模型过程

在上述结构示意图中，输入的单词实际上是一个 one-hot 向量。PROJECTION 层通过查表得到：首先初始化一个词向量矩阵 $W_{in}$，$W_{in}$ 是一个二维矩阵，行数等于构建的词典中的单词数目，列数是一个超参数，人为设定，一般为 100。那么其大小为 $|V| \times d$，其中 $|V|$ 是词典的大小，$d$ 是词向量的维度，$v$ 向量则是 $W_{in}$ 的一行，那么 look-up 过程操作如下：

$w_{i}^{T} W_{i n}=v_{i}$

这样我们就得到了 $w_i$ 对应的词向量。同理我们可以得到 $v_{i-2}$, $v_{i-1}$, $v_{i+1}$, $v_{i+2}$。

之后进行求和平均：

$v_{\text {PROJECTION}}=\frac{v_{i-2}+v_{i-1}+v_{i+1}+v_{i+2}}{4}$

通过该公式可以看出，四个词向量对于生成中心词的贡献是相同的，没有考虑到单词的顺序问题。

我们在输出层需要计算的是由 $w_{i-2}$, $w_{i-1}$, $w_{i+1}$, $w_{i+2}$ 生成 $w_i$ 的概率，即：

$P\left(w_{i} | w_{i-2}, w_{i-1}, w_{i+1}, w_{i+2}\right)$

经过上述的过程后， $w_{i-2}$, $w_{i-1}$, $w_{i+1}$, $w_{i+2}$ 被综合表示为了 $v_{\text {PROJECTION}}$ ，所以我们需要计算由 $v_{\text {PROJECTION}}$ 生成中心单词 $w_i$ 的概率为多大，也即是：

$P\left(w_{i} | w_{i-2}, w_{i-1}, w_{i+1}, w_{i+2}\right)=P\left(w_{i} | v_{P R O J E C T I O N}\right)$

由于给定上下文后，我们可以生成整个词典中的任意一个单词，只是生成的概率不同，那么我们用一个通式表示为：

$P\left(w_{i} | v_{P R O J E C T I O N}\right) ) \quad w_{i} \in V O C A B$

表示给定上下文单词 $w_{i-2}$, $w_{i-1}$, $w_{i+1}$, $w_{i+2}$ 生成 $w_i$ 的概率。这个值是通过对整个字典中的单词做 softmax 后得到，具体的公式如下：

$P\left(v_{i} | v_{i-2}, v_{i-1}, v_{i+1}, v_{i+2}\right)=\frac{\exp \left[u_{i}^{T}\left(v_{i-2}+v_{i-1}+v_{i+1}+v_{i+2}\right)\right]}{\sum_{j=1}^{V} \exp \left[u_{j}^{T}\left(v_{i-2}, v_{i-1}, v_{i+1}, v_{i+2}\right)\right]}$

其中，$V$ 表示词典的大小， $v_{i-2}$, $v_{i-1}$, $v_{i+1}$, $v_{i+2}$ 表示上下文单词向量。上式中的 $u_j$ 可以理解为一个打分权重。（存疑）

损失函数及优化

CBOW 模型中，假设训练数据是一段文本，长度为 $T$。那么，训练样本格式为：

$\left(\left(w_{i-2}, w_{i-1}, w_{i+1}, w_{i+2}\right), w_{i}\right) \quad 1 \leqslant i \leqslant T$

有训练数据，我们又建立了概率模型，因此我们可以定义一个似然函数，使得训练集中样本的似然概率最大。

$\prod_{i=1}^{T} P\left(w_{i} | w_{i-2}, w_{i-1}, w_{i+1}, w_{i+2}\right)$

上式就是我们 CBOW 模型的目标函数，为了学习到合适的词向量，我们需要最大化上述似然函数的值，这就等价于最小化如下损失函数的值：

$-\log \sum_{i=1}^{T} P\left(w_{i} | w_{i-2}, w_{i-1}, w_{i+1}, w_{i+2}\right)$

将具体的概率公式替换，可以得到损失函数为：

$-\log \sum_{i=1}^{T} \frac{\exp \left[u_{i}^{T}\left(v_{i-2}+v_{i-1}+v_{i+1}+v_{i+2}\right)\right]}{\sum_{j \in V} \exp \left[u_{j}^{T}\left(v_{i-2}+v_{i-1}+v_{i+1}+v_{i+2}\right)\right]}$

采用随机梯度下降方法，多次迭代后可以找到最优值。

2. 如何在 skip-gram 模型上进行高效训练

参考知乎专栏

不管在 CBOW 模型还是 skip-gram 模型，我们会发现 Word2Vec 模型是一个超级大的神经网络。

如果我们拥有 10000 个单词的词汇表，而我们想嵌入 300 维的词向量，那么我们的 输入-隐层权重矩阵 和 隐层-输出层权重矩阵 都会有 $1000 \times 300$ 个权重。

在如此庞大的神经网络中进行梯度下降是相当慢的。更糟糕的是，你需要大量的训练数据来调整这些权重并且避免过拟合。百万数量级的权重矩阵和亿万数量级的训练样本意味着训练这个模型将会是个灾难。

Word2Vec 的作者在第二篇论文里面强调了这些问题，并提出以下创新：

将常见单词组合（word pairs）或者词组作为单个词处理。
对高频词进行抽样来减少训练样本个数。
对优化目标采用 “negative sampling” 方法，这样每个训练样本的训练只会更新一小部分的模型权重，从而降低计算负担。

事实证明，对常用词抽样并且对优化目标采用“negative sampling”不仅降低了训练过程中的计算负担，还提高了训练的词向量的质量。

高频词抽样

首先回顾一下训练样本如何从原始文档中产生：

原始文本：”The quick brown fox jumps over the laze dog.”
窗口半径：2

但是，对于 “the” 这样的高频词，这样的处理方式会存在下面两个问题：

当我们得到成对的单词训练样本时，(“fox”, “the”) 这样的训练样本并不会给我们提供关于“fox”更多的语义信息，因为“the”在每个单词的上下文中几乎都会出现。
由于在文本中“the”这样的常用词出现概率很大，因此我们将会有大量的（”the“，…）这样的训练样本，而这些样本数量远远超过了我们学习“the”这个词向量所需的训练样本数。

Word2Vec通过“抽样”模式来解决这种高频词问题。它的基本思想如下：对于我们在训练原始文本中遇到的每一个单词，它们都有一定概率被我们从文本中删掉，而这个被删除的概率与单词的频率有关。

word2vec 的 C 语言代码实现了一个计算在词汇表中保留某个词概率的公式。$w_i$ 是一个单词，记 $Z(w_i)$ 为 $w_i$ 这个单词在所有语料中出现的频率。这个值越小意味着这个单词被保留下来的概率越小（即有越大的概率被我们删除）。

用 $P(w_i)$ 表示保留某个单词的概率，设定阈值 0.001，那么：

$P\left(w_{i}\right)=\left(\sqrt{\frac{Z\left(w_{i}\right)}{0.001}}+1\right) \times \frac{0.001}{Z\left(w_{i}\right)}$

从上图中，我们可以看出：

当 $Z(w_i) \leq 0.0026$ 时，单词百分之百被保留。
当 $Z(w_i) = 0.00746$ 时，单词百分之五十被保留。
当 $Z(w_i) = 1.0$ 时，单词仅有 $3.3 \% $ 的概率被保留。

负采样

负采样是用来提高训练速度并且改善所得到词向量的质量的一种方法。不同于原本每个训练样本更新所有的权重，负采样每次让一个训练样本仅仅更新一小部分的权重，这样就会降低梯度下降过程中的计算量。

当我们用训练样本 ( input word: “fox”，output word: “quick”) 来训练我们的神经网络时，“ fox”和“quick”都是经过one-hot编码的。如果我们的vocabulary大小为10000时，在输出层，我们期望对应“quick”单词的那个神经元结点输出1，其余9999个都应该输出0。在这里，这9999个我们期望输出为0的神经元结点所对应的单词我们称为“negative” word。

当使用负采样时，我们将随机选择一小部分的negative words（比如选5个negative words）来更新对应的权重。我们也会对我们的“positive” word进行权重更新（在我们上面的例子中，这个单词指的是”quick“）。

在论文中，作者指出指出对于小规模数据集，选择5-20个negative words会比较好，对于大规模数据集可以仅选择2-5个negative words。

回忆一下我们的隐层-输出层拥有 $300 \times 10000$ 的权重矩阵。如果使用了负采样的方法我们仅仅去更新我们的 positive word-“quick” 的和我们选择的其他5个negative words的结点对应的权重，共计 6 个输出神经元，相当于每次只更新 $300 \times 6$ 个权重，这样计算效率就大幅提高。

如何选择 negative words

我们使用“一元模型分布（unigram distribution）”来选择“negative words”。

要注意的一点是，一个单词被选作 negative sample 的概率跟它出现的频次有关，出现频次越高的单词越容易被选作 negative words 。

$P\left(w_{i}\right)=\frac{f\left(w_{i}\right)^{3 / 4}}{\sum_{j=0}^{n}\left(f\left(w_{j}\right)^{3 / 4}\right)}$

其中，$f(w_i)$ 代表着单词出现的频次。

参考材料

[Collobert et al., 2011] Collobert, R., Weston, J., Bottou, L., Karlen, M., Kavukcuoglu,
K., and Kuksa, P. P. (2011). Natural language processing (almost) from scratch.
CoRR, abs/1103.0398.

[Mikolov et al., 2013] Mikolov, T., Chen, K., Corrado, G., and Dean, J. (2013). Efficient
estimation of word representations in vector space. CoRR, abs/1301.3781.