作者丨蘇劍林

單位丨廣州火焰信息科技有限公司

研究方向丨NLP，神經網絡

個人主頁丨kexue.fm

2017 年的時候筆者曾寫過互懟的藝術：從零直達WGAN-GP，從一個相對通俗的角度來介紹了 WGAN，在那篇文章中，WGAN 更像是一個天馬行空的結果，而實際上跟 Wasserstein 距離沒有多大關系。?

在本篇文章中，我們再從更數學化的視角來討論一下 WGAN。當然，本文并不是純粹地討論 GAN，而主要側重于 Wasserstein 距離及其對偶理論的理解。

▲?推土機哪家強？成本最低找Wasserstein

本文受啟發于著名的國外博文 Wasserstein GAN and the Kantorovich-Rubinstein Duality [1]，內容跟它大體上相同，但是刪除了一些冗余的部分，對不夠充分或者含糊不清的地方作了補充。不管怎樣，在此先對前輩及前輩的文章表示致敬。?

注：完整理解本文，應該需要多元微積分、概率論以及線性代數等基礎知識。還有，本文確實長，數學公式確實多，但是，真的不復雜、不難懂，大家不要看到公式就嚇怕了。

Wasserstein距離

顯然，整篇文章必然圍繞著 Wasserstein 距離（W 距離）來展開。假設我們有了兩個概率分布 p(x),q(x)，那么 Wasserstein 距離的定義為：

事實上，這也算是最優傳輸理論中最核心的定義了。?

相信我，式 (1) 沒有想象中那么難理解。我們來逐項看看。?

成本函數

首先 d(x,y) ，它不一定是距離，其準確含義應該是一個成本函數，代表著從 x 運輸到 y 的成本。常用的 d 是基于 l 范數衍生出來的，比如：

都是常見的選擇，其中：

特別指出，其實哪種距離并不是特別重要，因為很多范數都是相互等價的，范數的等價性表明其實最終定義出來的 W 距離都差不多。

成本最小化

然后來看 γ ，條件 γ∈Π[p,q] 意味著：

這也就是說， γ 是一個聯合分布，它的邊緣分布就是原來的 p 和 q。?

事實上 γ 就描述了一種運輸方案。不失一般性，設 p 是原始分布，設 q 是目標分布， p(x) 的意思是原來在位置 x 處有 p(x) 量的貨物， q(x) 是指最終 x 處要存放的貨物量，如果 p(x)>q(x) ，那么就要把 x 處的一部分貨物運到別處，反之，如果 p(x)<q(x) ，那么就要從別的地方運一些貨物到 x 處。而 γ(x,y) 的意思是指，要從 x 處搬 γ(x,y)dx 那么多的東西到 y 處。?

最后是 inf ，這表示下確界，簡單來說就是取最小，也就是說，要從所有的運輸方案中，找出總運輸成本 ?γ(x,y)d(x,y)dxdy 最小的方案，這個方案的成本，就是我們要算的 W[p,q] 。

如果將上述比喻中的“貨物”換成“沙土”，那么 Wasserstein 距離就是在求最省力的“搬土”方案了，所以 Wasserstein 距離也被稱為“推土機距離”（Earth Mover's Distance）。?

最后改編一張開頭提到的國外博文的圖片，來展示這個“推土”過程：

▲?推土機距離圖示。左邊p(x)每處的沙土被分為若干部分，然后運輸到右端q(x)的同色的位置（或者不動）

矩陣形式

逐項分析完含義之后，現在我們再來完成地重述一下問題，我們實際上在求下式的最小值：

其中 d(x,y) 是事先給定的，而這個最小值要滿足如下約束：

認真盯著式 (5)，考慮到積分只是求和的極限形式，所以我們可以把 γ(x,y) 和 d(x,y) 離散化，然后看成很長很長的（列）向量 Γ 和 D：

所以式 (5) 相當于就是將 Γ 和 D 對應位置相乘，然后求和，這不就是內積 ?Γ,D? 了嗎？

如果還沒理解這一點，那么請再好好地盯一會式 (5)，頭腦中想象著將 x,y 分區間離散化的過程，再想想積分的定義，相信這并不難理解。

