Krossning & VC-dimension

När hypotesrymder blir oändliga

Gränsen m ≥ (1/ε)(ln|H| + ln(1/δ)) bryter samman när |H| = ∞. De flesta användbara hypotesklasser (linjära klassificerare i ℝᵈ, beslutsträd, neurala nät) innehåller oändligt många kandidater. Vapnik & Chervonenkis löste detta runt 1971 med ett rikare mått på komplexitet: VC-dimension.

Shattering

En hypotesklass H shatterar en mängd av n punkter om H kan producera varje möjlig etikettering av dessa n punkter (alla 2ⁿ dikotomier). Linjära klassificerare i ℝ² shatterar alla 3 punkter i generell position: för varje av de 8 möjliga +/−-etiketteringarna av dessa 3 punkter finns det en linje som separerar dem korrekt.

Men linjära klassificerare i ℝ² kan inte krossa 4 punkter arrangerade i en XOR-konfiguration. Ingen rak linje separerar det diagonala paret från det antidiagonala paret.

VC-dimension

VC(H) = det största n sådant att H krossar någon n-punktsmängd. För linjära klassificerare i 2D: VC = 3. För axeljusterade rektanglar i 2D: VC = 4. För neurala nätverk med W vikter: VC ≤ O(W² log W) (Bartlett & Anthony 1999).

Provkomplexitet med VC-dimension

Ersätt ln|H| i vår PAC-gräns med VC-dimension d:

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

VC-dimension fungerar som vår ”effektiva komplexitet” för en oändlig klass. En hypotesklass med låg VC-dimension generaliserar från få exempel; en klass med hög VC-dimension kräver mer data.

VC-dimension som effektivt hypotesantal

Ett neuralt nätverk har W = 10⁹ vikter. Enligt Bartlett-Anthony-gränsen gäller VC ≤ O(W² log W). Approximera VC ≈ W² log₂ W.

Utan Realiserbarhet, Posteriorer över Hypoteser

Två viktiga generaliseringar

Klassisk PAC antar att vårt målbegrepp c finns inom vår hypotesklass H. Verklig data innehåller brus, felmärkningar och begrepp som vår klass inte kan representera. Två utvidgningar hanterar detta.

Agnostic PAC

Släpp antagandet att c ∈ H. Konkurrera nu mot vår bästa-i-klassen-hypotes h* = argmin_{h ∈ H} risk(h). Gränsernas form ändras: istället för att komma nära perfekt får vi komma nära det bästa-möjliga-inom-H.

Agnostisk gräns: P[risk(h) ≤ risk(h*) + ε] ≥ 1 − δ med stickprovsstorlek m = O(1/ε² × (VC(H) + log(1/δ))). Notera ε² istället för ε i nämnaren: agnostisk inlärning behöver fler stickprov för samma precision.

PAC-Bayes (McAllester 1999)

Gå från att välja en enskild hypotes till att välja en fördelning över hypoteser. Börja med en prior P. Observera data. Härled posterior Q. PAC-Bayes ger gränser för förväntad risk under Q:

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

KL(Q‖P) mäter hur långt vår posterior har flyttat sig från vår prior. Två tolkningar:

1. Kompressionsvy. En posterior som ligger nära sin prior (litet KL) generaliserar väl — liten informationskostnad = litet generaliseringsgap.

2. Bayesiansk vy. Stark prior + svag datauppdatering = snäv gräns; svag prior + kraftig datauppdatering = lösare gräns.

Varför PAC-Bayes är viktigt. Empiriska PAC-Bayes-gränser (Catoni 2007, Dziugaite & Roy 2017) ger numeriskt meningsfulla generaliseringsgarantier för verkliga neurala nätverk där klassiska PAC-gränser blir tomma. De utgör fortfarande vårt starkaste teoretiska verktyg för att förstå generalisering i överparametriserade modeller.

Läsa en PAC-Bayes-gräns

Anta att vi tränar ett nätverk på n = 50 000 märkta exempel. Efter träningen har vår posterior Q över vikter KL(Q‖P) = 200 nats relativt en Gaussisk prior P. Empirisk risk under Q ligger på 0,10. Sätt δ = 0,05.

