Mi is...a Wasserstein-tér?

A Wasserstein-terek olyan speciális metrikus terek, amelynek pontjai valószínűségi mértékek, a pontok közötti távolságot pedig transzport tervek segítségével lehet meghatározni. Ilyen módon ez a cikk az előző számban megjelent „Mi is a... Monge-Kantorovics probléma” című írás folytatása.

Rávilágítandó a transzportelmélet eszközeinek erejére, vázlatosan bemutatjuk a 2018-ban Fields-éremmel kitüntetett Alessio Figalli egyik optimális transzportot használó eredményét. Ezek után néhány motiváló példa érintésével eljutunk az $\mathbb{R}^n$ -re épített Wasserstein-terek definíciójáig. Ugyan az $\mathbb{R}^n$ -nél komplikáltabb terekre is lehetne építkezni, és a definíciók sem lennének sokkal bonyolultabbak, mi megelégszünk ezzel az általánossággal. A Wasserstein-tér néhány érdekes tulajdonságának bemutatása után a cikket egy alkalmazással zárjuk: vázolunk egy eljárást, aminek segítségével egy képet fel lehet ruházni egy másik kép stílusjegyeivel.

1. Az izoperimetrikus egyenlőtlenség és alkalmazásai

Mielőtt rátérünk Figalli és szerzőtársainak eredményére, röviden felidézünk néhány alapfogalmat. Az $\mathbb{R}^n$ tér bizonyos részhalmazait akarjuk majd megmérni, természetes kívánalom, hogy az olyan egyszerű halmazok, mint a gömbök mérhetőek legyenek. Emlékeztetünk, hogy az $x\in\mathbb{R}^n$ középpontú $r$ sugarú nyílt gömb nem más, mint $G_r(x)=\big\{y\in\mathbb{R}^n\;\big\vert\;\vert x-y\vert<r \big\}$ , ahol $x=(x_1,\dots,x_n)$ , $y=(y_1,\dots,y_n)$ és $\vert x-y\vert=\sqrt{\sum_{j=1}^n\vert x_j-y_j\vert^2}$ .

Jelölje $\mathcal{B}(\mathbb{R}^n)$ a legszűkebb olyan halmazrendszert, amely

– tartalmazza az összes nyílt gömböt,
– zárt a komplementer képzésére, azaz ha tartalmazza $A$ -t, akkor tartalmazza $\mathbb{R}^n\setminus A$ -t is,
– ha tartalmazza egy $(A_n)_{n\in\mathbb{N}}$ sorozat minden tagját, akkor tartalmazza az egyesítésüket is.

Ezt a $\mathcal{B}(\mathbb{R}^n)$ halmazrendszert az $\big(\mathbb{R}^n,\vert\cdot\vert\big)$ metrikus tér Borel $\sigma$ -algebrájának nevezzük. A $\mu\colon\mathcal{B}(\mathbb{R}^n)\to[0,1]$ halmazfüggvény egy Borel valószínűségi mérték, ha

a) $\mu(\mathbb{R}^n)=1$ és
b) ha $(A_n)_{n\in\mathbb{N}}$ egy olyan $\mathcal{B}(M)$ -ben haladó halmazsorozat, hogy $j\neq k$ esetén $A_j\cap A_k=\emptyset$ , akkor $\mu\left(\bigcup_{j=1}^{\infty}A_j\right)=\sum_{j=1}^{\infty}\mu(A_j)$ .

Az összes Borel valószínűségi mérték halmazát mostantól $\mathcal{P}(\mathbb{R}^n)$ -nel jelöljük. Külön kiemeljük a $\mathcal{P}(\mathbb{R}^n)$ halmaz két fontos részhalmazát: a Dirac-mértékek $\Delta(\mathbb{R}^n)$ halmazát, és azok véges konvex kombinációinak $\mathcal{F}(\mathbb{R}^n)$ halmazát. Emlékeztetünk, hogy az $x\in\mathbb{\mathbb{R}^n}$ pontra koncentrált Dirac-mérték definíciója: $\delta_x(A)=1$ ha $x\in A$ , és $\delta_x(A)=0$ ha $x\notin A$ . Ebben a cikkben mindig Borel-mértékekkel dolgozunk, ezért a továbbiakban a Borel szót sem a mértékek, sem pedig a mérhető halmazok elé nem tesszük ki.

Felidézzük a transzportelmélet néhány alapfogalmát is. Tegyük fel, hogy adott egy folytonos $c\colon \mathbb{R}^n\times\mathbb{R}^n\to\mathbb{R}_{\geq0}$ költségfüggvény, és két valószínűségi mérték $\mu,\nu\in\mathcal{P}(\mathbb{R}^n)$ . Olyan $T\colon \mathbb{R}^n\to\mathbb{R}^n$ mérhető függvényt keresünk, amelyre

