🤖 machine learning

Null Measurability at the Symmetrization Interface in VC Learning

Dit artikel toont aan dat de eis van Borel-meetbaarheid voor ghost-gap-suprema in het standaard symmetrisatiebewijs voor VC-leren sterker is dan nodig, en laat in plaats daarvan zien dat de relevante slechte gebeurtenissen analytisch zijn en dus meetbaar in de voltooiing van elke eindige Borel-maat, een resultaat dat in Lean 4 is geformaliseerd en de meetbaarheidshypothese verzwakt die nodig zijn om PAC-lerbaarheid te vestigen.

Oorspronkelijke auteurs: Dhruv Gupta

Gepubliceerd 2026-04-29

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Dhruv Gupta

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 probeert een robot te leren katten op foto's te herkennen. Je hebt een enorme bibliotheek met mogelijke "regels" (hypothese) die de robot kan gebruiken om te beslissen of een afbeelding een kat is. Sommige regels zijn simpel, andere zijn ongelooflijk complex. Het doel is om aan te tonen dat, als je bibliotheek niet te chaotisch is (een eindige "VC-dimensie" heeft), de robot uiteindelijk de juiste regel zal leren door slechts een paar voorbeelden te bekijken.

Decennialang hebben wiskundigen een standaardbewijs voor dit probleem, genaamd Symmetrisatie. Het is als een goocheltruc waarbij je de prestaties van de robot vergelijkt op een "trainingsset" (foto's die het heeft gezien) met een "spookset" (foto's die het nog niet heeft gezien). Als de robot veel beter presteert op de trainingsfoto's dan op de spookfoto's, dan is het aan het valsspelen (overfitting).

Er zit echter een verborgen struikelblok in deze goocheltruc. Om de wiskunde te laten werken, eist het bewijs doorgaans dat het "slechte gebeurtenis" (het moment waarop de robot valsspelt) een Borel-meetbare verzameling moet zijn. In de wereld van geavanceerde wiskunde is een Borel-meetbare verzameling een zeer goed georganiseerde, nette vorm. Het is als een perfecte cirkel of een vierkant.

Het Probleem:
De auteurs van dit artikel, Dhruv Gupta, beseften dat het standaardbewijs te kieskeurig is. Het staat aan op een "perfect nette" vorm voor het slechte gebeurtenis, maar de wiskunde heeft dat niveau van perfectie eigenlijk niet nodig. Het is alsof je erop staat dat je alleen een rivier kunt oversteken als je een onberispelijke, marmeren brug hebt, terwijl een stevige, iets ruwe houten plank je eigenlijk net zo goed over de rivier zou krijgen.

De Ontdekking:
Gupta toont aan dat voor de specifieke "spookkloof" die in dit bewijs wordt gebruikt, het slechte gebeurtenis niet hoeft te zijn een perfecte Borel-meetbare verzameling. Het hoeft alleen maar Nul-maatbaar te zijn.

Hier is de analogie:

Borel-meetbare verzameling: Een vorm die je kunt tekenen met een liniaal en passer. Het is perfect gedefinieerd.
Analytische verzameling: Een vorm die de "schaduw" is van een object in een hogere dimensie. Het kan wat wazig of complex zijn, maar het is nog steeds een echte vorm.
Nul-maatbaar: Een vorm die misschien wazig is, maar als je probeert het te meten met een standaardliniaal (kans), gedraagt het zich precies als een normale vorm. Het is "goed genoeg" voor de wiskunde om te werken.

Gupta bewijst dat het "slechte gebeurtenis" in het leerproces van de robot altijd een Analytische verzameling is. Dankzij een beroemd wiskundig hulpmiddel genaamd Choquet-capaciteit weten we dat alle Analytische verzamelingen "Nul-maatbaar" zijn.

Waarom maakt dit uit?

Het is een losser Regel: Het artikel bewijst dat de eis van "Borel" te streng is. Er zijn conceptklassen (bibliotheken met regels) die perfect geschikt zijn voor leren, maar falen in de "Borel"-test omdat hun slechte gebeurtenissen "wazig" zijn (Analytisch maar niet Borel-meetbaar). Onder de oude regels zouden deze bibliotheken worden afgewezen als "onleerbaar" puur om een technische reden. Onder Gupta's nieuwe regels worden ze geaccepteerd.
Het is Stabiel: Het artikel toont aan dat als je twee "goede" bibliotheken combineert (door ze aan elkaar te plakken of te mixen), het resultaat nog steeds "goed" is onder deze nieuwe, losse regel. Je creëert niet per ongeluk een "slechte" bibliotheek door gewoon goede bibliotheken te combineren.
Het is Geverifieerd door een Robot: De auteur heeft dit niet alleen op papier geschreven; ze hebben een computerbewijshulpmiddel genaamd Lean 4 gebruikt om elke stap te controleren. Dit zorgt ervoor dat er geen menselijke fouten in de logica zitten.

De Strikte Scheiding:
Om te bewijzen dat de oude regel inderdaad te streng was, bouwde Gupta een specifiek voorbeeld (een "getuige"). Hij creëerde een bibliotheek met regels waarbij het "slechte gebeurtenis" een vorm is die Analytisch maar niet Borel-meetbaar is.

