Word embedding综述与回顾(之一)---word2vec模型与PMI分解

适合读者:对word2vec有概念上的了解, 希望有细节上的掌握以及更深一步理解的研究人员, 工程师。

早先和人聊天,曾经聊过一次自然语言方面深度学习方法的发展和影响, 虽然从word2vec之外,nlp的神经网络方法也已经成为业界的主流, 但是与图像, 语音等领域相比, 始终还是差点意思,christopher maning在CS224N中提到语言是不同于图像, 语音的信号系统, 可以认为是一种符号\类别\离散系统。

想想也是,一般来讲都认为, 语言是人类独有高级认知系统, 语言之秘似乎就代表着人工智能中最艰深的问题。

在我自己看来,深度学习在自然语言领域最重大的贡献,word2vec算一个, 这个工作直接给后续一系列的任务奠定了基础, 甚至说是起到了改变研究范式的作用也不为过。

seq2seq算一个, 这个工作直接让机器翻译等等序列标注问题有了一个能用的框架, 而且将把这个问题推向了应用化。

除此之外, 虽然领域中各种模型层出不穷, 但是论影响力的广度和深度, 以及从思想上来讲的深刻性, 似乎都差着一星半点。

最近刷emnlp, 看到emnlp2017又有一些很有趣的在word embedding上作文章的paper, 于是就想把这个方向的一些成果和研究梳理一下。

word2vec.

word2vec由mikilov于2013年提出, 虽然之前已经有了一些关于词的向量表示的工作, 例如使用svd分解, 但是其效果都不太好。

word2vec包括两个算法, skip-gram和CBOW, 其基本思想是一个词的意思, 可以由这个词的上下文来表示。 相似词拥有相似的上下文, 这也就是所谓的离散分布假设(distributional hypothesis)。

术语定义, 例如一句话, “I want to go home”, 中心词为"to", 上下文词为"I",  "want",  "go", "home"。

对于skip-gram来说, 我们是通过中心词来预测上下文词的概率。对于CBOW来说, 我们是通过上下文词来预测中心词的概率 。

CBOW

初始化

拿到一篇文章, 先扫一篇文章, 建立辞典, 然后将辞典中的所有词进行初始化, 初始化为一个N维向量(实际使用中, 300到500不等), 这样得到一个d * |V| 的一个矩阵, 重复这个操作, 得到一个同样size, 但是不同值的矩阵。这是因为在word2vec中, 对于输入的embedding和输出的embedding使用不同的编码, 由于同一个词, 即可能是上下文, 又可能是中心词, 故而做此处理。

训练

输入: 以相临的5(即所谓的滑动窗口, 窗口大小为超参数 ,可设)个词为一个样本, 那么上下文就是第0, 1, 4, 5个词在词典中的索引, 假设这个索引为7, 12, 6, 8.

输出, 一个|V|* 1的概率向量, 每个位元表示中心词正好是这个辞典中这个位置的词的概率。例如在辞典中第三个词为"absorb", 那么p3=0.017, 就表示模型认为中心词为absorb的概率为0.017.

过程,拿到输入上下文的索引后,在输入embedding矩阵中查表, 得到第[7, 12, 6, 8]列,于是我们得到了四个向量,然后将这四个向量进行平均, 得到一个context vecter.

再取到输出embedding矩阵中中心词的向量, 在这个例子中, 假设中心词"to"在辞典中的第1487位, 那么就取输出embedding矩阵中第1487列。 求这个向量和content vector的乘积, 将这个乘积在所有词上做softmax.

如上图所示, 其中m为2, 也就是滑动窗口size的一半减1,wc代表中心心词, 第一行是指, 我们需要在给定上下文的情况下,最小化中心词的条件概率。
第二行, 我们将上下文使用输入embedding矩阵向量化并求平均, 将中心词使用输出embedding矩阵向量化。
第三行, 表示其在整个辞典上建模的softmax概率。

回顾一下整个思想, word2vec的想法是, 使用一个(准确来说是两个)高维向量空间来对词进行建模。 每个词即为向量空间中的一个点。 使用向量的dot product来衡量两个点之间的距离, 然后根据这个距离来最大化条件概率。

在这个模型中, 两个embedding矩阵为参数, 最后求一个最大似然, 也就是最小化其negative log likelihood。

skip-gram

