💬 NLP

Lean Formalization of Generalization Error Bound by Rademacher Complexity and Dudley's Entropy Integral

Dit artikel presenteert een formalisatie in Lean 4 van generalisatiefoutgrenzen gebaseerd op Rademacher-complexiteit en Dudley's entropie-integraal, met een mechanisch geverifieerde pijplijn van maattheoretische fundamenten tot uniforme afwijkingsgrenzen met hoge waarschijnlijkheid en hun toepassing op lineaire voorspellers.

Oorspronkelijke auteurs: Sho Sonoda, Kazumi Kasaura, Yuma Mizuno, Kei Tsukamoto, Naoto Onda

Gepubliceerd 2026-05-26

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Sho Sonoda, Kazumi Kasaura, Yuma Mizuno, Kei Tsukamoto, Naoto Onda

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

Stel je voor dat je een chef-kok bent die net een nieuw recept heeft bedacht. Je hebt het 100 keer in je keuken bereid (de trainingsdata) en het smaakte elke keer perfect. Maar je wilt weten: als je ditzelfde recept voor een miljoen vreemden in een restaurant bereidt (de testdata), zal het dan nog steeds goed smaken?

In de wereld van machine learning heet dit het Generalisatieprobleem. Het artikel waar je naar vraagt, is een rigoureuze, door een computer gecontroleerde bewijsvoering die ons helpt deze vraag met wiskundige zekerheid te beantwoorden.

Hier is het verhaal van het artikel, opgesplitst in eenvoudige concepten en analogieën.

1. Het Probleem: De Kloof tussen "Keuken en Restaurant"

Wanneer een computer leert, probeert het een regel (een hypothese) te vinden die past bij de data die het ziet.

Trainingsfout: Hoe goed de regel past bij de data die het al heeft gezien (jouw 100 keukentests).
Testfout: Hoe goed de regel werkt op nieuwe data die het nog niet heeft gezien (de restaurantklanten).

Het gevaar is overfitting. Dit is als een chef die de exacte smaak van zijn 100 tests uit het hoofd leert, maar de principes van koken niet begrijpt. Als hij in het restaurant op een iets ander ingrediënt stuit, mislukt het gerecht. We hebben een manier nodig om te garanderen dat het "keukensucces" vertaalt naar "restaurantsucces".

2. Het Hulpmiddel: Rademacher-complexiteit (De "Muntopgooitest")

Om te meten hoe waarschijnlijk het is dat een recept overfit, gebruiken wiskundigen een hulpmiddel dat Rademacher-complexiteit heet.

Stel je een zak met munten voor. Je gooit ze, en ze landen volledig willekeurig op Kop (+1) of Munt (-1).

De Test: Je vraagt je recept (het leeralgoritme): "Kun je deze willekeurige muntopgooien voorspellen?"
De Logica: Als je recept een simpele, robuuste regel is, zou het deze willekeurige ruis niet moeten kunnen voorspellen. Het zou ongeveer 50% goed moeten hebben, puur door toeval.
Het Rode Vlaggetje: Als je recept te complex is (zoals een chef die elk detail uit het hoofd heeft geleerd), zou het per ongeluk een "patroon" kunnen vinden in de willekeurige muntopgooien en ze beter dan toeval voorspellen.

Rademacher-complexiteit meet precies hoe goed een model kan "valsspelen" door willekeurige ruis te passen. Hoe lager dit getal, hoe waarschijnlijker het model goed zal generaliseren naar nieuwe data.

3. De Prestatie: De "Digitale Dubbelcontrole"

De auteurs van dit artikel hebben deze wiskundige bewijzen niet alleen op papier geschreven; ze hebben ze gebouwd in een computerprogramma genaamd Lean 4.

Stel je Lean 4 voor als een superstreng, onwankelbaar redacteur.

De Oude Manier: Een wiskundige schrijft een bewijs op papier. Een menselijke reviewer leest het. Als de mens een klein logisch gat mist, kan het bewijs worden geaccepteerd, zelfs als het lichtjes verkeerd is.
De Nieuwe Manier (Dit Artikel): De auteurs voerden hun volledige bewijs in Lean in. De computer controleerde elke stap, elke definitie en elke aanname. Als er zelfs een klein ontbrekend verband was (zoals "Is deze functie meetbaar?"), zou de computer het verwerpen.

