Wassersteinova metrika - Wasserstein metric

v matematika, Wassersteinova vzdálenost nebo Metrika Kantorovich – Rubinstein je funkce vzdálenosti definováno mezi rozdělení pravděpodobnosti na dané metrický prostor ${displaystyle M}$.

Intuitivně, pokud se na každou distribuci pohlíží jako na hromadné množství země (půdy) ${displaystyle M}$, metrika je minimální „cena“ přeměny jedné hromádky na druhou, o které se předpokládá, že je to množství Země, které je třeba přemístit krát střední vzdálenost, kterou je třeba přemístit. Kvůli této analogii je metrika známa v počítačová věda jako vzdálenost hybatelů Země.

Název „Wassersteinova vzdálenost“ vymyslel R. L. Dobrushin v roce 1970, po ruština matematik Leonid Vaseršteĭn kdo představil tento koncept v roce 1969. Most Angličtina -jazykové publikace používají Němec hláskování "Wasserstein" (připisováno jménu "Vaseršteĭn", které je z Němec původ).

Definice

Nechat ${displaystyle (M, d)}$ být metrický prostor pro které je každé pravděpodobnostní měřítko zapnuto ${displaystyle M}$ je Radonová míra (tzv Radonový prostor ). Pro ${displaystyle pgeq 1}$, nechť ${displaystyle P_ {p} (M)}$ označují soubor všech pravděpodobnostních opatření ${displaystyle mu}$ na ${displaystyle M}$ s konečnou ${displaystyle p ^ {ext {th}}}$ okamžik. Pak tam nějaké jsou ${displaystyle x_ {0}}$ v ${displaystyle M}$ takové, že:

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

The ${displaystyle p ^ {ext {th}}}$ Wassersteinova vzdálenost mezi dvěma měřítky pravděpodobnosti ${displaystyle mu}$ a ${displaystyle u}$ v ${displaystyle P_ {p} (M)}$ je definován jako

${displaystyle W_ {p} (mu, u): = left (inf _ {gamma in Gamma (mu, u)} int _ {M imes M} d (x, y) ^ {p}, mathrm {d} gamma (x, y) ight) ^ {1 / p},}$

kde ${displaystyle Gamma (mu, u)}$ označuje sběr všech opatření na ${displaystyle M imes M}$ s marginální ${displaystyle mu}$ a ${displaystyle u}$ na prvním a druhém faktoru. (Sada ${displaystyle Gamma (mu, u)}$ se také nazývá množina všech spojky z ${displaystyle mu}$ a ${displaystyle u}$.)

Výše uvedená vzdálenost je obvykle označena ${displaystyle W_ {p} (mu, u)}$ (obvykle mezi autory, kteří dávají přednost pravopisu "Wasserstein") nebo ${displaystyle ell _ {p} (mu, u)}$ (obvykle mezi autory, kteří dávají přednost pravopisu „Vaserstein“). Ve zbývající části tohoto článku bude použito ${displaystyle W_ {p}}$ notace.

Wassersteinovu metriku lze ekvivalentně definovat pomocí

${displaystyle W_ {p} (mu, u) = left (inf operatorname {E} {ig [} d (X, Y) ^ {p} {ig]} ight) ^ {1 / p},}$

kde ${displaystyle mathbf {E} [Z]}$ označuje očekávaná hodnota a náhodná proměnná ${displaystyle Z}$ a infimum převezme všechna společná rozdělení náhodných proměnných ${displaystyle X}$ a ${displaystyle Y}$ s okraji ${displaystyle mu}$ a ${displaystyle u}$ resp.

Intuice a spojení k optimální přepravě

Dvě jednorozměrná rozdělení ${displaystyle mu}$ a ${displaystyle u}$, vynesené na osách xay a jedno možné společné rozdělení, které definuje přepravní plán mezi nimi. Společný plán distribuce / přepravy není jedinečný

