ワッサーシュタイン計量法

数学において、ワッセルシュタイン距離またはカントロヴィッチ-ルビンシュタイン距離は、与えられた距離空間上の確率分布間で定義される距離関数です。レオニード・ヴァセルシュタインにちなんで名付けられました。 ${\displaystyle M}$

直感的には、各分布を に積まれた土の単位量と見なすと、メトリックは 1 つの山を別の山に変える最小の「コスト」であり、移動する必要がある土の量に、移動する必要がある平均距離を掛けたものと想定されます。この問題は、 1781 年にガスパール モンジュによって初めて形式化されました。この類似性のため、メトリックはコンピューター サイエンスではアース ムーバーの距離として知られています。 ${\displaystyle M}$

「ワッサーシュタイン距離」という名前は、1970年にRLドブルシンが、マルコフ過程による大規模オートマトンシステムに関するレオニード・ヴァセルシュテインの研究^[1] (ロシア語、1969) でこの名前を知った後に作ったものです。しかし、このメトリックは、商品や材料の最適輸送計画の文脈で、レオニード・カントロヴィッチが「生産計画と組織の数学的方法」^[2] (ロシア語原文 1939)で初めて定義しました。そのため、一部の学者は「カントロヴィッチ メトリック」や「カントロヴィッチ距離」という用語の使用を推奨しています。ほとんどの英語の出版物では、ドイツ語の綴り「ワッサーシュタイン」が使用されています(「ヴァッサーシュタイン」(ロシア語: Васерштейн )という名前がイディッシュ語に由来するため)。

をポーランド空間である計量空間とします。に対して、 上の 2 つの確率測度との間の有限-モーメントを持つWasserstein -距離は、 となります 。 ここで、 はとのすべてのカップリングの集合です。はと定義され、最大ノルムに対応します。ここで、カップリングは上の結合確率測度であり、その周辺係数はそれぞれ第 1 因子と第 2 因子で、です。これは、すべての測定可能な に対して、 および が 満たされることを意味します。 ${\displaystyle (M,d)}$${\displaystyle p\in [1,+\infty ]}$${\displaystyle p}$ ${\displaystyle \mu}$${\displaystyle \nu}$${\displaystyle M}$${\displaystyle p}$${\displaystyle W_{p}(\mu ,\nu )=\inf _{\gamma \in \Gamma (\mu ,\nu )}\left(\mathbf {E} _{(x,y)\sim \gamma }d(x,y)^{p}\right)^{1/p},}$${\displaystyle \Gamma (\mu ,\nu )}$${\displaystyle \mu}$${\displaystyle \nu}$${\displaystyle W_{\infty }(\mu ,\nu )}$${\displaystyle \lim _{p\rightarrow +\infty }W_{p}(\mu ,\nu )}$${\displaystyle \gamma}$${\displaystyle M\times M}$${\displaystyle \mu}$${\displaystyle \nu}$${\displaystyle A\subset M}$${\displaystyle \gamma (A\times M)=\mu (A)}$${\displaystyle \gamma (M\times A)=\nu (A)}$

上記の定義を理解する一つの方法は、最適輸送問題を考えることです。つまり、空間 上の質量分布について、質量を同じ空間上の分布に変換されるように輸送したいのです。つまり、「土の山」を山 に変換します。この問題は、作成される山が移動する山と同じ質量を持つ場合にのみ意味を持ちます。したがって、一般性を失うことなく、およびが合計質量 1 を含む確率分布であると仮定します。また、何らかのコスト関数が与えられていると仮定します。 ${\displaystyle \mu (x)}$${\displaystyle X}$${\displaystyle \nu (x)}$${\displaystyle \mu}$${\displaystyle \nu}$${\displaystyle \mu}$${\displaystyle \nu}$

$${\displaystyle c(x,y)\geq 0}$$

