On the continuum limit of t-SNE for data visualization

Dit artikel bewijst dat de Kullback-Leibler-divergentie van t-SNE convergeert naar een continu variatieprobleem met niet-convexe gradiëntregularisatie en een straffing op de waarschijnlijkheidsdichtheid, wat de empirische vermogens van t-SNE om data op willekeurige manieren te scheuren theoretisch onderbouwt, hoewel de goedgesteldheid van dit probleem in hogere dimensies slechts gedeeltelijk is opgelost.

De kern

De Grote Reis: Hoe t-SNE Data in Beeld Brengt (en waarom dat soms raar gaat)

Stel je voor dat je een enorme berg met duizenden verschillende soorten fruit hebt. Je wilt ze sorteren en in een platte doos leggen, zodat je snel kunt zien welke vruchten op elkaar lijken (bijvoorbeeld alle appels bij elkaar en alle peren bij elkaar). Dit is precies wat t-SNE doet. Het is een populaire techniek om complexe, hoge-dimensional data (zoals foto's, woorden of genen) te vertalen naar een simpel plaatje dat we met onze ogen kunnen zien (meestal op een 2D-scherm).

Maar hier is het probleem: wiskundigen weten eigenlijk niet precies waarom t-SNE zo goed werkt, of waarom het soms vreemde resultaten geeft. Dit artikel probeert de "onderliggende regels" van t-SNE te ontdekken door te kijken naar wat er gebeurt als je oneindig veel data-punten hebt. Ze noemen dit de continuüm limiet.

Hier is hoe de auteurs dit uitleggen, stap voor stap:

1. Het Kruideniersprincipe: Aantrekken en Afstoten

t-SNE werkt als een spelletje met magneetjes en ballonnen.

• Aantrekking: Als twee data-punten in de originele wereld (bijv. twee foto's van katten) op elkaar lijken, wil t-SNE ze in de nieuwe wereld dicht bij elkaar houden.
• Afstoting: Als twee punten heel verschillend zijn, wil t-SNE ze uit elkaar duwen, zodat ze niet op elkaar gaan liggen.

De auteurs hebben bewezen dat als je naar oneindig veel punten kijkt, deze krachten veranderen in een wiskundige formule. Deze formule heeft twee delen:

1. Een aantrekkingskracht die probeert de structuur van de data te behouden.
2. Een afstotingskracht die probeert de punten gelijkmatig over het scherm te verspreiden, zodat ze niet allemaal in één hoopje samenkomen.

2. De "Scheur" in de Realiteit (Wanneer het goed gaat)

De auteurs kijken eerst naar het eenvoudigste geval: als je data en het plaatje beide één dimensie hebben (een rechte lijn).

• De verrassing: Ze ontdekten dat in dit geval er precies één perfecte manier is om de data te ordenen. Het is als het leggen van een rij stenen op een rechte lijn; er is één duidelijke, gladde oplossing.
• De valkuil: Maar t-SNE is niet altijd zo netjes. De wiskunde laat zien dat je ook "slechte" oplossingen kunt vinden waarbij de lijn plotseling breekt of springt.
  • Vergelijking: Stel je voor dat je een lange touw moet leggen. De beste manier is een rechte lijn. Maar t-SNE kan soms beslissen om het touw in stukken te knippen en de stukken ver uit elkaar te leggen. Dit verklaart waarom t-SNE in de praktijk soms clusters (groepen) creëert die er in de echte data niet waren, of waarom het data "doorsnijdt" op vreemde plekken.

3. De "Knoestige" Wereld (Wanneer het misgaat)

Nu wordt het lastig. In de echte wereld hebben we vaak veel data-dimensies (bijv. 1000 eigenschappen van een foto) die we naar een klein scherm (2 dimensies) willen persen.

• Het probleem: De auteurs bewijzen dat in dit geval (van 1000 naar 2) er geen perfecte oplossing bestaat.
  • Vergelijking: Probeer een grote, bolle aardappel in een platte pannenkoek te veranderen zonder dat hij uit elkaar valt. Als je te hard duwt, krijg je oneindig veel kleine scheurtjes en micro-structuren.
• De conclusie: De wiskundige formule die t-SNE probeert te minimaliseren, heeft geen "bottom" (een laagste punt). Het is alsof je een bal op een heuvel probeert te laten rollen, maar de heuvel is zo oneindig steil en glibberig dat de bal nooit stopt. De data blijft "micro-structuur" creëren: heel fijne, chaotische patronen die je op het scherm ziet als ruis of vreemde patronen.

4. De Verwante "Perona-Malik" Vergelijking

De auteurs merken op dat de wiskunde achter t-SNE heel erg lijkt op een beroemde, maar beruchte vergelijking uit de beeldverwerking, genaamd Perona-Malik.

• Die vergelijking wordt gebruikt om foto's te ontdoen van ruis (denoising).
• Het probleem is dat deze vergelijking wiskundig "ziek" is (ill-posed): hij kan leiden tot onstabiele resultaten.
• De les: Het feit dat t-SNE werkt, is eigenlijk een wonder. Het is alsof je een auto bestuurt die theoretisch zou moeten exploderen, maar in de praktijk toch redelijk rijdt. De "ziekte" van de vergelijking is precies wat t-SNE in staat stelt om scherpe randen te maken en clusters te scheiden, maar het maakt het ook onvoorspelbaar.

5. Wat betekent dit voor jou?

Dit artikel is belangrijk omdat het eindelijk uitlegt waarom t-SNE soms "raar" doet:

• Het is niet altijd eerlijk: Omdat de wiskunde toestaat dat de data in stukken wordt geknipt, kan t-SNE soms groepen creëren die er niet echt zijn, of echte groepen uit elkaar halen.
• Het hangt af van de instellingen: De manier waarop je t-SNE instelt (de "hyperparameters") bepaalt of je de gladde, perfecte oplossing krijgt, of de chaotische, gescheurde versie.
• Toekomst: De auteurs zeggen dat we voorzichtig moeten zijn met het interpreteren van t-SNE-plaatjes. Het is een krachtig hulpmiddel, maar het is geen perfecte spiegel van de realiteit. Het is meer een kunstzinnige interpretatie die gebaseerd is op een wiskundig proces dat soms "breekt" om mooie patronen te maken.

Kortom: t-SNE is als een getalenteerde maar wat onstabiele kunstenaar. Hij kan prachtige patronen creëren door data te "knippen en plakken", maar de wiskunde achter zijn penseelstreekjes is zo complex dat hij soms dingen doet die je niet verwacht. Dit artikel legt uit hoe die penseelstreekjes precies werken.

Technische samenvatting

Titel: Op de continuumlimiet van t-SNE voor datavisualisatie

Auteurs: Jeff Calder, Zhonggan Huang, Ryan Murray, en Adam Pickarski.

---

1. Probleemstelling

De t-Distributed Stochastic Neighbor Embedding (t-SNE) is een van de meest gebruikte algoritmen voor het visualiseren van hoog-dimensionale data in een laag-dimensionale ruimte (meestal $\mathbb{R}^2$ of $\mathbb{R}^3$). Het algoritme werkt door de Kullback-Leibler (KL) divergentie te minimaliseren tussen een similariteitsmatrix $P$ (in de oorspronkelijke ruimte) en een similariteitsmatrix $Q$ (in de ingebedde ruimte).

Hoewel t-SNE empirisch zeer succesvol is, is het theoretisch slecht begrepen. Er zijn belangrijke vragen onbeantwoord:

• Zijn de visualisaties "reproduceerbaar" bij een toenemend aantal datapunten ($n \to \infty$)?
• Convergeert het discrete algoritme naar een goed gedefinieerd continu probleem?
• Waarom kan t-SNE soms clusters creëren die niet in de data zitten, of data op willekeurige manieren "snijden"?

Deze paper onderzoekt de continuumlimiet van t-SNE wanneer het aantal datapunten $n \to \infty$ en de grafiek-sparse blijft (bandbreedte $h \to 0$).

2. Methodologie

De auteurs gebruiken technieken uit de variatierekening, kansrekening (concentratie van maat) en harmonic analysis om de discrete t-SNE-energie af te leiden naar een continu functionaal.

• Discrete Energie: De KL-divergentie wordt herschreven in termen van een aantrekkings- en een afstotingskracht. De auteurs introduceren een schaling van de inbeddingsmap $T$ (vaak met $h^{-1}$) om zinnige limieten te verkrijgen.
• Overgang naar Continu: Ze definiëren een niet-lokale energie $E_h[T]$ en laten zien dat deze convergeert naar een continu variatieprobleem $E[T]$ als $n \to \infty$ en $h \to 0$.
• De Continuum Energie: De limietenergie bestaat uit twee termen:
  1. Aantrekkingsterm: Een integraal die afhangt van de Jacobiaan $DT$ van de inbeddingsmap. Deze term vertegenwoordigt de lokale structuurbehoud.
  2. Afstotingsterm: Een term die afhangt van de dichtheid $\rho_Y$ van de ingebedde data in de visuele ruimte. Deze term voorkomt dat punten te dicht bij elkaar komen (crowding).

De specifieke vorm van de energie hangt af van de inbeddingsdimensie $m$.

3. Belangrijkste Bijdragen en Resultaten

A. Afleiding van de Continuum Energie

De auteurs bewijzen dat de t-SNE-energie convergeert naar een variatieprobleem van de vorm:
$$E_{t-SNE}[T] = \int_{\Omega} \Phi(\sigma DT) \rho_X dx + R[T]$$
Waarbij:

• $\Phi$ een logaritmische groei heeft (vergelijkbaar met de Perona-Malik energie).
• $R[T]$ een strafterm is op de $L^2$-norm van de dichtheid $\rho_Y$ (voor $m=1,2$), wat de data aanzet om zich te verspreiden.
• Voor $m \geq 3$ verandert de vorm van de afstotingsterm naar een negatieve Sobolev-norm.

B. Welgesteldheid in 1 Dimensie ($d=m=1$)

Voor het geval dat de data- en inbeddingsdimensie beide 1 zijn, bewijzen de auteurs een uniekheid en existentie resultaat voor een Lipschitz-minimalisator.

• Uniekheid: Er bestaat een unieke gladde minimizer (op een constante na).
• Discontinuïteiten: Hoewel er een unieke gladde minimizer is, tonen ze aan dat er oneindig veel discontinue minimalizers bestaan die even goed zijn in een "gerelaxeerde" zin.
• Interpretatie: Dit verklaart empirisch waargenomen gedrag waarbij t-SNE data lijkt te "snijden" en discontinuïteiten introduceert in de inbedding. De energie is niet gevoelig voor sprongen in de map.
• Numerieke Validatie: Numerieke experimenten tonen aan dat de discrete t-SNE-oplossingen (bij voldoende initialisatie) convergeren naar de oplossing van de continu limietvergelijking.

C. Niet-bestaandheid in Hogere Dimensies ($d > m$)

Voor het praktische geval waar de data-dimensie $d$ strikt groter is dan de inbeddingsdimensie $m$ (bijv. $d \gg 2$), tonen de auteurs aan dat het continu variatieprobleem geen minimizer toelaat.

• Microstructuur: Door de sublineaire groei van de aantrekkingsterm (logaritmisch) en de schalingseigenschappen, kan men een rij van functies construeren die steeds meer "snijlijnen" (microstructuur) introduceert.
• Energie: Door deze microstructuur kan de aantrekkingsenergie willekeurig laag worden (naar $-\infty$) terwijl de afstotingsenergie begrensd blijft.
• Conclusie: Het continu probleem is ill-posed (niet goed gesteld). Dit betekent dat de discrete t-SNE-minimalizers niet convergeren naar een enkele gladde functie in de limiet, maar eerder naar een object met microstructuur.

D. Vergelijking met SNE

De auteurs vergelijken t-SNE met de originele Stochastic Neighbor Embedding (SNE).

• Bij SNE is de aantrekkingsterm kwadratisch (Dirichlet-energie), wat leidt tot een goed gesteld probleem met een unieke minimizer in Sobolev-ruimtes ($W^{1,2}$).
• De logaritmische groei bij t-SNE (in plaats van kwadratisch) is de oorzaak van de mogelijkheid tot discontinuïteiten en de "crowding"-problematiek die t-SNE probeert op te lossen, maar die theoretisch leidt tot ill-posedheid in hoge dimensies.

E. Verbinding met Perona-Malik

De aantrekkingsenergie van t-SNE is sterk gerelateerd aan de Perona-Malik vergelijking, een bekend ill-posed probleem in beeldverwerking (denoising). De auteurs tonen aan dat de t-SNE-energie een geregulariseerde versie is van dit probleem, wat de stabiliteit van numerieke methoden in de praktijk verklaart, ondanks de theoretische ill-posedheid.

4. Significance en Implicaties

1. Theoretisch Inzicht: Dit werk biedt het eerste rigoureuze theoretische kader voor het begrijpen van het gedrag van t-SNE bij grote datasets. Het legt uit waarom t-SNE soms "willekeurige" clusters of snijlijnen produceert: het continu probleem heeft geen unieke gladde oplossing in hoge dimensies.
2. Reproduceerbaarheid: De resultaten suggereren dat t-SNE-visualisaties niet noodzakelijk stabiel zijn bij toenemende $n$ in de zin van convergentie naar één specifieke gladde kaart, maar eerder naar een familie van oplossingen met microstructuur.
3. Rol van Initialisatie: De numerieke resultaten benadrukken dat de keuze van initialisatie cruciaal is. Random initialisatie leidt vaak tot lokale minimalizers met discontinuïteiten, terwijl initialisatie dicht bij de continuumlimiet leidt tot een betere benadering van de theoretische minimizer.
4. Toekomstige Richtingen: De paper identificeert open vragen, zoals of er een minimizer bestaat voor $d=m \geq 2$, en hoe de discrete oplossingen precies convergeren in het geval van ill-posedheid (misschien via de niet-lokale energie $E_h$ als regularisatie).

Samenvatting

De paper toont aan dat de continuumlimiet van t-SNE leidt tot een variatieprobleem met een logaritmische aantrekkingskracht en een afstotingskracht gebaseerd op dichtheid. In 1D is dit probleem goed gesteld met een unieke gladde oplossing, maar in hogere dimensies ($d > m$) is het probleem ill-posed en admiteert het geen minimizer vanwege de vorming van microstructuur. Dit verklaart theoretisch het complexe en soms chaotische gedrag van t-SNE in de praktijk en verbindt het met klassieke ill-posed problemen uit de beeldverwerking.