Dikotomier på punktmoln

Hur sönderslitning ser ut

Placera n punkter i vårt plan. Välj en hypotesklass (linjära klassificerare = raka linjer). Räkna hur många distinkta sätt vår klass kan märka dessa n punkter (+/− på varje sida av en linje). Kalla detta antal Π_H(n).

Om Π_H(n) = 2ⁿ, söndersliter vår klass sönder denna punktuppsättning — den kan producera varje möjlig märkning. Om Π_H(n) < 2ⁿ, kan vissa märkningar inte förekomma.

Tre punkter i allmän position

Linjära klassificerare i ℝ² söndersliter vilka 3 icke-kollinära punkter som helst. 2³ = 8 märkningar; alla 8 uppnåbara av någon linje. Välj vilka 3 punkter som helst; för varje ±/± märkning, rita en linje som skiljer positiva från negativa.

Fyra punkter vägrar att sönderslas

Placera 4 punkter i hörnen på en kvadrat. Försök märka diagonalparet som positivt & anti-diagonalparet som negativt (XOR-märkning). Ingen rak linje skiljer dem. Så Π_H(4) ≤ 14 < 16 = 2⁴.

VC-dimension som maximal sönderslitningsstorlek

VC(linjär ℝ²) = 3. Vi kan söndersla 3 punkter; vi kan inte söndersla 4. VC räknar maximal dikotomi-kapacitet för vår hypotesklass.

Geometrisk intuition

Högre VC = vår klass ritar mer utarbetade beslutsgränser. Linjär (VC = d+1 i d dimensioner) ritar hyperplan. Polynom ritar kurvor. Neurala nätverk ritar mycket veckade grenrör. Mer vikning = fler dikotomier = högre VC = högre provkrav.

Räkna dikotomier

Betrakta linjära klassificerare i ℝ² (linjer). Vi har 5 punkter placerade i allmän position (inga 3 kollinära, ingen överflödig).

Sannolikhetsmassa på hypotesmanifold

Att föreställa sig PAC-Bayes

Föreställ oss hypotesrummet som ett högt-dimensionellt grenrör. Varje punkt på detta grenrör motsvarar en viktkonfiguration för ett neuralt nätverk. Prior P tilldelar en sannolikhetsfördelning över grenröret (ofta Gaussisk centrerad vid initialisering). Posterior Q koncentrerar sannolikhetsmassa där träningsdata drev våra vikter.

KL-divergens som geometrisk distans

KL(Q‖P) mäter hur långt Q drev bort från P. Geometrisk tolkning: hur långt vår posteriormoln förflyttades från priormoln, viktad av hur osannolikt varje posteriorregion var under priorn.

Liten KL = Q överlappar P kraftigt. Posterior förflyttades knappt. Generaliseringsgapet förblir litet.

Stor KL = Q är koncentrerad i regioner P tilldelade liten massa till. Posterior förflyttades långt. Generaliseringsgapet växer.

Varför denna geometri spelar roll

Föreställ oss SGD som en söktrajektoria över hypotesmanifold. Trajektoria slutar i ett bassäng med låg träningsförlust. PAC-Bayes frågar: hur brett är detta bassäng?

Brett bassäng = många närliggande viktkonfigurationer uppnår också låg träningsförlust. Posterior Q kan sprida sig över ett brett område & fortfarande ha låg risk. KL(Q‖P) förblir begränsad. Generaliseringsgapet litet.

Smalt bassäng = endast en tunn uppsättning vikter uppnår låg förlust. Posterior måste koncentrera sig skarpare. KL växer. Generaliseringsgapet vidgas.

Detta ansluter direkt till platt-vs-vass-minima-diskurs (Hochreiter & Schmidhuber 1997, Keskar et al 2017). Platta minima generaliserar bättre eftersom de stöder bredare posteriorer med mindre KL.

Läsa ett bassängbredd

Två tränade modeller når identisk träningsförlust men bor i olika bassänger:

- Modell A: plant bassäng, posterior sprider sig över region med KL(Q_A‖P) = 50 nats.

- Modell B: vass bassäng, posterior koncentreras med KL(Q_B‖P) = 500 nats.

Båda tränade på n = 10 000 exempel med empirisk risk 0,05, δ = 0,05.

En kurva som faller där teorin förutsade att den skulle stiga

Klassisk U-kurva

Plotta modellkapacitet på den horisontella axeln. Plotta testrisk på den vertikala axeln. Klassisk bias-varians-teori förutsäger:

- Låg kapacitet: högt bias, högt testrisk (underpassning)

- Mellan kapacitet: lågt bias + låg varians, lågt testrisk (söt punkt)

- Högt kapacitet: lågt bias, högt varians, högt testrisk (överpassning)

Resultat: U-formad kurva. Välj kapacitet vid vårt botten.

Vad Belkin et al (2019) observerade

Förbi interpolationströskeln (kapacitet där modell passar träningsdata exakt med nollfel), testrisk FALLER igen. Kurva läser: nedstigning → topp vid interpolation → andra nedstigning. Två nedstigningar, en kurva.

Geometrisk tolkning av andra nedstigning

Vid interpolationströskeln har modell just tillräcklig kapacitet för att passa träningsdata — endast en (eller få) interpolerande lösningar existerar & de tenderar att vara krusiga. Generalisering lider eftersom vald lösning är tvingad.

Förbi interpolationströskeln, MÅNGA interpolerande lösningar existerar. SGD har frihet att välja en smidig (minimalnorm, låg-krökning). Geometrisk bild: lösningsmanifold blir bredare & plattare. SGD:s implicita regularisering väljer godartade lösningar från detta platta grenrör. Testrisk faller.

Varför klassisk teori missar detta

