CS224N Lecture 1 Introduction and Word Vectors

Word meaning

Representing words as discrete symbols

在传统NLP中， 我们将word视为离散的符号。特别是one-hot encoding， 如：

$$\text{model} = [0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 1 \ 0 \ 0 \ 0 \ 0]\\ \text{hotel} = [0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 1 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0 \ 0] \tag{1}$$

其中， 向量维度= 词汇表单词数量(e.g, 500,000)

Problem with words as discrete symbols

• 式2两个向量正交
• 对于one-hot 向量没有相似性的自然理解。

Solution:

替代：学习把相似性编码到向量里。

Representing words by their context

• 语义分布：单词的意思有其频繁出现的近邻词来给定
• 当一个单词w出现在文本中，其上下文是出现在附近的一系列单词（ 在一个固定的窗口内）
• 用许多w的文本向量来构建一个w的表示矩阵

Word2vec： Overview

Word2vec （Mikolov et al. 2013 ） 是为了学习词向量的框架。

思路：

• 我们有一个庞大的文本语料库
• 在一个固定词汇表的每个词用一个向量表示
• 在文本中检查每个位置t，其中有一个中心词c 和 上下文词o
• 用对于c和o的词向量的相似度来计算给定中心词c的上下文的概率（或相反）
• 调整词向量来最大化这个概率

示例：窗口和处理计算$P(w_{t+j }\vert w_t)$

Word2vec: objective function

对于每个位置$t = 1, \cdots, T$,给定中心词$w_j$ 预测在一个固定大小m窗口上下文

$$Likelihood = L(\theta) = \prod_{t=1}^{T} \prod_{-m\le j \ge m ,\ j \neq0} P(w_{t+j} \vert w_{t}; \theta) \tag{2}$$

最大化的预测准确率式2，等于最小化目标函数：

$$J(\theta) = -\frac{1}{T}log L(\theta) = -\frac{1}{T}\prod_{t=1}^{T} \prod_{-m\le j \ge m ,\ j \neq0} log \ P(w_{t+j} \vert w_{t}; \theta) \tag{3}$$

Notes

基于SVD 的方法

Word-Document Matrix

矩阵X:

• 我们遍历百万级的文档，每次当单词i出现在文档j中，添加一个元素$X_{ij}$.显然这是一个规模非常大的矩阵$\mathbb{R}^{\lvert V \rvert \times M}$。
• M是文档数目， V是词汇表的长度

Notes：

Distributional semantics 语义分布: 这个概念表示一个基于单词通常在上下文的意义。它是一个密度估计，这能更好地获得相似度。

以下语料库包含3句话和窗口大小为1的关系：

1. I enjoy flying.
2. I like NLP .
3. I like deep learning.

结果的关系矩阵为:

Word-Word 共现矩阵的使用：

• 生成 $\lvert V \rvert \times \lvert V \rvert$共现矩阵$X$
• 对$X$使用SVD分解得到$X = USV^T$
• 选择$U$的前$k$列来得到一个$k$的词向量
• $\frac{\sum_{i=1}^{k}\sigma_i}{\sum_{i=1}^{\lvert V \rvert}\sigma_i}$表明通过前k维获得的方差数量

import numpy as np
A = np.mat([[0, 2, 1, 0, 0, 0, 0, 0],
       [2, 0, 0, 1, 0, 1, 0, 0],
       [1, 0, 0, 0, 0, 0, 1, 0],
       [0, 1, 0, 0, 1, 0, 0, 0], 
       [0, 0, 0, 1, 0, 0, 0, 1],
       [0, 0, 1, 0, 0, 0, 0, 1],
       [0, 0, 0, 0, 1, 1, 1, 0]])
u, s, vt = np.linalg.svd(A)
print("U:", u,'\n', "Sigma:", s, '\n', "VT:",vt)

