와세르슈타인 미터법

수학에서 와세르슈타인 거리 또는 칸토로비치-루빈스타인 미터법은 주어진 미터법 공간 $M{\displaystyle }$ ${\displaystyle$ M$}$에 대한 확률 분포 사이에 정의된 거리 함수로 레오니드 바세르슈테인의 이름을 따서 명명되었다$.$

직관적으로 각 분포를 M{M\displaystyle}에 쌓인 흙(토양)의 단위량으로 본다면, 측정기준은 한 더미를 다른 더미로 바꾸는 최소"비용"이며, 이는 이동해야 하는 평균 거리에 곱한 흙의 양으로 가정된다. 이 문제는 1781년 가스파드 몽에 의해 처음으로 공식화되었다. 이러한 유사성 때문에, 미터법은 컴퓨터 과학에서 지구 이동자의 거리로 알려져 있다.

"와세르슈타인 거리"라는 이름은 R. L. 도브루신(R. L. Dobrusin)이 마코프 공정에서^[1] 오토마타의 큰 시스템을 기술한 레오니드 바세르슈테인의 작품에서 그것을 알게 된 후 1970년에 만들어졌다(러시아, 1969년). 그러나 이 측정기준은 우선 레오니드 칸토로비치가 상품과 자재의 최적 운송계획이라는 맥락에서 <생산계획과 조직의 수학적 방법^[2]>(러시아어 원 1939년)에서 정의한 것이다. 따라서 일부 학자들은 "칸토로비치 미터법"과 "칸토로비치 거리"라는 용어의 사용을 권장한다. 대부분의 영어 출판물은 독일어 철자 "Wasserstein"을 사용한다. (독일어 원산의 "Basershteĭn"이라는 이름에 기인함).

정의

