机器学习 Embedding 之 Word2Vec

2014年的那篇 Efficient Estimation of Word Representations in Vector Space 第一次提出了将序列数据映射成向量的方法，自此也拉开了对于embedding技术的深度讨论。这篇文章将会总结word2vec背后的技术原理以及细节。

语言模型

N-gram模型

N-gram本质上是一个统计模型，它的思想很简单。假设一个长度M的词序列为 $w_1^M = {w_1, w_2, ..w_M}$ 那么我们有

P(W) = \prod_{m=1}^M P(w_m|w_1^{m-1})

上面这个条件概率的意思是第m个单词的概率由它之前的m-1个单词决定(一个句子内)。我们稍微把 $P(w_m|w_1^{m-1})$ 近似成 $P(w_m|w_{m-n+1}^{m-1})$ 。也就是说，下一个单词的概率只和之前的N个单词有关。 N-gram模型是一个N-阶的马尔可夫链，每一个状态只依赖之前的N-1个时刻，与更久远的历史无关。

在实际对语料库进行统计时，我们会采用以下近似

p(w_k|w_1, w_2, ..., W_{k-1}) \simeq \frac{count(w_{k- n + 1}, ... ,w_{k})}{count(w_{k-n+1}, ..., w_{k-1})}

一般N-gram模型我们会取N=3, 计算出所有概率。另外，n-gram模型中还有一个叫做平滑化的重要环节。试想如果某个组合的count为0，我们能认为概率为0吗？在这种情况下需要使用平滑技术。

总结起来，n-gram模型是这样一种模型，其主要工作是在语料中统计各种词串出现的次数以及平滑化处理。概率值计算好之后就存储起来，下次需要计算一个句子的概率时，只需找到相关的概率参数，将它们连乘起来就好了。

神经网络语言模型

词向量是训练神经网络的副产品，对于词汇表中的任一个单词，我们用一个低秩向量表示。训练一个以得到词向量为目标的神经网络，会从以下方面考虑

词语之间的相似性可以通过词向量来体现
相似的”的词对应的词向量也是相似的
概率函数关于词向量是光滑的，即词向量中的一个小变化对概率的影响也只是一个小变化。这样一来，对于下面这些句子，只要在语料库中出现一个，其他句子的概率也会相应的增大

A dog is running in the room
A cat is running in the room
The cat is running in a room
A dog is walking in a bedroom
The dog was walking in the room

常见的词向量表示方式有 one-hot representation 和 Distributed representation

one-hot representation

一种最简单的词向量方式是One-Hot编码，就是用一个很长的向量来表示一个词，向量的长度为词典的大小，向量中只有一个 1 ，其他全为 0 ，1 的位置对应该词在词典中的位置。但是这种方法存在一些问题

容易出现维灾
无法表达词和词之间的相似性
稀疏性无法保证有效训练存在训练不充分的问题

distributed representation

Distributed Representation最早是Hinton于1986年提出的，可以克服One-Hot Representation的上述缺点。其基本想法是：通过训练将某种语言中的每一个词映射成一个固定长度的短向量（当然这里的“短”是相对于One-Hot Representation的“长”而言的），所有这些向量构成一个词向量空间，而每一个向量则可视为该空间中的一个点，在这个空间上引入“距离”，就可以根据词之间的距离来判断它们之间的语法、语义上的相似性了。Word2Vec中采用的就是这种Distributed Representation 的词向量。

word2vec

word2vec本质是一个分类任务，中心词和上下文词的共现性来刻画词和词之间的相似性。损失函数可以从最大似然函数或者最小交叉熵(二者是一致的，似然函数maxmize可以通过添加符号做形式变换整理成最小交叉熵的形式)。同时机器学习使用的交叉熵损失函数和信息论的交叉熵略有不同

