GANなどの生成モデルで使われるようになりたびたび聞くことも増えたワッサースタイン(Wasserstein)距離というものを解説します。
ワッサースタイン距離というのは一言でいうと、確率分布間を測る距離の一つです。
この記事では離散確率分布に対するワッサースタイン距離の定義とそれが距離の公理を満たすことを証明します。
最適輸送問題とは
最適輸送問題は、物理学や経済学などの分野で長い歴史を持つ数理的な問題です。この問題は、ある場所に存在する物資を別の場所に運ぶ際の最適な方法を探求します。具体的には、物資を運ぶためのコストを最小化する方法を見つけることを目的としています。
最適輸送問題の歴史は、18世紀のフランスの数学者ガスパール・モンジュによる「モンジュの問題」にまで遡ります。モンジュの問題は、物資を運ぶ際の距離を最小化するというものでした。後に、ソビエト連邦の数学者レオン・カントロヴィッチがこの問題を拡張し、線形計画法を用いて解を導く方法を提案しました。このアプローチは「カントロヴィッチの問題」として知られています。
ヒストグラムの最適輸送距離の定式化
ヒストグラムの最適輸送距離の定式化
- 入力：比較するヒストグラム\(\boldsymbol{a}, \boldsymbol{b} \in \mathbb{R}^n\)、各点の距離を表す行列\(\mathbf{C} \in \mathbb{R}^{n \times n}\)
- 出力：ヒストグラムの距離\(\mathrm{OT}(\boldsymbol{a}, \boldsymbol{b}, \mathbf{C}) \in \mathbb{R}\)
- 最適輸送距離を以下の最適問題の最適値と定義する
$$
\begin{array}{lc}
\text{minimize}_{P \in \mathbb{R}^{n \times n}} & \sum_{i=1}^n \sum_{j=1}^n C_{i j} P_{i j} \\
\text { s.t. } & P_{i j} \geq 0 \quad \forall i, j \in [n]\\
& \sum_{j=1}^n P_{i j}=\boldsymbol{a}_i \quad \forall i \in [n] \\
& \sum_{i=1}^n P_{i j}=\boldsymbol{b}_j \quad \forall j \in [n]
\end{array}
$$
これは線形計画問題です。
点群の最適輸送距離の定式化
点群の最適輸送の定式化
- 入力：比較する点群\(\alpha=\left\{x_1, \cdots, x_n\right\}, \beta=\left\{y_1, \cdots, y_m\right\} \subset \mathcal{X}\)、各点の距離を表す関数\(C: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}\)
- 出力：点群の距離\(\mathrm{OT}(\alpha, \beta, C) \in \mathbb{R}\)
- 最適輸送距離を以下の最適化問題の最適値と定義する
$$
\begin{array}{lc}
\text{minimize}_{P \in \mathbb{R}^{n \times n}} & \sum_{i=1}^n \sum_{j=1}^n C_{i j} P_{i j} \\
\text { s.t. } & P_{i j} \geq 0 \quad \forall i\in [n], j \in [m] \\
& \sum_{j=1}^n P_{i j}=\boldsymbol{a}_i \quad \forall i \in [n] \\
& \sum_{i=1}^n P_{i j}=\boldsymbol{b}_j \quad \forall j \in [m]
\end{array}
$$
これも線形計画問題です。
点群、ヒストグラム両方に対して、条件のs.t.以降二行目と三行目\(\sum_{j=1}^n P_{i j}=\boldsymbol{a}_i ,\sum_{i=1}^n P_{i j}=\boldsymbol{b}_j\)に関しては質量（確率値）が消滅したり生成されたりしないことを表しており、質量保存制約と呼ばれます。成分がすべて１のベクトル\(\mathbb{1}_n \in \mathbb{R}^n, \mathbb{1}_m \in \mathbb{R}^m\)を用いると、質量保存制約は
$$
\begin{aligned}
\boldsymbol{P} \mathbb{1}_m & =\boldsymbol{a} \\
\boldsymbol{P}^{\top} \mathbb{1}_n & =\boldsymbol{b}
\end{aligned}
$$
と書くこともできます。
そこで、制約条件を満たすような行列全体の集合を
$$
\mathcal{U}(\boldsymbol{a}, \boldsymbol{b}) \stackrel{\text { def }}{=}\left\{\boldsymbol{P} \in \mathbb{R}^{n \times m} \mid \boldsymbol{P}_{i j} \geq 0, \boldsymbol{P} \mathbb{1}_m=\boldsymbol{a}, \boldsymbol{P}^{\top} \mathbb{1}_n=\boldsymbol{b}\right\}
$$
と書くことにしましょう。
連続分布比較の場合の最適輸送距離の定式化
連続分布比較の場合の最適輸送距離の定式化
- 入力：比較する確率分布\(\mu, \nu\)、各点の距離を表す関数\(C: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}\)
- 出力：分布の距離\(\mathrm{OT}(\mu, \nu, C) \in \mathbb{R}\)
- 最適輸送距離を以下の最適化問題の最適値と定義する
$$
\begin{aligned}
&\begin{array}{ll}
\text{minimize}_{\pi \in \mathcal{P}(\mathcal{X} \times \mathcal{X})} & \int_{\mathcal{X} \times \mathcal{X}} C(x, y) d \pi(x, y) \\
\text { s.t. } & \pi(\mathcal{A}, \mathcal{B}) \geq 0 \quad \forall \mathcal{A}, \mathcal{B} \\
& \pi(\mathcal{A}, \mathcal{X})=\mu(\mathcal{A}) \quad \forall \mathcal{A} \\
& \pi(\mathcal{X}, \mathcal{B})=\nu(\mathcal{B}) \quad \forall \mathcal{B}
\end{array}\\
\end{aligned}
$$
このように最適輸送では定式化されます。ヒストグラムの場合と点群の場合はほとんど同じ線形計画問題です。アルゴリズム的にはほとんど同じ問題とみなされる場合が多いです。これらは線形計画なので既存のソルバーを用いて機械的に解くことができます。
しかし連続分布同士の最適輸送は連続分布の最適化問題となるので解くのが難しいのです。(連続分布からサンプリングを行って点群比較に帰着させたり、双対を使ったアプローチなどで工夫して解かれる）
なのでここでは、一旦離散最適輸送を考えます。
ワッサースタイン距離(Wasserstein)とは
それぞれの定式化で入力されている距離を表す関数や行列\(\mathbf{C}\)は設定次第で距離の公理を満たしません。例えばすべてのコストが０なら、すべての分布の距離は０になってしまいます。
ワッサースタイン距離は、最適輸送コストの特別なケースであり、距離の公理を満たすように定義されています。距離の公理とは、非負性、対称性、三角不等式の3つの条件を満たすことを指します。
【定義】ワッサーシュタイン距離
\(\mathcal{X}\) 上の距離関数 \(d: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}\) と実数 \(p \geq 1\) について、コスト 関数を \(C(x, y)=d(x, y)^p\) と定義する. このとき, \(\alpha, \beta \in \mathcal{P}(\mathcal{X})\) に ついて
$$
W_p(\alpha, \beta) \stackrel{\text { def }}{=} \mathrm{OT}(\alpha, \beta, C)^{1 / p}
$$
を\(\alpha\)と\(\beta\)のp-ワッサースタイン距離という
コストとして距離や距離の二乗をとるのは自然な選択でしょう。たとえば、\(\mathcal{X}=\mathbb{R}^L\)のときには、\(C(\boldsymbol{x}, \boldsymbol{y})=\|\boldsymbol{x}-\boldsymbol{y}\|_2\)とした1-ワッサースタイン距離や\(C(\boldsymbol{x}, \boldsymbol{y})=\|\boldsymbol{x}-\boldsymbol{y}\|_2^2\)とした2-ワッサースタイン距離がよく用いられます。\(p\)が文脈上明らかな場合や、議論が\(p\)の値に依存しない場合は単にワッサースタイン距離と呼びます。
点同士の距離として点 \(x\) と点 \(y\) の間の距離を定めるのは比較的簡単です。例えば、ユークリッド距離（\(|x - y|_2\)）やマンハッタン距離（\(|x - y|_1\)）などが一般的です。これらは、点の座標を使って計算できる単純な距離です。
それに対し分布同士の距離に関して分布 \(\alpha\) と分布 \(\beta\) の間の距離を定めるのは難しいです。分布は単一の点ではなく、多くの点の集合で、その点がどの程度の頻度で出現するかを示すものです。そのため、単に点と点の距離を計算するようにはいきません。
分布 \(\alpha\) と \(\beta\) の間の距離を定める方法は色々ありますが、それぞれの方法には特有の問題があります。従来から機械学習でよく使われるKLダイバージェンスは分布の重なり具合を見る方法ですが、次の節で見ますが重なりがない場合（ディラック測度の例など）には無限大となり、直感的な距離とは言えません。
ワッサースタイン距離はその定義から、点 \(x\) と点 \(y\) の距離 \(d(x, y)\) を定めるだけで、分布 \(\alpha\) と \(\beta\) の間の距離が自動的に計算されます。つまり、分布間の距離を定めるという難しい問題を、点の距離を定めるという比較的簡単な問題に置き換えることができるのです。
ワッサースタイン距離とKLダイバージェンスの比較
ワッサースタイン距離とKLダイバージェンスは、確率分布間の「距離」を測るための異なるアプローチを提供します。これらは異なる性質を持ち、それぞれ特定の用途に適しています。ここでは、ディラック測度を用いた具体例を通じて、ワッサースタイン距離とKLダイバージェンスの性質を比較します。
ディラック測度のワッサースタイン距離
まず、\(\boldsymbol{x}, \boldsymbol{y} \in \mathbb{R}^L\) に対してディラック測度 \(\delta_{\boldsymbol{x}}, \delta_{\boldsymbol{y}}\) を考えます。ディラック測度は、質量が全て一点に集中している確率分布です。\(\boldsymbol{x}\) から \(\boldsymbol{y}\) への輸送方法は、質量1を \(\boldsymbol{x}\) から \(\boldsymbol{y}\) に輸送する方法のみであるため、p-ワッサースタイン距離は以下のように計算されます。
$$
\begin{aligned}
W_p\left(\delta_{\boldsymbol{x}}, \delta_{\boldsymbol{y}}\right) & =\left(1 \cdot\|\boldsymbol{x}-\boldsymbol{y}\|_2^p\right)^{1 / p} \\
& =\|\boldsymbol{x}-\boldsymbol{y}\|_2
\end{aligned}
$$
この結果から、ディラック測度に対するワッサースタイン距離は、\(\boldsymbol{x}\) と \(\boldsymbol{y}\) の間のユークリッド距離と一致することがわかります。これは、ワッサースタイン距離がユークリッド空間の距離構造を正確に反映していることを示しています。
ディラック測度のKLダイバージェンス
一方で、KLダイバージェンスは次のように定義されます。
$$
\mathrm{KL}\left(\delta_{\boldsymbol{x}} \| \delta_y\right)= \begin{cases}0 & (\boldsymbol{x}=\boldsymbol{y}) \\ \infty & (\boldsymbol{x} \neq \boldsymbol{y})\end{cases}
$$
この結果から、ディラック測度に対するKLダイバージェンスは、\(\boldsymbol{x}\) と \(\boldsymbol{y}\) が等しい場合には0、それ以外の場合には無限大となります。つまり、KLダイバージェンスはユークリッド空間の距離構造を反映していないことがわかります。
ワッサースタイン距離が距離の公理を満たすことの証明
ここからはワッサースタイン距離が距離の公理を満たすことを証明したいと思います。つまり、非負性、対称性、三角不等式の三つがワッサースタイン距離では成立することを示します。
証明したいこと
p-ワッサースタイン距離は距離の公理を満たす。すなわち,
1. \(W_p(\alpha, \beta)=0\) のときかつそのときのみ \(\alpha=\beta\) （非負性）
2. \(W_p(\alpha, \beta)=W_p(\beta, \alpha) \quad \forall \alpha, \beta\) （対称性）
3. \(W_p(\alpha, \beta)+W_p(\beta, \gamma) \geq W_p(\alpha, \gamma) \quad \forall \alpha, \beta, \gamma\) （三角不等式）
前提条件
\(\mathcal{X}=\left\{x_1, x_2, \ldots, x_n\right\}\)とし、距離関数\(d=\mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}\)を任意にとり、\(C(x, y)=d(x, y)^p\)とする。確率ベクトル\(\boldsymbol{a}, \boldsymbol{b}, \boldsymbol{c} \in \Sigma_n\)を任意にとり
$$
\begin{aligned}
& \alpha=\sum_{i=1}^n a_i \delta_{x_i} \\
& \beta=\sum_{i=1}^n b_i \delta_{x_i} \\
& \gamma=\sum_{i=1}^n c_i \delta_{x_i}
\end{aligned}
$$
とする。ただし、\(\mathcal{X}\)の要素に重複はなく
$$
i \neq j \Rightarrow x_i \neq x_j
$$
とする。\(\alpha,\beta\)間の最適輸送行列を\(\boldsymbol{P}^* \in \mathbb{R}_{\geq 0}^{n \times n}\),\((\beta, \gamma)\)間の最適輸送行列を\(Q^* \in \mathbb{R}_{\geq 0}^{n \times n}\)とする
1.非負性の証明
\(W_p(\alpha, \beta)=0\)とすると、\(W_p(\alpha, \beta)^p=\sum_{i j} d\left(x_i, x_j\right)^p \boldsymbol{P}_{i j}^*=0\)である。このとき、ある\((i, j)\)に対して、\(\boldsymbol{P}_{i j}^*>0\)であるとすると、\(d\left(x_i, x_j\right)^p=0\)でなければならず、距離の公理より\(x_i = x_j\)である。上式より、これは\(i = j\)を意味する。すなわち、\(i \neq j\) の場合は\(\boldsymbol{P}_{ij}^* = 0\) であり、\(i = j\) の場合のみ\(\boldsymbol{P}_{ij}^* > 0\)となります。
よって\(P^*\)の成分の中で正値をとるのは対角成分のみである。このとき
$$
\boldsymbol{a} \stackrel{(\mathrm{a})}{=} \boldsymbol{P}^* \mathbb{1}_n \stackrel{(\mathrm{b})}{=} \boldsymbol{P}^{* T} \mathbb{1}_n \stackrel{(\mathrm{c})}{=} \boldsymbol{b}
$$
である。ただし、(a),(c)は最適化問題の質量制約条件より、(b)は対角成分以外が０であるので\(P^*\)が対称であることより従う。ヒストグラムの重み\(\boldsymbol{a},\boldsymbol{b}\)が一致するということは\(\alpha=\beta\)を意味する。
逆に、\(\alpha=\beta\)すなわち\(\boldsymbol{a}=\boldsymbol{b}\)と仮定する。このとき、
$$
\boldsymbol{P}=\operatorname{Diag}(\boldsymbol{a})=\left(\begin{array}{cccc}
\boldsymbol{a}_1 & 0 & \ldots & 0 \\
0 & \boldsymbol{a}_2 & \ldots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \ldots & \boldsymbol{a}_n
\end{array}\right)
$$
とおくと、これは制約条件を満たし
$$
\sum_{i=1}^n \sum_{j=1}^n d\left(x_i, x_j\right)^p \boldsymbol{P}_{i j}=\sum_{i=1}^n d\left(x_i, x_i\right)^p \boldsymbol{P}_{i i}=0
$$
となる。距離の公理より\(d\left(x_i, x_j\right) \geq 0\)であり目的関数は常に非負であるので、これが最適解である。すなわち\(W_p(\alpha, \beta)=0\)である。
2.対称性の証明
\(P^*\)を\((\alpha, \beta)\)間の最適輸送行列とすると、\(\boldsymbol{P}^{* \top}\)は\((\beta, \alpha)\)間の輸送行列である。距離の公理より\(d\left(x_i, x_j\right)=d\left(x_j, x_i\right)\)であるので、\(\boldsymbol{P}^{* \top}\)の目的関数値は\(\boldsymbol{P}^*\)と一致する、よって少なくとも\(W_p(\beta, \alpha)^p\)は\(W_p(\alpha,\beta )^p\)以下である。同様の議論より\(W_p(\alpha, \beta)^p \leq W_p(\beta, \alpha)^p\)でもあるので、併せて\(W_p(\alpha, \beta)=W_p(\beta, \alpha)\)となる。
3.三角不等式の証明
\(\boldsymbol{R} \stackrel{\text { def }}{=} \boldsymbol{P}^* \operatorname{Diag}(1 / \boldsymbol{b}) \boldsymbol{Q}^*\)とする。ただし\(1 / \boldsymbol{b}\)は成分ごとに逆数をとり、\(0\)の逆数は\(0\)であると定義する。
ここで、\(\operatorname{Diag}(1 / \boldsymbol{b})\) は対角行列である。このとき、\(\boldsymbol{R}_{ij} \geq 0\) であることは明らか。なぜなら、\(\boldsymbol{P}^*\) と \(\boldsymbol{Q}^*\) はそれぞれ非負の行列であり、対角行列 \(\operatorname{Diag}(1 / \boldsymbol{b})\) も非負であるためである。
$$
\begin{aligned}
\boldsymbol{R} \mathbb{1}_n & =\boldsymbol{P}^* \operatorname{Diag}(1 / \boldsymbol{b}) \boldsymbol{Q}^* \mathbb{1}_n \\
& \stackrel{(\mathrm{a})}{=} \boldsymbol{P}^* \operatorname{Diag}(1 / \boldsymbol{b}) \boldsymbol{b} \\
& =\boldsymbol{P}^* \mathbb{1}_{\boldsymbol{b}>0} \\
& \stackrel{(\mathrm{b})}{=} \boldsymbol{P}^* \mathbb{1}_n \\
& \stackrel{(\mathrm{c})}{=} \boldsymbol{a}
\end{aligned}
$$
かつ、
$$
\begin{aligned}
\boldsymbol{R}^{\top} \mathbb{1}_n \stackrel{(\mathrm{d})}{=} \boldsymbol{Q}^{* \top} \operatorname{Diag}(1 / \boldsymbol{b}) \boldsymbol{P}^{* \top} \mathbb{1}_n
& =Q^{* \top} \operatorname{Diag}(1 / \boldsymbol{b}) \boldsymbol{b} \\
& =Q^{* \top} \mathbb{1}_{\boldsymbol{b}>0} \\
& \stackrel{(\mathrm{e})}{=} Q^{* \top} \mathbb{1}_n \\
& \stackrel{(\mathrm{f})}{=} c
\end{aligned}
$$
であるので、\(\boldsymbol{R} \in \mathcal{U}(\boldsymbol{a}, \boldsymbol{c})\)である。ただし\(\mathbb{1}_{\boldsymbol{b}>0} \in \mathbb{R}^n\)は\(\boldsymbol{b} > 0\)の指示ベクトルである。すなわち\(\mathbb{1}_{\boldsymbol{b}}>0\)の\(i\)次元目は\(\boldsymbol{b}_i>0\)のとき1でそれ以外は0となる。(a)は\(Q^* \in \mathcal{U}(\boldsymbol{b}, \boldsymbol{c})\)から、(b)は\(\boldsymbol{P}^* \in \mathcal{U}(\boldsymbol{a}, \boldsymbol{b})\)より\(\boldsymbol{b}_j=0\)のとき、任意のiについて\(\boldsymbol{P}_{i j}^*=0\)となることから、(c)は\(P^* \in \mathcal{U}(\boldsymbol{a}, \boldsymbol{b})\)から、(d)は\(R\)の定義から、(e)は\(Q^* \in \mathcal{U}(\boldsymbol{b}, \boldsymbol{c})\)より\(\boldsymbol{b}_j=0\)のとき、任意の\(k\)について\(\boldsymbol{Q}_{j k}^*=0\)となることから、(f)は\(Q^* \in \mathcal{U}(\boldsymbol{b}, \boldsymbol{c})\)から従う。
はてな
指示ベクトル \(\mathbb{1}_{\boldsymbol{b} > 0}\) は次のように定義されます。
$$
1_{\boldsymbol{b}>0}= \begin{cases}1 & \text { if } \boldsymbol{b}_i>0 \\ 0 & \text { if } \boldsymbol{b}_i=0\end{cases}
$$
このベクトルの各成分は、対応する \(\boldsymbol{b}\) の成分が0より大きいかどうかを示しています。
具体的な例を用いて説明しましょう。例えば、\(\boldsymbol{b} = (0.5, 0, 1.2, 0, 3.4)\) というベクトルがあったとします。この場合、\(\mathbb{1}_{\boldsymbol{b} > 0}\) は次のようになります。
$$
1_{b>0}=(1,0,1,0,1)
$$
これは、\(\boldsymbol{b}\) の成分が0より大きい場所に 1 を持ち、それ以外の場所に 0 を持つベクトルです。
この指示ベクトルは、計算や条件付き操作でよく使用されます。特に、この文脈では、\(\operatorname{Diag}(1 / \boldsymbol{b}) \boldsymbol{b}\) の計算に関連しています。
次に、\(\operatorname{Diag}(1 / \boldsymbol{b}) \boldsymbol{b}\) について詳しく見てみましょう。この演算は、\(\boldsymbol{b}\) の各成分の逆数を対角成分とする対角行列を \(\boldsymbol{b}\) に掛ける操作です。
例えば、\(\boldsymbol{b} = (0.5, 0, 1.2, 0, 3.4)\) の場合、\(\operatorname{Diag}(1 / \boldsymbol{b})\) は次のようになります。
$$
\operatorname{Diag}(1 / \boldsymbol{b})=\left(\begin{array}{ccccc}
2 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & \frac{1}{1.2} & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & \frac{1}{3.4}
\end{array}\right)
$$
この対角行列を \(\boldsymbol{b}\) に掛けると、\(\mathbb{1}_{\boldsymbol{b} > 0}\) が得られます。
$$
\operatorname{Diag}(1 / \boldsymbol{b}) \boldsymbol{b}=\left(\begin{array}{ccccc}
2 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & \frac{1}{1.2} & 0 & 0 \\
0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & \frac{1}{3.4}
\end{array}\right)\left(\begin{array}{c}
0.5 \\
0 \\
1.2 \\
0 \\
3.4
\end{array}\right)=\left(\begin{array}{l}
1 \\
0 \\
1 \\
0 \\
1
\end{array}\right)=1_{\boldsymbol{b}>0}
$$
このようにして、\(\mathbb{1}_{\boldsymbol{b} > 0}\) は、\(\boldsymbol{b}\) の成分が0より大きい場所に 1 を持ち、それ以外の場所に 0 を持つベクトルであることが確認できます。
また、
$$
\begin{aligned}
& W_p(\alpha, \gamma) \\
& =\min _{\boldsymbol{P} \in \mathcal{U}(\boldsymbol{a}, \boldsymbol{c})}\left(\sum_{i=1}^n \sum_{k=1}^n d\left(x_i, x_k\right)^p \boldsymbol{P}_{i k}\right)^{1 / p} \\
& \stackrel{(a)}{\leq}\left(\sum_{i=1}^n \sum_{k=1}^n d\left(x_i, x_k\right)^p \boldsymbol{R}_{i k}\right)^{1 / p} \\
& =\left(\sum_{i=1}^n \sum_{k=1}^n d\left(x_i, x_k\right)^p \sum_{j=1}^n \boldsymbol{P}_{i j}^* \frac{1}{\boldsymbol{b}_j} \boldsymbol{Q}_{j k}^*\right)^{1 / p} \\
& =\left(\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n d\left(x_i, x_k\right)^p \boldsymbol{P}_{i j}^* \frac{1}{\boldsymbol{b}_j} \boldsymbol{Q}_{j k}^*\right)^{1 / p}\\
& \stackrel{\text { (b) }}{\leq}\left(\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n d\left(x_i, x_j\right)^p \boldsymbol{P}_{i j}^* \frac{1}{\boldsymbol{b}_j} \boldsymbol{Q}_{j k}^*\right)^{1 / p} \\
&\qquad+\left(\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n d\left(x_j, x_k\right)^p \boldsymbol{P}_{i j}^* \frac{1}{\boldsymbol{b}_j} \boldsymbol{Q}_{j k}^*\right)^{1 / p} \\
&=\left(\sum_{i=1}^n \sum_{j=1}^n d\left(x_i, x_j\right)^p \boldsymbol{P}_{i j}^* \frac{1}{\boldsymbol{b}_j} \sum_{k=1}^n \boldsymbol{Q}_{j k}^*\right)^{1 / p} \\
&\qquad+\left(\sum_{j=1}^n \sum_{k=1}^n d\left(x_j, x_k\right)^p \boldsymbol{Q}_{j k}^* \frac{1}{\boldsymbol{b}_j} \sum_{i=1}^n \boldsymbol{P}_{i j}^*\right)^{1 / p} \\
& \stackrel{\text { (c) }}{=}\left(\sum_{i=1}^n \sum_{j=1}^n d\left(x_i, x_j\right)^p \boldsymbol{P}_{i j}^* \frac{1}{\boldsymbol{b}_j} \boldsymbol{b}_j\right)^{1 / p} \\
&\qquad+\left(\sum_{j=1}^n \sum_{k=1}^n d\left(x_j, x_k\right)^p \boldsymbol{Q}_{j k}^* \frac{1}{\boldsymbol{b}_j} \boldsymbol{b}_j\right)^{1 / p} \\
&=\left(\sum_{i=1}^n \sum_{j=1}^n d\left(x_i, x_j\right)^p \boldsymbol{P}_{i j}^*\right)^{1 / p}+\left(\sum_{j=1}^n \sum_{k=1}^n d\left(x_j, x_k\right)^p \boldsymbol{Q}_{j k}^*\right)^{1 / p} \\
& \stackrel{\text { (d) }}{=} W_p(\alpha, \beta)+W_p(\beta, \gamma)
\end{aligned}
$$
となる。ただし(a)は\(\boldsymbol{R} \in \mathcal{U}(a, c)\)より、目的関数値は最適値以上であることから、(b)はミンコフスキーの不等式と三角不等式より、(c)は\(P^* \in \mathcal{U}(a, b)\)および\(Q^* \in \mathcal{U}(b, c)\)から、(d)は\(\boldsymbol{P}^*\) と \(\boldsymbol{Q}^*\)が\(W_p(\alpha, \beta)\)と\(W_p(\beta, \gamma)\)についての最適輸送行列であることから従う。 □
参考先
