近几年来word2vec 在自然语言与机器学习方向上已经有巨大突破，将word表示成向量已经是自然语言处理中常见的方法。本文前部分介绍的是word2vec或者其他word embedding方法处理文本后计算两个文本相似程度的算法，算法思路来自论文《From Word Embeddings To Document Distances》，如果没有读过这篇论文也没有关系，后续会介绍这篇论文的大致思路和我自己改造的实现方法。后半部分介绍这种方法遇到的问题，以及自己优化这个算法思路与过程。
在对文本进行word embedding过程之后，文本中每个词都被表示成了向量，自然就拥有了相加或者计算彼此之间相似程度的属性。原始方法常常会将一个文本中所有的词向量相加之后再进行相似程度的比较，这种方法很直观有效但是问题也很明显，段落文本稍微长一些就会出现偏差。早起时期我也使用过gensim提供的doc2vec，但是doc2vec的效果一直都是很差的，而且鲁棒性不及LSI。
看了《From Word Embeddings To Document Distances》这篇文章后感觉思路不错，文章大致思路（个人理解后阐述）:
计算A,B句子里每两个词的距离 i.e. D = dist(A_i, B_j) over all i,j（这里用Euclidean distance b/t the word embeddings, from word2vec or other）。生成optimal transport problem，给solver。输入是（D，A，B）, A所有词的词频(A_BOW i.e. bag of words)， B所有词的词频(B_BOW)。其中optimal transport 使用 EMD（Earth mover's distance）计算，EMD返回的就是A和B的距离。
读完这篇文章之后结合了一些自己的想法和一些图论知识，对该算法进行重新定义。将匹配段落中的词比喻成生产地，被匹配段落中的词比喻成销售地，生产地的产量由该词在这个段落的重要性决定，销售地的销售量由被匹配段落该词的重要性决定。匹配词和被匹配词之间都有一条路，这条路的路费由词和词之间的embedding后计算欧式距离得出。得到原料之后开始构图，这里我们的边有4个属性（u,v,c,f）u为边的起始点，v为边的终点，c为边的容量，f为通过所需要的花费，设两个点s（源点），t（汇点），将匹配段落中的词抽象成一个点，s与所有匹配段落词生成的点相连，同理所有被匹配段落词生成的点与t相连，c容量设为每个词在该段落的重要程度（可以用tf-idf）f花费为0。中间对双方的词进行二分图全连接，每条边的容量为无限大，花费f为两个词欧氏距离。举一个例子Obama speaks to the media in Illinois.作为匹配段落，The President greets the press in Chicago. 作为被匹配段落，如下图所示。
例子中简化掉了一部分计算，每个词的权重简单的使用tf/|word|。构图之后对s和t进行MCFP（Minimum-cost flow problem），图中可行流网络可以看出对可行流并没有任何特殊的限制，左边流入和右边流出为词平均（相加为1），中间部分无限制，那么最终最大流量一定为1。费用网络只有中间部分体现，用于挑选最优的通路。
到这里其实与原论文的思路极为近似，但是这种算法有很大的问题：
1.该算法仅仅使用了word embedding 的结果可计算相似的属性，遗漏了其结果的可加性。word2vec中词的可加性是非常重要的性质，常见的经典例子：king - man + woman = queen。
2.最重要的问题是对语句相似性的理解，一个句子是一个word sequence ，这种算法只考虑了word之间的相似性而不考虑短语与短语之间、句子之间的paraphrase 或者说 topic。
对此我对算法进行了改造：在匹配句和被匹配句之间增加一层词向量累加层，累加的窗口的大小为k（k一般不超过训练word2vec时窗口的大小），举个例子Obama speaks to the media in Illinois.仍然是这句话，我们对这句话设置一个k为2的窗口，每个窗口之间的词向量进行累加，累加后的结果为一个新的点。新点与被加的两个词连上一条容量c为无穷大，花费f为0的边。
这样一来一句话7个词会多出来6个节点，使用这13个点与被匹配句进行二分图全连接，同样花费f为两个节点向量的欧式距离。
如此构建网络完成，重新计算s与t之间的MCFP会比原始的方法得出的距离更小，这种方法先简称WSMD（word sequence mover's distance）。举个例子look after 和 take care of 单纯的计算每个词之间的距离会很大，但是假设放到一个窗口超过3的网络中 look after 两个词 会通过累加节点将自己的流量传给take care of的累加节点，因为这两个累加节点得到的向量欧式距离更近，因此在费用网络中的花费也就更少。
我在客满逆向和维权数据上进行kNN classification， 分别使用LDA、LSI、WMD、WSMD来描述文本之间的距离得到的误差为 LDA>WMD>LSI>WSMD，WSMD误差略小于LSI。
对此我对算法进行了改造：在匹配句和被匹配句之间增加一层词向量累加层，累加的窗口的大小为k（k一般不超过训练word2vec时窗口的大小），举个例子Obama speaks to the media in Illinois.仍然是这句话，我们对这句话设置一个k为2的窗口，每个窗口之间的词向量进行累加，累加后的结果为一个新的点。新点与被加的两个词连上一条容量c为无穷大，花费f为0的边。
这样一来一句话7个词会多出来6个节点，使用这13个点与被匹配句进行二分图全连接，同样花费f为两个节点向量的欧式距离。
如此构建网络完成，重新计算s与t之间的MCFP会比原始的方法得出的距离更小，这种方法先简称WSMD（word sequence mover's distance）。举个例子look after 和 take care of 单纯的计算每个词之间的距离会很大，但是假设放到一个窗口超过3的网络中 look after 两个词 会通过累加节点将自己的流量传给take care of的累加节点，因为这两个累加节点得到的向量欧式距离更近，因此在费用网络中的花费也就更少。
我在客满逆向和维权数据上进行kNN classification， 分别使用LDA、LSI、WMD、WSMD来描述文本之间的距离得到的误差为 LDA>WMD>LSI>WSMD，WSMD误差略小于LSI。
