从单词嵌入到文档距离 ：WMD一种有效的文档分类方法

文档分类和文档检索已显示出广泛的应用。文档分类的重要部分是正确生成文档表示。马特·库斯纳（Matt J. Kusner）等人在2015年提出了Word Mover’s Distance（WMD）[1]，其中将词嵌入技术用于计算两个文档之间的距离。使用给定的预训练单词嵌入，可以通过计算“一个文档的嵌入单词需要“移动”以到达另一文档的嵌入单词所需的最小距离”来用语义含义来度量文档之间的差异。

在以下各节中，我们将讨论WMD的原理，WMD的约束和近似，预取和修剪，WMD的性能。

WMD原理

如前所述，WMD尝试测量两个文档的语义距离，并且语义测量是通过word2vec嵌入实现的。具体而言，在他们的实验中使用了跳过语法word2vec。一旦获得单词嵌入，文档之间的语义距离就由以下三个部分定义：文档表示，相似性度量和（稀疏）流矩阵。

文本的文字表示

文本文档用向量d表示，其中每个元素表示文档中单词的归一化频率，即

注意，文档表示d是高维空间中的稀疏向量。语义相似性度量定义

两个给定单词x_i和x_j在嵌入空间中的欧几里得距离定义如下：

在WMD中，x_i和x_j来自不同的文档，而c（i，j）是从单词x_i到x_j的“移动成本”。

流矩阵定义

假设有一个原始文件A和一个目标文件B。定义了流矩阵T。流矩阵中的每个元素T _ {ij}表示单词i（在文档A中）转换为单词j（在文档B中）的次数，然后通过词汇中单词的总数对值进行归一化。也就是说，

因此，语义距离定义如下：

通过调整T中的值，可以获得两个文档之间的语义距离。距离也是将所有单词从一个文档移动到另一个文档所需的最小累积成本。约束和下界近似

最低累计成本有两个限制，即

对于文档A中的任何单词i，文档B中的任何单词j

总的来说，受约束的最小累积成本的计算复杂度为O（p³logp），其中p是文档中唯一单词的数量。也就是说，WMD可能不适用于大型文档或具有大量唯一单词的文档。在本文中，作者提出了两种加快WMD计算的方法。两种加速方法均导致实际WMD值近似。

Word centroid distance（WCD）

通过使用三角不等式，可以证明累积成本始终大于或等于由单词嵌入的平均值加权的文档向量之间的欧几里得距离。这样，计算复杂度降低到O（dp）（在此，d代表文档向量d的维。）

Relaxed WMD（RWMD）

目标有两个限制。如果删除一个约束，则累积成本的最佳解决方案是将一个文档中的每个单词都移动到另一个文档中最相似的单词上。这意味着成本最小化问题变成了在嵌入空间中找到两个单词嵌入的最小欧几里得距离。因此，通过删除一个约束并保留另一个约束，可以得到两个近似的下限：我们称它们为l1（对i保持约束）和l2（对j保持约束）。更严格的近似值l可以定义为：

l = max（l1，l2）

利用这种近似的累积成本（作者称为“松弛WMD”（RWMD）），计算复杂度降至O（p²）。

预取和修剪

为了找到有效时间的查询文档的k个最近邻居，可以同时使用WCD和RWMD来减少计算成本。

1. 使用WCD估计每个文档到查询文档之间的距离。
   
2. 按升序对估计的距离进行排序，然后使用WMD计算到这些文档的前k个确切的距离。
   
3. 遍历其余文档（不在上一步的前k个文档中），计算RWMD下限。
   
4. 如果文档（到查询文档）的RWMD近似值大于到前k个文档的所有计算的WMD距离（在步骤2中），则意味着该文档不得位于查询文
   
5. k个最近邻居中，因此 可以修剪。否则，将计算确切的WMD距离并更新到k个最近的邻居。
   

WMD性能表现

作者在kNN上下文中对八个文档数据集评估了WMD性能，并将其与BOW，TFIDF，BM25 LSI，LDA，mSDA和CCG进行了比较。他们的实验表明，WMD在8个数据集中的6个数据集中表现最佳。对于其余两个数据集，即使WMD的性能不佳，错误率也非常接近最佳性能者。

一个有趣的实验结果是作者进行了一项实验，如果下限用于最近邻居检索，则评估下限的紧密度与kNN错误率之间的关系。它表明紧密度并不能直接转化为检索精度。在作者的陈述中，一次仅受到一个约束的RWMD的紧密度（称为RWMD_c1和RWMD_c2）明显高于WCD，但就kNN精度而言，RWMD_c1和RWMD_c2的性能都比WCD差。就我的新观点而言，这可能是由于对RWMD_c1和RWMD_c2施加了不对称约束。因为仅剩下一个约束得出距离度量的非严格定义，所以RWMD_c1和RWMD_c2都不是严格的距离近似值。

潜在的工作扩展

WMD在文件分类任务中表现出色。我认为，可以做一些试验来进一步探究WMD。

作者使用了不同的数据集进行单词嵌入生成，但是嵌入方法已通过skip-gram固定在word2vec上。通过将word2vet更改为其他方法（例如GloVe），看到嵌入方法对WMD的重要性将很有趣。

请注意，WMD无法处理词汇量（OOV）数据，并且在距离计算中遇到时会直接丢弃OOV单词。这可能是WMD性能未超过所有数据集的所有其他方法的原因。可以基于上下文信息构建OOV词的嵌入。例如，BiLSTM语言模型可以帮助生成OOV词嵌入[2]。同样，字节对编码（BPE）也可以建立OOV词嵌入。

引用

[1]From Word Embeddings To Document Distances http://proceedings.mlr.press/v37/kusnerb15.pdf

[2] Language Modelling for Handling Out-of-Vocabulary Words in Natural Language Processing https://www.researchgate.net/publication/335757797_Language_Modelling_for_Handling_Out-of-Vocabulary_Words_in_Natural_Language_Processing?showFulltext=1&linkId=5d7a26a04585151ee4afb0c5

[3] WMD 代码 https://github.com/mkusner/wmd