Dichotomien auf Punktwolken

Wie Zerschmettern aussieht

Platziere n Punkte in unserer Ebene. Wähle eine Hypothesenklasse (lineare Klassifikatoren = gerade Linien). Zähle, wie viele unterschiedliche Wege unsere Klasse diese n Punkte beschriften kann (+/− auf jeder Seite einer Linie). Nenne diese Anzahl Π_H(n).

Wenn Π_H(n) = 2ⁿ, dann zerschmettert unsere Klasse diese Punktmenge — sie kann jede mögliche Beschriftung erzeugen. Wenn Π_H(n) < 2ⁿ, können einige Beschriftungen nicht auftreten.

Drei Punkte in allgemeiner Position

Lineare Klassifikatoren in ℝ² zerschmettern jede 3 nicht-kollineare Punkte. 2³ = 8 Beschriftungen; alle 8 erreichbar durch eine Linie. Wähle beliebige 3 Punkte; für jede ±/±-Beschriftung zeichne eine Linie, die positive von negativen trennt.

Vier Punkte verweigern das Zerschmettern

Platziere 4 Punkte an den Ecken eines Quadrats. Versuche, das diagonale Paar als positiv und das anti-diagonale Paar als negativ zu beschriften (XOR-Beschriftung). Keine gerade Linie trennt sie. Also Π_H(4) ≤ 14 < 16 = 2⁴.

VC-Dimension als maximale Zerschmettergröße

VC(linear ℝ²) = 3. Wir können 3 Punkte zerschmettern; wir können 4 nicht zerschmettern. VC zählt die maximale Dichotomie-Kapazität unserer Hypothesenklasse.

Geometrische Intuition

Höhere VC = unsere Klasse zeichnet aufwendigere Entscheidungsgrenzen. Linear (VC = d+1 in d Dimensionen) zeichnet Hyperebenen. Polynome zeichnen Kurven. Neuronale Netze zeichnen stark gefaltete Mannigfaltigkeiten. Mehr Faltbarkeit = mehr Dichotomien = höhere VC = höherer Stichprobenbedarf.

Dichotomien zählen

Betrachte lineare Klassifikatoren in ℝ² (Linien). Wir haben 5 Punkte in allgemeiner Position platziert (keine 3 kollinear, keine redundant).

Wahrscheinlichkeitsmasse auf einer Hypothesen-Mannigfaltigkeit

PAC-Bayes bildlich

Stelle dir unseren Hypothesenraum als hochdimensionale Mannigfaltigkeit vor. Jeder Punkt auf dieser Mannigfaltigkeit entspricht einer Gewichtskonfiguration eines neuronalen Netzes. Prior P weist eine Wahrscheinlichkeitsverteilung über unserer Mannigfaltigkeit zu (oft Gaußsch, zentriert bei der Initialisierung). Posterior Q konzentriert Wahrscheinlichkeitsmasse dort, wo die Trainingsdaten unsere Gewichte trieben.

KL-Divergenz als geometrische Distanz

KL(Q‖P) misst, wie weit Q von P abgedriftet ist. Geometrische Lesart: wie viel sich unsere Posterior-Wolke von der Prior-Wolke bewegt hat, gewichtet danach, wie unwahrscheinlich jede Posterior-Region unter unserem Prior war.

Kleines KL = Q überlappt P stark. Posterior bewegte sich kaum. Generalisierungslücke bleibt klein.

Großes KL = Q konzentrierte sich in Regionen, denen P wenig Masse zuwies. Posterior bewegte sich stark. Generalisierungslücke wächst.

Warum diese Geometrie wichtig ist

Stelle dir SGD als Suchtrajektorie über unserer Hypothesen-Mannigfaltigkeit vor. Die Trajektorie endet in einem Becken niedrigen Trainingsverlustes. PAC-Bayes fragt: Wie breit ist dieses Becken?

Breites Becken = viele benachbarte Gewichtskonfigurationen erreichen ebenfalls niedrigen Trainingsverlust. Posterior Q kann sich über eine breite Region ausbreiten und immer noch ein niedriges Risiko haben. KL(Q‖P) bleibt beschränkt. Generalisierungslücke klein.

Schmales Becken = nur eine dünne Menge von Gewichten erreicht niedrigen Verlust. Posterior muss scharf konzentriert sein. KL wächst. Generalisierungslücke verbreitert sich.

Dies verbindet sich direkt mit dem Diskurs über flache vs. scharfe Minima (Hochreiter & Schmidhuber 1997, Keskar et al 2017). Flache Minima generalisieren besser, weil sie breitere Posteriore mit kleinerem KL unterstützen.

Eine Beckenbreite lesen