は、単位質量を点から点 に輸送するコストを与えます。に移動する輸送計画は、からに移動する質量の量を与える関数によって記述できます。 このタスクは、形状 の土の山を形状 の地面の穴に移動し、最後に土の山と地面の穴の両方が完全に消えるようにする必要があると想像できます。 この計画が意味を持つためには、次の特性を満たす必要があります。 ${\displaystyle x}$${\displaystyle y}$${\displaystyle \mu}$${\displaystyle \nu}$${\displaystyle \gamma (x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle \mu}$${\displaystyle \nu}$

1. 地点から移動した土の量は、最初にそこにあった土の量と等しくなければならない。つまり 、${\displaystyle x}$$${\displaystyle \int \gamma (x,y)\,\mathrm {d} y=\mu (x),}$$
2. ポイントに移動される土の量は、最初にあった穴の深さと同じでなければなりません。つまり、 ${\displaystyle y}$$${\displaystyle \int \gamma (x,y)\,\mathrm {d} x=\nu (y).}$$

つまり、の周りの微小領域から移動した全質量はに等しく、の周りの領域に移動する全質量は でなければならないということです。これは、 が周辺およびを持つ結合確率分布であるという要件に相当します。したがって、からに輸送される微小質量は であり、移動コストは であり、これはコスト関数の定義に従います。したがって、輸送計画の総コストは ${\displaystyle x}$${\displaystyle \mu (x)\mathrm {d} x}$${\displaystyle y}$${\displaystyle \nu (y)\mathrm {d} y}$${\displaystyle \gamma}$${\displaystyle \mu}$${\displaystyle \nu}$${\displaystyle x}$${\displaystyle y}$${\displaystyle \gamma (x,y)\,\mathrm {d} x\,\mathrm {d} y}$${\displaystyle c(x,y)\gamma (x,y)\,\mathrm {d} x\,\mathrm {d} y}$${\displaystyle \gamma}$$${\displaystyle \iint c(x,y)\gamma (x,y)\,\mathrm {d} x\,\mathrm {d} y=\int c(x,y)\,\mathrm {d} \ガンマ(x,y)。}$$

計画は一意ではありません。最適な輸送計画とは、考えられるすべての輸送計画の中でコストが最小となる計画です。前述のように、計画が有効であるための要件は、限界分布と を伴う結合分布であることです。最初のセクションと同様に、 がそのようなすべての尺度の集合を表すとすると、最適計画のコストは です。 移動のコストが 2 点間の距離だけである場合、最適コストは距離の定義と同じです。 ${\displaystyle \gamma}$${\displaystyle \mu}$${\displaystyle \nu}$${\displaystyle \ガンマ}$$${\displaystyle C=\inf _{\gamma \in \Gamma (\mu ,\nu )}\int c(x,y)\,\mathrm {d} \gamma (x,y).}$$${\displaystyle W_{1}}$

と を、内の点とにある2 つの退化した分布(つまり、ディラックのデルタ分布)とします。これら 2 つの測度を結合できるのは、にある質点だけです。したがって、上の距離関数として通常の絶対値関数を使用すると、任意の に対して、と間の -ワッサースタイン距離は次のようになります。 同様の理由から、と が内の点とにある質点である場合、 上の通常のユークリッドノルムを距離関数として使用すると、次のように なります。${\displaystyle \mu _{1}=\delta _{a_{1}}}$${\displaystyle \mu _{2}=\delta _{a_{2}}}$${\displaystyle a_{1}}$${\displaystyle a_{2}}$${\displaystyle \mathbb {R} }$${\displaystyle \delta _{(a_{1},a_{2})}}$${\displaystyle (a_{1},a_{2})\in \mathbb {R} ^{2}}$${\displaystyle \mathbb {R} }$${\displaystyle p\geq 1}$${\displaystyle p}$${\displaystyle \mu_{1}}$${\displaystyle \mu_{2}}$$${\displaystyle W_{p}(\mu _{1},\mu _{2})=|a_{1}-a_{2}|.}$$${\displaystyle \mu _{1}=\delta _{a_{1}}}$${\displaystyle \mu _{2}=\delta _{a_{2}}}$${\displaystyle a_{1}}$${\displaystyle a_{2}}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle \mathbb {R} ^{n}}$$${\displaystyle W_{p}(\mu _{1},\mu _{2})=\|a_{1}-a_{2}\|_{2}。}$$