如果已經理解了這一點，那就好辦了，我們可以把約束條件 (6) 也這樣看：把 p(x),q(x) 分別看成一個長向量，然后還可以拼起來，把積分也看成求和，這時候約束條件 (6) 也可以寫成矩陣形式 AΓ=b：

最后不能忘記的是 Γ ≥ 0 ，它表示 Γ 的每個分量都大于等于 0。?

線性規劃問題

現在問題可以用一行字來描述：

這就是“線性約束下的線性函數最小值”的問題，它就是我們在高中時就已經接觸過的線性規劃問題了。可見，雖然原始問題足夠復雜，又有積分又有下確界的，但經過轉寫，它本質上就是一個并不難理解的線性規劃問題（當然，“不難理解”并不意味著“容易求解”）。

線性規劃與對偶?

讓我們用更一般的記號，把線性規劃問題重寫一遍，常見的形式有兩種：

這兩種形式本質上是等價的，只不過在討論第一種的時候相對簡單一點（真的只是簡單一點點，并沒有本質差別），而從 (9) 式可以知道，我們目前只關心第一種情況。?

注意，為了避免混亂，我們必須聲明一下各個向量的大小。我們假設每個向量都是列向量，經過轉置 ? 之后就代表一個行向量，都是 n 維向量，其中 c 也就是權重，就是對 x 的各個分量加權求和；是 m 維向量，自然是一個 m×n 的矩陣了， Ax=b 實際上就是描述了 m 個等式約束。?

弱對偶形式

在規劃和優化問題中，“對偶形式”是一個非常重要的概念。一般情況下，“對偶”是指某種變換，能將原問題轉化為一個等價的、但是看起來幾乎不一樣的新問題，即：

“對偶”之所以稱為“對偶”，是因為將新問題進行同樣形式的變換后，通常來說能還原為原問題，即：

即“對偶”像是一面鏡子，原問題和新問題相當于“原像”和“鏡像”，解決了一個問題，就等價于解決了另一個問題。所以就看哪個問題更簡單了。

讀者可能還有疑問：“對偶”跟數學中諸如“逆否命題”之類的等價描述有什么區別？其實也沒有本質區別，簡單來說“對偶”和“逆否命題”都是跟原來的命題完全等價的，但是“對偶”看起來跟原命題很不一樣，而“逆否命題”僅僅是原命題的一個邏輯變換。從線性代數的角度來看，“對偶”相當于向量空間中的“原空間”和“補空間”之間的關系。

最大 vs 最小

這里我們先介紹“弱對偶形式”，其實它推導起來還是挺簡單的。

我們的目標是，設置最小值在處取到，那么我們有，我們可以在兩邊乘以一個，使得等式變成一個標量：。?

如果此時假設，那么（因為），則。也就是說，在條件下的任意總是不大于，“總是”意味著即使對于最大那個也一樣，所以我們就有：

這便稱為“弱對偶形式”，它的形式就是：“左邊的最大”還大不過“右端的最小”。

幾點評注

對于弱對偶形式，也許下面幾點值得進一步說明一下：?

1. 現在我們將原來的最小值問題變成了一個最大值問題，這便有了對偶的味道。當然，弱對偶形式之所以“弱”，是因為我們目前找到的對偶形式只是原來問題的一個下界，還沒有證明它們二者相等。?

2. 弱對偶形式在很多優化問題中（包括非線性優化）都成立。如果二者真的相等，那么就是真正意義上的對偶了，稱為強對偶形式。?

3. 理論上，我們確實需要證明式 (13) 左右兩端相等才能進一步應用它。但從應用角度，其實弱對偶形式給出的下界都已經夠用了，因為深度學習中的問題都很復雜，能有一個近似的目標去優化都已經很不錯了。?

4. 讀者可能會想問：前面我們為什么要假設而不干脆假設？假設后者當然簡單很多，但問題是后者在實踐中很難實現，所以只能假設前者。?

強對偶形式

上面已經說了，從實踐角度其實弱對偶形式已經夠用了。但是為了讓對完整理論的讀者也有更多收獲，這里繼續把“強對偶形式”也論證一番。對于只關心 WGAN 本身的讀者來說，可以考慮跳過這部分。?

