本文的说明基于 Skip-gram 模型训练的原始形式,建议读者请先阅读文档——Skip-gram 模型。
概述
Skip-gram 模型的原始训练采用 Softmax 函数将一系列分数转化成为一个概率分布,其中用于归一化的分母的计算涉及到语料库中的所有单词(参考以下 Softmax 公式),因而计算代价非常昂贵。优化 Skip-gram 模型时,我们想避免这样计算 Softmax。
另外,每次反向传播时:对于矩阵 W,只更新目标词输入向量 vw;而对于矩阵 W',所有单词的输出向量 v'w 都会更新,其中绝大多数单词与目标词和上下文词都没有关系。矩阵 W 和 W' 通常非常大,神经网络越大,需要的训练样本越多,梯度下降法也越慢。模型训练优化的一个方向就是限制单词输出向量更新的个数。
实际上,原始 Skip-gram 模型的训练方式几乎无法应用到实际场景中。T. Mikoliv 等人在提出 Skip-gram 模型的同时提出几种优化方法:分层 Softmax(Hierarchical Softmax)、负采样(Negative Sampling)以及高频词二次采样(Subsampling of Frequent Words)。这些方法不仅能提高训练速度,还能提升嵌入向量的质量。本文将具体解释 Node2Vec 和 Struc2Vec 等图嵌入算法都采用的负采样技术和高频词二次采样。
相关资料如下:
- T. Mikolov, I. Sutskever, K. Chen, G. Corrado, J. Dean, Distributed Representations of Words and Phrases and their Compositionality (2013)
- X. Rong, word2vec Parameter Learning Explained (2016)
负采样
正样本和负样本
自然语言处理领域中,如果两个单词是一对上下文词与目标词,就是正样本(Positive Sample),否则就是负样本(Negative Sample)。
负采样
负采样是一种采样方法,即采样得到一个训练样本(一个目标词和一个上下文词)作为正样本送入模型训练时,选择若干其他单词与目标词组合作为负样本。应用负采样后,Skip-gram 模型每次训练时只更新正样本和负样本单词的输出向量。
在描述 Skip-gram 模型原始形式时,我们用到了包含 10 个单词的语料库:
graph, is, a, good, way, to, visualize, data, very, at
以及一个句子:
Graph is a good way to visualize data.
滑动窗口大小为 1 且目标词为 is 时,其中一个训练样本是 (is, a),这是一个正样本。通过从语料库中随机选择其他单词与目标词 is 组合即形成负样本,假设我们随机选择 3 个负样本如下:
对于正样本,isContext 列为 1,代表这是一个目标词上下文词的组合;对于所有负样本,isContext 列均为 0,代表这些都不是目标词与上下文词的组合。值得留意的是,对于其中一个负样本 (is, graph),虽然 graph 的确在 is 的窗口范围内,但对于正样本 (is, a) 来说,它仍被视为一个负样本。
关于负样本数量,T. Mikoliv 等人建议小数据集选择 5~20 个,大数据集选择 2~5 个。
如何选取负样本
选择负样本单词的基本原则是:在语料库所有句子中越常出现的词,被选择的概率就越高。然而,如果仅考虑词频,高频词会被过度选择,而低频词几乎不会被选择。为了平衡这一点,T. Mikoliv 等人根据经验提出取词频的 3/4 次方,即
其中 wi 表示第 i 个单词,f(wi) 表示 wi 的词频,V 是语料库中不重复的单词总数,Pn(wi) 表示选取 wi 作为负样本的概率,下标 n 代表噪声(Noise),Pn 也称为噪声分布(Noise Distribution)。
举个极端的例子,假设语料库只有两个单词,词频分别为 0.9 和 0.1,经过上述公式处理后,它们被选择的概率则变成 0.84 和 0.16。
模型训练——负采样优化形式
前向传播过程
以训练样本 (is, a) 为例:
从隐藏层到输出层,只有正样本单词 w0 与选择的 3 个负样本单词 w1、w2 和 w3 的输出向量参与计算。应用负采样技术时,Skip-gram 模型采用如下的 Softmax 函数:
其中 h 是从矩阵 W 直接提取出来的目标词输入向量,v'wi 是来自矩阵 W' 的上下文词输出向量,ui = v'wih 表示两个向量的内积。从直观上理解,两个单词越相似,它们的向量内积(余弦距离)就越大,因而 yi → 1,反之 yi → 0。
负采样中 Softmax 函数的形式非常像 Sigmoid 函数,但由于 v'wi 和 h 都是需要训练的参数,所以不能称之为 Sigmoid。
损失函数
原始 Skip-gram 模型的训练目标是输出目标词的上下文词,应用负采样技术后,模型的训练目标改变了——我们期望模型能区分出正样本与负样本。具体来说,正样本 w0 对应的模型输出为 1(代表“是”),其他负样本对应的模型输出为 0(代表“否”):
因此,模型的训练目标是最大化 y0 和所有 1 - yi,假设选取 k 个负样本:
其中 i=1,2,...,k。经过上述推导得出模型的损失函数 E 为:
计算 E 对 u0 和 ui 的偏导数,并将结果定义为 e0 和 ei:
e0 和 ei 与 Skip-gram 的原始训练方式中的 ej 很类似,相当于用输出值减去期望的判断结果:
反向传播过程
推导出损失函数 E 以及 e0 和 ei 后,负采样 Skip-gram 模型的反向传播过程就很简单了。读者可参考 Skip-gram 模型的原始形式,唯一不同的是——更新输出层到隐藏层的矩阵 W' 时,只更新一个正样本和 k 个负样本单词对应的输出向量。
高频词二次采样
对于语料库来说,有些词出现地频率很高,比如 in、the、a 等词,这些高频词造成的问题有:
- 高频词通常不能提供太多的语义信息,例如,man 和 handsom 同时出现时就比 man 和 the 同时出现时提供的语义信息要多。
- 我们会得到很多包含高频词的训练样本,远超过为了训练这些词的词向量所需的样本数,实际上会进行大量不必要的计算。
因此,T. Mikolov 等人提出在采样过程中以一定的概率丢弃单词,且词频越高的单词被丢弃的概率越大。例如,丢弃例句“Graph is a good way to visualize data.”中的单词 a 后,这个句子的采样结果不会包含以 a 为目标词或上下文词的训练样本。具体来说,一个单词被丢弃的概率为:
其中 wi 表示第 i 个单词,f(wi) 表示 wi 的词频,t 是设定的阈值,通常在 10-5 左右。取 t = 0.006 时,假设单词 a 在语料库中的词频为 0.03(没错,0.03 是一个很高的词频),则 a 被丢弃的概率为 0.817;当一个单词的词频小于等于 t 时,该单词则绝对不会被丢弃。
注意,二次采样是在滑动窗口采样过程中进行的,不要与负采样混淆。
对应到图上,高频词就相当于有很多邻居的超级节点。一个节点的邻居越多,能为每个邻居节点提供的信息就越少。例如,在社交网络中,用户 A 有 10000 个好友,用户 B 只有 10 个好友,对于他们的共同好友 C 来说,与用户 B 的好友关系更具价值。