在机器学习看来，信息论里的交叉熵仅仅是针对一个样本的交叉熵，在机器学习进行优化时，会把所有样本的交叉熵值做一个平均，即机器学习的交叉熵损失函数定义为：假设有N个样本 $J = -\frac{1}{N}\sum_{n=1}^N H(p_n, q_n)$
因为交叉熵常用于解决分类问题，而分类问题(我们一般说分类问题，是指单标签多分类问题)的概率本质是计算类别变量的广义的伯努利分布，所以机器学习采用的是交叉熵的离散形式 $J = -\frac{1}{N}\sum_{n=1}^N \sum _{i=1}t_i\ln{s_i}$ . 其中， $t_i$ 是期望的类别标签， $s_i$ 是模型对第 $i$ 个类别计算得到的score，通常在计算损失之前，我们会用激活函数(sigmoid 或者 softmax)加以转换。

为什么说分类问题的概率本质是计算类别变量的广义伯努利分布呢？

因为对于分类问题，假设模型的输出层上只有2个输出结点，而且是一个二分类单标签问题，如果输出层用符号 $Y$ 表示，那么Y服从0-1分布(是二项分布的特例，或称伯努利分布，二元分布)，即随机变量 $Y$ 的样本空间有两个样本点(分别对应输出层的两个输出结点)，每个样本点就是一个类别。我们希望机器学习模型训练出的分布是某个类别的概率为1，另一个类别的概率为0。推广到多分类单标签问题，那么 $Y$ 服从广义的伯努利分布(是多项式分布的特例，或称Category分布，范畴分布，类别分布，Multinoulli分布)

伯努利分布及其极大似然和交叉熵

假设伯努利分布 $Y \in \{0, 1\}$ , 并假y=1的概率为 $P(y=1) = p$ ，那么其概率质量函数(Probability Mass Function，PMF): $P(Y|p) = p^Y(1-p)^{1-y}$ , 假设 $D =\{y_1, y_2, \dots y_N \}$ 是来自 $Y$ 的并且样本容量为N的样本，那么似然函数为:

\begin{equation} P(D|p) = \prod_{i = 1}^{N} p^{y_i}(1-p)^{1 - y_i} \end{equation}

在机器学习中，我们会创建参数为 $\theta$ 的模型，所以之前的概率 $p$ 会写成一个函数的形式 $p(Y = 1|\theta, x)$ ,那么最新的似然函数是

\begin{equation}\begin{split} P(D|\theta, X) &= \prod_{i = 1}^N p(Y=1|\theta, x_i)^{y_i}(1 - p(Y=1|\theta, x_i))^{1-y_i} \\ \end{split}\end{equation}

所以我们从PMF得到对数似然函数(log-likelyhood):

\begin{equation}\begin{split} L(\mathbf{\theta}|D,X) &= \log{\prod_{i = 1}^N p(Y=1|\theta, x_i)^{y_i}(1 - p(Y=1|\theta, x_i))^{1-y_i}} \\ &= \sum_{i = 1}^N y_i \ln{p(Y=1|\theta, x_i)} + (1 - y_i)\ln{(1 - p(Y=1|\theta, x_i))} \\ \end{split}\end{equation}

下面我们将说明最大似然函数和最小交叉熵损失其实是同一个损失函数，一般的我们把机器学习模型输出的结果记为 $\hat{y}$

\begin{equation}\begin{split} \theta &= \mathop{\arg\max}_{\theta} \ \ \sum_{i = 1}^N y_i \ln{p(Y=1|\theta, x_i)} + (1 - y_i)\ln{(1 - p(Y=1|\theta, x_i))}\\ &= \mathop{\arg\max}_{\theta} \ \ \sum_{i = 1}^N y_i \ln{\hat{y}_i} + (1 - y_i)\ln{(1 - \hat{y}_i)} \\ &= \mathop{\arg\min}_{\theta} \ \ -\sum_{i = 1}^N y_i \ln{\hat{y}_i} + (1 - y_i)\ln{(1 - \hat{y}_i)} \\ &= \mathop{\arg\min}_{\theta} \ \ \sum_{i=1}^N H(y_i, \hat{y}_i) \end{split}\end{equation}

广义伯努利分布及其极大似然和交叉熵

广义伯努利分布又被称做categorical分布，它的一般形式如下