$\displaystyle T_{\char93 }\mu(A):=\mu(T^{-1}(A))=\nu(A)$

teljesül minden $A\subseteq \mathbb{R}^n$ mérhető halmaz esetén. Ilyenkor a $T$ -t transzport leképezésnek, $\nu$ -t pedig a $\mu$ $T$ -szerinti előretoltjának neveztük. Egy ilyen $T$ függvény mentén a teljes transzport költsége

$\displaystyle \int_{\mathbb{R}^n} c(x,T(x))~\operatorname{d}\mu(x).$

Ilyen $T$ függvény persze nem feltétlenül létezik. A probléma Kantorovics-féle megfogalmazásában transzport terveket keresünk, azaz olyan $\pi$ valószínűségi mértékeket az $\mathbb{R}^n\times\mathbb{R}^n$ szorzat téren, amelyeknek marginálisai $\mu$ és $\nu$ . A transzport tervek halmazát $C(\mu,\nu)$ -vel jelöljük.

Megjegyzendő, hogy $C(\mu,\nu)$ soha nem üres, ugyanis $\mu$ és $\nu$ szorzatmértéke megfelel a kritériumnak. Láttuk, hogy egy $\pi$ transzport terv költsége

$\displaystyle \int_{\mathbb{R}^n\times\mathbb{R}^n}c(x,y)~\pi(dx,dy).$

Ki fog derülni, hogy a Wasserstein-tér definíciójához pontosan ezekre a fogalmakra van szükségünk abban a speciális esetben, amikor a $c$ költségfüggvény a távolság egy hatványával egyezik meg.

Most rátérünk Alessio Figalli és szerzőtársainak egy érdekes eredményére. Tudománynépszerűsítő előadásaiban Figalli a problémát Dido legendájával vezeti fel, ezt tesszük mi is. A legenda szerint Iarbás király (Jupiter istenség és Garamantis nimfa fia) annyi területet engedett át országából a Pygmalion zsarnoksága elől meneküló Didónak és követőinek, amennyit egy ökör bőre körülölel. Dido ravasz módon vékony csíkokra vágta a bőrt, és körülkerítette azt a dombot, ahová később Karthago fellegvára épült. De mi köze ennek az izoperimetrikus egyenlőtlenséghez?

Az izoperimetrikus egyenlőtlenség a síkon azt mondja, hogy ha egy egyszerű zárt rektifikálható görbe kerülete $\kappa$ , az általa körbekerített terület pedig $\tau$ , akkor $\kappa\geq 2\sqrt{\pi}\sqrt{\tau}$ . Egyenlőség csak akkor teljesül, ha a szóban forgó görbe a körvonal. Hasonló egyenlőtlenség magasabb dimenzióban is felírható a térfogattal és a felülettel.

Mostantól az egyszerűség kedvéért mindig nagyon szép halmazokkal dolgozunk. Ha azt mondjuk, hogy legyen $E\subseteq\mathbb{R}^n$ , akkor mindig egy korlátos és egyszeresen összefüggő tartományra gondolunk, aminek sima a határa. A $K$ jelölést olyan korlátos konvex nyílt halmazokra tartjuk fenn, amelyek tartalmazzák az origót. Az origó középpontú egység sugarú nyílt gömböt pedig $G$ -vel jelöljük.

1. ábra

Az $E$ halmaz térfogatát $\vert E\vert$ -vel, felszínét (periméterét) pedig $P(E)$ -vel jelöljük. Az $n$ -dimenziós perimetrikus egyenlőtlenség a következőképp szól:

$\displaystyle P(E)\geq n\vert G\vert^{\frac{1}{n}}\vert E\vert^{\frac{n-1}{n}}.$

Egyenlőség pontosan akkor áll fenn, ha $E$ egy gömb. Ennek az az oka, hogy a tér gömbje egy gömb. Hogy ezt hogy kell érteni, arra hamarosan fény derül. Most egy olyan módszerrel vezetjük be a $P(E)$ mennyiséget, ami egy fontos geometriai megfigyeléshez vezet. Jelölje $E_{\varepsilon}$ az $E$ halmaz $\varepsilon$ -nal való felfújtját, azaz minden $x\in E$ köré rakjunk egy $\varepsilon$ sugarú gömböt. Minkowski-összegként ezt úgy írhatjuk, hogy $E+\varepsilon G$ . Meg lehet mutatni, hogy ekkor

$\displaystyle \vert E_{\varepsilon}\vert=\vert E\vert+\varepsilon P(E)+o(\varepsilon),$

ahol az utolsó tag olyan kicsi, hogy még $\varepsilon$ -nal osztva is eltűnik, és így

$\displaystyle P(E)=\lim_{\varepsilon\to0}\frac{\vert E+\varepsilon G\vert-\vert E\vert}{\varepsilon}.$

