自然语言处理之词移距离Word Mover's Distance
目錄
?
一、從EMD到WMD
二、詞移距離（WMD）
舉例說(shuō)明
帶監(jiān)督的詞移距離（Supervised Word Mover’s Distance）
三、word2vec實(shí)現(xiàn)詞移距離
四、詞移距離來(lái)衡量唐詩(shī)詩(shī)句的相關(guān)性
一、從EMD到WMD
EMD算法簡(jiǎn)介，該部分引用自[1]。
Earth Mover’s Distance (EMD)，和歐氏距離一樣，他們都是一種距離度量的定義，可以用來(lái)測(cè)量某分布之間的距離。EMD主要應(yīng)用在圖像處理和語(yǔ)音信號(hào)處理領(lǐng)域。
EMD問(wèn)題如下圖所示
給定兩個(gè)簽名(或者叫分布、特征量集合)P和Q，P為m個(gè)特征量Pi和其權(quán)重wPi的集合，記作P={(P1,wP1),(P2,wP2),...(Pm,wPm)}，如圖左側(cè)部分。同樣的，還有一個(gè)分布Q，Q=(Q1,wQ1),(Q2,wQ2),...(Qn,wQn)，即上圖右側(cè)部分。在計(jì)算這個(gè)這兩個(gè)簽名的Earth Mover's Distance(EMD)前，我們要先定義好P、Q中任意取一個(gè)特征量(?Pi?and?Qj?)之間的距離（這個(gè)距離叫g(shù)round distance，兩個(gè)簽名之間EMD依賴于簽名中特征量之間的ground distance）。當(dāng)這兩個(gè)特征量是向量時(shí)得到的是歐式距離，當(dāng)這兩個(gè)特征量是概率分布時(shí)得到的是相對(duì)熵(KL距離/Kullback–Leibler divergence)。現(xiàn)在，給定兩個(gè)簽名(P和Q)，只要計(jì)算好每?jī)蓚€(gè)特征量之間的距離，系統(tǒng)就能給出這兩個(gè)簽名之間的距離了。
EMD?實(shí)際上是線性規(guī)劃中運(yùn)輸問(wèn)題的最優(yōu)解。首先，簡(jiǎn)要描述下運(yùn)輸問(wèn)題。我們假設(shè)這個(gè)例子是從多個(gè)工廠運(yùn)輸貨物到多個(gè)倉(cāng)庫(kù)。在上圖左側(cè)，P從在P1?到?Pm代表m座工廠，工廠Pi有重量為wPi的貨物。在上圖右側(cè)，Q從Q1到Qn代表n個(gè)倉(cāng)庫(kù)，倉(cāng)庫(kù)Qj最大容量為wQj。貨物之間沒(méi)有什么區(qū)別，都是同一類東西。每個(gè)倉(cāng)庫(kù)都希望裝盡可能多的貨物。如何盡可能高效把所有貨物(實(shí)際上不一定是所有貨物，部分也OK)從P運(yùn)送到Q，就是運(yùn)輸問(wèn)題的優(yōu)化目標(biāo)。在本例中，P、Q都是離散的，那么EMD可以用運(yùn)輸問(wèn)題的Hungarian算法來(lái)計(jì)算它們之間的距離。挖個(gè)坑而已，這里不具體討論。
這里定義，貨物從工廠Pi運(yùn)到倉(cāng)庫(kù)Qj，距離是，運(yùn)送貨物的重量為。這樣一次運(yùn)輸需要的工作量為?。顯然，距離越遠(yuǎn)、或貨物越重，工作量就越大。(注：運(yùn)輸可能是多對(duì)多的，即一個(gè)工廠運(yùn)輸貨物到多個(gè)倉(cāng)庫(kù)，或者一個(gè)倉(cāng)庫(kù)接收多個(gè)工廠的貨物。)貨物從工廠運(yùn)到倉(cāng)庫(kù)需要很多次這樣的運(yùn)輸，經(jīng)過(guò)一些計(jì)算和優(yōu)化，這時(shí)我們得到了工作量總和的最小值W。
W =?
距離是事先定義的，所以運(yùn)輸量fij是式中唯一的變量，對(duì)作如下4個(gè)約束：
(1)?運(yùn)輸過(guò)程從工廠P到倉(cāng)庫(kù)Q，不能反向。
≥ 0 (1≤i≤m,1≤j≤n)
(2)?從工廠Pi一次次運(yùn)出去的所有貨物重量的和不可能超過(guò)該工廠中所有貨物的總重量wPi
?≤ wPi (1≤i≤m)
(3)?倉(cāng)庫(kù)Qj接收的所有貨物總重量不可能超過(guò)其總?cè)萘縲Qj。
≤ wQj (1≤j≤n)
(4)?總運(yùn)輸量的上限是工廠中貨物總重、倉(cāng)庫(kù)總?cè)萘恐械淖钚≈怠?/p>
當(dāng)倉(cāng)庫(kù)的總?cè)萘亢凸S貨物總重不一樣時(shí)，我們才需要上述第4個(gè)限制條件。倉(cāng)庫(kù)總?cè)萘勘蓉浳锟偭看蟮脑捑涂梢匀窟\(yùn)輸了，所以這時(shí)候呢，運(yùn)輸量的上限就是貨物總量。但如果貨物總量比倉(cāng)庫(kù)總?cè)萘看蟮脑?#xff0c;就不能全部運(yùn)輸了，這時(shí)候，運(yùn)輸量的上限就是倉(cāng)庫(kù)的總?cè)萘坷病７奖闫鹨?jiàn)，本例中當(dāng)倉(cāng)庫(kù)的總?cè)萘亢凸S貨物總重是一樣的。
運(yùn)輸問(wèn)題的具體解答此處省略不討論，假設(shè)這個(gè)時(shí)候我們已經(jīng)得到了最優(yōu)解。為了使EMD不會(huì)隨著總運(yùn)輸量的變化而變化，每一次的運(yùn)輸量還要除以總運(yùn)輸量，以達(dá)到歸一化的目的。（in order to avoid favoring smaller signatures in the case of partial matching.）在后面的具體例子中會(huì)對(duì)它進(jìn)行詳細(xì)描述。
很自然可以想到，給定兩個(gè)簽名，把一個(gè)變成另一個(gè)所需要的最小工作量，就是EMD對(duì)距離的定義，這里的「工作量」要基于用戶對(duì)ground distance的定義，即特征量之間的距離的定義。然而，當(dāng)特征量非常多的時(shí)候，由于要做一一匹配，其計(jì)算量是非常大的。因此，有人提出了一種將多個(gè)特征量組合起來(lái)做向量量化編碼(Vector Quantization)后再組成簽名的方法。
EMD算法在自然語(yǔ)言處理領(lǐng)域的應(yīng)用
通過(guò)詞嵌入（Word Embedding），我們可以得到詞語(yǔ)的分布式低維實(shí)數(shù)向量表示，我們可以計(jì)算詞語(yǔ)之間的距離，即我們可以得到dij，因此可以將EMD引入自然語(yǔ)言處理領(lǐng)域。
Matt等人[2]將詞嵌入與EMD相聯(lián)系，用來(lái)度量文檔距離。提出了WMD（word mover’s distance）算法，以及WCD（word centroid distance）、RWMD（relaxed word mover’s distance）兩種犧牲精度降低復(fù)雜度的算法。
如何將一個(gè)文檔變?yōu)榉植糚這種形式？
用歸一化的詞袋模型（nBOW，?normalized bag-of-words）表示。其中P1表示詞語(yǔ)，用計(jì)算該詞的權(quán)重，其中表示詞語(yǔ)i在文檔中出現(xiàn)了次，P1的特征量用該詞語(yǔ)的詞向量表示。一個(gè)nBOW文檔向量是比較稀疏的，因?yàn)榇蟛糠值脑~語(yǔ)不會(huì)出現(xiàn)在該文檔中，且在生成文檔向量時(shí)，去掉的停用詞。用歐式距離計(jì)算詞語(yǔ)與詞語(yǔ)之間的距離。
假定數(shù)據(jù)集中只有兩個(gè)文檔，則這兩個(gè)文檔生成的歸一化nBOW向量如下圖所示。
轉(zhuǎn)移量用矩陣T表示，生成的矩陣T如下圖所示
表示詞語(yǔ)i有多少轉(zhuǎn)移到了詞語(yǔ)j，
綜上，Matt等人提出了WMD算法，WMD是EMD的一個(gè)特殊形式。
由于文檔向量是經(jīng)過(guò)歸一化的，與EMD算法相比，WMD沒(méi)有
的約束。
WMD算法的復(fù)雜度是，其中p表示nBOW模型的長(zhǎng)度，即數(shù)據(jù)集中不同詞語(yǔ)的數(shù)目（去處停用詞）。該算法已經(jīng)有成熟的解決方法，詳情參考[3]
算法的改進(jìn)
為了降低模型的計(jì)算復(fù)雜度，Matt等人提出了WCD和RWMD兩個(gè)算法，這兩個(gè)算法是WMD的兩個(gè)不同下限，通過(guò)降低精度來(lái)降低計(jì)算復(fù)雜度。
Word centroid distance(WCD)
將作為WCD。其中X是一個(gè)的矩陣，d表示詞向量的維度，p表示nBOW模型的長(zhǎng)度。d表示一個(gè)nBOW文檔向量。如下圖所示
WCD的復(fù)雜度度是
Relaxed word moving distance(RWMD)
通過(guò)放松限制條件，得到WMD的下限。通過(guò)去掉條件2，保留條件1，我們得到
通過(guò)去掉條件2，其實(shí)是去掉了倉(cāng)庫(kù)容量的限制，我們可以將貨物全部運(yùn)到離其最近的倉(cāng)庫(kù)，而不需要考慮倉(cāng)庫(kù)的容量。我們?cè)谶\(yùn)某個(gè)貨物時(shí)，往離該貨物最近的倉(cāng)庫(kù)運(yùn)送，即在轉(zhuǎn)移詞語(yǔ)i時(shí)，我們只向與詞語(yǔ)i距離最近的詞語(yǔ)j轉(zhuǎn)移。
當(dāng)我們?nèi)サ魲l件1，保留條件2時(shí)，我們得到，與基本相同。去掉條件1，其實(shí)是去掉了貨物量的限制，我們可以將貨物源源不斷的運(yùn)到倉(cāng)庫(kù)中，直到倉(cāng)庫(kù)滿了為止。我們?cè)跒樘顫M某個(gè)倉(cāng)庫(kù)選擇運(yùn)送的貨物時(shí)，選擇離該倉(cāng)庫(kù)距離最近的貨物，即在詞語(yǔ)j接收時(shí)，我們選擇接收與詞語(yǔ)j距離近詞語(yǔ)i。
我們將作為RWMD。在計(jì)算文檔距離時(shí)，我們可以事先計(jì)算該數(shù)據(jù)集中，每個(gè)詞語(yǔ)之間的相似度，復(fù)雜度為，之后計(jì)算兩個(gè)文檔的時(shí)，只需要。
WCD vs. RWMD
RWMD相比WCD更緊，具體的驗(yàn)證可以參考論文[2]。
讀完論文[2]后，有些問(wèn)題：對(duì)比實(shí)驗(yàn)使用的是歐式距離，歐式距離是否適用于所有的文本表示方式？譬如LDA得到的應(yīng)該是一個(gè)主題概率分布向量，對(duì)于概率分布KL距離是否更合適？
?
Reference:
[1]?http://blog.mckelv.in/articles/1474.html
[2] From word embeddings to document distances, Matt J. kusner et al.
[3] Fast and robust earth mover’s distance, Pele et al.
二、詞移距離（WMD）
假如現(xiàn)在有一個(gè)任務(wù)，是判斷兩段文本之間的相似性，那我們應(yīng)該怎么做呢？一個(gè)很自然的想法是用word2vec對(duì)兩段文本的詞向量化，然后再利用歐氏距離或者余弦相似性進(jìn)行求解。不過(guò)這種方法有著致命的缺陷，即無(wú)法從文檔整體上來(lái)考慮相似性，僅僅是基于詞，這就造成了很大的信息缺失問(wèn)題，下面要介紹的這種方法可以從文檔整體上來(lái)考慮兩個(gè)文檔之間的相似性，這種技術(shù)稱為詞移距離（WMD）。
究竟什么才是詞移距離呢？這要從Word2Vec講起。Word2Vec將詞映射為一個(gè)詞向量，在這個(gè)向量空間中，語(yǔ)義相似的詞之間距離會(huì)比較小，而詞移距離（WMD）正是基于word2vec的這一特性開(kāi)發(fā)出來(lái)的。
正如上面所講到的，Word2Vec得到的詞向量可以反映詞與詞之間的語(yǔ)義差別，那么如果我們希望有一個(gè)距離能夠反映文檔和文檔之間的相似度，應(yīng)該怎么做呢？一個(gè)想法是將文檔距離建模成兩個(gè)文檔中詞的語(yǔ)義距離的一個(gè)組合，比如說(shuō)對(duì)兩個(gè)文檔中的任意兩個(gè)詞所對(duì)應(yīng)的詞向量求歐氏距離然后再加權(quán)求和，大概是這樣的形式：∑i,j=1nTijc(i,j)∑i,j=1nTijc(i,j)，其中c(i,j)c(i,j)為i,ji,j兩個(gè)詞所對(duì)應(yīng)的詞向量的歐氏距離。
那我們?cè)鯓拥玫竭@個(gè)加權(quán)矩陣TT呢？又或者說(shuō)這個(gè)加權(quán)矩陣TT代表什么含義呢？在我看來(lái)，這個(gè)加權(quán)矩陣TT有些類似于HMM中的狀態(tài)轉(zhuǎn)移矩陣，只不過(guò)其中的概率轉(zhuǎn)換為權(quán)重了而已。我們?cè)賮?lái)看下面這個(gè)圖：
這里有兩個(gè)文檔，去除停用詞后，每篇文檔僅剩下4個(gè)詞，我們就是要用這四個(gè)詞來(lái)比較兩個(gè)文檔之間的相似度。在這里，我們假設(shè)’Obama’這個(gè)詞在文檔1中的的權(quán)重為0.5（可以簡(jiǎn)單地用詞頻或者TFIDF進(jìn)行計(jì)算），那么由于’Obama’和’president’的相似度很高，那么我們可以給由’Obama’移動(dòng)到’president’很高的權(quán)重，這里假設(shè)為0.4，文檔2中其他的詞由于和’Obama’的距離比較遠(yuǎn)，所以會(huì)分到更小的權(quán)重。這里的約束是，由文檔1中的某個(gè)詞ii移動(dòng)到文檔2中的各個(gè)詞的權(quán)重之和應(yīng)該與文檔1中的這個(gè)詞ii的權(quán)重相等，即’Obama’要把自己的權(quán)重（0.5）分給文檔2中的各個(gè)詞。同樣，文檔2中的某個(gè)詞jj所接受到由文檔1中的各個(gè)詞所流入的權(quán)重之和應(yīng)該等于詞jj在文檔2中的權(quán)重。
為什么要有這樣的操作呢？因?yàn)槲覀兛梢栽O(shè)想，∑i,j=1nTijc(i,j)∑i,j=1nTijc(i,j)代表的是文檔1要轉(zhuǎn)換為文檔2所需要付出的總代價(jià)。將這種代價(jià)求得下界即最小化之后，即可求得所有文檔a中單詞轉(zhuǎn)移到文檔b中單詞的最短總距離，代表兩個(gè)文檔之間的相似度。
舉例說(shuō)明
形象化的考慮一下，我們有三個(gè)文檔，文檔1中每個(gè)詞都跟“王者榮耀”緊密相關(guān)；文檔2中只有一個(gè)詞跟“王者榮耀”密切相關(guān)，其余詞都跟“王者榮耀”完全無(wú)關(guān)；文檔3中有一個(gè)詞跟“王者榮耀”密切相關(guān)，其他詞都跟“王者榮耀”有點(diǎn)關(guān)系但關(guān)聯(lián)性不大。那么可以想象，WMD(d1,d2)>WMD(d1,d3)WMD(d1,d2)>WMD(d1,d3)，因?yàn)槲臋n1中的詞和文檔2中和“王者榮耀”完全無(wú)關(guān)的詞之間的距離要比文檔1中的詞和文檔3中和“王者榮耀”有點(diǎn)關(guān)系但關(guān)聯(lián)性不大的詞之間的距離要大。
帶監(jiān)督的詞移距離（Supervised Word Mover’s Distance）
我們理解了WMD距離,那么問(wèn)題來(lái)了,學(xué)習(xí)這個(gè)權(quán)重矩陣用來(lái)聚類雖好(告訴我們哪些文檔比較相近),但是, 用來(lái)分類卻很差，這就要引入監(jiān)督學(xué)習(xí)。
為什么? 因?yàn)橐恍┪恼码m然近義詞很多, 但是表達(dá)的不是一個(gè)語(yǔ)義和主題. 比如: I love playing football 和 I like playing piano . 雖然看起來(lái)句式差不多, 可能會(huì)歸為同類, 但是如果打標(biāo)簽時(shí)如果是”運(yùn)動(dòng)”和”藝術(shù)”兩類, 顯然就不能用WMD直接分類了. 因?yàn)? WMD沒(méi)有加入 football和”運(yùn)動(dòng)”是強(qiáng)相關(guān)的信息.
所以, 論文Supervised Word Mover’s Distance給出的解決方案就是在WMD距離中加入可以訓(xùn)練類別權(quán)重的功能:
這里的dd加入了類別權(quán)重ww:
單詞間距離也要進(jìn)行調(diào)整(單詞間距離也因?yàn)轭悇e不同需要調(diào)整距離),加入訓(xùn)練參數(shù)矩陣AA。
詞移距離（Word Mover's Distance）是在詞向量的基礎(chǔ)上發(fā)展而來(lái)的用來(lái)衡量文檔相似性的度量。
本文主要介紹了詞移距離的源碼實(shí)現(xiàn)，并給出了使用實(shí)例計(jì)算文本相似度。
三、word2vec實(shí)現(xiàn)詞移距離
安裝gensim?并且有pyemd，詳情見(jiàn)下def wmdistance(self, document1, document2):"""Compute the Word Mover's Distance between two documents. When using thiscode, please consider citing the following papers:.. Ofir Pele and Michael Werman, "A linear time histogram metric for improved SIFT matching"... Ofir Pele and Michael Werman, "Fast and robust earth mover's distances"... Matt Kusner et al. "From Word Embeddings To Document Distances".Note that if one of the documents have no words that exist in theWord2Vec vocab, `float('inf')` (i.e. infinity) will be returned.This method only works if `pyemd` is installed (can be installed via pip, but requires a C compiler).Example:>>> # Train word2vec model.>>> model = Word2Vec(sentences)>>> # Some sentences to test.>>> sentence_obama = 'Obama speaks to the media in Illinois'.lower().split()>>> sentence_president = 'The president greets the press in Chicago'.lower().split()>>> # Remove their stopwords.>>> from nltk.corpus import stopwords>>> stopwords = nltk.corpus.stopwords.words('english')>>> sentence_obama = [w for w in sentence_obama if w not in stopwords]>>> sentence_president = [w for w in sentence_president if w not in stopwords]>>> # Compute WMD.>>> distance = model.wmdistance(sentence_obama, sentence_president)"""if not PYEMD_EXT:raise ImportError("Please install pyemd Python package to compute WMD.")# Remove out-of-vocabulary words.len_pre_oov1 = len(document1)len_pre_oov2 = len(document2)document1 = [token for token in document1 if token in self]document2 = [token for token in document2 if token in self]diff1 = len_pre_oov1 - len(document1)diff2 = len_pre_oov2 - len(document2)if diff1 > 0 or diff2 > 0:logger.info('Removed %d and %d OOV words from document 1 and 2 (respectively).',diff1, diff2)if len(document1) == 0 or len(document2) == 0:logger.info('At least one of the documents had no words that were''in the vocabulary. Aborting (returning inf).')return float('inf')dictionary = Dictionary(documents=[document1, document2])vocab_len = len(dictionary)if vocab_len == 1:# Both documents are composed by a single unique tokenreturn 0.0# Sets for faster look-up.docset1 = set(document1)docset2 = set(document2)# Compute distance matrix.distance_matrix = zeros((vocab_len, vocab_len), dtype=double)for i, t1 in dictionary.items():for j, t2 in dictionary.items():if not t1 in docset1 or not t2 in docset2:continue# Compute Euclidean distance between word vectors.distance_matrix[i, j] = sqrt(np_sum((self[t1] - self[t2])**2))if np_sum(distance_matrix) == 0.0:# `emd` gets stuck if the distance matrix contains only zeros.logger.info('The distance matrix is all zeros. Aborting (returning inf).')return float('inf')def nbow(document):d = zeros(vocab_len, dtype=double)nbow = dictionary.doc2bow(document) # Word frequencies.doc_len = len(document)for idx, freq in nbow:d[idx] = freq / float(doc_len) # Normalized word frequencies.return d# Compute nBOW representation of documents.d1 = nbow(document1)d2 = nbow(document2)# Compute WMD.return emd(d1, d2, distance_matrix)四、詞移距離來(lái)衡量唐詩(shī)詩(shī)句的相關(guān)性
詞移距離在gensim中有封裝包，代碼實(shí)現(xiàn)如上，本例子直接調(diào)用gensim中封裝函數(shù)
全唐詩(shī)txt鏈接：https://files.cnblogs.com/files/combfish/%E5%85%A8%E5%94%90%E8%AF%97.zip。
步驟：
1. 預(yù)處理語(yǔ)料集： 唐詩(shī)的斷句分詞，斷句基于標(biāo)點(diǎn)符號(hào)，分詞依靠結(jié)巴分詞
2. gensim訓(xùn)練詞向量模型與wmd相似性模型
3. 查詢
import?jieba from?nltk?import?word_tokenize from?nltk.corpus?import?stopwords from?time?import?time start_nb?=?time() import?loggingprint(20*'*','loading data',40*'*') f=open('全唐詩(shī).txt',encoding='utf-8') lines=f.readlines() corpus=[] documents=[] useless=[',','.','(',')','!','?','\'','\"',':','<','>','，',?'。',?'（',?'）',?'！',?'？',?'’',?'“','：','《','》','[',']','【','】'] for?each?in?lines:each=each.replace('\n','')each.replace('-','')each=each.strip()each=each.replace(' ','')if(len(each)>3):if(each[0]!='卷'):documents.append(each)each=list(jieba.cut(each))text=[w?for?w?in?each?if?not?w?in?useless]corpus.append(text)print(len(corpus))print(20*'*','trainning models',40*'*') from?gensim.models?import?Word2Vec model?=?Word2Vec(corpus, workers=3, size=100)# Initialize WmdSimilarity. from?gensim.similarities?import?WmdSimilarity num_best?=?10 instance?=?WmdSimilarity(corpus, model, num_best=10)print(20*'*','testing',40*'*') while?True:sent?=?input('輸入查詢語(yǔ)句： ')sent_w?=?list(jieba.cut(sent))query?=?[w?for?w?in?sent_w?if?not?w?in?useless]sims?=?instance[query]??# A query is simply a "look-up" in the similarity class.# Print the query and the retrieved documents, together with their similarities.print('Query:')print(sent)for?i?in?range(num_best):printprint('sim = %.4f'?%?sims[i][1])print(documents[sims[i][0]])
結(jié)果：從結(jié)果kan
?
?
?
?
?
?
?
相關(guān)參考：
https://www.cnblogs.com/combfish/p/8126857.html
詞移距離的具體介紹http://blog.csdn.net/qrlhl/article/details/78512598
官方例子
https://github.com/RaReTechnologies/gensim/blob/c971411c09773488dbdd899754537c0d1a9fce50/docs/notebooks/WMD_tutorial.ipynb?
如何通過(guò)詞向量技術(shù)來(lái)計(jì)算2個(gè)文檔的相似度?
Supervised Word Mover’s Distance (可監(jiān)督的詞移距離) – NIPS 2016論文精選#2
https://blog.csdn.net/qrlhl/article/details/78512598
總結(jié)
以上是生活随笔為你收集整理的自然语言处理之词移距离Word Mover's Distance的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： hbuilderx 各种项目 开发区别
- 下一篇： 例题：索洛模型——要素支付