word2vec由google在2013年推出&＃xff0c;其中获取词向量的方法CBOW和Skip-gram模型在《Efficient Estimation of Word Representations in Vector Space》中进行了阐述和介绍&＃xff0c;高效训练模型的策略Hierarchical Softmax和Negative Sampling则在《Distributed Representations of Words and Phrases and their Compositionality》做了陈述。由于Mikolov发表的的这两篇论文不是很好理解&＃xff0c;所以可以参考Xin Rong的《word2vec parameter learning explained》&＃xff0c;也可以直接看peghoty在博客园的发表的文章《word2vec中的数学原理详解》。网上有大量关于word2vec的文章&＃xff0c;但主要还是和其数学原理相关的内容&＃xff0c;本文主要是阅读和解析Mikolov在github上开源的源码&＃xff0c;其中也参考了别人的博客以及py版本(如果对py比较熟的建议看这个&＃xff0c;感觉更清晰一些)的实现&＃xff0c;这部分会在文末进行列举。word2vec的源码里涉及到大量的文件读取&＃xff0c;构建词表和hash表的操作以及对应的查询、比较、排序等辅助函数&＃xff0c;这部分本文暂不做详细分析&＃xff0c;本文会专注于其中的Hierarchical Softmax&＃xff0c;Negative Sampling&＃xff0c;Skip-gram以及CBOW的实现中。一般我读源码主要从main函数开始&＃xff0c;因为这块包含了整个代码的运行流程&＃xff0c;从main函数入手&＃xff0c;再对每一步骤涉及的类和方法进行阅读。word2vec中涉及训练的代码在TrainModel中&＃xff0c;这部分的重点我认为是&＃xff1a;网络初始化参数模块和训练模块&＃xff0c;前者包括InitNet、CreateBinaryTree、InitUnigramTable&＃xff0c;后者则是对应代码里的TrainModelThread&＃xff0c;主要为CBOW和Skip-gram&＃xff0c;下面我将对这两块分别进行解析。
01
网络初始化参数
这一块内容主要涉及Huffman树和UnigramTable的的构建&＃xff0c;分别为后续的Hierarchical Softmax和Negative Sampling的前置基础工作。
1、InitNet
该部分主要初始化一个projection layer的网络结构&＃xff0c;其中vocab_size为词表长度&＃xff0c;layer1_size为输出的词向量长度&＃xff0c;如果使用Hierarchical Softmax&＃xff0c;即hs&＃61;1&＃xff0c;则会初始化一个vocab_size*layer1_size全0的辅助向量syn1&＃xff0c;用来存储构建好的Haffman树中的非叶子节点。若使用Negative Sampling&＃xff0c;则会初始化一个vocab_size*layer1_size全0的辅助向量syn1neg。syn0则为我们最后需要的词向量&＃xff0c;初始化为[-0.5/layer1_size, 0.5/layer1_size]区间内vocab_size*layer1_size长度的随机向量。具体的代码如下&＃xff1a;
void InitNet() { long long a, b; unsigned long long next_random &＃61; 1; a &＃61; posix_memalign((void **)&syn0, 128, (long long)vocab_size * layer1_size * sizeof(real)); if (syn0 &＃61;&＃61; NULL) {printf("Memory allocation failed\n"); exit(1);} if (hs) { a &＃61; posix_memalign((void **)&syn1, 128, (long long)vocab_size * layer1_size * sizeof(real)); if (syn1 &＃61;&＃61; NULL) {printf("Memory allocation failed\n"); exit(1);} for (a &＃61; 0; a 0) { a &＃61; posix_memalign((void **)&syn1neg, 128, (long long)vocab_size * layer1_size * sizeof(real)); if (syn1neg &＃61;&＃61; NULL) {printf("Memory allocation failed\n"); exit(1);} for (a &＃61; 0; a 2、CreateBinaryTree
该部分就是创建Haffman二叉树&＃xff0c;主要是为Hierarchical Softmax方法的实现提供相对应的数据结构基础。Haffman树建立的伪代码如下&＃xff1a;输入&＃xff1a;权值为(?1,?2,...??)的?个节点输出&＃xff1a;对应的Haffman树1)将(?1,?2,...??)看做是有?棵树的森林&＃xff0c;每个树仅有一个节点。&＃xff1b;2)在森林中选择根节点权值最小的两棵树进行合并&＃xff0c;得到一个新的树&＃xff0c;这两颗树分布作为新树的左右子树。新树的根节点权重为左右子树的根节点权重之和&＃xff1b;3) 将之前的根节点权值最小的两棵树从森林删除&＃xff0c;并把新树加入森林&＃xff1b;4)重复步骤2)和3)直到森林里只有一棵树为止。根据Haffman树的特性&＃xff0c;权值越高的词其二叉树上的路径越短&＃xff0c;即二进制编码越短&＃xff0c;且更靠近根节点&＃xff0c;这也符合我们的业务认知&＃xff0c;即越常用的词拥有更短的编码&＃xff0c;word2vec里创建Haffman树的代码如下。void CreateBinaryTree() { long long a, b, i, min1i, min2i, pos1, pos2, point[MAX_CODE_LENGTH]; char code[MAX_CODE_LENGTH]; long long *count &＃61; (long long *)calloc(vocab_size * 2 &＃43; 1, sizeof(long long)); long long *binary &＃61; (long long *)calloc(vocab_size * 2 &＃43; 1, sizeof(long long)); long long *parent_node &＃61; (long long *)calloc(vocab_size * 2 &＃43; 1, sizeof(long long)); for (a &＃61; 0; a &＃61; 0) { if (count[pos1] &＃61; 0) { if (count[pos1] 首先我们需要定义point和code&＃xff0c;其中point用来存储一个词到根节点的Haffman树路径&＃xff0c;code用来存储一个词的Haffman编码。代码里同时也定义了count数组、binary数组以及parent_node数组&＃xff0c;长度均为vocab_size*2&＃43;1, 其中count数组前vocab_size为Haffman树的叶子节点&＃xff0c;初始化为词表中全部单词的词频&＃xff0c;它后vocab_size为Haffman树中即将生成的非叶子节点的词频&＃xff0c;通过合并子节点的权值得到&＃xff0c;初始化为1e15。binary数组记录的是各个节点相对于其父节点的二进制编码&＃xff0c;parent_node则记录了每个节点的父节点。接着就是构建Haffman树&＃xff0c;注意下这里的输入的count数组的前vocab_size已经按照词频做了降序排序&＃xff0c;初始的pos1&＃xff0c;pos2分别为词表中词频最低词和第一个1e15的索引&＃xff0c;后面通过对比当前的pos1和pos2对应单词的词频大小&＃xff0c;来更新作为当前词频(包括合并后)最小和次小节点的索引min1i、min2i。这边以原始序列{&＃39;u&＃39;: 7, &＃39;v&＃39;: 8, &＃39;w&＃39;: 9, &＃39;x&＃39;: 10, &＃39;y&＃39;: 19}为例&＃xff0c;对应的初始化词频为[19, 10, 9, 8, 7]&＃xff0c;对应的count数组为[19, 10, 9, 8, 7, 1e15, 1e15, 1e15, 1e15, 1e15]。第一轮迭代&＃xff0c;a为0&＃xff0c;pos1为4&＃xff0c;pos2为5&＃xff0c;count[pos1]为7&＃xff0c;count[pos2]为1e15&＃xff0c;此时count[pos1]
第二轮迭代&＃xff0c;a为1&＃xff0c;pos1为2&＃xff0c;pos2为5&＃xff0c;count[pos1]为9&＃xff0c;count[pos2]为15&＃xff0c;此时count[pos1]
第三轮迭代&＃xff0c;a为2&＃xff0c;pos1为0&＃xff0c;pos2为5&＃xff0c;count[pos1]为19&＃xff0c;count[pos2]为15&＃xff0c;此时count[pos1] > count[pos2]&＃xff0c;min1i为5&＃xff0c;pos2递增为6&＃xff0c;count[pos1]为19&＃xff0c;count[pos2]为19&＃xff0c;count[pos1] &＃61; count[pos2]&＃xff0c;min2i&＃61;6, pos2递增为7&＃xff0c;count[5&＃43;2]被赋值为count[5]&＃43;count[6]&＃61;34。
第四轮迭代&＃xff0c;a为3&＃xff0c;pos1为0&＃xff0c;pos2为7&＃xff0c;count[pos1]为19&＃xff0c;count[pos2]为34&＃xff0c;此时count[pos1]
由于是构建Huffman树&＃xff0c;所以最多只需进行vocab_size-1次循环操作。整个迭代的过程就是获取最小count[min1i]和次小count[min2i]&＃xff0c;并合并(求和)&＃xff0c;然后重复这一步骤直至迭代结束。在每轮迭代中binary数组中索引为min2i会置为1&＃xff0c;即词频较低的为1&＃xff0c;较高的为0。parent_node里则会将每次迭代中索引为min1i和min2i的元素置为a&＃43;vocab_size。接着就是遍历词表里的所有单词&＃xff0c;并为每个词分配其在Haffman树中的路径和编码。需要注意的有&＃xff1a;设立临时变量b,主要是获取当前词在parent_node里的路径&＃xff0c;该路径也直接对应了binary里的索引&＃xff1b;
由于Haffman树一共有vocab_size*2-1个节点&＃xff0c;所以vocab_size*2-2为根节点&＃xff0c;代码里以此为循环的终止条件&＃xff0c;即路径走到了根节点&＃xff1b;
由于Haffman编码和路径是从根节点到叶子结点的&＃xff0c;因此需要对之前得到的code和point进行reverse操作, 路径那边也要减去vocab_size。
以上述的序列中的&＃39;w&＃39;为例&＃xff0c;对应的词频为9&＃xff0c;对应的索引为2&＃xff0c;即a&＃61;2&＃xff0c;之前的binary序列为[0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0]&＃xff0c;parent_node为[8, 6, 6, 5, 5, 7, 7, 8, 0, 0, 0]&＃xff0c;对应得出的w的code为[0, 1, 1]&＃xff0c;point&＃61;[2, 6, 7]&＃xff0c;由于Haffman路径中存储的中间节点编号要在现在得到的基础上减去vocab_size&＃xff0c;即不算叶子结点&＃xff0c;仅取单纯在中间节点中的编号&＃xff0c;所以此时的根节点的编号为(vocab_size*2-2) - vocab_size &＃61; vocab_size - 2&＃xff0c;具体在此例为3&＃xff0c;逆序后vocab[2].code为[1, 1, 0], vocab[2].point为[3, 2, 1, -3]。至此每个词对应的Haffman编码和路径均已计算完毕。3、InitUnigramTable
为词表中的每个词构建一个幂律分布(power law distribution)表&＃xff0c;用于后续的负采样&＃xff0c;这边对词频取0.75次幂实际上属于一种平滑策略&＃xff0c;缩小词与词之间的词频差距&＃xff0c;具体代码如下。void InitUnigramTable() { int a, i; double train_words_pow &＃61; 0; double d1, power &＃61; 0.75; table &＃61; (int *)malloc(table_size * sizeof(int)); for (a &＃61; 0; a d1) { i&＃43;&＃43;; d1 &＃43;&＃61; pow(vocab[i].cn, power) / train_words_pow; } if (i >&＃61; vocab_size) i &＃61; vocab_size - 1; }}初始化的table_size为1e8&＃xff0c;然后遍历词表, train_words_pow为每个词对应的词频cn^0.75的累加。接着计算单个词对于train_words_pow的比率d1&＃xff0c;如果a/table_size一直不超过当前词的d1的话&＃xff0c;i就不会递增&＃xff0c;这就意味着当前词会一直占据a&＃43;n-a个位置, 否则会累加更新d1的值&＃xff0c;累加的原因是不需要从头开始比较&＃xff0c;a位置一直往后&＃xff0c;对应的d1应该也在之前的基础上累加&＃xff0c;保持相对位置不变&＃xff0c;绝对位置的更新。这样每个词都会对应一段区间&＃xff0c;在同一个区间的词都是一样的&＃xff0c;所以在采样的时候&＃xff0c;只需指定neg个索引位置&＃xff0c;必然会取到neg个词。
如果词表的长度比UnigramTable小的话&＃xff0c;即UnigramTable未能填满&＃xff0c;则将未填满的部分用词表中的最后一个词来进行填充。
02
训练模块
无论是CBOW还是Skip-gram在代码里都使用了下面几个变量&＃xff0c;在此先对他们做个介绍&＃xff1a;neu1&＃xff1a;输入的词向量【在CBOW是窗口中各个词的向量和&＃xff0c;在skip-gram是中心词的词向量】&＃xff0c;长度为layer1_size&＃xff0c;初始化为0&＃xff0c;用于更新syn1&＃xff1b;
neu1e&＃xff1a;长度为layer1_size&＃xff0c;初始化为0&＃xff0c;用于更新syn0&＃xff1b;
alpha&＃xff1a;学习率&＃xff1b;
last_word&＃xff1a;记录当前扫描到的上下文单词索引。
1、CBOW
CBOW需要我们根据上下文的窗口词来预测中心词&＃xff0c;这里先计算窗口词向量的和并求均值&＃xff0c;cw为窗口长度&＃xff0c;建立起中心词和窗口词的关联。for (c &＃61; 0; c 1.1 使用Hierarchical Softmax进行训练
根据前文构建的Haffman树&＃xff0c;遍历从根节点到当前词的叶子节点路径中所有经过的中间节点&＃xff0c;l2为当前遍历到的中间节点的向量在syn1中的位置, f为syn1在l2处对应的neu1在layer1_size范围内的累加&＃xff0c;其实本质就是neu1和中间节点向量的内积。这边的codelen即为树深度&＃xff0c;循环的时候可以直接过滤掉上述例子&＃39;w&＃39;对应的point中的-3。接着就是对f做Sigmoid变换处理&＃xff0c;这里是维护了一个expTable数组&＃xff0c;我们可以根据索引直接查表得知变换的结果。然后再对f和之前得到的每个词的Haffman编码计算误差并进行梯度更新&＃xff0c;需要注意的是这里编码为1的节点会被定义成负类&＃xff0c;0为正类&＃xff0c;即真实label为1-vocab[word].code[d]&＃xff0c;最后就是更新neu1e和syn1对应位置的向量&＃xff0c;其中每一次迭代即为一次逻辑回归&＃xff0c;整体其实就是一个利用随机梯度提升来最大化对数似然函数的过程。for (d &＃61; 0; d &＃61; MAX_EXP) continue; else f &＃61; expTable[(int)((f &＃43; MAX_EXP) * (EXP_TABLE_SIZE / MAX_EXP / 2))]; g &＃61; (1 - vocab[word].code[d] - f) * alpha; for (c &＃61; 0; c 1.2 使用Negative Sampling进行训练
其中negative为负样本的数量&＃xff0c;当d为0即获取的是目标词&＃xff0c;指定其为正样本&＃xff0c;否则就从UnigramTable中随机抽取negative个负样本(不能和当前正样本一样)。这边的l2为syn1neg中目标单词的位置&＃xff0c;后面的基本和Hierarchical Softmax一致&＃xff0c;不再多做赘述。for (d &＃61; 0; d > 16) % table_size]; if (target &＃61;&＃61; 0) target &＃61; next_random % (vocab_size - 1) &＃43; 1; if (target &＃61;&＃61; word) continue; label &＃61; 0; } l2 &＃61; target * layer1_size; f &＃61; 0; for (c &＃61; 0; c MAX_EXP) g &＃61; (label - 1) * alpha; else if (f <-MAX_EXP) g &＃61; (label - 0) * alpha; else g &＃61; (label - expTable[(int)((f &＃43; MAX_EXP) * (EXP_TABLE_SIZE / MAX_EXP / 2))]) * alpha; for (c &＃61; 0; c 最后我们再根据得到的neu1e来即时地更新syn0&＃xff0c;从而获取最终训练得出的vocab_size*layer1_size的词向量。for (a &＃61; b; a &＃61; sentence_length) continue; last_word &＃61; sen[c]; if (last_word &＃61;&＃61; -1) continue; for (c &＃61; 0; c 2、Skip-gram
Skip-gram需要我们根据输入的中心词来预测该单词上下文窗口词&＃xff0c;代码里的last_word为当前待预测的上下文单词&＃xff0c;l1为当前单词的词向量在syn0的位置&＃xff0c;初始化neu1e为0。训练这部分大体和前面一致&＃xff0c;区别就在于前面是用neu1[c]来和中间节点向量的内积&＃xff0c;而这边直接用syn0[c &＃43; l1]替换neu1[c], syn0[c &＃43; l1]在这里为单个词的词向量&＃xff0c;而neu1[c]则为窗口词向量的平均。另外需要注意的是Skip-gram虽然是给定中心词来预测上下文&＃xff0c;但真正在训练的时候仍是用上下文预测中心词。for (a &＃61; b; a &＃61; sentence_length) continue; last_word &＃61; sen[c]; if (last_word &＃61;&＃61; -1) continue; l1 &＃61; last_word * layer1_size; for (c &＃61; 0; c &＃61; MAX_EXP) continue; else f &＃61; expTable[(int)((f &＃43; MAX_EXP) * (EXP_TABLE_SIZE / MAX_EXP / 2))]; g &＃61; (1 - vocab[word].code[d] - f) * alpha; for (c &＃61; 0; c 0) for (d &＃61; 0; d > 16) % table_size]; if (target &＃61;&＃61; 0) target &＃61; next_random % (vocab_size - 1) &＃43; 1; if (target &＃61;&＃61; word) continue; label &＃61; 0; } l2 &＃61; target * layer1_size; f &＃61; 0; for (c &＃61; 0; c MAX_EXP) g &＃61; (label - 1) * alpha; else if (f <-MAX_EXP) g &＃61; (label - 0) * alpha; else g &＃61; (label - expTable[(int)((f &＃43; MAX_EXP) * (EXP_TABLE_SIZE / MAX_EXP / 2))]) * alpha; for (c &＃61; 0; c 
代码里的其他一些tricks:读取文件时&＃xff0c;每行末尾加入了一个""&＃xff0c;便于训练。
如果词表大小超过上限&＃xff0c;则做一次词表删减操作,将当前词频小于min_reduce(初始为1)的进行删除&＃xff0c;该删除操作在一个while(1)循环里&＃xff0c;min_reduce一次循环累加1&＃xff0c;保证最大的单词数量不超过vocab_hash_size * 0.7&＃xff0c;代码设定的vocab_hash_size &＃61; 30000000&＃xff0c;即词表最多只能有2100万个词&＃xff0c;否则就会一直删除低频词&＃xff0c;直至满足这个条件为止, 而expTable的大小为1e8, 还是远超过2100万的&＃xff0c;所以不必担心Negative Sampling无法训练的问题。
在初始学习率的基础上&＃xff0c;随着实际训练词数的上升&＃xff0c;逐步降低当前学习率(自适应调整学习率)&＃xff0c;并保证学习率不低于starting_alpha * 0.0001。
对高频词进行随机下采样&＃xff0c;丢弃掉一些高频词&＃xff0c;类似平滑处理&＃xff0c;这样也可以加快训练速度。
句子长度超过MAX_SENTENCE_LENGTH&＃xff0c;则做截断处理。
行文至此&＃xff0c;word2vec代码里的核心部分基本分析完毕&＃xff0c;如对文章有异议&＃xff0c;可私信互相探讨&＃xff0c;技术之路道阻且长&＃xff0c;愿各位仍能保持初心&＃xff0c;不断进步&＃xff0c;谢谢。参考链接&＃xff1a;https://github.com/tmikolov/word2vec/blob/master/word2vec.c
https://github.com/deborausujono/word2vecpy
https://blog.csdn.net/EnochX/article/details/52847696
https://blog.csdn.net/EnochX/article/details/52852271
http://www.hankcs.com/nlp/word2vec.html
https://www.cnblogs.com/pinard/p/7160330.html
![110. Balanced Binary Tree [Easy] 平衡树/递归](https://img8.php1.cn/3cdc5/2481c/882/fac9995ab74e0cea.webp)
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有