がサンプルを持つ経験的測度であり、がサンプルを持つ経験的測度である場合、距離は順序統計量の単純な関数です。 ${\displaystyle P}$${\displaystyle X_{1},\ldots ,X_{n}}$${\displaystyle Q}$${\displaystyle Y_{1},\ldots ,Y_{n}}$$${\displaystyle W_{p}(P,Q)=\left({\frac {1}{n}}\sum _{i=1}^{n}\|X_{(i)}-Y_{(i)}\|^{p}\right)^{1/p}.}$$

とがそれぞれ観測に基づく経験分布である場合、 ${\displaystyle P}$${\displaystyle Q}$${\displaystyle n}$

$${\displaystyle W_{p}(P,Q)=\inf _{\pi }\left({\frac {1}{n}}\sum _{i=1}^{n}\|X_{i}-Y_{\pi (i)}\|^{p}\right)^{1/p},}$$

ここで、最小値はすべての要素の順列にわたっています。これは線形割り当て問題であり、ハンガリーアルゴリズムによって3 次時間で解くことができます。 ${\displaystyle \pi}$${\displaystyle n}$

および を上の2つの非退化ガウス測度（すなわち正規分布）とし、それぞれの期待値およびと対称な半正定値共分散行列および とします。すると、^[3]上の通常のユークリッドノルムに関して、 と 間の2-ワッサーシュタイン距離はとなり 、 ここで はの主平方根を表します。第2項（トレースを含む）は、まさに と 間の（正規化されていない）ビュレス計量であることに注意してください。この結果は、2つの質点間のワッサーシュタイン距離の以前の例（少なくとも の場合）を一般化したものです。質点は共分散行列がゼロである正規分布と見なすことができ、その場合トレースの項は消えて、平均間のユークリッド距離を含む項のみが残るからです。 ${\displaystyle \mu_{1}={\mathcal{N}}(m_{1},C_{1})}$${\displaystyle \mu_{2}={\mathcal{N}}(m_{2},C_{2})}$${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle m_{1}}$${\displaystyle m_{2}\in \mathbb {R} ^{n}}$ ${\displaystyle C_{1}}$${\displaystyle C_{2}\in \mathbb {R} ^{n\times n}}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle \mu_{1}}$${\displaystyle \mu_{2}}$$${\displaystyle W_{2}(\mu _{1},\mu _{2})^{2}=\|m_{1}-m_{2}\|_{2}^{2}+\mathop {\mathrm {trace} } {\bigl (}C_{1}+C_{2}-2{\bigl (}C_{2}^{1/2}C_{1}C_{2}^{1/2}{\bigr )}^{1/2}{\bigr )}.}$$${\displaystyle C^{1/2}}$${\displaystyle C}$${\displaystyle C_{1}}$${\displaystyle C_{2}}$${\displaystyle p=2}$

を 上の確率測度とし、その累積分布関数をおよび で表すとします。このとき、輸送問題には解析解があります。最適輸送は確率質量要素の順序を保存するため、 の分位点における質量はの分位点に移動します。したがって、と の間の -ワッサースタイン距離は であり 、 およびは分位関数（逆 CDF）です。 の場合、変数の変更により式^{[4]が得られます。}${\displaystyle \mu _{1},\mu _{2}\in P_{p}(\mathbb {R} )}$${\displaystyle \mathbb {R} }$${\displaystyle F_{1}(x)}$${\displaystyle F_{2}(x)}$${\displaystyle q}$${\displaystyle \mu _{1}}$${\displaystyle q}$${\displaystyle \mu _{2}}$${\displaystyle p}$${\displaystyle \mu _{1}}$${\displaystyle \mu _{2}}$$${\displaystyle W_{p}(\mu _{1},\mu _{2})=\left(\int _{0}^{1}\left|F_{1}^{-1}(q)-F_{2}^{-1}(q)\right|^{p}\,\mathrm {d} q\right)^{1/p},}$$${\displaystyle F_{1}^{-1}}$${\displaystyle F_{2}^{-1}}$${\displaystyle p=1}$ $${\displaystyle W_{1}(\mu _{1},\mu _{2})=\int _{\mathbb {R} }\left|F_{1}(x)-F_{2}(x)\right|\,\mathrm {d} x.}$$

