Approximating invariant functions with the sorting trick is theoretically justified

In het uitgestrekte landschap van de moderne kunstmatige intelligentie wordt van machines steeds vaker gevraagd om patronen te herkennen die niet veranderen wanneer hun onderdelen worden herschikt. Stel je een verzameling punten voor die een molecuul representeren, een stofwolk in de ruimte, of een groep mensen in een sociaal netwerk. De identiteit van het object of de aard van de relatie hangt niet af van de volgorde waarin we deze onderdelen opsommen. Een molecuul is hetzelfde molecuul, of we nu de atomen van links naar rechts of van rechts naar links beschrijven. Om computers te leren deze fundamentele waarheid te respecteren, bouwen onderzoekers modellen die "invariant" zijn, wat betekent dat hun output constant blijft, zelfs wanneer de input wordt gehusseld. Dit is een krachtig hulpmiddel, maar het brengt een zware prijs met zich mee. De standaardmanier om een computer te dwingen de volgorde van gegevens te negeren, is door hem elke mogelijke arrangement van die gegevens te tonen en de resultaten te middelen. Voor een kleine set items is dit beheersbaar. Maar naarmate het aantal items groeit, explodeert het aantal mogelijke arrangementen, waardoor de berekening zo duur wordt dat het onmogelijk is om uit te voeren.

Jarenlang bestond er een eenvoudiger alternatief: in plaats van de computer elke arrangement te tonen, de data simpelweg sorteren in een standaardvolgorde voordat deze wordt ingevoerd. Als je een lijst met getallen hebt, breng je ze van klein naar groot in orde. Deze "sorteertruc" is ongelooflijk snel en vermijdt de computationele nachtmerrie van het controleren van elke permutatie. Deze snelheid komt echter met een theoretische prijs. De handeling van het sorteren creëert een wiskundige functie die grillig en gebroken is op de punten waar de volgorde van de data verandert. In de wereld van de gladde wiskunde is dergelijke grilligheid meestal een teken van falen, wat veel experts deed geloven dat deze snelle methode nooit zo nauwkeurig zou kunnen zijn als de trage, uitputtende methone. Lange tijd werd de sorteermethode in de praktijk gebruikt omdat het werkte, maar zonder een solide wiskundige uitleg waarom het werkte of hoe goed het presteerde.

Een recente studie door onderzoekers van de Chinese University of Hong Kong en de University of California, San Diego, biedt eindelijk die ontbrekende verklaring. Zij zetten zich in om te bewijzen dat het sorteren van data voordat het wordt verwerkt niet alleen een handige afkorting is, maar een wiskundig superieure strategie voor een specifieke klasse problemen. Door instrumenten uit de benaderingstheorie toe te passen, die bestudeert hoe goed de ene functie de andere kan nabootsen, hebben zij aangetoond dat de sorteertruc de nauwkeurigheid van het machine learning-model daadwerkelijk verbetert. Hun werk laat zien dat door de data in een gesorteerde volgorde te dwingen, het model effectief werkt in een kleinere, meer georganiseerde ruimte. Deze reductie in complexiteit stelt het model in staat om dichter bij het ware antwoord te komen met minder datapunten dan de traditionele, ongesorteerde methode vereist.

De onderzoekers concentreerden zich op een specifiek scenario waarbij de data bestaat uit punten in een multidimensionale ruimte, zoals coördinaten in een 3D-model of kenmerken in een dataset. Ze vergeleken twee benaderingen: één die een standaard wiskundige functie gebruikte om de ruwe, ongesorteerde data te verwerken, en een andere die eerst de data sorteerde en vervolgens de functie toepaste. Ze ontdekten dat de gesorteerde aanpak consequent de fout tussen de voorspelling van het model en de werkelijke waarde verminderde. Deze verbetering komt voort uit een principe dat bekend staat als de herrangschikkingsongelijkheid (rearrangement inequality), die in essentie stelt dat het samenbrengen van gesorteerde lijsten met getallen een sterkere, stabielere relatie oplevert dan het samenbrengen van ze in een willekeurige volgorde. Wanneer de data gesorteerd is, vergelijkt het model altijd vergelijkbare structuren, wat het leerproces efficiënter en nauwkeuriger maakt.

Cruciaal is dat de studie de bezorgdheid aanpakte dat de grillige aard van het sorteerproces de resultaten zou verpesten. Hoewel het waar is dat de wiskundige functie die door sorteren wordt gecreëerd niet perfect glad is, bewezen de onderzoekers dat dit gebrek aan gladheid slechts kleine problemen veroorzaakt nabij de uiterste randen van de dataruimte. Naarmate het aantal datapunten toeneemt, wordt het gebied waar deze randproblemen optreden verwaarloosbaar klein. In het overgrote deel van de ruimte waarin het model opereert, presteert de gesorteerde methode beter dan de ongesorteerde methode. De studie leverde rigoureuze wiskundige grenzen aan die aantonen dat de fout in de gesorteerde methode sneller afneemt naarmate er meer data wordt toegevoegd, waarbij het de traditionele methode met een aanzienlijke marge overtreft, vooral naarmate de complexiteit van de data toeneemt.

Het team onderzocht ook hoe de keuze van de datapunten de uitkomst beïnvloedt. Ze toonden aan dat er een specifieke manier is om de datapunten te ordenen die de kracht van sorteren volledig benut. Wanneer de data op deze optimale manier is verdeeld, is de verbetering in nauwkeurigheid spectaculair. De studie omvatte numerieke experimenten met gesimuleerde data om deze theoretische bevindingen te bevestigen. In deze tests produceerde de gesorteerde methode consistent veel kleinere fouten dan de ongesorteerde methode. Bijvoorbeeld, in tests waarbij twaalf verschillende dimensies betrokken waren, was de fout voor de ongesorteerde methode bijna zes keer groter dan de fout voor de gesorteerde methode. Deze kloof werd groter naarmate de complexiteit van het probleem toenam, wat suggereert dat de sorteertruc nog waardevoller wordt naarmate de data ingewikkelder wordt.

Dit werk doet meer dan alleen een populaire techniek te valideren; het opent een nieuw pad voor het ontwerpen van betere machine learning-modellen. Door te bewijzen dat sorteren theoretisch solide is, hebben de onderzoekers ingenieurs en wetenschappers het vertrouwen gegeven om deze efficiënte methode te gebruiken zonder angst om nauwkeurigheid op te offeren. De bevindingen suggereren dat de toekomst van invariant learning niet ligt in brute-force berekeningen die elke mogelijkheid controleren, maar in slimme, gestructureerde benaderingen die data organiseren om de onderliggende patronen te onthullen. De studie concludeert dat hoewel de sorteermethode enige wiskundige ruwheid introduceert, de voordelen van het werken in een kleinere, meer geordende ruimte veel groter zijn dan de nadelen. Het transformeert een heuristische truc in een robuuste, bewezen strategie, en biedt een duidelijke gids voor het bouwen van snellere en nauwkeurigere modellen voor taken variërend van moleculaire classificatie tot sociale netwerkanalyse.