===============================================================================
U: 
[[ 0.09455612  0.86336676 -0.12220393  0.25575989 -0.13285143 -0.02767876
   0.38326809]
 [ 0.8528587  -0.15327167 -0.21454303  0.27874733  0.19389029 -0.28718474
  -0.07309257]
 [ 0.37014698 -0.05682519  0.17128669  0.04188288 -0.63749818  0.64020128
  -0.11138756]
 [ 0.08992443  0.42456305  0.30406875 -0.05063662  0.45258658  0.24113937
  -0.67353925]
 [ 0.1664946   0.01282527 -0.45011352 -0.52355753  0.38881548  0.50010667
   0.30678371]
 [ 0.04823424  0.20744275 -0.41149144 -0.53891401 -0.42697718 -0.36324401
  -0.42500792]
 [ 0.29757182  0.06652636  0.66731789 -0.53668218 -0.00561351 -0.25826353
   0.32703632]] 
 Sigma: 
 [2.72252553 2.49475 1.84142251 1.58016483 1.1834359  0.83631332 0.61349731] 
 VT: [[ 0.76247747  0.10249184  0.05244776  0.3744146   0.1423297   0.42256005
   0.24525713  0.07887119]
 [-0.14565329  0.86232953  0.42922518 -0.05629678  0.19684915 -0.03477114
   0.00388863  0.08829262]
 [-0.14000011  0.03239935 -0.28982777 -0.36094733  0.5275197   0.2458832
   0.45541128 -0.46790183]
 [ 0.3793133   0.29166778 -0.17919277 -0.154927   -0.37168199 -0.16323288
  -0.31313145 -0.67238019]
 [-0.21101068  0.15791622 -0.4730536   0.49238473  0.37769099  0.15909335
  -0.54342756 -0.03224653]
 [ 0.07871667  0.22214383 -0.46743578  0.25459588 -0.02047576 -0.65220565
   0.45669219  0.16364998]
 [-0.41984324  0.15158491 -0.06803587  0.38091632 -0.56479943  0.41392806
   0.35150727 -0.19270534]
 [ 0.08333333  0.25       -0.5        -0.5        -0.25        0.33333333
  -0.08333333  0.5       ]]

Applying SVD to the cooccurrence matrix

通过对X做SVD， 观察对角阵上对角元素， 基于期望百分比方差获得前k个索引：

$$\frac{\sum_{i=1}^{k}\sigma_i}{\sum_{i=1}^{\lvert V \rvert}\sigma_i} \tag{4}$$

对X应用SVD：

通过选择前k个奇异向量:

这些方法给予我们词向量， 这不仅仅足以编码语义和句法（语音部分）信息，但其引起许多其他问题:

• 矩阵维度经常变化（新词频繁加入和语料库大小变化）
• 矩阵十分稀疏，大多数词不经常出现
• 矩阵通常维度非常高($\approx 10^6 \times 10^6$)
• 平方次复杂度的训练代价(e.g 执行SVD)
• 需要在X上创建一些技巧来解决词频的急剧不平衡

一些存在来解决这些问题的措施如下：

• 忽略一些功能词如”the”, “he”, “has”, etc.
• 应用ramp window—例如，基于文档中词与词距离加上一个共现次数的权重
• 用皮尔逊系数将负数设为0而不是使用原始计数

Iteration Based Methods - Word2vec

• 2 algorithms : continuous bag-of-words (CBOW) and skip-gram . CBOW 目标是用周围上下文的词向量来预测中心词。Skip-gram正好相反，用中心词来预测上下文的分布或者说概率。

• 2 training methods ：负采样或hierarchical softmax。负采样通过抽取负样本来定义目标，而hierarchical softmax用有效的树结构来对所有词汇计算概率从而定义目标。

Language Models (Unigrams, Bigrams, etc.)

Unigram model: 假设每个词出现的完全独立

$$p(w_1, w_2, \cdots, w_n) = \prod_{i=1}^{n} P(w_i) \tag{5}$$

Bigram model： 假定sequence 的概率取决于一个词在sequence中和其旁边词出现的概率：

$$p(w_1, w_2, \cdots, w_n) = \prod_{i=1}^{n} P(w_i \vert w_{i-1}) \tag{6}$$

Continuous Bag of Words Model (CBOW)

{“The”, “cat”, ’over”, “the’, “puddle”} 作为上下文，可以预测或生成中心词”jumped” 。——CBOW。

CBOW细节：

1. 设置已知参数。令模型中已知参数用one-hot词向量表示。输入one-hot向量或上下文用$x^{(c)}$，输出为$y^{(c)}$。

2. 未知参数：

   • 创建两个矩阵，$\mathcal{V} \in \mathbb{R}^{n \times \lvert V \rvert}$和$\mathcal{U} \in \mathbb{R}^{\lvert V \rvert \times n }$.其中， $n$是由embedding 空间定义的任意维度；

     $\mathcal{V}$是输入词矩阵，如$\mathcal{V}$的第$i$列是当其是模型的输入时，对词 $w_i$的 $n$维嵌入空间向量。记为$n \times 1 列向量v_i$。

     $\mathcal{U}$是输出词矩阵，如$\mathcal{U}$的第$j$列是当其是模型的输出时，对词 $w_j$的 $n$维嵌入空间向量。记为$1 \times n 行向量u_i$。

     注意： 对于每个词$w_i$都学到两个向量

