Press "Enter" to skip to content

From Word Embeddings To Document Distances 阅读笔记

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

作者:张贵发

 

研究方向:自然语言处理

 

本文主要解决文本相似度问题,在word2vec, BOW的基础上提出了WMD模型(Word Mover’s Distance),主要思想是将A文档中的每个词,通过最小距离的转移到B文档中对应的词,最终将每个距离相加,作为衡量两个文档的距离。WMD是无超参数的,而且可解释性高。在一些nlp任务中取得了不错效果。

 

背景介绍:

 

解决这类问题的常见思路如下:

 

文档最常用的两种表示方式BOW和TF-IDF。但是,这些特性通常不适合文档距离,因为它们经常接近正交性,它们无法捕捉单词之间的距离。

 

特征分解 如LSI Latent Semantic Indexing通过特征值分解求解词袋矩阵得到语义特征空间  生成模型

 

如LDA,尽可能可能将相似词分组为主题,并将文档表示为这些主题的分布 其他,如mSDA,CCG等 Word2Vec Embedding

 

WMD是基于word2vec的欧式距离来计算文档的距离的。我们首先要知道什幺是word2vec。

 

word2vec是一种词向量

 

Word的相似性来自与周围的word

 

可以直接下载已经与训练好的word2vec词向量

 

一种训练方式是根据当前词,预测周围的词,数学上的表达即使得给定当前词时,周围词的概率最大,目标函数如下:

 

可以捕捉到word之间的距离信息,语义相同的word,映射到向量的空间,也是相近的。看一个简单的例子。1、”king brave man” 2、”queen beautiful woman” 窗口大小为1时,我们有这样的训练数据:

在这里插入图片描述

在输入中,周围的单词成为网络的目标,通过训练得到如下结果,语义相相近的词被映射到的区域也是相近的。而且还可以进行简单的语义计算。 king – man + woman =queen [1,1] – [1,3 ]+ [5,7]      =[5,5]

 

WMD

 

WMD使用了归一化的BOW。给定例子如下:

 

D0: The President greets the press in Chicago

 

D1: Obama speaks to the media in lllinois

 

D2: The band gave a concert in Japan

 

D3: Obama speaks in lllinois

 

首先需要进行的处理是去除停用词,然后进行bow的归一化如下:[President ,greets,  press,  Chicago, Obama, speaks  media,lllinois, band ,gave, concert  Japan]

 

D0:  President greets  press Chicago [0.25 ,0.25 ,0.25 ,0.25,0,0,…]

 

D1: Obama speaks media  lllinois  [0,…, 0.25 ,0.25 ,0.25 ,0.25 ,0,0,…]

 

D2:band gave  concert  Japan [0,…, 0.25 ,0.25 ,0.25 ,0.25]

 

D3: Obama speaks  lllinois [0,…, 0.33 ,0.33 ,0.33,0 ,0,…,0]

 

我们不需要零值,进行去除。

 

D0:  President greets  press Chicago [0.25 ,0.25 ,0.25 ,0.25]

 

D1:Obama speaks media  lllinois  [0.25 ,0.25 ,0.25 ,0.25]

 

D2:band gave concert  Japan [ 0.25 ,0.25 ,0.25 ,0.25]

 

D3: Obama speaks  lllinois[0.33 ,0.33 ,0.33,0]

 

我们寻找每个词对应最相近的词作为该词的距离。如Obama最相近的是President,那幺我们将计算他们之间的距离作为这对pair的距离。依次寻找到所有词对应的相近词距离,最终相加作为最终结果。

 

对于长度不同的例子时,会出现交叉项,如: 那幺数学的角度怎幺理解呢?先来看一下每个项代表的含义。 目标函数和条件如下: 我们要对  进行加权求和,求出最小值。约束条件保证所有转移的权重之和与该词在文档中占的权重值相同。在WMD的求解过程中存在什幺问题呢?