Let${\displaystyle }$( ${\displaystyle M}$, ${\displaystyle d}$) ${\디스플레이$ 스타일 ($M,d)}$은 $M{\displaystyle }$ ${\$디스플레이 $스타일$ M$}$에 대한 모든 보렐 확률 측정이 라돈 측정( 소위 라돈 공간)인$$ 메트릭 공간이다. $p{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle 1}$ ${\displaystyle$ $p$$\geq 1}$의 경우 $P{\displaystyle {}_{}}$$$p (${\displaystyle {}_{}{M}_{}}$) ${\displaystyle P_{p}(M)}$은$($는) p ${\displaystyle {\text{th}}^{}}$ ${\$$$p$^{\text{th}}$ 모멘트가 유한한$$ $M{\displaystyle }$ ${\displaystystystyle M}$의 모든$$ 확률 측정 $\mu {\displaystyle }$ ${\\\\data$. $M{\displaystyle }$ ${\displaystyle M}$에는 다음과 같은$$ $일부{\displaystyle {}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$ 0$${\$displaystyle x_{0}$이 있다.

${\displaystyle \int _{M}d(x,x_{0})^{p}\,\mathrm {d}\mu(x)\mu(x)<\infit.}$

$p{\displaystyle {}^{}}$ ${\displaystyle {th}_{}}$ ${\$$P{\displaystyle {}_{}}$(${\displaystyle {\text{M}}^{}}$${\displaystyle )}$에서 두$$ 확률 측정 μ[\$displaystyle$ \$mu }$과($와{\displaystyle }$) ${\$$displaystyle$ $P_{p}(M)$ 사이의 와세슈타인$$ 거리는 다음과 같이 정의된다$$.

${\d}\displaystyle W_{p}(\mu ,\nu ):=\왼쪽(\inf _{\inf \in \inf \in \in \in \ma (\mu ,\nu )}\int_{M\m\\\\\time M}d(x,y)^{p}\math {d}, \d}}$

where ${\displaystyle \Gamma (\mu ,\nu )}$ denotes the collection of all measures on ${\displaystyle M\times M}$ with marginals ${\displaystyle \mu }$ and ${\displaystyle \nu }$ on the first and second factors respectively. (The set ${\displaystyle \Gamma (\mu ,\nu )}$ is also called t그는 $\mu s$의 모든 커플링 세트인$$\$displaystyle \mu }$과 $\nu {\displaystyle }$ ${\displaystyle \nu$}.$$

위의 거리는 대개 ${\displaystyle W_{}}$ p${\displaystyle {}_{}}$(${\displaystyle \mu }$ ,${\displaystyle \mu }$) ${\displaystyle W_{p}(\mu ,\nu )}($일반적으로 "Wasserstein" 철자를 선호하는 작가들 사이) 또는$$ p${\displaystyle {}_{}}$(${\displaystyle \mu }$ ,${\displaystyle \nu }$)[\$displaystyle \ell \{p}(\mu$,\$nu$)}($$일반적으로 "Vasserstesterstesterstesterstein) 철자를 선호하는 작가들 사이)]로 표시된다. 이 글의 나머지 부분에는 $W{\displaystyle {}_{}}$ ${\displaystyle p_{}}$ ${\$ 표기법이$$ 사용된다.

와세르슈타인 메트릭은 다음과 같이 동등하게 정의될 수 있다.

${\displaystyle W_{p}(\mu ,\nu )=\왼쪽(\inf \operatorname {E} {\big [}d(X,Y)^{p}{p}{\big ]}\오른쪽)^{1/p}}}$

여기서 $E{\displaystyle \mathbf{}}$[ ${\displaystyle Z}$ ${\displaystyle ]}$ ${\displaystyle \mathbf {E} [Z]}$은 랜덤 $변수{\displaystyle }$ Z ${\\displaystyle$ $Z$$}$의 기대값을 나타내며$$$$, 최소값은 여백 $(\displaystyle$$\$$mu }$ $및$ $display$ {\$displaystystyle \nu}$의 $모든{\displaystyle }$ 공동 분포를 인수한다. 각각

직관과 최적의 운송 수단과의 연결

위의 정의를 이해하는 한 가지 방법은 최적의 운송 문제를 고려하는 것이다. 즉, 공간 $X{\displaystyle }$ ${\displaystyle X}$에 질량 $($) {\$displaystyle$ $\$$mu(x)}$을(를) 분포하는 경우$,$ 질량을 동일한 공간에$$ 분포 $\nu {\displaystyle (x}$) ${\displaystystyle$$$\$nu($x)}로 변환하여 '지구의 편' $\mu {\displaystyle }$(pile of μ$) {\displaystaystymu$)을$$ 더미로 변환하는 $방식$으로 전달하고자 한다$.$$\displaystyle \nu$ 이 문제는 생성될 더미가 이동할 더미와 동일한 질량을 갖는 경우에만 의미가 있으므로 일반성을 잃지 않고 $\mu {\displaystyle }$ ${\displaystyle \mu }$ 및 $\mu$ ${\displaysty \nu }$이(가) 총 질량이 1인 확률 분포라고$$ 가정한다. 또한 일부 비용 함수가 주어진다고 가정하십시오.

$[0,\displaystyle c(x,y)\mapsto [0,\fty )}$

단위 질량을 지점 $x에서$지점$$ $y$로 운송하는 데 드는 비용을 산출한다$.$$$$\displaystyle \mu }$을(를$)$ $\nu {\displaystyle }$ ${\displaystyle \nu }($을)로$$ 이동시키는 운송 계획은 $\gamma {\displaystyle }$( ${\displaystyle x}$, ${\displaystyle y}$) ${\displaystyle \gamma$ ($x,y)$ 함수)로$$ 설명할$$ 수 있다.${\displaystyle x}$ ${\displaystyle x}$에서 y ${\displaystyle y}$까지$.$ $\mu {\displaystyle }$ 형상의 흙더미$[\displaystyle \mu$$}$을(를) 형상의 땅속 구멍으로$$ 옮겨야 하는$$ 작업으로서 마지막에는 흙더미와 땅속의 구멍이 모두 완전히 사라지는 작업이라고 상상할 수 있다. 이 계획이 의미가 있으려면 다음 특성을 충족해야 한다.

${\displaystyle {\regated}\int \int \int \x(x,y)\\mathrm {d}y=\mu(x)&\qquad {\text{{{}(지점 밖으로 이동한 지구의 양은 처음에 있던 양과 같아야 함)}}}\\int \int \x,y)\\\mathrm {d}x=\nu(y)&\qquad{\text{{{}(지점 이동량은 처음에 있던 구멍의 깊이와 같아야 함)}}}\end{정렬}}$

$즉{\displaystyle }$, $x{\displaystyle }$ ${\displaystyle$ x$}$ 주위의 최소 영역에서 이동한 총 질량은 $\mu {\displaystyle }$(x${\displaystyle }$) d ${\displaystyle x}$ ${\dstaystyle \mu(x)\$$mathrm$ {$d}$ x$\}$이어야 하며$$, y$$ ${\$$displaysty$ $y$$}$ 주위의 영역으로 이동한 총 질량은 $\mu {\displaystyle (y)}$ d$$ $y$ ($y)$ $.$ 이는 $\gamma {\displaystyle }$ ${\displaystyle \gamma}$이(가) 여백 $[\displaystyle$ $\$$mu }$과(와)$\nu {\displaystyle }$ {\$displaystyle$ \$nu$$$$}$을(를$)$ 갖는 공동 확률 분포여야$$ 하는 요구 사항과 같다$.$ $따라서$ x$${\$d$${\displaystyle ,}$ ${\displaystyle y}$}로 $전송$되는 최소 질량은$$ $\gamma {\displaystyle }$(${\displaystyle x,}$ ) d, ${\displaystyle d}$, d, y$.$$\gamma (x,y)\\\mathrm {d} x\,\mathrm$ {$d}$ y$\}$ , 이동 비용은 비용 함수의 정의에 따라 $c{\displaystyle }$(${\displaystyle x,}$ y )$γ$($x,y)\\\mathrm {d},\mathrm {d} y}$ 입니다$.$ 따라서 운송 계획 $plan{\displaystyle }$ ${\displaystyle \gamma}$의 총 비용은

${\displaystyle \iint c(x,y)\mathrm {d} x\,\mathrm {d} y=\int c(x,y)\\mathrm {d} \mathrm {d} \mathrm {d} \iint c(x,y)}$

계획 $\gamma {\displaystyle }$ ${\displaystyle \gamma}$은(는) 고유하지 않다. 최적의 운송 계획은 가능한 모든 운송 계획 중에서 최소한의 비용으로 계획하는 것이다. 전술한 바와 같이, 계획의 유효요건은 마진 $[\displaystyle \mu }$과 $[\displaystyle \nu }$이(가) 있는 공동분포라는 것이다$;$ $\gamma {\displaystyle \mathrm{}}$ ${\displaystyle \Gamma }$이(가)가 첫 번째 절에서와 같은 모든 조치의 집합을$$ 나타내도록 한다.

$\dmatrm {d}\damma(\mu ,\nu )}\int c(x,y)\\d}\mathrm {d} \gamma(x,y)}$

