The Theory behind UMAP?

Dit artikel corrigeert fouten in Spivaks onuitgegeven manuscript en McInnes et al.'s afleiding van UMAP door een zelfstandig document te bieden met de volledige afleiding van de metriek-realisatiefunctor en een analyse van de UMAP-algoritmeclaims.

De kern

Hier is een uitleg van het paper in simpel, alledaags Nederlands, vol met creatieve metaforen.

De Kern: Een Reis van Wiskunde naar Wereld

Stel je voor dat je een enorme, ingewikkelde berg hebt vol met schatten (data). Je wilt deze berg platleggen op een kaart (een 2D- of 3D-afbeelding) zodat je de schatten kunt zien en begrijpen, zonder dat je de relaties tussen ze verliest. Dit proces heet dimensiereductie.

Een van de populairste tools hiervoor is UMAP. Wetenschappers McInnes en collega's hebben in 2018 een algoritme bedacht dat dit doet. Ze zeiden: "We hebben een mooie wiskundige theorie die verklaart waarom dit werkt."

Maar... De auteur van dit paper, David Wegmann, zegt: "Hé, die theorie is een beetje rommelig. Het is alsof ze een bouwpakket hebben gebruikt waarvan de instructies half weggeveegd zijn en waar fouten in staan."

Dit paper is David's manier om die instructies te repareren, de fouten te corrigeren en te laten zien hoe het bouwpakket echt werkt.

---

De Grote Problemen (De "Gaten" in de theorie)

David identificeert een paar grote problemen in de oorspronkelijke theorie van UMAP:

1. De "Logaritme-Lus": De oorspronkelijke auteurs gebruikten een wiskundige truc met logaritmen (zoals $\log(0)$) die eigenlijk niet bestaat. Het is alsof je probeert te delen door nul. David lost dit op door de definitie iets anders te bouwen, zodat de wiskunde stabiel blijft.
2. De "Fuzzy" Verwarring: UMAP werkt met "fuzzy sets". Denk hierbij niet aan een wazig beeld, maar aan een lidmaatschap. Een punt is niet gewoon "in" of "uit" een groep, maar heeft een sterkte van lidmaatschap (bijvoorbeeld 0,8). De oorspronkelijke theorie was hier onnauwkeurig over. David maakt het strakker: hij gebruikt een concept uit de wiskunde genaamd "sheaves" (dekens) om te zorgen dat alles logisch klopt.
3. De "Afstand" Fout: In de theorie werd beweerd dat bepaalde lijnen niet langer werden dan ze mochten zijn. David toont aan dat dit alleen klopt als je een specifieke manier van afstand meten gebruikt (de "Manhattan-afstand", alsof je door een stratenraster loopt, niet als je diagonaal over velden loopt).

---

De Oplossing: De "Metrische Realisatie"

David introduceert een concept dat hij de Metrische Realisatie noemt. Laten we dit uitleggen met een metafoor:

Stel je voor dat je een modelbouwset hebt:

• De Simplicia: Dit zijn de bouwstenen. Een punt is een 0D-blokje, een lijn is een 1D-blokje, een driehoek is een 2D-blokje, een tetraëder is een 3D-blokje.
• De Fuzzy-waarden: In de UMAP-theorie hebben deze blokjes een "grootte" of "sterkte" gekoppeld. Een lijn met een hoge sterkte is een korte, strakke lijn. Een lijn met een lage sterkte is een lange, slappe lijn.

Wat doet David?
Hij bouwt een machine die deze "fuzzy" bouwstenen omzet in een echt, meetbaar object (een ruimte met afstanden).

• Als je een punt hebt met een hoge "lidmaatschapssterkte", wordt het een klein, compact puntje.
• Als je een lijn hebt met een lage sterkte, wordt het een lange, uitgerekte lijn.

De oorspronkelijke auteurs probeerden dit te doen, maar hun machine had een defecte schroef (de logaritme-fout). David repareert de machine en laat zien hoe hij precies werkt. Hij bouwt een brug tussen de abstracte wiskunde (categorietheorie) en de concrete computercode die data verwerkt.

---

De "Finite" Versie: De UMAP Algoritme

