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的距离。依次寻找到所有词对应的相近词距离，最终相加作为最终结果。

对于长度不同的例子时，会出现交叉项，如：

那么数学的角度怎么理解呢？先来看一下每个项代表的含义。

目标函数和条件如下：

我们要对 $c(i,j)$c(i,j) 进行加权求和，求出最小值。约束条件保证所有转移的权重之和与该词在文档中占的权重值相同。
在WMD的求解过程中存在什么问题呢？

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

Word Centroid Distance（WCD）：

根据三角不等式，文档d和d′之间的质心距离 $||Xd-Xd'||_2$∣∣Xd−Xd′∣∣2​ 为其WMD距离的下界（lower bound），WCD算法的复杂度为$O( dp )$O(dp)，WMD用WCD的计算来作为下界。

Relaxed word moving distance （RWMD）

RWMD即去掉了WMD中的一个约束条件，只留下一个约束条件。目标变成如下：

只考虑从文档出发转移到另一个文档的权重总和，不考虑另一个文档词语接收到的权重，那么很明显最优解将会是：

当找到最近的词i（距离j最近）时，权重是 $d_i$di​ ,距离j次相近和其他相近的权重为0。定义$j^{*}=argmin_{j}c(i,j)$j∗=argminj​c(i,j)，即词i与另一个文档中距离最小的词j，记为$j^{*}$j∗，对于单个词i来说距离为

因此， $T^*$T∗必能生成最小损失。计算该解仅需确定$j^{*}=argmin_{j}c(i,j)$j∗=argminj​c(i,j) ，可在欧氏word2vec空间中做最近邻搜索。对文档D中的每个词向量 $x_i$xi​ ，需要找到文档D′中的最相似的词向量 $x_j$xj​ ​。
若移除第一个约束，最近邻搜索过程相反，即对文档D′中的每个词向量 $x_j$xj​ ，需要找到文档D中的最相似的词向量 $x_i$xi​ ,令两者分别为$l_{1}(d,d^{'})、l_{2}(d,d^{'})$l1​(d,d′)、l2​(d,d′)，通过取二者中的最大值，可得到更紧致的下界，称为松弛WMD（Relaxed WMD，RWMD）：


从图中我们可以看出WCD作为下界，与WMD的差距还是很大的，RWMD比较接近与WMD但是计算较慢，怎么合理应用这两种算法？

预取和裁剪

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

1. 用 WCD 取离它最近的m个文档；
2. 计算前k个文档的 WMD；
3. 计算剩下文档的 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