A universal compression theory for lottery ticket hypothesis and neural scaling laws

Dit artikel bewijst dat grote neurale netwerken en datasets asymptotisch kunnen worden gecomprimeerd tot een polylogaritmische grootte zonder verlies van prestaties, wat een constructief bewijs levert voor de dynamische loterijticket-hypothese en de mogelijkheid aantoont om de wetten van neurale schaling te doorbreken.

De kern

De Magische Koffer: Hoe je een gigantische AI kunt verkleinen zonder kracht te verliezen

Stel je voor dat je een enorme, rommelige koffer hebt vol met kledingstukken. Je wilt op reis, maar de koffer is zo zwaar dat je hem niet kunt tillen. De huidige manier om dit op te lossen in de wereld van kunstmatige intelligentie (AI) is: "Goed, we gooien gewoon de helft van de kleding weg en hopen dat we nog wel warme kleren overhouden."

Dit werkt soms, maar vaak verlies je belangrijke dingen. Je hebt misschien je favoriete trui kwijt, of je hebt te weinig schoenen.

De auteurs van dit paper (van universiteiten zoals Princeton, MIT en Tsinghua) hebben een heel ander idee bedacht. Ze zeggen: "We hoeven niets weg te gooien. We kunnen de koffer juist slimmer inpakken."

Hier is hoe hun theorie werkt, in drie simpele stappen:

1. Het Geheim van de "Drukte" (Permutatie-Symmetrie)

Stel je voor dat je een klaslokaal hebt met 10.000 leerlingen. Als je vraagt: "Wie is er vandaag ziek?", maakt het niet uit in welke volgorde je de namen opschrijft. De antwoorden zijn hetzelfde. In de wiskunde noemen we dit permutatie-symmetrie.

In een groot AI-model (zoals een chatbot) zijn er miljoenen "neuronen" (de denkende stukjes). De paper laat zien dat veel van deze neuronen eigenlijk precies hetzelfde doen als hun buren. Ze staan in een dichte kluwen, net als mensen in een overvolle metro.

• De Metafoor: Stel je voor dat je 1.000 mensen in een klein parkje hebt. Als je kijkt naar de "drukte" in het park, maakt het niet uit of Jantje links van Pieter staat of rechts. Wat telt, is dat er veel mensen in dat stukje park staan.

2. De Kunst van het Samenvoegen (Compressie)

De auteurs bewijzen wiskundig dat je die 1.000 mensen in het park niet allemaal apart hoeft te tellen. Je kunt ze samenvoegen tot een paar "super-vertegenwoordigers".

• Hoe werkt het? In plaats van 1.000 losse mensen te hebben, maak je 10 "super-mensen". Elke super-mens vertegenwoordigt 100 echte mensen, maar met een gewicht (een "kracht") erbij.
• Het resultaat: Je hebt nu nog maar 10 mensen nodig om precies hetzelfde beeld te krijgen van de drukte in het park als met 1.000 mensen.
• De verrassing: Je kunt een AI-model met miljarden parameters verkleinen tot een model met slechts een paar duizend parameters (of zelfs minder!), en het gedrag blijft exact hetzelfde. Het leert even snel, maakt dezelfde fouten en geeft hetzelfde antwoord.

3. De "Lottery Ticket" (Het Geluksnummer)

Er is een bekend idee in de AI-wereld dat heet de "Lottery Ticket Hypothesis". Dit zegt: "In elke grote AI zit een klein, perfect stukje dat alles kan doen. We moeten het alleen maar vinden."

Tot nu toe was dit alleen een theorie die moeilijk te bewijzen was. Deze paper zegt: "We hoeven niet te zoeken. We kunnen het gewoon maken."

Ze bewijzen dat je elk groot netwerk kunt "verdichten" tot dat kleine, perfecte stukje, zonder dat het netwerk tijdens het leren (trainen) verandert. Het is alsof je een gigantische, rommelige bibliotheek kunt veranderen in een klein, perfect georganiseerd kastje met dezelfde boeken, zonder dat je een enkel boek hoeft te verliezen.

Wat betekent dit voor de toekomst?