Överparameterisering & Dubbel descent

Klassiska PAC:s förutsagda katastrof

Klassisk PAC förutsäger: fler parametrar än sampel = katastrofal överanpassning. Lär sig perfekt på träningsdata, generaliserar slumpmässigt på testdata. VC-gränsen förutsäger memorering utan inlärning.

Moderna neurala nätverk har rutinmässigt 10× till 1000× fler parametrar än träningsprov och generaliserar ändå. Detta borde inte hända enligt klassisk teori. Det händer ändå.

U-kurvan vi fick lära oss

Klassisk bias-varians: när modellens kapacitet ökar sjunker träningsfelet monotont; testfelet sjunker först (mindre underanpassning), når ett minimum och stiger sedan (överanpassning). U-formen förutspås av VC-teori.

Vad som faktiskt händer — Dubbel nedstigning

Belkin m.fl. (2019) visade att testfelet följer den klassiska U-kurvan fram till interpoleringströskeln (kapacitet = antal sampel), och sedan SJUNKER IGEN efter den tröskeln. Massivt överparametriserade modeller generaliserar bättre än modeller som bara är tillräckligt stora.

Varför klassisk PAC missar detta

1. Antagandet om distributionsfrihet är alltför pessimistiskt. Verkliga data har struktur (låg intrinsisk dimension, mångfaldsgeometri). PAC-gränser gäller för värsta tänkbara fördelningar; verkliga fördelningar utnyttjar struktur som även SGD utnyttjar.

2. Implicit regularisering. SGD på överparametriserade nätverk finner minimum-norm- eller minimum-komplexitetslösningar som interpolerar, inte godtyckliga sådana. Klassisk teori antar en worst-case empirisk riskminimering; verkliga algoritmer väljer godartade lösningar.

3. Hypotesklassdefinitionen är fel. Den effektiva hypotesklass som SGD utforskar är mycket mindre än det nominella viktutrymmet. PAC-Bayes-posteriorer fångar detta; VC-dimension gör det inte.

Modern teoretisk forskning (Bartlett, Long, Lugosi, Tsigler 2020 om benign overfitting; Nakkiran m.fl. 2020 om double descent) bygger en post-PAC-generaliserings­teori som tar hänsyn till vår överparametriserade regim.

Diagnostisering av ett misslyckande för klassisk PAC

Ett forskarteam tränar ett nätverk med 1 miljard parametrar på 100 000 märkta exempel. Klassisk PAC förutsäger tomma gränser. Empiriskt når testnoggrannheten 95 %.

Kaplan, Chinchilla och dimensionering av automatiserad generell intelligens

Från gränser till empiriska skalningslagar

Klassisk PAC förutsäger datasetstorlek teoretiskt och ger tomma resultat. Empiriska skalningslagar förutsäger datasetstorlek från observation och fungerar i praktiken. De har ersatt PAC som vårt praktiska verktyg för att dimensionera stora modeller.

Kaplan et al (2020)

Förlusten följer en potenslag i parametrar N, dataset-tokens D och beräkningsresurser C:

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

Att dubbla antalet parametrar sänker förlusten med en fast multiplikativ faktor. Att dubbla datamängden sänker förlusten med en annan fast faktor. Dessa exponenter (αN, αD, αC) mäter och förutsäger frontier-beteende över många storleksordningar.

Hoffmann et al 2022 (Chinchilla)

Chinchilla visade att Kaplans exponenter överviktade parametrar i förhållande till data. Beräkningsoptimal träning kräver ungefär 20 tokens per parameter:

D_opt ≈ 20 × N

GPT-3 (175B parametrar) tränades på ~300B tokens — kraftigt undertränad enligt Chinchillas beräkningar. En beräkningsoptimal 175B-parametermodell kräver ~3,5 biljoner tokens.

Data Wall

