Neural Networks Provably Learn Spectral Representations for Group Composition

Technische Samenvatting: Neurale Netwerken Leren Bewijsbaar Spectrale Representaties voor Groepssamenstelling

Probleemstelling
Het artikel onderzoekt de opkomst van gestructureerde interne representaties tijdens de training van neurale netwerken, specifiek gericht op de taak van het leren van groepssamenstelling. Gegeven een eindige groep $(G, \star)$, is het doel om een twee-laags neuraal netwerk te trainen om het product $g_1 \star g_2$ te voorspellen voor elk paar $(g_1, g_2) \in G \times G$. Hoewel eerder werk heeft vastgesteld dat netwerken die modulaire optelling over cyclische groepen ($\mathbb{Z}_p$) leren, Fourier-features ontdekken (specialisatie naar een enkele frequentie), bleef het gedrag van netwerken die willekeurige eindige groepen leren — met name niet-Abelse groepen waar representaties matrix-gewaard zijn in plaats van scalair — theoretisch onkarakteriseerd. De centrale vraag is of neurale netwerken de irreducibele representaties (irreps) van een algemene groep $G$ ontdekken en hoe de principes van fase-uitlijning en laag-rang structuur, waargenomen in de Abelse context, zich generaliseren naar deze bredere context.

Methodologie
De auteurs analyseren een twee-laags volledig verbonden neuraal netwerk met een kwadratische activatie ($\sigma(x) = x^2$) dat getraind is op de volledige samenstellingstabel van een eindige groep $G$ met behulp van cross-entropy loss. De netwerkarchitectuur gebruikt afzonderlijke input-embeddings voor de twee operanden om niet-commutatieve operaties te faciliteren.

De theoretische analyse verloopt in twee stadia:

1. Stadium I (Feature Learning): De schalingfactoren van de neuronen worden vastgezet op een kleine constante $a$, en de directionele parameters (input en output embeddings) evolueren via geprojecteerde gradiëntflow op de eenheidsbol. De auteurs tillen de trainingsdynamiek van de Euclidische parameterruimte naar het spectrale domein met behulp van de Groep Discrete Fourier Transformatie (DFT). Zij demonstreren dat de geprojecteerde gradiëntflow equivalent is aan een Riemanniaanse gradiëntascens op een specifieke energiefunctie $\Omega_m$ gedefinieerd over de manifold van Fourier-coëfficiënten.
2. Stadium II (Scale Optimization): Zodra de directionele parameters convergeren, worden de schalingfactoren geoptimaliseerd om de marge te maximaliseren, waardoor de cross-entropy loss naar nul wordt gedreven.

De analyse leunt zwaar op harmonische analyse op eindige groepen, specifiek de orthogonaliteit van irreducibele representaties en de Schur-orthogonaliteitsrelaties. De auteurs maken gebruik van instrumenten uit de dynamische systemen, inclusief de classificatie van kritieke punten (evenwichten) en saddle avoidance-argumenten uitgebreid naar continue Riemanniaanse gradiëntflows, om convergentie-eigenschappen te bewijzen.

Belangrijkste Bijdragen en Resultaten

• Algemene Groeprepresentatie-lering (Theorem 4.3): Voor willekeurige eindige groepen (inclusief niet-Abelse groepen) bewijzen de auteurs dat onder willekeurige initialisatie de gradiëntflow elke neuron naar bijna zeker convergeert naar een staat die wordt gekenmerkt door:

  • Enkele Representatie: Elke neuron selecteert exact één niet-triviale irreducibele representatie $\check{\rho}_m$ (en haar duale $\check{\rho}_m^\vee$), waardoor alle Fourier-coëfficiënten die bij andere representaties horen verdwijnen.
  • Rank-Eén Rotationele Uitlijning: De Fourier-coëfficiënten van de overlevende representatie zijn rank-één matrices. Bovendien vertonen deze coëfficiënten over de input- en outputlagen een specifieke rotationele uitlijning: $\hat{\xi}_m[\rho] \propto \hat{\theta}_{2m}[\rho] \hat{\theta}_{1m}[\rho]$, en cyclische permutaties daarvan. Dit generaliseert de scalaire fase-uitlijning waargenomen bij modulaire optelling naar matrix-gewaardeerde representaties.
  • Mechanisme: Het bewijs stelt vast dat de trainingsdynamiek een energiefunctie maximaliseert. Niet-doel evenwichten (negatieve energie, nul energie met triviaal support, of hogere-rang positieve energie) worden aangetoond ofwel measure-zero vallen te zijn of strikte saddles, die bijna zeker worden vermeden door de gradiëntflow.

