Optimizing Multidimensional Scaling in Gini Metric Spaces

Technische Samenvatting: Optimalisatie van Multidimensionale Schaling in Gini-Metriekruimten

Probleemstelling
Multidimensionale Schaling (MDS) is een standaardtechniek voor dimensiereductie, met als doel hoogdimensionele data weer te geven in een laagdimensionale geometrische ruimte (doorgaans 2D of 3D) zodanig dat de onderlinge afstanden in de embedding de oorspronkelijke dissimilariteiten benaderen. Klassieke MDS is echter gebaseerd op Euclidische afstanden, die zeer gevoelig zijn voor ruis, uitschieters en zwaarstaartverdelingen. In real-world toepassingen waar data verontreinigd kan zijn of waar latente structuren worden verduisterd door extreme waarden, faalt Euclidische MDS vaak om de ware onderliggende geometrie te behouden. Bovendien kunnen standaardimplementaties (bijvoorbeeld in sklearn) computatie-efficiëntieproblemen vertonen voor grote datasets, en ontbreekt het bestaande robuuste MDS-varianten vaak aan een instelbaar mechanisme om zich aan te passen aan specifieke dataverdelingen.

Methodologie
Het artikel stelt het Gini Multidimensionale Schaling (Gini MDS)-kader voor, dat klassieke MDS uitbreidt door de Euclidische metriek te vervangen door een Genueraliseerde Gini Pseudo-Afstand.

1. Generaliseerde Gini Pseudo-Afstand ($D_{G,\nu}$):

   • In tegenstelling tot standaard Gini-metrieken die uitsluitend vertrouwen op rangordes of waarden, integreert deze pseudo-afstand beide. Deze is gedefinieerd op basis van het Minkowski $p$-norm-concept, maar aangepast om ranginformatie op te nemen.
   • De kerninnovatie is de introductie van een instelbare hyperparameter, $\nu$ (waarbij $\nu > 1$). Deze parameter controleert de weging van de staarten van de verdeling:
     • $\nu = 2$ komt overeen met het minimaliseren van de Gini-index van residuen (vergelijkbaar met mediane regressie).
     • $\nu \in (1, 2)$ legt meer gewicht op het bovenste deel van de verdeling.
     • $\nu > 2$ legt meer gewicht op het onderste deel.
   • De afstand wordt gesymmetriseerd om te waarborgen dat deze voldoet aan de eigenschappen van een pseudo-afstand (symmetrie, niet-negativiteit, driehoeksongelijkheid), hoewel wordt opgemerkt dat de "nul"-eigenschap geldt voor egalitaire verdelingen (waarbij $x = c\mathbf{1}$) evenals voor identieke punten.
   • De structuur is gebaseerd op ranggaten en waargaten, waardoor deze inherent robuust is tegen uitschieters.