Att skala upp antalet parametrar kräver att vi skalar upp antalet tokens proportionellt. Offentliga webbskrapningar ger cirka 10¹³ användbara tokens. En hypotetisk 10¹⁵-parametrar stor automatiserad generell intelligens skulle behöva cirka 2×10¹⁶ tokens — tre storleksordningar mer än tillgänglig webbdata.

Detta är vår datavägg. Skalningslagar förutspår att vi stöter på brist på korpus långt innan vi stöter på brist på beräkningskraft. Syntetisk data, multimodala korpusar (video, ljud, sensordata) och RL-från-miljö syftar alla till att ta sig förbi den.

Klassisk PAC sa oss (felaktigt) att vi behövde 10²¹ exempel. Skalningslagar säger oss (kalibrerat mot verkligheten) att vi behöver 2×10¹⁶. Båda siffrorna överstiger tillgänglig text. Gränsforskning idag handlar om att täppa till det gapet.

Uppskattning av en korpus för automatiserad generell intelligens

Anta att ett frontlab föreslår en 10¹⁴-parametrars modell och hävdar att den kommer att nå automatiserad generell intelligens. Vi vill dimensionera dess träningskorpus enligt Chinchillas regel.

Från teoretiska gränser till produktionsmätningar

Sluta beräkna gränser; börja mäta dem

Klassiska PAC-gränser blir tomma. PAC-Bayes-gränser blir snäva under antaganden som är svåra att verifiera. Ett praktiskt alternativ: mät ε empiriskt på din verkliga fördelning och uppdatera den allt eftersom ditt system körs.

Idé 1 — Gör täckning till empirisk PAC

Ett make coverage-mål kör N hållna frågor genom ditt frågesystem och mäter två andelar:

- cache_hit_rate — andelen där ditt system hittade ett känt svar

- i_dont_know_rate — andelen där ditt system ärligt avstod

Varje mätning = ett Bernoulli-försök. Från observerade antal beräknas ett Wilson-konfidensintervall för den sanna andelen. Exempel: N = 1000 frågor, observerad i_dont_know_rate = 0.20 → 95 % CI ≈ [0.177, 0.226]. Övre gränsen 0.226 fungerar exakt som en PAC-ε vid δ = 0.05, härledd från verkliga data på den verkliga fördelningen istället för en teoretisk värsta-fall-analys.

Klassisk PAC-terminologi gäller (ε, δ, konfidens). Annan matematik (binomial koncentration vs. VC-teori). Snävare resultat eftersom verkliga fördelningar innehåller utnyttjbar struktur.

Idé 2 — PAC-Bayes-granskning via falsifieringshändelser

Behandla varje falsifiering (systemets svar är bevisligen felaktigt) som evidens som uppdaterar posteriorn över den sanna felandelen ε:

1. Prior: ε ~ Beta(α₀, β₀). Välj en svag prior, t.ex. Beta(1, 1) = likformig.

2. Varje query ger ett Bernoulli-utfall: förfalskad (1) eller godkänd (0).

3. Posterior efter k förfalskningar i n queries: Beta(α₀ + k, β₀ + n − k).

4. Posterior medelvärde: (α₀ + k) / (α₀ + β₀ + n) → empirisk förfalskningsfrekvens när n → ∞.

5. 95 % trovärdighetsintervall för ε stramas åt som 1/√n.

Vad detta ger oss

- Uppskattning av verklig ε₀ från faktisk drift, inte värsta-fall-teori

- Anytime-valid larm: när det bakre trovärdiga intervallet korsar kontraktströskeln, pager någon

- Monoton konfidens: fler observerade queries → smalare CI → starkare garanti

Släktingstekniker: konform prediktion med online-rekalibrering (Vovk), sekventiella sannolikhetskvottest (Wald), online PAC-Bayes (Haddouche & Guedj 2022). Samma familj, olika matematiska verktyg.

Beräkna en Beta-posterior för falsifikationer

Vårt team kör en täckningsrevision på ett produktionsfrågesystem. Prior på sann felfrekvens ε: Beta(1, 1) (likformig). Efter 200 hållna-out-frågor observerade vi 8 falsifikationer.