DR-SNE: Density-Regularized Stochastic Neighbor Embedding

Technische Samenvatting: DR-SNE (Density-Regularized Stochastic Neighbor Embedding)

Probleemstelling
Standaard methoden voor dimensiereductie, met name t-SNE en zijn varianten, worden geformuleerd als geometrische problemen die gericht zijn op het behoud van lokale buurverhoudingen. Hoewel deze methoden effectief zijn in het handhaven van conditionele structuur (lokale gelijkenissen), negeren ze impliciet de verdeling van waarschijnlijkheidsmassa over het dataset. Bijgevolg introduceren ze vaak ernstige vervormingen in de datadichtheid, waarbij ze schaarse gebieden uitrekken en dichte gebieden comprimeren. Dit leidt tot embedden die de onderliggende dataverdeling verkeerd weergeven, wat misleidende clustergroottes en ruimtelijke relaties oplevert. Bestaande dichtheidsbewuste benaderingen, zoals DensMAP en DenSNE, proberen dit te mitigeren door consistentie af te dwingen in lokale buurschalen (bijvoorbeeld stralen of bandbreedten). Het artikel betoogt echter dat deze op schaal gebaseerde proxies slechts indirect gerelateerd zijn aan de lokale steekproefdichtheid en gevoelig kunnen zijn voor de embeddingschaal en definities van buurten.

Methodologie
De auteurs stellen DR-SNE (Density-Regularized Stochastic Neighbor Embedding) voor, een herformulering van dimensiereductie als de gezamenlijke uitlijning van twee componenten:

1. Conditionele Structuur: Het vastleggen van lokale relaties (standaard in SNE/t-SNE).
2. Relatieve Dichtheidsstructuur: Het vastleggen van de variatie in waarschijnlijkheidsmassa via lokale dichtheidsstatistieken.

Theoretisch is dit gebaseerd op de decompositie van de Kullback-Leibler (KL)-divergentie tussen gezamenlijke verdelingen in conditionele en marginale componenten. Standaard SNE optimaliseert alleen de conditionele term door marginale verdelingen uniform te houden. DR-SNE introduceert een complementair doel om de marginale dichtheid uit te lijnen.

Algoritmische Implementatie:

• Dichtheidsschatting: Lokale dichtheden in zowel de hoogdimensionale ($X$) als de laagdimensionale ($Z$) ruimten worden geschat met behulp van $k$-nearest neighbor ($k$-NN) afstanden.
• Normalisatie: Deze dichtheidsschattingen ($\rho$) worden genormaliseerd naar een eenheidsgemiddelde om schaalinvariantie te waarborgen.
• Doelfunctie: Het totale verlies $L$ combineert de standaard sparse KL-divergentie ($L_{KL}$) met een dichtheidsregularisatieterm ($L_{dens}$):
  $$L = L_{KL} + \lambda L_{dens}$$
  waarbij $L_{dens}$ het kwadraat van het verschil minimaliseert tussen genormaliseerde log-dichtheidsschattingen:
  $$L_{dens} = \frac{1}{n} \sum_{i=1}^{n} \left( \log \tilde{\rho}^{high}_i - \log \tilde{\rho}^{low}_i \right)^2$$
• Optimalisatie: De methode gebruikt een warm-upfase met vroege exaggratie, gevolgd door optimalisatie via Adam met gradient clipping. De parameter $\lambda$ beheerst de afweging tussen buurtrouw en behoud van dichtheid.

Belangrijkste Bijdragen

1. Theoretische Herformulering: Het artikel formuleert dimensiereductie expliciet als de gezamenlijke uitlijning van conditionele structuur en marginale dichtheid, en identificeert het negeren van de marginale term als de worteloorzaak van dichtheidsvervorming in standaardmethoden.
2. Directe Dichtheidsuitlijning: In tegenstelling tot eerdere werken die vertrouwen op op schaal gebaseerde proxies, lijnt DR-SNE direct genormaliseerde log-dichtheidsschattingen uit. Dit biedt een schaalinvariant mechanisme voor het behoud van relatieve dichtheidsvariaties.
3. Nieuwe Evaluatiemeta: De auteurs introduceren Density Correlation (DC), gedefinieerd als de correlatie tussen genormaliseerde log-dichtheidsschattingen in de originele en embeddruimten, om dichtheidsbehoud kwantitatief te beoordelen.
4. Empirische Validatie: Uitgebreide experimenten tonen aan dat DR-SNE superieur dichtheidsbehoud bereikt in vergelijking met t-SNE, UMAP, PaCMAP, DensMAP en DenSNE, terwijl het concurrerende buurtrouw behoudt.

Resultaten

• Dichtheidsbehoud: Over diverse datasets (Digits, Fashion-MNIST, MNIST, PBMC, Shuttle en synthetische spiralen) behaalt DR-SNE consistent de hoogste Density Correlation-scores. Bijvoorbeeld, op de MNIST-dataset behaalde DR-SNE een DC van 0,991, vergeleken met 0,987 voor DensMAP en 0,118 voor standaard t-SNE.
• Topologie versus Dichtheid-afweging: Ablatiestudies onthullen een duidelijke Pareto-grens. Het verhogen van $\lambda$ verbetert de dichtheidscorrelatie monotoon, maar degradeert geleidelijk de betrouwbaarheid (lokale structuur). Opmerkelijk is dat kleine, niet-nul waarden van $\lambda$ vaak zowel het dichtheidsbehoud als de lokale structuur verbeteren, en fungeren als een stabilisator.
• Prestaties in downstream taken: Bij anomaliedetectietaken (met behulp van kNN, LOF, Isolation Forest en op centroid gebaseerde detectoren) levert DR-SNE winst op, met name in door dichtheid gedreven regimes (bijvoorbeeld Shuttle, Thyroid) waar anomalieën overeenkomen met gebieden met lage dichtheid. Het toont robuustheid over verschillende detectoren heen in vergelijking met methoden die alleen uitblinken met specifieke scoringsfuncties.
• Berekeningskosten: DR-SNE behoudt de $O(n^2)$ tijdscomplexiteit per iteratie van standaard t-SNE vanwege dichte paarwijze interacties, hoewel de auteurs opmerken dat bestaande versnellingsmethoden (bijvoorbeeld Barnes-Hut) kunnen worden toegepast.

Betekenis en Claims
Het artikel beweert dat DR-SNE een "eenvoudige en principiële uitbreiding" biedt aan het stochastische buurframework die een fundamentele beperking van veelgebruikte visualisatietools aanpakt. Door expliciet dichtheidsinformatie op te nemen, biedt DR-SNE een meer trouwe weergave van de onderliggende dataverdeling, met name in hybride datasets die zowel discrete clusters als continue variaties bevatten (bijvoorbeeld single-cell RNA-seq-data).

De auteurs benadrukken dat hun werk suggereert dat dimensiereductie niet enkel als een geometrisch probleem moet worden beschouwd, maar als de uitlijning van complementaire componenten van de dataverdeling. Ze betogen dat hoekpunten-gerichte methoden bij voorkeur blijven voor puur geklusterde of door variëteit gedomineerde settings, dichtheidsbehoudende embedden cruciaal zijn voor statistische analyse, anomaliedetectie en taken waarbij de relatieve dichtheid van datapunten betekenisvolle informatie draagt. De methode biedt een controleerbare afweging, waardoor practitioners de embed kunnen afstemmen op het specifieke structurele regime van hun data.