沃瑟斯坦度量

沃瑟斯坦度量（英語：Wasserstein metric）又稱為沃瑟斯坦距離（Wasserstein distance）、坎托羅維奇–魯賓施泰因度量（Kantorovich–Rubinstein metric），在數學中是指某一給定度量空間 $M$ 上概率分佈之間的距離函數，其名稱源於俄裔美國數學家列昂尼德·沃瑟斯坦（英語：Leonid Vaserstein）。

直觀而言，可以將每個概率分佈都看作 $M$ 上堆積的單位數量的土堆，則沃瑟斯坦度量便是指將一個土堆變成另一土堆的最小代價，可定義為需要移動的土壤量乘以需要移動的平均距離。這一問題於1781年由法國數學家加斯帕爾·蒙日首次正式提出。基於上述土堆類比，該度量在計算機科學中也被稱為推土機距離。

「沃瑟斯坦距離」這一名稱是蘇聯數學家羅蘭·多布魯申（英語：Roland Dobrushin）於1970年提出的，他在沃瑟斯坦關於描述大型自動機系統的馬爾可夫過程的工作中了解到了這一概念。^[1]不過早在1939年，另一位蘇聯數學家列昂尼德·坎托羅維奇就在研究貨物的最優運輸問題時最早定義了該度量。^[2]因此一些學者認為使用「坎托羅維奇度量」或「坎托羅維奇距離」來稱呼此度量更為恰當。

定義

對於一個度量空間 $(M,d)$ ，假設 $M$ 上每個博雷爾概率測度都是拉東測度（即該度量空間為拉東空間）。對有限 $p\geq 1$ ， $P_{p}(M)$ 表示 $M$ 上所有有 $p$ 階矩的概率測度 $\mu$ 的集合，即 $M$ 中存在 $x_{0}$ 滿足

\int _{M}d(x,x_{0})^{p}\,\mathrm {d} \mu (x)<\infty .

於是， $P_{p}(M)$ 中兩個概率測度 $\mu$ 和 $\nu$ 之間的 $p$ 階沃瑟斯坦距離可定義為

W_{p}(\mu ,\nu ):=\left(\inf _{\gamma \in \Gamma (\mu ,\nu )}\int _{M\times M}d(x,y)^{p}\,\mathrm {d} \gamma (x,y)\right)^{1/p},

其中 $\Gamma (\mu ,\nu )$ 表示 $M\times M$ 上所有測度的集合，即 $\mu$ 與 $\nu$ 的所有耦合（英語：Coupling (probability)）組成的集合。

此外，沃瑟斯坦度量也可等效地定義為

W_{p}(\mu ,\nu )=\left(\inf \operatorname {\mathbf {E} } {\big [}d(X,Y)^{p}{\big ]}\right)^{1/p},

其中 $\mathbf {E} [Z]$ 表示隨機變量 $Z$ 的期望值，下確界則由隨機變量 $X$ 和 $Y$ 的所有聯合分佈確定，它們分別對應邊緣分佈 $\mu$ 和 $\nu$ 。

與最優運輸問題的聯繫

x軸與y軸上分別繪有兩個一維分佈 $\mu$ 和 $\nu$ ，中間是兩者一種可能的聯合分佈（不唯一），而這一聯合分佈即定義了 $\mu$ 和 $\nu$ 之間的一個運輸方案。

理解上述定義的一種方法是將其與最優運輸問題聯繫起來。對於空間 $X$ 上的某一質量分佈 $\mu (x)$ ，我們希望以某種方式運輸其質量，使其轉化同一個空間中的另一分佈 $\nu (x)$ ，即將「土堆」 $\mu$ 轉換為「土堆」 $\nu$ 。兩者的總質量必須相同，因而可以不失一般性地假設 $\mu$ 和 $\nu$ 是總質量為1的概率分佈。此外還需假設代價函數

c(x,y)\mapsto [0,\infty ),

表示從點 $x$ 運輸質量到點 $y$ 的代價。一個從 $\mu$ 到 $\nu$ 的運輸方案可以用函數 $\gamma (x,y)$ 來描述，該函數表明從 $x$ 移動到 $y$ 的質量。一個運輸方案 $\gamma (x,y)$ 必須滿足以下性質

{\begin{aligned}\int \gamma (x,y)\,\mathrm {d} y=\mu (x),\\\int \gamma (x,y)\,\mathrm {d} x=\nu (y),\end{aligned}}

前者表示從某一點 $x$ 移到其他所有點的土堆總質量必須等於最初該點 $x$ 上的土堆質量，後者則表示從所有點移到某一點 $y$ 的土堆總質量必須等於最終該點 $y$ 上的土堆質量。

這一性質相當於要求 $\gamma$ 是邊緣分佈 $\mu$ 與 $\nu$ 對應的聯合概率分佈。於是可得到運輸方案 $\gamma$ 的總代價

\iint c(x,y)\gamma (x,y)\,\mathrm {d} x\,\mathrm {d} y=\int c(x,y)\,\mathrm {d} \gamma (x,y).

方案 $\gamma$ 並不是唯一的，所有可能的運輸方案中代價最低的方案即為最優運輸方案。最優運輸方案的代價為

C=\inf _{\gamma \in \Gamma (\mu ,\nu )}\int c(x,y)\,\mathrm {d} \gamma (x,y).

如果兩點之間移動的代價等於兩點之間的距離，那麼最小代價則與 $W_{1}$ 距離等價。

參見

參考文獻

^ Vaserstein LN. Markov processes over denumerable products of spaces, describing large systems of automata (PDF). Problemy Peredači Informacii. 1969, 5 (3): 64–72.
^ Kantorovich LV. Mathematical Methods of Organizing and Planning Production. Management Science. 1939, 6 (4): 366–422. JSTOR 2627082. doi:10.1287/mnsc.6.4.366.

[1] Vaserstein LN. Markov processes over denumerable products of spaces, describing large systems of automata (PDF). Problemy Peredači Informacii. 1969, 5 (3): 64–72.

[2] Kantorovich LV. Mathematical Methods of Organizing and Planning Production. Management Science. 1939, 6 (4): 366–422. JSTOR 2627082. doi:10.1287/mnsc.6.4.366.

[1]

[2]