From Word Embeddings To Document Distances
1. Word Mover’s Distance (WMD) 能解决的具体问题及本文的背景
这是一篇2015年发表的文章，主要是基于word embedding以及一个在运输领域使用很广的Word Mover’s Distance (WMD)来计算文档之间的距离（相似性）。 首先我们知道，从文本中提取摘应用是很广泛的，比如自动生成新闻题目，文档分类，不同语言的文本匹配等等（其实还能用来找同领域的文献，这样你阅读的论文就会成指数级增长:P）。 但是传统的NLP方法，比如计算文档中的词频（TF-IDF）或者a bag of words (BOW)没有考虑语义的影响。比如对Obama和American President其实是一个意思，但是如果只计算词频的话是没办法说这两个词是相近的。 传统的改进方法是对feature space进行改进，比如Latent Semantic Indexing (LSI) 对 BOW feature space做特征值分解, and Latent Dirichlet Allocation (LDA) 用概率的方法把相近的词group在一起，然后把文档表示为关于topic的概率分布。不过这些方法没有在计算文档之间距离（相似性）的任务上做改进。 而基于word to vec 算出来的word embedding之间的距离就可以考虑语义的影响，因此本文的工作是把两个文档之间距离表示为文档中从一个词到另一个词的最小距离之和，见图1（其实思想挺简单的但在当时word2vec刚出来，所以在此基础上做的工作还是值得肯定的）。 很明显这是一个最优化问题，并且还是一个在运输领域研究的很完备的问题，所以可以利用针对这个问题开发好的求解器来求解。事实上，WMD其实是earth mover’s distance metric的一个特例。跟前一篇类似，本文中也使用了一些lower bounds来近似和裁剪从而达到优化速度的效果。 作者还介绍了EMD在图像提取中的早期应用，以及在此领域对earth mover's distance metric（EMD）的一些优化，比如并行计算等。但那些优化有前提假设，即提取出的矩阵大小并不太大，这对NLP问题并不适用，因此作者本文对EMD进行了针对文档相似性计算的优化。
Fig.1 An illustration of the word mover's distance. All non-stop words (bold) of both documents are embedded into a word2vec space. The distance between the two documents is the minimum cumulative distance that all words in document 1 need to travel to exactly match document
1.1 Earth Mover’s Distance (EMD) 的背景
要了解WMD，首先要了解搬土问题，英文为EMD（earth mover distance）。假设有北京上海两地各有土250吨和300吨，现在有三个仓库分别需要土100, 250, 270吨，北京上海运输每吨土到三个仓库一共有6种不同的成本，问如果规划可以让成本最小，见图2。很明显，这是一个线性规划问题。 设从北京运到仓库1，2，3，成本为
，从上海运
到仓库1，2，3，成本为
，则EMD问题可写作：
Fig.2 An example of the earth mover's distance.
Minimize 总成本 = ,
Subject to
(仓库轴和地点轴分别的constraint)
写成矩阵，是从
搬到
的土的重量。这个线性规划模型很容易解，有很多solver可以求解。 （在WMD中由于这个矩阵被归一化了，所以
是搬多少
去第二篇文章的
的权重，并且由于
用到是BOW的表示比如文章中个
是“nice”，在文中出现了5次，所有的词加起来一共20次，则这个word的总重是
，所以
）
Fig.3 An example of flow matrix.
1.2 Word Mover’s Distance (WMD) 介绍
联系刚刚的例子，上海北京是一篇文章，仓库1，2，3是另一篇文章。上海，北京分别是文章1中的两个词，用BOW的一个长度为N的词库，比如在一个长度为5的词库{仓库1，北京，仓库2，上海，仓库3}里，文章1可以表示为『0，0.5，0，0.5，0』，文章2可以表示为『0.33，0，0.33，0，0.33』。是
到
的word2vec的embedding向量的距离，可以认为是从文章1的
到文章
的cost。 跟EMD相似的，从数学上正式定义这个问题的话可以写作：
在WMD中由于这个矩阵被归一化了，所以
是搬多少
去第二篇文章的
的权重，并且由于
用到是BOW的表示比如文章中个
是“nice”，在文中出现了5次，所有的词在文章1加起来一共20次，则这个word的总重是
，所以
） 这里横轴纵轴也有constrain，跟EMD一样理解。
2. Word Mover’s Distance (WMD) 的优化方法
2.1. Word centroid distance
与2012 KDD best paper 那篇优化DTW算法的方法一样，一个很有效的办法是通过计算WMD的lower bound来prune掉大部分距离比较大的document。即需要找到一个lower bound，算出来的距离始终比WMD小。那么在本文里，一个很明显的lower bound是根据三角形不等式，即两边之和大于第三边得到的。可以见下列的数学公式，或者用一张更明显的几何图来表示，如图4。公式左边是距离的和，右边是向量之和的距离。左边大于右边，严格证明的话可以把point连起来形成若干个三角形根据两边之和大于第三边来证。后面把公式右边那个比较小的距离做了一些变换得到word centroid distance，就是每个词的质心距离。
Fig.4 公式的几何表示
2.2. Relaxed word moving distance
WMD虽然计算很快但是不tight，还有一种优化方式就是去掉一个constraint。
由于不像EMD我们分一些北京的土到三个不同的仓库，对于词向量来说最优的情况是把一个词全部移动到与他距离最近词上去，因此可以重新定义为：
具体可以根据以下公式证明：
与之前那篇用DTW来做trillion时序comparison的优化方式一样，本文作者也是做了两个lower bound组合的方式来prune，并且也做了sorting和缓存计算好的距离。就不赘述了，具体可以看前一篇。
3. 关于此文的一些思考
本文通过word2vec得到有semantic的word embedding，然后通过转化文档相似性问题为一个在运筹领域研究的很透彻的EMD问题来解决，这种思想值得借鉴。
找lower bound看来是一种加速算法的通用方法，最好找到一些计算速度比较快的lower bound，然后做瀑布式的裁剪，同时sorting和存一些变量也是比较好的方法。
4\ WMD代码实现
- 下载用glove训练好的word embedding
https://nlp.stanford.edu/projects/glove/
import cvxopt
import numpy as np
import string
from collections import Counter
from scipy.optimize import linprog
glovefile = open("glove.6B.100d.txt","r",encoding="utf-8")
em = glovefile.readlines()
dic = {}
for i in range(len(em)):
s = em[i].strip("\n").split(" ")
dic[s[0]] = np.loadtxt(s[1:])
def WMD (sent1, sent2):
def get_words_counts(sent):
"""
given a sent, return its unique words and words count
Args:
sent: str
Return:
words: list of unique words in the sentence
freq_vector: array of normalized frequency of corresponding words, shape (len(words))
"""
words = sent.translate(str.maketrans('', '', string.punctuation)).lower().split(" ")
from collections import Counter
words1dict = Counter(words)
words1unique = list(words1dict.keys())
wordvector = [words1dict[i]/len(words) for i in words1unique]
return words1unique, wordvector
def flat_and_index(matr):
"""
given a matr with shape m x n,
after flat the matr, return original
row-wise coefficient matrix and column-wise coefficient matrix
Args:
matr: array like
Return:
A1: m x(m*n) row wise coefficient matrix
A2: n x(m*n) column wise coefficient matrix
"""
m, n = np.shape(matr)
A1 = np.zeros((m, m*n))
counter =0
for i in range(m):
A1[i, counter:counter+n] =1
counter = counter + n
A2 = np.zeros((n, m*n))
for i in range(n):
for j in range(m):
A2[i, i+j*n] =1
return A1, A2
words1unique, counter_vector1 = get_words_counts(sent1)
words2unique, counter_vector2 = get_words_counts(sent2)
words1_arrays = [dic[i] for i in words1unique]
words2_arrays = [dic[i] for i in words2unique]
dist_matrix = np.zeros((len(words1_arrays), len(words2_arrays)))
for i in range(len(words1unique)):
for j in range(len(words2unique)):
dist_matrix[i,j] = np.linalg.norm(words1_arrays[i]-words2_arrays[j])
A1, A2 = flat_and_index(dist_matrix)
assert len(A1) == len(counter_vector1)
assert len(A2) == len(counter_vector2)
A = np.vstack((A1, A2))
c = dist_matrix.flatten()
B = np.asarray(counter_vector1+counter_vector2)
sol = linprog(c, A_eq =A, b_eq=B, bounds=(0,None))
wmd = np.dot(sol.x, c)
return wmd
- 测试
print(WMD("people like this car", "those guys enjoy driving that"))
print(WMD("I love my home it is in a good place", "Believe it or not I like you"))
print(WMD("That is it, stop it!", "I hate it, do not do it right now"))
print(WMD("my leader is giving a speech", "Our president is presenting"))
4.271249445939769
3.6289936834376237
3.342944295085508
3.9697731866077657
References:
[1] M. J. Kusner, Y. Sun, N. I. Kolkin和K. Q. Weinberger, 《From Word Embeddings To Document Distances》, p10.