所謂強對偶形式，也就是：

注意前面已經說了，弱對偶形式對于很多優化問題都成立，但強對偶形式不一定成立。而對于線性規劃來說，強對偶形式是成立的。?

Farkas引理

強對偶形式的證明，主要用到稱之為“Farkas 引理”的結論：

對于固定的矩陣和向量，下面兩個選項有且只有一個成立：

1. 存在且 x≥0，使得Ax=b；

2. 存在使得且。

什么鬼？又大又小又轉置的？能不能說人話？

其實這個引理還真有一個很直觀的幾何解釋，只不過幾何解釋翻譯成代數語言就不簡單了。幾何解釋的出發點是我們去考慮如下的向量集合：

這個集合的含義是：我們將 A 看成是 n 個 m 維列向量的組合。

那么上述集合實際上就是所有 a1,a2,…,an 的非負線性組合。那這個集合是個啥呢？答案是：一個錐，如圖所示。

▲?給定向量的非負線性組合構成這些向量圍成的一個錐

現在我們隨便給定一個向量 b，那么顯然它只有兩種可能性，而且必有一種成立：1. 在錐內（包括邊界）；2. 在錐外。這當然是廢話，但是將它翻譯成代數語言，那就不是廢話了。

▲?給定的向量在錐內，意味著可以表示為非負線性組合

▲?給定的向量在錐外，我們可以找到一個“標桿”向量與之對比

如果它在錐內，那么根據錐本身的定義，它就可以表示為 a1,a2,…,an 的非負線性組合（表示方式可能不唯一），也就是存在 x≥0，使得 Ax=b，這就是第一種情況。

如果在錐外呢？怎么表示在錐外？當然我們可以直接寫出錐內的否命題，但是那實用價值不大。如果向量 b 在錐外，那么我們總是可以找到一個“標桿”向量 y，它與 a1,a2,…,an 的夾角都大于等于 90 度，向量表示法就是內積都小于等于零，即，或者寫成一個整體。

找到這個“標桿”后，向量 b 與“標桿”的夾角必然是要小于 90 度的，即。這樣一個大于等于 90 度，一個小于 90 度，保證了向量 b 在全體向量構成的錐外。這就是第二種情況。

當然，這不能算是完備的證明，只能算是一個啟發式引導，完備的證明還要仔細論證為什么這些向量的非負線性組合構成了一個錐。這些就不在本文的范疇了。Farkas 引理的特點是二選一，比如我要證明滿足第二點，只需要證明它不滿足第一點，反之亦然。這是對問題的一個轉化。

從引理到強對偶

有了 Farkas 引理，我們就可以證明強對偶形式了。證明的思路是：證明 max 可以任意程度地接近 min 。?

證明還是先假設 min 的最小值在處取到，即最小值為，那么我們考慮：

當 ?>0 時，那么對于任意 x≥0，都不可能等于，這是因為已經是最小值，所以是能達到的最大值，它不可能等于更大的。

前面已經說了，不滿足第一種情況，那就只能滿足第二種情況了，即存在使得且，這等價于：

下面我們表明 α 必須大于 0，這是因為，所以我們再去考慮 ?=0。而當 ?=0 時有，即滿足 Farkas 引理的第一種情況，那就不滿足第二種情況，而不滿足第二種情況，意味著，都有，剛剛我們已經證明了，所以必須有 α>0。

現在確定 α>0 了，我們就可以從式 (18) 得到：

這意味著：

而弱對偶形式已經告訴我們：

也就是被夾在和之間，而因為 ? > 0 是任意的，所以兩者可以無限接近，從而：

這便是要證的強對偶形式。?

簡單說明

Farkas 引理和強對偶形式的證明，看上去比較迂回，但實際上是優化理論中非常經典和重要的證明案例，對于初學者來說，它應該是一次非常強烈的思維沖擊。因為我們以往的認識中，我們對原命題做變換，僅僅是局限于“邏輯變換”，如否命題、逆否命題等。而對偶形式和 Farkas 引理卻出現了一些“看起來很不一樣，卻又偏偏等價”的結論。

