作者： @蘇劍林
單位：追一科技
研究方向：NLP、神經網絡
在NLP中，我們經常要去比較兩個句子的相似度，其標準方法是想辦法將句子編碼為固定大小的向量，然後用某種幾何距離（歐氏距離、cos距離等）作為相似度。這種方案相對來說比較簡單，而且檢索起來比較快速，一定程度上能滿足工程需求。
此外，還可以直接比較兩個變長序列的差異性，比如編輯距離，它通過動態規劃找出兩個字符串之間的最優映射，然後算不匹配程度；現在我們還有Word2Vec、BERT等工具，可以將文本序列轉換為對應的向量序列，所以也可以直接比較這兩個向量序列的差異，而不是先將向量序列弄成單個向量。
後一種方案速度相對慢一點，但可以比較得更精細一些，並且理論比較優雅，所以也有一定的應用場景。本文就來簡單介紹一下屬於後者的兩個相似度指標，分別簡稱為WMD、WRD。
Earth Mover's Distance
本文要介紹的兩個指標都是以Wasserstein距離為基礎，這裡會先對它做一個簡單的介紹，相關內容也可以閱讀筆者舊作《從Wasserstein距離、對偶理論到WGAN》。Wasserstein距離也被形象地稱之為“推土機距離”（Earth Mover's Distance，EMD），因為它可以用一個“推土”的例子來通俗地表達它的含義。
最優傳輸
假設在位置 i=1,2,dots,n 處我們分佈有 p_1,p_2,dots,p_n 那麼多的土，簡單起見我們設土的總數量為1，即 p_1 + p_2 + dots + p_n=1，現在要將土推到位置 j=1,2,dots,n' 上，每處的量為 q_1, q_2, dots, q_{n'}，而從i推到j的成本為 d_{i,j}，求成本最低的方案以及對應的最低成本。
這其實就是一個經典的最優傳輸問題。我們將最優方案表示為 gamma_{i,j}，表示這個方案中要從i中把 gamma_{i,j} 數量的土推到j處，很明顯我們有約束：
begin{equation}sum_j gamma_{i,j}=p_i,quad sum_i gamma_{i,j}=q_j,quad gamma_{i,j} geq 0label{eq:cond}end{equation} \
所以我們的優化問題是： begin{equation}min_{gamma_{i,j} geq 0} sum_{i,j} gamma_{i,j} d_{i,j}quad text{s.t.} quad sum_j gamma_{i,j}=p_i,sum_i gamma_{i,j}=q_jend{equation}\
參考實現
看上去復雜，但認真觀察下就能發現上式其實就是一個線性規劃問題——在線性約束下求線性函數的極值。而scipy就自帶瞭線性規劃求解函數linprog，因此我們可以利用它實現求Wasserstein距離的函數：
import numpy as np
from scipy.optimize import linprog
def wasserstein_distance(p, q, D):
"""通過線性規劃求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, :] = 1
A_eq.append(A.reshape(-1))
for i in range(len(q)):
A = np.zeros_like(D)
A[:, i] = 1
A_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