?PaperWeekly 原創(chuàng) ·?作者｜蘇劍林

單位｜追一科技

研究方向｜NLP、神經網絡

在 NLP 中，我們經常要去比較兩個句子的相似度，其標準方法是想辦法將句子編碼為固定大小的向量，然后用某種幾何距離（歐氏距離、cos 距離等）作為相似度。這種方案相對來說比較簡單，而且檢索起來比較快速，一定程度上能滿足工程需求。

此外，還可以直接比較兩個變長序列的差異性，比如編輯距離，它通過動態(tài)規(guī)劃找出兩個字符串之間的最優(yōu)映射，然后算不匹配程度；現在我們還有 Word2Vec、BERT 等工具，可以將文本序列轉換為對應的向量序列，所以也可以直接比較這兩個向量序列的差異，而不是先將向量序列弄成單個向量。

后一種方案速度相對慢一點，但可以比較得更精細一些，并且理論比較優(yōu)雅，所以也有一定的應用場景。本文就來簡單介紹一下屬于后者的兩個相似度指標，分別簡稱為 WMD、WRD。

Earth Mover's Distance

本文要介紹的兩個指標都是以?Wasserstein 距離為基礎，這里會先對它做一個簡單的介紹，相關內容也可以閱讀筆者舊作從 Wasserstein 距離、對偶理論到WGAN。

Wasserstein 距離也被形象地稱之為“推土機距離”（Earth Mover's Distance，EMD），因為它可以用一個“推土”的例子來通俗地表達它的含義。

1.1 最優(yōu)傳輸

假設在位置 處我們分布有 那么多的土，簡單起見我們設土的總數量為 1，即 ，現在要將土推到位置 上，每處的量為 ，而從 i 推到 j 的成本為 ，求成本最低的方案以及對應的最低成本。

這其實就是一個經典的最優(yōu)傳輸問題。我們將最優(yōu)方案表示為 ，表示這個方案中要從 i 中把 數量的土推到 j 處，很明顯我們有約束：

所以我們的優(yōu)化問題是：

1.2 參考實現

看上去復雜，但認真觀察下就能發(fā)現上式其實就是一個線性規(guī)劃問題——在線性約束下求線性函數的極值。而scipy就自帶了線性規(guī)劃求解函數linprog，因此我們可以利用它實現求 Wasserstein 距離的函數：

import?numpy?as?np from?scipy.optimize?import?linprogdef?wasserstein_distance(p,?q,?D):"""通過線性規(guī)劃求Wasserstein距離p.shape=[m],?q.shape=[n],?D.shape=[m,?n]p.sum()=1,?q.sum()=1,?p∈[0,1],?q∈[0,1]"""A_eq?=?[]for?i?in?range(len(p)):A?=?np.zeros_like(D)A[i,?:]?=?1A_eq.append(A.reshape(-1))for?i?in?range(len(q)):A?=?np.zeros_like(D)A[:,?i]?=?1A_eq.append(A.reshape(-1))A_eq?=?np.array(A_eq)b_eq?=?np.concatenate([p,?q])D?=?D.reshape(-1)result?=?linprog(D,?A_eq=A_eq[:-1],?b_eq=b_eq[:-1])return?result.fun

讀者可以留意到，在傳入約束的時候用的是A_eq=A_eq[:-1], b_eq=b_eq[:-1]，也就是去掉了最后一個約束。

這是因為 ，所以（1）中的等式約束本身存在冗余，而實際計算中有時候可能存在浮點誤差，導致冗余的約束之間相互矛盾，從而使得線性規(guī)劃的求解失敗，所以干脆去掉最后一個冗余的約束，減少出錯的可能性。

Word Mover's Distance

很明顯，Wasserstein 距離適合于用來計算兩個不同長度的序列的差異性，而我們要做語義相似度的時候，兩個句子通常也是不同長度的，剛好對應這個特性，因此很自然地就會聯想到 Wasserstein 距離也許可以用來比較句子相似度，而首次進行這個嘗試的是論文 From Word Embeddings To Document Distances [1]?。

2.1 基本形式

設有兩個句子 ，經過某種映射（比如? Word2Vec 或者 BERT）后，它們變成了對應的向量序列 ，現在我們就想辦法用 Wasserstein 距離來比較這兩個序列的相似度。

根據前一節(jié)的介紹，Wasserstein 距離需要知道 三個量，我們逐一把它們都定義好即可。

由于沒有什么先驗知識，所以我們可以很樸素地將讓 ，所以現在還剩 。顯然， 代表著第一個序列的向量 與第二個序列的向量 的某種差異性，簡單起見我們可以用歐氏距離 ，所以兩個句子的差異程度可以表示為：

這便是?Word Mover's Distance（WMD）（推詞機距離），大概可以理解為將一個句子變?yōu)榱硪粋€句子的最短路徑，某種意義上也可以理解為編輯距離的光滑版。實際使用的時候，通常會去掉停用詞后再計算 WMD。

▲ Word Mover's Distance 的示意圖，來自論文 From Word Embeddings To Document Distances

2.2 參考實現

參考實現如下：

def?word_mover_distance(x,?y):"""WMD（Word?Mover's?Distance）的參考實現x.shape=[m,d],?y.shape=[n,d]"""p?=?np.ones(x.shape[0])?/?x.shape[0]q?=?np.ones(y.shape[0])?/?y.shape[0]D?=?np.sqrt(np.square(x[:,?None]?-?y[None,?:]).mean(axis=2))return?wasserstein_distance(p,?q,?D)

2.3 下界公式

