論文筆記:From Word Embeddings To Document Distances

文檔相似度(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è)字典中有N個(gè)唯一的詞摔寨,隨意排序好去枷,w_i指字典中的第i個(gè)單詞。然后是复,統(tǒng)計(jì)每篇文檔使用了字典中的哪些詞删顶,以及每個(gè)詞使用了多少次。假設(shè)文檔A中淑廊,所有字典詞出現(xiàn)的頻率為(d_1^A,d_2^A,...,d_N^A)d_i^A \in [0, 1], \sum_{i=1}^N d_i^A=1)逗余。自然,A中沒(méi)使用的詞的頻率為0季惩。 類(lèi)似的录粱,文檔B的單詞頻率為(d_1^B,d_2^B,...,d_N^B)。記w_i^A為文檔A中出現(xiàn)的第i個(gè)字典詞蜀备。然后構(gòu)建一個(gè)N \times N的矩陣c关摇,其中元素(i,j)記為c(i,j)。具體含義上碾阁,c(i,j)=dist(w_i^A, w_j^B),也就是w_i^Aw_j^B的基于單詞詞義的語(yǔ)義距離些楣。距離矩陣c由某個(gè)詞向量模型給出的單詞向量結(jié)合一個(gè)距離函數(shù)可以得出脂凶,視為給定即可宪睹。

那么直觀上,可以定義如下文檔距離蚕钦,
dist(A,B)=\sum_{i=1,j=1}^{i=N,j=N} c(i,j)d_i^A d_j^B

即單詞對(duì)(w_i^A, w_j^B)對(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è)w_i^A,我們都需要求解一個(gè)“argmin”問(wèn)題宣渗,即在B中找到c(i,j)最小的w_j^B抖所。第二,沒(méi)有考慮詞頻痕囱。最后田轧,從語(yǔ)言理解的角度出發(fā),文檔A中的一個(gè)主體詞(題眼)鞍恢,可能同時(shí)對(duì)應(yīng)文檔B中多個(gè)具體的詞傻粘;只考慮與其語(yǔ)義最接近的一個(gè)詞,有失片面帮掉。綜上所述弦悉,原則上,w_i^A(或w_j^B)應(yīng)該被允許對(duì)應(yīng)到B(或A)中的任意多個(gè)詞蟆炊。

數(shù)學(xué)上稽莉,我們使用T_{ij} \ge 0來(lái)描述w_i^{A}w_j^{B}的對(duì)應(yīng)強(qiáng)度,這個(gè)對(duì)應(yīng)是有方向的涩搓。也就是說(shuō)污秆,一般意義上劈猪,T_{ij} \ne T_{ji}×计矗基于此構(gòu)建兩個(gè)文檔間詞到詞的對(duì)應(yīng)矩陣T战得。給定T,文檔間的距離可以計(jì)算為
dist(A,B)=\sum_{i=1,j=1}^{i=N,j=N} T_{ij} c(i,j)
那么庸推,什么樣的對(duì)應(yīng)關(guān)系T才是最優(yōu)的呢常侦?或者說(shuō),什么樣的文檔距離才是合理的語(yǔ)義距離呢贬媒?自然而然聋亡,我們希望算法給予c(i,j)較小的單詞對(duì)較大的T_{ij}(較強(qiáng)的對(duì)應(yīng))。數(shù)學(xué)上掖蛤,這對(duì)應(yīng)一個(gè)最小化線(xiàn)性規(guī)劃問(wèn)題杀捻。T_{ij}是待解的決策變量,dist(A,B)是待優(yōu)化的目標(biāo)函數(shù)蚓庭,c(i,j)是給定的系數(shù)致讥。翻譯成大白話(huà),優(yōu)化問(wèn)題的目標(biāo)是器赞,尋找到使總體語(yǔ)義距離最小的詞與詞的兩兩對(duì)應(yīng)關(guān)系垢袱。然而,假設(shè)c(i,j) \ge 0 \ \ \forall (i,j)港柜,目前的優(yōu)化問(wèn)題有個(gè)平凡解请契,即T_{ij}=0 \ \ \forall (i,j)。這是因?yàn)槲覀兺浛紤]詞頻信息夏醉。假設(shè)一個(gè)詞在距離公式中的總權(quán)重應(yīng)該同它的詞頻相匹配爽锥。我們有,
\sum_i T_{ij}=d_i^A,\sum_j T_{ij}=d_j^B

以上的優(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)枚粘。

一方面馅闽,T_{ij}是從w_i^A車(chē)站到w_j^B車(chē)站的運(yùn)輸量,c(i,j)是單位運(yùn)輸成本。因此捞蛋,(i,j)間運(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ē)站w_i^A的總發(fā)出的乘客數(shù)為d_i^A拟杉。而B(niǎo)中的每個(gè)車(chē)站也有自己的最大承載人數(shù),等于對(duì)應(yīng)的詞頻量承。又因?yàn)榘l(fā)出的總乘客數(shù)必須等于接受的總乘客數(shù)搬设,所以分派到車(chē)站w_j^B上,必須滿(mǎn)足總接受的乘客數(shù)為d_j^B撕捍。我們希望尋找到使全部乘客的總運(yùn)輸成本拿穴,dist(A,B),最小的運(yùn)輸方案忧风,T默色。求解優(yōu)化問(wèn)題得到最優(yōu)運(yùn)輸方案T^*后,帶入到dist(A,B)中得到最小成本狮腿,dist^*(A,B)腿宰,這個(gè)值就是所謂的文檔A和B的word mover's distance (WMD)。WMD(A,B)越小缘厢,文檔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è)文檔向量v_A策吠,然后結(jié)合一個(gè)容易計(jì)算的距離函數(shù)K(x,y)(論文中的核函數(shù)),使得K(v_A, v_B)\approx WMD(A,B)瘩绒?這樣猴抹,我們只需提前把待比較的文檔的向量都計(jì)算好,文章中稱(chēng)為word mover's embedding (WME)锁荔,就可以快速計(jì)算所有文檔對(duì)的距離了蟀给。