이동 비용이 단순히 두 지점 사이의 거리일 경우 최적 ${\displaystyle {비용}_{}}$은 W 1 ${\$} 거리의$$ 정의와 동일하다.

예

점 질량(분포 제거)

Let ${\displaystyle \mu _{1}=\delta _{a_{1}}}$ and ${\displaystyle \mu _{2}=\delta _{a_{2}}}$ be two degenerate distributions (i.e. Dirac delta distributions) located at points ${\displaystyle a_{1}}$ and ${\displaystyle a_{2}}$ in ${\displaystyle \math$$bb {R} }$. There is only one possible coupling of these two measures, namely the point mass ${\displaystyle \delta _{(a_{1},a_{2})}}$ located at ${\displaystyle (a_{1},a_{2})\in \mathbb {R} ^{2}}$. Thus, using the usual absolute value function as the distance function on $$${\displaystyle }$${\displaystyle \mathrm{R}}$ ${\$p${\displaystyle }p{\displaystyle }$ 1 ${\displaystyle$ p$\geq$ 1$\}$에 $대한{\displaystyle }$ p$${\$displaystyle$p} - $\mu$ ${\displaystyle {1\mathrm{}}_{}}${\$displaysty \mu$ _${$$1$}와 ${\displaystyle {\mu \mathrm{}}_{}}$ 2$${\$displaystystylease \mu_$${$2}} $사이의 거리$

${\displaystyle W_{p}(\mu _{1},\mu _{2}= a_{1}-a_{2} .}$

By similar reasoning, if ${\displaystyle \mu _{1}=\delta _{a_{1}}}$ and ${\displaystyle \mu _{2}=\delta _{a_{2}}}$ are point masses located at points ${\displaystyle a_{1}}$ and ${\displaystyle a_{2}}$ in ${\displaystyle \mathbb {R} ^{n}}$, and we $R{\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {}^{}}$ ${\$에 있는 일반적인 유클리드 규범을 거리 함수로 사용한$$ 다음

${\displaystyle W_{p}(\mu _{1},\mu _{2}=\ a_{1}-a_{2}\ _{2}.}$

정규 분포

Let ${\displaystyle \mu _{1}={\mathcal {N}}(m_{1},C_{1})}$ and ${\displaystyle \mu _{2}={\mathcal {N}}(m_{2},C_{2})}$ be two non-degenerate Gaussian measures (i.e. normal distributions) on ${\displaystyle \mathbb {R} ^{n}}$, with respective expec테드 값 치고 1{\displaystyle m_{1}}과 m2∈ Rn{\displaystyle m_{2}\in \mathbb{R}^{n}}대칭이고 긍정적인 semi-definite 공분산 매트릭스 C1{\displaystyle C_{1}}과 C2∈ Rn× n{\displaystyle C_{2}\in \mathbb{R}^{n\times의 스녀}}. Then,[3]은 평소 이용과 관련해아니요.rm on ${\displaystyle {}^{}}$ ${\$$\mu {\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$}와$$ $\mu {\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}} 사이의$$ 2-Wasserstein 거리

${\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 \mathrm{사례}}$ p${\displaystyle }$= 2 ${\displaystyle p=2}).$ 점 질량은 공분산 행렬이 0인 정규 분포로 간주할 수 있으며, 이 경우 추적 항은 사라지고 유클리드 거리 벳위(E)를 포함하는 용어만 포함되기 때문이다.수단이 남다.

적용들

와세슈타인 메트릭은 두 변수 X와 Y의 확률 분포를 비교하는 자연스러운 방법이다. 여기서 한 변수는 작은 불균일한 섭동(랜덤 또는 결정론적)에 의해 다른 변수로부터 파생된다.

예를 들어 컴퓨터 과학에서 미터법 W는₁ 두 디지털 이미지의 색상 히스토그램과 같은 이산 분포를 비교하는 데 널리 사용된다. 자세한 내용은 지구 이동자의 거리를 참조하십시오.

그들의 논문 'Wasserstein GAN'에서 Arjovsky 외 연구진.^[4] Wasserstein-1 메트릭스를 GAN(Generative Attherarical Network)의 원래 프레임워크를 개선하여 소멸하는 구배와 모드 붕괴 문제를 완화하기 위한 방법으로 사용한다. 정규 분포의 특별한 경우는 프리쳇 인셉션 거리에 사용된다.

와세르슈타인 메트릭스는 프로크루스테스 분석과 공식적인 연관성을 가지고 있으며, 치례성 측정에 적용하고,^[5] 분석을 구체화한다.^[6]

특성.

미터법 구조

또한_p W는 P_p(M)에 대한 측정의 모든 공리를 만족한다는 것을 알 수 있다. 더욱이_p W에 대한 정합성은 측정의 약한 정합화 + 첫 번째 순간의 정합화와 같다.^[7]

W의₁ 이중 표현

다음의 W의₁ 이중적 표현은 칸토로비치와 루빈스타인(1958)의 이중성 정리의 특수한 경우로, μ와 μ가 지지에 경계를 했을 때,

${\displaystyle W_{1}(\mu ,\nu )=\suppy \left\{\왼쪽).\int _{M}f(x)\,\mathrm {d}(\mu -\nu )(x)\right {\text{연속 }f:M\to \mathb {R} ,\operatorname {Lip}(f)\leq 1\right\}}$

여기서 립(f)은 f에 대한 최소 립스치츠 상수를 나타낸다.

이를 라돈 측정 기준의 정의와 비교해 보십시오.

$\displaystyle \rho (\mu ,\nu )=\suppled\{\왼쪽.\int _{M}f(x)\,\mathrm {d}(\mu -\nu )(x)\right {\text{연속 }f:M\to [-1,1]\right\}.}$

미터법 d가 일정한 C로 경계를 이루면

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

따라서 라돈 측정지표의 수렴(M이 폴란드 공간일 때 총 변동 수렴과 동일)은 와세르슈타인 측정지표의 수렴을 의미하지만, 그 반대의 경우도 아니다.

W와₂ 음순 소볼레프 표준의 동등성

적절한 가정 하에서 와세르슈타인 거리 $W{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}} 순서는$$ 음순 동종 소볼레프 규범에 상당하는 립시츠다.^[8] 좀 더 정확히 $말하자면{\displaystyle }$, 만약 M$${\$displaystyle$M}을(를$$) 양성 측정 $\pi {\displaystyle }$ ${\displaystyle \pi$ $\}$을(를) 갖춘 연결된 리만 매니폴드로 본다면, $f{\displaystyle }$: ${\displaystyle M}$→ ${\displaystyle R\mathbb{}}$ ${\displaystyle$ f$\colon$ M\to$$\mathb {$R}}}$에 대해 정의할 수 있다.

${\displaystyle \ \f\{\dot{H}^{1}(\pi )}^{2}=\int_{M} \nabla f(x) ^{2}\,\pi(\mathrm {d}x)}}$

$및{\displaystyle }$ M$${\$displaystyle M}$의 서명된 측정 $\mu {\displaystyle }${\$displaystyle \mu }$의 경우 이중$$ 표준

${\dapty \mu \{\dot{H}^{-1}(\pi )}=\suppy \langle f,\mu \angle \,{\bigg \}\{\dot {H}^{{\h}}}}}\{\dot {H}^{{{{pi}}}}}}}}}}}}}}}}}}\bigg }}}}}}}}}}}}}}}.}$

