最適輸送

同義語:optimal transport最適輸送問題optimal transportationMonge–Kantorovich問題

概要

最適輸送(optimal transport)とは、確率測度 $\mu$ の質量を確率測度 $\nu$ の形へ運ぶ費用 $\int c(x,y)\,d\pi$ を、周辺分布が $\mu,\nu$ の結合 $\pi$ について最小にする問題とその理論である。コンパクトな距離空間と連続な費用では最適な結合が存在し、最小値は $\varphi(x)+\psi(y)\le c(x,y)$ を満たす連続関数の組の $\int\varphi\,d\mu+\int\psi\,d\nu$ の最大値に等しい(Kantorovich の双対定理)。結合が最適であることは、台が $c$-巡回単調であることと同値である。実数直線の上で費用が $\lvert x-y\rvert^p$($p\ge1$)で $p$ 次モーメントが有限なら、分布関数の逆関数を並べた単調な結合が最適である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Prokhorovの定理, 凸関数, 輸送問題

最適輸送(optimal transport)は、ある確率測度 $\mu$ で分布する質量を、別の確率測度 $\nu$ の形に運び直すとき、運ぶ費用の合計を最小にする方法を求める問題とその理論である。点 $x$ から点 $y$ へ単位質量を運ぶ費用を $c(x,y)$ とする。Monge(1781)は質量を写像 $T$ で運ぶ問題を立て、Kantorovich(1940)は 1 点の質量を分けて運ぶことを許す緩和した問題を立てた。
Kantorovich の問題は、無限次元の 線形計画法 である。有限個の点の場合は 輸送問題 そのもので、その双対定理が理論の中心にある。この記事の主定理は、コンパクトな距離空間と連続な費用について、次の 3 つを示す Kantorovich の双対定理 である。

  • 最小の費用は、$\varphi(x)+\psi(y)\le c(x,y)$ を満たす関数の組についての $\int\varphi\,d\mu+\int\psi\,d\nu$ の最大値に等しい。
  • 最大値は、互いに $c$-変換の関係にある組で達成される。
  • 結合が最適であることは、その台が $c$-巡回単調であることと同値である。
    応用として、実数直線の上で費用 $\lvert x-y\rvert^p$($p\ge1$)について、分布関数の逆関数を並べた 単調な結合 が最適であることを示す。$p$ 乗の費用による距離は Wasserstein距離、2 乗の費用の最適な写像は Brenierの定理、有限個の点の計算は 輸送問題 が扱う。

Monge の問題と Kantorovich の問題

$X,Y$ を完備可分な距離空間とし、$\mathcal{P}(X)$ を $X$ の上の Borel 確率測度の全体とする。Borel 写像 $T\colon X\to Y$ による押し出しを $T_\#\mu(E):=\mu(T^{-1}(E))$ と書く。$\mu\in\mathcal{P}(X)$、$\nu\in\mathcal{P}(Y)$ について、$X\times Y$ の上の Borel 確率測度 $\pi$ で、周辺分布が $\mu,\nu$ であるもの、すなわち
$$ \pi(A\times Y)=\mu(A),\qquad\pi(X\times B)=\nu(B) $$
を満たすものを 結合(coupling)または 輸送計画 という。結合の全体を $\Pi(\mu,\nu)$ と書く。$\pi(A\times B)$ は「$A$ にある質量のうち $B$ へ運ばれる量」を表す。

Monge の問題と Kantorovich の問題

$c\colon X\times Y\to[0,\infty]$ を Borel 関数とし、費用 と呼ぶ。

  1. Monge の問題:$T_\#\mu=\nu$ を満たす Borel 写像 $T\colon X\to Y$(輸送写像)の中で、$\displaystyle\int_Xc(x,T(x))\,d\mu(x)$ を最小にする。
  2. Kantorovich の問題:$\pi\in\Pi(\mu,\nu)$ の中で、$\displaystyle\int_{X\times Y}c\,d\pi$ を最小にする。最小を達成する $\pi$ を 最適な結合 という。

$T$ が輸送写像なら、$(\mathrm{id},T)_\#\mu$ は結合で、費用は $\int c(x,T(x))\,d\mu$ に等しい。したがって Kantorovich の問題の下限は、Monge の問題の下限以下である。Kantorovich の問題には次の利点がある(AG13 Problem 1.1・1.2 の後の段落、pp. 4–5)。

  • $\Pi(\mu,\nu)$ は積の測度 $\mu\otimes\nu$ を含むので空でなく、凸集合で、費用は $\pi$ について線形である。
  • 費用が下半連続で下に有界なら、最適な結合が存在する(AG13 Theorem 1.5、p. 5。$p$ 乗の距離の場合の証明は Wasserstein距離 の定理「最適な結合の存在」にある)。