Jedním ze způsobů, jak pochopit motivaci výše uvedené definice, je zvážit optimální dopravní problém. To znamená pro rozdělení hmoty ${displaystyle mu (x)}$ na mezeru ${displaystyle X}$, chceme přenést hmotu takovým způsobem, aby byla přeměněna na distribuci ${displaystyle u (x)}$ ve stejném prostoru; transformace „hromady Země“ ${displaystyle mu}$ na hromadu ${displaystyle u}$. Tento problém má smysl pouze v případě, že hromada, která má být vytvořena, má stejnou hmotnost jako hromada, která má být přesunuta; proto bez ztráty obecnosti předpokládejme, že ${displaystyle mu}$ a ${displaystyle u}$ jsou rozdělení pravděpodobnosti obsahující celkovou hmotnost 1. Předpokládejme také, že je dána nějaká nákladová funkce

${displaystyle c (x, y) mapsto [0, infty)}$

což dává náklady na přepravu jednotkové hmoty z bodu ${displaystyle x}$ do té míry ${displaystyle y}$Plán dopravy k přesunu ${displaystyle mu}$ do ${displaystyle u}$ lze popsat funkcí ${displaystyle gamma (x, y)}$ což udává množství hmoty, ze které se lze pohybovat ${displaystyle x}$ na ${displaystyle y}$. Úkol si můžete představit jako nutnost přemístit hromadu hlíny tvaru ${displaystyle mu}$ do díry v zemi tvaru ${displaystyle u}$ tak, že na konci hromada země i díra v zemi úplně zmizí. Aby měl tento plán smysl, musí splňovat následující vlastnosti

${displaystyle {egin {aligned} int gamma (x, y), mathrm {d} y = mu (x) & qquad {ext {(množství Země přesunuté z bodu}} x {ext {musí se rovnat množství, které tam bylo začít)}} int gamma (x, y), mathrm {d} x = u (y) & qquad {ext {(množství Země přesunuté do bodu}} y {ext {je třeba rovnat hloubce díry, která tam byla na začátku)}} konec {zarovnáno}}}$

To znamená, že se celková hmota pohnula mimo nekonečně malá oblast kolem ${displaystyle x}$ musí se rovnat ${displaystyle mu (x) mathrm {d} x}$ a celková hmotnost se pohnula do oblast kolem ${displaystyle y}$ musí být ${displaystyle u (y) mathrm {d} y}$. To odpovídá požadavku, že ${displaystyle gamma}$ být společné rozdělení pravděpodobnosti s okraji ${displaystyle mu}$ a ${displaystyle u}$. To znamená, že nekonečně malá hmota transportována z ${displaystyle x}$ na ${displaystyle y}$ je ${displaystyle gamma (x, y), mathrm {d} x, mathrm {d} y}$a náklady na stěhování jsou ${displaystyle c (x, y) gama (x, y), mathrm {d} x, mathrm {d} y}$, v návaznosti na definici nákladové funkce. Proto celkové náklady na plán dopravy ${displaystyle gamma}$ je

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

Plán ${displaystyle gamma}$ není jedinečný; optimální plán dopravy je plán s minimálními náklady ze všech možných plánů dopravy. Jak již bylo zmíněno, podmínkou platnosti plánu je to, že se jedná o společnou distribuci s marginálními částkami ${displaystyle mu}$ a ${displaystyle u}$; pronájem ${displaystyle Gamma}$ označit soubor všech takových opatření, jako v první části, náklady na optimální plán je

${displaystyle C = inf _ {gama v gama (mu, u)} int c (x, y), mathrm {d} gama (x, y)}$

Pokud je cena pohybu jednoduše vzdálenost mezi dvěma body, pak je optimální cena shodná s definicí ${displaystyle W_ {1}}$ vzdálenost.

Příklady

Bodové hmoty (degenerované distribuce)

Nechat ${displaystyle mu _ {1} = delta _ {a_ {1}}}$ a ${displaystyle mu _ {2} = delta _ {a_ {2}}}$ být dva zdegenerované distribuce (tj. Dirac delta distribuce ) umístěný v bodech ${displaystyle a_ {1}}$ a ${displaystyle a_ {2}}$ v ${displaystyle mathbb {R}}$. Existuje pouze jedna možná spojka těchto dvou měr, jmenovitě bodová hmotnost ${displaystyle delta _ {(a_ {1}, a_ {2})}}$ nachází se na ${displaystyle (a_ {1}, a_ {2}) v mathbb {R} ^ {2}}$. Tedy pomocí obvyklých absolutní hodnota funkce zapnutá funkce vzdálenosti ${displaystyle mathbb {R}}$, pro všechny ${displaystyle pgeq 1}$, ${displaystyle p}$-Wassersteinova vzdálenost mezi ${displaystyle mu _ {1}}$ a ${displaystyle mu _ {2}}$ je

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

