Wassersteinova metrika - Wasserstein metric

V matematiky se Wasserstein vzdálenost nebo Kantorovich - Rubinstein metrika je funkce vzdálenosti definován mezi rozdělení pravděpodobnosti na daném metrickém prostoru . ${\ displaystyle M}$

Intuitivně, pokud je každá distribuce považována za jednotkové množství hromady Země (půdy) , je metrika minimální „cenou“ přeměny jedné hromádky na druhou, což se předpokládá jako množství Země, které je třeba přesunout střední vzdálenost, kterou musí být přesunuta. Díky této analogii je metrika v počítačové vědě známá jako vzdálenost pohybu země . ${\ displaystyle M}$

Název „Wassersteinova vzdálenost“ vytvořil RL Dobrushin v roce 1970, poté, co se o něm dozvěděl v práci ruského matematika Leonida Vaseršteĭna 1969, nicméně metriku poprvé definoval Leonid Kantorovich v Matematická metoda plánování výroby a organizace (ruský originál 1939) ) v kontextu optimálního plánování dopravy zboží a materiálu. Někteří vědci proto podporují používání termínů „metrika Kantorovich“ a „vzdálenost Kantorovich“. Většina publikací v anglickém jazyce používá německý pravopis „Wasserstein“ (přisuzovaný jménu „Vaseršteĭn“ německého původu).

Definice

Dovolit být metrický prostor , u nichž každá míra pravděpodobnosti Borel na je opatření Radon (tzv Radon prostor ). Neboť , označme shromažďování všech pravděpodobnostních měr na s konečným okamžikem . Pak existuje nějaký v taková, že: ${\ displaystyle (M, d)}$${\ displaystyle M}$${\ Displaystyle p \ geq 1}$${\ displaystyle P_ {p} (M)}$${\ Displaystyle \ mu}$${\ displaystyle M}$${\ displaystyle p^{\ text {th}}}$ ${\ displaystyle x_ {0}}$${\ displaystyle M}$

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

Wasserstein vzdálenost mezi dvěma opatřeními pravděpodobnostními a v je definována jako ${\ displaystyle p^{\ text {th}}}$${\ Displaystyle \ mu}$${\ displaystyle \ nu}$${\ displaystyle P_ {p} (M)}$

${\ Displaystyle W_ {p} (\ mu, \ nu): = \ left (\ inf _ {\ gamma \ in \ Gamma (\ mu, \ nu)} \ int _ {M \ times M} d (x, y)^{p} \, \ mathrm {d} \ gamma (x, y) \ right)^{1/p},}$

kde označuje shromažďování všech opatření s mezními hodnotami a prvního a druhého faktoru. (Sada je také nazýván množinu všech spojek z a ). ${\ displaystyle \ Gamma (\ mu, \ nu)}$${\ displaystyle M \ times M}$ ${\ Displaystyle \ mu}$${\ displaystyle \ nu}$${\ displaystyle \ Gamma (\ mu, \ nu)}$${\ Displaystyle \ mu}$${\ displaystyle \ nu}$

Výše uvedená vzdálenost je obvykle označována (typicky mezi autory, kteří dávají přednost hláskování „Wasserstein“) nebo (obvykle mezi autory, kteří dávají přednost hláskování „Vaserstein“). Zbývající část tohoto článku bude používat notaci. ${\ Displaystyle W_ {p} (\ mu, \ nu)}$${\ Displaystyle \ ell _ {p} (\ mu, \ nu)}$${\ displaystyle W_ {p}}$

Wassersteinovu metriku lze ekvivalentně definovat pomocí

${\ Displaystyle W_ {p} (\ mu, \ nu) = \ left (\ inf \ operatorname {E} {\ big [} d (X, Y)^{p} {\ big]} \ right)^{ 1/p},}$

kde označuje očekávanou hodnotu o náhodné proměnné a infimum je převzata všech společných distribucí náhodných proměnných a s marginální a resp. ${\ displaystyle \ mathbf {E} [Z]}$ ${\ displaystyle Z}$${\ displaystyle X}$${\ displaystyle Y}$${\ Displaystyle \ mu}$${\ displaystyle \ nu}$

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

Dvě jednorozměrná rozdělení a vynesená na osách x a y a jedno možné společné rozdělení, které definuje transportní plán mezi nimi. Plán společné distribuce/přepravy není jedinečný${\ Displaystyle \ mu}$${\ displaystyle \ nu}$