VC-dimension räknar lösningsuppsättningskapacitet men ignorerar vilken lösning som väljs. Klassisk gräns antar värsta-fall empirisk riskminimerare. Verklighet: SGD väljer tillförlitligt vår plattaste, smidigaste interpolerande lösning. Två gånger vi räknar SOLVER-VALDA lösningar istället för alla lösningar, andra nedstigning är logisk.

Geometrisk slutsats

Kapacitet spelar mindre roll än bassänggeometri. Breda platta bassänger (efter interpolation) generaliserar bättre än smala vassa (vid interpolation). Modern teori försöker begränsa generalisering genom bassängbredd, inte genom parameterantal.

Lokalisera de två nedstigningarna

På en dubbel nedstigningskurva spelar tre regioner roll: (1) under-parametriserad regim, (2) interpolationstoppi, (3) över-parametriserad regim.

Potenslagsyta i parameter-token-rymd

En 3D-yta

Plotta parametrar N på en horisontell axel. Plotta tokens D på en andra horisontell axel. Plotta förlust L på vertikal. Empirisk förlust ritar en potenslagsyta över detta (N, D)-plan:

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

Ytan lutar nedåt när antingen N eller D växer. Sluttningar följer log-linjära potensslagar (raka linjer i log-log-plot). Asymptot L∞ förblir positiv — irreducerbar förlust som vår modell inte kan krympa förbi.

Beräknings-optimal rygg

Fixera total beräkningsbudget C ∝ N × D (parametrar × tokens, ungefär). Skiva vår yta längs denna begränsning. Skivspår skär en 2D-kurva genom 3D-yta. Botten på denna kurva = beräknings-optimal punkt.

Chinchilla (Hoffmann et al 2022) beräknade denna botten analytiskt: D_opt ≈ 20 × N. Kurva längs beräkningsbudget = en rygg. Gång längs rygg: samma beräkning, minskande förlust. Gång av rygg (fler parametrar än 20× tokens, eller färre): slösat beräkning.

Geometrisk läsning av GPT-3 kontra Chinchilla

GPT-3: 175B params, 300B tokens. Chinchilla-optimal skulle vilja 175B × 20 = 3500B tokens. GPT-3 sitter långt från den beräknings-optimala ryggen i vår parameter-tung riktning. Chinchilla själv: 70B params tränade på 1400B tokens. 1400 / 70 = 20 — exakt på rygg. Chinchilla slog GPT-3 med mindre än hälften av dess parameterantal genom att sitta på geometrisk optimum.

Dataväggen som vertikal plan

Offentligt webb ~10¹³ användbara tokens. Detta plottas som en vertikal vägg vid D = 10¹³ på vår parameter-token-plan. Förbi denna vägg, beräknings-optimal träning kräver N ≤ D / 20 = 5 × 10¹¹ params. Väggar förbi N = 5 × 10¹¹ antingen kör under-tränade (av-rygg) eller kräver syntetisk / multimodal / RL-data för att skjuta vägg outåt.

Gå längs den beräknings-optimala ryggen

Vi sitter vid GPT-3 koordinater: N = 175B params, D = 300B tokens. Beräknings-proxy C = N × D = 5,25 × 10²² param-tokens.

Beta-posterior som stramar åt till en nål

En sannolikhetstäthet på [0, 1]

Beta(α, β) är en sannolikhetstäthet över enhetsintervallet [0, 1]. Variabel: ε = sann felfrekvens. Form: α kontrollerar massa på högt-ε-sida; β kontrollerar massa på lågt-ε-sida.

Beta(1, 1): uniform — ingen information, platt densitet över [0, 1].

Beta(α, β) med α + β stor: koncentrerad topp vid α / (α + β).

Bredd på Beta-topp krymper som 1/√(α+β). Att lägga till 100 observationer till vår prior stramar åt topppen med faktor √100 = 10. Att lägga till 10000 observationer stramar åt med √10000 = 100.

Geometrisk läsning av en revisionskörning

Start: Beta(1, 1) = platt rektangel på [0, 1]. Maximal osäkerhet om ε.

Efter 200 frågor med 8 falsifieringar: Beta(9, 193). Medelvärde = 9/202 ≈ 0,045. Densitet nu en skarp puckel centrerad nära 0,045 med karakteristisk bredd σ ≈ 0,014.

Efter 2000 frågor med 80 falsifieringar: Beta(81, 1921). Medelvärde fortfarande ≈ 0,045, men bredd σ ≈ 0,0046. Puckel tre gånger skarpare.

Efter 200 000 frågor med 8000 falsifieringar: Beta(8001, 192 001). Medelvärde ≈ 0,040, bredd σ ≈ 0,0004. Puckel blir en nål.

Geometrisk konvergens till en punktmassa

När n → ∞, Beta-posterior kollapsar till en Dirac-delta vid sann ε. Geometri: rektangel → bred puckel → smal puckel → nål → punkt. Varje fråga stramar åt vår fördelning med 1/√n.

Varför detta slår teoretiska PAC-gränser

Teoretiska PAC-gränser ger en STATISK ε-uppskattning baserad på hypotesklasstorlek. Beta-posterior ger en DYNAMISK ε-uppskattning som stramar åt med varje observation, kalibrerad mot din verkliga fördelning. Teoretisk gräns = en garanti under värsta-fall-antaganden. Empirisk revision = en mätning av faktisk verklighet.

Hur många frågor för att halvera det trovärda intervallet?

Vi sitter för närvarande vid Beta(9, 193) efter 200 frågor: medelvärde ε ≈ 0,045, σ ≈ 0,014. Vi vill halvera det trovärda intervallet bredd till σ ≈ 0,007.