Skip to content

P
project2
Switch branch/tag
Find file
BlameHistoryPermalink
problem2.ipynb 11.4 KB

线性规划与Word Mover's Distance

WMD在文本分析领域算作是一个比较经典的算法，它可以用来计算两个文本之间的相似度。 比如问答系统中，可以判断一个用户的query跟哪一个知识库里的问题最相近。而且，计算两个文本之间的相似度这个问题是NLP的核心，这也是为什么文本相似度计算这么重要的原因。

背景： 在文本相似度匹配问题上如果使用tf-idf等模型，那这时候假如两个文本中没有出现共同的单词，则计算出来的相似度为0，但我们知道实际上很多时候单词可能不一样，但表示的内容确是类似的。 比如 ”People like this car“, "Those guys enjoy driving that", 虽然没有任何一样的单词，意思确是类似的。 这是WMD算法提出来的初衷。

WMD作为文本相似度计算的一种方法，最早由Matt J. Kusner, Yu Sun, Nicholas I. Kolkin, Kilian Q. Weinberger等人提出。但实际上它的想法极其简单，可以认为是Transportation Problem用在了词向量上， 其核心是线性规划。 对于Transportation问题在课上已经讲过，仍不清楚的朋友可以回顾一下课程的内容。

在Section B里我们需要做两件事情： 1. 实现WMD算法来计算两个字符串之间的距离。 2. WMD的拓展方案

1. WMD算法的实现

具体算法的实现是基于线性规划问题，细节请参考WMD的论文。 核心思想是把第一个句子转换成第二个句子过程中需要花费的最小cost。

<img src="picture1.png" alt="drawing" width="600"/>

线性规划问题即可以写成如下形式：

<img src="picture2.png" alt="drawing" width="500"/>

这里的参数是$T{ij}$， 需要通过LP Solver去解决。$c(i,j)$指的是两个单词之间的距离, $c{i,j}=||x_i-x_j||_2$。 参考： ∣∣x∣∣2=x12+...+xd2 ||x||_2=\sqrt{x_1^2+...+x_d^2}

为了实现WMD算法，首先需要词向量。 在这里，我们就不自己去训练了，直接使用已经训练好的词向量。 请下载训练好的Glove向量：https://nlp.stanford.edu/projects/glove/ 下载其中的 glove.6B.zip， 并使用d=100维的向量。 由于文件较大，需要一些时间来下载。 如果太慢的话，可以找找国内的镜像。

请注意：提交作业时不要上传此文件， 但文件路径请使用我们给定的路径，不要改变。 

# 读取Glove文件。 注意： 不要试图修改文件以及路径
glovefile = open("glove.6B.100d.txt","r",encoding="utf-8")  

# TODO: 编写WMD函数来计算两个句子之间的相似度

def WMD (sent1, sent2):
    """
    这是主要的函数模块。参数sent1是第一个句子， 参数sent2是第二个句子，可以认为没有经过分词。
    在英文里，用空格作为分词符号。
    
    在实现WMD算法的时候，需要用到LP Solver用来解决Transportation proboem. 请使用http://cvxopt.org/examples/tutorial/lp.html
    也可以参考blog： https://scaron.info/blog/linear-programming-in-python-with-cvxopt.html
    
    需要做的事情为：
    
    1. 对句子做分词： 调用 .split() 函数即可
    2. 获取每个单词的词向量。这需要读取文件之后构建embedding matrix. 
    3. 构建lp问题，并用solver解决
    
    可以自行定义其他的函数，但务必不要改写WMD函数名。测试时保证WMD函数能够正确运行。
    """
    
    return wmd_dist
    
## TODO: 自己写至少4个Test cases来测试一下。 比如 print (WMD("people like this car", "those guys enjoy driving that"))
##

2. WMD算法的拓展

2.1 从欧式距离到Mahalanobis距离

WMD算法本身不需要任何的标注好的数据，所以它属于无监督学习。 而且在上述的WMD算法里使用的是欧式距离，$c(i,j)=||x_i-x_j||_2$， 那这种距离有什么缺点呢？ 其中一个缺点是欧式距离的计算把一个空间里的每一个维度都看成了同样的权重，也就是每一个维度的重要性都是一致的，而且不同维度之间的相关性也没有考虑进来。如果想把这些信息考虑进来，我们则可以使用一个改进版的距离计算叫做Mahalanobis Distance， 距离计算变成 c(i,j)=(xi−xj)⊤M(xi−xj) c(i,j)=(x_i-x_j)^{\top}M(x_i-x_j)。

这如何去理解呢？ Mahalanobis distance可以理解成： 首先我们对原始空间里的样本做了一层线性的转换， 然后在转换后的空间里计算欧式距离。 我们把这个过程写一下： 原始空间里的点为 xi x_i, 然后我们定义一个转换矩阵 L L, 这时候就可以得到 ∣∣Lxi−Lxj∣∣22=∣∣L(xi−xj)∣∣22=(L(xi−xj))⊤L(xi−xj)=(xi−xj)⊤L⊤L(xi−xj)=(xi−xj)⊤M(xi−xj) ||Lx_i - Lx_j||_2^2=||L(x_i-x_j)||_2^2=(L(x_i-x_j))^{\top}L(x_i-x_j)=(x_i-x_j)^{\top}L^{\top}L(x_i-x_j)=(x_i-x_j)^{\top}M(x_i-x_j), 相当于把$L^{\top}L$看做是矩阵$M$。这时候很容易看出来矩阵$M$是PSD(positive semidefinite).

假设我们定义了这种距离，这里的M如何选择呢？ 当然，这是需要学出来的！ 那为了学出M， 必须要有标注好的训练数据，也就需要监督学习场景！

在这个式子里，第一部分代表的是让同一类型的样本的距离变小， 第二部分代表的是不同类型的样本之间要扩大距离。

  • Q1: 这里$\lambda$起到什么作用？

// TODO: 你的答案....

  • Q2: 在目标函数里有$\eta$值，这个值怎么理解？ 如果去设定这个值呢？

// TODO: 你的答案 ....

这里的$d_{u,v}$指的是$s_u$和$s_v$之间的距离， 而且这个距离被定义为：

\begin{equation} d{u, v}=min{T\geq 0}\sum{i,j}^{}T{ij}c(i,j)^u~~~~ s.t. \sum{j=1}^{}T{ij}=di^u, ~~\sum{i=1}^{}T_{ij}=d_j'^v\end{equation}

这里 c(i,j)=(xi−xj)⊤M(xi−xj) c(i,j)=(x_i-x_j)^{\top}M(x_i-x_j)。 所以是不是可以察觉到这个问题目标函数里既包含了参数$M$也包含了线性规划问题。

  • Q3: 请试着去理解上述所有的过程，并回答： 优化问题如何解决呢？ 请给出解题的思路 （文字适当配合推导过程）。

// TODO 你的答案....

对于上述问题，其实我们也可以采用不一样的损失函数来求解M。 一个常用的损失函数叫作 “kNN-LOO error”， 相当于把KNN的准确率转换成了smooth differential loss function. 感兴趣的朋友可以参考： https://papers.nips.cc/paper/6139-supervised-word-movers-distance.pdf

以上是优化部分的一个简短的作业，通过这些练习会对优化理论有更清晰的认知。 Good luck for everyone！