🤖 machine learning

Learning the symmetric group: large from small

Dit artikel stelt een schaalbare machine learning-methode voor waarbij transformer-modellen die zijn getraind op het voorspellen van permutaties in kleinere symmetrische groepen (zoals $S_{10}$ ) met specifieke transpositiestrategieën, met bijna perfecte nauwkeurigheid kunnen generaliseren naar aanzienlijk grotere groepen (zoals $S_{25}$ ), door technieken zoals identiteitsaugmentatie en gepartitioneerde vensters te benutten om uitdagingen op het gebied van gegevensgeneratie en interpreteerbaarheid te overwinnen.

Oorspronkelijke auteurs: Max Petschack, Alexandr Garbali, Jan de Gier

Gepubliceerd 2026-05-08

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Max Petschack, Alexandr Garbali, Jan de Gier

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Idee: Een Leerling Leren Reuzepuzzels Oplossen met Klein Oefenmateriaal

Stel je voor dat je een leerling wilt leren hoe je een enorme, complexe puzzel met 25 stukjes (of zelfs 100) oplost. Normaal gesproken zou je hen oefenpuzzels van diezelfde grootte geven. Maar wat als je hen alleen oefenpuzzels met 10 stukjes gaf?

Dit artikel vraagt zich af: Kan een computer (specifiek een AI genaamd een "Transformer") de regels van een enorme puzzel leren door alleen te oefenen op kleine versies ervan, en vervolgens de reuzenpuzzel succesvol oplossen zonder er ooit één te hebben gezien?

Het antwoord, volgens deze studie, is ja. De AI leerde de logica van een enorm wiskundig systeem door te trainen op een klein subset ervan en generaliseerde die kennis vervolgens om veel grotere, complexere systemen met bijna perfecte nauwkeurigheid te hanteren.

De Personages in Ons Verhaal

De Symmetrische Groep ( $S_n$ ): Denk hierbij aan een groot spel "kaarten schudden".
- Als je een stapel van $n$ kaarten hebt (genummerd 1 tot $n$ ), is een "permutatie" gewoon een specifieke volgorde van die kaarten.
- De "Symmetrische Groep" is de verzameling van elke mogelijke manier waarop je die stapel kunt schudden.
- Het doel is om naar een lijst met instructies (een "woord") te kijken die je vertelt hoe je de kaarten moet schudden, en de uiteindelijke volgorde van de stapel te voorspellen.
De Instructies (Transposities):
- Algemene Transposities: Stel je voor dat je elke twee kaarten in de stapel kunt kiezen en ze kunt verwisselen. Dit is als het hebben van een "toverstaf" die elk twee items direct kan verwisselen.
- Aangrenzende Transposities: Stel je voor dat je alleen kaarten kunt verwisselen die direct naast elkaar liggen. Dit is veel moeilijker. Om kaart #1 en kaart #10 te verwisselen, moet je ze één voor één langs elkaar schuiven. Dit creëert een veel langere, complexere lijst met instructies.
De AI (De Transformer): Dit is een type machine learning-model dat bekend staat om het lezen van tekst en het begrijpen van patronen. Hier leest het, in plaats van zinnen, lijsten met wiskundige instructies.

Het Experiment: Twee Verschillende Uitdagingen

De onderzoekers voerden twee hoofdexperimenten uit om te zien of de AI kon "schalen" van klein naar groot.

Uitdaging 1: De "Toverstaf" (Algemene Transposities)

De Training: De AI werd alleen getraind op het schudden van stapels van 10 kaarten. Het leerde hoe het instructies moest volgen om twee willekeurige kaarten in een stapel van 10 kaarten te verwisselen.
De Test: Vervolgens vroegen ze de AI om schudproblemen op te lossen voor een stapel van 25 kaarten.
Het Resultaat: De AI had het bijna 100% van de tijd goed. Het memoriseerde niet alleen de regels voor 10 kaarten; het begreep de onderliggende logica van "verwisselen" en paste dit toe op een veel grotere stapel die het nooit eerder had gezien.

Uitdaging 2: De "Buurman-Verwisseling" (Aangrenzende Transposities)

De Training: Dit was moeilijker. De AI werd getraind op een stapel van 10 kaarten waarbij het alleen buren mocht verwisselen.
Het Probleem: Als je alleen buren verwisselt, worden de instructies erg lang. Een simpele verwisseling van de eerste en de laatste kaart vereist veel stappen.
De Truc (Partitioned Windows): De onderzoekers realiseerden zich dat de AI lui werd. Het memoriseerde gewoon het specifieke "venster" van kaarten waar het naar keek. Om dit op te lossen, gebruikten ze een methode genaamd "partitioned window". Stel je voor dat je de lange lijst met instructies in stukken breekt en die stukken door elkaar schudt, zodat de AI niet alleen op positie kon vertrouwen. Het moest de feitelijke logica van de verwisselingen leren.
De Test: Ze testten de AI op een stapel van 16 kaarten.
Het Resultaat: Ook hier bereikte de AI bijna 100% nauwkeurigheid.