Magyarul a $P(E)$ semmi mástól nem függ, mint $E$ -től és $G$ -től. Ez a felírás lehetőséget ad arra, hogy bevezessük az analóg fogalmat olyan terekben, amelyeknek tulajdonságai nem függetlenek az iránytól. Gondolhatunk arra, hogy egy fizikai jelenséget írunk le, és különböző irányokban különböző erők hatnak. A fenti 1. ábra azt mutatja, hogy ha a $G$ gömböt lecseréljük $K$ -ra, akkor az $x$ vektor „hossza” kisebb lesz, hiszen $K$ -t nem kell annyiszorosára fújni mint $G$ -t, hogy az $x$ -et elnyelje. Továbbá előfordulhat, hogy egy origó körüli forgatással lemegyünk a gömbről. Ez azt mutatja, hogy a kék szaggatott nyíllal jelölt irányban máshogy skálázódik át hossz, mint a nem szaggatott kék nyíl irányában.

Mostantól tehát a gömb szerepét egy origót tartalmazó konvex nyílt $K$ halmaz játssza, a $K$ -szerinti perimétert pedig az alábbi formulával definiáljuk:

$\displaystyle P_K(E)=\lim_{\varepsilon\to0}\frac{\vert E+\varepsilon K\vert-\vert E\vert}{\varepsilon}.$

Wulff már 1901-ben megmutatta [16], hogy ebben az anizotróp környezetben is igaz az egyenlőtlenség, persze $G$ helyett $K$ -val

$\displaystyle P_K(E)\geq n\vert K\vert^{\frac{1}{n}}\vert E\vert^{\frac{n-1}{n}}.$

Az egyenlőtlenség pontosan akkor teljesül egyenlőséggel, ha $E$ nagyítástól és eltolástól eltekintve megegyezik $K$ -val, vagyis $E=x+rK$ alkalmas $x\in\mathbb{R}^n$ -re és $r>0$ -ra. Tehát az derült ki, hogy az optimális konfigurációkat mindig a tér szerkezetét meghatározó (vagy ha úgy tetszik, a gömb szerepét betöltő) $K$ halmaz adja. Ezt a $P_K(E)$ mennyiséget Wulff a felületi energia leírására alkalmazta kristályok egyensúlyi konfigurációjának tanulmányozásakor. Az egyensúlyi konfigurációt emiatt Wulff-alaknak nevezik. De hogy jön ide az optimális transzport?

Figalliék a [4] cikkben megadták a fenti anizotróp egyenlőtlenségnek egy olyan bizonyítását, amelyik a transzportelmélet néhány nagyon mély eredményét használta. Ehhez először is mértékké kellett változtatni $E$ -t és $K$ -t:

$\displaystyle \mu_E(A):=\frac{\vert A\cap E\vert}{E},\quad\mu_K(A):=\frac{\vert A\cap K\vert}{\vert K\vert}\qquad(A\in\mathcal{B}(\mathbb{R}^n)).$

Tulajdonképpen $E$ -n és $K$ -n egyenletesen szétterítettünk egy-egy egységnyi tömeget. Amit kaptunk, az két olyan mérték, amihez Brenier és McCann nagyon szép eredményei (lásd [1,11,12]) szerint létezik $T\colon \mathbb{R}^n\to\mathbb{R}^n$ transzport leképezés, ami átviszi $\mu_E$ -t $\mu_K$ -ba. Sőt, ez a $T$ előáll, mint egy alkalmas $\varphi\colon\mathbb{R}^n\to\mathbb{R}$ konvex függvény gradiense. Tehát a transzportelmélet segítségével be lehetett hozni a képbe két függvényt $T$ -t és $\varphi$ -t, majd ezek segítségével meg tudtak becsülni néhány fontos mennyiséget. Így például az egyenlőtlenség két oldala közötti deficitet mérő

$\displaystyle D(E):=\frac{P_K(E)}{n\vert K\vert^{\frac{1}{n}}\vert E\vert^{\frac{n-1}{n}}}-1$

mennyiséget, és az $E$ és $K$ alakjának eltérőségét mérő aszimmetriaindexet

$\displaystyle A(E):=\inf\left\{\frac{\vert E\ominus(x_0+rK)\vert}{\vert E\vert}\;\Bigg\vert\;x_0\in\mathbb{R}^n, r^n\vert K\vert=\vert E\vert\right\}.$

Az $A(E)$ definíciójában lévő $\ominus$ szimbólum a szimmetrikus differencia, tehát

$\displaystyle U\ominus V=(U\setminus V)\cup(V\setminus U).$

Megmutatták, hogy egy alkalmas $n$ -től függő $C(n)$ konstanssal

$\displaystyle A(E)\leq C(n)\sqrt{D(E)}.$