ワッサーシュタイン計量は、2 つの変数XとYの確率分布を比較する自然な方法です。ここで、一方の変数は、小さな非均一な摂動 (ランダムまたは決定論的) によって他方の変数から派生します。

たとえば、コンピュータ サイエンスでは、メトリックW _{1 は、2 つの}デジタル画像のカラーヒストグラムなどの離散分布を比較するために広く使用されています。詳細については、 earth mover's distance を参照してください。

Arjovskyら^[5]は、論文「Wasserstein GAN 」で、生成的敵対ネットワーク（GAN）の元のフレームワークを改良し、勾配消失とモード崩壊の問題を軽減する方法としてWasserstein-1メトリックを使用しています。正規分布の特殊なケースは、Frechet開始距離で使用されます。

ワッサーシュタイン計量はプロクルステス解析と形式的に関連しており、キラリティー測度^[6]や形状解析^{[7]に応用されている。}

計算生物学では、ワッサースタインメトリックは、サイトメトリーデータセットの持続図を比較するために使用できます。^[8]

ワッサーシュタイン計量は地球物理学の逆問題にも使われてきた。^[9]

ワッサーシュタイン計量は統合情報理論において概念と概念構造の差を計算するために使用されます。^[10]

ワッサーシュタイン計量と関連する定式化は、高エネルギー物理学や衝突型加速器物理学のデータセットにおける形状観測解析のための統一理論を提供するためにも使用されている。^{[11] [12]}

W _{p は、}有限のp次モーメントを持つM上のすべてのボレル確率測度からなるワッサーシュタイン空間P _p ( M ) 上の計量の公理をすべて満たすことを示すことができる。さらに、 W _pに関する収束は、測度の通常の弱収束と最初のp次モーメントの収束を加えたものと同等である。^[13]

W ₁の次の双対表現は、 KantorovichとRubinstein (1958)の双対定理の特別な場合である。μとνが有界台を持つとき、

$${\displaystyle W_{1}(\mu ,\nu )=\sup \left\{\left.\int _{M}f(x)\,\mathrm {d} (\mu -\nu )(x)\,\right|{\text{ continuous }}f:M\to \mathbb {R} ,\operatorname {Lip} (f)\leq 1\right\},}$$

ここで、Lip( f )はfの最小リプシッツ定数を表します。この形式は、W _1が積分確率計量であることを示しています。

これをラドン測定の定義と比較してみましょう。

$${\displaystyle \rho (\mu ,\nu ):=\sup \left\{\left.\int _{M}f(x)\,\mathrm {d} (\mu -\nu )(x)\,\right|{\text{ continuous }}f:M\to [-1,1]\right\}.}$$

距離空間（M、d ）の距離dが定数Cで制限されている場合、

$${\displaystyle 2W_{1}(\mu ,\nu )\leq C\rho (\mu ,\nu ),}$$

そして、ラドン計量の収束（Mがポーランド空間の場合の全変分収束と同じ）はワッサーシュタイン計量の収束を意味しますが、その逆は当てはまりません。

以下は技術的な点を省略した直感的な証明である。厳密な証明は^{[14]に記載されている。}

離散的なケース:が離散的な場合、1-ワッサーシュタイン距離を解くことは線形計画法の問題です。 ここで、は一般的な「コスト関数」です。 ${\displaystyle M}$$${\displaystyle {\begin{cases}\min _{\gamma }\sum _{x,y}c(x,y)\gamma (x,y)\\\sum _{y}\gamma (x,y)=\mu (x)\\\sum _{x}\gamma (x,y)=\nu (y)\\\gamma \geq 0\end{cases}}}$$${\displaystyle c:M\times M\to [0,\infty )}$