輸送写像がない例

$X=Y=\mathbb{R}$、$\mu=\delta_0$、$\nu=\frac12(\delta_{-1}+\delta_1)$ とする。どの写像 $T$ についても $T_\#\delta_0=\delta_{T(0)}$ は 1 点の測度なので、輸送写像はない。結合は $\delta_0\otimes\nu$ だけで、Kantorovich の問題の値は $\frac12c(0,-1)+\frac12c(0,1)$ である。原点の質量を半分ずつに分けて運ぶ計画が、写像では表せない。

$c$-巡回単調性と $c$-変換

最適な結合の台がもつ性質を定める。台 $\operatorname{supp}\pi$ は、$\pi$ 測度が $0$ の開集合の和の補集合で、閉集合である。

$c$-巡回単調

$c\colon X\times Y\to\mathbb{R}$ とする。集合 $\Gamma\subset X\times Y$ が $c$-巡回単調($c$-cyclically monotone)であるとは、$N\ge1$ と $(x_1,y_1),\dots,(x_N,y_N)\in\Gamma$ と $\{1,\dots,N\}$ の置換 $\sigma$ について
$$ \sum_{i=1}^Nc(x_i,y_i)\le\sum_{i=1}^Nc(x_i,y_{\sigma(i)}) $$
が成り立つことをいう。

$\Gamma$ の有限個の点の組で、行き先を入れ替えても費用は減らない、という条件である。置換は巡回置換の積に分かれ、点の重複も許しているので、巡回置換 $\sigma(i)=i+1$($y_{N+1}:=y_1$)についてだけ確かめれば十分である。Brenierの定理 の定義「巡回単調」は、$c(x,y)=\frac12\lvert x-y\rvert^2$ の場合にあたる。

$c$-変換と $c$-凹関数

$\varphi\colon X\to\mathbb{R}$ の $c$-変換 を
$$ \varphi^c(y):=\inf_{x\in X}\bigl(c(x,y)-\varphi(x)\bigr) $$
で定める。$Y$ の上の関数についても同様に $\psi^c(x):=\inf_{y\in Y}(c(x,y)-\psi(y))$ と定める。ある $\psi$ について $\varphi=\psi^c$ と書ける関数を $c$-凹関数 という。

定義から、すべての $x,y$ で $\varphi(x)+\varphi^c(y)\le c(x,y)$ であり、$\varphi^c$ はこの不等式を満たす $\psi$ の中で最大のものである。$c(x,y)=-x\cdot y$($X=Y=\mathbb{R}^n$)なら $-\varphi^c$ は $-\varphi$ の Legendre変換 で、$c$-凹関数は符号を変えると凸関数である(AG13 Remark 1.11、p. 8)。

Kantorovich の双対定理

この節では $X,Y$ をコンパクトな距離空間、$c\colon X\times Y\to\mathbb{R}$ を連続関数とし、$\|c\|:=\max\lvert c\rvert$ とおく。双対問題を
$$ D(\mu,\nu):=\sup\Bigl\{\int_X\varphi\,d\mu+\int_Y\psi\,d\nu\Bigm|\varphi\in C(X),\ \psi\in C(Y),\ \varphi(x)+\psi(y)\le c(x,y)\Bigr\} $$
とする。$\varphi(x),\psi(y)$ を積む値段と降ろす値段と読むと、$D$ は値段の合計が運送費を超えない条件の下での最大の収入である。

最適な結合の台は $c$-巡回単調である

$\pi\in\Pi(\mu,\nu)$ が Kantorovich の問題の最適な結合なら、$\operatorname{supp}\pi$ は $c$-巡回単調である。

質量を少しだけ入れ替える

要点:台の点の近傍から少しずつ質量を取り、行き先を置換で入れ替えた結合を作ると費用が下がる。

詳しい証明を開く