De echte UMAP-algoritme die mensen gebruiken, werkt niet met oneindig veel puntjes, maar met een eindige hoeveelheid (bijvoorbeeld 10.000 foto's).

David toont aan hoe je de complexe, oneindige wiskundige theorie kunt "knijpen" tot een eindige versie die op een computer werkt.

• Hij definieert precies wat "eindig" betekent in dit verband.
• Hij laat zien dat de stappen die UMAP doet (een grafiek maken, veren, en dan optimaliseren) inderdaad overeenkomen met wat de wiskundige theorie voorspelt, mits je de fouten uit de originele paper verwijdert.

---

Wat betekent dit voor de gebruiker?

1. Betrouwbaarheid: De theorie achter UMAP is nu wiskundig waterdicht. Je kunt erop vertrouwen dat de resultaten niet op toeval of foutieve aannames berusten.
2. Geen "Magie" meer: UMAP voelt soms als zwarte magie. David legt uit dat het eigenlijk een heel logisch proces is van het vertalen van "hoe dicht bij elkaar lijken deze punten?" naar "hoe ver moeten ze van elkaar staan op de kaart?".
3. Verbetering: Hoewel de code van UMAP waarschijnlijk nog steeds werkt (want de programmeurs hebben het goed gedaan), is de uitleg nu correct. Dit helpt andere wetenschappers om betere algoritmen te bouwen die op dezelfde principes rusten.

Samenvattend in één zin:

David Wegmann heeft de wiskundige blauwdruk van de populaire data-analyse-tool UMAP opgepakt, de scheuren en fouten in de instructies gerepareerd, en een nieuwe, strakke versie gebouwd die precies uitlegt hoe je van een wirwar van data naar een heldere kaart gaat.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het proefschrift "The Theory behind UMAP?" van David Wegmann, geschreven in het Nederlands.

Probleemstelling

De UMAP-algoritme (Uniform Manifold Approximation and Projection), geïntroduceerd door McInnes et al. in 2018, is een extreem populair hulpmiddel voor dimensiereductie onder datawetenschappers. De theoretische onderbouwing in het originele artikel [5] is gebaseerd op een "metrische realisatie" (metric realization), een functor die afkomstig is uit een ongepubliceerd manuscript van David Spivak [9].

Het centrale probleem dat dit proefschrift adresseert, is dat zowel Spivak's manuscript als het artikel van McInnes et al. ernstige wiskundige fouten, gaten in de logica en inconsistenties bevatten. Deze fouten leiden tot een gebrekkige theoretische onderbouwing van het UMAP-algoritme. Specifieke problemen omvatten:

• Definitie van fuzzy sets: Onjuiste definities van topologieën op het interval $(0, 1]$ en incorrecte toepassing van de theorie van sheaves (garven).
• Logaritmische singulariteiten: De gebruikte schalingsfactoren bevatten logaritmen van parameters die nul kunnen zijn ($\log(0)$), wat wiskundig ongeldig is.
• Niet-expansieve afbeeldingen: De bewering dat bepaalde operaties in het algoritme "niet-expansief" zijn (afstanden niet vergroten), is onjuist voor de gebruikte metriek (Euclidisch/ $\ell_2$).
• Categorische inconsistenties: Gebrekkige behandeling van eindige varianten en de relatie tussen simpliciale objecten en de Yoneda-inbedding.

Het doel van het proefschrift is deze fouten te repareren, een zelfstandig en wiskundig correct document te bieden met een volledige afleiding van Spivak's functors en de eindige variant van McInnes et al., en de relatie tot het UMAP-algoritme kritisch te evalueren.

Methodologie

De auteur hanteert een strikt categorische en topologische aanpak, gebaseerd op de werken van Barr, Spivak en McInnes, maar met een fundamentele herformulering om de bestaande fouten te omzeilen.

1. Categorische Grondslagen: Het proefschrift bouwt op de theorie van locales (puntloze topologie), sheaves op locales, en de theorie van gekleurde verzamelingen (valued sets). Er wordt een equivalence bewezen tussen klassieke "valued sets" (verzamelingen met een membership-functie) en een subcategorie van sheaves.
2. Herdefinitie van de Metrische Realisatie:
   • In plaats van de oorspronkelijke definitie van Spivak die gebruikmaakt van fuzzy sets met een logaritmische schaling, introduceert de auteur een klassieke variant gebaseerd op genormaliseerde verzamelingen (normed sets).
   • De auteur definieert een metrische n-simplice met een $\ell_1$-metriek (Manhattan-metriek) in plaats van de $\ell_2$-metriek. Dit is cruciaal omdat alleen de $\ell_1$-metriek garandeert dat de degeneratie-afbeeldingen (degeneracy maps) niet-expansief zijn.
   • De realisatie wordt geconstrueerd als een Linker Kan-uitbreiding (Left Kan Extension) langs de Yoneda-inbedding.
3. Eindige Variant: Voor de toepassing in UMAP wordt een eindige variant van de categorieën gedefinieerd (eindige extended pseudo-metric spaces en eindige fuzzy sets). De auteur bewijst dat de bestaande equivalenties tussen categorieën ook gelden voor deze eindige subcategorieën, waardoor de constructie van de "finite metric realization" wiskundig geldig wordt.
4. Analyse van UMAP: Het proefschrift analyseert de stappen van het UMAP-algoritme (lokaal graaf bouwen, verenigen via T-conorms, spectrale embedding, en stochastische gradiëntafdaal) en vergelijkt deze met de theoretisch afgeleide "finite singular nerve" en "finite metric realization".

Belangrijkste Bijdragen

• Correctie van Fundamentele Fouten: De auteur identificeert en repareert specifieke fouten in Spivak's en McInnes' werk, waaronder de definitie van de topologie op $(0, 1]$, de behandeling van logaritmische singulariteiten, en de keuze van de metriek.
• Expliciete Constructie van Functors: Er wordt een expliciete beschrijving gegeven van de metrische realisatie ($MetRe$) en de singuliere zenuw ($Sing$) als een paar van adjungerende functors tussen de categorie van simpliciale genormaliseerde verzamelingen en extended pseudo-metric spaces.
• Equivalentie van Categorieën: Het proefschrift levert een volledige bewijsvoering voor de equivalentie tussen de categorie van klassieke fuzzy sets en de categorie van sheaf-theoretische fuzzy sets, inclusief de expliciete constructie van de inverse functors die nodig zijn voor berekeningen.
• Validatie van de Eindige Realisatie: Er wordt bewezen dat McInnes' "finite metric realization" bestaat binnen de categorie van eindige extended pseudo-metric spaces, ondanks dat deze categorie niet volledig cocompleet is.
• Kritische Evaluatie van UMAP: Het werk ontleedt de theoretische claims van UMAP en toont aan dat bepaalde stappen (zoals het interpreteren van gewichten als kansen) momenteel niet strikt wiskundig onderbouwd zijn.

Resultaten

• Wiskundige Zuiverheid: De auteur toont aan dat de metrische realisatie correct kan worden gedefinieerd zonder de fouten uit de originele literatuur, door gebruik te maken van $\ell_1$-metrieken en een herformulering in termen van genormaliseerde verzamelingen.
• Verband met UMAP: Het proefschrift bevestigt dat de lokale graafconstructies in UMAP inderdaad corresponderen met de 1-skeletten van de "finite singular nerve" van de data. De vereniging van deze lokale graafjes via de probabilistische T-conorm komt overeen met de vereniging van de bijbehorende fuzzy sets.
• Beperkingen van de Theorie: Hoewel de constructie van de "finite metric realization" correct is, concludeert de auteur dat de claim dat UMAP de topologische structuur van een Riemannse variëteit perfect behoudt, niet formeel bewezen is. De interpretatie van gewichten als kansen en de keuze voor cross-entropy als verliesfunctie blijven informele aannames zonder strikt probabilistische onderbouwing in het oorspronkelijke artikel.

Betekenis

Dit proefschrift is van groot belang voor de theoretische gemeenschap binnen machine learning en topologische data-analyse:

1. Fundamentele Correctie: Het biedt de eerste wiskundig correcte en zelfstandige afleiding van de theorie achter UMAP, wat essentieel is voor het vertrouwen in de algoritme-uitkomsten en voor toekomstige theoretische ontwikkelingen.
2. Brug tussen Theorie en Praktijk: Het maakt de abstracte categorische theorie van Spivak toegankelijker en toepasbaar door de constructie te vertalen naar klassieke genormaliseerde verzamelingen en expliciete formules.
3. Kritische Reflectie: Het zet een nieuwe standaard voor theoretische onderbouwing in datawetenschap door de kloof tussen informele claims en strikte wiskundige bewijzen te benadrukken. Het waarschuwt onderzoekers om kritisch te zijn over de interpretatie van "kansen" en "topologie" in empirische algoritmes zonder formele garanties.

Kortom, het werk transformeert de theorie achter UMAP van een verzameling intuïtieve maar gebrekkige beweringen naar een robuust, wiskundig gefundeerd kader, terwijl het tegelijkertijd de grenzen van de huidige theoretische onderbouwing blootlegt.