skip-gram模型与CBOW相似,不同在于, skip-gram是使用中心词来预测上下文的词。
惟一值得注意的是, 中心词只有一个, 而上下文的词有四个, 那么如何建立这种一个对四个的对应关系, 在这里mikolov使用的是朴素贝叶斯假设, 也就是认为在给定中心词的情况下, 上下文词之间是相互独立的。
于是我们有这样的结果:

negative sampling

上面两个公式在实际计算的时候有一个问题,因为最后我们是对整个辞典上求softmax, 那也就意味将, 每过一个样本, 我们都要在整个辞典上算一次全部词向量和当前中心词的点积。 这个计算量太大了。
因此, 在论文中, 使用negative sampling这样一个技巧来处理这个问题。

其思想就是, 我们做一个负样本, 可以理解成随机语料, 于是每次训练的时候, 我们就有一个正样本和若干个负样本,我们让正样本的预测概率尽可能大, 而让负样本预测概率尽可能小, 通过负样本的引入, 将本来建立在整个辞典上的一个|V|分类问题, 转换成一个建模在正负样本上的一个二分类问题。 具体来说:

如上图, 当D等于1时, 即样本来自于真实语料, 当D等于0时, 样本来自于随机语料, 我们要使如果样本是真实样本, 那么概率就尽可能大, 如果样本来自随机语料, 那么概率就尽可以小(也就是D=0尽可能大)

这种转换中中涉及到一个很有意思的点, 就是softmax多分类概率和sigmoid二分类概率的等价性, softmax即是sigmoid, 参见CS229.

在生成负样本时, 我们使用Pn(w), 也就是决定要不要sample出某个词作为负样本,使用Pn(w)=freqency^(3/4)
即以词的unigram频率的3/4次方。
其意图是:

于是像is这样的高频词,在处理之后, 生成的概率还是较高, 但是变化不大, 而像bombastic这样的低频词, 其生成的概率就提高了三倍之多。

word2vec还使用Hierarchical Softmax来解决softmax计算量过大的问题, 思路是将词典挂在一棵哈夫曼树的叶结点上, 然后将一个词的softmax, 转换为这个词与这棵树上从根结点到词的父结点每个结点向量的点积的方向加权的sigmoid乘积。 这里就不多说了。

word embedding与矩阵分解的内在一致性

2014年, Yoav Goldberg在其《Neural Word Embedding as Implicit Matrix Factorization》 分析得出结论, word2vec其实质就是对语料的word-context的PMI矩阵进行分解 ,让我们来仔细看看这个过程:

上图是skip-gram同时进行negative-sampling之后的损失函数, 其中w为中心词, c为上下文, 这个损失函数是定义在整个语料上的(也就是跑完一个epoch), 因此要对中心词和上下文都进行求和符运算,k是指对于一个中心词进行多少次negative-sampling, 生成多少个负样本,Cn为negative-sample出来的负样本的上下文词。#(w, c)是指一个(w, c)的词对,在语料中出现的次数。

假设在真实语料由三句话组成, 分别是"what i am",   "fine. but what is that", “so Lucy, what are you doing about”, 那么what作为中心词就只有两次,分别是

样本1:  "."   "but"   "what"   "is"   "that"

样本2:"Lucy"  "."  "what"   "are"    "doing"

在以what作为中心词时, 我们negative sample出这样一个句子:

样本3:"about"   "am"   "what"  "fine"  "is"

作为上下文词,what出现1次, 分别为:

"what"   "are"   "you"   "doing"  "about"

公式1