Hoe Kregen Ze Het Werkend? (Het Geheime Ingrediënt)

De onderzoekers gebruikten een slimme truc genaamd "Identity Augmentation".

Stel je voor dat je een recept schrijft, maar het receptenboek vereist dat elk recept precies 50 stappen lang is. Sommige recepten zijn van nature kort (slechts 5 stappen). Om in het boek te passen, moet je "dummy-stappen" toevoegen die zeggen "doen niets" (zoals "5 seconden stil staan") totdat je 50 stappen hebt bereikt.

De AI moest leren dat deze "doen niets"-stappen het resultaat niet veranderden. Door de korte instructies op te vullen met deze "identiteits"-stappen, leerde de AI het ruis te negeren en zich te concentreren op de feitelijke wiskunde.

Wat Leerde de AI Eigenlijk?

De onderzoekers keken in het "brein" van de AI (zijn interne data-representaties) om te zien wat het deed.

Het leerde relaties: De AI besefte dat het verwisselen van kaart A met kaart B hetzelfde is als het verwisselen van B met A.
Het leerde structuur: Het begreep dat de volgorde van verwisselingen belangrijk is, maar het leerde ook de regels voor wanneer de volgorde niet uitmaakt.
Het bedroog niet: De AI memoriseerde niet gewoon de antwoorden. Het moest de "algoritme" van hoe schudden werkt leren, omdat de testvragen verschillend waren van de trainingsvragen.

De Conclusie

Dit artikel bewijst dat AI-modellen complexe wiskundige regels kunnen leren uit kleine voorbeelden en ze kunnen toepassen op veel grotere, complexere versies van hetzelfde probleem.

De Analogie: Het is als een kind leren hoe je schoenen moet strikken met een klein oefenbord, en hen vervolgens een paar reuzenlaarzen geven. Het kind, dat de logica van de knoop heeft geleerd, kan de reuzenlaarzen perfect strikken.
De Beperking: De auteurs merken op dat hoewel dit geweldig werkt voor de "symmetrische groep" (kaarten schudden), andere wiskundige groepen rommeliger en moeilijker te leren kunnen zijn. Deze succesvolle poging suggereert echter dat AI uiteindelijk kan helpen bij het oplossen van andere moeilijke wiskundige problemen, zoals het "unknot-probleem" (knoesten ontwarren), wat momenteel zeer moeilijk is voor computers.

Kortom: De AI leerde om een meester-schudder te worden door te oefenen op een kleine stapel, en bewees dat machines met de juiste training kunnen generaliseren van "klein" naar "groot" in de pure wiskunde.

Technische Samenvatting: Het Leren van de Symmetrische Groep: Groot uit Klein

Probleemstelling
Het artikel onderzoekt of op Transformers gebaseerde neurale netwerken de structuur van de symmetrische groep $S_n$ kunnen leren door uitsluitend te trainen op kleinere ondergroepen $S_m$ (waarbij $m < n$ ) en vervolgens te generaliseren om permutaties in grotere groepen te voorspellen zonder groeprelaties hard te coderen. De specifieke taak bestaat erin een woord $w \in S_n$ , uitgedrukt als een product van transposities, te nemen en de resulterende permutatie van de verzameling $\{1, \dots, n\}$ te voorspellen. De auteurs behandelen twee verschillende formuleringen van dit probleem:

Algemene Transposities: Woorden gefactoriseerd met willekeurige transposities $s_{i,j}$ .
Aangrenzende Transposities: Woorden gefactoriseerd met uitsluitend elementaire aangrenzende transposities $s_i = s_{i,i+1}$ .

Een belangrijke uitdaging is het hanteren van variabele woordlengtes. De auteurs merken op dat de lengtes van gereduceerde woorden variëren van $0$ (identiteit) tot $n-1$ (algemeen geval) of $n(n-1)/2$ (aangrenzend geval). Om dit te beheersen, worden de modellen getraind op vaste lengte, niet-gereduceerde woorden die zijn aangevuld met identiteitstransposities.

Methodologie
De auteurs maken gebruik van een autoregressieve Transformer-architectuur (Figuur 1) die permutatietokens één voor één voorspelt. De invoer bestaat uit een "contextvenster" dat de transpositievolgorde en het gedeeltelijk voorspelde permutatie bevat.

