Technische Samenvatting: Eindige Steekproefcomplexiteit van Feedforward Neurale Netwerken in o-minimale Structuren

1. Probleemstelling

Het artikel adresseert een fundamentele vraag in de statistische leertheorie: Bezitten alle standaard, vaste eindige feedforward neurale netwerken een eindige steekproefcomplexiteit in het Probably Approximately Correct (PAC)-leermodel?

Hoewel specifieke architectuurfamilies (bijvoorbeeld piecewise-linear MLP's, specifieke GNN's of transformers) eerder zijn aangetoond als leerbare middels architectuurspecifieke argumenten (zoals VC-dimensie-omgrenzingen voor ReLU-netwerken), ontbrak een verenigde theoretische garantie die het brede spectrum van moderne architecturen dekt, inclusief die met onbegrensde parameters. De auteurs onderzoeken of de "tamme" aard van de wiskundige functies die deze netwerken samenstellen, voldoende is om leerbbaarheid te garanderen zonder restrictieve gewichtsbeperkingen op te leggen of te vertrouwen op ad-hoc combinatorische bewijzen voor elke nieuwe architectuur.

2. Methodologie en Theoretisch Kader

2.1 o-minimale Structuren

De kernmethodologie vertrouwt op o-minimale structuren, een concept uit de wiskundige logica en modeltheorie. Een o-minimale structuur $\mathcal{S}$ die het reële veld uitbreidt, is een collectie van deelverzamelingen van $\mathbb{R}^n$ die gesloten is onder Booleaanse operaties, projecties en Cartesische producten, met het cruciale kenmerk dat elke definieerbare deelverzameling van $\mathbb{R}$ een eindige unie van punten en intervallen is. Deze "tamheid" voorkomt de pathologische oscillaties die typisch leiden tot eindeloze VC-dimensies.

De auteurs maken gebruik van de volgende belangrijke logische hulpmiddelen:

• Definieerbaarheid: Een afbeelding is definieerbaar als zijn grafiek een definieerbare verzameling is binnen de structuur.
• Gemeenschappelijke Definieerbaarheid: De auteurs stellen vast dat als de primitieve bewerkingen (poorten) van een netwerk definieerbaar zijn, de gehele netwerkfunctie gemeenschappelijk definieerbaar is in zijn invoer en parameters.
• Cel-decompositie: Een fundamentele stelling in o-minimale meetkunde stelt dat elke definieerbare verzameling kan worden opgesplitst in een eindig aantal "cellen". Dit impliceert dat het aantal samenhangende componenten van niveauverzamelingen (oscillaties) van een definieerbare functie uniform begrensd is, ongeacht de parameterwaarden.

2.2 Netwerk Formalisering

Het artikel definieert een G-Neuraal Netwerk als een berekening die georganiseerd is door een Gerichte Acyclische Graaf (DAG).

• Knopen: Invoerknopen, berekeningsknopen (poorten) en uitvoerknopen.
• Poorten: Geparametriseerde afbeeldingen $g: \mathbb{R}^n \times \mathbb{R}^p \to \mathbb{R}^m$ geselecteerd uit een "poortwoordenlijst" $\mathcal{G}$.
• Compositie: Het netwerk berekent een functie $f_\theta(x)$ door toestanden door de DAG te propageren, waarbij $\theta$ de trainbare parameters voorstelt.

Het centrale technische inzicht is Propositie 2.5: Als elke poort in de woordenlijst $\mathcal{G}$ definieerbaar is in een o-minimale structuur $\mathcal{S}$, dan is het resulterende G-Neurale Netwerk gemeenschappelijk definieerbaar in zijn invoer en parameters.

3. Belangrijkste Bijdragen

3.1 Verenigde Leerbaarheidsstellingen

Het artikel biedt twee hoofdstellingen die eindige steekproefcomplexiteit vaststellen voor de agnostische PAC-setting:

• Stelling 3.1 (Classificatie): Voor elke vaste eindige feedforward architectuur met definieerbare lagen heeft de klasse van classifiers een eindige VC-dimensie. Bijgevolg convergeert het empirische risico uniform naar het ware risico met een steekproefcomplexiteitsgrens van $O(K \log(1/\delta) / \epsilon^2)$, waarbij $K$ afhangt van de architectuur maar niet van de grootte van de parameters.
• Stelling 3.2 (Regressie): Voor regressie met definieerbare verliesfuncties (bijvoorbeeld afgekapte MSE, MAE) heeft de klasse een eindige pseudo-dimensie (en vet-verbrokkelingsdimensie), wat vergelijkbare uniforme convergentiegaranties oplevert.

Cruciaal Onderscheid: Deze resultaten gelden zelfs wanneer de parameterruimte onbegrensd is. Traditionele argumenten over overdekkingsgetallen falen hier vaak omdat de metrische grootte van de parameterruimte divergeert naarmate de gewichten groeien. De o-minimale benadering omzeilt dit door de geometrische complexiteit (aantal oscillaties) van de functieklass te begrenzen in plaats van de metrische grootte van de parameterruimte.

