982
Word Sequence To Document Distances 實踐與優化
近幾年來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。
最後更新：2017-06-05 11:32:35