喵喵爱编程

这个屌丝很懒，什么也没留下！

热门标签

Word2Vec原理_training complexity

作者：喵喵爱编程 | 2024-08-20 06:53:54

踩

training complexity

本篇不是入门型文章，仅记录关于word2vec的一点思考，欢迎大家一起讨论。为了更好地表达，本文会采用cs224n官网以及刘建平老师的博客中的一些图片，在下面的介绍中不再一一注明出处。

一、原始的word2vec模型架构

二、原始word2vec的改进

2.1 Hierarchical Softmax

2.2 Negative Sampling

一、原始的word2vec模型架构

论文Efficient Estimation of Word Representations in Vector Space

skipgram的训练任务是：根据中心词预测上下文
cbow的训练任务是：根据上下文预测中心词

需要注意的是，左图是一个训练样本，右图表示四个训练样本(wt,w(t-2)), (wt,w(t-1)), (wt,w(t+2)), (wt,w(t+1)),。

据身边的同学（包括我自己）反映，右图对新手非常的不友好，容易造成误解，以为输出是4个值，真实标签是“对应的四个词处是1，其他词表中的词都是0”，预测标签是“由softmax计算的词表中各个词的概率”，这样理解是不对的，因为损失函数用的是交叉熵，而交叉熵衡量的是两个分布之间的距离，显然真实标签并不是一个分布（和不是1，是4）。

为什么叫skipgram呢？因为会有一个window size，这个window在句子上不断移动来获得上下文词和中心词以构成训练样本，故叫skipgram。个人理解emmm

为什么叫CBOW(continuous bag of words)? bag of word直译是把一些词装进袋子里，这是一种离散表示且不考虑词序，而word2vec得到的embeddings是连续的向量，故称为CBOW。

复杂度分析（ training complexity）：

假设窗口大小为C，取当前词的前C个词与后C个词，与当前词一起构成一组训练样例，embedding size为D，vocab size为V，则

对于SkipGram，训练复杂度为 $O(C\times (D+D\times V))$ ，这里 $D = 1\times D$ 是embedding层的计算复杂度， $D\times V$ 是隐层到输出层的计算复杂度，也是复杂度的主要来源。

对于CBOW，训练复杂度为 $O(C\times D+D\times V)$

通过复杂度分析，可以得出两点结论，

embedding层的计算是简单的，直接将word id对应行的行向量(假定词向量矩阵为V行D列)取出作为其embedding，也就是隐层。计算复杂度主要来源于隐层到输出层的计算，一般vocab size是很大的，这使得计算非常的慢。
skipgram的复杂度高于cbow，这使得skipgram训练时间更长。

二、原始word2vec的改进

2.1 Hierarchical Softmax

在原始的word2vec中，隐藏到输出层的计算量很大，相当于一颗V叉树，叶子节点是vocab中的每个词，需要计算隐层向量与每个叶子节点的点积。

如果我们采用平衡二叉树，同样的，叶子节点是vocab中的词，其他节点都是一个二分类器，以决定走向左子树还是右子树。树的深度为 log(V) ，且我们仅需要计算根节点到真实值对应的叶节点的路径的概率，所以隐层到输出层的计算复杂度为 $D\times log_{2}(V)$ 。

如图，每个灰色的节点都是一个二分类器（逻辑回归分类器），叶子节点是vocab中的词，假定w2是output的真值，那我们就只需要让从根节点到w2这段路径的概率最大即可。因为是二分类器，在增大左子树的概率的同时，也会降低右子树的概率，所以，在增大到w2的概率的同时，会导致其他路径上的概率降低，这使得在训练过程中不仅会提高“看得见”词的概率，也会降低“看不见”词的概率。

进一步地，我们将二叉树改为Huffman树，让高频词拥有更短的路径长度，这样计算复杂度比平衡二叉树略有降低，但其实两者的复杂度还是在一个量级上的，也就是说Huffman树的平均树深约为 log(V) 。

Q1：为什么Hierarchical Softmax中只需要计算到w2的概率？
A1：我们知道，不论是原始的word2vec还是Hierarchical Softmax，所用的损失函数都是交叉熵，交叉熵要求预测分布是一个概率分布。原始的word2vec为了使得预测结果是概率分布采用了softmax来归一化，而Hierarchical Softmax本身的特性保证了各个叶子节点的概率和一定为1，无需做任何调整。在计算交叉熵的时候，其实真正有用的是真实值为1对应的项，其他项都为0，所以仅需要知道真值（w2）对应的概率即可。
Q2：原始的word2vec是否可以只计算一个节点的概率？
A2：不可以。因为要用softmax来使得各个词的概率和为1，所以需要计算隐层向量与vocab中每个词“相似度”。
Q3：构建二叉树的方法有哪些？
A3：huffman树仅需构建一次，且需要corpus上每个词的词频统计信息。所以第一步统计词频，第二步构建二叉树，采用最小堆的数据结构，或者数组的数据结构。如果用数组的话，要通过全局扫描来得到最小值和次小值。

2.2 Negative Sampling

Huffman树确实提高了效率，但如果遇到一个生僻词，那在前向传播计算概率的时候，就要在huffman树中向下走很久了。负采样可以解决这个问题，无论是生僻词还是高频词，负采样的计算复杂度都是一样的。与huffman树一样，都是利用了二元逻辑回归来求解模型参数

我们从负采样的损失函数说起，如下

显然，这是一个对数似然，还原为似然函数就是

$\prod _{i = 0}^k\sigma {(v_{Wi}{v_{WI}})^{yi}}{(1 - \sigma (v_{Wi}{v_{WI}}))^{1 - yi}}$

其中，i=0表示正样本，其他k个表示负样本。显然，这是让正样本(真实值)的概率越大越好，负样本(噪音)的概率越小越好。这里无需计算 |V| 个词的概率，只需要计算k+1个，且这k+1个词的概率和不是1。为什么呢？因为损失函数不是交叉熵了，变成极大似然了哈哈哈~

接下来，我们聊一聊负采样时除正样本外其他词被选中的概率p(w)

$\sigma {(v_{Wi}{v_{WI}})^{yi}}{(1 - \sigma (v_{Wi}{v_{WI}}))^{1 - yi}}$

这里U(w)表示unigram distribution,f(w)表示词w的词频，3/4是一个经验值。从p(w）可以看出，

p(w)是关于词频f(w)的增函数，所以高频词更容易被当做负样本。为什么这样做呢？个人理解如下：我们都知道，依照频率学派的观点，在没有任何先验知识的情况下，我们倾向于概率高的选择。这样一来，高频词更有可能被认为是真值，但实际上却不是真值。如果我们的分类器可以识别高频的负样本，那么识别低频的负样本就更加容易了，所以，选高频词作为负样本，能提高分类器的分类能力。
为什么取3/4作为幂？我们来看看和1相比的区别，（不妨画一下x和 ${x^{3/4}}$ 的函数图像对比一番），相比而言，3/4为幂实际上是一种平滑策略，让高频词贡献出一些出场机会给低频词，有点劫富济贫的意味~

最后，over。

三、 numpy实现word2vec

待更新

四、tensorflow实现word2vec

待更新

五、总结

skipgram对于低频词比cbow友好

两个模型都是local的，只使用了词的局部共现信息，没有使用整个语料库的统计信息

词向量不是模型训练的任务，而是为完成任务顺带得到的附属品，词向量和模型参数在训练过程中一起训练

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】