Ezeket az eredményeket felhasználva az [5] cikkben azt vizsgálták, hogy egy külső energiaforrás hatására hogyan változik meg egy kristály alakja. A sematikus 2. ábrán $K$ a kék sokszög, amely a kristály egyensúlyi állapotát mutatja, $E$ pedig az a pirossal jelölt alakzat, amit a hevítéssel kapunk. Figalliék megmutatták, hogy $E$ egyenletesen közel van $K$ -hoz, sőt a közelség mértékét egy olyan konstanssal tudták kontrollálni, ami csak a tér dimenziójától, $K$ felületi energiájától, és a rendszerhez hozzáadott energiától függ.

2. ábra

2. Speciális metrikus terek

Röviden emlékeztetünk a metrikus tér fogalmára. Legyen $M$ egy nemüres halmaz, amelyen adott egy $\varrho\colon M\times M\to\mathbb{R}_{\geq0}$ függvény, amely teljesíti az

i) minden $x,y\in M$ -re $\varrho(x,y)=0\Longleftrightarrow x=y$ ,

ii) minden $x,y\in M$ -re $\varrho(x,y)=\varrho(y,x)$ ,

iii) minden $x,y,z\in M$ -re $\varrho(x,y)\leq\varrho(x,z)+\varrho(z,y)$ .

feltételeket. Ekkor a $\varrho$ függvényt metrikának, a $\varrho$ -val ellátott $M$ halmazt (röviden az $(M,\varrho)$ párt) metrikus térnek nevezzük. Mostantól olyan speciális metrikus terekről lesz szó, amelyeknél $M$ szerepét az $\mathbb{R}^n$ tér Borel valószínűségi mértékeinek egy-egy kitüntetett részhalmaza játssza.

Az egyszerűség kedvéért tegyük fel most, hogy a mértékek a valós számegyenesen élnek, azaz $n=1$ . Ebben a speciális esetben minden $\mu\in \mathcal{P}(\mathbb{R})$ mérték helyett tekinthetjük az ő eloszlásfüggvényét, azaz az

$\displaystyle F_{\mu}\colon\mathbb{R}\to[0,1];\qquad F_{\mu}(t):=\mu((-\infty,t])$

függvényt. A 3. ábrán a $\mu=\frac{1}{2}\delta_{-\frac{1}{2}}+\frac{1}{4}\delta_{1}+\frac{1}{4}\delta_{\frac{3}{2}}\in\mathcal{F}(\mathbb{R})$ és a $\nu=\delta_{\frac{7}{8}}\in\Delta(\mathbb{R})$ mértékekhez tartozó eloszlásfüggvények láthatók. Egy eloszlásfüggvény általában nem szigorúan monoton, így a hagyományos értelemben vett inverzéről nem beszélhetünk. Ennek ellenére definiálhatunk egyfajta általánosított inverzet:

$\displaystyle F^{-1}_{\mu}\colon(0,1)\to\mathbb{R};\qquad F^{-1}_{\mu}(s):=\sup\{t\in\mathbb{R}\mid F_{\mu}(t)\leq s\}.$

A 4. ábrán a fenti eloszlásfüggvények általánosított inverzei láthatók.

3. ábra

4. ábra

Ismerkedjünk meg három olyan nevezetes metrikával, amelyeket eloszlásfüggvények segítségével definiálnak.

2.1. A Kolmogorov–Smirnov távolság

Két valószínűségi mérték Kolmogorov–Smirnov távolságát a

$\displaystyle d_{KS}(\mu,\nu):=\sup_{x\in\mathbb{R}}\vert F_{\mu}(x)-F_{\nu}(x)\vert$

formulával definiáljuk. Tehát $d_{KS}(\mu,\nu)<\varepsilon$ , ha $F_{\nu}$ az $F_{\mu}$ -re ilesztett $\varepsilon$ -sávon belül halad (lásd 5. ábra). Ez a metrika ismerős lehet azoknak, akik már találkoztak a Kolmogorov-Smirnov próbával, amelyet a statisztikában illeszkedésvizsgálatra, illetve homogenitásvizsgálatra használnak.

5. ábra

2.2. A Lévy-távolság

Második példánk a Lévy-metrika, az egyik olyan metrika, ami a gyenge konvergenciát metrizálja. Két valószínűségi mérték Lévy-távolságát így definiáljuk:

$\displaystyle d_L(\mu,\nu)=\inf\{\varepsilon>0\mid \forall x\in\mathbb{R}\colon... ...silon )-\varepsilon \leq F_{\nu}(x)\leq F_{\mu}(x+\varepsilon )+\varepsilon\}.$

Az alábbi 6. ábra azt szemlélteti, hogy egy $\varepsilon$ érték mikor elégíti ki a definícióban látható egyenlőtlenség láncot.

6. ábra