3.2 Verificatie van Definieerbaarheid voor Moderne Architecturen

Een significant deel van het werk (Sectie 4) verifieert dat de "definieerbaarheidsaanname" mild is door aan te tonen dat standaard deep learning-componenten definieerbaar zijn in specifieke o-minimale structuren (voornamelijk $\mathbb{R}_{exp}$ en $\mathbb{R}_{an,exp}$):

• Lineaire/Convolutionele Lagen: Polynoomafbeeldingen (semi-algebraïsch).
• Activeringsfuncties: ReLU, LeakyReLU, Sigmoid, Tanh, Softplus, GELU, Swish, SwiGLU en Mish worden aangetoond als definieerbaar in $\mathbb{R}_{exp}$ of $\mathbb{R}_{an,exp}$.
• Aandachtsmechanismen: Multi-head self-attention en cross-attention zijn definieerbaar in $\mathbb{R}_{exp}$ vanwege de definieerbaarheid van de exponentiële functie en softmax.
• Normalisatie: Batch, Layer, Group en RMS normalisatie zijn semi-algebraïsch.
• Positie-encoding: Op Fourier gebaseerde encoding is definieerbaar mits het positiedomein begrensd is (een standaardbeperking in de praktijk).
• Geavanceerde Blokken: Residuele verbindingen, gating-mechanismen, Maxout en Deep Equilibrium (DEQ) lagen worden aangetoond als behoudend voor definieerbaarheid.

3.3 Architecturale Corollaria

Door de definieerbaarheid van primitieven te combineren met de sluitingseigenschappen van o-minimale structuren, leiden de auteurs af dat de volgende standaardarchitecturen een eindige steekproefcomplexiteit hebben:

• Multilayer Perceptrons (MLP's)
• Convolutionele Neurale Netwerken (CNN's)
• Graph Neural Networks (GNN's)
• Transformers (inclusief die met vaste sequentielengtes)

4. Resultaten en Betekenis

4.1 Hoofdresultaat

Het artikel concludeert dat distributie-vrije leerbbaarheid een universeel gevolg is van tamme feedforward berekening. Elke vaste eindige feedforward architectuur opgebouwd uit definieerbare primitieven (wat de overgrote meerderheid van moderne niet-recurrente modellen dekt) heeft een eindige steekproefcomplexiteit in de agnostische PAC-setting, ongeacht parametergrenzen.

4.2 Verschuiving in Perspectief

De auteurs betogen dat dit resultaat eindige steekproefcomplexiteit verplaatst van een "differentiator" naar een basis eigenschap.

• Vorige Visie: Leerbbaarheid werd vaak gezien als een fragiele eigenschap die specifieke architecturale beperkingen of activeringsfuncties vereiste om te bewijzen.
• Nieuwe Visie: Leerbbaarheid is automatisch voor elk "tam" feedforward model. Daarom zou de theoretische focus moeten verschuiven van het bewijzen of een model leert, naar het begrijpen hoe het leert.

4.3 Praktische Implicaties

Het artikel suggereert dat architecturale vergelijkingen geleid moeten worden door fijnere criteria in plaats van algemene leerbbaarheid:

• Inductieve Biases: Hoe goed de architectuur probleem-specifieke symmetrieën en geometrische priors codeert.
• Optimalisatiegedrag: Het landschap van de verliesfunctie en convergentie-eigenschappen.
• Schaalbaarheid: Rekenkundige efficiëntie en het vermogen om groeiende modelgroottes aan te kunnen.

4.4 Beperkingen

De auteurs merken expliciet de reikwijdte en beperkingen op:

• Vaste Architectuur: De resultaten zijn van toepassing op vaste diepte, breedte en graafgrootte. Ze bieden geen uniforme grenzen voor groeiende modelgroottes.
• Geen Recurrentie: Echte recurrente architecturen (RNN's, geloopte transformers) worden niet gedekt tenzij ze worden uitgerold tot een vaste tijds horizon.
• Kwalitatieve Aard: De grenzen zijn kwalitatief (existentie van constanten) in plaats van scherpe, architectuurspecifieke rates te bieden.
• Optimalisatie: Het artikel garandeert leerbbaarheid (existentie van een goede hypothese) maar maakt geen claims over de efficiëntie om deze te vinden (optimalisatiegaranties).

5. Conclusie

Het artikel stelt vast dat de wiskundige "tamheid" van moderne neurale netwerken, geformaliseerd via o-minimale structuren, voldoende is om eindige steekproefcomplexiteit te garanderen. Dit verenigt de leertheorie van diverse architecturen onder één raamwerk, wat suggereert dat het vermogen om te leren een generiek kenmerk is van feedforward berekening in plaats van een speciale eigenschap van specifieke ontwerpen. De auteurs concluderen dat toekomstig onderzoek zich moet richten op de specifieke inductieve biases en optimalisatiedynamiek die architecturen onderscheiden, in plaats van hun fundamentele capaciteit om te leren.