wasserstein 距離的問題?

01-21

背景:
最近被老大(實習公司)要求看一點關於多標籤學習的文章, 然後就甩給我了這篇NIPS: Learning with a Wasserstein Loss (https://papers.nips.cc/paper/5679-learning-with-a-wasserstein-loss.pdf)
這篇文章在NIPS 2015有什麼值得關注的亮點？ - 知乎用戶的回答也有人提到, 想必是很不錯的工作.
文中的wasserstein distance 我怎麼也看不懂, wiki (Wasserstein metric)上的解釋也看不明白.
以下是wiki頁面中關於wasserstein distance的部分內容:

Let (M, d) be a metric space for which every probability measure on M is a Radon measure (a so-called Radon space). For p ≥ 1, let Pp(M) denote the collection of all probability measures μ on M with finite pth moment: for some x0 in M,
Then the pth Wasserstein distance between two probability measures μ and ν in Pp(M) is defined as
where Γ(μ, ν) denotes the collection of all measures on M × M with marginals μ and ν on the first and second factors respectively. (The set Γ(μ, ν) is also called the set of all couplings of μ and ν.)
The above distance is usually denoted Wp(μ, ν) (typically among authors who prefer the "Wasserstein" spelling) or ?p(μ, ν) (typically among authors who prefer the "Vasershtein" spelling). The remainder of this article will use the Wpnotation.
問題1:
第一個式子中d(x,x0)表示M域中兩個元素x與x0之間的距離, u(x)又是什麼? wiki中說"collection of all probability measures μ on M", 那麼這個"probability measure "u(x) 和 d(x,x0)什麼區別呢?
問題2:
第二段中"distance between two probability measures μ and ν"是什麼含義? 我的理解是wasserstein distance是描述兩個probabilitydistribution之間距離的, 那為什麼說是distance between two probability measure? 我好像對probability measure 不是很理解.

問題3:
其實我是沒怎麼弄明白wasserstein distance到底是怎麼算的....所以能幫我解釋一下最好了.
謝謝!

同意 @Zheng Jiansen 所說，學好實變和測度論對機器學習是很有幫助的。對於暫時沒有這些數學背景的同學，可以安全的把概率測度(probability measure)理解為概率分布(probability distribution)，只要我們關心的空間是 $mathbb R^n$ 。兩個概率分布之間的距離有很多種描述方式，一個比較膾炙人口的是KL divergence: $KL(p||q) = int_{mathbb R^n}p(x)logfrac{p(x)}{q(x)}dx$ ，儘管它嚴格意義上不是一個距離(比如不滿足對稱性)。從定義可以看出，KL並不關心 $mathbb R^n$ 的幾何性質，因為p和q的比較都是在同一點進行的(換句話說，只要 $x_1 eq x_2$ ，KL並不care $p(x_1)/q(x_2)$ 的大小)。舉個例子，考慮如下兩個一維高斯分布：p= $mathcal N(0, epsilon^3)$ 和q= $mathcal N(epsilon, epsilon^3)$ ，借蠻力可算出 $KL(p||q) = frac{1}{2epsilon}$ 。q只是p的一個微小平移，但當平移量趨於0時，KL卻blow up了！

這就激勵我們定義一種分布間的距離，使其能夠把 $mathbb R^n$ 的幾何/度量性質也考慮進去。Wasserstein distance就做到了這一點，而且是高調的做到了這一點，因為 $d(x,y)$ 顯式的出現在了定義中。具體的，對於定義在 $mathbb R^n$ 上的概率分布 $mu$ 和 $u$ ，

$W_p(mu, u) := inf_{gamma in Gamma(mu, u)}left(int_{mathbb R^n imes mathbb R^n} d(x, y)^p dgamma (x, y) ight)^{1/p} = left(inf_xi mathbf E[d(x,y)^p] ight)^{1/p}$ ，

其中 $xi$ 是一個 $mathbb R^n imes mathbb R^n$ 上的聯合分布，必須同時滿足 $mu$ 和 $u$ 是其邊緣分布。 $d$ 可以是 $mathbb R^n$ 上的任意距離，比如歐式距離， $L_1$ 距離等等。舉個特例，當 $mu = delta_x$ 和 $u = delta_y$ 時，唯一符合條件的 $xi$ 只有 $delta_{(x, y)}$ ，所以 $W_p(mu, u) = d(x,y)$ ，兩個delta分布間的距離正好等於它們中心間的距離，非常的符號直覺對不對！(因為建立了 $mathbb R^n$ 和delta分布之間的isometry)

剛才的例子也告訴我們，Wasserstein distance是可以定義兩個support不重合，甚至一點交集都沒有的分布之間的距離的，而KL在這種情況並不適用。

維基中也給出了兩個正態分布的Wasserstein distance (p=2時候) 的公式，大家可以去看一下，正好是兩部分的和，一部分代表了中心間的幾何距離，另一部分代表了兩個分布形狀上的差異。現在返回去看上面KL時候舉的那個例子，它們之間的Wasserstein distance正好是 $epsilon$ 。

實際應用中Wasserstein distance的計算大都依賴離散化，因為目前只對有限的幾個分布存在解析解。對於任意分布 $mu$ 我們可以用delta分布來逼近 $mu approx frac{1}{n}sum_{i=1}^ndelta_{x_i}$ ，這裡並不要求 $x_i$ 是唯一的。對於 $u$ 做同樣的近似 $u approx frac{1}{n}sum_{i=1}^n delta_{y_i}$ 。為什麼 $mu$ 和 $u$ 的近似能夠取相同的n？因為總是可以把當前的近似點拷貝幾份然後renormalize，所以取n為兩者原始近似點數量的最小公倍數即可。那麼

$W_p(mu, u) approx W_pleft(frac{1}{n}sum_{i=1}^ndelta_{x_i}, frac{1}{n}sum_{i=1}^ndelta_{y_i} ight) = min_{sigmain S_n}left(sum_{i=1}^nd(x_{sigma_i}, y_i)^p ight)^{1/p}$ ，

這就變成了一個組合優化的問題：有n個位於 $x_i$ 的石子，大自然藉助水的力量將它們衝到的新的位置 $y_i$ 。就像光總是走最短路一樣，大自然總是選取最短的路徑來移動這些石子。這些石子總共移動的距離因此得名Wasserstein distance。

最後這段純屬娛樂。。。

PS: 證明Wasserstein distance為什麼定義了一個距離是一個很好的練習。尤其在證明三角不等式的時候，可以意識到它就是在映射 $mathbb R^n$ 中的 $L_p$ 距離。

你可以看這篇文章Wasserstein GAN and the Kantorovich-Rubinstein Duality。

另外，沒必要將按照前面回答，將實變，測度論這些學了才動手研究。實變領域的數學，大部分能用得上的定理，基本你都能靠感覺都猜出個大概。。。數學觀念的具現能力才是應該多多培養的。。。

為什麼Wasserstein distance被叫做transport distance，從那個基於coupling的定義看起來其實是不那麼顯然的，我們還是要看一看optimal transport的歷史。

optimal transport說起來很簡單，有一堆土和一個坑，怎麼把土填到坑裡面做的功最少。所以這個問題最早是這麼給的，叫做Monge problem

$inf_T {int c(x, T(x)) mathrm{d} mu_0(x) ,|, T_{#}mu_0 = mu_1}$

那個#是pushforward measure，c是cost function. Monge problem應該在18世紀就有了，是一個非常直觀的優化問題，如果已知cost function是c，怎麼把一堆形狀為 $mu_0$ 的土填到形狀為 $mu_1$ 的坑裡面的花費最小，這個最低成本的運輸方式就是函數T，換句話說就是把土從x運到T(x)。但是Monge problem本身是有一些難以克服的問題的，如果這兩個測度相互之間不是絕對連續的話，這個T的存在性都有問題。（想一下如果 $mu_0$ 是點測度， $mu_1$ 是個正態分布）

正因為這樣，才有了基於coupling的optimal transport的定義，也就是我們從維基百科上看到的那個，這個叫做Kantorovich problem。如果直觀地去理解Kantorovich problem的話，一個coupling，也就是一個乘積空間 $mathbb{R}^d imes mathbb{R}^d$ 上的測度 $gamma$ ，對應的是一個optimal transport plan。什麼意思呢，假設 $gamma$ 有一個密度函數p(x,y)，那麼p(x,y)的意思就是把x上面的土運到 $mathbb{R}^d$ 上形成一個分布（注意不再是把土給運到一點T(x)），這個分布是p(x,y)（x是一個已經給定的點）。反過來，如果最低成本的運輸方式對應的是函數T的話，那麼Monge問題的解對應的是限制在圖像(x, T(x))上面的coupling，這個叫做deterministic coupling。

換句話說，Kantorovich問題是Monge問題的一個relaxation。如果 $mu_0$ 和 $mu_1$ 滿足一定的條件（比如如果這兩個測度都和Lebesgue測度絕對連續，具體的條件比這個略微寬鬆一點。），那麼我們知道Kantorovich問題的解一定是一個deterministic coupling，也就是這兩個問題在這種情況下等價。

optimal transport給出的距離叫做Wasserstein distance，最早這是一個有很強應用背景的最優化問題，但是後面我們知道Wasserstein distance，特別是2-Wasserstein distance，有著極為深刻的幾何背景。比如說如果X是一個黎曼流形， P(X)是X上面的概率測度構成的空間。假設P(X)上面的距離是Wasserstein distance，那麼相對熵在P(X)上面具有凸性和X具有非負Ricci曲率是等價的。

很久很久不碰這些東西，很多結果具體的條件已經記不得了。這方面的比較好的參考書應該就是Villani的optimal transport, old and new。

問題1：u(x)是M上的概率測度（即若事件a屬於M，則p(a)表示事件a的概率大小），你就想像為評價事件大小的標準，類比黎曼積分dx中的x為評價x軸上小線段的長度的標準。所以按照相同的過程可以定義以u(x)為度量標準的積分定義，只不過把x軸換成了M。

問題2：這裡的u和v為兩個概率測度，這裡只不過是聯合分布的積分罷了，你就類比dxdy上的積分。

問題3:wassertain distance計算就直接在所有的邊緣分布為u和v的聯合分布上，將那個式子積分（回憶一下二維正態分布，相同的邊緣分布有無窮多種聯合分布，其中聯合分布由x與y的相關係數決定）再在求其中最小的(嚴格來說是下確界），再開方就是了。

裡面在分布上的積分可以聯想期望的定義，有興趣可以看看羅貝格積分，希望這些可以幫到你，我比較菜，有錯的話多交流哈=。=

盡量不用測度論來粗鄙的回答。

有兩個隨機事件A,B（隨機變數/過程/etc.），比如扔兩個骰子得到的兩個數字。

你可以對這兩個事件之間的關係有很多假設，比如獨立的扔兩個骰子；或者骰子1扔完後，骰子2一定和骰子1相差某個數；或者骰子1和骰子2的奇偶性一定要相同，etc。

所以讓這兩個事件發生的概率空間（它倆的關係你隨便定，但是如果你單看骰子1或2的數字，它還是和隨機的扔一個骰子是一樣的分布）有很多種。

在不同的概率空間（你假定的關係，或者叫coupling）里，這兩個隨機變數的差的期望是不一樣的。

（也就是E|A-B|）

wasserstein distance就是在所有可能的概率空間里，最小的那個差的期望。也就是找到一個空間（A和B都可以發生，且之間有某種關係，只看A或者只看B還是原來的分布），讓它倆之間的差距最小。

=====

學渣的理解大概就是這樣了。

不知樓主是否查閱到了wasserstein distance(WD)提出的背景: 把一堆沙子從原材料供應地運送到建築工地的最優化問題。第一個問題: d相當於運送單位沙子單位距離的成本，而miu(x)-題主說的u(x)是運送路徑，M是所有可能的運送方式集合。WD定義為了所有運送方式中最優化的方式。第三個問題不是一個帖子能回答的，多查查吧。

建議先學好實變分析與測度論, 機器學習需要的數學並非只是線性代數:)

我也是醉了。題主這是基本的概率論沒有過關，和實分析測度論毫無關係，這麼多答主忙著聯繫實分析，但卻回答了一堆和實分析毫無關係的內容。你以為把概率分布換個名字叫概率測度就要讓那些非數學系的學個實分析再回來看？有時這是毫無必要的。

數學學了不是這樣用的。機器學習里真要用到什麼避不過去的實分析測度論的概念，也未必會是在數學系課本里出現過的內容。