Technische Samenvatting: Neuronale Gewichtsnorm = Kolmogorov-complexiteit

Probleemstelling

Het artikel behandelt een fundamentele vraag in de theorie van deep learning: Waarom werkt gewichtsdecay? Hoewel gewichtsdecay de meest universeel toegepaste regularisator is in modern deep learning, falen klassieke op capaciteit gebaseerde leertheorieën (zoals VC-dimensie en Rademacher-complexiteit) om de effectiviteit ervan te verklaren. Deze theorieën karakteriseren de functieklassen van een netwerk, maar kunnen geen onderscheid maken tussen een netwerk dat met gewichtsdecay is getraind en een netwerk zonder, aangezien de functieklassen identiek blijven ongeacht de regularisator. Bovendien kunnen architecturen die in staat zijn om te generaliseren op echte data, worden getraind om willekeurige labels te memoriseren, wat suggereert dat generalisatie niet uitsluitend een eigenschap is van de grootte van de functieklassen.

De auteurs stellen dat de verklaring ligt in de theorie van beschrijvingslengte, specifiek de Kolmogorov-complexiteit ($K(s)$), die de lengte meet van het kortste programma dat een string $s$ produceert. Hoewel Solomonoofs universele prior, afgeleid van $K(s)$, theoretisch optimaal is voor induktie, is deze niet-berekenbaar. De kloof tussen dit asymptotische ideaal en praktische regularisatoren zoals gewichtsdecay is tot nu toe onoverbrugd gebleven. Dit artikel tracht te bewijzen dat, onder specifieke voorwaarden, de gewichtsnorm van een neurale netwerk direct equivalent is aan de Kolmogorov-complexiteit van zijn output.

Methodologie en Model

Het artikel legt een rigoureuze verbinding tussen gewichtsnormen en Kolmogorov-complexiteit binnen een regime met vaste precisie.

1. Beperking tot Vaste Precisie: De auteurs betogen dat de vraag naar de relatie tussen gewichtsnorm en Kolmogorov-complexiteit alleen niet-triviaal is in regimes met vaste precisie (bijv. fp16, int8). In regimes met oneindige precisie (reële of rationale gewichten) kunnen netwerken niet-berekenbare functies of willekeurige hoeveelheden informatie coderen in een enkel gewicht, waardoor de norm irrelevant wordt voor de beschrijvingslengte. In vaste precisie is elk gewicht een object van $O(1)$-bits, wat garandeert dat grootte en beschrijvingslengte samen opschalen.
2. Geloopde Neuronale Netwerken: Het model maakt gebruik van geloopde neuronale netwerken, gedefinieerd als een enkel feedforward-blok dat wordt geïtereerd totdat een aangewezen "stop"-kanaal activeert. Deze architectuur is Turing-compleet bij constante precisie (met verwijzing naar Li en Wang, Giannou et al.) en vangt de recurrente dieptetoewijzing op die wordt gebruikt in Universele Transformers en chain-of-thought-resoneren.
3. Neuronale Complexiteit ($N(s)$): De auteurs definiëren $N(s)$ als het minimumaantal niet-nul parameters dat nodig is voor een geloopd netwerk met vaste precisie om te stoppen en een specifieke binaire string $s$ te outputten.
4. Norminstorting: Een belangrijke observatie is dat in elk regime met vaste precisie elke $L_p$-norm, verheven tot de macht $p$, equivalent is aan het aantal niet-nul parameters ($\|\theta\|_0$) tot op constante factoren. Specifiek geldt: $\delta^p \|\theta\|_0 \le \|\theta\|_p^p \le M^p \|\theta\|_0$. Dit impliceert dat regularisatie met $L_1$, $L_2$ of elke $L_p$-norm effectief dezelfde onderliggende grootheid controleert: de sparsiteit van het netwerk.

Belangrijkste Bijdragen en Resultaten

1. Het Hoofdstelling (Sandwich-grens)

Het centrale resultaat is een tweezijdige grens die de neuronale complexiteit $N(s)$ relateert aan de Kolmogorov-complexiteit $K(s)$ van de outputstring $s$:
$$N(s) \le K(s) \le N(s) \log N(s)$$
Deze grens geldt tot op additieve en multiplicatieve constanten die afhankelijk zijn van de universele Turing-machine en de netwerkarchitectuur, maar niet van de string $s$.

