论文总结：From Word Embeddings to Document Distance

Published On 2020/03/12 Friday, Singapore

文章提出词移距离(Word Mover’s Distance, WMD)用于计算文档之间的距离。文档之间的距离被看作为一个文档中词与词距离的加权平均。词与词的距离可基于Word Embedding得到的词向量计算，两篇文档词与词的映射关系为可变条件，目标函数为最小化文档之间的距离。求解得到最小的文档距离为词移距离。而这个最优化问题是Earth’s Mover’s Distance的特殊情况，可采用相应的算法进行求解。

| 文章链接：From Word Embeddings to Document Distance

背景

在文档检索和新闻分类等领域，常需要对进行文档之间的相似度进行计算。文本相似度则通常通过文档之间的距离衡量，而要计算文档之间的距离，则需要先对文档进行向量表示。常见的文档表示方法有：

词袋模型(Bag of Words，BOW）
词频逆文件频(Term Frequency-Inverse Document Frequency, TFIDF)

但是这两种文档表示方法在应用于文档距离计算时存在两点问题。首先，表示文档的向量之间频繁表示出接近正交性。由于两篇文档之间共同出现的词语少或没有，而不同词语会使得文档被表示在不同的向量空间上。如此一来，大量的文档直接都会被认为没有相关性。其次，它们都没有考虑词与词的距离。比如Obama speaks to the media in Illinois 和 The President greets the press in Chicago 虽然没有共同词存在，却是表达几乎同样的意思。因为没有考虑到Obama和President, speaks和greets, media和press，Illinois和Chicogo几组词的距离，而无法有效反应两篇文档的真实距离和相似性。

已有研究都试图用低维向量表示文档来规避这些问题。比如隐性语义索引（Latent Semantic Indexing，LSI)和隐含狄利克雷分布(Latent Dirichlet Allocation,LDA)。这些方法在应用于基于距离的分类时效果并不好。

与此同时，Word Embedding基于大量的训练数据得到词语的向量表示可以用于计算相似词对应的词之间的距离。也就是说,通过这个词向量表示下，我们可以知道Obama和President是存在一定关系的，而非完全正交。倘若能够把Word Embedding得到的词的向量表示引入到文档之间的距离计算中，便可以解决以上问题。基于此，作者提出来词移距离(Word Mover’s Distance)。

词移距离(Word Mover’s Distance)

用归一化词袋模型(nBOW)对文档进行表示,记为 $\boldsymbol{d}\in \mathbb{R}^n$。
\[d_i = \frac{c_i}{\sum_{k=1}^n c_k}\]
其中，$c_i$ 为第$i$个词语出现的在文档中出现的次数。$n$为词汇集合中词的总个数。
对每一个词汇集合中的每个词用word2vec embedding得到的词向量来表示。记为 $\boldsymbol{x_i}\in \mathbb{R}^n$
现在有两篇文档 $D_1$和 $D_2$。那么$D_1$中的第 $i$ 词到$D_2$中的第 $j$ 词的距离为： $c(i,j) = \|x_i-x_j\|_2$
假设两篇文档之间的词存在多对多的对应关系，$T_{ij}$表示 $D_1$ 文档中的第 $i$ 词映射(转移)到 $D_2$ 文档中第 $j$ 词的份额。对于第 $i$ 词。其映射/转移到$D_2$文档中所有词份额之和为$d_i$。同理，对于第 $j$ 词, 其映射（转移）入份额之和为$d_j$。数学表示如下
\[\sum_{j=1}^n T_{ij}=d_i\] \[\sum_{i=1}^n T_{ij}=d'_j\]
那么 $D_1$ 文档中的第 $i$ 词到 $D_2$ 文档中所有词的距离可以表示为
\[\sum_{j=1}^n T_{ij}c(i,j)\]
那么 $D_1$ 文档中的所有词到 $D_2$ 文档中所有词的距离可以表示为
\[\sum_{i=1}^n\sum_{j=1}^n T_{ij}c(i,j)= \sum_{i,j=1}^n T_{ij}c(i,j)\]

由于两篇文章之间的映射的可能性有很多种，那么文档的之间的距离也会有很多种。词移距离(WMD)定义为以上距离中的最小值。求解以上距离的最小值，本质为求解以下最优化问题。

\[\min_{T>=0} \sum_{i,j=1}^n T_{ij}c(i,j)\]

$s.t.$

\[\sum_{j=1}^n T_{ij}=d_i , \forall i \in \{1,\cdots,n\}\] \[\sum_{i=1}^n T_{ij}=d'_j , \forall j \in \{1,\cdots,n\}\]

而这个最优化问题是陆地移动距离(Earth’s Mover’s Distance, EMD)的特殊情况，可采用相应的算法进行求解。

快速计算改进

对于给定文档集合，集合中词汇的数量的数量为 $p$, 词移距离的算法复杂度为 $O(p^3logp)$ 。当 $p$ 非常大时，算法的时间复杂度会非常大。基于此，作者提出了三种针对快速计算的改进方法。

词中心距离（Word Centroid Distance）： $\|X\mathrm{d} - X\mathrm{d}^{'}\|_2$

\[\sum_{i,j=1}^n T_{ij}c(i,j) = \sum_{i,j=1}^n T_{ij}\|x_i-x'_j\|_2 = \sum_{i,j=1}^n \|T_{ij}(x_i-x_j^{'})\|_2\] \[\ge \|\sum_{i,j=1}^n T_{ij}(x_i-x_j^{'})\|_2=\|\sum_{i=1}^n(\sum_{j=1}^n T_{ij})x_i-\sum_{j=1}^n(\sum_{i=1}^n T_{ij})x_j^{'}\|_2\] \[= \|\sum_{i=1}^n d_ix_i - \sum_{j=1}^n d_j^{'}x_j^{'}\|_2= \|X\mathrm{d} - X\mathrm{d}^{'}\|_2\]

松弛词移距离(Relaxed Word Moving Distance)

\[\min_{T>=0} \sum_{i,j=1}^n T_{ij}c(i,j)\]

$s.t.$

\[\sum_{j=1}^n T_{ij}=d_i , \forall i \in \{1,\cdots,n\}\] \[\min_{T>=0} \sum_{i,j=1}^n T_{ij}c(i,j)\]

$s.t.$

\[\sum_{i=1}^n T_{ij}=d'_j , \forall j \in \{1,\cdots,n\}\]

参考资料

[1]https://github.com/src-d/wmd-relax

💚 Back to Home