Probably Approximately Correct
La Domanda di Valiant (1984)
Leslie Valiant pose una domanda apparentemente semplice: cosa significa per una macchina imparare? Non "può memorizzare?" Non "può prevedere perfettamente?" Piuttosto: può imparare in modo approssimativamente buono, con alta probabilità, da un campione finito, in tempo polinomiale?
Quella formulazione gli valse il Turing Award nel 2010 e fondò la computational learning theory.
Due Manopole
ε (epsilon) — tolleranza dell'errore. Approssimativamente corretto significa errore ≤ ε. ε più piccolo = apprendimento più rigoroso.
δ (delta) — parametro di confidenza. Probabilmente significa probabilità di successo ≥ 1 − δ. δ più piccolo = maggiore confidenza richiesta.
Definizione
Una classe di concetti C si dice PAC-learnable se esiste un algoritmo tale che, per qualsiasi distribuzione D e qualsiasi concetto target c ∈ C, dato m esempi campionati da D e etichettati secondo c, l’algoritmo restituisce un’ipotesi h che soddisfa:
P[error(h) ≤ ε] ≥ 1 − δ
con m polinomiale in 1/ε, 1/δ e nella dimensione del concetto.
In English: forniscigli abbastanza esempi e si avvicinerà abbastanza spesso, e 'abbastanza' non esplode esponenzialmente.
Complessità campionaria per spazi di ipotesi finiti
Se il nostro spazio di ipotesi H contiene un numero finito di ipotesi candidate, l'analisi classica fornisce:
m ≥ (1/ε)(ln|H| + ln(1/δ))
Leggi questa formula come un budget. Dimezzare ε raddoppia i campioni necessari. Dimezzare δ aggiunge una costante. Raddoppiare |H| aggiunge ln(2) campioni — crescita logaritmica, incredibilmente controllata.
Dimensionamento di un Campione per una Classe di Ipotesi
Un filtro antispam sceglie tra |H| = 1.000.000 insiemi di regole candidati. Vogliamo un errore ε ≤ 0,05 con confidenza 1 − δ = 0,99 (quindi δ = 0,01).
Shattering e Dimensione VC
Quando gli spazi delle ipotesi diventano infiniti
Il limite m ≥ (1/ε)(ln|H| + ln(1/δ)) non vale più quando |H| = ∞. La maggior parte delle classi di ipotesi utili (classificatori lineari in ℝᵈ, alberi decisionali, reti neurali) contiene un numero infinito di candidati. Vapnik e Chervonenkis risolsero il problema intorno al 1971 con una misura di complessità più ricca: la dimensione VC.
Shattering
Una classe di ipotesi H shatterizza un insieme di n punti se H è in grado di produrre tutte le possibili etichettature di quei n punti (tutte le 2ⁿ dicotomie). I classificatori lineari in ℝ² shatterizzano qualsiasi insieme di 3 punti in posizione generale: per ciascuna delle 8 possibili etichettature +/− di quei 3 punti, esiste una retta che li separa correttamente.
Ma i classificatori lineari in ℝ² non possono shatter 4 punti disposti in una configurazione XOR. Nessuna retta separa la coppia diagonale dalla coppia anti-diagonale.
VC Dimension
VC(H) = il più grande n tale che H shatter un insieme di n punti. Per i classificatori lineari 2D: VC = 3. Per i rettangoli allineati agli assi in 2D: VC = 4. Per le reti neurali con W pesi: VC ≤ O(W² log W) (Bartlett & Anthony 1999).
Sample Complexity con VC Dimension
Sostituisci ln|H| nel nostro bound PAC con la VC dimension d:
m = O((d/ε) log(1/ε) + (1/ε) log(1/δ))
La dimensione VC funge da nostra 'complessità effettiva' di una classe infinita. Una classe di ipotesi con bassa dimensione VC generalizza da pochi campioni; una classe con alta dimensione VC richiede più dati.
Dimensione VC come conteggio effettivo delle ipotesi
Una rete neurale ha W = 10⁹ pesi. Secondo il bound di Bartlett-Anthony, VC ≤ O(W² log W). Approssimiamo VC ≈ W² log₂ W.
Eliminando la Realizzabilità, Posteriori sulle Ipotesi
Due Generalizzazioni Importanti
Il PAC classico assume che il nostro concetto target c viva all'interno della nostra classe di ipotesi H. I dati reali portano rumore, etichette errate e concetti che la nostra classe non può rappresentare. Due estensioni gestiscono questo.
PAC Agnostico
Abbandoniamo l’assunzione che c ∈ H. Ora competiamo contro la nostra ipotesi migliore della classe h* = argmin_{h ∈ H} risk(h). La forma del bound cambia: invece di avvicinarci alla perfezione, ci avviciniamo al miglior risultato possibile all’interno di H.
Bound agnostico: P[risk(h) ≤ risk(h*) + ε] ≥ 1 − δ con complessità campionaria m = O(1/ε² × (VC(H) + log(1/δ))). Nota ε² al posto di ε al denominatore: l’apprendimento agnostico richiede più campioni per la stessa precisione.
PAC-Bayes (McAllester 1999)
Passiamo dalla scelta di una singola ipotesi alla scelta di una distribuzione su ipotesi. Partiamo da un prior P. Osserviamo i dati. Deriviamo il posterior Q. I bound PAC-Bayes riguardano il rischio atteso sotto Q:
𝔼_{h~Q}[risk(h)] ≤ 𝔼_{h~Q}[empirical_risk(h)] + √[(KL(Q‖P) + ln(2√n/δ)) / 2n]
KL(Q‖P) misura quanto la nostra posterior si è allontanata dalla nostra prior. Due interpretazioni:
1. Vista compressione. Una posterior vicina alla sua prior (piccolo KL) generalizza bene — piccolo costo informativo = piccolo gap di generalizzazione.
2. Vista bayesiana. Prior forte + debole aggiornamento dai dati = bound stretto; prior debole + forte aggiornamento dai dati = bound più lasco.
Perché PAC-Bayes è importante. I bound PAC-Bayes empirici (Catoni 2007, Dziugaite & Roy 2017) forniscono garanzie di generalizzazione numericamente significative per reti neurali reali, dove i bound PAC classici risultano vacui. Rimangono il nostro più stretto strumento teorico sulla generalizzazione in regime sovraparametrizzato.
Lettura di un limite PAC-Bayes
Supponiamo di addestrare una rete su n = 50.000 esempi etichettati. Dopo l'addestramento, la nostra distribuzione a posteriori Q sui pesi ha KL(Q‖P) = 200 nats rispetto a una prior gaussiana P. Il rischio empirico sotto Q è 0,10. Impostiamo δ = 0,05.
Sovraparametrizzazione e Double Descent
Il disastro previsto dal PAC classico
Il PAC classico prevede: più parametri che campioni = overfitting catastrofico. Impara perfettamente sui dati di training, generalizza in modo casuale sui dati di test. Il bound VC prevede memorizzazione senza apprendimento.
Le reti neurali moderne hanno comunemente da 10× a 1000× più parametri che campioni di training e generalizzano comunque. Questo non dovrebbe accadere secondo la teoria classica. Eppure accade.
La curva a U che ci hanno insegnato
Bias-varianza classica: all’aumentare della capacità del modello, l’errore di training diminuisce monotonicamente; l’errore di test prima scende (meno underfit), raggiunge un minimo, poi sale (overfit). Curva a U prevista dalla teoria VC.
Cosa succede davvero — Double Descent
Belkin et al. (2019) hanno mostrato che l’errore di test segue la classica curva a U fino alla soglia di interpolazione (capacità = #campioni), poi SCENDE NUOVAMENTE oltre tale soglia. Modelli massivamente sovraparametrizzati generalizzano meglio di modelli appena sufficientemente grandi.
Perché la PAC classica non coglie questo fenomeno
1. L’assunzione distribution-free è troppo pessimistica. I dati reali hanno struttura (bassa dimensionalità intrinseca, geometria di varietà). I bound PAC valgono per distribuzioni worst-case; le distribuzioni reali sfruttano la struttura che anche l’SGD sfrutta.
2. Regolarizzazione implicita. SGD su reti sovraparametrizzate trova soluzioni interpolanti a minima norma o minima complessità, non soluzioni arbitrarie. La teoria classica assume il minimizzatore del rischio empirico nel caso peggiore; gli algoritmi reali selezionano soluzioni benigne.
3. Definizione errata della classe di ipotesi. La classe di ipotesi effettiva esplorata da SGD è molto più piccola dello spazio nominale dei pesi. I posteriori PAC-Bayes la catturano; la dimensione VC no.
Il lavoro teorico moderno (Bartlett, Long, Lugosi, Tsigler 2020 sul benign overfitting; Nakkiran et al. 2020 sul double descent) sta costruendo una teoria della generalizzazione post-PAC che tiene conto del nostro regime sovraparametrizzato.
Diagnosi di un fallimento del PAC classico
Un team di ricerca addestra una rete da 1 miliardo di parametri su 100.000 esempi etichettati. Il PAC classico prevede bound vacui. Empiricamente, l’accuratezza sul test raggiunge il 95%.
Kaplan, Chinchilla e il Dimensionamento dell’Intelligenza Artificiale Generale Automatizzata
Dai Bound alle Leggi di Scaling Empiriche
Il PAC classico prevede teoricamente la dimensione del dataset e risulta vacuo. Le leggi di scaling empiriche prevedono la dimensione del dataset dall’osservazione e funzionano davvero. Hanno sostituito il PAC come strumento pratico di dimensionamento per modelli di grandi dimensioni.
Kaplan et al (2020)
La perdita segue una legge di potenza nei parametri N, nei token del dataset D e nel compute C:
L(N) ≈ (Nc/N)^αN L(D) ≈ (Dc/D)^αD L(C) ≈ (Cc/C)^αC
Raddoppiare i parametri riduce la perdita di un fattore moltiplicativo fisso. Raddoppiare i dati riduce la perdita di un altro fattore fisso. Questi esponenti (αN, αD, αC) misurano e predicono il comportamento frontier su molti ordini di grandezza.
Hoffmann et al 2022 (Chinchilla)
Chinchilla ha dimostrato che gli esponenti di Kaplan sovrastimavano i parametri rispetto ai dati. L’addestramento compute-optimal richiede circa 20 token per parametro:
D_opt ≈ 20 × N
GPT-3 (175B parametri) è stato addestrato su ~300B token — fortemente under-trained secondo la matematica di Chinchilla. Un modello compute-optimal da 175B parametri richiede ~3,5 trilioni di token.
Il Muro dei Dati
Scalare il numero di parametri richiede di scalare proporzionalmente anche il numero di token. Il web pubblico fornisce circa 10¹³ token utili. Un’ipotetica intelligenza generale automatizzata da 10¹⁵ parametri richiederebbe ~2×10¹⁶ token — tre ordini di grandezza oltre i dati web disponibili.
Questo è il nostro muro dei dati. Le scaling laws prevedono che raggiungeremo una carenza di corpus molto prima di una carenza di compute. Dati sintetici, corpora multimodali (video, audio, flussi sensoriali) e RL-from-environment mirano tutti a superarlo.
Il PAC classico ci diceva (erroneamente) che servivano 10²¹ campioni. Le scaling laws ci dicono (calibrate alla realtà) che ne servono 2×10¹⁶. Entrambi i numeri superano il testo disponibile. Il lavoro frontier di oggi si confronta con la chiusura di questo divario.
Stima del Corpus per un’Intelligenza Generale Automatizzata
Supponiamo che un laboratorio frontier proponga un modello da 10¹⁴ parametri e affermi che raggiungerà l’intelligenza generale automatizzata. Vogliamo dimensionare il suo corpus di addestramento secondo la regola di Chinchilla.
Dai Limiti Teorici alle Misure in Produzione
Smetti di Calcolare i Limiti; Inizia a Misurarli
I limiti PAC classici risultano vacui. I limiti PAC-Bayes risultano stretti sotto assunzioni difficili da verificare. Un’alternativa pratica: misura ε empiricamente sulla tua distribuzione reale e aggiornalo man mano che il sistema gira.
Idea 1 — Rendi la Coverage come PAC Empirico
Un target make coverage esegue N domande di validazione sul tuo sistema di query e misura due tassi:
- cache_hit_rate — frazione di domande per cui il sistema ha trovato una risposta nota
- i_dont_know_rate — frazione di domande per cui il sistema ha onestamente rinunciato
Ogni misurazione = un trial di Bernoulli. Dai conteggi osservati, calcola un intervallo di confidenza di Wilson sulla vera probabilità. Esempio: N = 1000 query, i_dont_know_rate osservato = 0.20 → 95% CI ≈ [0.177, 0.226]. Il limite superiore 0.226 funziona esattamente come un ε PAC a δ = 0.05, derivato da dati reali su una distribuzione reale anziché da un’analisi teorica worst-case.
Il vocabolario classico PAC si applica (ε, δ, confidenza). Meccanismo diverso (concentrazione binomiale vs. teoria VC). Risultato più stretto perché le distribuzioni reali contengono struttura sfruttabile.
Idea 2 — Audit PAC-Bayes tramite eventi di falsificazione
Tratta ogni falsificazione (risposta del sistema dimostrabilmente errata) come evidenza che aggiorna la posterior sulla vera probabilità di errore ε:
1. Prior: ε ~ Beta(α₀, β₀). Scegli un prior debole, ad es. Beta(1, 1) = uniforme.
2. Ogni query produce un esito di Bernoulli: falsificato (1) o mantenuto (0).
3. Posteriore dopo k falsificazioni in n query: Beta(α₀ + k, β₀ + n − k).
4. Media posteriore: (α₀ + k) / (α₀ + β₀ + n) → tasso empirico di falsificazione quando n → ∞.
5. Intervallo credibile al 95% su ε si stringe come 1/√n.
Cosa ci offre
- Stima reale di ε₀ da un deployment effettivo, non da una teoria worst-case
- Allarme anytime-valid: quando l’intervallo credibile posteriore supera la soglia del contratto, avvisa qualcuno
- Confidenza monotona: più query osservate → intervallo più stretto → garanzia più forte
Tecniche affini: conformal prediction con ricalibrazione online (Vovk), test del rapporto di probabilità sequenziale (Wald), PAC-Bayes online (Haddouche & Guedj 2022). Stessa famiglia, diversi strumenti matematici.
Calcolo di una Posterior Beta sulle Falsificazioni
Il nostro team esegue un audit di copertura su un sistema di query in produzione. Prior sul vero tasso di errore ε: Beta(1, 1) (uniforme). Dopo 200 query di validazione abbiamo osservato 8 falsificazioni.