Het artikel beweert een mechanisch geverifieerde pijplijn te hebben gebouwd. Het begint met de basisdefinities, loopt door een "symmetrisatie"-truc (een slimme wiskundige shuffle) en eindigt met een garantie met hoge zekerheid dat de testfout niet veel slechter zal zijn dan de trainingsfout.

4. De Grote Hindernis: Het "Oneindige Bibliotheek"-probleem

In de echte wereld hebben machine learning-modellen vaak oneindige mogelijkheden (zoals een continu bereik van getallen voor gewichten).

Het Probleem: In wiskunde is het makkelijk om een eindige lijst van items te controleren (zoals 100 recepten). Het is veel moeilijker om een oneindige lijst te controleren. In computertaal kan het controleren van het "maximum" van een oneindige lijst soms de regels van de logica breken (problemen met meetbaarheid).
De Oplossing van het Artikel: De auteurs creëerden een slimme "brug". Ze bewezen de wiskunde eerst voor een aftelbare (eindige of opsommbare) verzameling hypothesen. Vervolgens toonden ze aan dat voor veel real-world modellen (die "separabele" topologische ruimten zijn), je de oneindige verzameling kunt benaderen met een aftelbare dichte deelverzameling (zoals het gebruik van een zeer fijn rooster om een gladde kromme te benaderen).
De Analogie: Stel je voor dat je de lengte van elke mogelijke persoon in de wereld wilt meten. Het is onmogelijk om iedereen te meten. Maar als je elke persoon meet die precies 1 cm uit elkaar ligt in lengte, kun je wiskundig bewijzen dat je meting iedereen anders met hoge precisie dekt. Het artikel formaliseerde deze "rooster"-truc zodat de computer het accepteert.

5. De Resultaten: Wat hebben ze bewezen?

Zodra de "motor" was gebouwd, reden ze hem door drie specifieke scenario's om te laten zien dat het werkt:

Lineaire Predictors met $\ell_2$ Regularisatie: Dit is als een model dat gedwongen wordt zijn "ingrediënten" (gewichten) klein en gebalanceerd te houden. Het artikel bewees de standaard wiskundige grens hiervoor.
Lineaire Predictors met $\ell_1$ Regularisatie: Dit dwingt het model om "spaarzaam" te zijn (slechts een paar ingrediënten gebruiken). Ze bewezen de grens hiervoor, wat een iets andere berekening inhoudt (met de vierkantswortel van het aantal kenmerken).
Dudley's Entropie-integraal: Dit is een meer geavanceerd, algemeen hulpmiddel. Stel je voor dat je een zeer rommelige, complexe vorm hebt. In plaats van het hele ding te meten, bedek je het met kleinere, eenvoudigere vormen (zoals het bedekken van een hobbelige rots met gladde kiezels). Het artikel formaliseerde hoe je de complexiteit kunt berekenen op basis van hoeveel "kiezels" je nodig hebt om de vorm te bedekken.

Samenvatting

Dit artikel is een fundamentele ingenieursprestatie.

Wat ze deden: Ze namen complexe, schoolboektheorieën over hoe machine learning-modellen generaliseren (Rademacher-complexiteit) en vertaalden ze naar een taal die een computer met 100% zekerheid kan verifiëren.
Waarom het belangrijk is: Het verwijdert de "menselijke fout" uit de meest kritieke veiligheidsgaranties van AI. Het bewijst dat als je deze specifieke wiskundige regels volgt, je model niet alleen het verleden zal uit het hoofd leren; het zal echt leren voor de toekomst.
De Metafoor: Ze hebben niet alleen een recept voor een veilig cake geschreven; ze hebben een robot gebouwd die elk ingrediënt en elke stap van het recept controleert om ervoor te zorgen dat de cake nooit zal instorten, ongeacht wie hem eet.

Technische Samenvatting: Lean-formalisering van de Generalisatiefoutgrens via Rademacher-complexiteit en Dudley's Entropie-integraal

Probleemstelling

