📊 statistics

An Optimal Agnostic PAC Algorithm

Dit artikel presenteert een agnostisch PAC-leeralgoritme voor binaire classificatie dat een statistisch optimale risicogrens bereikt, waarbij de steekproefcomplexiteit wordt vastgesteld tot aan universele constanten door overeen te komen met gevestigde ondergrenzen.

Oorspronkelijke auteurs: Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

Gepubliceerd 2026-08-07

📖 8 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

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 robot probeert te leren het verschil te zien tussen katten en honden. Je laat het de robot duizenden foto's zien, maar de wereld is rommelig: soms zit de kat verstopt in het donker, soms draagt de hond een hoed, en soms zijn de labels die je aan de robot geeft gewoon fout. Dit is de wereld van machine learning, specifiek een vakgebied genaamd statistische leertheorie. De grote vraag hier is: hoeveel voorbeelden moet een robot zien voordat hij goed wordt in het raden?

Om dit te beantwoorden, gebruiken wetenschappers een concept genaamd VC-dimensie (vernoemd naar Vapnik en Chervonenkis). Denk aan de VC-dimensie als een maatstaf voor hoe "verwarrend" of "complex" het brein van de robot is. Een simpel brein dat alleen naar de vorm van de oren kijkt, heeft een lage VC-dimensie; een supercomplex brein dat naar elke afzonderlijke pixel kijkt, heeft een hoge VC-dimensie. Het doel is om een "sweet spot" te vinden waar de robot snel genoeg leert om nuttig te zijn, maar niet zo complex is dat hij de trainingsfoto's uit het hoofd leert in plaats van de regels te begrijpen. Decennialang hebben wiskundigen geprobeerd de perfecte formule te vinden die precies vertelt hoeveel "extra" fout de robot zal maken vergeleken met de absoluut beste mogelijke robot, gegeven een bepaald aantal voorbeelden en een bepaald niveau van complexiteit.

Lama lang was er een gat in onze kennis. We wisten wat de beste mogelijke snelheid van leren was wanneer de data perfect was (geen fouten in de labels), en we wonden de snelheid wanneer de data erg rommelig was. Maar wat als de data zich in het midden bevindt? Wat als de data slechts een beetje ruis bevat? Eerdere pogingen om dit op te lossen waren als het proberen te hardlopen met een zware rugzak; ze kwamen dichtbij, maar ze droegen extra "logaritmisch" gewicht dat hen trager maakte dan nodig. De grote vraag was: Kunnen we een leerling bouwen die met de absoluut hoogste snelheid kan draaien, ongeacht hoeveel ruis er in de data zit, zonder dat hij dat extra gewicht meedraagt?

Dit artikel, getiteld "An Optimal Agnostic PAC Algorithm", beantwoordt die vraag met een luidruchtig "ja". De auteurs, Markus Engelund Mathiasen, Jian Qian en Nikita Zhivotovskiy, hebben een specifieke leeralgoritme geconstrueerd dat de statistisch optimale risicogrens bereikt. In gewone mensentaal betekent dit dat ze een manier hebben gevonden om een classifier te trainen die de minste fouten maakt, waarbij ze wiskundig hebben bewezen dat geen enkele andere methode hen kan verslaan (tot aan enkele universele constanten) voor elk vast niveau van ruis. Ze hebben niet alleen gegokt; ze hebben het bewezen.

Hier is hoe ze het deden, gebruikmakend van een verhaal over een zeer georganiseerde bibliotheek en een slim spel van "one-inclusion".

Het Probleen: De Ruisende Bibliotheek

Stel je een enorme bibliotheek voor waar elk boek een foto is, en elk boek een label op de rug heeft staan met "Kat" of "Hond". De bibliothecaris is echter een beetje onhandig. Soms labelt hij een boek verkeerd, of is het boek beschadigd. Je wilt een systeem bouwen dat naar een nieuw, ongelabeld boek kan kijken en het label correct kan raden.

Het "best mogelijke" systeem (laten we het de Oracle noemen) kent de ware regels van het universum. Zelf zal de Oracle ook fouten maken omdat de labels van de bibliothecaris soms fout zijn. Dit minimale foutpercentage wordt $L^*$ genoemd. Jouw doel is om een systeem te bouwen dat zo dicht mogelijk bij de prestaties van de Oracle komt, met behulp van een beperkt aantal boeken ( $n$ ) uit de bibliotheek.

Het artikel bewijst dat hun nieuwe systeem, laten we het De Optimizer noemen, een foutpercentage ( $L(\hat{h})$ ) zal hebben dat begrensd wordt door:
$L(\hat{h}) \le L^* + 7 \cdot 10^8 \left( \sqrt{\frac{L^*(d + \log(1/\delta))}{n}} + \frac{d + \log(1/\delta)}{n} \right)$
Laat de wiskunde je niet afschrikken. Het cruciale deel is de wortelterm. Deze formule zegt dat de extra fouten die je maakt (het "excess risk") krimpen naarmate je meer boeken ( $n$ ) krijgt, en het krimpt met de hoogst mogelijke snelheid die door de wetten van de waarschijnlijkheid wordt toegestaan. Eerdere methoden hadden extra factoren (zoals $\log(n)$ ) die hen vertraagden, maar De Optimizer laat deze weg.

Het Geheime Recept: De Kubus en de Oriëntatie

Hoe hebben ze het gedaan? Ze gebruikten een briljante combinatie van twee ideeën: De One-Inclusion Graph en Suffix Averaging.

1. De One-Inclusion Graph (Het Kubusspel)
Stel je alle mogelijke manieren voor waarop de boeken in je steekproef gelabeld zouden kunnen zijn. Als je $n$ boeken hebt, zijn er $2^n$ mogelijke labelcombinaties. Je kunt deze combinaties visualiseren als de hoekpunten van een enorme, meerdimensionale kubus (een "Boolean cube").

Twee hoekpunten zijn verbonden door een zijde als ze verschillen door precies één label van een boek.
De "Oracle" (de beste regel) leeft ergens in deze kubus.
Het doel is om te achterhalen in welke richting je moet wijzen wanneer je op een hoekpunt staat, zodat je dichter bij de Oracle komt.

De auteurs gebruiken een techniek genaamd oriëntatie. Stel je voor dat je op een hoekpunt van deze kubus staat. Je moet beslissen welke kant je op gaat. Het artikel introduceert een nieuw wiskundig instrument genaamd Lemma 2.1, wat een "class-dependent edge isoperimetric inequality" is. In onze bibliotheekanalogie is dit een regel die zegt: "Het aantal paden dat je moet controleren om de juiste richting te vinden, hangt af van hoe ver je van de Oracle bent en hoe complex de bibliotheek is."

Ze bewijzen dat je een richting kunt toekennen aan elke zijde in deze enorme kubus, zodanig dat je, ongeacht waar je begint, nooit meer dan een specifiek aantal stappen hoeft te zetten om dicht bij het beste antwoord te komen. Deze stap is cruciaal omdat het een rommelig gokspel verandelt in een deterministisch pad.

2. Suffix Averaging (De Stem van het Comité)
Zodra ze deze perfecte oriëntatie hebben, moeten ze deze omzetten in een echte voorspeller. Ze gebruiken een truc genaamd suffix averaging.
Stel je voor dat je een team van experts samenstelt. Je vraagt niet alleen één expert om een mening. In plaats daarvan vraag je een reeks experts die net iets verschillende hoeveelheden data hebben gezien.

Expert 1 heeft de eerste $k$ boeken gezien.
Expert 2 heeft de eerste $k+1$ boeken gezien.
...
Expert $m$ heeft de eerste $2k-1$ boeken gezien.

De uiteindelijke voorspelling is het gemiddelde van de meningen van al deze experts. Dit is krachtig omdat het de willekeur wegvlakt. Als één expert pech heeft met een boek met ruis, zullen de anderen dit compenseren. Het artikel bewijst dat dit gemiddelde proces, gecombineerd met hun perfecte kubusoriëntatie, het foutpercentage laag houdt, zelfs wanneer de data ruis bevat.

3. De Laatste Afwerking: Thresholding
Het gemiddelde resultaat is een getal tussen -1 en 1 (een "score"). Om tot een definitief "Kat" of "Hond" antwoord te komen, gebruiken ze een threshold (drempelwaarde). Ze testen een paar verschillende afkappunten op een aparte set validatieboeken om degene te kiezen die het beste werkt. Deze stap zorgt ervoor dat het eindresultaat een eenvoudige, deterministische regel is (een binaire classifier) in plaats van een vage waarschijnlijkheid.

Waarom dit ertoe doet

Vóór dit artikel moest je, als je de snelst mogelijke leersnelheid wilde, kiezen tussen methoden die goed werkten voor perfecte data en methoden die goed werkten voor rommelige data. Je kon niet het beste van beide werelden hebben zonder een prijs te betalen.

Dit artikel laat zien dat je wel het beste van beide werelden kunt hebben. Ze hebben een leerling geconstrueerd die:

Geen kennis nodig heeft van het ruisniveau: Het werkt zonder te weten hoe rommelig de data is ( $L^*$ ) of hoe zeker je wilt zijn ( $\delta$ ).
Optimaal is: Het komt overeen met de theoretische ondergrens (de snelheidslimiet van leren) die is vastgesteld door eerdere onderzoekers zoals Devroye, Györfi en Lugosi.
Deterministisch is: Het vertrouwt niet op geluk; het geeft elke keer hetzelfde antwoord als je het op dezelfde data draait.

De auteurs sluiten expliciet de mogelijkheid uit dat we "polylogaritmische" factoren (die extra vertragingen) nodig hebben om optimale resultaten te behalen in de agnostische (ruisende) setting. Ze bewijzen dat die factoren onnodig zijn. Ze laten ook zien dat hoewel sommige eerdere methoden (zoals eenvoudige meerderheidsstemmen) goed werken voor perfecte data, ze niet in staat zijn om de optimale snelheid te behouden wanneer er ruis wordt geïntroduceerd.

Kortom, dit artikel sluit een langlopend hoofdstuk in de geschiedenis van de machine learning-theorie. Het biedt het "perfecte" algoritme voor binaire classificatie in de echte wereld, waar data nooit perfect is. Het is een beetje als het vinden van een kaart die garandeert dat je de schat kunt bereiken in het minimale aantal stappen, ongeacht hoeveel kuilen er op de weg zitten. De auteurs suggereerden niet alleen dat dit mogelijk was; ze bouwden de kaart en bewezen dat deze werkt.

TECHNISCHE SAMENVATTING: Een Optimaal Agnostisch PAC-algoritme

Probleemstelling
Het artikel behandelt het fundamentele probleem van het bepalen van scherpe risicobovengrenzen in agnostisch Probably Approximately Correct (PAC) leren voor binaire classificatie. Laat $H \subseteq \{-1, +1\}^{\mathcal{X}}$ een hypotheseklasse zijn met VC-dimensie $d \geq 1$ . Gegeven een i.i.d. steekproef $S$ van omvang $n$ uit een distributie over $\mathcal{X} \times \{-1, +1\}$ , is het doel om een leerder te construeren die een classifier $\hat{h}$ uitvoert zodanig dat het risico $L(\hat{h})$ dicht bij het optimale risico $L^* = \min_{h \in H} L(h)$ ligt.

Historisch gezien zijn grenzen in deze setting afgeleid via twee afzonderlijke regimes:

Realiseerbaar geval ( $L^*=0$ ): Optimale snelheden van $O(d/n)$ worden bereikt met behulp van combinatorische argumenten zoals de one-inclusion graph (Haussler, Littlestone, Warmuth) of specifieke aggregatieschema's.
Agnostisch geval ( $L^* > 0$ ): Klassieke empirische procesmethoden (chaining, covering) leveren optimale snelheden van $O(\sqrt{d/n})$ op wanneer $L^*$ ver van nul afwijkt.

De openstaande vraag, vastgesteld door ondergrenzen van Devroye, Györfi en Lugosi, is of een enkel algoritme een optimale snelheid kan bereiken over het gehele spectrum van $L^*$ , specifiek overeenkomend met de grens:
$L(\hat{h}) \leq L^* + C \left( \sqrt{\frac{L^*(d + \log(1/\delta))}{n}} + \frac{d + \log(1/\delta)}{n} \right)$
Eerdere bovengrenzen incorporeerden ofwel suboptimale polylogaritmische factoren in de snelle term, of vereisten specifieke condities op $L^*$ (bijv. $L^* \lesssim (d+\log(1/\delta))/n$ ) om optimaliteit te bereiken.

Methodologie
De auteurs construeren een deterministische, over het algemeen imperfecte leerder die de optimale bovengrens bereikt zonder voorafgaande kennis van $L^*$ of de betrouwbaarheidsparameter $\delta$ . De methodologie verloopt in drie hoofdfasen:

Klasse-afhankelijke Rand-isoperimetrie (Sectie 2):
De kern van de theoretische innovatie is Lemma 2.1, een klasse-afhankelijke rand-isoperimetrische ongelijkheid op de Booleaanse kubus. In tegen tegenstelling tot eerdere resultaten die randaantallen uitsluitend begrenzen door de VC-dimensie of de afstand tot een trace, introduceert dit lemma gewichten $w_{v,p}$ die tegelijkertijd voldoen aan:
- $w_{v,p} + w_{v \oplus p, p} = 1$ (verdeling van randen).
- $\sum_{p \in D} w_{v,p} \leq \rho_F(v) + R_D(F)$ , waarbij $\rho_F(v)$ de Hamming-afstand is tot een trace $F$ en $R_D(F)$ de ongenormaliseerde Rademacher-breedte is van de projectie van $F$ op coördinaten $D$ .
Deze ongelijkheid maakt een gelokaliseerde grens mogelijk op het aantal geïnduceerde randen $|E_U|$ in een subgraaf, waarbij deze worden gecontroleerd via zowel de afstand tot de optimale trace als de complexiteit van de projectie.
Optimale Leave-One-Out Oriëntatie (Sectie 2):
Met behulp van Hall's Huwelijksstelling converteren de auteurs de isoperimetrische ongelijkheid naar een deterministische oriëntatie $\sigma$ van de volledige Booleaanse kubus. Deze oriëntatie zorgt ervoor dat voor elke vertex $v$ , de uitgraad wordt begrensd door:
$\text{out}(v; \sigma) \leq \rho_F(v) + 120\sqrt{d \rho_F(v)} + 7202d$
Dit leidt tot een leave-one-out regel waarbij de verwachte fout wordt begrensd door het optimale empirische risico plus een term die schaalt met $\sqrt{d L^*/n}$ en $d/n$ .
Van Leave-One-Out naar PAC-grenzen (Sectie 3):
Om de leave-one-out regel om te zetten in een hoog-waarschijnlijkheid PAC-garantie, maken de auteurs gebruik van een tweestaps derandomisering en middelingproces:
- Symmetrisatie en Suffix-middeling: De deterministische leave-one-out regel wordt gesymmetriseerd over permutaties. Een gerandomiseerde voorspeller $\hat{p}$ wordt geconstrueerd door deze gesymmetriseerde scores te middelen over een suffix van de steekproef (indices $k$ tot $2k-1$ ). Deze stap maakt gebruik van reverse en forward martingale-argumenten (Lemma's 3.1 en 3.2), aangepast van Aden-Ali et al., om de variantie en afwijking van het excessieve risico te controleren, waardoor de grens uniform geldt voor $L^*$ .
- Drempelwaarde en ERM: De gerandomiseerde voorspeller $\hat{p}$ (die waarden in $[-1, 1]$ aanneemt) wordt omgezet in een deterministische binaire classifier. Dit gebeurt door een klasse van drempelwaarde-hypothesen $T_{\hat{p}} = \{ x \mapsto 2\mathbb{1}[\hat{p}(x) \geq u] - 1 \}$ te overwegen. Een empirische risicominimizer (ERM) wordt geselecteerd uit deze klasse met behulp van een onafhankelijke validatiesteekproef. Cruciaal is dat de geneste structuur van de drempelwaarde-klasse een lokale entropie-grens mogelijk maakt zonder een extra logaritmische factor in de steekproefomvang te introduceren, waardoor de optimale coëfficiënt op $L^*$ behouden blijft.

Belangrijkste Bijdragen en Resultaten
Het artikel bewijst Theorem 1, waarmee wordt vastgesteld dat er een deterministische leerder bestaat die, voor elke distributie, steekproefomvang $n$ en betrouwbaarheid $\delta$ , een classifier $\hat{h}$ uitvoert die voldoet aan:
$L(\hat{h}) \leq L^* + 2 \cdot 10^8 \left( \sqrt{\frac{L^*(d + \log(48/\delta))}{n}} + \frac{d + \log(48/\delta)}{n} \right)$
met een waarschijnlijkheid van ten minste $1-\delta$ . De uiteindelijke afleiding in het bewijs van Theorem 1 levert een strakkere constante op van ongeveer $3.1 \cdot 10^7$ .

Optimaliteit: Deze grens komt overeen met de ondergrenzen van Devroye, Györfi en Lugosi tot aan universele constanten. Het is het eerste resultaat dat de optimale snelheid voor elke vaste $L^*$ bereikt, waardoor de kloof tussen het realiseerbare en het volledig agnostische regime wordt overbrugd zonder suboptimale polylogaritmische factoren.
Algoritmische Eigenschappen: De leerder is deterministisch, over het algemeen imperfect (geeft een classifier uit die niet noodzakelijkerwijs in $H$ zit) en vereist geen kennis van $L^*$ of $\delta$ .
Technische Vernieuwing: Het bewijs rust op de nieuwe klasse-afhankelijke rand-isoperimetrische ongelijkheid (Lemma 2.1), die het aantal geïnduceerde randen controleert via een combinatie van benaderingsfouten en geprojecteerde Rademacher-breedtes, een techniek die verschilt van eerdere combinatorische of zuivere empirische procesbenaderingen.

Betekenis
Het artikel beweert de steekproefcomplexiteit van agnostisch PAC-leren te hebben beslecht tot universele constanten. Door een algoritme te construeren dat de minimax excessieve risico-grens voor binaire classificatie bereikt voor elke vaste $L^*$ , lossen de auteurs een langdurig openstaand vraagstuk op over het bestaan van een enkel algoritme dat optimaal is over het gehele spectrum van ruisniveaus. Het werk toont aan dat de optimale snelheid bereikbaar is zonder de leidende coëfficiënt van de $L^*$ -term op te offeren, een prestatie die voorheen moeilijk geacht werd vanwege de spanning tussen de analyse van de realiseerbare en de agnostische regimes.

Het Probleen: De Ruisende Bibliotheek

Het Geheime Recept: De Kubus en de Oriëntatie

Waarom dit ertoe doet

TECHNISCHE SAMENVATTING: Een Optimaal Agnostisch PAC-algoritme

Meer zoals dit