CBOW model：

从周围上下文来预测中心词：对每个词，我们希望学到两个向量

• $v$ 输入向量: 当这个词在上下文中
• $u$ 输出向量: 当这个词是中心词

CBOW model 记号：

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

CBOW model步骤分解：

1. 为输入的上下文生成大小为$m$的one-hot词向量：$(x^{c-m}, \cdots, x^{c-1}, x^{c+1}, \cdots, x^{c+m} \in \mathbb{R}^{\lvert V \rvert})$, 注即中心词$c$附近$m$窗口内的词的词向量。
2. 为上下文$( 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)$得到嵌入词向量
3. 取这些向量的均值得到$\hat v = \frac{v_ {c-m} + v_ {c-m+1} + \cdots + v_ {c+m}}{2m}$
4. 生成分数向量 $z = \mathcal{U} \hat v \in \mathbb{R}^{\lvert V \rvert}$. 因为相似向量的点积会高(点积的几何意义)，为了达到高分数， 将会迫使相似词彼此靠近。
5. 将分数变为概率$\hat y = \text{softmax} (z) \in \mathbb{R}^{\lvert V \rvert}$。
6. 要求生成的概率， $\hat y \in \mathbb{R}^{\lvert V \rvert}$, 来匹配真正的概率， $y \in \mathbb{R}^{\lvert V \rvert}$, 这也恰好是真实词的one-hot向量。

现在，我们了解了如果我们有$\mathcal{V} \ 和 \ \mathcal{U}$模型怎么工作， 我们怎样学到这两个矩阵?

利用交叉熵来得到到loss function：

$$H(\hat y, \ y) = -\sum_{j = 1}^{\lvert V \rvert} y_j \text{log} (\hat y_{j}) \tag{7}$$

$ y $是一个one-hot 向量， 因此，可以将式7简化为：

$$H(\hat y, \ y) = -y_i\text{log} (\hat y_{j}) \tag{8}$$

softmax 操作 ：

$$\frac {e^{\hat y_i}}{\sum_{k = 1}^{\lvert V \rvert}e^{\hat y_k}} \tag{9}$$

​ Note:： $\hat y \mapsto H(\hat y, y), \ 当 \ \hat y = y取最小值。那么当我们找到H(\hat y, y)最小值，有\hat y \approx y$。这意味着我们模型在预测中心词上是非常好的。

最小化 目标函数：

$$\begin{aligned} \text{minimize} \ J &=-\log P\left(w_{c} \mid w_{c-m}, \ldots, w_{c-1}, w_{c+1}, \ldots, w_{c+m}\right) \\&=-\log P\left(u_{c} \mid \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} \tag{10}$$

可以用随机梯度下降来更新所有有关词向量$u_c \ 和 \ v_j$。

Skip-Gram Model

Skip-Gram Model :

• 给定中心词预测周围上下文

大部分参数设定跟CBOW一样， 不过把$x$与 $y$交换下。 输入one-hot向量是中心词用$x$表示， 输出向量是周围上下文用$y$表示。$\mathcal{V} \ 和 \ \mathcal{U}$跟CBOW一样。

Skip-Gram model步骤分解：

1. 生成中心词的one-hot输入向量$x \in \mathbb{R}^{\lvert V \rvert}$。
2. 中心词$v_{c} = \mathcal{V}x \in \mathbb{R}^n$ 的嵌入向量。
3. 生成分数向量 $z = \mathcal{U} v_c \in \mathbb{R}^{\lvert V \rvert}$.
4. 将分数变为概率$\hat y = \text{softmax} (z)$。注:$\hat y^{c-m}, \cdots, \hat y^{c-1}, \hat y^{c+1}, \cdots, \hat y^{c+m}$是观察的每个上下文词的概率
5. 要求生成的概率向量来匹配真实的概率 $y^{c-m}, \cdots, y^{c-1}, y^{c+1}, \cdots, y^{c+m}$,即真实输出的one-hot向量。

CBOW中，是生成目标函数来估计模型。Skip-Gram 是用朴素贝叶斯分解概率表达式， 即假定输出词是完全独立的。