2. Optimalisatiealgoritme:

   • Het kader maakt gebruik van een stress-minimalisatiebenadering (Kruskal's Stress) om de optimale latente ruimte te vinden.
   • Algoritme 1 itereren door een bereik van $\nu$-waarden (bijvoorbeeld 1,1 tot 5). Voor elke $\nu$ wordt de Gini pseudo-afstandsmatrix berekend, wordt MDS uitgevoerd om een embedding te genereren, en wordt de stress-score berekend.
   • De optimale $\nu^*$ wordt geselecteerd als die welke de gemiddelde stress over kruisvalidatie-folden minimaliseert.
   • De implementatie maakt gebruik van PyTorch met tensorgebaseerde bewerkingen om GPU-versnelling te benutten, wat aanzienlijke snelheidswinst biedt ten opzichte van standaard CPU-gebaseerde bibliotheken.

Belangrijkste Bijdragen

1. Nieuwe Metriek: Introductie van een Gini pseudo-afstand die waarden en rangordes combineert met een instelbare hyperparameter $\nu$, wat een flexibele verkenning van latente configuraties mogelijk maakt.
2. Robuustheid: Aantonen dat de Gini pseudo-afstand robuust is tegen ruis en uitschieters vanwege de afhankelijkheid van rangverschillen, die de impact van extreme waarden afzwakken.
3. Geoptimaliseerd Kader: Een compleet algoritme voor "Geoptimaliseerde Gini MDS" dat automatisch de beste hyperparameter selecteert om waargenomen dissimilariteiten aan te passen, en hiermee statische Euclidische benaderingen overtreft.
4. Efficiënte Implementatie: Een GPU-versnelde, tensorgebaseerde implementatie in PyTorch die de rekentijd aanzienlijk verkort ten opzichte van standaard sklearn MDS.
5. Uitgebreide Evaluatie: Uitgebreide experimenten op 16 UCI-datasets (met en zonder uitschieters), MNIST-afbeeldingsdata (met Gaussische ruis) en simulaties op zwaarstaartverdelingen.

Experimentele Resultaten

• UCI Datasets (Uitschieterverontreiniging):
  • Op 16 datasets met 2% en 5% verontreiniging presteerde Gini MDS consequent beter dan Euclidische MDS en drie geoptimaliseerde Euclidische varianten (Huber, Sammon, SMACOF) wat betreft Trustworthiness (behoud van lokale structuur) en Nearest Neighbor-metrieken.
  • Hoewel Euclidische methoden soms hogere Silhouet-scores (globale clustering) behaalden bij schone data, toonde Gini MDS superieure prestaties in het behoud van lokale buurten wanneer de data verontreinigd was.
• MNIST Classificatie (Ruis):
  • In een classificatietaken waarbij cijfers 5 en 6 werden onderscheiden met toegevoegde Gaussische ruis, presteerde Gini MDS beter dan Euclidische MDS bij gebruik van een enkele embeddingcomponent.
  • De resultaten suggereren dat Gini MDS meer "compressievermogen" heeft, waardoor meer relevante informatie in het eerste component wordt vastgelegd onder ruisvoorwaarden.
• Zwaarstaartsimulaties:
  • In vergelijking met niet-lineaire methoden (t-SNE, Isomap, UMAP) op zwaarstaartverdelingen behaalde Gini MDS de hoogste Pearson- en Spearman-correlaties tussen de oorspronkelijke en de ingebedde afstandsmatrices.
  • Dit geeft aan dat Gini MDS bijzonder effectief is in het behoud van de globale geometrische structuur (onderlinge afstandrelaties) van data met zware staarten, terwijl andere methoden zich meer richtten op het behoud van lokale buurten.
• Prestaties:
  • De PyTorch-implementatie was aanzienlijk sneller dan sklearn (bijvoorbeeld 9 seconden versus 46 seconden voor de Banknote-dataset met 1.372 instanties).

Betekenis en Claims
Het artikel beweert dat Gini MDS een robuust alternatief biedt voor klassieke MDS, met name voor real-world toepassingen waar data ruis bevat of uitschieters. Door gebruik te maken van de eigenschappen van Gini-statistieken (integratie van rang en waarde) en het optimaliseren van de hyperparameter $\nu$, biedt de methode:

• Verhoogde Robuustheid: Superieure omgang met uitschieters en zwaarstaartverdelingen in vergelijking met Euclidische metrieken.
• Structuurbehoud: Het vermogen om zowel lokale structuur (via trustworthiness) als globale geometrische relaties (via afstandscorrelatie) in de embeddingruimte te behouden.
• Praktische Efficiëntie: Een schaalbare, GPU-bereide implementatie die robuuste dimensiereductie haalbaar maakt voor grotere datasets.

De auteurs concluderen dat hoewel Euclidische MDS effectief blijft voor schone data, het Gini MDS-kader een superieure keuze is voor scenario's met dataverontreiniging, en een flexibel en computatie-efficiënt instrument biedt voor de ontdekking van latente structuren.