PAC come Piano a Due Assi
Due Assi, Una Superficie di Conteggio di Campioni
Traccia ε sull'asse orizzontale (tolleranza d'errore, intervallo da 0 a 1). Traccia δ sull'asse verticale (probabilità di fallimento, intervallo da 0 a 1). Ogni punto in questo quadrato unitario corrisponde a una coppia di domanda (ε, δ).
Sopra ogni punto siede un valore di conteggio di campioni m(ε, δ) = (1/ε)(ln|H| + ln(1/δ)). Insieme, quei valori di m traccia una superficie curva sopra il nostro quadrato. Esigenze più rigorose (ε minore, δ minore) tirano la nostra superficie verso l'alto; esigenze più lasca la appiattiscono.
Linee di Contorno Iso-Campione
Proietta la nostra superficie indietro nel piano come contorni iso-m. Ogni coppia (ε, δ) su un singolo contorno richiede il nostro stesso bilancio di campioni. Muoviti lungo un contorno per scambiare tolleranza d'errore con fiducia a costo fisso.
Dimezzare un Asse
Dimezzare ε lungo il nostro orizzontale sposta m verso l'alto di fattore 2 (lineare in 1/ε). Dimezzare δ lungo il nostro verticale sposta m verso l'alto di ln(2) ≈ 0,69 (logaritmico in 1/δ). La geometria ci dice: la tolleranza d'errore porta un costo più ripido della fiducia.
Leggere la Superficie di Bilancio
Siamo nel punto (ε = 0,05, δ = 0,05) per la classe di ipotesi |H| = 10⁶. Il requisito di campioni m₀ = (1/0,05)(ln(10⁶) + ln(20)) = 20 × (13,8 + 3,0) = 336.
Dicotomie su Nuvole di Punti
Come Appare la Frantumazione
Posiziona n punti nel nostro piano. Scegli una classe di ipotesi (classificatori lineari = linee rette). Conta quanti modi distinti la nostra classe può etichettare quei n punti (+/− su ogni lato di una linea). Chiama questo conteggio Π_H(n).
Se Π_H(n) = 2ⁿ, la nostra classe frantuma quel insieme di punti — può produrre ogni etichettatura possibile. Se Π_H(n) < 2ⁿ, alcune etichettature non possono verificarsi.
Tre Punti in Posizione Generale
I classificatori lineari in ℝ² frantumano tutti i 3 punti non collineari. 2³ = 8 etichettature; tutte 8 realizzabili da una qualche linea. Scegli 3 punti qualsiasi; per ogni etichettatura ±/±, disegna una linea che separa i positivi dai negativi.
Quattro Punti si Rifiutano di Frantumarsi
Posiziona 4 punti agli angoli di un quadrato. Prova a etichettare la coppia diagonale come positiva & la coppia anti-diagonale come negativa (etichettatura XOR). Nessuna linea retta le separa. Quindi Π_H(4) ≤ 14 < 16 = 2⁴.
Dimensione VC come Dimensione Massima di Frantumazione
VC(lineare ℝ²) = 3. Possiamo frantumare 3 punti; non possiamo frantumare 4. VC conta la capacità massima di dicotomia della nostra classe di ipotesi.
Intuizione Geometrica
VC più alto = la nostra classe disegna confini decisionali più elaborati. Lineare (VC = d+1 in d dimensioni) disegna iperpiani. I polinomi disegnano curve. Le reti neurali disegnano varietà altamente piegate. Più pieghevolezza = più dicotomie = VC più alto = requisito di campioni più alto.
Conteggio delle Dicotomie
Considera i classificatori lineari in ℝ² (linee). Abbiamo 5 punti posizionati in posizione generale (nessun 3 collineari, nessuno ridondante).
Massa di Probabilità su Varietà di Ipotesi
Immaginando PAC-Bayes
Immagina lo spazio delle ipotesi come una varietà ad alta dimensionalità. Ogni punto su questa varietà corrisponde a una configurazione di peso di una rete neurale. La priorità P assegna una distribuzione di probabilità attraverso la nostra varietà (spesso gaussiana centrata sull'inizializzazione). Il posteriore Q concentra la massa di probabilità dove i dati di addestramento hanno spinto i nostri pesi.
Divergenza KL come Distanza Geometrica
KL(Q‖P) misura quanto lontano Q si è allontanato da P. Lettura geometrica: quanto la nuvola posteriore si è mossa dalla nuvola prioritaria, ponderata da quanto improbabile fosse ogni regione posteriore secondo la nostra priorità.
KL piccolo = Q si sovrappone a P pesantemente. Il posteriore si è appena mosso. Il divario di generalizzazione rimane piccolo.
KL grande = Q concentrato in regioni a cui P ha assegnato poca massa. Il posteriore si è mosso molto. Il divario di generalizzazione cresce.
Perché Questa Geometria Importa
Immagina SGD come una traiettoria di ricerca attraverso la nostra varietà di ipotesi. La traiettoria termina in un bacino di bassa perdita di addestramento. PAC-Bayes chiede: quanto è largo questo bacino?
Bacino largo = molte configurazioni di peso vicine raggiungono anche bassa perdita di addestramento. Il posteriore Q può diffondersi su una vasta regione & avere comunque basso rischio. KL(Q‖P) rimane limitato. Il divario di generalizzazione è piccolo.
Bacino stretto = solo una serie sottile di pesi raggiunge bassa perdita. Il posteriore deve concentrarsi in modo acuto. KL cresce. Il divario di generalizzazione si allarga.
Questo si collega direttamente al discorso minimi piatti vs acuti (Hochreiter & Schmidhuber 1997, Keskar et al 2017). I minimi piatti si generalizzano meglio perché supportano posteriori più larghi con KL minore.
Leggere una Larghezza di Bacino
Due modelli addestrati raggiungono una perdita di addestramento identica ma vivono in bacini diversi:
- Modello A: bacino piatto, il posteriore si diffonde su una regione con KL(Q_A‖P) = 50 nats.
- Modello B: bacino acuto, il posteriore si concentra con KL(Q_B‖P) = 500 nats.
Entrambi addestrati su n = 10.000 esempi con rischio empirico 0,05, δ = 0,05.
Una Curva che Scende Dove la Teoria Prevedeva Ascesa
Curva U Classica
Traccia la capacità del modello sull'asse orizzontale. Traccia il rischio di prova sull'asse verticale. La teoria classica di bias-varianza prevede:
- Bassa capacità: alto bias, alto rischio di prova (sottoapprendimento)
- Capacità media: basso bias + bassa varianza, basso rischio di prova (punto dolce)
- Alta capacità: basso bias, alta varianza, alto rischio di prova (sovraapprendimento)
Risultato: curva a forma di U. Scegli la capacità al nostro fondo.
Cosa Ha Osservato Belkin et al (2019)
Oltre la soglia di interpolazione (capacità dove il modello si adatta esattamente ai dati di addestramento con errore zero), il rischio di prova SCENDE di nuovo. La curva legge: discesa → picco all'interpolazione → seconda discesa. Due discese, una curva.
Lettura Geometrica della Seconda Discesa
Alla soglia di interpolazione, il modello ha proprio la giusta capacità per adattarsi ai dati di addestramento — esiste una sola (o poche) soluzione interpolante & tendono ad essere frastagliate. La generalizzazione soffre perché la soluzione scelta è forzata.
Oltre la soglia di interpolazione, esistono MOLTE soluzioni interpolanti. SGD ha la libertà di sceglierne una liscia (norma minima, bassa curvatura). Il quadro geometrico: la varietà della soluzione diventa più larga & più piatta. L'implica regolarizzazione di SGD sceglie soluzioni benigne da questa varietà piatta. Il rischio di prova scende.
Perché la Teoria Classica lo Manca
La dimensione VC conta la capacità dell'insieme di soluzioni ma ignora quale soluzione viene scelta. Il legame classico assume il peggiore minimizzatore di rischio empirico. Realtà: SGD sceglie in modo affidabile la soluzione interpolante più piatta & liscia. Una volta che contiamo le soluzioni SCELTE DAL RISOLUTORE anziché tutte le soluzioni, la seconda discesa ha senso.
Rapporto Geometrico da Portare a Casa
La capacità importa meno della geometria del bacino. Bacini ampi piatti (post-interpolazione) si generalizzano meglio di quelli stretti acuti (all'interpolazione). La teoria moderna tenta di limitare la generalizzazione dalla larghezza del bacino, non dal conteggio dei parametri.
Localizzare le Due Discese
Su una curva di doppia discesa, tre regioni importano: (1) regime sottoparametrizzato, (2) picco di interpolazione, (3) regime sovraparametrizzato.
Superficie di Legge di Potenza nello Spazio Parametri-Token
Una Superficie 3D
Traccia i parametri N su un asse orizzontale. Traccia i token D su un secondo asse orizzontale. Traccia la perdita L in verticale. La perdita empirica incide una superficie di legge di potenza attraverso questo piano (N, D):
L(N, D) ≈ (Nc/N)^αN + (Dc/D)^αD + L∞
La superficie degrada verso il basso mentre N o D cresce. Le pendenze seguono leggi di potenza log-lineari (linee rette nel grafico log-log). L'asintoto L∞ rimane positivo — perdita irriducibile che il nostro modello non può ridurre oltre.
Crinale Ottimale di Calcolo
Fissa il bilancio di calcolo totale C ∝ N × D (parametri × token, approssimativamente). Affetta la nostra superficie lungo questo vincolo. L'affetta traccia una curva 2D attraverso una superficie 3D. Il fondo di questa curva = punto ottimale di calcolo.
Chinchilla (Hoffmann et al 2022) ha calcolato questo fondo analiticamente: D_opt ≈ 20 × N. La curva lungo il bilancio di calcolo = un crinale. Camminando lungo il crinale: calcolo uguale, perdita decrescente. Camminando fuori dal crinale (più parametri di 20× token, o meno): calcolo sprecato.
Lettura Geometrica di GPT-3 vs Chinchilla
GPT-3: 175B params, 300B token. Chinchilla-ottimale avrebbe voluto 175B × 20 = 3500B token. GPT-3 siede lontano dal crinale ottimale di calcolo nella nostra direzione pesante di parametri. Chinchilla stesso: 70B param addestrati su 1400B token. 1400 / 70 = 20 — esattamente sul crinale. Chinchilla ha battuto GPT-3 con meno della metà del suo conteggio di parametri sedendo sull'ottimale geometrico.
Muro di Dati come Piano Verticale
Web pubblico ~10¹³ token usabili. Questo traccia come un muro verticale a D = 10¹³ sul nostro piano parametri-token. Oltre questo muro, l'addestramento ottimale di calcolo richiede N ≤ D / 20 = 5 × 10¹¹ param. I muri oltre N = 5 × 10¹¹ o girano sotto-addestrati (fuori dal crinale) o richiedono dati sintetici / multimodali / RL per spingere il muro verso l'esterno.
Camminare il Crinale Ottimale di Calcolo
Siamo seduti alle coordinate GPT-3: N = 175B param, D = 300B token. Proxy di calcolo C = N × D = 5,25 × 10²² param-token.
Posteriore Beta che si Stringe in un Ago
Una Densità di Probabilità su [0, 1]
Beta(α, β) è una densità di probabilità sull'intervallo unitario [0, 1]. Variabile: ε = tasso di errore vero. Forma: α controlla la massa sul lato ε alto; β controlla la massa sul lato ε basso.
Beta(1, 1): uniforme — nessuna informazione, densità piatta attraverso [0, 1].
Beta(α, β) con α + β grande: picco concentrato a α / (α + β).
La larghezza del picco Beta si riduce come 1/√(α+β). Aggiungere 100 osservazioni alla nostra priorità stringe il picco di fattore √100 = 10. Aggiungere 10000 osservazioni stringe di √10000 = 100.
Lettura Geometrica di una Esecuzione di Audit
Inizio: Beta(1, 1) = rettangolo piatto su [0, 1]. Massima incertezza su ε.
Dopo 200 query con 8 falsificazioni: Beta(9, 193). Media = 9/202 ≈ 0,045. La densità è ora una gobba affilata centrata vicino a 0,045 con larghezza caratteristica σ ≈ 0,014.
Dopo 2000 query con 80 falsificazioni: Beta(81, 1921). Media ancora ≈ 0,045, ma larghezza σ ≈ 0,0046. La gobba è tre volte più affilata.
Dopo 200.000 query con 8.000 falsificazioni: Beta(8001, 192.001). Media ≈ 0,040, larghezza σ ≈ 0,0004. La gobba diventa un ago.
Convergenza Geometrica a una Massa Puntuale
Mentre n → ∞, il posteriore Beta collassa in un delta di Dirac al vero ε. Geometria: rettangolo → gobba larga → gobba stretta → ago → punto. Ogni query stringe la nostra distribuzione di 1/√n.
Perché Questo Batte i Legami Teorici PAC
I legami PAC teorici danno una stima ε STATICA basata sulla dimensione della classe di ipotesi. Il posteriore Beta dà una stima ε DINAMICA che si stringe con ogni osservazione, calibrata contro la tua distribuzione reale del mondo. Il legame teorico = una garanzia sotto ipotesi del caso peggiore. L'audit empirico = una misurazione della realtà vera.
Quante Query per Dimezzare l'Intervallo Credibile?
Attualmente siamo seduti a Beta(9, 193) dopo 200 query: media ε ≈ 0,045, σ ≈ 0,014. Vogliamo dimezzare la larghezza dell'intervallo credibile a σ ≈ 0,007.