如果是檢索場景，要將輸入句子跟數據庫里邊所有句子一一算 WMD 并排序的話，那計算成本是相當大的，所以我們要盡量減少算 WMD 的次數，比如通過一些更簡單高效的指標來過濾掉一些樣本，然后才對剩下的樣本算 WMD。

幸運的是，我們確實可以推導出 WMD 的一個下界公式，原論文稱之為?Word Centroid Distance (WCD)：

也就是說，WMD 大于兩個句子的平均向量的歐氏距離，所以我們要檢索 WMD 比較小的句子時，可以先用 WCD 把距離比較大的句子先過濾掉，然后剩下的采用? WMD 比較。

Word Rotator's Distance

WMD 其實已經挺不錯了，但非要雞蛋里挑骨頭的話，還是能挑出一些缺點來：

它使用的是歐氏距離作為語義差距度量，但從 Word2Vec 的經驗我們就知道要算詞向量的相似度的話，用 往往比歐氏距離要好；

WMD 理論上是一個無上界的量，這意味著我們不大好直觀感知相似程度，從而不能很好調整相似與否的閾值。

為了解決這兩個問題，一個比較樸素的想法是將所有向量除以各自的模長來歸一化后再算 WMD，但這樣就完全失去了模長信息了。

最近的論文 Word Rotator's Distance: Decomposing Vectors Gives Better Representations [2]?則巧妙地提出，在歸一化的同時可以把模長融入到約束條件 p,q 里邊去，這就形成了? WRD。

3.1 基本形式

首先，WRD 提出了“詞向量的模長正相關于這個詞的重要程度”的觀點，并通過一些實驗結果驗證了這個觀點。事實上，這個觀點跟筆者之前提出的 simpler glove 模型的觀點一致，參考《更別致的詞向量模型(五)：有趣的結果》[3] 。

而在 WMD 中， 某種意義上也代表著對應句子中某個詞的重要程度，所以我們可以設：

然后 就用余弦距離：

得到：

這就是 Word Rotator's Distance (WRD) 了。由于使用的度量是余弦距離，所以兩個向量之間的變換更像是一種旋轉（rotate）而不是移動（move），所以有了這個命名；同樣由于使用了余弦距離，所以它的結果在 [-1,1] 內，相對來說更容易去感知其相似程度。

3.2 參考實現

參考實現如下：

def?word_rotator_distance(x,?y):"""WRD（Word?Rotator's?Distance）的參考實現x.shape=[m,d],?y.shape=[n,d]"""x_norm?=?(x**2).sum(axis=1,?keepdims=True)**0.5y_norm?=?(y**2).sum(axis=1,?keepdims=True)**0.5p?=?x_norm[:,?0]?/?x_norm.sum()q?=?y_norm[:,?0]?/?y_norm.sum()D?=?1?-?np.dot(x?/?x_norm,?(y?/?y_norm).T)return?wasserstein_distance(p,?q,?D)def?word_rotator_similarity(x,?y):"""1?-?WRDx.shape=[m,d],?y.shape=[n,d]"""return?1?-?word_rotator_distance(x,?y)

3.3?下界公式

同 WMD 一樣，我們也可以推導出 WRD 的一個下界公式：

不過這部分內容并沒有出現在 WRD 的論文中，只是筆者自行補充的。

小結

文本介紹了兩種文本相似度算法 WMD、WRD，它們都是利用 Wasserstein 距離（Earth Mover's Distance，推土機距離）來直接比較兩個不定長向量的差異性。這類相似度算法在效率上會有所欠缺，但是理論上比較優(yōu)雅，而且效果也頗為不錯，值得學習一番。

參考鏈接

[1] http://proceedings.mlr.press/v37/kusnerb15.html

[2] https://arxiv.org/abs/2004.15003

[3] https://kexue.fm/archives/4677

點擊以下標題查看更多往期內容：?

• NLP中的Mask全解
  

• 從ACL和ICLR看知識圖譜嵌入的近期研究進展
  

• 對比學習（Contrastive Learning）相關進展梳理
  

• GELU的兩個初等函數近似是怎么來的？
  

• BERT在小米NLP業(yè)務中的實戰(zhàn)探索
  

• 復旦大學邱錫鵬教授：NLP預訓練模型綜述

#投 稿?通 道#

?讓你的論文被更多人看到?

如何才能讓更多的優(yōu)質內容以更短路徑到達讀者群體，縮短讀者尋找優(yōu)質內容的成本呢？答案就是：你不認識的人。

總有一些你不認識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學者和學術靈感相互碰撞，迸發(fā)出更多的可能性。?

PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優(yōu)質內容，可以是最新論文解讀，也可以是學習心得或技術干貨。我們的目的只有一個，讓知識真正流動起來。

?????來稿標準：

? 稿件確系個人原創(chuàng)作品，來稿需注明作者個人信息（姓名+學校/工作單位+學歷/職位+研究方向）?

? 如果文章并非首發(fā)，請在投稿時提醒并附上所有已發(fā)布鏈接?

? PaperWeekly 默認每篇文章都是首發(fā)，均會添加“原創(chuàng)”標志

?????投稿郵箱：

? 投稿郵箱：hr@paperweekly.site?

? 所有文章配圖，請單獨在附件中發(fā)送?

? 請留下即時聯系方式（微信或手機），以便我們在編輯發(fā)布時和作者溝通

????

現在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關注」訂閱我們的專欄吧

關于PaperWeekly

PaperWeekly 是一個推薦、解讀、討論、報道人工智能前沿論文成果的學術平臺。如果你研究或從事 AI 領域，歡迎在公眾號后臺點擊「交流群」，小助手將把你帶入 PaperWeekly 的交流群里。

總結

以上是生活随笔為你收集整理的从EMD、WMD到WRD：文本向量序列的相似度计算的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。