上記の方程式を注意深く行列方程式として書き表すと、その双対問題が得られます。^[15] 線型計画法の双対性定理 により、主問題は実行可能かつ有界であるため、双対問題も実行可能かつ有界であり、最初の問題の最小値は2番目の問題の最大値に等しくなります。つまり、問題のペアは強い双対性を示しています。 $${\displaystyle {\begin{cases}\max _{f,g}\sum _{x}\mu (x)f(x)+\sum _{y}\nu (y)g(y)\\f(x)+g(y)\leq c(x,y)\end{cases}}}$$

一般の場合、双対問題は和を積分に変換することで見つかる。 そして強い双対性は依然として成り立つ。これがカントロヴィッチの双対性定理である。セドリック・ヴィラニはルイス・カファレッリによる次の解釈を述べている。^[16]$${\displaystyle {\begin{cases}\sup _{f,g}\mathbb {E} _{x\sim \mu }[f(x)]+\mathbb {E} _{y\sim \nu }[g(y)]\\f(x)+g(y)\leq c(x,y)\end{cases}}}$$

として分布している鉱山から、 として分布している工場に石炭を輸送するとします。輸送の費用関数は です。ここで、荷送人がやって来て、輸送を申し出ます。 で石炭を積み込むのに石炭 1 個当たり支払い、 で石炭を降ろすのに石炭 1 個当たり支払います。 ${\displaystyle \mu }$${\displaystyle \nu }$${\displaystyle c}$${\displaystyle f(x)}$${\displaystyle x}$${\displaystyle g(y)}$${\displaystyle y}$

取引を承諾するには、価格表が を満たす必要があります。 カントロビッチの双対性によれば、荷送人は、荷送人が自分で発送する場合とほぼ同じ金額を支払うような価格表を作成できることになります。${\displaystyle f(x)+g(y)\leq c(x,y)}$

この結果をさらに推し進めると次のようになります。

確率空間が のとき、2 つの最小畳み込みステップは視覚的に明らかです。 ${\displaystyle \mathbb {R} }$

表記の便宜上、最小畳み込み演算を で表します。 ${\displaystyle \square }$

最初のステップでは、 を使用し、 の曲線をプロットし、各点で傾き 1 の円錐を描き、図に示すように円錐の下側のエンベロープを とすると、 は傾きが 1 より大きい場合に増加することはできません。したがって、そのすべての割線の傾きは になります。 ${\displaystyle f={\text{cone}}\mathbin {\square } (-g)}$${\displaystyle -g}$${\displaystyle f}$${\displaystyle f}$${\displaystyle {\bigg |}{\frac {f(x)-f(y)}{x-y}}{\bigg |}\leq 1}$

2 番目のステップでは、内接畳み込み を描きます。 のすべての正割の傾きが最大でも 1 であれば、 の下側のエンベロープは円錐の頂点そのものになります。したがって となります。 ${\displaystyle {\text{cone}}\mathbin {\square } (-f)}$${\displaystyle f}$${\displaystyle {\text{cone}}\mathbin {\square } (-f)}$${\displaystyle {\text{cone}}\mathbin {\square } (-f)=-f}$

