GloVe

GloVe: Global Vectors for Word Representation

GloVe (Global Vectors)名称由来：因为这个模型捕获了语料库全局统计信息

概述

做自然语言处理的时候很多时候会用的Word Embedding，目前常用的方法是word2vec算法训练词向量。不过训练词向量的方法有很多，今天介绍GloVe算法。

模型输入：语料库 corpus

模型输出：每个词的表示向量

基本思想

要讲GloVe模型的思想方法，我们先介绍两个其他方法：

一个是基于奇异值分解（SVD）的LSA算法，该方法对word-word矩阵进行奇异值分解。此处使用的是全局统计特征。

另一个方法是word2vec算法，该算法可以分为skip-gram 和 continuous bag-of-words（CBOW）两类,但都是基于局部滑动窗口计算的。即，该方法利用了局部的上下文特征（local context）

LSA和word2vec作为两大类方法的代表，一个是利用了全局特征的矩阵分解方法，一个是利用局部上下文的方法。

GloVe模型就是将这两中特征合并到一起的，即使用了语料库的全局统计（overall statistics）特征，也使用了局部的上下文特征（即滑动窗口）。为了做到这一点GloVe模型引入了Co-occurrence Probabilities Matrix。

notation:
$X$: co-occurrence matrix
$X{i j}$: 语料库中出现在word i上下文中word j的次数
$X_i=\sum_k X{i k}$，出现在word i上下文中所有的word的次数
$P{i j}=P(j \mid i)=\frac{X{i j}}{X_i}$，word j出现在word i上下文的概率
由以上概念引申出共现概率矩阵（Co-occurrence Probabilities matrix）

$$\begin{array}{l|cccc} \text { Probability and Ratio } & k=\text { solid } & k=\text { gas } & k=\text { water } & k=\text { fashion } \\ \hline P(k \mid \text { ice }) & 1.9 \times 10^{-4} & 6.6 \times 10^{-5} & 3.0 \times 10^{-3} & 1.7 \times 10^{-5} \\ P(k \mid \text { steam }) & 2.2 \times 10^{-5} & 7.8 \times 10^{-4} & 2.2 \times 10^{-3} & 1.8 \times 10^{-5} \\ P(k \mid \text { ice }) / P(k \mid \text { steam }) & 8.9 & 8.5 \times 10^{-2} & 1.36 & 0.96 \end{array}$$

solid 与 ice 相关，与steam 不相关
gas 与 ice 不相关，与steam 相关
water 与 ice，steam 都相关
fashion 与 ice，steam 都不相关

由Co-occurrence Probabilities matrix可以看出Ratio $=\frac{P{i k}}{P{j k}}$的取值是有规律的。

ratio i,j,k的值	单词j,k相关	单词j,k不相关
单词i,k相关	趋近1	很大
单词i,k不相关	很小	趋近1

也就是说Ratio值能够反映word之间的相关性，而GloVe模型就是利用了这个Ratio值。
再明确一下，GloVe模型的目标就是获取每一个word的向量表示 $\mathrm{v}$。不妨假设现在已经得到了word $i, j, k$ 的词 向量 $wi, w_j, w_k$ 。**GloVe认为，这三个向量通过某种函数的作用后所呈现出来的规律和Ratio $=\frac{P{i k}}{P_{j k}}$ 具有一致性，即相等，也就可以认为词向量中包含了共现概率矩阵中的信息。**
假设这个末知的函数是 $F$, 则:

$$F\left(w_i, w_j, w_k\right)=\frac{P_{i k}}{P_{j k}}$$

右侧的 $\frac{P{ik}}{P{jk}}$ 可以通过统计求的；
左侧的 $w_i, w_j, w_k$ 是我们模型要求的量；
同时函数 $F$ 是末知的。
如果能够将函数F的形式确定下来，就可以通过优化算法求解词向量了。那么GloVe模型的作者是怎么将$F$确定下来的呢?

1.$\frac{P{ik}}{P{j k}}$ 考察了 $i, j, k$ 三个word两两之间的相似关系，不妨单独考察 $i, j$ 两个词和他们词向量 $w_i, w_j$ ，线性空间中旳相似关系自然想到的是两个向量的差 $\left(v_i-v_j\right)$ 。所以F函数的形式可以是

$$F\left(w_i-w_j, w_k\right)=\frac{P_{i k}}{P_{j k}}$$

2.$\frac{P{i k}}{P{j k}}$ 是一个标量，而F是作用在两个向量上的，向量和标量之间的关系自然想到了使用内积。所以F函数的形式可以进一步确定为

$$F\left(\left(w_i-w_j\right)^T w_k\right)=F\left(w_i^T w_k-w_j^T w_k\right)=\frac{P_{i k}}{P_{j k}}$$

3.到此为止模型公式的形式是 $F\left(wi^T w_k-w_j^T w_k\right)=\frac{P{i k}}{P_{j k}}$ 。左边是差，右边是商，模型通过将F取作 $\exp$ 来将差和商关联起来