WME的核心想法是,引入R個(gè)長(zhǎng)度和內(nèi)容都完全隨機(jī)的短文檔作為中間量阳堕。對(duì)于任意待比較的文檔A跋理,計(jì)算一個(gè)長(zhǎng)度為R的向量,第i個(gè)元素是該文檔同第i個(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.

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末刽射,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子剃执,更是在濱河造成了極大的恐慌誓禁,老刑警劉巖,帶你破解...
    沈念sama閱讀 216,372評(píng)論 6 498
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件肾档,死亡現(xiàn)場(chǎng)離奇詭異摹恰,居然都是意外死亡辫继,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,368評(píng)論 3 392
  • 文/潘曉璐 我一進(jìn)店門(mén)俗慈,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)姑宽,“玉大人,你說(shuō)我怎么就攤上這事闺阱∨诔担” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 162,415評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵馏颂,是天一觀的道長(zhǎng)示血。 經(jīng)常有香客問(wèn)我,道長(zhǎng)救拉,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 58,157評(píng)論 1 292
  • 正文 為了忘掉前任瘫拣,我火速辦了婚禮亿絮,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘麸拄。我一直安慰自己派昧,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,171評(píng)論 6 388
  • 文/花漫 我一把揭開(kāi)白布拢切。 她就那樣靜靜地躺著蒂萎,像睡著了一般。 火紅的嫁衣襯著肌膚如雪淮椰。 梳的紋絲不亂的頭發(fā)上五慈,一...
    開(kāi)封第一講書(shū)人閱讀 51,125評(píng)論 1 297
  • 那天,我揣著相機(jī)與錄音主穗,去河邊找鬼泻拦。 笑死,一個(gè)胖子當(dāng)著我的面吹牛忽媒,可吹牛的內(nèi)容都是我干的争拐。 我是一名探鬼主播,決...
    沈念sama閱讀 40,028評(píng)論 3 417
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼晦雨,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼架曹!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起闹瞧,我...
    開(kāi)封第一講書(shū)人閱讀 38,887評(píng)論 0 274
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤绑雄,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后夹抗,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體绳慎,經(jīng)...
    沈念sama閱讀 45,310評(píng)論 1 310
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,533評(píng)論 2 332
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了杏愤。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片靡砌。...
    茶點(diǎn)故事閱讀 39,690評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖珊楼,靈堂內(nèi)的尸體忽然破棺而出通殃,到底是詐尸還是另有隱情,我是刑警寧澤厕宗,帶...
    沈念sama閱讀 35,411評(píng)論 5 343
  • 正文 年R本政府宣布画舌,位于F島的核電站,受9級(jí)特大地震影響已慢,放射性物質(zhì)發(fā)生泄漏曲聂。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,004評(píng)論 3 325
  • 文/蒙蒙 一佑惠、第九天 我趴在偏房一處隱蔽的房頂上張望朋腋。 院中可真熱鬧,春花似錦膜楷、人聲如沸旭咽。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 31,659評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)穷绵。三九已至,卻和暖如春特愿,著一層夾襖步出監(jiān)牢的瞬間仲墨,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 32,812評(píng)論 1 268
  • 我被黑心中介騙來(lái)泰國(guó)打工洽议, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留宗收,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 47,693評(píng)論 2 368
  • 正文 我出身青樓亚兄,卻偏偏與公主長(zhǎng)得像混稽,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子审胚,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,577評(píng)論 2 353

推薦閱讀更多精彩內(nèi)容

  • 前面的文章主要從理論的角度介紹了自然語(yǔ)言人機(jī)對(duì)話(huà)系統(tǒng)所可能涉及到的多個(gè)領(lǐng)域的經(jīng)典模型和基礎(chǔ)知識(shí)匈勋。這篇文章,甚至之后...
    我偏笑_NSNirvana閱讀 13,906評(píng)論 2 64
  • 主要內(nèi)容 自然語(yǔ)言輸入編碼 前饋網(wǎng)絡(luò) 卷積網(wǎng)絡(luò) 循環(huán)網(wǎng)絡(luò)(recurrent networks ) 遞歸網(wǎng)絡(luò)(re...
    JackHorse閱讀 4,119評(píng)論 0 2
  • 本文主要用于記錄華盛頓大學(xué)發(fā)表于2015年的一篇論文(引用量500+)膳叨,該論文主要提出了一種計(jì)算文本(語(yǔ)句)相似度...
    蘑菇轟炸機(jī)閱讀 2,091評(píng)論 0 11
  • 一洽洁、詞嵌入背景 詞嵌入(Word Embedding)是一種將文本中的詞轉(zhuǎn)換成數(shù)字向量的方法,為了使用標(biāo)準(zhǔn)機(jī)器學(xué)習(xí)...
    rosyxiao閱讀 20,872評(píng)論 0 15
  • 當(dāng)你喜歡一個(gè)女生的時(shí)候菲嘴,你會(huì)付出你的所有饿自,和我好像汰翠。 1.文本相似度計(jì)算——文本向量化 1.前言 在自然語(yǔ)言處理過(guò)...
    T_129e閱讀 474評(píng)論 0 0