# Wasserstein GAN and the Kantorovich-Rubinstein Duality(翻譯)
###### tags: `翻譯` `WGAN` `GAN` `Earth Mover Distance` `Wasserstein GAN` `Kantorovich-Rubinstein Duality`

[文章來源_Source](https://vincentherrmann.github.io/blog/wasserstein/)
作者_Author: Vincent Herrmann

---

據我所知，人們對最近的[Wasserstein GAN paper](https://arxiv.org/abs/1701.07875)非常感興趣。這篇文章中，我不打算重覆WGANS的理由、機制與好處，這你應該閱讀原始論文或這個[出色的總結](https://www.alexirpan.com/2017/02/22/wasserstein-gan.html)。相反的，我們將聚焦在一個主要的細節，只是快速的提到，但我認為，某種意義上就是它的核心，Kantorovich-Rubinstein duality(二元性)，或者更確切的說是它的特殊情況。這當然不是一個新的結果，但應用程式非常聰明並且有吸引力。

論文引用Fields-Medal得主french eccentric Cedric Villani的"Optimal Transport - Old and New"乙書，你可以在他的網頁下載這本書_{(連結已失效，因此未附上)}。那大約一千多頁，是針對數學博士與研究人員的-玩開心點!Villani也在[講座大約28分鐘處](https://www.youtube.com/watch?v=zo46TEp6FB8)以淺顯易懂的方式討論這個主題。一般來說，我發現很難找到元素來給出真正的解釋，但並不是給一堆的定義跟引用我不知道的定理。也許這篇文章可以幫忙填補一點點這個缺口。我們將單純的使用基礎線性代數(basic linear algebra)、機率理論與最佳化。這些不會是枯燥的證明，而且我們會豐富地說明許多規律性條件。但我試著讓推理鏈盡可能的清楚、完整，因此應該對這主題可以得到足夠的直覺想法。

我們關於Kantorovich-Rubinstein duality的論點實際上並不複雜，而且代表它本身。然而，這非常抽像，這也是為什麼我要把它放到最後，並且從線性規劃中好的離散情況與一些相關問題開始。

如果你有興趣，你可以看一下我建立的[Jupyter Notebook](https://github.com/vincentherrmann/wasserstein-notebook/blob/master/Wasserstein_Kantorovich.ipynb)，那邊繪製這篇文章中的一些圖形。
## Earth Mover’s Distance
對於離散機率分佈(discrete probability distributions)，Wasserstein distance也被稱為Earth Mover's Distance(EMD)。如果我們將分佈想像為不同數量的土方堆，那麼EMD就是最小化將從土方堆從一邊移至另一邊的工作量。工作被定義為土方堆裡的數量乘上它被移動的距離。我們定義我們的離散分佈$P_r$與$P_\theta$，每個分佈都各別具有$l$可能狀態$x$或$y$，以兩個任意分佈為例。

_{Fig.1: 機率分佈$P_r$與$P_\theta$，各自帶有十個狀態}

計算EMD本身就是一個最佳化的問題：有無限種可能方法可以移動土方堆，我們需要找到最好的那一個。我們將試著找出的運輸計算定義為$\gamma(x,y)$。這簡單的說明我們如何從$y$上的$x$分配土方堆，反之亦然(簡單說，即將$x$的分佈移至$y$)。

要成為有效的運輸計劃，約束式$\sum_x\gamma(x,y)=P_r(y)$與$\sum_y\gamma(x,y)=P_\theta(x)$當然必需適用。這確保依循這個運輸計劃生成正確的分佈。相同的，我們可以定義$\gamma$為聯合機率分佈，而且必需符合$\gamma \in \prod(P_r,P_\theta)$，而$\gamma \in \prod(P_r,P_\theta)$為所有分佈的集合，其邊界分別為$P_r$或$P_\theta$。為了得到EMD，我們必須將每一個$\gamma$的值乘上$x$、$y$的Euclidian distance(歐幾里德距離)。因此Earth mover’s distance的定義是：
$$\mathrm{EMD}(P_r, P_\theta) = \inf_{\gamma \in \Pi} \, \sum\limits_{x,y} \Vert x - y \Vert \gamma (x,y) = \inf_{\gamma \in \Pi} \ \mathbb{E}_{(x,y) \sim \gamma} \Vert x - y \Vert$$

如果你對表達式的$inf$不熟，它代表最大下界([infimum](http://terms.naer.edu.tw/detail/2117023/))或是最大下限(greatest lower bound)。它只是最小值的一個微小的數學變化。它的相反是$sup$，或最低上限([supremum](http://terms.naer.edu.tw/detail/2427020/))，大概就是最大化，我們稍後會碰到。我們也可以定義$\mathbf{\Gamma} = \gamma(x,y)$與$\mathbf{D} = \Vert x - y \Vert$，其中$\mathbf{\Gamma}, \mathbf{D} \in \mathbb{R}^{l \times l}$。現在我們可以寫成這樣：
$$\mathrm{EMD}(P_r, P_\theta) = \inf_{\gamma \in \Pi} \, \langle \mathbf{D}, \mathbf{\Gamma} \rangle_\mathrm{F}$$

其中$\langle , \rangle_\mathrm{F}$為Frobenius內積(元素乘積的總合)

_{Fig.2: 運輸計劃$\mathbf{\Gamma}，以$P_r, P_\theta$做為邊際機率與距離\mathbf{D}$}
## Linear Programming
從上面的圖你可以看到最佳運算計算$\mathbf{\Gamma}$。它可以使用線性規劃的通用方法計算(LP)。通過LP，我們可以解決某種規範形式的問題：尋找一個向量$\mathbf{x} \in \mathbb{R}^n$，可以最小化成本(cost)$z = \mathbf{c}^T \mathbf{x}, \ \mathbf{c} \in \mathbb{R}^n$。此外，$\mathbf{x}$受限於方程式$\mathbf{A} \mathbf{x} = \mathbf{b}, \ \mathbf{A} \in \mathbb{R}^{m \times n}, \mathbf{b} \in \mathbb{R}^m$與$\mathbf{x} \geq \mathbf{0}$。

為了將尋找EMD的問題轉換為這個形式，我們要平展$\mathbf{\Gamma}$與$\mathbf{D}$：
$$% <![CDATA[
\begin{align}
\mathbf{x} &= \mathrm{vec}(\mathbf{\Gamma}) \\
\mathbf{c} &= \mathrm{vec}(\mathbf{D}) \\
\end{align} %]]>$$

這意味著$n=l^2$。對於這個約束式，我們堆疊目標分佈，這使得$m=2l$：
$$\mathbf{b} = \begin{bmatrix} P_r \\ P_\theta\end{bmatrix}$$

對於$\mathbf{A}$，我們需要建構一個大型稀疏[二進制矩陣](http://terms.naer.edu.tw/detail/2341813/?index=1)，從$\mathbf{x}$中取值加總得到$\mathbf{b}$。下面示意圖應該很清楚：

這樣，我們就可以調用一個標準線性[常程式](http://terms.naer.edu.tw/detail/2123959/)(standard LP routine)，以scipy `linprog()`為例：

import numpy as np
from scipy.optimize import linprog

# We construct our A matrix by creating two 3-way tensors,
# and then reshaping and concatenating them
A_r = np.zeros((l, l, l))
A_t = np.zeros((l, l, l))

for i in range(l):
	for j in range(l):
		A_r[i, i, j] = 1
		A_t[i, j, i] = 1

A = np.concatenate((A_r.reshape((l, l**2)), A_t.reshape((l, l**2))), axis=0)
b = np.concatenate((P_r, P_t), axis=0)
c = D.reshape((l**2))

opt_res = linprog(c, A_eq=A, b_eq=b)
emd = opt_res.fun
gamma = opt_res.x.reshape((l, l))

現在我們有運輸計劃與EMD。
_{Fig.3: $\mathbb{P}_r$與$\mathbb{P}_\theta$之間的最佳運輸}

## Dual Form
很不幸的，這樣的最佳化在許多情況下並不實用，當然也不用於GAN的領域。在我們的範例，我們使用具有十個可能狀態的一維隨機變數。可能的離散狀態會隨著輸入變數的維度而呈指數級縮放。對許多應用而言，像是影像，輸入的維度輕輕鬆鬆就可以上千維。即使是$\gamma$的近似值也是幾乎不可能。

但實際上我們並不在意$\gamma$，我們只需要一個數字，就是EMD。此外，我們希望用它(EMD)來訓練Generator，用來生成分佈-$P_\theta$。要做這點，我們必須可能計算$\nabla_{P_\theta} \mathrm{EMD}(P_r, P_\theta)$的梯度。由於$\mathbb{P}_r$與$\mathbb{P}_\theta$只是我們的最佳化的約束式，因此這不可能以任何直接的方式實現。

事實證明，有另一種更方便的方法可以計算EMD。任何的LP(Linear Programming)都有兩種方式可以表達問題：我們剛才用的原始型(primal form)與[對偶型](http://terms.naer.edu.tw/detail/3468660/)(dual form)

$$\begin{array}{c|c}
\mathbf{primal \ form:} & \mathbf{dual \ form:}\\
\begin{array}{rrcl}
\mathrm{minimize} \ & z & = & \ \mathbf{c}^T \mathbf{x}, \\
\mathrm{so \ that} \ & \mathbf{A} \mathbf{x} & = & \ \mathbf{b} \\
\mathrm{and}\ & \mathbf{x} & \geq &\ \mathbf{0}
\end{array} &
\begin{array}{rrcl}
\mathrm{maximize} \ & \tilde{z} & = & \ \mathbf{b}^T \mathbf{y}, \\
\mathrm{so \ that} \ & \mathbf{A}^T \mathbf{y} & \leq & \ \mathbf{c} \\ \\
\end{array}
\end{array}$$

通過改變相同值之間的關係，我們可以將最小化問題轉換為最大化問題。這裡的目標$\widetilde{z}$直接依賴於$\mathbf{b}$，其中包含我們的分佈$\mathbb{P}_r$與$\mathbb{P}_\theta$。這正是我們要的。很簡單的看的出來，$\widetilde{z}$是$z$的lower bound：

$$z = \mathbf{c}^T \mathbf{x} \geq \mathbf{y}^T \mathbf{A} \mathbf{x} = \mathbf{y}^T \mathbf{b} = \tilde{z}$$

這稱為[弱對偶定理](http://terms.naer.edu.tw/detail/2127420/)(Weak Duality theorem)。如你所猜想的那樣，還存在著[強對偶定理](http://terms.naer.edu.tw/detail/2125511/)(strong duality theorem)，這定理指出，如果我們到最$\widetilde{z}$的最佳解，那麼$z=\widetilde{z}$。證明它有點麻煩，而且需要Farkas定理做為中間結果。

## Farkas Theorem
我們可以將矩陣$\hat{\mathbf{A}} \in \mathbb{R}^{d \times n}$視為向量$\mathbf{a}_{1}, \mathbf{a}_{2}, …, \mathbf{a}_{n}\in \mathbb{R}^{d}$。這些帶有非負系數向量的所有可能的線性組合的集合是[凸錐](http://terms.naer.edu.tw/detail/2113744/)(convex cone)的，而它的頂點位於原點(注意，[凸錐](http://terms.naer.edu.tw/detail/2113744/)(convex cone)也可能覆蓋整個$\mathbb{R}^d$空間)。我們可以在向量$\mathbf{x} \in \mathbb{R}^{n}_{\geq 0}$結合這些系數。

對於向量$\hat{\mathbf{b}} \in \mathbb{R}^{d}$，現在有兩種可能性：不論$\hat{\mathbb{b}}$是否包含在[錐面](http://terms.naer.edu.tw/detail/2113250/)之中。如果$\hat{\mathbb{b}}$並不包含在裡面，那我們可以擬合一個穿越介於[凸錐](http://terms.naer.edu.tw/detail/2113744/)(convex cone)與$\hat{\mathbb{b}}$之間的原點的超平面-$h$。我們可以單純依據它的[法向量](http://terms.naer.edu.tw/detail/2120686/)(normal vector)$\hat{\mathbf{y}} \in \mathbb{R}^{d}$來定義它。如果向量$\mathbf{v} \in \mathbb{R}^{d}$位於$h$，那麼$\mathbf{v}^T \hat{\mathbf{y}} = 0$，如果$\mathbf{v}$位在$h$的上[半空間](http://terms.naer.edu.tw/detail/2117102/)(half-space)(與$\hat{y}$相同邊)，那麼$\mathbf{v}^T \hat{\mathbf{y}} > 0$，並且如果$\mathbf{v}$位在下[半空間](http://terms.naer.edu.tw/detail/2117102/)(half-space)($\hat{y}$的對立邊)，那麼$\mathbf{v}^T \hat{\mathbf{y}} < 0$。正如我們所指出，如果$h$存在，那$\hat{\mathbf{b}}$位於一個不同于所有向量$\mathbf{a}_i$的[半空間](http://terms.naer.edu.tw/detail/2117102/)(half-space)。

_{Fig.4: Farkas theorem的幾何視圖：如果$\mathbf{b}$}不位於藍色錐面內或上，那我們可以擬合一個介於$\mathbf{b}$與錐面之間的超平面$h$

總結而言，下面其中一個論述是正確的：
* (1) 存在$\mathbf{x} \in \mathbb{R}^{n}$，因此$\hat{\mathbf{A}} \mathbf{x} = \hat{\mathbf{b}}$與$\mathbf{x} \geq \mathbf{0}$
* (2) 存在$\hat{\mathbf{y}} \in \mathbb{R}^{d}$，因此$\hat{\mathbf{A}}^T \hat{\mathbf{y}} \leq \mathbf{0}$與$\hat{\mathbf{b}}^T \hat{\mathbf{y}} > 0$

這稱為Farkas theorem，或Farkas alternatives。那存在一點點的版本與證明上的差異，但我們說明的足夠我們用了。
## Strong Duality
這個證明的第二部份的技巧是構造一個與我們原始LP形式有關的問題，但是有一個額外的維度，而且這樣的方式剛好位於[凸錐](http://terms.naer.edu.tw/detail/2353213/)的邊緣。然後根據Farkas的說明，對某些人來說，相對應的超平面任意接近。於此，結合[弱對偶定理](http://terms.naer.edu.tw/detail/2127420/)，我們將證明[強對偶](http://terms.naer.edu.tw/detail/2125511/)。

假設，原始問題的[極小解](http://terms.naer.edu.tw/detail/2119756/)為$z^*=c^Tx^*$，然後我們定義：
$$\hat{\mathbf{A}} = \begin{bmatrix} \mathbf{A} \\ -\mathbf{c}^T \end{bmatrix}, \ \ \
\hat{\mathbf{b}}_\epsilon = \begin{bmatrix} \mathbf{b} \\ -z^* + \epsilon \end{bmatrix}, \ \ \
\hat{\mathbf{y}} = \begin{bmatrix} \mathbf{y} \\ \alpha \end{bmatrix}$$

與$\epsilon, \alpha \in \mathbb{R}$。當$\epsilon=0$，我們有Farkas case(1)，因為$\hat{\mathbf{A}} \mathbf{x}^* = \hat{\mathbf{b}}_0$。當$\epsilon>0$，不存在非負值解(因為$z^*$已經是最小值)，而且我們有Farkas case(2)。這意味著存在$\mathbf{y}$與$\alpha$，這樣

$$\begin{bmatrix} \mathbf{A} \\ -\mathbf{c}^T \end{bmatrix}^T
\begin{bmatrix} \mathbf{y} \\ \alpha \end{bmatrix} \leq \mathbf{0}, \ \ \ \
\begin{bmatrix} \mathbf{b} \\ -z^* + \epsilon \end{bmatrix}
\begin{bmatrix} \mathbf{y} \\ \alpha \end{bmatrix} > 0$$

或者相當於

$$\mathbf{A}^T \mathbf{y} \leq \alpha \mathbf{c}, \ \ \mathbf{b}^T \mathbf{y} > \alpha(z^* - \epsilon).$$

根據我們建構它的方式，我們可以發現$\hat{\mathbf{y}}$，因此$\hat{\mathbf{b}}_0 \hat{\mathbf{y}} = 0$。然後改變$\epsilon$為大於0的任何數值都將造成$\hat{\mathbf{b}}_0 \hat{\mathbf{y}} > 0$。在我們的問題裡面，只有當$\alpha > 0$的時候才會造成這個問題，因為$z^* > 0$。我們說明$\hat{\mathbf{y}}$只是超平面上的一個[法向量](http://terms.naer.edu.tw/detail/2120686/)，因此我們可以將它自由縮放至大於零的任意大小。特別是，我們可以縮放它讓$\alpha = 1$。這意味著存在向量$\hat{\mathbf{y}}$，因此

$$\mathbf{A}^T \mathbf{y} \leq \mathbf{c}, \ \ \mathbf{b}^T \mathbf{y} > z^* - \epsilon.$$

我們看到，$\tilde{z} := z^* - \epsilon$對於任何$\epsilon > 0$都是我們對偶問題的目標可行值。根據[弱對偶定理](http://terms.naer.edu.tw/detail/2127420/)，我們知道$\tilde{z} \leq z^{* }$。我們只是說明$\tilde{z}$可以任意地接近$z^*$。這意味著我們對偶形的最佳(最大值)值也是$z^*$。

## Dual Implementation
現在我們可以很有信心的使用[對偶形](http://terms.naer.edu.tw/detail/4689910/)來計算EMD。如我們所說明，最大值$\tilde{z}^* = \mathbf{b}^T \mathbf{y}^{*}$就是EMD。讓我們來定義

$$\mathbf{y}^* = \begin{bmatrix} \mathbf{f} \\ \mathbf{g} \end{bmatrix}$$

其中$\mathbf{f}, \mathbf{g} \in \mathbb{R}^d$。這意味著$\mathrm{EMD}(P_r, P_\theta) = \mathbf{f}^T P_r + \mathbf{g}^T P_\theta$。回想一下[對偶形](http://terms.naer.edu.tw/detail/4689910/)的約束式：$\mathbf{A}^T \mathbf{y} \leq \mathbf{c}$


我們將向量$\mathbf{f}$與$\mathbf{g}$寫為函數$f$與$g$的值。約束式可以總結為$f(x_i) + g(x_j) \leq \mathbf{D}_{i,j}$。$i=j$的情況會對所有的$i$產生$g(x_i) \leq -f(x_i)$，因為$\mathbf{D}_{i,i} = 0$。由於$P_r$與$P_\theta$是非負數，為了最大化我們的目標，$\sum_i \mathbf{f}_i + \mathbf{g}_i$要盡可能的愈大愈好。這個和的最大值是零，這是我們用$g=-f$得到的。考慮所有其它的約束式，這仍然是正確的：選擇$g(x_{i}) < - f(x_{i})$只有在當$j \neq i$而$f(x_j)$與$g(x_j)$的值是有利益的時候才有意義。由於$f(x_j)$與$g(x_j)$仍然受其它約束式的[上界限制](http://terms.naer.edu.tw/detail/958937/)(upper-bounded)，情況並非如此。

_{Fig.5：對偶解的約束式。藍線與紅線分別表示$f$與$g$的上界(upper bound)。對每一個$f \neq -g$，其最佳化函式都有淨損失。}

當$g=-f$，約束式變為$f(x_i) - f(x_j) \leq \mathbf{D}_{i,j}$與$f(x_i) - f(x_j) \geq -\mathbf{D}_{i,j}$。如果我們看值$f(x_i)$與線段相連，這意味著，這些線段的向上、向下斜率是有限的。在我們的案例中，我們使用Euclidian distances(歐幾里德距離)，這些斜率限制在$1$與$-1$之間。我們稱這個約束式為Lipschitz continuity(1-Lipschitz)，並寫成$\lVert f \lVert_{L \leq 1}$。這樣，我們EMD的[對偶形](http://terms.naer.edu.tw/detail/4689910/)就是
$$\mathrm{EMD}(P_r, P_\theta) = \sup_{\lVert f \lVert_{L \leq 1}} \ \mathbb{E}_{x \sim P_r} f(x) - \mathbb{E}_{x \sim P_\theta} f(x).$$

實作很簡單：

# linprog() can only minimize the cost, because of that
# we optimize the negative of the objective. Also, we are
# not constrained to nonnegative values.
opt_res = linprog(-b, A, c, bounds=(None, None))

emd = -opt_res.fun
f = opt_res.x[0:l]
g = opt_res.x[l:]


_{Fig.6：最佳化$f$、$P_r$以及$g=-f$與$P_\theta$的逐一元素相乘。}

如我們所看到的，最佳化的策略當然要設置$f(x)$在$P_r(x) > P_\theta(x)$取得高的數值，在$P_\theta > P_r$得到低的數值。
## Wasserstein Distance
最後，我們必須考慮[連續機率分佈](http://terms.naer.edu.tw/detail/3647494/)。當然我們可以很直觀的將它們視為有無限多個狀態的離散分佈，並使用到目前為止所描述的類似推理。但就像我在一開始的時候提到，我們會嚐試一些更簡潔的東西。假設我們的連續分佈是$p_r$與$p_\theta$，連結分佈與邊界$p_r$與$p_\theta$的為$\pi(p_r,p_\theta)$。然後，Wasserstein distance定義為：

$$W(p_r, p_\theta) = \inf_{\gamma \in \pi} \iint\limits_{x,y} \lVert x - y \lVert \gamma (x,y) \, \mathrm{d} x \, \mathrm{d} y = \inf_{\gamma \in \pi} \mathbb{E}_{x,y \sim \gamma} \left[ \lVert x - y \lVert \right].$$

如果我們增加適當的項目，我們就可以移除所有在分佈-$\gamma$上的約束式。這可以通過在函數$f: x \mapsto k \in \mathbb{R}$增加額外的優化來完成，排除所有$\gamma \neq \pi$做為解法：

$$\begin{array}{rl}
W(p_r, p_\theta) & = \inf\limits_{\gamma \in \pi} \mathbb{E}_{x,y \sim \gamma} [ \lVert x - y \lVert ] \\
&\begin{array}{cc}
= \inf\limits_{\gamma } \mathbb{E}_{x,y \sim \gamma} [ \lVert x - y \lVert & + \; \underbrace{\sup\limits_{f} \mathbb{E}_{s \sim p_r}[f(s)] - \mathbb{E}_{t \sim p_\theta}[f(t)] - \left( f(x) - f(y) \right)} ] \\
&= \cases{\begin{align} 0, & \ \ \ \mathrm{if \ \gamma \in \mathrm{\pi}} \\ + \infty & \ \ \ \mathrm{else} \end{align}} \end{array}\\
& = \inf\limits_{\gamma} \ \sup\limits_{f} \ \mathbb{E}_{x,y \sim \gamma} [ \lVert x - y \lVert + \mathbb{E}_{s \sim p_r}[f(s)] - \mathbb{E}_{t \sim p_\theta}[f(t)] - \left( f(x) - f(y) \right) ]
\end{array}$$

現在我們有二階優化。這意味著我們對外部優化($\inf_\gamma$)的每個值採用內部優化($\sup_f$)的最佳解，然後從這些可能的解法中選擇對外部優化而言的最佳解。

為了繼續，我們必需使用[大中取小的原則](http://terms.naer.edu.tw/detail/2119777/)，這說明了在某些情況下，我們可以在不改變解法的情況下反轉$\inf$與$\sup$的排序。但首先我們必須證明我們的問題確實是這種情況。

考慮某些函數$g: A, B \rightarrow \mathbb{R}$。假設$g(\hat{a}, \hat{b}) = \inf_{a \in A} \sup_{\ b \in B} g(a,b)$(最小的最大值)，而且$g(\hat{a}’, \hat{b}’) = \sup_{\ b \in B} \inf_{a \in A} g(a,b)$(最大的最小值)。$g(\hat{a}, \hat{b}) \geq g(\hat{a}’, \hat{b}’)$的論點很簡單：任何的$g(\hat{a}, \hat{b})$都會自動地被允許做為$\sup_{\ b \in B} \inf_{a \in A} g(a,b)$的[最大下界](http://terms.naer.edu.tw/detail/3184349/)的候選，反之不行。

對於$g(\hat{a}, \hat{b}) > g(\hat{a}’, \hat{b}’)$，最少下面一項論述需為真：
* $g(\hat{a}+t, \hat{b}) < g(\hat{a}, \hat{b})$，$t \neq 0$，這只有在$\inf_{\ a \in A} g(a,b)$在$a$不是[凸的](http://terms.naer.edu.tw/detail/3186767/)(convex)才有可能，因為$g(\hat{a}, \hat{b})$已經是$\hat{a}$的[最大下界](http://terms.naer.edu.tw/detail/3184349/)
* $g(\hat{a}’, \hat{b}’+t) > g(\hat{a}’, \hat{b}’)$ ，$t \neq 0$，這只有在$\inf_{\ a \in A} g(a,b)$在$b$不是[凹的](http://terms.naer.edu.tw/detail/2113188/)(concave)，因為$g(\hat{a}’, \hat{b}’)$已經是$\hat{b}’$的[最小上界](http://terms.naer.edu.tw/detail/3184750/)

這當然意味著，如果$\sup_{\ b \in B} g(a,b)$是[凸的](http://terms.naer.edu.tw/detail/3186767/)(convex)的，並且$\inf_{\ a \in A} g(a,b)$是[凹的](http://terms.naer.edu.tw/detail/2113188/)(concave)，那麼[大中取小的原則](http://terms.naer.edu.tw/detail/2119777/)適用，而且$g(\hat{a}, \hat{b}) = g(\hat{a}’, \hat{b}’)$。在我們的情況，我們可以從下面的括號看到[凸性](http://terms.naer.edu.tw/detail/2113768/)條件已經滿足。讓我們試著調整為$\sup \inf$：

$$\begin{array}{ll}
&\phantom{= , } \sup\limits_{f} \ \inf\limits_{\gamma} \ \mathbb{E}_{x,y \sim \gamma} [ \lVert x - y \lVert + \mathbb{E}_{s \sim p_r}[f(s)] - \mathbb{E}_{t \sim p_\theta}[f(t)] - (f(x) - f(y)) ] \\
&\begin{array}{cc}
= \sup\limits_{f} \ \mathbb{E}_{s \sim p_r}[f(s)] - \mathbb{E}_{t \sim p_\theta}[f(t)] + & \underbrace{ \inf\limits_{\gamma} \ \mathbb{E}_{x,y \sim \gamma} [ \lVert x - y \lVert - ( f(x) - f(y))} ] \\
&= \cases{\begin{align} 0, & \ \ \ \mathrm{if} \ \| f \| {}_{L} \leq 1\\ - \infty & \ \ \ \mathrm{else} \end{align}}
\end{array}
\end{array}$$

根據需要，我們看到[最大下界](http://terms.naer.edu.tw/detail/3184349/)(infimum)是[凹的](http://terms.naer.edu.tw/detail/2113188/)(concave)。因為所有的Lipschitz連續函數$\mathbf{f}$都為$\inf_\gamma$產生相同的最佳解，而且只有它們是$\sup_f$的可行解，我們可以將這個條件變為約束式。這樣，我們就得到Wasserstein distance的[對偶形](http://terms.naer.edu.tw/detail/4689910/)(dual form)：

$$\begin{align}
W(p_r, p_\theta) & = \sup_{f} \ \mathbb{E}_{s \sim p_r}[f(s)] - \mathbb{E}_{t \sim p_\theta}[f(t)] + \inf_{\gamma} \ \mathbb{E}_{x,y \sim \gamma} [ \lVert x - y \lVert - ( f(x) - f(y)) ] \\
& =\sup_{\lVert f \lVert_{L \leq 1}} \ \mathbb{E}_{s \sim p_r}[f(s)] - \mathbb{E}_{t \sim p_\theta}[f(t)]
\end{align}$$

這就是Kantorovich-Rubinstein duality的範例。它還適合其它的度量距離，而不是只有我們所使用的歐幾里德距離。但是函數$\mathbf{f}$是適合用神經網路來近似的，使用神經網路的優點是可以透過限制權重的方式來實現Lipschitz連續性。