$$\exp \left(w_i^T w_k-w_j^T w_k\right)=\frac{\exp \left(w_i^T w_k\right)}{\exp \left(w_j^T w_k\right)}=\frac{P_{i k}}{P_{j k}}$$

4.现在只需要让分子分母分别相等，上式就能够成立，所以

$$\exp \left(w_i^T w_k\right)=P_{i k}, \exp \left(w_j^T w_k\right)=P_{j k}$$

5.所以只需要在整个文本库中考察$\exp \left(wi^T w_k\right)=P{i k}=\frac{X_{i k}}{X_i}$，即

$$w_i^T w_k=\log \left(\frac{X_{i k}}{X_i}\right)=\log X_{i k}-\log X_i$$

6.作为向量，交换 $i$ 和 $k$ 的顺序 $wi^T w_k$ 和 $w_k^T w_i$ 是相等的，即公式左边对于 $i$ 和 $k$ 的顺序是不敏感的，但是公式右边交换 $i$ 和 $k$ 的顺序 $\log X{i k}-\log Xi \neq \log X{k i}-\log X_k$ 。为了解决这个对称性问题 ，模型引入了两个偏置项 $b_i, b_k$,从而将模型变成了

$$\log X_{i k}=w_i^T w_k+b_i+b_k$$

7.上面旳公式只是理想情况下，在实际实验中左右两边只能要求接近。从而就有了代价函数cost function：

$$J=\sum_{i k}\left(w_i^T w_k+b_i+b_k-\log X_{i k}\right)^2$$

8.根据经验，如果两个词共同出现的次数越多，那么这两个词在代价函数中的影响就应该越大，所以可以根据两个词共同出现的次数设计一个权重项来对代价函数中的每一项进行加权：

$$J=\sum_{i k} f\left(X_{i k}\right)\left(w_i^T w_k+b_i+b_k-\log X_{i k}\right)^2$$

模型认为权重函数 $f$ 应该符合以下三个特点：

1. $f(0)=0$ （如果两个词没有共同出现过，权重就是0）；
2. $f(x)$ 必项是非减函数 (两个词共同出现的次数多，反而权重变小了，违反了设置权重项的初衷）；
3. $f(x)$ 对于较大的 $x$ 不能取太大的值(就像是汉语中”的”这个字，在很多文章中都会出现很多次，但是其在文中的重要程度非常小)。综合这三条特点的 $f(x)$ 定义为：

$$f(x)=\left\{\begin{array}{c} \left(\frac{x}{x_{\max }}\right)^\alpha, \text { if } x<x_{\max } \\ 1, \text { otherwise } \end{array}\right.$$

根据经验，GloVe作者认为$x_{\max }=100, \alpha=\frac{3}{4}$是一个比较好的选择

Least Squares Objective

GloVe也从另一个角度推导了这个公式。
不同的词向量学习方法最终都是基于语料库的共现统计信息，不同的模型之间应该存在一些共通性
GloVe类似skip-gram 模型，我们利用下式计算单词j出现在单词i的上下文的概率

$$Q_{i j}=\frac{\exp \left(\vec{u}_j^T \vec{v}_i\right)}{\sum_{w=1}^W \exp \left(\vec{u}_w^T \vec{v}_i\right)}$$

所以全局交叉熵为

$$J=-\sum_{i \in \text { corpus }} \sum_{j \in \text { context }(i)} \log Q_{i j}$$

利用Co-occurrence Matrix，我们可以将上式写为：

$$J=-\sum_{i=1}^W \sum_{j=1}^W X_{i j} \log Q_{i j}$$

如果定义上述损失函数，那么$Q_{i j}$的softmax分母计算需要很多计算量。为了解决这点，我们使用最小二乘损失函数来代替上述损失函数：

$$\hat{J}=\sum_{i=1}^W \sum_{j=1}^W X_i\left(\hat{P}_{i j}-\hat{Q}_{i j}\right)^2$$

其中

$$\begin{aligned} \hat{P}_{i j} & =X_{i j} \\ \hat{Q}_{i j} & =\exp \left(\vec{u}_j^T \vec{v}_i\right) \end{aligned}$$

由于指数函数可能会产生很大的值，所以对括号内的值取对数更容易减少误差：

$$\begin{aligned} \hat{J} & =\sum_{i=1}^W \sum_{j=1}^W X_i\left(\log (\hat{P}_{i j})-\log (\hat{Q}_{i j})\right)^2 \\ & =\sum_{i=1}^W \sum_{j=1}^W X_i\left(\vec{u}_j^T \vec{v}_i-\log X_{i j}\right)^2 \end{aligned}$$

注意到$X_i$不一定是最好的系数，更一般的形式为

$$\hat{J}=\sum_{i=1}^W \sum_{j=1}^W f\left(X_{i j}\right)\left(\vec{u}_j^T \vec{v}_i-\log X_{i j}\right)^2$$