\begin{equation}\begin{split} P(X_k=1|\theta_1,\theta_2, \dots, \theta_K) &= \prod_{k=1}^K \theta_k^{x_k} \\ \sum_{k=1}^K \theta_k &= 1 \\ x_k \in {0, 1}, \sum_{k=1}^K x_k &= 1 \\ \end{split}\end{equation}

我们常用one-hot向量表示选中的category, 同样假设 $D =\{y_1, y_2, \dots y_N \}$ 是来自 $Y$ 的并且样本容量为N的样本。 PMF函数为

\begin{split} P(Y|p_1,p_2, \dots, p_k) &= \prod_{i=1}^K p_i^{y_i} \\ y_i &\in \{0, 1\} \end{split}

引入模型参数那么新的似然函数为

\begin{equation} P(D|\theta, \mathbf{X}) =\prod_{i=1}^N \prod_{j=1}^K p_j(\theta, x_i)^{y_j} \end{equation}

其对数似然函数

\begin{equation}\begin{split} L(\theta|D, X) &= \sum_{i=1}^N \sum_{j=1}^K y_i^{(j)}\ln{p_j(\theta, x_j)} \\ &= \sum_{i=1}^N \sum_{j=1}^K y_i^{(j)}\ln{\hat{y}_i^{(j)}} \end{split}\end{equation}

其目标优化函数

\begin{equation}\begin{split} \theta &= \mathop{\arg\max}_{\theta} \ \ \sum_{i=1}^N \sum_{j=1}^K y_i^{(j)}\ln{\hat{y}_i^{(j)}} \\ &= \mathop{\arg\min}_{\theta} \ \ -\sum_{i=1}^N \sum_{j=1}^K y_i^{(j)}\ln{\hat{y}_i^{(j)}} \\ &= \mathop{\arg\min}_{\theta} \ \ \sum_{i=1}^NH(y_i, \hat{y}_i) \end{split}\end{equation}

稍微小结一下:

最大似然函数和最小交叉熵都是描述的同一个损失函数
机器学习中的多分类问题是本质是一个广义伯努利分布(categorical分布)

候选采样candidate sampling

在word2vec论文中提出了两种模型，Continuous Bag-of-words Model 和 Continuous Skip-gram Model，俩者的主要区别在于输入和输出。CBOW输入是上下文词，输出是中心词。SG正好相反。在开始讲模型之前还要多铺垫一个知识，candidate sampling。

在机器学习中，经常用一个softmax层来处理多分类任务, 输出是一个one-hot编码向量。

\begin{equation} \begin{split} \hat{y}_i &= \frac{e^{z_i}}{\sum_{j=1}^K e^{z_j} } \\ J &= -\sum_{i=1}^K y_i\ln{\hat{y}_i} \\ &= -\ln{\frac{e^{z_{pos}}}{\sum_{i=1}^K e^{z_i}}} \\ &= -z_{pos} + \ln{\sum_{i=1}^K e^{z_i}} \end{split} \end{equation}

假设 $z = -\xi{(w)}$ , 那么

J = \xi{(w_{pos})} + \ln\sum_{i=1}^K e^{-\xi{(w_i)}}

注意上面式子的理解, $w_{pos}$ 是对应的正例(label值为1的)。那么对其求导可以得到

\begin{equation}\label{eq:gradent} \begin{split} abla_{\theta}J &= abla_{\theta} \xi{(w_{pos})} + abla_{\theta}\ln\sum_{i=1}^K e^{-\xi{(w_i)}} \\ &= abla_{\theta} \xi{(w_{pos})} + \frac{1}{\sum_{i=1}^K e^{-\xi{(w_i)}}} abla_{\theta}\sum_{i=1}^K e^{-\xi{(w_i)}} \\ &= abla_{\theta} \xi{(w_{pos})} + \frac{1}{\sum_{i=1}^K e^{-\xi{(w_i)}}}\sum_{i=1}^K e^{-\xi{(w_i)}} abla_{\theta}{-\xi{(w_i)}} \\ &= abla_{\theta} \xi{(w_{pos})} - \sum_{i=1}^K\frac{e^{-\xi{(w_i)}}}{\sum_{i=1}^K e^{-\xi{(w_i)}}} abla_{\theta}{\xi{(w_i)}} \\ \end{split} \end{equation}