• Abelse Groep Karakterisering (Theorem 5.1 & 5.3): Voor Abelse groepen bieden de auteurs een volledige populatie-niveau beschrijving:

  • Diversificatie: Onder uniforme sferische initialisatie zijn de geleerde representaties uniform verdeeld over alle niet-triviale irreps, en de fasen zijn Haar-uniform op de eenheidscirkel, onafhankelijk van de gekozen representatie.
  • Flawed Indicator: De resulterende ensemble-voorspeller fungeert als een "flawed indicator", waarbij de hoogste logit wordt toegewezen aan het correcte groepsproduct $g_1 \star g_2$, met secundaire "ghost" pieken bij $g_1^2$ en $g_2^2$. Deze structuur ontstaat door de exacte annulering van ruistermen via de orthogonaliteit van representaties en het middelen over Haar-uniforme fasen.
  • Convergentiesnelheden: Het artikel stelt expliciete exponentiële convergentiesnelheden vast voor zowel fase-uitlijning als representatie-competitie. De selectie van de winnende representatie volgt een "lottery ticket" mechanisme, bepaald door de initiële spectrale magnituden.

• Stadium II Dynamica (Theorem 4.5): De auteurs bewijzen dat als de mean-field voorspeller aan een perfecte accuratesse-conditie voldoet (wat geldt voor Abelse groepen en empirisch is geverifieerd voor niet-Abelse gevallen), de schalingfactoren logaritmisch groeien, wat de softmax-distributie verscherpt en de loss naar nul drijft met een snelheid van $O(1/T)$.

Significantie en Claims
Het artikel beweert de eerste rigoureuze theoretische karakterisering te bieden van hoe neurale netwerken groepssamenstelling leren voor algemene eindige groepen. Door het fenomeen van "single-frequency specialization" in cyclische groepen te verenigen met het bredere kader van representatietheorie, tonen de auteurs aan dat gradiëntgebaseerde training natuurlijk irreducibele representaties selecteert en de geleerde matrix-gewaardeerde coëfficiënten tot rank één comprimeert.

De significantie ligt in:

1. Het overbruggen van Mechanistische Interpreteerbaarheid en Representatietheorie: Het werk formaliseert de link tussen emergente neurale features en de wiskundige structuur van de onderliggende groep, waarbij het laat zien dat de "Fourier-features" in modulaire optelling simpelweg het scalaire geval zijn van het leren van irreducibele representaties.
2. Nieuwe Laag-Rang Compressie: De ontdekking van rank-één rotationele uitlijning in matrix-gewaardeerde representaties voor niet-Abelse groepen is een nieuwe structurele bevinding die de laag-rang bias waargenomen in andere deep learning contexten naar het spectrale domein van groepoperaties uitbreidt.
3. Dynamische Verklaring: Het artikel gaat verder dan empirische observatie door een dynamisch systeem-gebaseerd bewijs (via Riemanniaanse gradiëntflow en saddle avoidance) te leveren dat verklaart waarom en hoe deze gestructureerde oplossingen vanuit willekeurige initialisatie emergeren.

De auteurs merken op dat hoewel hun resultaten algemene eindige groepen dekken, er openstaande problemen zijn met betrekking tot de theoretische karakterisering van limiterende distributies voor groepen met hoog-dimensionale irreps of zelf-geconjugeerde representaties, evenals de analyse van generalisatie-gaps (grokking) in eindige-sample settings.