Shatteren & VC-dimensie

Wanneer hypotheseruimten oneindig worden

De bound m ≥ (1/ε)(ln|H| + ln(1/δ)) breekt wanneer |H| = ∞. De meeste nuttige hypotheseklassen (lineaire classifier in ℝᵈ, decision trees, neurale netwerken) bevatten oneindig veel kandidaten. Vapnik & Chervonenkis losten dit rond 1971 op met een rijkere complexiteitsmaat: VC-dimensie.

Shatteren

Een hypotheseklasse H shattert een verzameling van n punten als H elk mogelijk labelen van die n punten kan produceren (alle 2ⁿ dichotomieën). Lineaire classifier in ℝ² shattert elke 3 punten in algemene positie: voor elk van de 8 mogelijke +/−-labelingen van die 3 punten, scheidt een of andere lijn ze correct.

Maar lineaire classifiers in ℝ² kunnen 4 punten in een XOR-configuratie niet shatteren. Geen rechte lijn scheidt het diagonaal paar van het antidiagonaal paar.

VC-dimensie

VC(H) = de grootste n zodanig dat H een willekeurige n-puntenverzameling shattert. Voor 2D lineaire classifiers: VC = 3. Voor as-uitgelijnde rechthoeken in 2D: VC = 4. Voor neurale netwerken met W gewichten: VC ≤ O(W² log W) (Bartlett & Anthony 1999).

Sample-complexiteit met VC-dimensie

Vervang ln|H| in onze PAC-bound door VC-dimensie d:

m = O((d/ε) log(1/ε) + (1/ε) log(1/δ))

VC-dimensie fungeert als onze 'effectieve complexiteit' van een oneindige klasse. Een hypotheseklasse met lage VC-dimensie generaliseert vanuit weinig voorbeelden; een klasse met hoge VC-dimensie vereist meer data.

VC-dimensie als effectief hypothese-aantal

Een neuraal netwerk heeft W = 10⁹ gewichten. Volgens de Bartlett-Anthony-bound geldt VC ≤ O(W² log W). Benader VC ≈ W² log₂ W.

Realiseerbaarheid laten vallen, Posterioren over Hypothesen

Twee Belangrijke Generalisaties

Klassieke PAC gaat ervan uit dat ons doelconcept c zich binnen onze hypotheseklasse H bevindt. Echte data bevat ruis, verkeerde labels en concepten die onze klasse niet kan representeren. Twee uitbreidingen pakken dit aan.

Agnostic PAC

Laat onze aanname varen dat c ∈ H. We concurreren nu met onze best-in-class hypothese h* = argmin_{h ∈ H} risk(h). De vorm van de bound verandert: in plaats van dicht bij perfect te komen, komen we dicht bij het best-mogelijke binnen H.

Agnostische bound: P[risk(h) ≤ risk(h*) + ε] ≥ 1 − δ met sample complexity m = O(1/ε² × (VC(H) + log(1/δ))). Let op ε² in plaats van ε in de noemer: agnostisch leren vereist meer samples voor dezelfde precisie.

PAC-Bayes (McAllester 1999)

We gaan van het kiezen van één hypothese naar het kiezen van een verdeling over hypotheses. Begin met een prior P. Observeer data. Leid de posterior Q af. PAC-Bayes bounds de verwachte risk onder Q:

𝔼_{h~Q}[risk(h)] ≤ 𝔼_{h~Q}[empirical_risk(h)] + √[(KL(Q‖P) + ln(2√n/δ)) / 2n]

KL(Q‖P) meet hoe ver onze posterior zich heeft verwijderd van onze prior. Twee interpretaties:

1. Compressie-view. Een posterior die dicht bij zijn prior ligt (kleine KL) generaliseert goed — kleine informatiekost = kleine generalisatiekloof.

2. Bayesiaanse view. Sterke prior + zwakke data-update = strakke bound; zwakke prior + zware data-update = lossere bound.

Waarom PAC-Bayes belangrijk is. Empirische PAC-Bayes-bounds (Catoni 2007, Dziugaite & Roy 2017) geven numeriek betekenisvolle generalisatiegaranties voor echte neurale netwerken waar klassieke PAC-bounds vacueus zijn. Ze blijven onze strakste theoretische greep op generalisatie bij overparameteriseerde modellen.

Reading a PAC-Bayes Bound

Stel dat we een netwerk trainen op n = 50.000 gelabelde voorbeelden. Na training heeft onze posterior Q over de gewichten KL(Q‖P) = 200 nats ten opzichte van een Gaussische prior P. Het empirische risico onder Q bedraagt 0,10. Stel δ = 0,05.

Overparameterisatie & dubbele afdaling

Klassieke PAC voorspelt een ramp

Klassieke PAC voorspelt: meer parameters dan samples = catastrofale overfitting. Perfect leren op trainingsdata, willekeurig generaliseren op testdata. VC-bound voorspelt memorisatie zonder leren.

Moderne neurale netwerken hebben routinematig 10× tot 1000× meer parameters dan trainingsvoorbeelden en generaliseren toch. Dit zou volgens de klassieke theorie niet mogen gebeuren. Het gebeurt toch.

De U-curve die ons werd geleerd

Klassieke bias-variance: naarmate de modelcapaciteit groeit, daalt de trainingsfout monotoon; de testfout daalt eerst (minder underfit), bereikt een minimum en stijgt daarna (overfit). U-vorm voorspeld door VC-theorie.

Wat er werkelijk gebeurt — Double Descent

Belkin et al (2019) toonden aan dat de testfout de klassieke U-curve volgt tot aan de interpolatiedrempel (capaciteit = #samples), en daarna opnieuw daalt voorbij die drempel. Sterk overparameteriseerde modellen generaliseren beter dan net-groot-genoeg modellen.

Waarom klassieke PAC dit mist

1. Distribution-free aanname is te pessimistisch. Echte data heeft structuur (lage intrinsieke dimensie, manifold-geometrie). PAC-bounds gelden voor worst-case distributies; echte distributies benutten structuur die SGD ook benut.

2. Impliciete regularisatie. SGD op overparameteriseerde netwerken vindt interpolerende oplossingen met minimale norm of minimale complexiteit, niet willekeurige oplossingen. Klassieke theorie gaat uit van de worst-case empirical risk minimizer; echte algoritmen kiezen goedaardige oplossingen.

3. Definitie van de hypotheseklasse is onjuist. De effectieve hypotheseklasse die door SGD wordt verkend is veel kleiner dan de nominale gewichtruimte. PAC-Bayes posterior-verdelingen vangen dit; VC-dimensie niet.

Modern theoretisch werk (Bartlett, Long, Lugosi, Tsigler 2020 over benign overfitting; Nakkiran et al 2020 over double descent) bouwt aan een post-PAC generalisatietheorie die rekening houdt met ons overparameteriseerde regime.

Diagnose van een falen van klassieke PAC

Een onderzoeksteam traint een netwerk met 1 miljard parameters op 100.000 gelabelde voorbeelden. Klassieke PAC voorspelt vacueuze bounds. Empirisch bereikt de testnauwkeurigheid 95%.

Kaplan, Chinchilla, & Het Dimensioneren van Automated General Intelligence

Van Bounds naar Empirische Schaalwetten

Klassieke PAC voorspelt datasetgrootte theoretisch en levert nietszeggende resultaten. Empirische schaalwetten voorspellen datasetgrootte vanuit observatie en werken daadwerkelijk. Ze hebben PAC vervangen als ons praktische hulpmiddel voor het bepalen van de grootte van grote modellen.

Kaplan et al (2020)

Loss volgt een machtswet in parameters N, dataset-tokens D en compute C:

L(N) ≈ (Nc/N)^αN L(D) ≈ (Dc/D)^αD L(C) ≈ (Cc/C)^αC

Het verdubbelen van parameters verlaagt de loss met een vaste multiplicatieve factor. Het verdubbelen van data verlaagt de loss met een andere vaste factor. Deze exponenten (αN, αD, αC) meten en voorspellen frontier-gedrag over vele ordes van grootte.

Hoffmann et al 2022 (Chinchilla)

Chinchilla toonde aan dat de exponenten van Kaplan parameters relatief zwaarder wogen dan data. Compute-optimal trainen vereist ongeveer 20 tokens per parameter:

D_opt ≈ 20 × N

GPT-3 (175B parameters) werd getraind op ~300B tokens — sterk onder-getraind volgens de Chinchilla-berekening. Een compute-optimaal model met 175B parameters heeft ~3,5 biljoen tokens nodig.

De Data Wall

Het schalen van ons aantal parameters vereist dat we het aantal tokens proportioneel schalen. Een publieke webcrawl levert ~10¹³ bruikbare tokens op. Een hypothetische geautomatiseerde algemene intelligentie met 10¹⁵ parameters zou ~2×10¹⁶ tokens nodig hebben — drie ordes van grootte meer dan de beschikbare webdata.

Dit is onze data wall. Schaalwetten voorspellen dat we een tekort aan corpus tegenkomen lang voordat we een tekort aan rekenkracht hebben. Synthetische data, multimodale corpora (video, audio, sensorstromen) en RL-from-environment zijn allemaal gericht op het doorbreken van deze muur.

Klassieke PAC vertelde ons (onjuist) dat we 10²¹ samples nodig hadden. Schaalwetten vertellen ons (gekalibreerd aan de realiteit) dat we 2×10¹⁶ nodig hebben. Beide aantallen overschrijden de beschikbare tekst. Frontierwerk vandaag richt zich op het dichten van dat gat.

Een corpus voor geautomatiseerde algemene intelligentie schatten

Stel dat een frontierlab een model met 10¹⁴ parameters voorstelt en beweert dat het geautomatiseerde algemene intelligentie zal bereiken. We willen de omvang van de trainingscorpus bepalen volgens Chinchilla’s regel.

Van theoretische grenzen naar productie-metingen

Stop met het berekenen van grenzen; begin ze te meten

Klassieke PAC-bounds zijn vacuous. PAC-Bayes-bounds zijn strak onder aannames die moeilijk te verifiëren zijn. Een praktisch alternatief: meet ε empirisch op je echte distributie en update deze terwijl je systeem draait.

Idee 1 — Dekking empirisch maken als PAC

Een make coverage-doel draait N hold-out-vragen door je query-systeem en meet twee percentages:

- cache_hit_rate — fractie waarbij je systeem een bekend antwoord vond

- i_dont_know_rate — fractie waarbij je systeem eerlijk uitstelde

Elke meting = een Bernoulli-trial. Uit de waargenomen tellingen bereken je een Wilson-betrouwbaarheidsinterval voor de ware rate. Voorbeeld: N = 1000 queries, waargenomen i_dont_know_rate = 0.20 → 95% CI ≈ [0.177, 0.226]. De bovengrens 0.226 fungeert exact als een PAC ε bij δ = 0.05, afgeleid uit echte data op de echte verdeling in plaats van een worst-case theoretische analyse.

De klassieke PAC-terminologie is van toepassing (ε, δ, betrouwbaarheid). Andere wiskundige onderbouwing (binomiale concentratie versus VC-theorie). Strakker resultaat omdat echte verdelingen exploiteerbare structuur bevatten.

Idee 2 — PAC-Bayes-audit via falsificatie-events

Behandel elke falsificatie (systeemantwoord dat aantoonbaar fout is) als bewijs dat de posterior over de ware foutmarge ε bijwerkt:

1. Prior: ε ~ Beta(α₀, β₀). Kies een zwakke prior, bijv. Beta(1, 1) = uniform.

2. Elke query levert een Bernoulli-uitkomst op: vervalst (1) of behouden (0).

3. Posterior na k vervalsingen in n queries: Beta(α₀ + k, β₀ + n − k).

4. Posterior gemiddelde: (α₀ + k) / (α₀ + β₀ + n) → empirische vervalsingsratio als n → ∞.

5. 95% credible interval rond ε wordt nauwer als 1/√n.

Wat Dit Ons Oplevert

- Schatting van ε₀ uit de echte wereld op basis van daadwerkelijke inzet, niet op basis van worst-case theorie

- Anytime-geldig alarm: wanneer het posterieure geloofwaardigheidsinterval de contractdrempel overschrijdt, iemand pagineren

- Monotone betrouwbaarheid: meer waargenomen queries → smaller CI → sterkere garantie

Verwante technieken: conforme predictie met online herkalibratie (Vovk), sequentiële waarschijnlijkheidsratio-toetsen (Wald), online PAC-Bayes (Haddouche & Guedj 2022). Zelfde familie, verschillende wiskundige machinerie.

Een Beta-posterior berekenen op falsificaties

Ons team voert een dekkingsaudit uit op een productie-query-systeem. Prior op de ware foutmarge ε: Beta(1, 1) (uniform). Na 200 out-of-sample queries observeerden we 8 falsificaties.