Zwei trainierte Modelle erreichen identischen Trainingsverlust, leben aber in verschiedenen Becken:

- Modell A: flaches Becken, Posterior breitet sich über einer Region mit KL(Q_A‖P) = 50 nats aus.

- Modell B: scharfes Becken, Posterior konzentriert sich mit KL(Q_B‖P) = 500 nats.

Beide trainiert auf n = 10.000 Beispielen mit empirischem Risiko 0,05, δ = 0,05.

Eine Kurve, die fällt, wo die Theorie Anstieg vorhersagte

Klassische U-Kurve

Trage die Modellkapazität auf der horizontalen Achse ab. Trage das Testrisiko auf der vertikalen Achse ab. Klassische Bias-Varianz-Theorie sagt voraus:

- Niedrige Kapazität: hoher Bias, hohes Testrisiko (Underfit)

- Mittlere Kapazität: niedriger Bias + niedrige Varianz, niedriges Testrisiko (Sweet Spot)

- Hohe Kapazität: niedriger Bias, hohe Varianz, hohes Testrisiko (Overfit)

Ergebnis: U-förmige Kurve. Wähle die Kapazität an unserem Tiefpunkt.

Was Belkin et al (2019) beobachteten

Jenseits der Interpolationsschwelle (Kapazität, bei der das Modell die Trainingsdaten genau mit Null-Fehler anpasst), FÄLLT das Testrisiko erneut. Die Kurve liest sich: Abstieg → Spitze bei Interpolation → zweiter Abstieg. Zwei Abstiege, eine Kurve.

Geometrische Lesart des zweiten Abstiegs

An der Interpolationsschwelle hat das Modell gerade genug Kapazität, um die Trainingsdaten anzupassen — nur eine (oder wenige) interpolierende Lösungen existieren und sie neigen dazu, gezackt zu sein. Generalisierung leidet, weil die gewählte Lösung erzwungen ist.

Jenseits der Interpolationsschwelle existieren VIELE interpolierende Lösungen. SGD hat die Freiheit, eine glatte (minimale-Norm, niedrige Krümmung) zu wählen. Geometrisches Bild: Die Lösungs-Mannigfaltigkeit wird breiter und flacher. SGDs implizite Regularisierung wählt gutartige Lösungen aus dieser flachen Mannigfaltigkeit. Testrisiko fällt.

Warum die klassische Theorie dies verfehlt

Die VC-Dimension zählt die Lösungsmengen-Kapazität, ignoriert jedoch, welche Lösung gewählt wird. Die klassische Schranke nimmt den Worst-Case-Empirisch-Risiko-Minimierer an. Realität: SGD wählt zuverlässig unsere flachste, glatteste interpolierende Lösung. Sobald wir SOLVER-GEWÄHLTE Lösungen anstelle aller Lösungen zählen, ergibt der zweite Abstieg Sinn.

Geometrische Schlussfolgerung

Kapazität zählt weniger als Beckengeometrie. Breite flache Becken (post-Interpolation) generalisieren besser als schmale scharfe (bei Interpolation). Die moderne Theorie versucht, Generalisierung durch Beckenbreite zu beschränken, nicht durch Parameteranzahl.

Lokalisierung der zwei Abstiege

Auf einer Double-Descent-Kurve sind drei Regionen wichtig: (1) unterparametrisiertes Regime, (2) Interpolationsspitze, (3) überparametrisiertes Regime.

Potenzgesetz-Oberfläche im Parameter-Token-Raum

Eine 3D-Oberfläche

Trage Parameter N auf einer horizontalen Achse ab. Trage Tokens D auf einer zweiten horizontalen Achse ab. Trage Verlust L auf der vertikalen ab. Empirischer Verlust schnitzt eine Potenzgesetz-Oberfläche über diese (N, D)-Ebene:

L(N, D) ≈ (Nc/N)^αN + (Dc/D)^αD + L∞

Die Oberfläche neigt sich nach unten, wenn entweder N oder D wächst. Steigungen folgen log-linearen Potenzgesetzen (gerade Linien im Log-Log-Plot). Die Asymptote L∞ bleibt positiv — irreduzibler Verlust, den unser Modell nicht kleiner schrumpfen kann.

Rechenoptimaler Grat

Festes Gesamt-Rechenbudget C ∝ N × D (Parameter × Tokens, grob). Schneide unsere Oberfläche entlang dieser Einschränkung. Die Schnittspur schneidet eine 2D-Kurve durch die 3D-Oberfläche. Tiefpunkt dieser Kurve = rechenoptimaler Punkt.