Jedním ze způsobů, jak porozumět výše uvedené definici, je zvážit optimální dopravní problém . To znamená, že pro distribuci hmoty v prostoru si přejeme transportovat hmotu takovým způsobem, aby byla transformována do distribuce ve stejném prostoru; transformace „hromady země“ na hromadu . Tento problém má smysl pouze v případě, že hromádka, která má být vytvořena, má stejnou hmotnost jako hromada, která má být přesunuta; Proto bez újmy na obecnosti předpokládat, že a jsou rozdělení pravděpodobnosti, které obsahují celkové hmotnosti 1. Předpokládejme také, že je vzhledem k některým funkce náklady ${\ Displaystyle \ mu (x)}$${\ displaystyle X}$${\ displaystyle \ nu (x)}$${\ Displaystyle \ mu}$${\ displaystyle \ nu}$${\ Displaystyle \ mu}$${\ displaystyle \ nu}$

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

to dává náklady na přepravu jednotkové hmotnosti z bodu do bodu . Dopravní plán postupu do mohou být popsány funkce , která udává množství hmoty přejít od do . Úkol si můžete představit jako potřebu přesunout hromadu zeminy tvaru do otvoru v zemi tvaru tak, aby na konci hromada země i díra v zemi úplně zmizely. Aby byl tento plán smysluplný, musí splňovat následující vlastnosti ${\ displaystyle x}$${\ displaystyle y}$${\ Displaystyle \ mu}$${\ displaystyle \ nu}$${\ displaystyle \ gamma (x, y)}$${\ displaystyle x}$${\ displaystyle y}$${\ Displaystyle \ mu}$${\ displaystyle \ nu}$

${\ Displaystyle {\ begin {aligned} \ int \ gamma (x, y) \, \ mathrm {d} y = \ mu (x) & \ qquad {\ text {(množství Země se posunulo mimo bod}} x {\ text {se musí rovnat částce, která tam byla pro začátek)}} \\\ int \ gamma (x, y) \, \ mathrm {d} x = \ nu (y) & \ qquad {\ text {(množství Země přesunuté do bodu}} y {\ text {se musí rovnat hloubce díry, která tam byla na začátku)}} \ end {aligned}}}$

To znamená, že celková hmotnost přesunutá z nekonečně malé oblasti kolem musí být stejná a celková hmotnost přesunutá do oblasti kolem musí být . To je ekvivalentní požadavku, aby byla společná distribuce pravděpodobnosti s mezními a . Nekonečně malá hmota transportovaná z do je tedy a náklady na pohyb se řídí definicí nákladové funkce. Celkové náklady na dopravní plán jsou tedy ${\ 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} \ gamma (x, y)}$

Plán není jedinečný; optimální přepravní plán je plán s minimálními náklady ze všech možných přepravních plánů. Jak již bylo zmíněno, podmínkou platnosti plánu je, aby se jednalo o společnou distribuci s okrajovými a ; nechat označit soubor všech takových opatření jako v první části, náklady na optimální plán jsou ${\ displaystyle \ gamma}$${\ Displaystyle \ mu}$${\ displaystyle \ nu}$${\ displaystyle \ Gamma}$

${\ Displaystyle C = \ inf _ {\ gamma \ in \ Gamma (\ mu, \ nu)} \ int c (x, y) \, \ mathrm {d} \ gamma (x, y)}$

Pokud jsou náklady na tah jednoduše vzdáleností mezi dvěma body, pak je optimální cena identická s definicí vzdálenosti. ${\ displaystyle W_ {1}}$

Příklady

Bodové masy (degenerované rozdělení)

Nechť jsou a jsou dvě degenerované distribuce (tj. Diracovy delta distribuce ) umístěné v bodech a v . Existuje pouze jedno možné spojení těchto dvou měr, a to hmota bodu umístěná na . Tak s použitím obvyklého absolutní hodnoty funkci jako funkce vzdálenosti na , pro všechny je -Wasserstein vzdálenost mezi a je ${\ 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} |.}$

Podobným úvahy, je-li a jsou hmotné body umístěné v bodech a v , a používáme obvyklou Euklidova normu na jako funkce vzdálenosti, potom ${\ 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}.}$

Normální rozdělení

Nechť jsou a jsou dvě nedegenerované Gaussovy míry (tj. Normální distribuce ) na , s příslušnými očekávanými hodnotami a a symetrickými kladnými semi-určitými kovariančními maticemi a . Potom, s ohledem na obvyklou euklidovskou normu na , 2-Wassersteinova vzdálenost mezi a je ${\ 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)}.}$

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

Aplikace