De centrale uitdaging die wordt aangepakt, is de formele verificatie van generalisatieprestaties in machine learning. Specifiek streven de auteurs ernaar theoretische schattingen van de testfout (populatierisico) af te leiden uit de trainingsfout (empirisch risico) met behulp van een maattheoretisch raamwerk. Waar klassieke benaderingen vertrouwen op de Vapnik–Chervonenkis (VC)-dimension, zijn deze vaak data-onafhankelijk en toegespitst op binaire classificatie. Moderne leertheorie maakt steeds meer gebruik van Rademacher-complexiteit, die scherpe, data-afhankelijke grenzen biedt die van toepassing zijn op reëelwaardige verliezen en diverse functieklassen (bijvoorbeeld deep learning, kernelmethoden). Het formaliseren van deze argumenten in bewijshulpmiddelen is echter moeilijk vanwege de noodzaak van een rigoureuze behandeling van meetbaarheid (met name voor supremums over overaftelbare hypotheseklassen), productmaten en concentratieongelijkheden.

Methodologie

De auteurs formaliseren de generalisatiefoutgrens in Lean 4, waarbij ze gebruikmaken van de uitgebreide maattheoretische probabiliteitsinfrastructuur van de Mathlib-bibliotheek. De ontwikkeling volgt de standaard "symmetrisatie + begrensd verschil"-piplijn die in handboeken wordt aangetroffen (bijvoorbeeld Mohri et al., Wainwright), maar past deze aan aan de beperkingen van formele verificatie:

Maattheoretische Opzet: Het raamwerk modelleert datageneratie via een kansruimte $(\Omega, m_\Omega, \mu)$ en een stochastische variabele $X: \Omega \to \mathcal{X}$ . Steekproeven worden gemodelleerd als functies $\omega: \text{Fin } n \to \Omega$ , die worden doorgeschoven om $S = X \circ \omega$ te verkrijgen.
Kerndefinities:
- Rademacher-complexiteit: Gedefinieerd voor zowel empirische (over een vaste steekproef $S$ ) als verwachte (over het productmaat $\mu^n$ ) gevallen. De empirische versie middelt over alle tekenvectoren $\sigma \in \{-1, 1\}^n$ .
- Uniforme Afwijking: Gedefinieerd als het supremum van het absolute verschil tussen empirische en populatiegemiddelden over een hypotheseklasse $F = \{f_i\}_{i \in \iota}$ .
Symmetrisatie: Een formeel theorem (abs_symmetrization_equation) vervangt het supremum van verschillen tussen twee onafhankelijke steekproeven door een gemiddelde over teken-gespiegelde sommen, waardoor de uniforme afwijking wordt gekoppeld aan Rademacher-complexiteit.
Concentratie: De auteurs bewijzen een McDiarmid-ongelijkheid vanaf de basis binnen Lean. Zij stellen vast dat de functionaal voor uniforme afwijking voldoet aan de eigenschap van begrenste verschillen (het veranderen van één steekproefpunt verandert de waarde met maximaal $2b/n$ ), wat de afleiding van staartgrenzen met hoge waarschijnlijkheid mogelijk maakt.
Omgaan met Overaftelbare Indexverzamelingen: Een kritieke technische hindernis is de meetbaarheid van supremums over overaftelbare indexverzamelingen $\iota$ $ι$ . Mathlib biedt meetbaarheid voor aftelbare indices, maar niet automatisch voor overaftelbare. De auteurs lossen dit op door:
- Eerst stellingen te bewijzen voor aftelbare indexverzamelingen.
- Resultaten uit te breiden naar separabele topologische indexverzamelingen via een aftelbare dichte reductie. Dit houdt in dat wordt bewezen dat voor continue functies het supremum over een separabele ruimte gelijk is aan het supremum over een aftelbare dichte deelverzameling, mits continuïteit behouden blijft onder integratie (gewaarborgd door uniforme dominantie).

Belangrijkste Bijdragen

Het artikel presenteert de eerste systematische formalisering van generalisatieanalyse via Rademacher-complexiteit. De specifieke bijdragen omvatten:

Herbruikbare Formele Infrastructuur: Een mechanisch gecontroleerde pijplijn die empirische/verwachte Rademacher-complexiteit, symmetrisatie, analyse van begrenste verschillen en de ongelijkheid van McDiarmid omvat.
Oplossing voor Meetbaarheid: Een herbruikbaar mechanisme om resultaten te heffen van aftelbare hypotheseklassen naar separabele topologische parameterruimten. Dit verpakt expliciet de voldoende voorwaarden (separabiliteit, eerste-telbaarheid, uniforme dominantie en continuïteit onder integratie) die nodig zijn om overaftelbare supremums meetbaar te maken, een stap die in informele bewijzen vaak impliciet is.
Geformaliseerde Concentratie-instrumenten: Een volledig bewijs van de ongelijkheid van McDiarmid en ondersteunende lemma's voor maximale ongelijkheden, Massart's lemma en overdekkingsgetallen.
Doorgewerkte Toepassingen:
- Lineaire Predictors: Formalisering van standaard $O(1/\sqrt{n})$ -grenzen voor $\ell_2$ -geregulariseerde predictors en $O(\sqrt{\log(d)/n})$ -grenzen voor $\ell_1$ -geregulariseerde predictors.
- Dudley's Entropie-integraal: Een formalisering van de Dudley-achtige grens die Rademacher-complexiteit relateert aan overdekkingsgetallen via een chaining-constructie. Dit vereiste het definiëren van empirische pseudo-metrieken en het behandelen van de overgang van discrete chaining-sommen naar integraalgrenzen.

Resultaten

De formalisatie levert mechanisch geverifieerde versies op van standaard leer-theoretische grenzen:

Verwachte Grens: $E[\text{UD}_n(F)] \leq 2 R_n(F)$ , waarbij $R_n(F)$ de Rademacher-complexiteit is.
Grens met Hoge Waarschijnlijkheid: Voor elke $\delta \in (0, 1)$ , met waarschijnlijkheid ten minste $1-\delta$ :
$\text{UD}_n(F) \leq 2 R_n(F) + b \sqrt{\frac{2 \log(1/\delta)}{n}}$
Specifieke Grenzen: Het repository biedt concrete bewijzen voor de empirische Rademacher-complexiteit van lineaire predictors onder $\ell_2$ - en $\ell_1$ -beperkingen, evenals de Dudley-entropie-integraalgrens.

Betekenis en Claims

De auteurs positioneren dit werk als een fundamentele stap richting betrouwbare, gecertificeerde machine learning-theorie.

Brug tussen Theorie en Verificatie: Het werk toont aan dat moderne, maattheoretische leertheorie (die vertrouwen op productmaten, integreerbaarheid van omhulsels en concentratie) kan worden geformaliseerd in een bewijshulpmiddel zonder terug te vallen op overmatig vereenvoudigde discrete proxies.
Verduidelijking van Impliciete Aannames: Een primaire bijdrage is de expliciete identificatie van de voorwaarden die nodig zijn om overaftelbare hypotheseklassen te behandelen. De formalisatie isoleert de "aftelbaar-dichte reductie" en de specifieke continuïteits/integreerbaarheids-hypothesen die nodig zijn, die in standaardhandboeken vaak worden over het hoofd gezien.
Modulariteit: De ontwikkeling is zo ontworpen dat de abstracte Rademacher-pijplijn herbruikbaar is. Concrete grenzen worden "uitvoerbare corollaria" die worden verkregen door de functieklassen te实例eren en specifieke analytische schattingen (bijvoorbeeld normbeperkingen) te ontladen.
Vergelijking met Eerdere Werk: In tegenstelling tot eerdere formalisaties die beperkt waren tot eindige hypotheseklassen (bijvoorbeeld Bagnall & Stewart) of specifieke algoritmische gevallen (bijvoorbeeld decision stumps), behandelt dit werk algemene, potentieel overaftelbare functieklassen met reëelwaardige verliezen.

Het artikel concludeert dat hoewel de wiskundige grenzen zelf klassiek zijn, de formalisatie de precieze logische structuur en nevenvoorwaarden verduidelijkt die noodzakelijk zijn voor hun geldigheid in een rigoureuze setting, en zo een fundament biedt voor toekomstige uitbreidingen zoals Lipschitz-contractie-ongelijkheden en connecties met Gaussische complexiteit.