本文是对论文From Word Embeddings To Document Distances的总结和code实现。该论文基于word2vec embedding 和EMD（Earth Mover's Distance）提出了一种新的计算文档距离的算法WMD（Word Mover's Distance）。旨在解决 Obama speaks to the media in Illinois 和 The President greets the press in Chicago 仅仅因词语拼写不同而导致距离很远的不合理现象。尽管这两个句子对应的词语在语义上是相近的。
本文的主要内容包括：
- WMD模型
- WMD模型的速度优化
- 总结
- Code
在WMD模型提出以前，计算文档相似度主要是使用词袋模型或TF-IDF。这两种方法都存在严重的数据稀疏问题，而且完成没有考虑词与词之间的语义关系。对意义相近但用词不同的文档无能为力。
Word Mover’s Distance（WMD）模型
MWD既考虑了词袋模型的词频也考虑了词与词之间的距离：
文档表示（nBOW）
WMD中文档表示就是归一化的词袋模型，文档向量各分量值形式化表示为： \[ d _ { i } = \frac { c _ { i } } { \sum _ { i = 1 } ^ { n } c _ { j } } \] 分子为词频，分母为文档总词数。以论文中的例句为例，去停后可表示为：
- D0：President greets press Chicago [0.25, 0.25, 0.25, 0.25, 0, 0, ...]
- D1：Obama speaks media Illinois [0, ..., 0.25, 0.25, 0.25, 0.25, 0, ...]
- D3：Obama speaks Illinois [0, .., 0.33, 0.33, 0.33, 0, ..., 0]
词转化损失（word travel cost）
利用word2vec词向量计算欧式距离得到： \[ c ( i , j ) = \| x _ { i } - x _ { j } \| _ { 2 } \] $c ( i , j ) $表示一个词转化为另一个词的损失。
文档距离
WMD文档距离是由文档表示（nBow）和词转化损失（word travel cost）共同作用得到的，计算方法为寻找两个文档中对应的词，累加各组对应词对的（词转化损失 * nBow对应的分量分到该词上的权重）。对应词的标准是\(c(i, j)\)最小的词，如Figure 1所示。
当比较的两个文档长度相同时，文档距离可以简单理解为： \[ W\!M\!D \ document \ distance = \sum _ {i=1}^ {n} d_{i} * min(c(i, j)) \] 但更通用的表示，即当比较的两个文档长度不同时，我们需要引入矩阵\(T \in R ^ { n \times n }\)来表示文档距离： \[ \sum _ { i , j = 1 } ^ { n } T _ { i j } c ( i , j ) \] 其中 \(T _ { i j } \geq 0\)，表示文档中的词\(i\)在多大程度上转化为另一个文档中的词 \(j\)，也可理解为文档中的词\(i\)在文档nBow表示中对应的分量有多少权重被分到另一个文档中的词\(j\)上。
举个例子，Figure 1中的\(D_{0}\)和\(D_{3}\)，当\(T\) 矩阵为如下情况时，\(D_{0}\)和\(D_{3}\)会产生如图中所示的对应关系： \[ \begin{array}{c|cccc} & \text{President} & \text{greets} & \text{press} & \text{Chicago}\\ \hline Obama & 0.25 & 0.08 & 0. & 0. \\ speaks & 0.08 & 0. & 0.25 & 0. \\ Illinois & 0.08 & 0. & 0. & 0.25 \\ \end{array} \]
还记得\(D_3\)的nBow表示，Obama对应的分量值为0.33，这里Obama被距离最近的词President 分走了0.25, 还剩0.08需要分配出去。图中的情况，greets是距离Obama第二近的词，于是0.08被分配给了greets。以此类推。
显然，两个文档长度相同时，\(T\) 除一一对应的词的位置是nbow分量值外，其他位置都是0.
注：Figure 1中\(D_0\)和\(D_3\)只是众多可能的对应关系的一种，并不是最优的对应关系。最优的对应关系如前面所说，寻找\(c(i, j)\)尽可能小的词对。一对多的情况下，按\(c(i, j)\)由小到大顺位取。
WMD模型
WMD模型的\(Obj\)： \[ \begin{split} \min _ { T \geq 0 } &\sum _ { i , j = 1 } ^ { n } T _ { i j } c ( i , j ) \\ subject\ to: &\sum _ { j = 1 } ^ { n } T _ { i j } = d _ { i } \quad \forall i \in \{ 1 , \ldots , n \} \qquad (1)\\ &\sum _ { i = 1 } ^ { n } T _ { i j } = d _ { j } ^ { \prime } \quad \forall j \in \{ 1 , \ldots , n \} \qquad (2) \end{split} \\ \] 条件（1）就是\(T\)的行元素相加和等于\(d_i\) 。如 Obama (0.33) = President (0.25) + greets (0.08) + press (0.) + Chicago (0.)。
条件（2）就是\(T\)的列元素相加和等于\(d_j\)。如Press (0.25) = Obama (0.) + speak (0.25) + Illinois (0.)。
（Figure2中例子\(president\)是不满足条件（2）的，下面优化部分会提到，其实只满足一个条件就可以）
从\(\min _ { T \geq 0 } \sum _ { i , j = 1 } ^ { n } T _ { i j } c ( i , j )\)可以看出，这是一个有条件的线性规划问题。所有线性规划问题都有最优解。
WMD模型的速度优化
Word centroid distance（WCD）
计算WMD的复杂度太高，为\(O ( p ^ { 3 } \log p )\)。WCD的结果是WMD的下限，它是一些简单的矩阵运算，复杂度为\(O (dp)\)。其推导过程如下： \[ \begin{split} &\sum _ { i , j = 1 } ^ { n } T _ { i j } c ( i , j ) = \sum _ { i , j = 1 } ^ { n } T _ { i j } \| x _ { i } - x _ { j } ^ { \prime } \| _ { 2 } \\ = &\sum ^ { n } \| T _ { i j } ( x _ { i } - x _ { j } ^ { \prime } ) \| _ { 2 } \geq \| \sum ^ { n } T _ { i j } ( x _ { i } - x _ { j } ^ { \prime } ) \| _{2} \\ = &\| \sum _ { i = 1 } ^ { n } ( \sum _ { j = 1 } ^ { n } T _ { i j } ) x _ { i } - \sum _ { j = 1 } ^ { n } ( \sum _ { i = 1 } ^ { n } T _ { i j } ) x _ { j } ^ { \prime } \| _ { 2 } \\ = &\| \sum _ { i = 1 } ^ { n } d _ { i } x _ { i } - \sum _ { j = 1 } ^ { n } d _ { j } ^ { \prime } x _ { j } ^ { \prime } \| _ { 2 } = \| X d - X d ^ { \prime } \| _ { 2 } \\ \end{split} \]
WCD的推导相对容易，上面推导中不等式的步骤是利用\(\sqrt a + \sqrt b \geq \sqrt{a+b}\) 得到的。
得到两个文档的WMD下限\(\| X d - X d ^ { \prime } \| _ { 2 }\)，可知这两个文档的距离一定大于这个值。在很多情况下，可以直接排除掉这些下限都已经很大的文档，免去进一步的运算，减少计算量。
Relaxed word moving distance （RWMD）
虽然WCD速度很快，但计算出来的下限相比真实值还是差距比较大的。RWMD通过分别去掉WMD中的一个条件来得到两个下限\(\ell _ { 1 } ( d , d ^ { \prime } )\)和\(\ell _ { 2 } ( d , d ^ { \prime } )\), 然后取\(\ell _ { r } ( d , d ^ { \prime } ) = \max ( \ell _ { 1 } ( d , d ^ { \prime } ) , \ell _ { 2 } ( d , d ^ { \prime } ) )\)。当去掉的是条件（2）时，RMWD形式化表示如下： \[ \begin{split} \min _ { T \geq 0 } &\sum _ { i , j = 1 } ^ { n } T _ { i j } c ( i , j ) \\ subject\ to: &\sum _ { j = 1 } ^ { n } T _ { i j } = d _ { i } \quad \forall i \in \{ 1 , \ldots , n \} \\ \end{split} \\ \] RWMD的复杂度为\(O(p^2)\)。（Figure 2的情况满足RWMD）
Prefetch and prune
- 计算所有文档与目标文档的WCD并对结果进行排序，选择前k个文档作为k-nearest-neighbour。
- 计算这k个文档与目标文档的具体WMD。
- 依次计算其他文档与目标文档的RWMD，并将其与第k个文档WMD进行对比，超过的可以直接prune掉。
- 如果没超过，计算该文档与目标文档的WMD并对k-nearest-neighbour进行更新。
总结
- WMD完美地将word2vec与传统的Bow结合起来，这在深度学习与传统机器学习算法结合方面做得都不是很好的今天，无疑是个很novel的idea.
- 在解决WMD复杂度过高的问题上，利用复杂度低很多的两个下限配合使用，既大大提高了速度，又没有损失精度。
代码实现
本文实现代码请见 https://github.com/Adline125/Similarity
开源的WMD实现有：
- gensim（python）调用pyemd的c扩展，使用fast EMD算法。
- Word Mover's Distance (WMD) from Matthew J Kusner 单纯形法实现
- Fast WMD有RWMD的实现。
参考文献
From Word Embeddings To Document Distances
文本距离类的其他资料
CIKM Cup 2018阿里小蜜短文本匹配算法竞赛 – 冠军DeepSmart团队分享
Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks