From Word Embeddings To Document

0. 摘要

本文提出了WMD来衡量两个文档的不相似度，表明一个句子需要迁移多少才能变成另一个句子。这是把文档距离转化成了运输问题的思路（也就是线性规划问题），比较直观，是非常好的把未知问题转化成容易求解的数学问题的例子。论文中还用数据做了验证，在8个文章分类的数据集上的效果非常好。

1. 引言

以往的表示文档的方式是bow和if-idf，其正交（而导致的稀疏性）不适合用于衡量文档距离。降维处理的方法如LSI，LDA也不比bow更好。本文提出的基于词向量的表示矩阵，这个方法是基于词向量的。词向量的研究表明可以用低维向量来表示距离在语义上站得住脚。文档A、B之间的最小距离就是A需要迁移多少才能变成B。

WMD的特性：1. 不需要超参数，2. 直观，可解释，3. 天然与词向量相容，在几个数据集上的召回率很高。

2. 相关工作

略

3. 词向量

略

4. WMD

假设我们已经有了词向量矩阵，词汇量大小为n，维度为d，整个空间就是R^dxn。第i列x_i表示d维空间中第i个词的向量表示。如果用nbow表示文档，那么第i个词出现的次数为c_i，那么定义

image.png

nbow表示。回忆之前的例子，“奥巴马在伊利纳斯州通过媒体讲话”和“总统在芝加哥会见新闻机构”，用nbow就完全不相似，但语义上其实是十分接近的。

word travel cost。词汇距离用

image.png
表示。

文档距离。 T_ij 特指文档d中的单词i和文档d’中的单词j的对应关系，这个定义跟c_(i.j)好像有点混淆， T_ij 是两个句子中单词的对应关系，举个不太恰当的例子：T中的元素要么是0要么是1就是要么对应要么不对应（实际上这个数可以是小数，理解为比例），c_(i.j) 是单词本身的距离值。单词的出量d_i需要满足

image.png
（直观理解就是出现了几次，都要对应到另一个文档中，不允许某个单词完全不对应到另一个句子中）。这样，就定义了两个文档的距离，所有的出入量 image.png
，就是把d中单词全部迁移到d’中的距离加和。

问题转化成经典的运输问题，并且是线性规划。

image.png

约束就是每个单词的nbow权重di（就是出现了几次）都要对应到另一个句子中，D1中的单词都要在D2中找到对应，反之亦然。目标函数就是求所有迁移距离之和的最小值。

以下图为例

image.png

首先去除停用词。D₀得到President, greets, press, Chicago，每个di都等于0.25。D₁，D₂中的每个单词i到D₀中每个单词j的距离在图中用箭头表示出来。因为考虑了语义，所以D1比D2更接近D0. D3到D0的例子中，句子长度不同。D3中每个单词的dj都是0.33，这样就会有到相似词的额外流量。这就增加了距离，这样就人为的增加了短文本的影响，因为长文本中可能有多个相似的词。

4.1 计算提速

Word centroid distance

计算WMD的最快速度是O(n³logn) ，n代表文档中单词个数。这就很麻烦，下面介绍几个加快计算的方法Word centroid distance。

image.png

这是原问题的一个下确界。简化成了D1中单词出现次数*词向量 – D2中单词出现次数 * 词向量的平方和。（这个计算定义好简单啊卧槽）

Relaxed word moving distance

因为WCD的方式不是很tight，所以还有下面这个优化：

image.png

去掉原问题的其中一个约束。

比如说去掉D1的入度，可以得到一个解l1。去掉D2的入度，得以得到另一个解l2，然后取max(l1,l2)可以得到一个更tight的解。

预取和剪枝

通过以上几种方法，我们可以取前K个相似词，然后用标准的wmd来精确计算，达到剪枝的效果。

5. 数据实验

image.png

这个就不详细介绍了，总之效果很棒。

6. 结论

WMD的效果好应该归因于词向量，其训练使用了大量的数据集，不仅限于要比较的目标。

本文的两个未来可以优化的点：
一是进一步增加解释性，文档可以转为词汇的稀疏距离。
二是可以利用文档结构这个信息来加权重，比如论文中两个段落中的句子相似度应该不如同一个段落中的句子高。

7. 个人感想

1. 通过对WMD的实现和试用，感觉这个算法在比较短句时会有些无力吧，句子之间的距离都差不多。
2. 任何算法要应用到工程中都应该考虑对效率进行优化，通过找lower bound，upper bound来进行剪枝是很好的思路。