1. Minder Data nodig: AI-modellen leren nu op enorme hoeveelheden data (zoals alle boeken en websites op internet). Deze theorie suggereert dat we misschien veel minder data nodig hebben. Als je de data "slimmer" samenvat, kan een AI net zo goed leren met 1% van de data die we nu gebruiken.
2. Snellere en goedkopere AI: Grote modellen zijn duur en traag om te trainen. Als we ze kunnen verkleinen tot een fractie van hun huidige grootte, kunnen we krachtige AI's draaien op je telefoon in plaats van op enorme serverparken.
3. De "Wet van de Schaal": Nu geldt: "Hoe groter het model, hoe slimmer het is, maar het gaat heel langzaam." Deze paper zegt: "Nee, als we slim comprimeren, kan de slimheid exponentieel sneller groeien."

Kortom:
De auteurs hebben een wiskundige sleutel gevonden die laat zien dat de "grootte" van een AI-model vaak een illusie is. Door slim te kijken naar hoe de onderdelen samenwerken, kunnen we enorme systemen verkleinen tot een handvol, super-efficiënte componenten. Het is alsof je een olifant in een theepot kunt stoppen, maar de olifant blijft net zo groot en sterk als voorheen.

Technische samenvatting

Probleemstelling

Het trainen van grote schaalmodellen (zoals GPT-4) is extreem kostbaar, zowel qua rekentijd als qua data-efficiëntie. Moderne modellen worden getraind op datasets met biljoenen tokens, terwijl biologische systemen (zoals het menselijk brein) taal met veel minder data leren.
De huidige empirische richtlijn voor het trainen van Large Language Models (LLM's) wordt beschreven door Neural Scaling Laws (NSL). Deze stellen dat de generalisatiefout $L$ afneemt volgens een machtswet met betrekking tot de datasetgrootte $N$ of het aantal parameters:
$$L(N) \propto N^{-\alpha}$$
waarbij de exponent $\alpha$ vaak klein is (tussen 0,1 en 0,3). Dit impliceert dat om de fout met een factor 2 te verkleinen, de datasetgrootte met een factor $2^{1/\alpha}$ (bijv. 1000x) moet worden vergroot. Dit is onpraktisch gezien de beperkte beschikbaarheid van data.

De centrale vraag is: Kan men vergelijkbare prestaties behalen met aanzienlijk kleinere modellen en minder data, en zo ja, hoe kan dit theoretisch worden onderbouwd?

Methodologie: Universele Compressie Theorie

De auteurs presenteren een fundamentele theoretische doorbraak gebaseerd op permutatie-invariantie (symmetrie) in machine learning.

1. Permutatie-Symmetrie:

   • Data: De verliesfunctie is een som over datapunten; de volgorde van de datapunten maakt niet uit.
   • Neuronen: In een neurale laag met breedte $d$ (bijv. $f(x) = \sum v_i \sigma(w_i^T x)$) is de output invariant onder het verwisselen van paren $(v_i, w_i)$.
   • De auteurs behandelen zowel datasets als modelparameters als verzamelingen van $d$ objecten die een symmetrische functie vormen.

2. Fundamentele Stelling van Symmetrische Polynomen (FTSP) & Momenten:

   • Een symmetrische functie van $d$ objecten kan volledig worden gekarakteriseerd door de statistische momenten van die objecten (analoog aan de momenten in kansrekening).
   • Volgens de Fundamentele Stelling van Symmetrische Polynomen kan elke symmetrische polynoom worden uitgedrukt als een functie van de eerste $k$ momenten.
   • Tchakaloff's Theorema: Dit stelt dat er een kleine verzameling van gewogen punten bestaat die dezelfde eerste $k$ momenten heeft als de oorspronkelijke grote verzameling.

3. Compressie-algoritme:

   • Het paper stelt een algoritme voor dat $d$ objecten comprimeert tot $d'$ objecten door momenten te matchen.
   • Door objecten te clusteren (op basis van afstand) en binnen clusters momenten te matchen, kan de steun (support) van de verdeling worden gereduceerd zonder de waarde van de symmetrische functie significant te veranderen.
   • De fout wordt gecontroleerd door de differentieerbaarheid van de functie en de diameter van de clusters.

Belangrijkste Bijdragen

De paper levert drie hoofdresultaten:

1. Universele Compressiestelling:
   Bewezen dat een generieke permutatie-invariante functie van $d$ objecten asymptotisch kan worden gecomprimeerd tot een functie van polylogaritmische grootte ($O(\text{polylog}(d))$) met een verwaarloosbare fout. Deze compressiesnelheid is bewezen optimaal (tot op een constante factor).

2. Dynamische Loterij Ticket Hypothese (Dynamical LTH):

   • De klassieke Lottery Ticket Hypothesis (LTH) stelt dat er een klein subnetwerk bestaat dat net zo goed presteert als het oorspronkelijke netwerk. Echter, eerdere theorieën garandeerden niet dat het trainingsproces (dynamica) hetzelfde bleef.
   • De auteurs bewijzen dat een groot netwerk kan worden gecomprimeerd tot een polylogaritmische breedte zodanig dat de trainingsdynamica (de weg naar de oplossing) identiek blijft aan die van het originele netwerk. Dit is een sterkere vorm van LTH.

3. Verbetering van Neural Scaling Laws:

   • Door datasets te comprimeren tot polylogaritmische grootte terwijl het verlieslandschap ongewijzigd blijft, kunnen de traditionele machtswet-scaling laws ($L \sim d^{-\alpha}$) worden "opgeblazen" naar een verlengde exponentiële afname:
     $$L(d') \sim \exp(-\alpha' \sqrt[m]{d'})$$
   • Dit betekent dat men met veel minder data (of parameters) dezelfde fout kan bereiken, ofwel dat de efficiëntie exponentieel toeneemt in plaats van lineair of volgens een machtswet.

Resultaten

De auteurs ondersteunen hun theorie met numerieke experimenten:

• Dataset Compressie: In een teacher-student setup (MLP) werd getoond dat training op een gecomprimeerde dataset (bijv. $10^3$ punten afgeleid van $10^4$) bijna identieke prestaties oplevert als training op de volledige dataset. Naive subsampling (willekeurig verwijderen van data) presteerde daarentegen veel slechter.
• Netwerk Compressie (Dynamical LTH): Een breed netwerk (breedte $10^4$) werd gecomprimeerd tot een gewogen netwerk van breedte $10^3$. De trainingsverliezen en testverliezen van het gecomprimeerde netwerk volgden die van het originele netwerk nauwkeurig, ongeacht de gebruikte optimizer (SGD, Adam, Rprop).
• Schalingswetten: Experimenten toonden aan dat door compressie de effectieve schalingsexponent verdubbelt. Een compressie van $d$ objecten naar $\approx \sqrt{d}$ objecten resulteerde in een kwadratische versnelling in de leercurve.
• Attention Mechanismen: De theorie werd toegepast op Transformer-modellen, waarbij getoond werd dat een model met 4000 attention heads kan worden gecomprimeerd tot 800 heads met behoud van de leercurve.

Betekenis en Toekomstperspectief

• Theoretisch: Dit paper biedt een unificerende theorie voor compressie in deep learning, gebaseerd op symmetrie in plaats van specifieke architecturale eigenschappen. Het verbindt de Lottery Ticket Hypothesis en Neural Scaling Laws via een gemeenschappelijk wiskundig raamwerk.
• Praktisch: Het suggereert dat huidige AI-systemen verre van optimaal gebruikmaken van data. Door slimme compressie (in plaats van willekeurige pruning) kunnen modellen veel efficiënter worden getraind.
• Beperkingen: De theoretische compressie naar $O(\log^m d)$ is computationeel zwaar (NP-hard problemen bij clustering in hoge dimensies). De auteurs benadrukken dat in de praktijk benaderingen (zoals k-means) werken, maar dat er nog werk nodig is om schaalbare algoritmen te ontwikkelen voor zeer hoge dimensies.
• Conclusie: De auteurs concluderen dat het mogelijk is om de "curse of dimensionality" te omzeilen voor gladde symmetrische functies, wat leidt tot een fundamenteel nieuwe manier van denken over de schaalbaarheid en efficiëntie van neurale netwerken.