Podobným uvažováním, pokud ${displaystyle mu _ {1} = delta _ {a_ {1}}}$ a ${displaystyle mu _ {2} = delta _ {a_ {2}}}$ jsou bodové hmoty umístěné v bodech ${displaystyle a_ {1}}$ a ${displaystyle a_ {2}}$ v ${displaystyle mathbb {R} ^ {n}}$a používáme obvyklé Euklidovská norma na ${displaystyle mathbb {R} ^ {n}}$ jako funkci vzdálenosti pak

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

Normální rozdělení

Nechat ${displaystyle mu _ {1} = {mathcal {N}} (m_ {1}, C_ {1})}$ a ${displaystyle mu _ {2} = {mathcal {N}} (m_ {2}, C_ {2})}$ být dva nedegenerovaní Gaussovy míry (tj. normální distribuce ) zapnuto ${displaystyle mathbb {R} ^ {n}}$, s příslušnými očekávané hodnoty ${displaystyle m_ {1}}$ a ${displaystyle m_ {2} v mathbb {R} ^ {n}}$ a symetrický kladný polořadový kovarianční matice ${displaystyle C_ {1}}$ a ${displaystyle C_ {2} v mathbb {R} ^ {n imes n}}$. Pak,^[1] s ohledem na obvyklou euklidovskou normu dne ${displaystyle mathbb {R} ^ {n}}$, 2-Wassersteinova vzdálenost mezi ${displaystyle mu _ {1}}$ a ${displaystyle mu _ {2}}$ je

${displaystyle W_ {2} (mu _ {1}, mu _ {2}) ^ {2} = | m_ {1} -m_ {2} | _ {2} ^ {2} + mathop {mathrm {trace} } {igl (} C_ {1} + C_ {2} -2 {igl (} C_ {2} ^ {1/2} C_ {1} C_ {2} ^ {1/2} {igr)} ^ { 1/2} {igr)}.}$

Tento výsledek zobecňuje dřívější příklad Wassersteinovy ​​vzdálenosti mezi dvěma bodovými hmotami (alespoň v případě ${displaystyle p = 2}$), protože bodovou hmotu lze považovat za normální rozdělení s kovarianční maticí rovnou nule, v tom případě stopa termín zmizí a zůstane pouze člen zahrnující euklidovskou vzdálenost mezi prostředky.

Aplikace

Wassersteinova metrika je přirozeným způsobem, jak porovnat rozdělení pravděpodobnosti dvou proměnných X a Y, kde je jedna proměnná odvozena od druhé malou, nejednotnou odchylkou (náhodnou nebo deterministickou).

Například v informatice metrické Ž₁ je široce používán k porovnání diskrétních distribucí, např. the barevné histogramy ze dvou digitální obrázky; vidět vzdálenost hybatelů Země Více podrobností.

Ve svém příspěvku „Wasserstein GAN“ Arjovsky et al.^[2] použít metriku Wasserstein-1 jako způsob, jak zlepšit původní rámec Generativní Adversarial Networks (GAN), zmírnit mizející přechod a problémy se zhroucením režimu.

Wassersteinova metrika má formální souvislost s Analýza prokrustů, s aplikací na opatření chirality ^[3]a tvarovou analýzu ^[4].

Vlastnosti

Metrická struktura

To lze ukázat Ž_p vyhovuje všem axiomy a metrický na P_p(M). Dále konvergence s ohledem na Ž_p je ekvivalentní obvyklému slabá konvergence opatření plus konvergence prvního pth okamžiky.^[5]

Duální zastoupení Ž₁

—Následující dvojí znázornění Ž₁ je speciální případ věty o dualitě Kantorovich a Rubinstein (1958): kdy μ a ν mít ohraničený Podpěra, podpora,

${displaystyle W_ {1} (mu, u) = sup left {left.int _ {M} f (x), mathrm {d} (mu -u) (x) ight | {ext {spojitý}} f: M o mathbb {R}, operatorname {Lip} (f) leq 1ight},}$