Azt látjuk, hogy $F_{\nu}$ -nek az $F_{\mu}$ átlós irányban vett $\sqrt{2}\varepsilon$ -nal való eltoltjai között kell haladni. A két ábra első ránézésre elég hasonló, de nem szabad elfelejteni, hogy a Lévy-metrikánál a függvények változójában is történik eltolás. Ezáltal a metrika érzékeny lesz nem csak arra, hogy az $F_{\mu}$ és $F_{\nu}$ egy adott $x$ pontban mennyire tér el egymástól, hanem arra is, hogy a számegyenes $x$ -hez közeli pontjaiban hogyan alakulnak az eloszlások.

Erre a tényre elég jól rávilágít, ha kiszámoljuk két Dirac-mérték távolságát. Ha $x,y\in\mathbb{R}$ két tetszőleges pont, akkor $d_{KS}(\delta_x,\delta_y)=1$ , míg $d_L(\delta_x,\delta_y)=\min\{\vert x-y\vert,1\}$ . Azt látjuk, hogy a Kolmogorov-Smirnov metrika semmilyen információt nem ad vissza $x$ és $y$ távolságáról, azaz $\vert x-y\vert$ -ról. Ezzel szemben a Lévy-metrika segítségével ki tudjuk olvasni a tartó pontok távolságát, amennyiben az kisebb, mint 1.

Ezen a ponton rátérhetünk a transzport tervekhez köthető metrikák tárgyalására.

2.3. A Kantorovics-távolság

A Lévy-metrikát általában kicsi mennyiségek becslésére alkalmazzák, így nem okoz gondot, hogy a metrika semmit nem tud mondani azokról a mértékekről, amelyek egymástól távol vannak. Ha olyan problémát akarunk kezelni, ahol nem csak kicsi mennyiségekkel kell dolgozni, akkor másik metrikát kell használnunk. Ahhoz hogy a következő definíció értelmes legyen, meg kell szorítanunk a valószínűségi mértékek $\mathcal{P}(\mathbb{R})$ halmazát. Vegyük azokat a valószínűségi mértékeket, amelyeknek véges a várható értéke. Ha $\mu$ és $\nu$ két ilyen mérték, akkor a

$\displaystyle d_K(\mu,\nu):=\int_{-\infty}^{+\infty}\vert F_{\mu}(t)-F_{\nu}(t)\vert~\mathrm{d}t$

integrál véges. Azt látjuk, hogy egyrészt $d_K(\delta_x,\delta_y)=\vert x-y\vert$ , másrészt azt is megsejthetjük, hogy ennek a metrikának már köze lesz a szállítási feladatokhoz.

7. ábra

Erre később visszatérünk, sejtésünket egyelőre a 7. ábrával szemléltetjük. Tekintsük megint a 3. ábrán látható mértékeket. A definícióban szereplő integrál értéke éppen a (különböző színekkel jelölt) téglalapok összterülete. Egy-egy téglalap területe pedig nem más, mint a megfelelő súlyok mozgatásának költsége, ha $1$ egység $x$ -ből $y$ -ba való mozgatásának költsége $\vert x-y\vert$ . Valójában amit itt látunk (a véges várható értékű mértékek halmaza a Kantorovics-metrikával ellátva) egy Wasserstein-tér. Hogy pontosan hogyan kell ezt érteni, az a következő fejezetből kiderül.

3. A $\mathcal{W}_p(\mathbb{R}^n)$ Wasserstein-tér

Rátérünk a Wasserstein-tér definíciójára. Legyen $p\geq1$ egy rögzített szám. Jelölje $\mathcal{P}_p(\mathbb{R}^n)$ a véges $p$ -edik momentumú valószínűségi mértékek halmazát

