Vandaag's post is een samenwerking met mijn jeugdvriend Andrés Silva :-) ------- Als je een willekeurig punt in een eenheidsvierkant laat vallen, is er ongeveer 78,5% kans dat het binnen de ingeschreven cirkel valt. Laat je er een in een eenheidskubus vallen, dan is er 52,4% kans dat het binnen de ingeschreven bol valt. Bij dimensie 10 daalt die kans naar 0,25%. Bij dimensie 100 is het effectief nul. Dit is de "vloek van dimensionaliteit" - standaardkost in elke cursus machine learning, en het onderwerp van een lange wiskundige literatuur. De gemiddelde afstand tussen willekeurige punten in een doos werd door Robbins geponeerd en in 1978 opgelost. Johan Philip leidde de volledige verdeling af voor 3D. Deze problemen zijn goed beproefd. Wat we hier willen doen is iets anders: systematisch afstandshistogrammen vergelijken over verschillende geometrieën (Euclidisch, sferisch, hyperbolisch), topologieën (hypercube vs. torus), en dimensies - en dan vragen wat deze "handtekeningen" zouden kunnen onthullen over echte inbeddingsruimtes in neurale netwerken. Het kernidee: het histogram van paargewijze afstanden tussen willekeurige punten is een geometrische vingerafdruk. Verschillende ruimtes laten verschillende sporen achter. Je zou dit kunnen gebruiken om te diagnosticeren in welke geometrie je gegevens zich in het geheim bevinden. Het Oorspronkelijke Verhaal: Twee Andreses Lopen Een Bar Binnen in Coyoacán... De ideeën in deze post zijn voortgekomen uit een gesprek tussen ons tweeën (ja, we heten allebei Andrés - bienvenidos a México). De opzet: als jij en een vriend op willekeurige locaties in een n-dimensionale hypercube worden gedropt, hoe ver van elkaar zijn jullie dan, gemiddeld? En interessanter nog, hoe ziet de verdeling van mogelijke afstanden eruit? "Het ding is," zoals een van ons tijdens ons gesprek zei, "als je twee willekeurige punten in de ruimte pakt, hoe ziet de afstandsverdeling eruit? Ik weet zeker dat je over dit probleem hebt nagedacht?" - "ja, en ik vroeg me af over hogere dimensies." Het antwoord blijkt prachtig eenvoudig te zijn voor de 1D-zaak (een lijnsegment): de verdeling van afstanden tussen twee uniforme willekeurige punten op [0,1] is driehoekig, met een piek bij 0. De meeste paren zijn dicht bij elkaar, en de kans om precies 1 uit elkaar te zijn (de maximale afstand) is precies nul - het is een set van maat nul. Maar wat gebeurt er als je wraparound toevoegt? Wanneer je in plaats van een lijnsegment op een cirkel bent? De Torus Truc: Zonder Verlies van Algemeenheid Hier komt de eerste prachtige inzicht naar voren. Op een lijnsegment [0,1] is de afstand tussen punten x en y gewoon |x - y|. Maar op een cirkel (een 1-torus) kun je in beide richtingen gaan. De "gewikkelde" afstand is min(|x - y|, 1 - |x - y|). Kernidee: Op een torus kun je altijd aannemen dat één punt zich op de oorsprong bevindt zonder verlies van algemeenheid. Waarom? Omdat de torus homogeen is - elk punt lijkt op elk ander punt. Er zijn geen randen, dus er zijn geen hoeken. Elke locatie waar je het eerste punt plaatst, is "dezelfde locatie". Als je twee willekeurige punten op een torus laat vallen, kun je de ruimte altijd mentaal vertalen zodat één punt op nul zit. Dit betekent dat de verdeling van afstanden volledig wordt bepaald door de verdeling van de afstand van een enkel uniform willekeurig punt tot nul. Op de 1D torus (cirkel) is deze gewikkelde coördinaat uniform op [0, 0,5]. Het hele probleem factoriseert prachtig: in een n-dimensionale platte torus is de totale afstand: D = sqrt(D_1^2 + D_2^2 + ... + D_n^2) waarbij elke D_i de gewikkelde coördinaatafstand in dimensie i is, onafhankelijk uniform op [0, 0,5]. "Dus je kijkt naar de verdeling van de Euclidische norm van een vector waarvan de componenten uniform zijn op [0, 0,5]," merkte Andrés S. op tijdens ons gesprek. "Je zou een set van maat 1/2 van al die mogelijkheden kunnen hebben..." ...