文檔相似度(document similarity)是自然語(yǔ)言處理(NLP)領(lǐng)域中比較經(jīng)典的一個(gè)下游任務(wù)浮驳》唤眨基本問(wèn)題是谜疤,給定兩個(gè)文檔柑船,判斷它們的內(nèi)容有多相似帽撑。這種判斷可以基于多個(gè)層次。最低級(jí)的就是字符串到字符串的匹配鞍时,最高級(jí)的就是兩篇文檔是不是傳達(dá)了相似的信息亏拉。從低級(jí)到高級(jí)扣蜻,評(píng)判算法給出的相似度的合理性越來(lái)越依賴(lài)于算法對(duì)人類(lèi)語(yǔ)言的理解,或者說(shuō)越來(lái)越基于“語(yǔ)義”及塘。比如莽使,"Obama speaks to the media in Illinois"同"The President greets the press in Chicago" (引自標(biāo)題論文)有類(lèi)似的語(yǔ)義,但完全不一樣的表達(dá)笙僚,或者說(shuō)兩句話(huà)的字符串形式差異很大芳肌。那么,如何才能做到基于語(yǔ)義的相似度計(jì)算肋层?
隨著神經(jīng)網(wǎng)絡(luò)的復(fù)興亿笤,NLP領(lǐng)域里涌現(xiàn)了一個(gè)重要技術(shù),就是詞向量栋猖,或者說(shuō)詞嵌入净薛。語(yǔ)言學(xué)家很早就在思考對(duì)于人類(lèi)語(yǔ)言的數(shù)學(xué)建模。自然而然蒲拉,這需要語(yǔ)言學(xué)家解決一個(gè)基本問(wèn)題:以英語(yǔ)為例罕拂,如果說(shuō)英語(yǔ)的基本單位是一個(gè)個(gè)的英文單詞,那么該如何把每個(gè)單詞映射為幾何空間里的一個(gè)向量全陨,使得語(yǔ)義相關(guān)的單詞有相鄰近的空間位置爆班?直觀的做法是,手工設(shè)計(jì)一個(gè)高維空間辱姨,每個(gè)維度都有明確的定義柿菩,然后按照人類(lèi)對(duì)語(yǔ)言的理解,給一個(gè)單詞在每個(gè)維度打分雨涛,也就是依靠人來(lái)定義坐標(biāo)軸和每個(gè)單詞的具體坐標(biāo)枢舶。這樣的映射通常會(huì)有比較好的性質(zhì),比如同義詞應(yīng)該在所有坐標(biāo)軸上坐標(biāo)相似替久,反義詞應(yīng)該在某些坐標(biāo)軸上坐標(biāo)相反凉泄。但很明顯,手工做法難以大規(guī)模推廣到所有英文單詞蚯根。也因此有了word2vec后众、glove這一類(lèi)基于統(tǒng)計(jì)共現(xiàn)的詞向量模型。這一類(lèi)模型本質(zhì)上是在對(duì)單詞的共現(xiàn)矩陣做矩陣分解颅拦,此處按下不表蒂誉。總之距帅,我們現(xiàn)在有大量的可選的詞向量模型右锨,能夠用向量間的空間距離來(lái)抽象的表達(dá)單詞間的語(yǔ)義距離。接下來(lái)的問(wèn)題是碌秸,如何從給定的單詞間的語(yǔ)義距離绍移,推斷文檔間的語(yǔ)義距離悄窃?這也就是標(biāo)題論文的主題。
基本思路如下蹂窖。首先轧抗,一篇文檔可以粗糙的理解為一個(gè)單詞的集合(無(wú)序)。如果文檔A和B相似恼策,那么我們應(yīng)該能發(fā)現(xiàn)A中的一些詞在語(yǔ)義上對(duì)應(yīng)著B(niǎo)中的一些詞鸦致。比如,在第一段的兩個(gè)例句中涣楷,“Obama”應(yīng)該對(duì)應(yīng)"President"分唾,“media”應(yīng)該對(duì)應(yīng)“press”。為什么狮斗?以A句中的“media”為例绽乔,相對(duì)于B句中的其他單詞,“media”同“press”有最小的基于單詞對(duì)的語(yǔ)義距離碳褒。
更一般來(lái)說(shuō)折砸,假設(shè)我們有一個(gè)語(yǔ)料庫(kù)(corpus),也就是一堆文檔的集合沙峻。我們先收集語(yǔ)料庫(kù)中至少出現(xiàn)一次的單詞睦授,構(gòu)成字典(vocabulary)。假設(shè)字典中有個(gè)唯一的詞摔寨,隨意排序好去枷,指字典中的第個(gè)單詞。然后是复,統(tǒng)計(jì)每篇文檔使用了字典中的哪些詞删顶,以及每個(gè)詞使用了多少次。假設(shè)文檔A中淑廊,所有字典詞出現(xiàn)的頻率為()逗余。自然,A中沒(méi)使用的詞的頻率為季惩。 類(lèi)似的录粱,文檔B的單詞頻率為。記為文檔A中出現(xiàn)的第個(gè)字典詞蜀备。然后構(gòu)建一個(gè)的矩陣关摇,其中元素記為。具體含義上碾阁,,也就是到的基于單詞詞義的語(yǔ)義距離些楣。距離矩陣由某個(gè)詞向量模型給出的單詞向量結(jié)合一個(gè)距離函數(shù)可以得出脂凶,視為給定即可宪睹。
那么直觀上,可以定義如下文檔距離蚕钦,
即單詞對(duì)對(duì)文檔距離的貢獻(xiàn)正比于它們的語(yǔ)義距離亭病,以及它們的詞頻乘積。然而嘶居,該定義并不合理罪帖。比如,如果套用該定義計(jì)算第一段兩個(gè)例句的距離邮屁,我們實(shí)際上了考慮了“Obama”同“Illinois”的距離整袁。顯然,因?yàn)樗鼈兊膯卧~語(yǔ)義相差很多佑吝,將其算在總距離內(nèi)坐昙,夸大了兩句話(huà)的語(yǔ)義距離。
其實(shí)芋忿,我們想要做的是炸客,將A中出現(xiàn)過(guò)的每一個(gè)詞匹配到B中出現(xiàn)過(guò)的語(yǔ)義最相近的詞,文檔A和B的距離就是所有匹配到一起的單詞對(duì)的語(yǔ)義距離之和戈钢”韵桑可是這個(gè)想法也有很多問(wèn)題。第一殉了,數(shù)學(xué)上難以求解开仰。對(duì)每一個(gè),我們都需要求解一個(gè)“argmin”問(wèn)題宣渗,即在B中找到最小的抖所。第二,沒(méi)有考慮詞頻痕囱。最后田轧,從語(yǔ)言理解的角度出發(fā),文檔A中的一個(gè)主體詞(題眼)鞍恢,可能同時(shí)對(duì)應(yīng)文檔B中多個(gè)具體的詞傻粘;只考慮與其語(yǔ)義最接近的一個(gè)詞,有失片面帮掉。綜上所述弦悉,原則上,(或)應(yīng)該被允許對(duì)應(yīng)到B(或A)中的任意多個(gè)詞蟆炊。
數(shù)學(xué)上稽莉,我們使用來(lái)描述到的對(duì)應(yīng)強(qiáng)度,這個(gè)對(duì)應(yīng)是有方向的涩搓。也就是說(shuō)污秆,一般意義上劈猪,×计矗基于此構(gòu)建兩個(gè)文檔間詞到詞的對(duì)應(yīng)矩陣战得。給定,文檔間的距離可以計(jì)算為
那么庸推,什么樣的對(duì)應(yīng)關(guān)系才是最優(yōu)的呢常侦?或者說(shuō),什么樣的文檔距離才是合理的語(yǔ)義距離呢贬媒?自然而然聋亡,我們希望算法給予較小的單詞對(duì)較大的(較強(qiáng)的對(duì)應(yīng))。數(shù)學(xué)上掖蛤,這對(duì)應(yīng)一個(gè)最小化線(xiàn)性規(guī)劃問(wèn)題杀捻。是待解的決策變量,是待優(yōu)化的目標(biāo)函數(shù)蚓庭,是給定的系數(shù)致讥。翻譯成大白話(huà),優(yōu)化問(wèn)題的目標(biāo)是器赞,尋找到使總體語(yǔ)義距離最小的詞與詞的兩兩對(duì)應(yīng)關(guān)系垢袱。然而,假設(shè)港柜,目前的優(yōu)化問(wèn)題有個(gè)平凡解请契,即。這是因?yàn)槲覀兺浛紤]詞頻信息夏醉。假設(shè)一個(gè)詞在距離公式中的總權(quán)重應(yīng)該同它的詞頻相匹配爽锥。我們有,
以上的優(yōu)化問(wèn)題有一個(gè)直觀理解畔柔。把每個(gè)單詞想象成一個(gè)車(chē)站氯夷,每個(gè)車(chē)站都有一定量的乘客,數(shù)量上等于該詞的詞頻靶擦。詞頻為零等價(jià)于車(chē)站里沒(méi)有乘客腮考。一篇文檔就是一個(gè)城市,里面有許多車(chē)站(單詞)玄捕。我們希望把城市A中的所有車(chē)站的所有乘客(即文檔A中的詞頻總量踩蔚,等于1)轉(zhuǎn)移到城市B中的車(chē)站(同B中的詞對(duì)應(yīng)起來(lái),注意B中的詞頻總量也為1)枚粘。
一方面馅闽,是從車(chē)站到車(chē)站的運(yùn)輸量,是單位運(yùn)輸成本。因此捞蛋,間運(yùn)輸?shù)目偝杀緸?img class="math-inline" src="https://math.jianshu.com/math?formula=T_%7Bij%7Dc(i%2Cj)" alt="T_{ij}c(i,j)" mathimg="1">孝冒。另一方面柬姚,車(chē)站的總發(fā)出的乘客數(shù)為拟杉。而B(niǎo)中的每個(gè)車(chē)站也有自己的最大承載人數(shù),等于對(duì)應(yīng)的詞頻量承。又因?yàn)榘l(fā)出的總乘客數(shù)必須等于接受的總乘客數(shù)搬设,所以分派到車(chē)站上,必須滿(mǎn)足總接受的乘客數(shù)為撕捍。我們希望尋找到使全部乘客的總運(yùn)輸成本拿穴,,最小的運(yùn)輸方案忧风,默色。求解優(yōu)化問(wèn)題得到最優(yōu)運(yùn)輸方案后,帶入到中得到最小成本狮腿,腿宰,這個(gè)值就是所謂的文檔A和B的word mover's distance (WMD)。越小缘厢,文檔A和B在語(yǔ)義上越接近吃度。
然而,該算法的局限性很大贴硫。第一椿每,計(jì)算復(fù)雜度約等于文檔長(zhǎng)度(唯一詞數(shù)量)的三次方。即便后文做了些優(yōu)化英遭,計(jì)算復(fù)雜度也在平方左右间护。所以,當(dāng)我們需要對(duì)大量長(zhǎng)文檔計(jì)算每一對(duì)文檔的相似度時(shí)挖诸,論文的算法顯然不適用汁尺。另一個(gè)問(wèn)題在于,算法完全忽略了詞序税灌,導(dǎo)致最終捕捉到的語(yǔ)義相似度比較粗糙均函。不過(guò),可能因?yàn)楹诵南敕ㄝ^為有趣直觀菱涤,該論文有不少后續(xù)研究苞也。比如,Wu et al. (2018) 通過(guò)理論推導(dǎo)粘秆,為WMD提出了容易計(jì)算的上界如迟。基本思路如下。
當(dāng)A和B的長(zhǎng)度太長(zhǎng)時(shí)殷勘,直接計(jì)算WMD(A,B)較為費(fèi)時(shí)此再。而且當(dāng)我們需要計(jì)算WMD(A,B),WMD(A,C),WMD(A,D), ... 時(shí),雖然都涉及到文檔A玲销,但多次計(jì)算卻只能彼此獨(dú)立進(jìn)行输拇,沒(méi)有任何可重復(fù)利用的信息。那么贤斜,可不可以為任意文檔A設(shè)計(jì)一個(gè)文檔向量策吠,然后結(jié)合一個(gè)容易計(jì)算的距離函數(shù)(論文中的核函數(shù)),使得瘩绒?這樣猴抹,我們只需提前把待比較的文檔的向量都計(jì)算好,文章中稱(chēng)為word mover's embedding (WME)锁荔,就可以快速計(jì)算所有文檔對(duì)的距離了蟀给。
WME的核心想法是,引入個(gè)長(zhǎng)度和內(nèi)容都完全隨機(jī)的短文檔作為中間量阳堕。對(duì)于任意待比較的文檔A跋理,計(jì)算一個(gè)長(zhǎng)度為的向量,第個(gè)元素是該文檔同第個(gè)隨機(jī)文檔的WMD距離的簡(jiǎn)單函數(shù)嘱丢。這個(gè)向量稱(chēng)為文檔A的WME向量薪介。文檔A和B的距離定義為它們WME向量的內(nèi)積。因此越驻,給定WME向量計(jì)算WME距離極其迅速汁政。又因?yàn)榭梢灾苯涌刂粕呻S機(jī)文檔的最大長(zhǎng)度,計(jì)算所有文檔的WME向量的總時(shí)間復(fù)雜度可控缀旁。當(dāng)然了记劈,這篇文章的核心想法是有理論背書(shū)的。比如并巍,在什么意義上目木,WME距離是WMD的近似上界?具體論述請(qǐng)參考原文懊渡。
參考文獻(xiàn)
Wu, Lingfei, Ian En-Hsu Yen, Kun Xu, Fangli Xu, Avinash Balakrishnan, Pin-Yu Chen, Pradeep Ravikumar, and Michael J. Witbrock. 2018. “Word Mover’s Embedding: From Word2Vec to Document Embedding.” In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, 4524–4534.
Kusner, Matt J., Yu Sun, Nicholas I. Kolkin, and Kilian Q. Weinberger. 2015. “From Word Embeddings to Document Distances.” In Proceedings of the 32Nd International Conference on International Conference on Machine Learning - Volume 37, 957–966. ICML’15.