上述公式 $\ref{eq:gradent}$ 中，说明了两件事

$abla_{\theta} \xi{(w_{pos})}$ 是关于正样本的梯度，可以理解为对目标词的正面优化
剩下的右边部分是所有样本概率对应梯度的累加和(想一想为什么有个负号是不是值越小对应概率越大?) 可以理解为其它词汇的负向优化。在基于采样的优化当中，我们不需要计算所有类别的累加，只需要通过采样求到 $abla_{\theta}{(\xi{(w_i))}}$ 在分布的期望即可，这个分布指 $p{(w_i|c)}$

\sum_{i=1}^K\frac{e^{-\xi{(w_i)}}}{\sum_{i=1}^K e^{-\xi{(w_i)}}} abla_{\theta}{\xi{(w_i)}} = \sum_{i=1}^K p(w_i|c) abla_{\theta}{\xi{(w_i)}} = \mathbb{E}_{w_i \sim p}[ abla_{\theta}{\xi{(w_i)}}]

那么接下来的问题就变成了如何准确的计算梯度在概率分布 $p(w_i)$ 上的期望:

\mathbb{E}_{w_i \sim p(w_i)}[ abla_{\theta}{\xi{(w_i)}}]

Importance Sampling

关于采样这块，经典书籍PRML有对其完整的介绍，我们直接给出importance sampling的具体做法，以后我会把所有的samling做一个归纳和总结

\begin{split} r(w) &= \frac{e^{\xi{(w)}}}{Q(w)} \\ \mathbb{E}_{w_i \sim p} & \simeq \frac{r(w_1) abla_{\theta}{\xi{(w_1)}} + \dots + r(w_m) abla_{\theta}{\xi{(w_m)}}}{r(w_1) + \dots + r(w_m)} \\ & = \frac{\sum_{i=1}^m r(w_i) abla_{\theta}{\xi{(w_i)}}}{\sum_{i=1}^mr(w_i)} \end{split}

其中 $Q(w)$ 是一个一元分布(比如一个均匀分布)

impoatance sampling 可以把不可计算的期望变得可算，但是似乎还没有减少计算量，还有其它办法来减少计算吗？

Noise Contrastive Estimation

在NCE中，完全推翻上述方法并从试图从另外一个角度来解决多分类问题loss计算的问题——我们能否找到一个损失函数用于替代原来的损失计算，从而避免softmax中归一化因子的计算。

NCE的基本思想是将多分类问题转换成为二分类问题，从噪音分布中采样，减少优化过程的计算复杂度。它是importance Sampling的改良升级方法。基本思想是将最终问题转换为一个二分类代理问题，将target词和非target词做一个二分类任务标签。通常我们将非target词叫做noise examples，即噪声数据。而这些noise样本会服从某个noise分布Q(w),这个Q(w)需要我们人工引入。相对的，我们的target词也是来自于一个分布，这个分布我们通常叫做emprical分布，即经验分 $\tilde{p}(w|c), \tilde{p}(c)$ 。我们的目的就是要学习参数 $\theta$ , 使得我们计算得到的 $p_{theta}(w|c)$ 无限逼近经验分布 $\tilde{p}(w|c)$ 。

下面来看如何得到新的二分类问题的训练集

从经验分布即原数据集 $\tilde{p}(c)$ 中采样得到context词c
从经验分布即原数据集 $\tilde{p}(w|c)$ 中采样一个正确的样本w，即target词，标签记为d=1 从noise分布中采样K个noise样本，即非target词，标签记为d=0

给定context词 (d,w)的联合概率为

\begin{equation} p(d, w|c) = \begin{cases} \frac{K}{1+K} * Q(w), & \text{if d = 0} \\ \frac{1}{1 + K} * \tilde{p}(w|c), &\text{if d = 1} \end{cases} \end{equation}

利用条件概率公式，可以将上述概率式子转换为d给定w和c的条件概率公式

