Technische Samenvatting: Karakterisering van Leren in Diepe Neuronale Netwerken met Behulp van Berekenbare Algorithmische Complexiteitsanalyse

Probleemstelling

Het trainen van diepe neuronale netwerken (DNN's) op grote schaal wordt steeds meer resource-intensief, wat noodzaak maakt van compressietechnieken voor modellen zoals pruning, kennisdistillatie en kwantisatie. De hypothese "leren als compressie" stelt dat training structurele organisatie in de netwerkgewichten induceert, waardoor compressie mogelijk wordt. Waar Kolmogorov-Chaitin-Solomonoff (KCS)-complexiteit de theoretische maatstaf is voor het meten van dergelijke structuur, is deze niet-berekenbaar. Bestaande schatters gebaseerd op de Coding Theorem Method (CTM) en de Block Decomposition Method (BDM) zijn beperkt tot kleine binaire objecten en schalen niet naar moderne DNN's, die grote, niet-binaire (float) gewichtstensors omvatten. Bovendien vertrouwen bestaande methoden vaak op binarisatie, wat verliesgevend kan zijn en betekenisvolle structurele informatie kan verdoezelen.

Methodologie: Gequantiseerde Blokdecompositie (QuBD)

Om schaalbaarheid en precisiebeperkingen aan te pakken, introduceren de auteurs de methode Quantized Block Decomposition (QuBD). Deze benadering breidt de schatting van algorithmische complexiteit uit naar elk $k$-air object via de volgende pijplijn:

1. Quantisatie: Netwerkgewichten $W \in \mathbb{R}^d$ worden afgebeeld op een eindig alfabet $\Sigma_q$ met behulp van een affiene uniforme quantizer, resulterend in gehele code $W^{(q)}$.
2. Bit-Plaat Decompositie: Elk gekwantiseerd gewicht wordt ontbonden in zijn binaire expansie over $q$ bit-Platen. De $l$-de bit-Plaat $\beta_l$ verzamelt het $l$-de bit van alle $d$ symbolen.
3. Aggregatie: De KCS-complexiteit wordt geschat door per-bit-Plaat CTM-schattingen te aggregeren. De totale complexiteit wordt berekend als $C_{QuBD}(W) = \sum_{l=0}^{q-1} C(\beta_l)$, waarbij $C(\beta_l)$ is afgeleid van vooraf berekende CTM-tabellen voor kleine binaire blokken.

Theoretische Voordelen:
Het artikel levert theoretische bewijzen die aantonen dat QuBD een strikt nauwkeurigere schattingskloof oplevert ten opzichte van de ware KCS-complexiteit in vergelijking met op binarisatie gebaseerde methoden.

• Residudecompositie (Stelling 3.1): Het artikel formaliseert dat het schatten van een object vanuit zijn gekwantiseerde prefix $y_q$ residu-informatie $R_q$ mist die is opgeslagen in de weggegooide lagere bits.
• Bit-Plaat Residuverlies (Stelling 3.2): Er wordt bewezen dat het toevoegen van bit-Platen het residuverlies vermindert. Specifiek levert het behouden van meerdere bit-Platen een strikt kleiner residu op dan één-bit binarisatie, mits de bit-Platen niet identiek zijn.
• Saturatieanalyse: De auteurs analyseren de "saturatie" van eindige CTM-tabellen. Zij tonen aan dat hoewel serialisatie (platleggen van alle bits) CTM-tabellen snel verzadigt vanwege de enorme hoeveelheid blokken, bit-Plaat decompositie de draagwijdte effectief schaalt door lokale structuren onafhankelijk over de platen te evalueren, waardoor informatieve schattingen op grotere schalen behouden blijven.

Belangrijkste Resultaten

Met behulp van QuBD bieden de auteurs de eerste schaalbare empirische karakterisering van leerdynamiek in DNN's buiten eenvoudige feedforward-netwerken:

• Complexiteitsreductie tijdens Training: Naarmate modellen leren, neemt de algorithmische complexiteit van hun gewichten af. Dit wordt waargenomen bij Multi-Layer Perceptrons (MLP's) en Vision Transformers (ViT's), waarbij complexiteitsreductie correleert met verbeterde testnauwkeurigheid.
• Overfitting en Complexiteit: Tijdens overfitting neemt de algorithmische complexiteit toe. Dit suggereert dat memorisatie structuur introduceert die algorithmisch complex is (minder comprimeerbaar), in tegenstelling tot de vereenvoudiging die tijdens generalisatie wordt waargenomen.
• Grokking-fenomeen: In "grokking"-experimenten (waarbij modellen na een lange periode van overfitting goed generaliseren) blijft de QuBD-complexiteit hoog tijdens de fase met hoge validatieverlies en neemt deze pas significant af zodra het validatieverlies naar nul daalt, waarmee de vertraagde generalisatie wordt gevolgd.
• Verdeling van Bit-Plaat Informatie: Algorithmische informatie is niet uniform verdeeld. De meest significante bit-Platen (MSB) vertonen de grootste complexiteitsreductie (wat wijst op hoge structuur), terwijl lagere bit-Platen vaak complexiteitsverhoudingen tonen die dicht bij 100% liggen (willekeurig).
• Diagnose voor Compressie: De concentratie van algorithmische informatie in de MSB's correleert met de prestaties van Post-Training Quantization (PTQ). Modellen kunnen worden gekwantiseerd tot 4–6 bits met minimaal verlies aan nauwkeurigheid, aangezien de lagere bit-Platen verwaarloosbare algorithmische informatie bevatten. QuBD-complexiteit dient als een praktische diagnose om optimale kwantisatieniveaus te bepalen en lagen te identificeren die geschikt zijn voor pruning.

Betekenis en Aanspraken

Het artikel claimt de eerste schaalbare, berekenbare schattingen van KCS-complexiteit voor grote, niet-binaire objecten zoals DNN-gewichten te bieden. De betekenis hiervan ligt in:

1. Operationalisering van "Leren als Compressie": Het levert empirisch bewijs dat training structuur induceert in gewichten, meetbaar via algorithmische complexiteit, wat de hypothese ondersteunt dat leren een proces van compressie is.
2. Theoretische Superieurtiteit: Het stelt theoretisch vast dat bit-Plaat decompositie een strakkere bovengrens biedt voor KCS-complexiteit dan binarisatie, waarmee een fundamentele beperking in eerdere toepassingen van algorithmische informatietheorie op DNN's wordt aangepakt.
3. Praktisch Nut: Het toont aan dat algorithmische complexiteitsanalyse kan dienen als diagnosehulpmiddel voor modelcompressie, waarbij redundante capaciteit (bijvoorbeeld lagere bit-Platen of specifieke lagen) wordt geïdentificeerd zonder prestatieverlies te vereisen.

De auteurs concluderen dat algorithmische informatietheorie een krachtig paradigma biedt voor het verklaren van mechanismen van diep leren, en een concrete methode biedt om leerdynamiek te karakteriseren die overeenkomt met generalisatieprestaties en fenomenen zoals grokking.