$$\begin{aligned} \text{minimize} \ J &=-\log P\left( w_{c-m}, \ldots, w_{c-1}, w_{c+1}, \ldots, w_{c+m} \mid w_{c}\right) \to \text{给定中心词， 而不是给定上下文} \\&=-\log \prod_{j=0,\ j \neq m}^{2m} P\left(w_{c-m+j} \mid w_c\right) \\ \\ &= -\log \prod_{j=0,\ j \neq m}^{2m} P\left(u_{c-m+j} \mid v_c\right) \\\\ &=-\log \prod_{j=0,\ j \neq m}^{2m} \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}^{2m}u_{c}^{T} v_c+2m\log \sum_{j=1}^{|V|} \exp \left(u_{j}^{T} v_c\right) \end{aligned} \tag{11}$$

利用SGD来迭代求出未知参数：

$$\begin{align} J &=-\sum_{j=0,\ j \neq m}^{2m} \text{log} \ P(u_{c-m+j}|v_c) \\ &= \sum_{j=0,\ j \neq m}^{2m} H(\hat y, \ y_{c-m+j}) \end{align} \tag{12}$$

注： 仅仅只有一个概率向量$\hat y$要计算。Skip-gram 将每个上下词平等看待：模型计算独立地出现在中心词的每个上下词对中心词距离的概率。

Negative Sampling

注意到对$|V|$的计算量巨大。做目标函数的任何更新或计算时间复杂度为O(|V|)。采用负采样可以近似，而不是计算整个词汇表。更新以下参数：

• 目标函数
• 梯度
• 更新准则

Tomas Mikolov 的《Distributed Representations of Words and Phrases and their Compositionality》论文中提出的负采样。虽然负采样是基于Skip-Gram模型，但实际上是优化不同的目标函数。考虑一对中心词和上下文$(w, c)$。记$P(D=1|w, c)$表示$(w, c)$来自语料数据的概率，对应地记$P(D=0|w, c)$表示$(w, c)$不来自语料数据的概率。 接下来， 用sigmoid函数对$P(D=1|w, c)$建模：

$$P(D=1|w, c, \theta) = \sigma(v_c^T v_w) = \frac{1}{1+e^{-v_c^T v_w}} \tag{13}$$

建立一个新的目标函数，如果中心词和上下文词确实在语料库中，就最大化概率$P(D=1|w, c)$ ，如果中心词和上下文词确实不在语料库中，就最大化概率 $P(D=0|w, c)$。我们对这两个概率用一个简单的极大似然估计的方法（这里把$\theta$作为模型的参数，在该例子中是$\mathcal{V}$和 $\mathcal{U}$）。

$$\begin{aligned} \theta &=\underset{\theta}{\operatorname{argmax}} \prod_{(w, c) \in D} P(D=1 \mid w, c, \theta) \prod_{(w, c) \in \tilde{D}} P(D=0 \mid w, c, \theta) \\ \\ &=\underset{\theta}{\operatorname{argmax}} \prod_{(w, c) \in D} P(D=1 \mid w, c, \theta) \prod_{(w, c) \in \tilde{D}}(1-P(D=1 \mid w, c, \theta)) \\ \\ &=\underset{\theta}{\operatorname{argmax}} \sum_{(w, c) \in D} \log P(D=1 \mid w, c, \theta)+\sum_{(w, c) \in \tilde{D}} \log (1-P(D=1 \mid 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} \tag{14}$$

注意：最大化似然函函数等价于最小化负对数似然

$$J = - \left( \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)\right) \tag{15}$$

注：$\tilde D$是负语料。无意义的句子出现概率是很低的。我们可以从语料库中随机抽取负样例$\tilde D$。

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

$$-\text{log} \ \sigma (u_{c-m+j}^T \cdot v_c) - \sum_{k=1}^{K} \sigma (- \tilde u_k^{T} \cdot v_c) \tag{16}$$

对于CBOW ，给定上下文词向量$\hat v = \frac{v_{c-m} + v_{c-m+1}+\cdots+v_{c+m}}{2m}$观察的中心词$u_c$的目标函数为：

$$-\text{log} \ \sigma (u_{c}^T \cdot \hat v) - \sum_{k=1}^{K} \sigma (- \tilde u_k^{T} \cdot \hat v) \tag{17}$$

Skip-Gram对应的softmax损失：