1Dの例。両方が 上の超関数である場合、部分積分は 次のように 表される。${\displaystyle \mu ,\nu }$${\displaystyle \mathbb {R} }$$${\displaystyle \mathbb {E} _{x\sim \mu }[f(x)]-\mathbb {E} _{y\sim \nu }[f(y)]=\int f'(x)(F_{\nu }(x)-F_{\mu }(x))\,\mathrm {d} x,}$$$${\displaystyle f(x)=K\cdot \operatorname {sign} (F_{\nu }(x)-F_{\mu }(x)).}$$

ベナモウとブレニエは流体力学によるの双対表現を発見し、凸最適化による効率的な解法を可能にした。^{[17] [18]}${\displaystyle W_{2}}$

上の2 つの確率密度が与えられ、 ここで は流体密度場上の境界条件を持つ 連続方程式を駆動する速度場上の範囲です。つまり、質量は保存され、速度場は時間間隔 の間に 確率分布を に輸送する必要があります。 ${\displaystyle p,q}$${\displaystyle \mathbb {R} ^{n}}$$${\displaystyle W_{2}^{2}(p,q)=\min _{\mathbf {v}}\int _{0}^{1}\int _{\mathbb {R} ^{n}}\|{\mathbf {v}}({\mathbf {x}},t)\|^{2}\rho ({\mathbf {x}},t)\,d{\mathbf {x}}\,dt}$$${\displaystyle {\mathbf {v}}}$$${\displaystyle {\dot {\rho }}+\nabla \cdot (\rho {\mathbf {v}})=0\quad \rho (\cdot ,0)=p,\;\rho (\cdot ,1)=q}$$${\displaystyle p}$${\displaystyle q}$${\displaystyle [0,1]}$

適切な仮定の下では、2 次ワッサーシュタイン距離は、負の次数同次ソボレフノルムとリプシッツ同値です。より正確には、を正の測度 を備えた連結リーマン多様体とすると、半ノルム に対して を 、双対ノルム 上の符号付き測度に対してを定義できます 。すると、 上の任意の 2 つの確率測度とは上限を満たします^[19] 逆に、と がそれぞれ上の標準体積測度に関する密度を持ち、その両方が によって上方に有界で、非負のリッチ曲率を持つ場合、次のようになります^{[20] [21]}${\displaystyle W_{2}}$${\displaystyle M}$ ${\displaystyle \pi }$${\displaystyle f\colon M\to \mathbb {R} }$$${\displaystyle \|f\|_{{\dot {H}}^{1}(\pi )}^{2}=\int _{M}\|\nabla f(x)\|^{2}\,\pi (\mathrm {d} x)}$$ ${\displaystyle \mu }$${\displaystyle M}$$${\displaystyle \|\mu \|_{{\dot {H}}^{-1}(\pi )}=\sup {\bigg \{}|\langle f,\mu \rangle |\,{\bigg |}\,\|f\|_{{\dot {H}}^{1}(\pi )}\leq 1{\bigg \}}.}$$${\displaystyle \mu }$${\displaystyle \nu }$${\displaystyle M}$ $${\displaystyle W_{2}(\mu ,\nu )\leq 2\,\|\mu -\nu \|_{{\dot {H}}^{-1}(\pi )}.}$$${\displaystyle \mu }$${\displaystyle \nu }$${\displaystyle M}$${\displaystyle 0<C<\infty }$${\displaystyle M}$ $${\displaystyle \|\mu -\nu \|_{{\dot {H}}^{-1}(\pi )}\leq {\sqrt {C}}\,W_{2}(\mu ,\nu ).}$$

任意のp ≥ 1に対して、距離空間( P _p ( M ), W _p )は分離可能であり、( M , d )が分離可能かつ完全であれば距離空間は完全である。^[22]

のワッサーシュタイン計量を考えることも可能である。この場合、定義式は次式となる。 ここで、は測度 に関するの本質的上限を表す。計量空間 ( P _∞ ( M ), W _{∞ ) は、(} M ,  d ) が分離可能かつ完全である場合に完全である。ここで、P _{∞ は、}有界台を持つすべての確率測度の空間である。^[23]${\displaystyle p=\infty }$$${\displaystyle W_{\infty }(\mu ,\nu )=\lim _{p\rightarrow +\infty }W_{p}(\mu ,\nu )=\inf _{\gamma \in \Gamma (\mu ,\nu )}\gamma \operatorname {-essup} d(x,y),}$$${\displaystyle \gamma \operatorname {-essup} d(x,y)}$${\displaystyle d(x,y)}$${\displaystyle \gamma }$