$\displaystyle \mathcal{P}_p(\mathbb{R}^n):=\left\{\mu\in\mathcal{P}(\mathbb{R}^... ...athbb{R}^n\colon \int_{\mathbb{R}^n}\vert x-x_0\vert^p~d\mu(x)<\infty\right\}.$

Ez a mértékcsalád szolgáltatja a $p$ -Wasserstein-tér alaphalmazát. Noha nem egészen magától értetődő, be lehet bizonyítani, hogy a

$\displaystyle d_{\mathcal{W}_p}(\mu,\nu):=\left(\inf_{\pi\in C(\mu,\nu)}\int\limits_{\mathbb{R}^n\times\mathbb{R}^n} \vert x-y\vert^p~d\pi(x,y)\right)^{1/p}$

kétváltozós függvény metrika a $\mathcal{P}_p(\mathbb{R}^n)$ halmazon. A $d_{\mathcal{W}_p}$ függvényt $p$ -Wassertein-távolságnak, a $(\mathcal{P}_p(\mathbb{R}^n),d_{\mathcal{W}_p})$ párt az $\mathbb{R}^n$ feletti $p$ -Wasserstein-térnek nevezzük és röviden $\mathcal{W}_p(\mathbb{R}^n)$ -nel jelöljük.

Világos a kapcsolat a metrika és a transzport probléma között: két mérték távolsága nem más, mint az optimális transzport költsége a $c(x,y):=\vert x-y\vert^p$ költségfüggvény mellett. Megjegyezzük, hogy Wasserstein-teret bármilyen szeparábilis metrikus térre lehet építeni. Azaz ha $(M,\varrho)$ egy ilyen tér, akkor $\mathbb{R}^n$ helyére $M$ -et, $\vert x-y\vert$ helyére $\varrho(x,y)$ -t írva és a transzport terv fogalmát értelemszerűen módosítva a $\mathcal{W}_p(M)$ Wasserstein-tér definícióját kapjuk.

Könnyű meggondolni, hogy ha $\mu$ és $\nu$ közül legalább az egyik egy Dirac-mérték, akkor $C(\mu,\nu)$ halmaz egyetlen eleme a szorzatmérték, és így a távolság könnyen kiszámítható. Egy ilyen egyszerű számítás mutatja, hogy a Wasserstein-távolságból ki lehet olvasni az alul fekvő tér metrikáját:

$\displaystyle d_{\mathcal{W}_p}(\delta_x,\delta_y)=\vert x-y\vert\qquad(x,y\in\mathbb{R}^n).$

Azt is mondhatnánk, hogy a Wasserstein-tér alján Dirac-mértékek formájában ott ül az $\mathbb{R}^n$ -nek egy másolata. Ezek a Dirac-mértékek a térnek egyfajta építőkövei abban az értelemben, hogy tetszőleges $\mu\in\mathcal{W}_p(\mathbb{R}^n)$ -hez és $\varepsilon>0$ -hoz van olyan $\nu=\sum_{j=1}^k\alpha_j\delta_{x_j}\in\mathcal{F}(\mathbb{R}^n)$ mérték, amelyre $d_{\mathcal{W}_p}(\mu,\nu)<\varepsilon$ .

Felmerülhet a kérdés, hogy különböző $p$ értékekre a $\mathcal{W}_p(\mathbb{R}^n)$ terek mennyire térnek el egymástól. Az egyszerűség kedvéért ismét az $n=1$ esetet, tehát a számegyenes esetét fogjuk vizsgálni. A $p$ -Wasserstein-metrika

$\displaystyle d_{\mathcal{W}_p}(\mu,\nu):=\left(\inf_{\pi\in C(\mu,\nu)}\int\limits_{\mathbb{R}\times\mathbb{R}} \vert x-y\vert^p~d\pi(x,y)\right)^{1/p}$

definícióját látva az embernek az a benyomása támad, hogy amit lát, az az $L^p$ függvénytér mértékelméleti analogonja. Ebben az esetben egy egyszerű analógiánál többről van szó: a $\mathcal{W}_p(\mathbb{R})$ Wasserstein-tér beágyazható az $L^p\big((0,1)\big)$ térbe az általánosított inverzek segítségével. Nevezetesen, minden $\mu,\nu\in\mathcal{W}_p(\mathbb{R})$ -re

$\displaystyle d_{\mathcal{W}_p} (\mu,\nu)=\left(\int_0^1\vert F_{\mu}^{-1}(t)-F... ...~\mathrm{d}t\right)^{\frac{1}{p}}=\Vert F_{\mu}^{-1}-F_{\nu}^{-1}\Vert _{L^p}.$

Ha egy pillanatra visszagondolunk az 7. ábrára és a Kantorovics-metrikára, akkor egy egyszerű integrál átalakítással megállapíthatjuk, hogy ott éppen az $1$ -Wasserstein-távolságot láttuk.

A fenti $\mathcal{W}_p(\mathbb{R})\hookrightarrow L^p\big((0,1)\big)$ beágyazásnak a létezéséből már sejthető, hogy különböző $p$ értékekre a $\mathcal{W}_p(\mathbb{R})$ terek szerkezete eltérő, és hogy a $p=1$ és a $p=2$ esetek különlegesek. A $p=1$ azért, mert az $L^p$ $(p\geq1)$ terek közül az $L^1$ az egyetlen, aminek a normája nem szigorúan konvex, a $p=2$ pedig azért, mert az $L^p$ terek között az $L^2$ az egyetlen Hilbert tér.

A $\mathcal{W}_2(\mathbb{R})$ tér gazdagságát jól mutatja, hogy a többi $\mathcal{W}_p(\mathbb{R})$ térrel összehasonlítva sokkal több szimmetriája van. Szimmetria alatt olyan bijektív $\Phi\colon\mathcal{W}_p(\mathbb{R})\to\mathcal{W}_p(\mathbb{R})$ leképezéseket értünk, amelyek megtartják a távolságot, azaz

$\displaystyle d_{\mathcal{W}_p}(\Phi(\mu),\Phi(\nu))=d_{\mathcal{W}_p}(\mu,\nu)\qquad(\mu,\nu\in\mathcal{W}_p(\mathbb{R})).$

Be lehet bizonyítani, hogy a $\mathcal{W}_p(\mathbb{R})$ tér szimmetriái a $p\neq 2$ esetben éppen a számegyenes szimmetriáinak feleltethetők meg (lásd [7]). Azaz $\Phi$ pontosan akkor szimmetriája $\mathcal{W}_p(\mathbb{R})$ -nek, ha ő az $\mathbb{R}$ egy $\phi$ szimmetriájának az előretoltja

$\displaystyle \Phi(\mu)(A)=\mu(\phi^{-1}(A))\qquad(A\in\mathcal{B}(\mathbb{R})).$

Egy véges tartójú mértéken könnyű is szemléltetni a $\Phi$ hatását, mindössze a tartópontokat kell mozgatni:

$\displaystyle \Phi\left(\sum_{j=1}^k\alpha_j\delta_{x_j}\right)=\sum_{j=1}^k\alpha_j\delta_{\phi^{-1}(x_j)}.$

Azt jól tudjuk, hogy mik a számegyenes szimmetriái: eltolások és csúsztatva tükrözések. Innen könnyű meggondolni, hogy ha $\Phi$ a $\mathcal{W}_p(\mathbb{R})$ -nek $(p\neq2)$ egy olyan szimmetriája, ami két Dirac-mértéket helyben hagy, akkor minden mértéket helyben hagy. Tehát a tér meglehetősen merev. Ezzel szemben Kloeckner bebizonyította (lásd [9]), hogy a $\mathcal{W}_2(\mathbb{R})$ térnek van egy egész sereg olyan egzotikus szimmetriája, ami minden Dirac-mértéket fixen hagy, de mégsem igaz, hogy $\Phi(\mu)=\mu$ minden $\mu\in\mathcal{W}_2(\mathbb{R})$ -re. Általában is igaz, hogy a $2$ -Wasserstein-terek struktúrája sokkal gazdagabb, emiatt az alkalmazásokban legtöbbször ezekkel a terekkel találkozhatunk.

4. Wasserstein stílustranszfer

Az optimális transzport, illetve a hozzá kötődő metrikák így például a Wasserstein-metrika nagy előnye, hogy nem csak egy számértéket rendelnek a mértékpárokhoz, de arra vonatkozóan is szolgálnak információval, hogy hogyan transzformálható át egyik mérték a másikba. A $\mathcal{W}_p(\mathbb{R})$ esetben ez könnyen látható: az eloszlásfüggvények általánosított inverzeit kell egymásba mozgatni, ahogy az a 8. ábrán látható.

8. ábra

De nem csak a valós számok, vagy $\mathbb{R}^n$ esetén ennyire szép a helyzet. Általánosabban, ha $M$ egy Riemann-sokaság, akkor a $\mathcal{W}_2(M)$ tér nagyon jó geometriai tulajdonságokkal rendelkezik. Emiatt a transzportelméletnek rengeteg alkalmazása van nem csak az elméleti matematikában, hanem az alkalmazott tudományokban is. Így például a jel- és képfeldolgozásban [10], [14], az alakfelismerésben [8], a szín és textúra modellezésben [3], [15], vagy a gépi tanulásban [2], [6]. A cikket egy képmanipuláló eljárás vázlatos bemutatásával zárjuk. A feladat a következő: adott két kép, $A$ és $B$ .

A. ábra

B. ábra

Az $A$ képet akarjuk manipulálni úgy, hogy az eredmény rendelkezzen a $B$ stílusjegyeivel.

A feladatot egy konvolúciós neurális háló végzi el: beazonosítja a két kép jellegzetességeit, és átkódolja őket egy-egy valószínűségi mértékké. Jelölje ezeket a mértékeket $\mu_A,\mu_B\in\mathcal{W}_2(\mathbb{R}^n)$ . Innentől kezdve a $\mathcal{W}_2(\mathbb{R}^n)$ Wasserstein-téren dolgozunk: egy olyan $\nu\in\mathcal{W}_2(\mathbb{R}^n)$ mértéket keresünk, amit ha visszakódolunk, akkor olyan képet kapunk, ami rendelkezik a kívánt tulajdonsággal. Sőt, nem is elégszünk meg ennyivel, a stilizálás erősségét is be akarjuk állítani.

Vegyük szemügyre a következő kifejezést rögzített $t\in[0,1]$ mellett:

$\displaystyle (1-t)d_{\mathcal{W}_2}^2(\nu,\mu_A)+td_{\mathcal{W}_2}^2(\nu,\mu_B).$

Az összeg első tagja arról ad információt, hogy ha $\nu$ -t kódoljuk vissza, akkor mennyit vesztünk $A$ -ból, a második tag pedig arról, hogy mennyit vesztünk $B$ -ből. Látjuk, hogy ha $t$ közel van $1$ -hez, akkor a stilizálás nagyon erős, hiszen a kifejezés értékébe az első tag alig szól bele. Ha pedig $t$ kicsi, akkor a stilizálás gyenge. A $t$ kívánt értékre való beállítása után a fenti kifejezés csak a $\nu$ -nek függvénye, a feladat az, hogy minimalizáljuk a veszteségek összegét. Ez a feladat megoldható, sőt egyetlen megoldása van, jelölje ezt $\nu_t$ . Ezt a $\nu_t$ mértéket dekódolva a kívánt erősséggel stilizált képet kapjuk. Világos, hogy $\nu_0=\mu_A$ és $\nu_1=\mu_B$ . Az már kevésbé világos, de igaz, hogy a minimalizáló mértékek által alkotott $(\nu_t)_{t\in[0,1]}$ sereg egy $\mu_A$ -t $\mu_B$ -vel összekötő geodetikus görbét határoz meg. Két mérték ilyen módon való összekötését McCann-interpolációnak nevezik.

Végül megjegyezzük, hogy a transzfer bemutatásánál két nehézséget is átugrottunk: az első, hogy hogyan kódolja és dekódolja a neurális háló a képeket/mértékeket. A másik probléma, hogy technikailag hogyan oldja meg az ember a minimalizálási feladatot, vagy általában, hogyan lehet hatékonyan kiszámolni a $2$ -Wasserstein-távolságot. Erről az olvasó többet is megtudhat a [13] cikkben.

A cikk az ITM és az NKFIH ÚNKP-19-4-BGE-1 és PD128374 kódszámú projektjeinek, valamint az MTA Bolyai János Kutatási Ösztöndíjának támogatásával készült.

Irodalomjegyzék

[1] Y. Brenier, Polar factorization and monotone rearrangement of vector-valued functions, Commun. Pure Appl. Math. 44(4) (1991), 375–417.
: [2] N. Courty, R. Flamary, D. Tuia, Domain adaptation with regularized optimal transport, Machine Learning and Knowledge Discovery in Databases, Springer, 274–289.
: [3] S. Ferradans, G.S. Xia, G. Peyré, J.F. Aujol, Static and dynamic texture mixing using optimal transport, Springer; 2013.
: [4] A. Figalli, F. Maggi, A. Pratelli, A mass transportation approach to quantitative isoperimetric inequalities, Invent. Math. 182 (2010), no. 1, 167–211.
: [5] A. Figalli, F. Maggi, On the shape of liquid drops and crystals in the small mass regime, Arch. Ration. Mech. Anal. 201 (2011), no. 1, 143–207.
: [6] C. Frogner, C. Zhang, H. Mobahi, M. Araya, T. A. Poggio, Learning with a Wasserstein loss, Advances in Neural Information Processing Systems, 2015:2044–2052.
: [7] Gy. P. Gehér, T. Titkos, D. Virosztek, Isometric study of Wasserstein spaces – The real line, Trans. Amer. Math. Soc., Volume 373, Number 8, August 2020, Pages 5855--5883.
: [8] S. Haker, L. Zhu, A. Tannenbaum, S. Angenent, Optimal mass transport for registration and warping. International Journal of Computer Vision. 2004;60(3):225–240.
: [9] B. Kloeckner, A geometric study of Wasserstein spaces: Euclidean spaces, Annali della Scuola Normale Superiore di Pisa - Classe di Scienze IX, 2 (2010), 297–323.
: [10] S. Kolouri, A.B. Tosun, J.A. Ozolek, G.K. Rohde, A continuous linear optimal transport approach for pattern analysis in image datasets. Pattern Recognition. 2016;51:453–462.
: [11] R.J. McCann, Existence and uniqueness of monotone measure-preserving maps, Duke Math. J., 80 (2) (1995), 309–323.
: [12] R. J. McCann, A convexity principle for interacting gases, Adv. Math. 128 (1) (1997), 153–179.
: [13] Y. Mroueh, Wasserstein Style Transfer, arxiv:1905.12828
: [14] S. R. Park, S. Kolouri, S. Kundu, G.K. Rohde GK, The cumulative distribution transform and linear pattern classification, Applied and Computational Harmonic Analysis. 2017.
: [15] J. Rabin, S. Ferradans, N. Papadakis, Adaptive color transfer with relaxed optimal transport, Image Processing (ICIP), IEEE 2014.; pp. 4852–4856.
: [16] G. Wulff, Zur Frage der Geschwindigkeit des Wachstums und der Auflösung der Krystallflagen, Zeitschrift für Krystallographie und Mineralogie. 34 (5/6) (1901) 449–530.

Titkos Tamás

Rényi Alfréd Matematikai Kutatóintézet

és Budapesti Gazdasági Egyetem

Információk

Főmenü

Mi is...a Wasserstein-tér?