我们进行第一次变换, 第一行只是简单地把求和符拆开, 第二行之所以可以进行如此变换的原因是因为在negative sampling的时候,是针对每一个中心词来做的, Cn的次数生成只与Pd也就是negative-distribution有关, 所以第二项对于c来说是个常数, 于是sum(#(w, c)) when c belong to Vc, 就等于#w, 这里#符号代表着在语料中的计数。
公式2

我们把注意力集中在公式1的第二部分, 进行再一步的变换, 在这次变换之后,negative-distribution的期望写成其分布原本定义的形式, 这里的Pd, 就是上面negative-sample小节中的Pn, 注意在这篇论文中为了简化起见,Pd, 直接用了基于频率的unigram distribution, 和mikolov的原文不太一样, 不过这里并不影响最终的结论, 只需要把这个#(cN)换成#(cN)^(3/4)就可以了。
这个变换的意思, 是指将negative-sample出来的上下文做一个更细的区分, 将那些正好在真实语料的上下文词集合中出现过的上下文词写出来做为公式的第一部分,在这个例子中, ("what", “is”)句对, 就属于即在真实上下文, 中心词对中出现过, 也在negative-sample中出现过的应该, 归到上面公式的第一种部分, 而(“what”, "fine")就属于只存在于negative-sample中的情况, 应该归到公式中的第二部分。

将上面的公式1和公式2合并, 得到如下的变换:

也就是说, 现在我们暂时只考虑在语料中出现过的(w, c)词对。对于这种词来把loss单独写出来。也就是只考虑("what", "is")这样的词对。令x = w . c, 然后再求偏导


就得到了上面的式子。
然后再令这个式子的偏导为零, 很容易能够求得:

最后, 把式子拆开, 就得到了。

这里就非常有意思了, 在第一个对数符号里包的那一堆东西, 恰恰就是广为人知的point-wise互信息公式。

最后我们来回溯一下, 在skip-gram中, 我们学到了两个矩阵, 输入embedding矩阵和输出embedding矩阵, 分别用来编码中心词和上下文词, 我们在skip-gram的原始形式中, 做向量的点积, 然后用这个点积来做softmax, 在做点积时, 我们实际就是取了, 这两个矩阵的某一行和某一列, 做点积, 那么如果把输入embedding矩阵表示为W, 输出embedding矩阵表示为C, 我们就得到了这样的结果:

也就是说, skip-gram模型的实质, 其实就等同于, 我们拿到了语料之后, 先进行了一个全局扫描, 然后建立了一个行为W, 列为C, 每个位元的值为PMI(w, c)的这么一个矩阵, 然后对这个矩阵进行全局减log(k), 这里k就是negative-sample时的次数(在这个例子中k=1),  就得到了一个矩阵M, 我们对这个M进行分解, 分解之后的W, C, 就是我们所谓的词嵌入矩阵, 或者称谓为lookup table.

 

参考文献:

Turney, P. D., & Pantel, P. (2010, March 5). From Frequency to Meaning: Vector Space Models of Semantics. arXiv.org. http://doi.org/10.1613/jair.2934

Levy, O., & Goldberg, Y. (2014). Neural Word Embedding as Implicit Matrix Factorization. Nips.

Mikolov, T., Sutskever, I., 0010, K. C., Corrado, G., & Dean, J. (2013). Distributed Representations of Words and Phrases and their Compositionality. CoRR Abs/1003.1141, cs.CL.

Mikolov, T., Chen, K., Corrado, G., & Dean, J. (2013, January 17). Efficient Estimation of Word Representations in Vector Space. arXiv.org.

https://web.stanford.edu/class/cs224n/lecture_notes/cs224n-2017-notes1.pdf

The Brain vs Deep Learning

段落大意

本文我也没有读完, 因此只能做一个简单的摘要, 大体来说, 文中在讨论之前风行一时的所谓奇点理论, 当然曾经有王威谦等人对库兹韦尔进行扒皮处理, 但是那种扒皮更多的建立在对其资历的质疑上. 而对于理论的具体扒皮则论述不多.

库兹韦尔的理论主要建立在对大脑的计算能力的估计上, 并通过摩尔定律(芯片计算能力第十八个月翻一番)的估计, 得出计算机在有生之年, 计算能力将达到人脑, 从而实现智能这样的判断.

文章谈到大脑模拟计划的问题, 目前的大脑模拟, 其思路是首先建立神经元的连接(依照大脑), 然后随机神经元的脉冲, 并通过目前对神经活动的了解, 逐步地优化神经脉冲, 当这些神经脉冲能够收敛到和大脑的活动状态类似的情况下, 就认为这种模拟是成功.
这种模拟有三个问题, 第一是无法难特定的科学假说, 第二是模拟并没有模拟生化层面的大脑活动, 第三也是比较重要的一点, 这种模拟对我们认知大脑的功能并没有起到多大的助益, 因为这种模拟是宏观的, 所以我们无法从中分离和提取出一个解释框架, 我们也无法从中提取让这种模拟完成, 识别苹果和梨这样的任务.

接下来, 文章提到, 库兹韦尔对大脑的计算复杂度的计算已经过时了, 神经科学的发展近两年来突飞猛进, 2005年之前我们的神经学的知识只占我们现在所有的神经科学知识的0.098%, 因此库氏的估计方法很多是错误的, 现在来计算大脑的神经复杂度的, 应该做新型的计算.

接下来, 文章一步一步地开始使用新的数据开始分析大脑的计算复杂度, 同时在第一步, 将这种计算与已有深度学习中的神经网络的架构进行对比. 先后分析了, 下丘脑和脑皮层和神经元数目, 类型, 连接数目. 大脑的运算的维数估计, 中间结点维数估计. 等等. 后面我也看得比较草草, 就不细说了. 看这张图, 也许大体就明白精华所在.

brain_complexity

我的AI学习史

接触这个领域的时间并不长,到现在也称不上入门,但是也有些经历,也许说出来可能给相同阶段的童鞋们一些借鉴。

关于学习的动机

为什么在这样一篇谈学习线路的文章里要首先谈学习的动机,原因在于学习或者说工作和职业在深入之后希望做出一些成果的话都仍然是一件非常需要投入的事情,没有这样的动机,hinton, lecun等几位大神不可能在神经网络几次陷低谷的时候仍然在这个领域深耕并推动这个领域的发展。
我在接触AI之前兴趣非常驳杂(现在也并没有好多少),在人文社科和自然科学领域都有一点接触,于是很长时间内,在各个领域之间跳来跳去,遇到Ai之后,感觉到这门学科的思维范式以及跨领域性可以把之前对计算机,心理学,经济学,哲学的非常多的思考贯通起来,而且这门学科中的很多内容都是如此好玩,因此才确定入坑.

关于学习的路径

我的学习路径是这样的:

<用nltk进行自然语言处理(书籍)> —> <cs181.1伯克利人工智能课程> —> <coursera斯坦福机器学习课程> —> <cs229,斯坦福机器学习讲义> —> <一个文本分类的project> —> <统计学习方法 李航> —> <PRML> & <cs224d 斯坦福自然语言处理课>

这其中也读了不少论文, 看了不少的博客和技术文章, 跟了不少的小项目, 但是都比较零散.

DraggedImage

这本书当时读主要作用是打下了python编程的基础, 我是从这本书开始接触python的, 关于机器学习的语言问题, 从现在看来, java、python、scala、R、c-plus-plus应该是之后主要的几门语言, 其中java和c-plus-plus偏向工程化应用, scala主要是spark这个工具带起来的, R纯研究目的, python则跨研究和工程两大类, 可用的包最多, 语法简单易上手, 算是刚开始入坑的不二之选; 另外这本书中顺带也讲了自然语言处理的一些基本方法, 课后题中有很多的非常不错的小题目. 大家可以参照一看.
DraggedImage-1

<cs188伯克利人工智能课程>

需要重点推一下这门课, 这门课给出整体的框架, AI都有哪些主要问题, 主要的学科范式是什么, 如何对一个问题进行建模, 我当时学习的时候, edx平台只有前半部分, 现在已经是完全版的archive.
这门课也是我在跟过的公开课中体验最好的一次, 当然时间的投入也比较长, 作业相对难一些.这门课最好的地方在于, 它的作用从前到后, 几乎是在一个一个大的游戏项目的框架下进行的, 跟着课程一步步走, 能够较快地进入到一个大型项目的协同开发的路子上, 这种经验是非常可贵的, 相比之下, cs229的课程作用使用的大多是matlab代码, 几个文件解决一个理论问题. 从实践性到深入程度与这门课都不可相提并论.
pacman-show
上图就是这门课强化学习的一个作业, 基于强化学习做的pacman小游戏, 其中pacman的行为完全是通过强化学习在随机经验中学习出来的. 图不太清楚, 大家凑合着看吧.

coursera ng课程与cs229讲义

这两个可以放在一起说, 因为都是ng的东西. 吴恩达童鞋的coursera课程应该是机器学习入门最多的推荐了. 吴童鞋的讲课实在是深入浅出, 把一个东西讲得非常透彻(曾经听过吴童鞋演讲, 他初任教职的时候讲课全校排名倒数, 不得不感叹人要用心做一件事, 也是耶风挡不往)
ng课程的内容大家说得够多, 顺便推一下cs229, cs229的比coursera课程要难了很多, 更偏理论推导, 而且会讲到线性指数族, 强化学习, EM算法等等更多更深的内容, 由于和cousera课程的内容有一部分重合之处, 和coursera课程参考着看更好, 而且有概率,线代,高斯等等补充材料. 也方便快速地过一下基础.

DraggedImage-2
如果这门课能够好好地刷完的话, 机器学习就算是入门了. 整个领域的方法论就算完全掌握了, 掌握的好的话, 独立完成一些项目就没有问题了. 去各大公司面试什么的, 应该也是OK.

PRML & 统计学习方法

这两本书也放在一起说了, 需要说的是这两本书, 我还没有读完, 但是啃PRML应该是每个有志于机器学习的童鞋必须要做的一件事, 此书确实非常经典, 但是也非常难啃, 具体应该如何啃, 方法放到后面说.
DraggedImage-3
对于统计学习方法而言, 这本书写作的方法更像我们之前读过教科书, 非常的简洁, 但是李航老师对这些问题的讲解仍然清楚, 虽然是薄薄的一本小册子, 料却十足. 最近写knn, 优化的时候, 仍然是从这本书的kd树中得到的思路.

cs224d

这个已经是自己的研究方向了, 比较个人化, 只捎带提一句就好.
提一下深度学习, 深度学习近两年非常火, 机器学习和深度学习的关系到底应该怎么摆, 是否有了深度学习就可以不用机器学习了? 想必是一些人心中的疑问.
其实我对这个问题并没有多少发言权(毕竟入行时间不长), 但是从个人体会出发, 深度学习从长远来看必然会发挥越来越大的作用, 但是即使它解决了表示的问题, 在实际工作中, 大量的任务, 还是需要使用机器学习的方法来进行探索, 聚类, 简单的分类, 特征工程, 无论是在哪个任务中, 出现的频次都非常高, 而这些活如果都使用深度网络来实现, 其代价和成本实在是太大, 而且深度学习的模型本来是比较复杂的, 数据量如果不大到一定程度, 使用深度学习并无必要而且容易过拟合.

关于学习的一点心得.

从接触这个领域到现在, 算算已经过了两年半的时间, 除去中间被各种事情打断的时间, 自己的学习和工作应该已经有近两年, 但是对于这个领域仍然不敢说是入门, 主要在于这个领域每一个点的背后都是有着数学支撑的, 到底怎样算是对机器学习入了门呢, 拿到一个问题, 能够找到合适的算法包解决它? 能够架设一个分布式平台实现大数据规模的机器学习? 能够优化模型, 在数学上优化新算法? 上述每一个问题都需要长期扎实的学习和钻研.

一个最大的想法是:
一定要在代码, 工具, 数学, 论文之间找到一个平衡. 这个领域吸引人的东西很多, 像vanpik这样的数学家和jeff dean这样的工程之神都在这个领域中, 中间更有ng, hinton这样的人物, 这些大神们的背景也正像黑客与画家一书中所谈的那样, 计算机是个框, 什么都可以往里装, 工程师, 数学家, 黑客, 计算机科学家看起来好像都是同一个title, 在相似的title之下, 找准自己的定位的长期的发展方向是非常必要的.

但是同时, 如果要实现什么东西, 无论是优秀的工程实践也好, 牛叉的科研成果也罢, 工程能力和学术能力都是需要的, 无非是这两者之间的谁多谁少的平衡问题.

所以在学习时, 从一个算法的数学证明, 到复杂度计算, 到算法的实现, 到工具平台化的抽象, 这几个部分也需要一个平衡和侧重, 建议是在学习的时候, 也能够从几个不同的点来学习.
举例来说, 对于knn, 掌握knn的数学证明, sciki-learn中的包使用, kd树的优化方法, 能够分析其算法复杂度(例子不太好…), 这样间杂着学习, 理论和实践相互替, 才能够更地对这个算法有比较透彻的了解, 同时也需要对数据集的数据特性做一些探索.

写在最后

我入行不久, 造诣也并不算深, 厚着脸皮写下这篇文章, 无非是想也许正好有处在相似阶段的童鞋确实想入坑, 那么这篇文章也许能够有一定借鉴作用.
借用ng童鞋的话, ai是一门回报非常大的学科, 无论是对机器的认识, 对人自身的认识, 对自然问题的认识, 甚至人的存在本质, 自由意志, 都可以在门学科中得到更深入的洞见和收获.
更何况, 它还是一门新生的学科. 五十年历史过去, 却连学科(人工智能)的定义都没有, 这个天地也是大为可为. 期待与大家一起努力.