Farkas 引理和強對偶形式也可以進一步推廣到一般的凸集優化問題，證明手段相似，只不過在對區域和不等關系的討論上，比上面的線性規劃的過程更為細致和復雜。不過我也不是專門搞這些優化問題的，所以只有一個模糊的認識，就不再繼續班門弄斧了。

Wasserstein GAN

好了，進行了一大通的準備工作后，我們終于可以導出 Wasserstein GAN 了，就本文來看，它只不過是線性規劃的對偶形式的一個副產品罷了。?

W距離的對偶

在推導之前，我們還是再來捋一捋本文的思路：本文先給出了 W 距離的定義 (1) ，然后經過分析，發現它其實就是普通線性規劃問題的一個連續版本，轉化過程為 (7) , (8) 和 (9) ；因此中間我們花了相當一部分篇幅去學習線性規劃及其對偶形式，最終得到了結論 (14) 。?

現在我們要做的事情，就是把整個過程“逆”過來，也就是將找出 (14) 對應的連續版本，為 W 距離找一個對偶表達式。 其實這個過程也不復雜，由結論 (14) 和式 (9) ，我們得到：

注意式 (8) 中 b 是由兩部分拼起來的，所以我們也可以把 F 類似地寫成：

現在 ?b,F? 可以寫成：

或者對應的積分形式是：

別忘了約束條件：

代入計算后，可以發現這個諾大的矩陣運算實際上就說了這樣的一件事情：

或者直接寫成：

從對偶到WGAN

終于，我們就要接近尾聲了，現在我們得到了 W 距離 (1) 的一個對偶形式了：

注意到由 f(x)+g(y)≤d(x,y) 我們得到：

即 g(x)≤?f(x)，所以我們有：

即如果 g=?f，它的最大值不會小于原來的最大值，所以我們可以放心地讓 g=?f，從而：

這便是我們最終要尋找的 W 距離 (1) 的對偶形式了，其中約束條件我們可以寫為 ||f||L≤1，稱為 Lipschitz 約束。

由于 p,q 都是概率分布，因此我們可以寫成采樣形式：

這就是 WGAN 的判別器所采用的 loss 了，自然地，整個 WGAN 的訓練過程就是：

千呼萬喚的 WGAN 終于現身，剩下的就是怎么加 Lipschitz 約束的問題了，可以參考：深度學習中的Lipschitz約束：泛化與生成模型。

文章小結

本文主要介紹了 Wasserstein 距離，然后轉化為一個線性規劃問題，繼而介紹了線性規劃的對偶理論，最終導出了 Wasserstein 距離的對偶形式，它可以用作訓練生成模型，即 WGAN 及后面一系列推廣。

本文是筆者對線性規劃及其對偶理論的一次簡單學習總結，對熟悉線性代數后希望從理論上了解 WGAN 的讀者應該會有一定的參考價值。如果對文中內容有什么疑惑或批評，歡迎留言指出。

點擊以下標題查看作者其他文章：?

• 變分自編碼器VAE：原來是這么一回事 | 附開源代碼

• 再談變分自編碼器VAE：從貝葉斯觀點出發

• 變分自編碼器VAE：這樣做為什么能成？

• 從變分編碼、信息瓶頸到正態分布：論遺忘的重要性
  

• 深度學習中的互信息：無監督提取特征

• 全新視角：用變分推斷統一理解生成模型

• 細水長flow之NICE：流模型的基本概念與實現

• 細水長flow之f-VAEs：Glow與VAEs的聯姻

• 深度學習中的Lipschitz約束：泛化與生成模型
  

#投 稿 通 道#

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

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

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

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

??來稿標準：

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

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

? PaperWeekly 默認每篇文章都是首發，均會添加“原創”標志

? 投稿郵箱：

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

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

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

?

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

進入知乎首頁搜索「PaperWeekly」

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

關于PaperWeekly

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

▽ 點擊 |?閱讀原文?| 查看作者博客

總結

以上是生活随笔為你收集整理的从Wasserstein距离、对偶理论到WGAN的全部內容，希望文章能夠幫你解決所遇到的問題。

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