Datageneratie en Augmentatie:
- Identiteitsaugmentatie: Om variabele lengtes te hanteren, worden woorden opgepadded tot een maximale lengte $N$ met transposities die als identiteiten werken onder groeprelaties. Het model moet deze relaties impliciet leren om de padding te negeren.
- Training op Ondergroepen: Het model wordt getraind op data gegenereerd vanuit $S_m$ (specifiek $m=10$ ), maar getest op $S_n$ ( $n=25$ voor algemeen, $n=16$ voor aangrenzend).
- Herverkenningsstrategie: Om trainingsdata voor $S_n$ $S_{n}$ te genereren die alleen $S_m$ $S_{m}$ betreft, mappingen de auteurs woorden van $S_m$ $S_{m}$ naar $S_n$ $S_{n}$ via een willekeurige permutatie $\sigma \in S_n$ $σ \in S_{n}$ .
  - Voor Algemene Transposities wordt een eenvoudige willekeurige herverdeling van indices $\{1, \dots, m\}$ naar een willekeurige deelverzameling van $\{1, \dots, n\}$ gebruikt.
  - Voor Aangrenzende Transposities faalde een naïeve "venster"-methode (herverdeling van $s_1, \dots, s_{m-1}$ naar een aaneengesloten blok $s_{k+1}, \dots$ ) omdat het model leerde om de vensterlocatie te identificeren in plaats van de groepstructuur. Om dit te counteren, introduceerden de auteurs een Gesplitst Venster-methode. Dit houdt in dat $m$ wordt ontbonden in een samenstelling (bijvoorbeeld $12 = 3+6+3$ ), waarbij meerdere niet-aaneengesloten vensters van variërende lengtes binnen $S_n$ worden gecreëerd, en de invoertokens worden gemapt naar deze vensters met willekeurige offsets. Dit dwingt het model om de lokale groeprelaties te leren in plaats van globale positionele aanwijzingen.
Architectuurdetails:
- Tokenisatie: Algemene transposities worden gemapt naar gehele getallen $x_k = i_k - 1 + n(j_k - 1)$ . Aangrenzende transposities worden direct gemapt naar indices $x_k = i_k$ .
- Embeddings: Het model maakt gebruik van geleerde token-embeddings en positionele embeddings. De invoer wordt verwerkt via standaard Transformer-lagen (multi-head attention, feed-forward, normalisatie) voordat een lineaire laag en Softmax-uitvoerprobabiliteiten volgen.

Belangrijkste Resultaten
De experimenten tonen aan dat de modellen bijna 100% nauwkeurigheid bereiken op out-of-distribution (OOD) testsets:

Algemene Transposities: Een model getraind op $S_{10}$ generaliseerde naar $S_{25}$ met nul trainingsverlies en bijna perfecte testprestaties (Figuur 2).
Aangrenzende Transposities: Een model getraind op $S_{10}$ generaliseerde naar $S_{16}$ met vergelijkbare hoge prestaties (Figuur 3). De auteurs merken op dat het aangrenzende geval theoretisch complexer is vanwege langere woordlengtes en strengere localiteitsbeperkingen, maar dat de gesplitste venstermethode generalisatie succesvol mogelijk maakte.

Observaties over Interpretatie
De auteurs analyseerden de zelfgelijkheids-heatmaps van de geleerde embeddings:

Algemene Transposities: De token-embeddingsmatrix onthulde een regelmatig roosterstructuur, wat aangeeft dat het model hoogwaardige relaties tussen generatoren heeft geleerd (bijvoorbeeld $s_{i,j}$ relateert sterk aan $s_{i,k}$ en $s_{j,i}$ ). De positionele embedding toonde geen intrinsieke orde onder algemene transposities.
Aangrenzende Transposities: De positionele embedding voor aangrenzende transposities vertoonde een verrassende bloksubstructuur binnen de eerste $n(n-1)/2$ rijen, hoewel de auteurs opmerken dat dit niet consistent was over alle groepsgroottes en de betekenis daarvan onduidelijk blijft.

Betekenis en Beweringen
Het artikel beweert aan te tonen dat Transformers de onderliggende algoritmische structuur van groepvermenigvuldiging kunnen leren uit kleine trainingssets en kunnen generaliseren naar aanzienlijk grotere groepen, zelfs wanneer de invoerrepresentatie verandert (via herverdeling en partitionering).

Schaalbaarheid: Het werk stelt een schaalbare methode voor waarbij modellen getraind op eenvoudigere structuren ( $S_m$ ) taken kunnen oplossen voor grotere, complexere groepen ( $S_n$ ).
Out-of-Distribution Leren: Dit dient als een specifiek voorbeeld van OOD-leren in de wiskunde, waarbij wordt aangetoond dat kenmerken geleerd op kleine ondergroepen universeel genoeg kunnen zijn om toe te passen op grotere groepen.
Toekomstige Richtingen: De auteurs suggereren dat deze aanpak inzichten kan bieden in het woordprobleem voor eindig gegenereerde groepen en toepassingen op NP-moeilijke problemen in vergelijkende genomica. Zij identificeren specifiek de vlechtgroep als een doel voor toekomstig werk, gemotiveerd door de relevantie voor het ontknopenprobleem, en merken op dat de symmetrische groep "goed gedragen" is en dat exotischere groepen grotere uitdagingen zullen presenteren.

De auteurs blijven bescheiden wat betreft de interne mechanismen, en stellen dat het een "open vraag" is of de modellen een algemeen algoritme hebben ontdekt of specifieke representaties hebben geleerd, en zij plannen om in toekomstig werk mechanistische interpretatieanalyse uit te voeren.