《From word embedding to document Distance》

该篇论文提出了一种新的计算句子相似度的方法wordmover distance，以及提升这种方法的计算效率的两种方法：word centroiddistance和Relaxed word moving distance。

一、word moverdistance 

(1)单词向量化表示方式

使用word2vec的向量化矩阵X∈R^dxn来表示有n个单词的词汇表，第i列表示在d维空间中第i个单词的向量。

(2)文档向量化

首先采用nBOW将文档表示为归一化的n维的词袋向量，用nBOW表示文档时每个单词的权重如图di所示，其中ci是出现频次，可能存在两个语义相似的文本由于所用词完全不同导致文档向量的非零部分分布在不同的部分的情况。例如：

（3）文档距离

将文档距离拆解成文档中各个词之间的距离,采用曼哈顿距离进行计算每个word2vec词向量之间的距离

由于每个单词有自己的权重，因此，可以将文档相似度问题转换为一个transportation问题，并且是earth mover's distance的一个特殊子问题。EMD问题的形式为：

其中，EMD问题的图如下：

在WMD问题中，可以将文档d的单词的权重看作工厂p的货物量，将另一个文档d’看作仓库Q，将单词Pi转换到单词Qi需要消耗的权重看作从工厂P中运出的货物量Tij，c(i,j)表示两个单词向量的曼哈顿距离。因此，WMD算法下的文档距离如下：

求解该距离的时间复杂度是O(p^3logp),其中p表示nBOW中向量的长度。可以将该式看作如下：

假设该nBOW*有m个单词，用Pi表示每个单词，则单词之间的转换矩阵如下：

 

二、word centroid distance

虽然通过WMD距离可以更准确的求解文本相似度，但是花费时间却很长，因此提出了对WMD的改进，用降低精确度的方法来降低时间复杂度

通过对两个文档之间的距离设置一个下限来过滤掉一部分文档，能够更快的搜索到k近邻个文档

word centroid distance的计算公式如下：

其中X是一个d*p维的矩阵，xi表示单词向量,d表示词向量的维度，p是nBOW的长度。 d是一个文档的p维的矩阵，如下：

WCD算法的复杂度是O(dp)

 

三、Relaxed word moving distance

该算法是丢弃下式中的其中一个约束条件分别得到下限。

当只考虑第一个约束时，相当于只要工厂把所有货物运输出去即可，则定义一个优化矩阵：

该式子表明工厂将全部的货物都运输到距离最短的那个仓库中，而不考虑仓库的容量。放在句子距离度量问题中可以看作对于文档d中的单词只要找到每个单词距离最近的d’文档中的单词即可，因此，可以将MWD距离做如下变换：

可以得到一个下限l₁(d,d’),由于c(i,j)已经固定，因此只需要找出T^*_i,j即可

 

再只考虑第二个约束条件，即只要仓库装满就行，则优化矩阵变成：

 

即不考虑工厂的货物量，而只是寻找一个和该仓库距离最近的工厂将自己填满即可

由此可以得到另一个下限l₂(d,d’)，同样只需要构造T^*_i,j

l_r(d,d’)=max(l1,l2)即为Relaxed WMD,该算法的时间复杂度是O(p^2)

 

三、使用

我们需要查询一个文档的k个近邻文档，首先需要将文档按照他们的WCD距离递增排序，然后计算前k个文档的WMD距离，随后，遍历剩下的文档，首先检查当前第k个最接近文档的距离是否超过了RWMD下限，如果超过了，则将该文档移除，否则，计算该文档的WMD距离并且更新k个最近的文档。由于RWMD是非常的tight，因此可以过滤掉95%的文档。如果不需要k近邻，遍历可以被限制到m<n个文档。我们将这个算法称为prefetch and prune。如果m=k则返回WCD距离中最接近的k个。如果m=n，则没有邻近的被过滤。

 

该过程相当于先选取k个比较可能相似的文档，再在剩下的文档中采用RWMD进行过滤后再计算WMD距离，然后不断更新前k个相似的文档列表，因此还可用于推荐系统等

 

实验中的算法参数都使用贝叶斯优化进行优化

 

四、WMD特点

1、没有参数，可以直接使用

2、将两个文档之间的距离拆解成独立单词之间的距离，并将word2vec的语义相似信息结合进文档距离矩阵中

3、结合了word2vec的向量化方法，使得检索准确率更高

 

 

 

参考链接：

https://www.cnblogs.com/shihuajie/p/5772130.html

http://ir.dlut.edu.cn/news/detail/362