$$- u_{c-m+j}^T \cdot v_c + \text{log} \sum_{k=1}^{|V|} \text{exp} ^{ u_k^{T} \cdot v_c} \tag{18}$$

CBOW对应的softmax损失：

$$- u_{c}^T \cdot \hat v+ \text{log} \sum_{j=1}^{|V|} \text{exp} ^{ u_j^{T} \cdot \hat c} \tag{19}$$

上面公式中， $\{ \tilde u | k = 1 \cdots K \}$ 是从$P_n(w)$抽样得到的。实际上效果最好的是取$\frac{3}{4}$的Unigram model，论文中取值。

Hierarchical Softmax

同样是, Tomas Mikolov 的《Distributed Representations of Words and Phrases and their Compositionality》论文中提出的Hierarchical Softmax。实际上， Hierarchical Softmax对低频词表现更好，而负采样对高频词和低维向量表现更好。

Hierarchical Softmax用二叉树表示词汇表中的所有词。树的每一个叶子节点都是一个词，并且只有一条路径从根到叶子。在该模型中，没有词的输出表示。相反， 图的每个节点， 除了根节点和叶子节点， 都跟模型要学的向量相关。

在该模型中，给定向量$w_i$ 单词$w$的概率，记为$P(w|w_i)$,等于从根结点开始到对应$w$ 的叶结点的随机的概率。优势是时间复杂度变为O(log(|V|)),对应该路径的长度。

引入一些记号：

• $L(w)$： 从根节点到叶子节点$w$的路径上的节点数目。下图， $w_2$对应3.

• $v_n(w, i)$：该路径上第i个节点向量， 即叶子节点w到跟节点路径的第i个节点。

  $n(w, 1)$是根节点， 而 $n(w, L(w))$是w的父节点。

• 对于每个内部节点n, 任意选择其中一个孩子节点称为$ch(n)$，总是左节点。

计算概率为:

$$P(w \vert w_i) = \prod_{j=1}^{L(w)-1} \sigma \left( \left[ n(w, j+1)=ch(n(w, j)) \right] \cdot v_{n(w, j)^{T}v_{w_i}}\right) \tag{20}$$

这里，

$$[x] = {\begin{cases}1,&{\mbox{if }} \ x \text{ is true}\\-1&{\mbox{if }}\ \ x \text{ is otherwise} \end{cases}} \tag{21}$$

式20是风采难懂的。

• 基于从根节点$(n(w, 1))$到叶子节点$(w)$的累乘项。如果我们假设$ch(n)$总是左节点$n$, $[n(w， j+1)=ch(n(w, j))]$就返回1， 反之则是-1.

• $[n(w， j+1)=ch(n(w, j))]$提供标准化。在节点$n$上， 如果从左节点到右节点的概率求和，对于任意的$v_n^Tv_{w_i}$有：

$$\sigma(v_n^Tv_{w_i}) + \sigma (-v_n^Tv_{w_i}) = 1 \tag{22}$$

​ 同时保证了$\sum_{w=1}^{|V|} P(w|w_i) = 1$， 跟原来的softmax一样。

• 使用点积对比输入向量$v_{w_i}$和每个内部节点向量$v_{n(w, j)}^T$相似度。例如，上图 $w_2$, 我们必须要取两条左边和一条右边来从$w_2$到根节点，即：

$$P(w_2|w_i) = p(n(w_2|1), \text{ left}) \cdot p(n(w_2|2), \text{ left}) \cdotp(n(w_2|3), \text{ right}) \cdot \\\\= \sigma(v_{(w_2, 1)}^Tv_{w_i} \cdot \sigma(v_{(w_2, 2)}^Tv_{w_i}\cdot \sigma(-v_{(w_2, 3)}^Tv_{w_i}) \tag{23}$$

为了训练模型，我们的目标仍然是最小化负对数似然$-log \ P(w|w_i)$。但不是更新每个输出向量， 而是更新在二叉树上从根到叶子节点的节点向量。

该方法的速度取决于二叉树构建的方式和分配到叶子节点的单词。Mikolov 使用了哈夫曼树， 将高频词分配到树的最短路径上。

参考

[1] cs224n-2019-notes01-wordvecs1

[2] cs224n-2020-lecture01-wordvecs1

[3] CS224n课程笔记翻译 词向量I: 简介, SVD和Word2Vec

[4] Word2Vec Tutorial Part I: The Skip-Gram Model

[5] Word2Vec Tutorial Part II: The Continuous Bag-of-Words Model