Chinchilla (Hoffmann et al 2022) berechnete diesen Tiefpunkt analytisch: D_opt ≈ 20 × N. Die Kurve entlang des Rechenbudgets = ein Grat. Auf dem Grat zu gehen: gleiche Rechenleistung, abnehmender Verlust. Vom Grat herunterzugehen (mehr Parameter als 20× Tokens, oder weniger): verschwendete Rechenleistung.

Geometrische Lesart von GPT-3 vs. Chinchilla

GPT-3: 175B Parameter, 300B Tokens. Chinchilla-optimal würde 175B × 20 = 3500B Tokens wollen. GPT-3 sitzt weit abseits des rechenoptimalen Grats in unsere parameter-schwere Richtung. Chinchilla selbst: 70B Parameter trainiert auf 1400B Tokens. 1400 / 70 = 20 — genau auf dem Grat. Chinchilla schlug GPT-3 mit weniger als der Hälfte seiner Parameteranzahl, indem es auf dem geometrischen Optimum saß.

Datenmauer als vertikale Ebene

Öffentliches Web ~10¹³ nutzbare Tokens. Dies wird als vertikale Mauer bei D = 10¹³ auf unserer Parameter-Token-Ebene aufgetragen. Jenseits dieser Mauer erfordert rechenoptimales Training N ≤ D / 20 = 5 × 10¹¹ Parameter. Mauern jenseits N = 5 × 10¹¹ laufen entweder untertrainiert (abseits des Grats) oder erfordern synthetische / multimodale / RL-Daten, um die Mauer nach außen zu drücken.

Auf dem rechenoptimalen Grat gehen

Wir sitzen an GPT-3 Koordinaten: N = 175B Parameter, D = 300B Tokens. Rechen-Proxy C = N × D = 5,25 × 10²² Parameter-Tokens.

Beta-Posteriore verengt sich zu einer Nadel

Eine Wahrscheinlichkeitsdichte auf [0, 1]

Beta(α, β) ist eine Wahrscheinlichkeitsdichte über dem Einheitsintervall [0, 1]. Variable: ε = wahre Fehlerrate. Form: α steuert Masse auf der hohen-ε-Seite; β steuert Masse auf der niedrigen-ε-Seite.

Beta(1, 1): gleichmäßig — keine Information, flache Dichte über [0, 1].

Beta(α, β) mit α + β groß: konzentrierter Spitzenwert bei α / (α + β).

Breite des Beta-Spitzenwerts schrumpft als 1/√(α+β). 100 Beobachtungen zum Prior hinzuzufügen verengt den Spitzenwert um Faktor √100 = 10. 10000 Beobachtungen hinzuzufügen verengt um √10000 = 100.

Geometrische Lesart eines Audit-Laufs

Start: Beta(1, 1) = flaches Rechteck auf [0, 1]. Maximale Unsicherheit über ε.

Nach 200 Abfragen mit 8 Falsifikationen: Beta(9, 193). Mittelwert = 9/202 ≈ 0,045. Dichte jetzt ein scharfer Buckel zentriert nahe 0,045 mit charakteristischer Breite σ ≈ 0,014.

Nach 2000 Abfragen mit 80 Falsifikationen: Beta(81, 1921). Mittelwert immer noch ≈ 0,045, aber Breite σ ≈ 0,0046. Buckel dreimal schärfer.

Nach 200.000 Abfragen mit 8000 Falsifikationen: Beta(8001, 192.001). Mittelwert ≈ 0,040, Breite σ ≈ 0,0004. Buckel wird eine Nadel.

Geometrische Konvergenz zu einer Punktmasse

Wenn n → ∞, kollabiert die Beta-Posteriore zu einem Dirac-Delta beim wahren ε. Geometrie: Rechteck → breiter Buckel → schmaler Buckel → Nadel → Punkt. Jede Abfrage verengt unsere Verteilung um 1/√n.

Warum dies theoretische PAC-Schranken übertrifft

Theoretische PAC-Schranken geben eine STATISCHE ε-Schätzung basierend auf der Größe der Hypothesenklasse. Beta-Posteriore gibt eine DYNAMISCHE ε-Schätzung, die sich mit jeder Beobachtung verengt, kalibriert gegen unsere reale Verteilung. Theoretische Schranke = eine Garantie unter Worst-Case-Annahmen. Empirische Prüfung = eine Messung der tatsächlichen Realität.

Wie viele Abfragen um das glaubwürdige Intervall zu halbieren?

Wir befinden uns derzeit bei Beta(9, 193) nach 200 Abfragen: Mittelwert ε ≈ 0,045, σ ≈ 0,014. Wir wollen die glaubwürdige Intervallbreite auf σ ≈ 0,007 halbieren.