$그런{\displaystyle }$ 다음 M ${\displaystyle M}$의 두 확률 측정$\mu {\displaystyle }$[\$displaystyle \mu }$과($와{\displaystyle }$) ${\displaystyle \nu }$이(가) 상한을 만족한다$$.

${\dot {H}^{1}(\mu ,\nu )\leq 2\ \mu -\nu \{{\dot{H}^{-1}(\mu )}.}$

다른 방향에서 $\mu$ ${\displaystyle \mu }$ 및 $\mu {\displaystyle }$ ${\$$displaystyle$ $\nu$}이(가$$) < < {\$displaystyle 0<C<\infty$ 위에 경계된 $M$ {\displaystystyle $M}$의 표준 볼륨 측정과 관련된 밀도를 갖는 $경우{\displaystyle }$, 그 다음$,$ 음성이 음성이 음성이$$ 음성이 음성이 음성이 음수치인 경우

${\displaystyle \mu -\nu \ _{\dot{H}^{-1}(\mu )\leq {\c}W_{2}(\mu ,\nu).}$

분리성과 완전성

p ≥ 1에 대해 미터법 공간(P_p(M), W_p)은 분리가 가능하며, (M, d)가 분리가 가능하고 완전할 경우 완전하다.^[9]

참고 항목

• 레비 미터법
• 레비-프로호로프 미터법
• 확률 측정값의 총 변동 거리
• 교통이론
• 지구 이동 거리

참조

• Villani, Cédric (2008). Optimal Transport, Old and New. Springer. ISBN 978-3-540-71050-9.
• Ambrosio, L., Gigli, N. & Savaré, G. (2005). Gradient Flows in Metric Spaces and in the Space of Probability Measures. Basel: ETH Zürich, Birkhäuser Verlag. ISBN 3-7643-2428-7.{{cite book}}: CS1 maint : 복수이름 : 작성자 목록(링크)
• Jordan, Richard; Kinderlehrer, David; Otto, Felix (1998). "The variational formulation of the Fokker–Planck equation". SIAM J. Math. Anal. 29 (1): 1–17 (electronic). CiteSeerX 10.1.1.6.8815. doi:10.1137/S0036141096303359. ISSN 0036-1410. MR 1617171.
• Rüschendorf, L. (2001) [1994], "Wasserstein metric", Encyclopedia of Mathematics, EMS Press

외부 링크

• "What is the advantages of Wasserstein metric compared to Kullback–Leibler divergence?". Stack Exchange. August 1, 2017.