• Ondergrens ($N(s) \le K(s) + c_U$): De auteurs bewijzen dat elk programma $p$ voor een universele Turing-machine kan worden gecodeerd in de gewichten van een geloopd netwerk met vaste precisie, met een kostprijs van één niet-nul parameter per programmabits. Dit wordt bereikt door de programmabits vooraf te laden in een aangewezen inputregio van een universeel geloopd netwerk via een routeringslaag.
• Bovengrens ($K(s) \le c_d \cdot N(s) \log N(s) + c_d$): Omgekeerd kan elk netwerk met vaste precisie worden beschreven door de opsomming van zijn niet-nul parameters. Aangezien elke parameter de specificatie van zijn locatie (adres) en waarde vereist, en er $W$ niet-nul parameters zijn, is de beschrijvingslengte $O(W \log W)$. De logaritmische factor ontstaat uit de adresruimte die nodig is om de locatie van elke niet-nul parameter aan te geven binnen het totale aantal mogelijke verbindingen.

2. Striktheid van de Grenzen

Het artikel toont aan dat de logaritmische factor in de bovengrens fundamenteel is en geen artefact van het bewijs.

• Permutatiegetuige: De auteurs construeren een familie van strings gebaseerd op permutaties $\pi: [N] \to [N]$. Het coderen van een permutatie vereist $N$ niet-nul parameters (ternaire randen) om de mapping te specificeren. De Kolmogorov-complexiteit van de resulterende string is $\Theta(N \log N)$ omdat er $N!$ mogelijke permutaties zijn.
• Dit voorbeeld toont aan dat een netwerk het volledige $\log W$-budget per parameter kan "inzetten", wat bewijst dat de grens strak is voor ongestructureerde architecturen.

3. Verbinding met Solomonoofs Universele Prior

Het artikel leidt een corollarium af met betrekking tot de geïnduceerde prior op de output van het netwerk.

• Gewichtsdecay (bijv. $L_2$) komt overeen met een Gaussische prior op gewichten. In vaste precisie is deze prior equivalent aan een sparsiteitsprior ($\propto 2^{-\|\theta\|_0}$) tot op constanten.
• Bijgevolg komt de geïnduceerde prior op de outputstring $Q(s)$ overeen met Solomonoofs universele prior $M(s)$ tot op een logaritmische factor in de exponent:
  $$2^{-K(s) - \alpha} \le Q(s) \le 2^{-K(s) / (\beta \log K(s))}$$
• Dit impliceert dat gewichtsdecay een prior induceert die asymptotisch optimaal is voor berekenbare hypothesen, en overeenkomt met de prior die een geïdealiseerd, onbeperkt Bayesiaans agent zou kiezen.

4. Generalisatiegrens

Met behulp van de codering van netwerken als programma's leiden de auteurs een generalisatiegrens in de stijl van MDL af. De complexiteitsstraf schaalt als $\|\theta\|_2^2 \log \|\theta\|_2^2$, wat suggereert dat de effectieve complexiteit voor het voorspellen van generalisatie de log-verrijkte kwadratische norm is, en niet het ruwe aantal parameters.

Betekenis en Beweringen

Het artikel claimt de kloof te dichten tussen het asymptotische ideaal van Solomonoofse induktie en de praktische regularisator van gewichtsdecay. De betekenis ligt in:

1. Norm-agnostisch Resultaat: Het resultaat geldt voor elke $L_p$-norm in vaste precisie, aangezien ze allemaal instorten tot het aantal niet-nul parameters.
2. Noodzaak van Vaste Precisie: De auteurs benadrukken dat de aanname van vaste precisie geen technische gemakskwestie is, maar de substantiële inhoud van het resultaat. Zonder deze aanname breekt de relatie tussen gewichtsnorm en Kolmogorov-complexiteit af vanwege de super-Turing-capaciteiten van reëelwaardige gewichten.
3. Theoretische Rechtvaardiging voor Gewichtsdecay: Het biedt een kwantitatieve, tweezijdige link die aantoont dat de meest betrouwbare regularisator in modern deep learning een hanteerbare proxy is voor de optimale inductieve bias over berekenbare functies.
4. Beperkingen: De auteurs zijn bescheiden over de praktische implicaties, en merken op dat de constanten in de grenzen waarschijnlijk groot zijn voor realistische architecturen, waardoor het resultaat conceptueel is in plaats van voorspellend op kleine schaal. De theorie is van toepassing op geloopde netwerken die strings uitzenden vanuit een nul-initiële staat, en uitbreidingen naar standaard settings voor toezicht op leren (feedforward, gebatchte inputs) worden hier niet in detail behandeld.

Kortom, het artikel stelt vast dat in het regime met vaste precisie dat wordt gebruikt door moderne hardware, gewichtsdecay effectief een mechanisme is voor het minimaliseren van de Kolmogorov-complexiteit van de output van het netwerk, en aldus de optimale prior induceert voor berekenbare induktie.