用线性规划去计算句子之间的相似度

本文原载于知乎「Data Science with R&Python」专栏,AI 研习社获其作者何史提授权转载。

Word2Vec 或 FastText 之类的字嵌入模型已经被自然语言处理的人员广泛使用,原因无他,因为这些模型把所需要的维度降低了许多(用 bag-of-words 模型要和词典数相等的维度,但这类模型的维度只是在数百之间),而且字的相似度有更好的理解(用 bag-of-words 模型,字义相似的字都被视为不同,但这类模型字义相似的字都可用 cosine 相似度描述)。

那麽,如何用这些模型去描述句子之间的相似度?直接的方法就是把每一句子的每一个字加起来,然后计算 cosine 相似度。但这方法有点粗略,如果有些字加起来抵消了某些字义,那不太好。在 2015 年,Kusner 发表了一篇论文去解决这个问题,而这方法一个大好处就是他像距离或相似度一样是无需训练的,这方法叫作 Word Mover’s Distance (WMD),可以说是 Earth Mover’s Distance 或 Wasserstein Distance 的一个特例。

WMD 的定义很漂亮。假设字篏入模型标示为

,当中 d 是字篏入模型维度, n 是字数。每一句子由一个 normalized BOW 向量表示

,而

,而 i 代表每一个字。字和字之间的距离是模型中的欧氏距离,

, i 和 j 代表不同的字。我们想要计算的 WMD 就是

当中 T 是一个 n×n的矩阵,

,每一个

代表由第一句子的字 i 到第二句子字 j 的部分。(第二句子的 normalized BOW 向量是

。)

这个问题的关键在于解 T ,而我们想把 WMD 降到最低,所以这也是一个最优化的问题:

,

条件:

很明显地,这是一个綫性规划(linear programming)的问题。

在 Python 中,有很多最优化的包,其实 scipy 本身也自带一个优化器,但不合用;我也考虑过 cvxopt,但因为一些原因使程序变得混乱;到最后,我选择了 PuLP,然后我发现这个是最合适的工具。

先载入所需要的包:

然后建一个函数,计算一个句子的 normalized BOW 向量:

以下就是最核心的程序:

其中 wvmodel 是 Word2Vec 模型,去载入模型,用:

(读者其实也可以用 FastText 或 Poincare Embedding,载入的函数不一样,但不影响以下的代码。FastText: gensim.models.wrappers.FastText.load_fasttext_format;Poincare:gensim.models.poincare.PoincareKeyedVectors.load_word2vec_format)

可以看到,使用 PuLP,要先定义一个 LpProblem,然后把成本函数和所有条件都加进去,最后用 LpProblem 的 solve() 方法去解决。读出我们想要的 WMD,可用 pulp.value(prob.objective),但我们用以下的代码展示我们可如何读出各个参数和变量:

然后可得

第一行就是 WMD,其他则是T的元素的量。其他例子:

document1 = physician, assistant

document2 = doctor

WMD = 2.8760048151

document1 = physician, assistant

document2 = doctor, assistant

WMD = 1.00465738773

document1 = doctors, assistant

document2 = doctor, assistant

WMD = 1.02825379372

document1 = doctor, assistant

document2 = doctor, assistant

WMD = 0.0

读者可参考此 Jupyter Notebook:http://t.cn/RHcJLkyhttps://

其实,Python 包 shorttext 已经实现了这个方法,安装后,使用方法如下:

读参这个 tutorial:Metrics - shorttext 0.5.9 documentation(http://t.cn/RHcJHKm)

另外,gensim 提供的 Word2Vec 模型中,也供程序员计算 WMD,但用的是 SIFT,而且距离是曼哈顿距离而非欧氏距离,详情参见:gensim: topic modelling for humans(http://t.cn/RHcJuid)

圖片來至:Matt Kusner, Yu Sun, Nicholas Kolkin, Kilian Weinberger, “From Word Embeddings To Document Distances,” Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:957-966 (2015).[http://t.cn/RHcJDpq]

延伸閱讀:

Kwan-Yuet Ho, “Word Mover’s Distance as a Linear Programming Problem,”Everything About Data Analytics, WordPress (2017). [http://t.cn/RHci4ZE]

Matt Kusner, Yu Sun, Nicholas Kolkin, Kilian Weinberger, “From Word Embeddings To Document Distances,”Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:957-966 (2015). [http://t.cn/RHcJDpq]

Github: mkusner/wmd. [http://t.cn/RthCUOV]

Kwan-Yuet Ho, “Toying with Word2Vec,”Everything About Data Analytics, WordPress (2015). [http://t.cn/RHciCU9]

Kwan-Yuet Ho, “On Wasserstein GAN,”Everything About Data Analytics, WordPress (2017). [http://t.cn/RHcimxH]

Martin Arjovsky, Soumith Chintala, Léon Bottou, “Wasserstein GAN,” arXiv:1701.07875 (2017). [https://arxiv.org/abs/1701.07875]

Alison L. Gibbs, Francis Edward Su, “On Choosing and Bounding Probability Metrics,” arXiv:math/0209021 (2002) [https://arxiv.org/abs/math/0209021]

cvxopt: Python Software for Convex Optimization. [http://cvxopt.org/]

gensim: Topic Modeling for Humans. [http://t.cn/R4zI4yA]

PuLP: Optimization for Python. [https://pythonhosted.org/PuLP/]

Demonstration of PuLP: Github: stephenhky/PyWMD. [http://t.cn/RHc6jiB]

Implemenation of WMD: Github: stephenhky/PyWMD. [http://t.cn/RHcJLky]

Github: stephenhky/PyWMD. [http://t.cn/RHc6F12]

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20171228A02N2L00?refer=cp_1026

扫码关注云+社区