台が $c$-巡回単調でないとする。$(x_i,y_i)\in\operatorname{supp}\pi$($1\le i\le N$)と置換 $\sigma$ で $\sum_{i}(c(x_i,y_{\sigma(i)})-c(x_i,y_i))< 0$ となるものがある。$c$ は連続なので、$x_i$ の近傍 $U_i$ と $y_i$ の近傍 $V_i$ と $\eta>0$ があって、$u_i\in U_i$、$v_i\in V_i$ をどう選んでも $\sum_i(c(u_i,v_{\sigma(i)})-c(u_i,v_i))\le-\eta$ である。台の点なので $m_i:=\pi(U_i\times V_i)>0$ である。$\pi_i:=\frac1{m_i}\pi|_{U_i\times V_i}$ とおき、$(X\times Y)^N$ の上の積の確率測度 $P:=\pi_1\otimes\cdots\otimes\pi_N$ の座標を $(u_i,v_i)_{i}$ と書く。$m:=\min_im_i$ として、符号つき測度$$\alpha:=\frac mN\sum_{i=1}^N\Bigl((u_i,v_{\sigma(i)})_\#P-(u_i,v_i)_\#P\Bigr)$$を考える。

非負性。 $(u_i,v_i)_\#P=\pi_i\le\frac1{m_i}\pi$ なので、引く項の和は $\frac mN\sum_i\pi_i\le\pi$ 以下である。よって $\tilde\pi:=\pi+\alpha\ge0$ である。

周辺分布。 $\alpha$ の第 1 周辺分布は $\frac mN\sum_i\bigl((u_i)_\#P-(u_i)_\#P\bigr)=0$ である。第 2 周辺分布は $\frac mN\bigl(\sum_i(v_{\sigma(i)})_\#P-\sum_i(v_i)_\#P\bigr)$ で、$\sigma$ は置換なので 2 つの和は同じ項の並べ替えであり、$0$ である。よって $\tilde\pi\in\Pi(\mu,\nu)$ である。

費用。 $c$ は有界なので$$\int c\,d\tilde\pi-\int c\,d\pi=\frac mN\int\sum_{i=1}^N\bigl(c(u_i,v_{\sigma(i)})-c(u_i,v_i)\bigr)\,dP\le-\frac{m\eta}N< 0$$である。これは $\pi$ の最適性に反する。$\square$

Kantorovich の双対定理

$X,Y$ をコンパクトな距離空間、$c\colon X\times Y\to\mathbb{R}$ を連続関数、$\mu\in\mathcal{P}(X)$、$\nu\in\mathcal{P}(Y)$ とする。

  1. Kantorovich の問題には最適な結合がある。
  2. $\displaystyle\min_{\pi\in\Pi(\mu,\nu)}\int c\,d\pi=D(\mu,\nu)$ である。
  3. $D(\mu,\nu)$ の上限は、ある連続な $c$-凹関数 $\varphi$ と $\psi=\varphi^c$ の組で達成される。
  4. $\pi\in\Pi(\mu,\nu)$ について次は同値である。(a) $\pi$ は最適である。(b) $\operatorname{supp}\pi$ は $c$-巡回単調である。(c) 3 の組について、$\operatorname{supp}\pi$ の上で $\varphi(x)+\psi(y)=c(x,y)$ である。
台から値段を組み立てる

最適な結合の存在。 $X\times Y$ はコンパクトなので、Prokhorovの定理 によりその上の確率測度の全体は弱収束について点列コンパクトである。$\pi_k\in\Pi(\mu,\nu)$ が $\pi$ に弱収束すると、$f\in C(X)$ について $\int f(x)\,d\pi=\lim_k\int f(x)\,d\pi_k=\int f\,d\mu$ なので第 1 周辺分布は $\mu$ で、第 2 周辺分布も同様に $\nu$ である。よって $\Pi(\mu,\nu)$ は点列コンパクトで、$c$ は有界連続なので $\pi\mapsto\int c\,d\pi$ は連続である。最小値を達成する $\pi$ がある。
弱い不等式。 $\varphi(x)+\psi(y)\le c(x,y)$ で $\pi\in\Pi(\mu,\nu)$ なら
$$ \int\varphi\,d\mu+\int\psi\,d\nu=\int(\varphi(x)+\psi(y))\,d\pi(x,y)\le\int c\,d\pi $$
である。よって $D(\mu,\nu)\le\min\int c\,d\pi$ である。
$c$-巡回単調な集合から値段を作る。 $\Gamma\subset X\times Y$ を空でない $c$-巡回単調な集合とし、$(\bar x,\bar y)\in\Gamma$ を固定する。$N\ge0$ と $(x_1,y_1),\dots,(x_N,y_N)\in\Gamma$ の組(鎖)について
$$ V(x):=c(x,y_1)-c(x_1,y_1)+c(x_1,y_2)-c(x_2,y_2)+\cdots+c(x_N,\bar y)-c(\bar x,\bar y) $$
とおく($N=0$ なら $V(x)=c(x,\bar y)-c(\bar x,\bar y)$)。すべての鎖についての下限を $\varphi(x)$ とする。
(i) $\varphi(\bar x)=0$ である。$N=0$ の鎖から $\varphi(\bar x)\le0$ である。点 $(\bar x,\bar y),(x_1,y_1),\dots,(x_N,y_N)$ に def-ot-cyclic の巡回置換を当てると、どの鎖でも $V(\bar x)\ge0$ である。
(ii) $(\tilde x,\tilde y)\in\Gamma$ とすると、すべての $x$ で
$$ \varphi(x)\le c(x,\tilde y)-c(\tilde x,\tilde y)+\varphi(\tilde x)\qquad(*) $$
である。$\tilde x$ での鎖の先頭に $(\tilde x,\tilde y)$ を付け加えると、$x$ での鎖になるからである。
(iii) $\varphi$ は有界である。$N=0$ の鎖から $\varphi\le2\|c\|$ である。$N\ge1$ の鎖の値は、$V(x)=c(x,y_1)-c(x_1,y_1)+V'(x_1)$ と書ける。$V'$ は残りの鎖の値なので $V'(x_1)\ge\varphi(x_1)$ で、($*$) で $x=\bar x$ とおいて (i) を使うと $\varphi(x_1)\ge c(x_1,y_1)-c(\bar x,y_1)$ である。よって $V(x)\ge c(x,y_1)-c(\bar x,y_1)\ge-2\|c\|$ である。$N=0$ の鎖も同じ下界を満たす。
(iv) $\varphi$ は連続である。$c$ はコンパクト集合の上で一様連続なので、$d(x,x')\le\delta$ なら、すべての $y$ で $\lvert c(x,y)-c(x',y)\rvert\le\omega(\delta)$ となる $\omega(\delta)\to0$ がある。各鎖の値は $x\mapsto c(x,y_1)$ に定数を足したもので、$\lvert V(x)-V(x')\rvert\le\omega(\delta)$ である。有界な関数の族の下限なので、$\lvert\varphi(x)-\varphi(x')\rvert\le\omega(\delta)$ である。
(v) $\psi:=\varphi^c$ とおくと、$\psi$ は値が $[-3\|c\|,3\|c\|]$ に入り、(iv) と同じ理由で連続である。$\varphi(x)+\psi(y)\le c(x,y)$ はすべての点で成り立つ。$(\tilde x,\tilde y)\in\Gamma$ なら、($*$) を書き直すと、すべての $x$ で $c(x,\tilde y)-\varphi(x)\ge c(\tilde x,\tilde y)-\varphi(\tilde x)$ である。左辺の下限が $\psi(\tilde y)$ なので、$\psi(\tilde y)\ge c(\tilde x,\tilde y)-\varphi(\tilde x)$、すなわち
$$ \varphi(\tilde x)+\psi(\tilde y)=c(\tilde x,\tilde y)\qquad((\tilde x,\tilde y)\in\Gamma) $$
である。
(vi) 最後に $\varphi$ を $\tilde\varphi:=\psi^c$ に取り替える。$\varphi(x)\le c(x,y)-\psi(y)$ がすべての $y$ で成り立つので $\tilde\varphi\ge\varphi$ であり、$\tilde\varphi+\psi\le c$ と合わせて、$\Gamma$ の上で $\tilde\varphi(x)+\psi(y)=c(x,y)$ である。$\tilde\varphi$ は定義から $c$-凹関数で、(iv) と同じ理由で連続である。さらに $\tilde\varphi^c=\psi$ である。実際、$\tilde\varphi\ge\varphi$ から $\tilde\varphi^c\le\varphi^c=\psi$ であり、逆に $\tilde\varphi(x)+\psi(y)\le c(x,y)$ から $\psi\le\tilde\varphi^c$ である。以下、$\tilde\varphi$ を改めて $\varphi$ と書く。
等号と達成。 1 の最適な結合 $\pi$ をとる。lem-ot-support により $\Gamma:=\operatorname{supp}\pi$ は $c$-巡回単調である。$\pi(\Gamma)=1$ なので、上の $\varphi,\psi$ について
$$ \int c\,d\pi=\int_\Gamma(\varphi(x)+\psi(y))\,d\pi=\int\varphi\,d\mu+\int\psi\,d\nu\le D(\mu,\nu) $$
である。弱い不等式と合わせて 2 と 3 を得る。
最適性の判定。 (a) ⇒ (b) は lem-ot-support である。(b) ⇒ (a):$\operatorname{supp}\pi$ から上のとおり $\varphi,\psi$ を作ると、上の式から $\int c\,d\pi=\int\varphi\,d\mu+\int\psi\,d\nu$ で、弱い不等式から任意の $\pi'\in\Pi(\mu,\nu)$ について $\int c\,d\pi\le\int c\,d\pi'$ である。(a) ⇒ (c):最適な組 $(\varphi,\psi)$ と最適な $\pi$ について $\int(c-\varphi-\psi)\,d\pi=0$ で、被積分関数は非負の連続関数なので、台の上で $0$ である。(c) ⇒ (a):同じ式から $\int c\,d\pi=D(\mu,\nu)$ で、弱い不等式から最適である。$\square$

完備可分な $X,Y$ でも、$c$ が連続で下に有界で、可積分な $a,b$ について $c(x,y)\le a(x)+b(y)$ なら、4 の同値と双対の等式が成り立つ(AG13 Theorem 1.13、p. 9、Theorem 1.17、p. 13。鎖の値の作り方は p. 10 の証明による)。
有限個の点の場合、thm-ot-duality は 輸送問題 の定理「輸送問題の双対定理」に一致する。(c) は線形計画法の相補性条件で、正の量を運ぶ道では値段の合計が運送費にちょうど等しい。

実数直線の上の最適輸送

$X=Y=\mathbb{R}$ とし、$\mu,\nu$ の分布関数を $F,G$、その一般化逆関数を
$$ F^{-1}(t):=\inf\{x\in\mathbb{R}\mid F(x)\ge t\}\qquad(0< t< 1) $$
とする。$U$ が $(0,1)$ の一様分布に従えば $F^{-1}(U)$ の分布は $\mu$ である($F^{-1}(t)\le x\iff t\le F(x)$ による)。$(0,1)$ の上の Lebesgue 測度 $\lambda$ の押し出し
$$ \pi_{\mathrm{mon}}:=(F^{-1},G^{-1})_\#\lambda $$
を 単調な結合 という。$\mu$ の下から $t$ の割合の位置にある質量を、$\nu$ の下から $t$ の割合の位置へ運ぶ計画である。
集合 $\Gamma\subset\mathbb{R}^2$ が 単調 であるとは、$(x_1,y_1),(x_2,y_2)\in\Gamma$ で $x_1< x_2$ なら $y_1\le y_2$ であることをいう。$F^{-1},G^{-1}$ は単調非減少なので、$\{(F^{-1}(t),G^{-1}(t))\}$ は単調で、単調な集合の閉包も単調である。よって $\operatorname{supp}\pi_{\mathrm{mon}}$ は単調である。

四辺形の不等式

$h\colon\mathbb{R}\to\mathbb{R}$ を凸関数、$c(x,y):=h(x-y)$ とする。$x_1\le x_2$、$y_1\le y_2$ なら
$$ c(x_1,y_1)+c(x_2,y_2)\le c(x_1,y_2)+c(x_2,y_1) $$
である。

両端の値で抑える

要点:4 つの差は和が等しく、左辺の 2 つは右辺の 2 つの間にある。

詳しい証明を開く

$a:=x_1-y_2$、$b:=x_2-y_1$、$s:=x_1-y_1$、$t:=x_2-y_2$ とおくと、$a\le s,t\le b$ で $s+t=a+b$ である。$a=b$ なら 4 つは等しい。$a< b$ なら $s=\theta a+(1-\theta)b$ と書くと $t=(1-\theta)a+\theta b$($\theta\in[0,1]$)で、凸性から $h(s)+h(t)\le h(a)+h(b)$ である。$\square$

単調な集合は $c$-巡回単調である

$h$ を凸関数、$c(x,y)=h(x-y)$ とする。単調な集合 $\Gamma\subset\mathbb{R}^2$ は $c$-巡回単調である。

転倒を 1 つずつ解消する

要点:点を順に並べ、置換の転倒を隣どうしの入れ替えで解消するたびに、lem-ot-quadrangle で費用が増えない。

詳しい証明を開く

$(x_i,y_i)\in\Gamma$($1\le i\le N$)を $(x_i,y_i)$ の辞書式順序で並べる。単調性から、$x_1\le\cdots\le x_N$ かつ $y_1\le\cdots\le y_N$ である($x_i=x_j$ の組は $y$ の順に並べてある)。置換 $\sigma$ に対し $C(\sigma):=\sum_ic(x_i,y_{\sigma(i)})$ とおく。$\sigma$ が恒等置換でなければ、隣り合う位置 $i$ と $j:=i+1$ で $\sigma(i)>\sigma(j)$ となるもの(転倒)がある。$\sigma(i)$ と $\sigma(j)$ を入れ替えた置換を $\sigma'$ とすると、$x_i\le x_j$、$y_{\sigma(j)}\le y_{\sigma(i)}$ なので、lem-ot-quadrangle から$$c(x_i,y_{\sigma(j)})+c(x_j,y_{\sigma(i)})\le c(x_i,y_{\sigma(i)})+c(x_j,y_{\sigma(j)})$$で、$C(\sigma')\le C(\sigma)$ である。$\sigma'$ の転倒の数は $\sigma$ より 1 少ない。繰り返すと恒等置換に達し、$\sum_ic(x_i,y_i)\le C(\sigma)$ を得る。$\square$

1 次元の最適輸送

$p\ge1$、$\mu,\nu\in\mathcal{P}(\mathbb{R})$ とし、$p$ 次モーメントが有限であるとする。費用 $c(x,y)=\lvert x-y\rvert^p$ について、単調な結合 $\pi_{\mathrm{mon}}$ は最適で、
$$ \min_{\pi\in\Pi(\mu,\nu)}\int\lvert x-y\rvert^p\,d\pi=\int_0^1\bigl\lvert F^{-1}(t)-G^{-1}(t)\bigr\rvert^p\,dt $$
である。

単調な台は最適性の判定を満たす

$\pi_{\mathrm{mon}}\in\Pi(\mu,\nu)$ であることは上で見た。右辺は $\pi_{\mathrm{mon}}$ の費用で、押し出しの定義から $\int c\,d\pi_{\mathrm{mon}}=\int_0^1c(F^{-1}(t),G^{-1}(t))\,dt$ である。$h(z)=\lvert z\rvert^p$ は凸なので、prop-ot-monotone により $\operatorname{supp}\pi_{\mathrm{mon}}$ は $c$-巡回単調である。
台が有界な場合。 $\mu,\nu$ が $[-R,R]$ に台をもつなら、$X=Y=[-R,R]$ はコンパクトで $c$ は連続なので、thm-ot-duality の 4 の (b) ⇒ (a) から $\pi_{\mathrm{mon}}$ は最適である。
一般の場合。 $c$ は連続で非負であり、$\lvert x-y\rvert^p\le2^{p-1}(\lvert x\rvert^p+\lvert y\rvert^p)$ なので $a(x)=2^{p-1}\lvert x\rvert^p\in L^1(\mu)$、$b(y)=2^{p-1}\lvert y\rvert^p\in L^1(\nu)$ について $c\le a+b$ である。この仮定の下で、台が $c$-巡回単調な結合は最適である(AG13 Theorem 1.13 の (ii) ⇒ (i)、p. 9)。$\square$

$p=1$ のとき、右辺は $\int_{\mathbb{R}}\lvert F(x)-G(x)\rvert\,dx$ に等しい(グラフ $t=F(x)$ と $t=G(x)$ の間の面積を、縦と横の 2 通りに測る)。これは Wasserstein距離 の命題「実数直線の $W_1$」の式である。thm-ot-line の証明は $h$ の凸性だけを使うので、凸な $h$ による費用 $h(x-y)$ でも、台が有界なら単調な結合は最適である。

正規分布の間の輸送

$\mu=N(m_1,s_1^2)$、$\nu=N(m_2,s_2^2)$($s_1>0$)とすると、$G^{-1}(t)=m_2+\frac{s_2}{s_1}(F^{-1}(t)-m_1)$ なので、単調な結合は写像 $T(x)=m_2+\frac{s_2}{s_1}(x-m_1)$ で与えられる。$p=2$ では
$$ \int\lvert x-T(x)\rvert^2\,d\mu=E\Bigl[\bigl(m_1-m_2+(s_1-s_2)Z\bigr)^2\Bigr]=(m_1-m_2)^2+(s_1-s_2)^2 $$
である($Z$ は標準正規分布に従う)。Wasserstein距離 の命題「正規分布どうしの $W_2$」と一致する。

Brenier の定理と Monge の問題

ex-ot-nomap のように、Kantorovich の問題の解が写像で与えられるとは限らない。$\mathbb{R}^n$ の 2 乗の費用では、出発の測度に原子がないだけでなく Lebesgue 測度に絶対連続であれば、解は写像で与えられる。

Brenier の定理(主張)

$\mu,\nu$ を $\mathbb{R}^n$ の上の 2 次モーメントが有限な確率測度とし、$\mu$ は Lebesgue 測度に絶対連続とする。費用 $c(x,y)=\lvert x-y\rvert^2$ の Kantorovich の問題の最適な結合はただ 1 つで、ある凸関数 $\Phi$ について $(\mathrm{id},\nabla\Phi)_\#\mu$ の形をしている。特に $T=\nabla\Phi$ は Monge の問題の解である。

証明の所在と双対定理との関係

証明は Brenierの定理 の定理「Brenier の定理」にある(AG13 Theorem 1.26、p. 16)。2 乗の費用は $\lvert x-y\rvert^2=\lvert x\rvert^2+\lvert y\rvert^2-2x\cdot y$ と分かれるので、thm-ot-duality の $c$-凹関数は、$\lvert x\rvert^2$ から凸関数を引いたものになる。(c) の接触集合は凸関数の劣微分のグラフで、$\mu$ が絶対連続なら凸関数はほとんどいたるところ微分可能なので、劣微分は 1 点になる。

例

2 点から 2 点への輸送と値段

$\mu=\frac12(\delta_0+\delta_1)$、$\nu=\frac12(\delta_1+\delta_3)$、$c(x,y)=\lvert x-y\rvert^2$ とする。結合は $\pi(\{(0,1)\})=\pi(\{(1,3)\})=s$、$\pi(\{(0,3)\})=\pi(\{(1,1)\})=\frac12-s$($0\le s\le\frac12$)の形で、費用は
$$ s(1+4)+\Bigl(\frac12-s\Bigr)(9+0)=\frac92-4s $$
である。$s=\frac12$ の単調な結合が最適で、最小値は $\frac52$ である。値段 $\varphi(0)=0$、$\varphi(1)=-1$、$\psi(1)=1$、$\psi(3)=5$ は
$$ \varphi(0)+\psi(1)=1,\quad\varphi(1)+\psi(3)=4,\quad\varphi(0)+\psi(3)=5\le9,\quad\varphi(1)+\psi(1)=0\le0 $$
を満たし、収入は $\frac12(0-1)+\frac12(1+5)=\frac52$ で最小の費用に等しい。運ぶ道 $(0,1)$ と $(1,3)$ では等号が成り立っている。$\varphi(1)+\psi(1)=c(1,1)$ も等号だが、最適解はそこを運ばない。(c) は運ぶ道の等号だけを要求する。

費用の指数で解が変わる

$\mu$ を $[0,1]$ の一様分布、$\nu$ を $[1,2]$ の一様分布とし、平行移動 $T_1(x)=x+1$ と折り返し $T_2(x)=2-x$ を比べる。どちらも $\mu$ を $\nu$ に押し出す。

  • $p=1$:$\int_0^1\lvert T_1(x)-x\rvert\,dx=1$、$\int_0^1\lvert2-2x\rvert\,dx=1$ で、thm-ot-line の値 $\int_0^1\lvert t-(1+t)\rvert\,dt=1$ と等しい。2 つとも最適で、最適な結合は一意でない。
  • $p=2$:$\int_0^1 1\,dx=1$ に対し $\int_0^1(2-2x)^2\,dx=\frac43$ である。最適なのは単調な $T_1$ だけである(thm-ot-brenier)。
    $p=1$ では質量はすべて右へ動くので、どの結合でも費用は $\int y\,d\nu-\int x\,d\mu=1$ である。

反例:条件を外すと成り立たないこと

各行は、その主張の仮定を 1 つだけ外す。

主張外す仮定反例成り立たなくなること
$c$ が連続なら Monge の問題の下限は Kantorovich の問題の最小値に等しい(AG13 p. 6 の (1.2))$\mu$ に原子がない$\mu=\delta_0$、$\nu=\frac12(\delta_{-1}+\delta_1)$輸送写像が 1 つもなく、Monge の問題の下限は $+\infty$ である
thm-ot-brenier の写像の存在$\mu$ の絶対連続性($\mu$ に原子はない)$\mathbb{R}^2$、$\mu$ は線分 $[0,1]\times\{0\}$ の一様分布、$\nu$ は線分 $[0,1]\times\{1\}$ と $[0,1]\times\{-1\}$ の一様分布の半分ずつKantorovich の最小値 $1$ は達成されるが、Monge の問題の下限 $1$ は達成されない
最適な結合の存在$c$ の下半連続性$X=Y=[0,1]$、$\mu=\nu$ は一様分布、$c(x,y)=\lvert x-y\rvert$($x\ne y$)、$c(x,x)=1$下限 $0$ が達成されない
thm-ot-line の後の注意(凸な $h$ の費用 $h(x-y)$、台が有界)の単調な結合の最適性$h$ の凸性$h(z)=\sqrt{\lvert z\rvert}$、$\mu=\frac12(\delta_0+\delta_1)$、$\nu=\frac12(\delta_1+\delta_2)$単調な結合の費用 $1$ が、交差する結合の費用 $\frac{\sqrt2}2$ より大きい
thm-ot-brenier の一意性費用が 2 乗(狭義凸)$p=1$、ex-ot-uniform最適な結合が 2 つ以上ある
反例の確かめ

2 行目。 要点:結合なら費用 $1$ にできるが、写像は各点の質量を分けられないので、費用 $1$ の写像では密度が合わない。

確かめを開く

$\nu$ の台の点と $\mu$ の台の点の距離は $1$ 以上なので、どの結合の費用も $1$ 以上である。各点 $(t,0)$ の質量を $(t,1)$ と $(t,-1)$ へ半分ずつ運ぶ結合の費用は $1$ である。$[0,1]$ を長さ $\frac1n$ の $n$ 個の区間 $I_k$ に分け、$I_k$ の左半分を 2 倍に引き伸ばして $I_k\times\{1\}$ へ、右半分を $I_k\times\{-1\}$ へ運ぶ写像 $T_n$ は輸送写像で、横の移動は $\frac1n$ 以下なので費用は $1+\frac1{n^2}$ 以下である。よって Monge の問題の下限は $1$ である。費用がちょうど $1$ の輸送写像 $T$ があれば、ほとんどすべての $t$ で横の移動が $0$ なので $T(t,0)=(t,s(t))$、$s(t)\in\{\pm1\}$ である。このとき $T_\#\mu$ の $[0,1]\times\{1\}$ の部分は、集合 $\{s=1\}$ の上の Lebesgue 測度の像で、密度は $0$ か $1$ であり、密度 $\frac12$ の $\nu$ の部分と一致しない。


3 行目。 $c>0$ なので、どの結合の費用も正である。
確かめを開く

$y=x+\varepsilon\pmod 1$ の結合の費用は $2\varepsilon(1-\varepsilon)$ で、$0$ に近づく。費用 $0$ の結合は存在しない。


4 行目。 凹な $h$ では lem-ot-quadrangle の不等式が逆向きになる。
確かめを開く

単調な結合 $0\mapsto1$、$1\mapsto2$ の費用は $\frac12(1+1)=1$、交差する結合 $0\mapsto2$、$1\mapsto1$ の費用は $\frac12(\sqrt2+0)=\frac{\sqrt2}2\approx0.707$ である。$h$ は原点の両側で凹である。

歴史と出典

Monge は 1781 年の論文「切り土と盛り土の理論」で、$\mathbb{R}^d$ の距離 $c(x,y)=\lvert x-y\rvert$ を費用とする写像の問題を立てた。Kantorovich は 1940 年の論文で結合の問題を、1942 年の論文で双対問題を導入した。$c$-巡回単調性と $c$-凹関数の理論は Rüschendorf らにより、2 乗の費用の最適な写像の特徴づけは Brenier(1987、1991)による(AG13 §1.5、pp. 22–23)。

出典

問題の定式化は AG13 Problem 1.1・1.2(p. 4)、$c$-巡回単調性と $c$-変換は Definition 1.7–1.9(p. 7)、基本定理と双対定理は Theorem 1.13(p. 9)・Theorem 1.17(p. 13)、Brenier の定理は Theorem 1.26(p. 16)にある。thm-ot-duality の証明はコンパクトな場合に AG13 の議論を有界連続な関数で書き直したもので、prop-ot-monotone の転倒を解消する証明と thm-ot-line の組み立てはこの記事による。

関連項目

参考文献

[1]
Luigi Ambrosio, Nicola Gigli, A user's guide to optimal transport, Modelling and Optimisation of Flows on Networks (B. Piccoli, M. Rascle eds.), Lecture Notes in Mathematics 2062, pp. 1–155, Springer, 2013, Problem 1.1・1.2(p. 4)、Theorem 1.5(p. 5)、(1.2)(p. 6)、Definition 1.7–1.9(p. 7)、Remark 1.11(p. 8)、Theorem 1.13(pp. 9–10)、Theorem 1.17(p. 13)、Theorem 1.26(p. 16)、§1.5(pp. 22–23)。番号・頁は cvgmt の著者稿による

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する