Robust Wasserstein barycenter

Probleemstelling

De klassieke Wasserstein-barycentrum (WB) is een krachtig instrument in optimalisatie, statistiek en machine learning om een "gemiddelde" verdeling te vinden van een verzameling kansverdelingen. Het minimaliseert de som van de Wasserstein-afstanden tot een gegeven set verdelingen.

Echter, de klassieke WB heeft twee fundamentele beperkingen:

1. Gevoeligheid voor uitschieters (outliers): Omdat de WB gebaseerd is op het concept van het zwaartepunt, kan de aanwezigheid van enkele extreme waarden (uitschieters) de berekende barycentrum sterk verstoren.
2. Aannames over momenten: De klassieke definitie vereist dat de betrokken kansverdelingen eindige eerste of tweede momenten hebben. Dit is vaak niet het geval in real-world scenario's met zware staarten (heavy-tailed distributions) of ruis.

In traditionele datasets worden uitschieters vaak verwijderd, maar bij de WB, die gedefinieerd is als een centrum van massa over een verzameling kansmaten, is het identificeren en verwijderen van uitschieters complex en niet direct toepasbaar.

Methodologie

De auteurs introduceren de Robuuste Wasserstein-barycentrum (RWB) om deze problemen op te lossen. De kern van hun aanpak bestaat uit drie onderdelen:

1. Robuuste Optimal Transport (ROT):
   De auteurs bouwen voort op het concept van robuuste optimal transport. In plaats van de standaard kostenfunctie $d(x, y)$ te gebruiken, introduceren ze een afgeknotte kostenfunctie:
   $$c^{(\lambda)}(x, y) := \min\{d(x, y), \lambda\}$$
   Hierbij is $\lambda > 0$ een regularisatieparameter die het niveau van afkapping bepaalt. Dit zorgt ervoor dat extreme afstanden niet oneindig grote invloed hebben op de berekening.

2. Definitie van de RWB:
   Gebaseerd op de robuuste $p$-Wasserstein-afstand $W_p^{(\lambda)}$, wordt de RWB gedefinieerd als de verdeling die de verwachte $k$-de macht van de robuuste afstand minimaliseert:
   $$\nu_p^{(\lambda), k} := \arg \min_{\xi} \mathbb{E}\left[ W_p^{(\lambda)}(\Lambda, \xi)^k \right]$$
   Belangrijk: De RWB stelt geen eisen aan de eindigheid van momenten van de invoerverdelingen, wat het toepasbaar maakt op een bredere klasse van data.

3. Berekeningsalgoritme (Free-Support):
   De meeste bestaande algoritmen voor het berekenen van een barycentrum zijn "fixed-support" (gebaseerd op een vast rooster), wat leidt tot de "curse of dimensionality" (exponentiële groei van rekentijd met de dimensie).
   De auteurs stellen een free-support algoritme voor. Dit algoritme optimaliseert zowel de gewichten als de locatie van de steunpunten (support points) van de barycentrum.

   • Ze bewijzen dat de steun van de RWB eindig is als de invoer eindig is.
   • Ze gebruiken een vast-punt algoritme (gebaseerd op een iteratieve update van de steunpunten) dat de som van de robuuste afstanden monotoon verlaagt. Dit omzeilt de beperkingen van rooster-gebaseerde methoden.

Belangrijkste Bijdragen

De paper levert drie hoofdcontributies:

1. Conceptuele Innovatie: Introductie van de RWB als een robuust alternatief voor de klassieke WB, zonder de restrictieve moment-aannames.
2. Theoretische Garanties:
   • Bewijs van existentie: Er bestaat altijd een minimizer voor de RWB.
   • Bewijs van consistentie: De empirische RWB convergeert naar de ware RWB naarmate de steekproefgrootte toeneemt.
   • Karakterisering van de steun-grootte: Voor discrete invoerverdelingen wordt een bovengrens gegeven voor het aantal benodigde steunpunten van de barycentrum.
3. Efficiënt Algoritme: Ontwikkeling van een free-support algoritme dat de "curse of dimensionality" aanpakt en beter presteert dan traditionele fixed-support methoden (zoals IBP) in beeldverwerking.

Resultaten

De auteurs testen hun methode uitgebreid op gesimuleerde en real-world data:

• Beeldverwerking (Ellipsen):
  Bij het genereren van willekeurige ellipsen met toegevoegde uitschieters (ruis) in de hoek, vertoont de klassieke WB vage randen en een verschuiving richting de ruis. De RWB behoudt scherpe randen en blijft stabiel, ongeacht de aanwezigheid van de uitschieters.
• Numerieke Simulaties (Verontreiniging en Zware Staarten):
  • Bij data met variërende percentages verontreiniging (outliers) neemt de afwijking van de WB sneller toe dan die van de RWB.
  • Bij data gegenereerd uit een $t$-verdeling (zware staarten, waar de tweede moment niet bestaat voor lage vrijheidsgraden), presteert de RWB aanzienlijk beter dan de WB.
  • De optimale parameter $\lambda$ (afkappingsniveau) bleek cruciaal; een te kleine of te grote waarde leidt tot suboptimale resultaten, maar een goed gekozen $\lambda$ (bijv. 30 in de simulaties) levert de beste balans op.
• Real-world Data (Aandelenprijzen):
  Bij analyse van dagelijkse log-rendementen van aandelen (waarbij extreme waarden vaak voorkomen), bleek de RWB veel minder gevoelig voor deze uitschieters dan de WB. De RWB berekende een barycentrum dat dichter bij de "schone" verdeling (zonder uitschieters) lag dan de klassieke WB.

Significantie

Dit onderzoek is significant omdat het een fundamentele beperking van de Wasserstein-barycentrum oplost. Door de introductie van de RWB:

• Wordt het mogelijk om robuuste gemiddelden te berekenen over kansverdelingen in scenario's waar data ruis, uitschieters of zware staarten bevat (bijv. in financiële tijdreeksen of medische beeldvorming).
• Wordt de theoretische basis voor robuuste statistiek in de ruimte van kansmaten uitgebreid.
• Biedt het een praktisch, schaalbaar algoritme (free-support) dat de berekeningskosten in hoge dimensies verlaagt, waardoor de methode toepasbaar wordt in complexe machine learning-toepassingen.

De auteurs concluderen dat de RWB een overtuigend alternatief is voor de standaard WB en pleiten voor toekomstig onderzoek naar entropie-geregulariseerde versies en integratie met deep learning-modellen.