计算两个文档之间的 WMD 距离相当于求解一个大型的线性规划问题,要是用它来做 kNN  就比较耗时了。文章接下来便考虑了 WMD 两个计算比较方便的下界,方便在kNN 的时候做加速,如果当前待检查文档跟中心 query 文档的 WMD 下界已经大到可以确定它不在 ,query 文档的kNN 列表里,那就直接扔掉而不用再花时间求当前文档的 WMD 距离了。

 

Word Centroid Distance(WCD):

 

根据三角不等式,文档d和d′之间的质心距离为其WMD距离的下界(lower bound),WCD算法的复杂度为,WMD用WCD的计算来作为下界。

 

Relaxed word moving distance (RWMD)

 

RWMD即去掉了WMD中的一个约束条件,只留下一个约束条件。目标变成如下: 只考虑从文档出发转移到另一个文档的权重总和,不考虑另一个文档词语接收到的权重,那幺很明显最优解将会是: 当找到最近的词i(距离j最近)时,权重是,距离j次相近和其他相近的权重为0。定义,即词i与另一个文档中距离最小的词j,记为,对于单个词i来说距离为 因此,必能生成最小损失。计算该解仅需确定,可在欧氏word2vec空间中做最近邻搜索。对文档D中的每个词向量,需要找到文档D′中的最相似的词向量  。若移除第一个约束,最近邻搜索过程相反,即对文档D′中的每个词向量  ,需要找到文档D中的最相似的词向量,令两者分别为,通过取二者中的最大值,可得到更紧致的下界,称为松弛WMD(Relaxed WMD,RWMD): 从图中我们可以看出WCD作为下界,与WMD的差距还是很大的,RWMD比较接近与WMD但是计算较慢,怎幺合理应用这两种算法?

 

预取和裁剪

 

最后是如何利用这两个下界做所谓的 prefetch and prune 来为kNN   加速:给定 query 文档\mathbf{d}后,

 

 

用 WCD 取离它最近的m个文档;

 

计算前k个文档的 WMD;

 

计算剩下文档的 RWMD,如果某个文档的 RWMD 大于 k-NN 列表中第k个文档的 WMD 就扔掉,不然就计算它的 WMD。如果发现在 k-NN 列表中就更新 k-NN 列表,不然也扔掉。

 

 

实验:

 

实验主要比较7种文档表示baseline:,BOW、TFIDF、BM25 Okapi、LSI、LDA、mSDA、CCG 在不同数据上的错误率。 上图中展示在不同数据集上KNN分类的错误率,除了ohsumed中WMD与LSI的错误率持平,WMD在其他的数据集中都是低于其他方法的。 上图展示了相对于原始的WMD,利用下界后的提升速度。

 

总结与展望:

 

WMD在文档的相似度计算中确实取得了一定进展,具有如下优点:

 

效果出色:充分利用了word2vec的领域迁移能力

 

无监督:不依赖标注数据,没有冷启动问题

 

模型简单:仅需要词向量的结果作为输入,没有任何超参数

 

可解释性:将问题转化成线性规划,有全局最优解

 

灵活性:可以人为干预词的重要性

 

缺点:

 

BOW,没有保留语序信息

 

不能很好的处理词向量的OOV(Out of vocabulary)问题

 

处理否定词能力偏差

 

处理领域同义词互斥词的能力偏差

 

在WMD中,向量d的每一位代表词在文本中的词频进行归一化,因此在排除出现次数的影响因素的情况下,不同词对于文本的贡献是一样的。但实际上在一条文本中,不同词的重要性是不一样的,因此我们可以尝试使用tf-idf与bm25进行进一步优化。

 

5. 参考文献

 

WMD: http://proceedings.mlr.press/v37/kusnerb15.pdf ↩  理解WMD算法:https://supernan1994.github.io/nlp/wmd1.html 文本相似度度量:https://zhuanlan.zhihu.com/p/76958536 https://www.zhihu.com/question/33952003

原文链接:

 

https://blog.csdn.net/mr2zhang/article/details/104874561

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。