跳至內容

沃瑟斯坦度量

維基百科,自由的百科全書

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

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

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

定義

對於一個度量空間,假設上每個博雷爾概率測度都是拉東測度(即該度量空間為拉東空間)。對有限表示上所有有的概率測度的集合,即中存在滿足

於是,中兩個概率測度之間的沃瑟斯坦距離可定義為

其中表示上所有測度的集合,即的所有耦合英語Coupling (probability)組成的集合。

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

其中表示隨機變量期望值下確界則由隨機變量的所有聯合分布確定,它們分別對應邊緣分布

與最優運輸問題的聯繫

x軸與y軸上分別繪有兩個一維分布,中間是兩者一種可能的聯合分布(不唯一),而這一聯合分布即定義了之間的一個運輸方案。

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

表示從點運輸質量到點的代價。一個從的運輸方案可以用函數來描述,該函數表明從移動到的質量。一個運輸方案必須滿足以下性質

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

這一性質相當於要求是邊緣分布對應的聯合概率分布。於是可得到運輸方案的總代價

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

如果兩點之間移動的代價等於兩點之間的距離,那麼最小代價則與距離等價。

參考文獻

  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.