Onder de oude regels: Deze bibliotheek is "illegaal" omdat het slechte gebeurtenis geen perfecte Borel-meetbare verzameling is.
Onder de nieuwe regels: Deze bibliotheek is "legaal" omdat het slechte gebeurtenis Nul-maatbaar is.
Dit bewijst dat de nieuwe regel strikt zwakker (meer inclusief) is dan de oude.

Samenvattend:
Dit artikel gaat over het opschonen van de fundamenten van de theorie van machine learning. Het zegt: "We hebben een diamant vereist om een huis te bouwen, maar een hoogwaardige baksteen werkt net zo goed en laat ons meer huizen bouwen." Het versoepelt de wiskundige eisen voor het bewijzen dat een machine learning-algoritme zal werken, waardoor de theorie toepasbaar wordt op een breder scala aan scenario's zonder de wiskunde te breken. De auteurs hebben zelfs een digitale "veiligheidsnet" gebouwd (met behulp van Lean 4) om ervoor te zorgen dat dit nieuwe fundament rotsvast is.

1. Probleemstelling

Het artikel behandelt een subtiel maar kritiek meetbaarheidsprobleem in het bewijs van de Fundamentele Stelling van Statistisch Leren (FTSL).

Context: Het standaardbewijs dat een eindige VC-dimensie PAC-learnability impliceert, vertrouwt op het symmetrisatie-argument (dubbel bemonsteren). Dit houdt in dat de kans op een "slechte gebeurtenis" wordt begrensd waarbij de "geest"-fout (op een tweede steekproef) de trainingsfout met een bepaalde marge overschrijdt.
Het Probleem: De slechte gebeurtenis wordt gedefinieerd door een existentiële kwantor over een conceptklasse $\mathcal{C}$ . Als $\mathcal{C}$ overaftelbaar is, is de unie van meetbare verzamelingen die deze gebeurtenis definiëren niet noodzakelijk Borel-meetbaar.
Huidige Stand: Recent werk (Krapp en Wirth) heeft de behoefte aan Borel-meetbaarheid van het supremum van de "geest-gap"-functie geformaliseerd om te waarborgen dat het bewijs wiskundig klopt.
Het Gat: De auteur betoogt dat het vereisen dat de slechte gebeurtenis Borel is, sterker is dan nodig. Het symmetrisatiebewijs vereist slechts dat de gebeurtenis meetbaar is ten opzichte van de voltooiing van het product-kansmaat (d.w.z. nul-meetbaar). Het artikel onderzoekt of deze zwakkere voorwaarde voldoende is en stabiel onder natuurlijke constructies van conceptklassen.

2. Methodologie

Het artikel maakt gebruik van instrumenten uit de Beschrijvende Steltheorie en Maattheorie, geformaliseerd binnen de Lean 4 bewijshulp.

Theoretisch Kader:
- Poolse Ruimten: Het domein $X$ wordt verondersteld een Poolse ruimte te zijn (separabel, volledig metriserbaar) met zijn Borel $\sigma$ -algebra.
- Borel-geparametriseerde Klassen: Conceptklassen worden gedefinieerd via een meetbare evaluatiemap $e: \Theta \times X \to \{0,1\}$ , waarbij $\Theta$ een standaard Borel-ruimte is.
- Beschrijvende Hiërarchie: De analyse volgt de complexiteit van de "slechte gebeurtenis" door de hiërarchie:
  1. Borel Getuige Verzameling: De verzameling parameters en steekproeven die aan de gap-voorwaarde voldoen, is Borel.
  2. Analytische Projectie: De slechte gebeurtenis is de projectie van de Borel getuige verzameling op de steekproefruimte. Volgens de Stelling van Suslin is deze projectie een Analytische Verzameling.
  3. Nul-meetbaarheid: Door Choquet-capaciteerbaarheid zijn analytische verzamelingen in Poolse ruimten universeel meetbaar (meetbaar in de voltooiing van elke eindige Borel-maat).
Formalisatie: Alle hoofdresultaten, inclusief de brug van analytische verzamelingen naar nul-meetbaarheid, zijn formeel geverifieerd in Lean 4. Dit dient niet alleen als controle, maar als een "forcerend middel" om ervoor te zorgen dat de regulariteitsvoorwaarden op het precies benodigde niveau worden gesteld (onderscheidend tussen MeasurableSet en NullMeasurableSet).

3. Belangrijkste Bijdragen

A. De Borel–Analytische Brug Stelling

Het artikel bewijst dat voor elke Borel-geparametriseerde conceptklasse met een meetbaar doel, de eenzijdige geest-gap slechte gebeurtenis Analytisch is.

Resultaat: Bijgevolg is de gebeurtenis nul-meetbaar (meetbaar in de voltooiing van het productmaat) voor elke eindige Borel-maat.
Implicatie: Dit stelt vast dat de Borel-meetbaarheid van de supremum-map (een voorwaarde vereist door Krapp en Wirth) niet noodzakelijk is voor het symmetrisatiebewijs om te gelden. De zwakkere NullMeasurableSet-voorwaarde volstaat.