\begin{equation} \begin{split} p(d=0|w, c) &= \frac{p(d=0, w|c)}{p(w|c)} = \frac{ \frac{K}{1+K}*Q(w)}{\frac{1}{1+K}*\tilde{p}(w|c) +\frac{K}{1+K}*Q(w)} = \frac{K*Q(w)}{\tilde{p}(w|c) + K*Q(w)} \\ p(d=1|w, c) &= \frac{p(d=1, w|c)}{p(w|c)} = \frac{ \frac{1}{1+K}*\tilde{p}(w|c)}{\frac{1}{1+K}*\tilde{p}(w|c) +\frac{K}{1+K}*Q(w)} = \frac{\tilde{p}(w,|c)}{\tilde{p}(w|c) + K*Q(w)} \end{split} \end{equation}

NCE通过学习 $p_{\theta}$ 来逼近替代 $\tilde{p}(w|c)$ ，而学习的过程就是去最大化上述条件概率式的过程。

说到这里，貌似NCE还没解决做除法的高成本问题，目前为止只是通过增加一些noise负样本将目标函数做了转化。因此NCE还引入了两个假设。

将分母 $z_{\theta}(c)$ 近似估计为一个参数 $z_c$ ,这样对任意一个样本context词c来说，都只引入了同一个参数。

对于神经网络参数繁多的情况，当我们令 $z_c$ 固定为1时，能够有效地减小参数的数量，同时鼓励模型对输出进行自标准化。

引入上述两条假设后，重写概率公式 $\tilde{p}(w|c)\approx \frac{e^{s_{\theta}(w, c)}}{\sum_{w^{'}} s_{\theta}(w^{'}, c) }$

此时

\begin{equation} \begin{split} p(d=0|w, c) &= \frac{K*Q(w)}{e^{s_{\theta}(w, c)} + K*Q(w)} \\ p(d=1|w, c) &= \frac{e^{s_{\theta}(w, c)}}{e^{s_{\theta}(w, c)} + K*Q(w)} \end{split} \end{equation}

假设我们的原始语料样本为T，接下来就是将所有样本的条件概率结合起来，同时应用log函数，防止数据下溢，得到我们的目标优化函数(针对单个样本)