Wassersteinova metrika je přirozeným způsobem srovnání rozdělení pravděpodobnosti dvou proměnných X a Y , kde jedna proměnná je od druhé odvozena malými, nejednotnými odchylkami (náhodnými nebo deterministickými).

Ve vědě o počítačích, například metrika W ₁ je široce používán pro porovnání diskrétní distribuce, například na barevný histogram dvou digitálních obrazů ; více podrobností najdete ve vzdálenosti Země .

Ve svém příspěvku 'Wasserstein GAN', Arjovsky et al. použijte metriku Wasserstein-1 jako způsob, jak vylepšit původní rámec Generative Adversarial Networks (GAN), zmírnit problémy s mizivým přechodem a kolapsem režimu. Zvláštní případ normálních distribucí je použit ve Frechet Počáteční vzdálenosti .

Metoda Wasserstein má formální spojení s Procrustesovou analýzou , s aplikací na opatření chirality a na analýzu tvarů.

Vlastnosti

Metrická struktura

To může být prokázáno, že W _p splňuje všechny axiomy hotelového metrika na P _p ( M ). Navíc konvergence s ohledem na W _p je ekvivalentní obvyklé slabé konvergenci opatření plus konvergence prvních p th momentů.

Duální reprezentace W ₁

Následující dvojí zastoupení W ₁ je zvláštní případ duality věta Kantorovich a Rubinstein (1958): když μ a ν mají ohraničený podporu ,

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

kde Lip ( f ) označuje minimální Lipschitzovu konstantu pro f .

Porovnejte to s definicí metriky radonu :

${\ Displaystyle \ rho (\ mu, \ nu): = \ sup \ left \ {\ left. \ int _ {M} f (x) \, \ mathrm {d} (\ mu -\ nu) (x) \ vpravo | {\ text {průběžný}} f: M \ až [-1,1] \ vpravo \}.}$

Pokud je metrika d ohraničena nějakou konstantou C , pak

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

a tak konvergence v radonové metrice (shodná s celkovou variační konvergencí, když M je polský prostor ) znamená konvergenci ve Wassersteinově metrice, ale ne naopak.

Ekvivalence W ₂ a Sobolevova norma negativního řádu

Za vhodných předpokladů je Wassersteinova vzdálenost řádu dva Lipschitz ekvivalentní homogenní Sobolevově normě negativního řádu . Přesněji řečeno, vezmeme -li být propojený Riemannovský rozdělovač vybavený pozitivním měřítkem , pak můžeme definovat pro seminorm ${\ 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)}$

a za podepsané opatření o dvojí normě ${\ Displaystyle \ mu}$${\ displaystyle M}$

${\ Displaystyle \ | \ mu \ | _ {{\ dot {H}}^{-1} (\ pi)} = \ sup {\ bigg \ {} | \ langle f, \ mu \ rangle | \, { \ bigg |} \, \ | f \ | _ {{\ tečka {H}}^{1} (\ pi)} \ leq 1 {\ bigg \}}.}$

Pak jakákoli dvě pravděpodobnostní opatření a on splňují horní hranici ${\ Displaystyle \ mu}$${\ displaystyle \ nu}$${\ displaystyle M}$

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

V opačném směru, pokud a každý má hustotu vzhledem ke standardnímu objemu, na které jsou oba ohraničeny nad některými a mají nezáporné Ricciho zakřivení , pak ${\ Displaystyle \ mu}$${\ displaystyle \ nu}$${\ displaystyle M}$${\ Displaystyle 0 <C <\ infty}$${\ displaystyle M}$

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

Oddělitelnost a úplnost

Pro jakékoli p ≥ 1 je metrický prostor ( P _p ( M ), W _p ) oddělitelný a je úplný, pokud ( M , d ) je oddělitelný a úplný.

Viz také

• Lévyho metrika
• Metrika Lévy – Prochorov
• Celková variační vzdálenost měr pravděpodobnosti
• Dopravní teorie
• Vzdálenost stěhováku Země

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). Gradientní toky v metrických prostorech a v prostoru pravděpodobnostních opatření . Basilej: ETH Zürich, Birkhäuser Verlag. ISBN 3-7643-2428-7.Správa CS1: více jmen: seznam autorů ( odkaz )
• Jordan, Richard; Kinderlehrer, David; Otto, Felix (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 . MR  1617171 .
• Rüschendorf, L. (2001) [1994], „Wassersteinova metrika“ , encyklopedie matematiky , EMS Press

externí odkazy

• „Jaké jsou výhody Wassersteinovy ​​metriky ve srovnání s divergencí Kullback – Leibler?“ . Výměna zásobníku . 1. srpna 2017.