kde Lip (F) označuje minimální Lipschitzova konstanta pro F.

Porovnejte to s definicí Radonová metrika:

${displaystyle ho (mu, u): = sup left {left.int _ {M} f (x), mathrm {d} (mu -u) (x) ight | {ext {spojitý}} f: M o [ -1,1] v noci}.}$

Pokud je metrika d je omezena nějakou konstantou C, pak

${displaystyle 2W_ {1} (mu, u) leq Cho (mu, u),}$

a tak konvergence v radonové metrice (shodná s celková variační konvergence když M je Polský prostor ) implikuje konvergenci v Wassersteinově metrice, ale ne naopak.

Rovnocennost Ž₂ a Sobolevova norma záporného řádu

Za vhodných předpokladů Wassersteinova vzdálenost ${displaystyle W_ {2}}$ druhého řádu je Lipschitz ekvivalentní s homogenem záporného řádu Sobolevova norma.^[6] Přesněji řečeno, pokud vezmeme ${displaystyle M}$ být a připojeno Riemannovo potrubí vybaveno kladným měřítkem ${displaystyle pi}$, pak můžeme definovat pro ${displaystyle fcolon M o mathbb {R}}$ seminář

${displaystyle | f | _ {{dot {H}} ^ {1} (pi)} ^ {2} = int _ {M} | abla f (x) | ^ {2}, pi (mathrm {d} x )}$

a pro podepsané opatření ${displaystyle mu}$ na ${displaystyle M}$ dvojí norma

${displaystyle | mu | _ {{dot {H}} ^ {- 1} (pi)} = sup {igg {} | langle f, mu angle |, {igg |}, | f | _ {{dot {H }} ^ {1} (pi)} leq 1 {igg}}.}$

Pak jakákoli dvě pravděpodobnostní opatření ${displaystyle mu}$ a ${displaystyle u}$ na ${displaystyle M}$ uspokojit horní hranici

${displaystyle W_ {2} (mu, u) leq 2 | mu -u | _ {{dot {H}} ^ {- 1} (mu)}.}$

V opačném směru, pokud ${displaystyle mu}$ a ${displaystyle u}$ každý má hustotu vzhledem k standardní měření objemu na ${displaystyle M}$ které jsou nad některými omezeny ${displaystyle 0$, a ${displaystyle M}$ má nezáporné Ricciho zakřivení, pak

${displaystyle | mu -u | _ {{dot {H}} ^ {- 1} (mu)} leq {sqrt {C}} W_ {2} (mu, u).}$

Oddělitelnost a úplnost

Pro všechny p ≥ 1, metrický prostor (P_p(M), Ž_p) je oddělitelný, a je kompletní pokud (M, d) je oddělitelný a úplný.^[7]

Viz také

• Lévyho metrika
• Lévy – Prochorovova metrika
• Celková variační vzdálenost pravděpodobnostních opatření
• Teorie dopravy
• Vzdálenost pohybujícího se Země

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Červenec 2012) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Reference

• Villani, Cédric (2008). Optimální doprava, stará i nová. Springer. ISBN  978-3-540-71050-9.
• Ambrosio, L., Gigli, N. & Savaré, G. (2005). Toky gradientu v metrických prostorech a v prostoru pravděpodobnostních opatření. Basilej: ETH Zürich, Birkhäuser Verlag. ISBN  3-7643-2428-7.CS1 maint: více jmen: seznam autorů (odkaz)
• Jordan, Richard; Kinderlehrer, David; Otto, Felixe (1998). "Variační formulace Fokker-Planckovy rovnice". SIAM J. Math. Anální. 29 (1): 1–17 (elektronický). CiteSeerX  10.1.1.6.8815. doi:10.1137 / S0036141096303359. ISSN  0036-1410. PAN  1617171.
• Rüschendorf, L. (2001) [1994], „Wassersteinova metrika“, Encyclopedia of Mathematics, Stiskněte EMS

externí odkazy

• „Jaké jsou výhody Wassersteinovy ​​metriky ve srovnání s Kullback-Leiblerovou divergencí?“. Stack Exchange. 1. srpna 2017.