B. Strikte Splitsing Getuige

De auteur construeert een specifiek tegenvoorbeeld om aan te tonen dat de kloof tussen "Borel" en "Nul-meetbaar" in deze context strikt is.

Constructie: Een conceptklasse $\mathcal{C}_A$ geparametriseerd door een Analytische maar niet-Borel verzameling $A \subseteq \mathbb{R}$ .
Resultaat: De slechte gebeurtenis voor deze klasse is Analytisch en nul-meetbaar, maar niet Borel.
Betekenis: Dit bewijst dat de Borel-voorwaarde (KW) strikt sterker is dan de noodzakelijke voorwaarde (WBmeas) voor de symmetrisatieroute.

C. Sluiting onder Constructoren

Het artikel demonstreert dat de eigenschap "Nul-meetbaar" te zijn (specifiek, het voldoen aan de WellBehavedVCMeasTarget interface) stabiel is onder natuurlijke operaties die worden gebruikt om complexe conceptklassen op te bouwen:

Patching: Klassen combineren op basis van een meetbare routingfunctie.
Interpolatie: Vaste-regio en aftelbare interpolatie van klassen.
Vezel-product Amalgamatie: Klassen samenvoegen op basis van een gemeenschappelijke parameterruimte.

Resultaat: Deze operaties behouden de zwakkere nul-meetbaarheidsvoorwaarde, zelfs als ze Borel-meetbaarheid zouden kunnen vernietigen.

D. Lean 4 Formalisatie

De resultaten zijn volledig geformaliseerd in Lean 4. De formalisatie omvat:

De Choquet-capaciteerbaarheidsroute van analytische verzamelingen naar nul-meetbaarheid.
De specifieke interface-definities (WellBehavedVC versus WellBehavedVCMeasTarget).
Verificatie dat het symmetrisatiebewijs werkt met de zwakkere interface.

4. Belangrijkste Resultaten

Stelling 3.1 (Borel–Analytische Brug): Voor Borel-geparametriseerde klassen is de slechte gebeurtenis Analytisch en bijgevolg universeel meetbaar (nul-meetbaar).
Stelling 4.1 (Strikte Splitsing): Er bestaat een conceptklasse waarbij de slechte gebeurtenis nul-meetbaar is maar niet Borel, wat bewijst dat de Borel-voorwaarde te sterk is.
Corollarium 6.1 (Verzwakte Interface): In het realiseerbare scenario (waar het doelconcept in de klasse zit en meetbaar is), vereist het standaard symmetrisatiebewijs van eindige VC-dimensie naar PAC-learnability slechts de Nul-meetbare voorwaarde, niet de Borel-supremumvoorwaarde.
Stabiliteit: De klasse van conceptklassen die voldoen aan de nul-meetbaarheidsvoorwaarde vormt een robuuste algebra die gesloten is onder patching, interpolatie en amalgamatie.

5. Betekenis en Impact

Verfijning van de Fundamentele Stelling: Het artikel verduidelijkt de exacte meetbaarheidshypothese die nodig is voor de implicatie VC-dimensie $\implies$ PAC-learnability. Het verwijdert een onnodige "Borel"-beperking, waardoor een bredere klasse van conceptklassen (die analytische maar niet-Borel slechte gebeurtenissen hebben) als leerbaar kan worden beschouwd onder standaardbewijzen.
Beschrijvende Steltheorie in ML: Het benadrukt de bruikbaarheid van beschrijvende steltheorie (Analytische verzamelingen, Stelling van Suslin, Choquet-capaciteit) bij het oplossen van fundamentele problemen in de theorie van statistisch leren, verder gaand dan eenvoudige combinatorische argumenten.
Formele Verificatie: Door deze resultaten te formaliseren in Lean 4, biedt het artikel een rigoureuze, machine-gecontroleerde basis voor leerteorie. Het demonstreert dat formele methoden subtiele onderscheidingen (zoals Borel versus Nul-meetbaar) kunnen blootleggen die vaak over het hoofd worden gezien in informele handboekbewijzen.
Praktische Implicaties: Hoewel de tegenvoorbeelden pathologische verzamelingen betreffen, suggereren de sluitingsresultaten dat veel natuurlijke constructies van conceptklassen (die per ongeluk niet-Borel slechte gebeurtenissen kunnen produceren) nog steeds geldig zijn voor PAC-leringsbewijzen, mits het doel meetbaar is.

Conclusie

Dhruv Gupta's artikel isoleert succesvol de exacte regulariteitsvoorwaarde die vereist is voor de symmetrisatiestap in VC-leren. Door te bewijzen dat nul-meetbaarheid (afgeleid van de analytische aard van de slechte gebeurtenis) voldoende is, verzwakt de auteur de hypothesen van de Fundamentele Stelling van Statistisch Leren. Dit werk overbrugt de kloof tussen klassieke empirische procestheorie en moderne formele verificatie, en biedt een nauwkeurigere en robuustere wiskundige basis voor leerteorie.