\begin{equation}\label{eq:nceloss} \begin{split} J &= \ln{p(d=1|w, c)} + K * E_{w^{'} \sim Q} \ln{p(d=0|w, c)} \\ &= \ln{p(d=1|w, c)} + K * \sum_{i=1, w^{'} \sim Q}^K \frac{1}{K}\ln{p(d=0|w, c)} \\ &= \ln{p(d=1|w, c)} + \sum_{i=1, w^{'} \sim Q}^K \ln{p(d=0|w, c)} \end{split} \end{equation}

上述式子中加法的前一项很简单没问题，但是后一项求解期望的计算量还是比较大的，需要在给定context词c条件下，在词库V中引入的noise分布中采样生成一个负样本，并计算概率的期望值，对整个词库还是有一个次遍历。因此最后一步，NCE使用了Monte Carlo估计来替代这个概率期望。这样就不需要遍历整个词库了，只需要从Q分布的部分词集计算就可以了。

negative sampling

上面的NCE可能还是有些复杂，因此有的学者又在此基础上做了简化，Mikolov在2012年的paper上介绍了在word2vec中使用的采样方法——Negative Sampling，又叫负采样。

基本思想在于：每采样一个target词，就采样k个非target词（即负样本）。可以看到他跟NCE的基本思想是类似的，但是具体实现的时候又有不同。

不同于NCE，负采样在定义p(d|w,c)时采取了更加简单的实现：

\begin{equation} \begin{split} p(d=0|w, c) &= \frac{1}{e^{s_{\theta}(w, c)} + 1} \\ p(d=1|w,c) &= \frac{e^{s_{\theta}(w, c)}}{e^{s_{\theta}(w, c)} + 1} \\ \end{split} \end{equation}

其实它与NCE的概率式子是有联系的，即在NCE中，令K=|V|,且Q分布是一个均匀分布，那么就可以得到负采样的式子。最后列一下负采样的目标函数

\begin{split} J &= \ln{p(d=1|w, c)} + K * \sum_{i=1, w^{'} \sim Q}^K \frac{1}{K}\ln{p(d=0|w, c)} \\ &= \ln{\sigma{(s_{\theta}(w, c))}} + \sum_{i=1, w^{'} \sim Q}^K \ln{\sigma{(-s_{\theta}(w^{'}, c))}} \end{split}

所以最终我们的优化目标函数长这样(针对一个batch N个样本)

\begin{equation} \begin{split} \mathop{\arg\max}_{\theta} & \frac{1}{N}\sum_{( w, c \in T)}( \ln{\sigma{(s_{\theta}(w, c))}} + \sum_{i=1, w^{'} \sim Q}^K \ln{\sigma{(-s_{\theta}(w^{'}, c))}} )\\ \mathop{\arg\min}_{\theta} & - \frac{1}{N} \sum_{( w, c \in T)} (\ln{\sigma{(s_{\theta}(w, c))}} - \sum_{i=1, w^{'} \sim Q}^K \ln{\sigma{(-s_{\theta}(w^{'}, c))}}) \end{split} \end{equation}

抛一次硬币，正面朝上的概率，这是伯努利分布。
抛 $n$ 次硬币，正面朝上出现了 $m$ 次的概率，这是二项分布。
抛一次骰子，第 $k$ 面朝上的概率，这是categorical分布。
抛 $n$ 次骰子，第 $1$ 面朝上出现了 $m_1$ 次，第 $2$ 面朝上出现了 $m_2$ 次…第 $k$ 面朝上出现了 $m_k$ 次的概率，这是多项分布。

关于Word2Vec若干问题的思考

Word2Vec两个算法模型的原理是什么，网络结构怎么画？如果仔细浏览一下论文附带的C源码。会发现不论是CBOW模型还是skip-gram模型，都是用context(也就是上下文词)作为输入，中心词word(也就是论文里提到的中心词)作为输出。唯一的差别就在于CBOW取了context词的平均。这其实是一种朴素的思想: 环境决定结果。所以context输入，中心词word输出
怎么做的subsampling subsampling的做法是对最原始的序列根据概率做discard，然后再根据pair的方式，生成样本对。这样做的原因是一方面可以打击过热，另一面引入了一些其它的“化学反应”。这就是为什么先做了discard然后做pair，否则我们先做pair再discard，就不会出现一些离得稍为远一些的词组成的pair。根据C源码，先discard再pair。
我们到底应该把那个矩阵当作需要的词向量呢我提出几个关键词，共现，交叉熵。那么对于一个输出矩阵来说，如果其中的两个向量相似，说明它们的context上下文有相似的pattern(比如有共现的context词和非context词)，同样的对于输入矩阵来说，如果其中两个向量相似，说明在他们代表的含义空间里相似，这个含义可能就是:这两个向量有共现的中心词和非中心词。对于CBOW方法来说，输出矩阵还是可以用上面所说的理解方式去理解，输入矩阵由于取了平均值观上不是很好理解了(含义空间很奇怪)。最后，我的观点,不论是CBOW还是SG, 输入矩阵和输出矩阵都可以作为词向量，但是含义空间各不相同，输出矩阵可能更好理解一点。
怎么确定discard和负采样的采样函数这里面用了带有parameter的经验公式

\begin{equation} \begin{split} p(w_i) &= \sqrt{\frac{z(w_i)}{0.001} + 1} * \frac{0.001}{z(w_i)} \\ n(w_i) &= \frac{z(w_i)^{0.75}}{\sum_{j=0}^n (z(w_i)^{0.75})} \end{split} \end{equation}

word2vec有哪些缺陷 Word2Vec只考虑到上下文信息，而忽略的全局信息； Word2Vec只考虑了上下文的共现性，而忽略的了彼此之间的顺序性；

小结

明确word2vec的思想，以及它的损失函数
通过negative sampling方式把需要大量的分母计算规避，加速计算，是一种candidate sampling思想的运用
注意在构造样本时的采样概率函数构造

参考: