Shattering & VC-Dimension

Wenn Hypothesenräume unendlich werden

Die Schranke m ≥ (1/ε)(ln|H| + ln(1/δ)) versagt, wenn |H| = ∞. Die meisten nützlichen Hypothesenklassen (lineare Klassifikatoren in ℝᵈ, Entscheidungsbäume, neuronale Netze) enthalten unendlich viele Kandidaten. Vapnik & Chervonenkis lösten dies um 1971 mit einem reichhaltigeren Komplexitätsmaß: VC-Dimension.

Shattering

Eine Hypothesenklasse H zertrümmert eine Menge von n Punkten, wenn H jede mögliche Beschriftung dieser n Punkte erzeugen kann (alle 2ⁿ Dichotomien). Lineare Klassifikatoren in ℝ² zertrümmern beliebige 3 Punkte in allgemeiner Lage: Für jede der 8 möglichen +/−-Beschriftungen dieser 3 Punkte existiert eine Linie, die sie korrekt trennt.

Aber lineare Klassifikatoren in ℝ² können 4 Punkte in XOR-Anordnung nicht zertrümmern. Keine Gerade trennt das diagonale Paar vom antidiagonalen Paar.

VC-Dimension

VC(H) = die größte n, für die H eine n-Punkt-Menge zertrümmert. Für lineare Klassifikatoren in 2D: VC = 3. Für achsenparallele Rechtecke in 2D: VC = 4. Für neuronale Netze mit W Gewichten: VC ≤ O(W² log W) (Bartlett & Anthony 1999).

Stichprobenkomplexität mit VC-Dimension

Ersetze ln|H| in unserer PAC-Schranke durch die VC-Dimension d:

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

Die VC-Dimension dient als unsere „effektive Komplexität“ einer unendlichen Klasse. Eine Hypothesenklasse mit niedriger VC-Dimension generalisiert aus wenigen Beispielen; eine Klasse mit hoher VC-Dimension benötigt deutlich mehr Daten.

VC-Dimension als effektive Hypothesenanzahl

Ein neuronales Netz hat W = 10⁹ Gewichte. Nach der Bartlett-Anthony-Schranke gilt VC ≤ O(W² log W). Wir approximieren VC ≈ W² log₂ W.

Realisierbarkeit fallen lassen, Posterioren über Hypothesen

Zwei wichtige Verallgemeinerungen

Klassisches PAC nimmt an, dass unser Zielkonzept c innerhalb unserer Hypothesenklasse H liegt. Reale Daten enthalten Rauschen, Fehlbeschriftungen und Konzepte, die unsere Klasse nicht darstellen kann. Zwei Erweiterungen behandeln dies.

Agnostic PAC

Lassen wir unsere Annahme fallen, dass c ∈ H gilt. Jetzt konkurrieren wir gegen unsere best-in-class-Hypothese h* = argmin_{h ∈ H} risk(h). Die Form der Schranke ändert sich: statt sich der perfekten Hypothese anzunähern, nähern wir uns der bestmöglichen Hypothese innerhalb von H an.

Agnostische Schranke: P[risk(h) ≤ risk(h*) + ε] ≥ 1 − δ mit Stichprobenkomplexität m = O(1/ε² × (VC(H) + log(1/δ))). Beachte ε² statt ε im Nenner: Agnostisches Lernen benötigt mehr Beispiele für dieselbe Genauigkeit.

PAC-Bayes (McAllester 1999)

Wir wechseln von der Auswahl einer einzelnen Hypothese zur Auswahl einer Verteilung über Hypothesen. Beginnen wir mit dem Prior P. Beobachten wir Daten. Leiten wir den Posterior Q ab. PAC-Bayes-Schranken geben eine obere Schranke für das erwartete Risiko unter Q:

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

KL(Q‖P) misst, wie weit sich unsere Posterior-Verteilung von unserer Prior-Verteilung entfernt hat. Zwei Interpretationen:

1. Kompressionssicht. Eine Posterior-Verteilung, die nah an ihrer Prior-Verteilung liegt (kleines KL), generalisiert gut — geringe Informationskosten = geringe Generalisierungslücke.

2. Bayessche Sicht. Starker Prior + schwache Datenaktualisierung = enge Schranke; schwacher Prior + starke Datenaktualisierung = lockerere Schranke.

Warum PAC-Bayes wichtig ist. Empirische PAC-Bayes-Schranken (Catoni 2007, Dziugaite & Roy 2017) liefern numerisch aussagekräftige Generalisierungsgarantien für reale neuronale Netze, bei denen klassische PAC-Schranken leerlaufen. Sie bleiben unser engstes theoretisches Werkzeug für die Generalisierung überparametrisierter Modelle.

Reading a PAC-Bayes Bound

Angenommen, wir trainieren ein Netzwerk auf n = 50.000 gelabelten Beispielen. Nach dem Training hat unsere Posterior Q über die Gewichte KL(Q‖P) = 200 Nats relativ zu einem Gaußschen Prior P. Das empirische Risiko unter Q beträgt 0,10. Setze δ = 0,05.

Überparametrisierung & Double Descent

Klassisches PAC sagt Katastrophe voraus

Klassisches PAC sagt voraus: mehr Parameter als Stichproben = katastrophales Overfitting. Perfektes Lernen auf Trainingsdaten, zufällige Generalisierung auf Testdaten. VC-Bound sagt Memorierung ohne Lernen voraus.

Moderne neuronale Netze haben routinemäßig 10× bis 1000× mehr Parameter als Trainingsbeispiele und generalisieren trotzdem. Das dürfte nach klassischer Theorie nicht passieren. Es passiert trotzdem.

Die U-Kurve, die wir gelernt haben

Klassischer Bias-Varianz-Konflikt: Mit steigender Modellkapazität sinkt der Trainingsfehler monoton; der Testfehler fällt zunächst (weniger Underfitting), erreicht ein Minimum und steigt dann wieder (Overfitting). Die U-Form wird durch die VC-Theorie vorhergesagt.

Was tatsächlich passiert — Double Descent

Belkin et al. (2019) zeigten, dass der Testfehler der klassischen U-Kurve bis zum Interpolationsschwellwert (Kapazität = Anzahl der Samples) folgt und danach erneut Abfällt. Stark überparametrisierte Modelle generalisieren besser als gerade ausreichend große Modelle.

Warum klassische PAC-Bounds dies nicht erfassen

1. Die verteilungsfreie Annahme ist zu pessimistisch. Reale Daten besitzen Struktur (niedrige intrinsische Dimension, Mannigfaltigkeitsgeometrie). PAC-Schranken gelten für Worst-Case-Verteilungen; reale Verteilungen nutzen Strukturen, die auch SGD ausnutzt.

2. Implizite Regularisierung. SGD auf überparametrisierten Netzen findet interpolierende Lösungen mit minimaler Norm oder minimaler Komplexität, nicht beliebige. Die klassische Theorie geht vom worst-case Empirical-Risk-Minimizer aus; reale Algorithmen wählen gutartige Lösungen.

3. Falsche Definition der Hypothesenklasse. Die effektive Hypothesenklasse, die SGD tatsächlich durchläuft, ist deutlich kleiner als der nominale Gewichtsraum. PAC-Bayes-Posteriori-Verteilungen erfassen dies; die VC-Dimension nicht.

Aktuelle theoretische Arbeiten (Bartlett, Long, Lugosi, Tsigler 2020 zu benign overfitting; Nakkiran et al. 2020 zu Double Descent) entwickeln eine post-PAC-Generalisierungstheorie, die unser überparametrisiertes Regime berücksichtigt.

Diagnose eines Versagens klassischer PAC

Ein Forschungsteam trainiert ein Netzwerk mit 1 Milliarde Parametern auf 100.000 gelabelten Beispielen. Klassische PAC-Theorie liefert vacuous bounds. Empirisch erreicht die Testgenauigkeit 95 %.

Kaplan, Chinchilla & die Dimensionierung automatisierter allgemeiner Intelligenz

Von Grenzen zu empirischen Skalierungsgesetzen

Klassisches PAC sagt die Datensatzgröße theoretisch vorher und liefert leere Ergebnisse. Empirische Skalierungsgesetze sagen die Datensatzgröße aus Beobachtungen vorher und funktionieren tatsächlich. Sie haben PAC als praktisches Dimensionierungswerkzeug für große Modelle abgelöst.

Kaplan et al (2020)

Der Verlust folgt einem Potenzgesetz in den Parametern N, den Datensatz-Tokens D und dem Rechenaufwand C:

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

Eine Verdopplung der Parameter reduziert den Verlust um einen festen multiplikativen Faktor. Eine Verdopplung der Daten reduziert den Verlust um einen weiteren festen Faktor. Diese Exponenten (αN, αD, αC) messen und prognostizieren das Verhalten an der Frontier über viele Größenordnungen hinweg.

Hoffmann et al. 2022 (Chinchilla)

Chinchilla zeigte, dass Kaplans Exponenten Parameter gegenüber Daten übergewichtet haben. Compute-optimales Training erfordert etwa 20 Tokens pro Parameter:

D_opt ≈ 20 × N

GPT-3 (175B Parameter) wurde mit ~300B Tokens trainiert — nach Chinchilla-Mathematik stark untertrainiert. Ein compute-optimales 175B-Parameter-Modell benötigt ~3,5 Billionen Tokens.

Die Datenwand

Die Skalierung unserer Parameteranzahl erfordert eine proportionale Skalierung unserer Token-Anzahl. Ein öffentlicher Web-Crawl liefert etwa 10¹³ nützliche Token. Eine hypothetische automatisierte allgemeine Intelligenz mit 10¹⁵ Parametern würde etwa 2×10¹⁶ Token benötigen — drei Größenordnungen mehr als die verfügbaren Web-Daten.

Das ist unsere Datenwand. Skalierungsgesetze sagen vorher, dass wir auf einen Korpus-Mangel stoßen, lange bevor wir auf einen Rechenmangel stoßen. Synthetische Daten, multimodale Korpora (Video, Audio, Sensordatenströme) und RL aus der Umgebung zielen alle darauf ab, diese Wand zu überwinden.

Die klassische PAC-Theorie sagte uns (fälschlicherweise), dass wir 10²¹ Beispiele benötigen. Skalierungsgesetze sagen uns (an der Realität kalibriert), dass wir 2×10¹⁶ benötigen. Beide Zahlen übersteigen den verfügbaren Text. Die aktuelle Frontier-Forschung beschäftigt sich damit, diese Lücke zu schließen.

Schätzung eines Korpus für automatisierte allgemeine Intelligenz

Angenommen, ein Frontier-Labor schlägt ein Modell mit 10¹⁴ Parametern vor und behauptet, es werde automatisierte allgemeine Intelligenz erreichen. Wir wollen die Größe seines Trainingskorpus nach der Chinchilla-Regel bestimmen.

Von theoretischen Schranken zu Produktionsmessungen

Aufhören, Schranken zu berechnen; anfangen, sie zu messen

Klassische PAC-Schranken sind leer. PAC-Bayes-Schranken sind unter schwer verifizierbaren Annahmen eng. Eine praktische Alternative: ε empirisch auf der realen Verteilung messen und während des Betriebs aktualisieren.

Idee 1 — Coverage als Empirical PAC definieren

Ein make coverage-Target führt N zurückgehaltene Fragen durch Ihr Abfragesystem und misst zwei Raten:

- cache_hit_rate — Anteil der Fälle, in denen Ihr System eine bekannte Antwort gefunden hat

- i_dont_know_rate — Anteil der Fälle, in denen Ihr System ehrlich verzichtet hat

Jede Messung = ein Bernoulli-Versuch. Aus den beobachteten Zählungen wird ein Wilson-Konfidenzintervall für die wahre Rate berechnet. Beispiel: N = 1000 Queries, beobachtete i_dont_know_rate = 0.20 → 95 % CI ≈ [0.177, 0.226]. Die obere Grenze 0.226 entspricht exakt einem PAC-ε bei δ = 0.05, abgeleitet aus realen Daten der realen Verteilung statt aus einer worst-case-theoretischen Analyse.

Die klassische PAC-Terminologie gilt (ε, δ, Konfidenz). Andere mathematische Grundlage (Binomial-Konzentration vs. VC-Theorie). Strengeres Ergebnis, da reale Verteilungen ausnutzbare Struktur besitzen.

Idee 2 — PAC-Bayes-Audit über Falsifikationsereignisse

Jede Falsifikation (nachweisbar falsche Systemantwort) wird als Evidenz behandelt, die die Posterior-Verteilung über die wahre Fehlerrate ε aktualisiert:

1. Prior: ε ~ Beta(α₀, β₀). Wähle einen schwachen Prior, z. B. Beta(1, 1) = Uniform.

2. Jede Abfrage erzeugt ein Bernoulli-Ergebnis: gefälscht (1) oder gehalten (0).

3. Posterior nach k Fälschungen in n Abfragen: Beta(α₀ + k, β₀ + n − k).

4. Posterior-Mittelwert: (α₀ + k) / (α₀ + β₀ + n) → empirische Fälschungsrate als n → ∞.

5. 95%-Glaubwürdigkeitsintervall für ε wird enger wie 1/√n.

Was uns das bringt

- Schätzung von ε₀ aus der realen Welt durch tatsächlichen Einsatz, nicht durch Worst-Case-Theorie

- Anytime-gültiger Alarm: wenn das posteriore Glaubwürdigkeitsintervall die Vertragsgrenze überschreitet, jemanden alarmieren

- Monotone Konfidenz: mehr beobachtete Abfragen → engeres CI → stärkere Garantie

Verwandte Techniken: konforme Vorhersage mit Online-Rekalibrierung (Vovk), sequentielle Wahrscheinlichkeitsverhältnistests (Wald), Online PAC-Bayes (Haddouche & Guedj 2022). Gleiche Familie, unterschiedliche mathematische Methodik.

Berechnung einer Beta-Posterior-Verteilung für Falsifikationen

Unser Team führt ein Coverage-Audit an einem produktiven Abfragesystem durch. Prior für die wahre Fehlerrate ε: Beta(1, 1) (uniform). Nach 200 Out-of-Sample-Abfragen beobachteten wir 8 Falsifikationen.