Variabili aleatorie, convergenza, disuguaglianze

Ogni numero che il machine learning produce — un’accuratezza, un rischio empirico, una stima Monte Carlo — è una media. Questo capitolo costruisce gli strumenti per rispondere a una sola domanda, la più importante: di quanto quel numero può sbagliare. La risposta non è un’opinione né un’intuizione, è un teorema. Tre teoremi, anzi: la legge dei grandi numeri dice che la media converge al valore vero, il teorema del limite centrale dice che forma ha l’errore mentre converge, e le disuguaglianze di concentrazione danno una garanzia esplicita per ogni numero finito di campioni. Su quest’ultimo fatto poggia l’intero edificio delle garanzie di generalizzazione del ML.

Perché questo capitolo

Un classificatore segna il 91,3% di accuratezza su un test set. Un secondo classificatore segna il 90,8%. Il primo è migliore? La domanda sembra banale — 91,3 è più di 90,8 — e quasi sempre viene trattata come tale: si scrive un post, si cambia il modello in produzione. Ma se il test set ha cinquecento esempi, quel mezzo punto è quasi certamente rumore di campionamento, e sparirà alla valutazione successiva. Per saperlo non serve fortuna: serve un conto di tre righe. Quel conto è il contenuto di questo capitolo.

La Parte IV ha presentato la probabilità in versione operativa: distribuzioni, valore atteso, varianza, trattati come strumenti pronti all’uso. La Parte V ha costruito l’inferenza statistica sopra di essi. Questo capitolo scava sotto le fondamenta e risponde a due domande che fin qui erano rimaste implicite. La prima: cos’è davvero una variabile aleatoria, una volta che si smette di accontentarsi dell’intuizione? La seconda, e più importante per chi costruisce sistemi AI: perché le garanzie del machine learning — la promessa che un modello addestrato su dati visti funzionerà su dati mai visti — poggiano su un piccolo gruppo di teoremi che parlano di medie e di code di distribuzioni.

Il filo che tiene insieme tutto è semplice. Quasi ogni quantità che il machine learning calcola è una media empirica: l’accuratezza su un benchmark è la media di un indicatore “giusto/sbagliato”, il rischio empirico minimizzato durante il training è la media della loss sugli esempi, una stima Monte Carlo di un integrale è la media dei valori di una funzione su punti campionati. Una media empirica è un’approssimazione di un valore vero che non possiamo calcolare.

Le disuguaglianze di concentrazione sono lo strumento che trasforma quell’approssimazione in una garanzia: non “la media è vicina al valore vero”, ma “con n campioni, l’errore è sotto epsilon con probabilità almeno 1 meno delta”. Quella frase, resa precisa, è il cuore del PAC learning e di ogni bound di generalizzazione. Chi salta questo capitolo continua a riportare metriche senza barre di incertezza, cioè a fare metà del lavoro. Chi lo legge sa, di ogni numero che produce, quanto fidarsene.

Contesto

La probabilità ha avuto, per quasi tre secoli, un problema di fondamenta. Sapeva calcolare — Pascal, Fermat, Bernoulli, Laplace avevano risolto problemi profondi — ma non sapeva dire con precisione di che cosa stesse parlando. Cos’è un evento? Cos’è una probabilità? La risposta intuitiva (“la frazione di volte che una cosa accade”) funziona per i dadi e fallisce per gli oggetti continui: qual è la probabilità che un numero scelto a caso fra 0 e 1 sia esattamente un terzo? Zero. E allora come può un evento di probabilità zero accadere comunque?

La sistemazione definitiva arriva nel 1933, quando Andrey Kolmogorov (matematico sovietico, 1903-1987) pubblica Grundbegriffe der Wahrscheinlichkeitsrechnung (Concetti fondamentali del calcolo delle probabilità). L’idea di Kolmogorov è radicale per la sua economia: la probabilità non è una disciplina a sé, è un caso particolare della teoria della misura — la branca dell’analisi che studia come assegnare “dimensioni” (lunghezze, aree, volumi) agli insiemi.

Una probabilità è semplicemente una misura la cui massa totale vale 1. Un evento è un insieme misurabile. Una variabile aleatoria è una funzione misurabile. Tutto qui. Con tre assiomi, Kolmogorov dà alla probabilità lo stesso grado di rigore dell’analisi, e tutto il resto del capitolo lavora dentro questa cornice.

Le disuguaglianze che useremo sono più antiche dell’assiomatizzazione. Pafnuty Chebyshev (matematico russo, 1821-1894) e il suo allievo Andrey Markov (matematico russo, 1856-1922) lavoravano nella seconda metà dell’Ottocento alla scuola probabilistica di San Pietroburgo, da cui sarebbe poi uscita gran parte della probabilità moderna. La disuguaglianza di concentrazione che ci serve per il machine learning è invece recente: la dimostra Wassily Hoeffding (statistico, 1914-1991) nel 1963, in un articolo sul Journal of the American Statistical Association dedicato alle somme di variabili aleatorie limitate.

Il ponte verso l’informatica lo costruisce Leslie Valiant (informatico, nato nel 1949) nel 1984, con l’articolo A Theory of the Learnable sulle Communications of the ACM. Valiant prende le disuguaglianze di concentrazione e le usa per definire cosa significhi, formalmente, che una macchina “impara”: ne nasce il PAC learning, che chiude la sezione finale di questo capitolo.

Nel grafo della wiki, questo è il settimo capitolo della Parte VI e poggia su tre capitoli precedenti. Da Distribuzioni, valore atteso, varianza arrivano valore atteso e varianza, qui ripresi e formalizzati. Da Legge dei grandi numeri e teorema del limite centrale, nella Parte V, arrivano i due teoremi che qui rivisiteremo con più rigore — distinguendo la versione debole dalla forte, e collocandoli nella gerarchia dei modi di convergenza. Da Convessità, Jensen, minimi globali arriva la disuguaglianza di Jensen, parente stretta delle disuguaglianze di concentrazione: entrambe legano medie e funzioni. A valle stanno i capitoli di machine learning, dove rischio empirico, generalizzazione e complessità campionaria diventano oggetti operativi quotidiani.

L’ordine del capitolo segue una costruzione precisa. Prima si fissa cosa sia una variabile aleatoria, con i due angoli di intuizione — la procedura “esperimento più lettura” e la concentrazione come elisione del caso. Poi la meccanica: lo spazio di probabilità di Kolmogorov, la funzione di distribuzione, valore atteso e momenti, l’indipendenza, e le tre disuguaglianze di concentrazione in ordine di forza crescente. Poi i quattro modi in cui una successione di variabili può convergere, con la gerarchia che li lega. Poi la rilettura rigorosa di legge dei grandi numeri e limite centrale, ora che abbiamo il vocabolario per dire in che senso convergono. Poi gli esempi e le applicazioni. Infine le due sezioni che danno al capitolo il suo scopo: il ponte verso il machine learning — rischio empirico, generalizzazione, PAC learning — e la sezione “dove si rompe”, che è ampia perché i confini di questi strumenti contano quanto gli strumenti stessi.

Una nota di metodo prima di partire: nessuna parte del capitolo richiede la teoria della misura nella sua forma completa. Della sigma-algebra serve sapere perché esiste, non come si costruisce; delle disuguaglianze serve l’enunciato e l’intuizione, non ogni passaggio della prova. Il lettore con basi matematiche da liceo può seguire tutto: dove un argomento diventerebbe troppo tecnico, il capitolo lo nomina e rimanda, senza chiedere di inghiottirlo.

L’intuizione, primo angolo: la variabile aleatoria come “esperimento più lettura”

Prima di qualsiasi formula, fissiamo cosa sia una variabile aleatoria, perché il nome inganna. Non è una variabile nel senso della programmazione — una casella che contiene un valore — e non è un numero. È una procedura in due tempi.

Primo tempo: si esegue un esperimento il cui esito è incerto. Si lancia un dado, si estrae un individuo da una popolazione, un modello genera il prossimo token. Il risultato grezzo di questo esperimento — la faccia del dado, la persona estratta, il token — è la materia prima.

Secondo tempo: si legge un numero da quel risultato grezzo. Dal dado, leggi il punteggio. Dalla persona, leggi l’altezza in centimetri. Dal token generato, leggi 1 se è corretto e 0 se è sbagliato. La variabile aleatoria è esattamente questa lettura: una funzione che prende l’esito grezzo e restituisce un numero reale.

Questa distinzione fra l’esito grezzo e la sua lettura non è pedanteria. Spiega una cosa che altrimenti resterebbe oscura: perché la teoria ha bisogno di un oggetto chiamato sigma-algebra, e perché non è un tecnicismo da saltare.

Considera la collezione di tutte le domande a cui possiamo dare una risposta in termini di probabilità: “il punteggio è pari?”, “l’altezza supera 180 cm?”, “il token è corretto?”. Ciascuna di queste domande individua un sottoinsieme degli esiti possibili — un evento. Per un esperimento finito, come il dado, ogni sottoinsieme degli esiti è un evento legittimo, e a ciascuno sappiamo assegnare una probabilità senza problemi.

Il problema nasce con gli esperimenti continui: scegliere un numero reale a caso nell’intervallo da 0 a 1, misurare un tempo di attesa. Qui gli esiti possibili sono infiniti e non numerabili. Se si pretende di assegnare una probabilità a ogni sottoinsieme di quegli esiti, rispettando le proprietà naturali che una probabilità deve avere, si arriva a una contraddizione: esistono insiemi così patologici che nessuna assegnazione coerente è possibile (sono gli insiemi non misurabili, costruiti con strumenti logici come l’assioma della scelta).

La soluzione di Kolmogorov è chirurgica: non pretendere di misurare tutto. Si fissa in anticipo una famiglia di sottoinsiemi “buoni” — la sigma-algebra — e si assegna probabilità solo a quelli.

La sigma-algebra, in parole povere, è l’elenco delle domande lecite: gli eventi a cui la teoria si impegna a dare una risposta. Deve essere chiusa rispetto alle operazioni logiche di base — se “A” è una domanda lecita lo è anche “non A”, se “A” e “B” lo sono lo è anche “A oppure B”, anche per infinite domande messe in catena — perché altrimenti combinando domande lecite si finirebbe fuori dall’elenco.

La sigma-algebra è dunque la recinzione che tiene la probabilità dentro il terreno in cui è coerente. Per gli esperimenti finiti la recinzione contiene tutto e si può dimenticare; per gli esperimenti continui è ciò che impedisce alla teoria di crollare. Questo capitolo non ha bisogno della teoria della misura completa — niente integrale di Lebesgue, niente costruzioni — ma ha bisogno di sapere perché la sigma-algebra esiste: è il dominio di legittimità della probabilità, non un orpello.

L’intuizione, secondo angolo: la concentrazione, ovvero il caso che si annulla in massa

Una singola variabile aleatoria è imprevedibile. La media di tante variabili aleatorie indipendenti è quasi un numero fisso. Questo passaggio — da imprevedibile a quasi-deterministico, solo facendo una media — è il fenomeno della concentrazione, ed è il secondo angolo da cui guardare l’intero capitolo.

Immagina di stare in mezzo a una folla in cui ognuno spinge in una direzione a caso. Una sola persona può spostarti dove vuole. Ma se mille persone spingono in direzioni indipendenti e prive di una direzione privilegiata, le spinte si elidono: la risultante è quasi nulla. Non per magia, e non perché qualcuno coordini le spinte. È un fatto aritmetico. Gli scarti positivi e negativi, sommati in gran numero, tendono a cancellarsi; e la somma divisa per il numero di addendi — la media — si stringe attorno al suo valore atteso.

Un numero rende concreta l’immagine. Un singolo lancio di moneta ha deviazione standard $0{,}5$ — è massimamente imprevedibile, vale 0 o 1 con uguale probabilità. La media di cento lanci ha deviazione standard $0{,}5/\sqrt{100} = 0{,}05$, dieci volte più piccola. La media di diecimila lanci ha deviazione standard $0{,}005$. La singola moneta non è diventata meno casuale; è la media che si concentra, perché la dispersione di una media di $n$ variabili indipendenti si restringe come $1/\sqrt{n}$. Raddoppiare la precisione costa quattro volte i campioni: è un prezzo, ma è un prezzo finito e calcolabile.

Le disuguaglianze di concentrazione sono i teoremi che quantificano quanto si stringe. Sono tre, e formano una gerarchia: ognuna chiede più informazioni della precedente e in cambio dà un controllo più stretto.

La disuguaglianza di Markov chiede solo che la variabile sia non negativa e dà un controllo debole. La disuguaglianza di Chebyshev chiede anche la varianza e dà un controllo che migliora come 1 diviso il numero di campioni. La disuguaglianza di Hoeffding chiede che le variabili siano limitate e dà un controllo che migliora esponenzialmente con il numero di campioni. La differenza fra “polinomiale” ed “esponenziale” sembra una sfumatura tecnica e non lo è: è la differenza fra un benchmark che richiede milioni di esempi e uno che ne richiede qualche migliaio.

C’è un punto che distingue questo angolo dalla legge dei grandi numeri e dal teorema del limite centrale, e conviene fissarlo subito. Quei due teoremi sono enunciati asintotici: dicono cosa succede quando il numero di campioni tende all’infinito. Sono veri ma muti su una domanda pratica: con questi mille campioni che ho davvero in mano, quanto posso sbagliare? Le disuguaglianze di concentrazione rispondono proprio a questo. Valgono per ogni n finito. Sono garanzie, non promesse sul limite. Ed è per questo che il machine learning, che lavora sempre con campioni finiti, ne ha bisogno.

Figura in preparazione

fig-1: tre pannelli affiancati che mostrano la stessa nuvola di n campioni con n crescente (n=10, n=100, n=10000). In ciascun pannello, la distribuzione dei singoli campioni resta larga e identica, mentre un marcatore della media empirica si stringe progressivamente verso una linea verticale “valore atteso”. Titolo del frame: “La media si concentra anche se i campioni restano sparsi”

La meccanica

Lo spazio di probabilità

Tutto il formalismo poggia su una tripla di oggetti, scritta $(\Omega, \mathcal{F}, P)$.

Il primo, $\Omega$, è lo spazio campionario: l’insieme di tutti gli esiti possibili dell’esperimento. Per un dado, $\Omega$ ha sei elementi; per “scegliere un reale in $[0,1]$”, $\Omega$ è l’intervallo $[0,1]$.

Il secondo, $\mathcal{F}$, è la sigma-algebra: la famiglia dei sottoinsiemi di $\Omega$ che chiamiamo eventi — quelli a cui assegneremo una probabilità. Deve contenere $\Omega$ stesso, ed essere chiusa per complemento e per unione numerabile (se $A_1, A_2, \dots$ stanno in $\mathcal{F}$, anche la loro unione ci sta). In parole povere, $\mathcal{F}$ è l’elenco delle domande lecite, costruito in modo che combinando domande lecite si resti sempre fra le domande lecite.

Il terzo, $P$, è la misura di probabilità: una funzione che a ogni evento di $\mathcal{F}$ assegna un numero in $[0,1]$. Deve rispettare tre regole, gli assiomi di Kolmogorov (1933):

$P(A) \ge 0 \qquad P(\Omega) = 1 \qquad P\Big(\bigcup_i A_i\Big) = \sum_i P(A_i) \;\text{ per } A_i \text{ disgiunti}$

In parole povere: nessuna probabilità è negativa; l’evento certo ha probabilità 1; la probabilità di un’unione di eventi che non si sovrappongono è la somma delle probabilità, e questo vale anche per infiniti eventi (additività numerabile). Questi tre assiomi sono, letteralmente, gli assiomi della teoria della misura ristretti al caso in cui la massa totale vale 1.

La variabile aleatoria e la sua distribuzione

Una variabile aleatoria $X$ è una funzione da $\Omega$ ai numeri reali, con un requisito tecnico: deve essere misurabile. Misurabile significa che, per ogni intervallo $I$ di numeri reali, l’insieme degli esiti $\omega$ tali che $X(\omega)$ cade in $I$ è un evento di $\mathcal{F}$. In parole povere: ogni domanda della forma ”$X$ è finita dentro l’intervallo $I$?” deve essere una domanda lecita, una a cui $P$ sa rispondere. Senza misurabilità, $X$ potrebbe produrre domande fuori dal dominio di $P$, e l’enunciato "$P(X \in I)$" non avrebbe senso.

L’oggetto che riassume tutta l’informazione probabilistica su $X$ è la funzione di distribuzione cumulativa (CDF):

$F_X(x) = P(X \le x)$

In parole povere, $F_X(x)$ è la probabilità che la variabile non superi il valore $x$. La CDF esiste per ogni variabile aleatoria — discreta, continua o mista — e questa universalità è il motivo per cui è l’oggetto giusto su cui costruire la teoria. Ha tre proprietà che la caratterizzano: parte da 0 quando $x$ va verso meno infinito e arriva a 1 quando $x$ va verso più infinito (l’evento ”$X$ è un numero” è certo); non decresce mai, perché ampliando l’intervallo $(-\infty, x]$ si possono solo aggiungere esiti; è continua da destra.

Dove la CDF fa un salto verticale, c’è un valore che la variabile assume con probabilità positiva — l’altezza del salto è esattamente $P(X = x)$. Dove la CDF sale in modo liscio, la variabile è continua. La CDF, in un colpo solo, distingue la parte discreta dalla parte continua di qualsiasi variabile.

Quando $X$ assume valori isolati (il punteggio di un dado, il numero di teste), si descrive con la funzione di massa $p(x) = P(X = x)$. Quando $X$ assume valori su un continuo (un’altezza, un tempo), si descrive con la densità $f(x)$, definita in modo che la probabilità di cadere in un intervallo sia l’area sotto la curva:

$P(a \le X \le b) = \int_a^b f(x)\,dx$

Un avvertimento che il capitolo riprenderà nella sezione finale: la densità $f(x)$ non è una probabilità. Può tranquillamente superare 1 — una distribuzione uniforme su $[0, \tfrac{1}{2}]$ ha densità costante pari a 2. È una probabilità per unità di lunghezza. La probabilità vera è sempre l’area, mai l’altezza della curva.

Valore atteso e momenti

Il valore atteso di $X$, scritto $E[X]$ o $\mu$, è il baricentro della distribuzione:

$E[X] = \sum_x x\,p(x) \quad\text{(discreto)} \qquad E[X] = \int x\,f(x)\,dx \quad\text{(continuo)}$

In parole povere, è la media dei valori possibili, ciascuno pesato per la sua probabilità. Ha una proprietà che useremo continuamente, la linearità: $E[aX + bY] = a\,E[X] + b\,E[Y]$, e questo vale sempre, anche quando $X$ e $Y$ sono dipendenti.

I momenti misurano la forma della distribuzione. Il momento $k$-esimo è $E[X^k]$. I momenti centrati si calcolano sugli scarti dal valore atteso, $E[(X-\mu)^k]$. Il più importante è il momento centrato secondo, la varianza:

$\text{Var}(X) = E[(X-\mu)^2] = E[X^2] - \mu^2$

In parole povere, la varianza è la media del quadrato della distanza dal baricentro: misura quanto la distribuzione è dispersa. La sua radice è la deviazione standard $\sigma$, che ha la stessa unità di misura di $X$ — e per questo è il numero che di solito si riporta. Il momento centrato terzo, normalizzato, dà l’asimmetria (skewness): dice se la distribuzione pende più da un lato. Il quarto dà la curtosi: dice quanto pesano le code, cioè quanto sono probabili i valori estremi.

C’è infine un oggetto che ricorrerà di sfuggita: la funzione generatrice dei momenti $M(t) = E[e^{tX}]$, che — quando esiste — codifica tutti i momenti in un colpo solo. Non la useremo direttamente, ma vale la pena sapere che è lei a stare dietro la dimostrazione della disuguaglianza di Hoeffding: è applicando Markov a $e^{tX}$, e poi ottimizzando su $t$, che si ottiene la coda esponenziale.

Vale la pena vedere questi oggetti su un caso concreto. La distribuzione di Bernoulli di parametro $p$ — vale 1 con probabilità $p$, 0 con probabilità $1-p$ — ha valore atteso $E[X] = p$, perché la media pesata è $1 \cdot p + 0 \cdot (1-p) = p$. La sua varianza è $p(1-p)$: massima quando $p = \tfrac{1}{2}$ (incertezza massima, valore $0{,}25$) e nulla agli estremi $p = 0$ e $p = 1$ (nessuna incertezza, l’esito è certo).

È la distribuzione che modella ogni “successo/fallimento”: una predizione corretta o sbagliata, un click o un non-click, un token accettato o rifiutato. Tornerà in ogni esempio del capitolo, perché l’accuratezza di un modello è la media di tante Bernoulli.

Indipendenza e varianza di una somma

C’è un fatto, breve da enunciare ma decisivo, su cui poggiano tutti i teoremi del capitolo. Due variabili $X$ e $Y$ sono indipendenti se sapere il valore di una non cambia nulla sulla distribuzione dell’altra — formalmente, se la probabilità congiunta si fattorizza, $P(X \in A,\, Y \in B) = P(X \in A)\,P(Y \in B)$ per ogni coppia di intervalli. L’indipendenza è un’ipotesi forte: dice che non c’è alcun legame, di nessun tipo, fra le due variabili.

Da essa discende la proprietà che fa funzionare la concentrazione. Mentre il valore atteso è lineare sempre, la varianza è additiva solo per variabili indipendenti:

$\text{Var}(X_1 + \dots + X_n) = \text{Var}(X_1) + \dots + \text{Var}(X_n) \quad\text{se indipendenti}$

In parole povere: sommando variabili indipendenti, le varianze si sommano. Per $n$ variabili iid di varianza $\sigma^2$, la somma ha varianza $n\sigma^2$, e la media — la somma divisa per $n$ — ha varianza $n\sigma^2/n^2 = \sigma^2/n$. È esattamente questo $\sigma^2/n$ che tende a zero: la dispersione della media empirica si restringe perché le varianze si sommano linearmente mentre la divisione per $n$ le scala quadraticamente.

Quando le variabili non sono indipendenti compare un termine in più, la covarianza, che misura quanto due variabili tendono a muoversi insieme. Se le variabili sono positivamente correlate la varianza della somma è maggiore della somma delle varianze, e la media si concentra più lentamente. È il motivo tecnico per cui l’ipotesi di indipendenza non è un dettaglio: senza di essa, le barre di confidenza calcolate con le formule di questo capitolo sono sbagliate per difetto.

Le tre disuguaglianze di concentrazione

Eccoci allo strumento centrale. Tre disuguaglianze, in ordine di forza crescente.

Markov. Se $X$ è non negativa (non assume mai valori sotto zero) e $a > 0$:

$P(X \ge a) \le \frac{E[X]}{a}$

In parole povere: se la media è piccola, la variabile non può stare spesso lontano da zero.

La dimostrazione è di una riga. Si parte dalla disuguaglianza puntuale $a \cdot \mathbb{1}[X \ge a] \le X$ — dove $\mathbb{1}[\cdot]$ vale 1 quando la condizione è vera e 0 altrimenti — vera perché quando $X \ge a$ il lato sinistro vale $a$ e $X$ è almeno $a$, mentre quando $X < a$ il lato sinistro vale 0 e $X$ è non negativa. Prendendo il valore atteso di entrambi i lati e usando la linearità: $a\,P(X \ge a) \le E[X]$, da cui la tesi. Markov chiede pochissimo — solo non-negatività — e in cambio dà un controllo debole.

Chebyshev. Per qualsiasi variabile $X$ con varianza finita e $a > 0$:

$P(|X - \mu| \ge a) \le \frac{\text{Var}(X)}{a^2}$

In parole povere: la probabilità che $X$ si discosti dalla sua media di almeno $a$ è controllata dalla varianza divisa per $a^2$. Si ottiene applicando Markov alla variabile non negativa $(X-\mu)^2$ con soglia $a^2$: $P(|X-\mu| \ge a) = P((X-\mu)^2 \ge a^2) \le E[(X-\mu)^2]/a^2 = \text{Var}(X)/a^2$. Chebyshev usa un’informazione in più rispetto a Markov — la varianza — e per questo è più forte.

Applichiamola subito alla media, perché è lì che diventa potente. Siano $X_1, \dots, X_n$ variabili indipendenti e identicamente distribuite (iid), con media $\mu$ e varianza $\sigma^2$. La loro media campionaria $\bar{X}_n = \tfrac{1}{n}\sum_i X_i$ ha varianza $\sigma^2/n$ — perché la varianza di una somma di variabili indipendenti è la somma delle varianze, e dividere per $n$ scala la varianza per $1/n^2$. Chebyshev dà allora:

$P(|\bar{X}_n - \mu| \ge \epsilon) \le \frac{\sigma^2}{n\,\epsilon^2}$

Questo è già un risultato notevole: una dimostrazione in due righe del fatto che la media converge. Il lato destro tende a zero quando $n$ cresce. Ma cala solo come $1/n$, e questo si rivelerà lento.

Hoeffding (Wassily Hoeffding, 1963). Se $X_1, \dots, X_n$ sono indipendenti e ciascuna è limitata nell’intervallo $[a_i, b_i]$, allora per la somma $S_n = \sum_i X_i$ e ogni $t > 0$:

$P\big(S_n - E[S_n] \ge t\big) \le \exp\!\left(\frac{-2t^2}{\sum_i (b_i - a_i)^2}\right)$

Per la media di $n$ variabili iid tutte confinate nello stesso intervallo $[a, b]$, la forma più usata è quella a due code:

$P\big(|\bar{X}_n - \mu| \ge \epsilon\big) \le 2\exp\!\left(\frac{-2n\,\epsilon^2}{(b-a)^2}\right)$

In parole povere: la probabilità che la media empirica si discosti dal valore vero di almeno $\epsilon$ cala esponenzialmente con il numero di campioni. La coda è sub-gaussiana — decade veloce come quella di una curva a campana.

Il prezzo di questa potenza è l’ipotesi di limitatezza: ogni variabile deve stare in un intervallo noto. È un’ipotesi che il machine learning soddisfa spesso senza fatica — un indicatore di correttezza vive in $[0,1]$, una loss troncata anche — ma che cade su quantità non limitate, e lì Hoeffding va sostituito. La dimostrazione non viene svolta qui per esteso: passa per la funzione generatrice dei momenti e il metodo di Chernoff, troppo tecnici per questa sede. L’enunciato, però, è tutto ciò che serve per usarlo.

La differenza pratica fra Chebyshev e Hoeffding si vede invertendo le formule. Vogliamo garantire errore $\epsilon$ con confidenza $1 - \delta$, cioè vogliamo che il lato destro valga $\delta$. Con Chebyshev serve $n$ proporzionale a $1/(\epsilon^2\,\delta)$. Con Hoeffding serve $n$ proporzionale a $\log(1/\delta)/\epsilon^2$.

La dipendenza dalla confidenza passa così da $1/\delta$ a $\log(1/\delta)$: per $\delta = 0{,}01$, da un fattore 100 a un fattore circa 4,6. È la differenza fra una garanzia costosa e una a buon mercato — e il motivo per cui, ogni volta che le variabili sono limitate, Hoeffding è la scelta da preferire a Chebyshev.

Figura in preparazione

fig-2: grafico con sull’asse orizzontale il numero di campioni n e sull’asse verticale la probabilità di sbagliare di almeno epsilon, in scala logaritmica. Tre curve: “Markov” che cala lentissima, “Chebyshev” che cala come 1/n (retta in scala log-log), “Hoeffding” che cala esponenziale (retta ripida in scala semi-log). Una banda evidenzia la regione “garanzia raggiunta”. Titolo del frame: “Tre disuguaglianze, tre velocità di garanzia”

I quattro modi di convergenza

Una successione di variabili aleatorie $X_1, X_2, \dots$ può “tendere” a una variabile $X$ — o a una costante — in sensi diversi. Non è pedanteria: i tre teoremi del capitolo (legge debole, legge forte, limite centrale) sono enunciati di tre modi diversi, e confonderli è confondere ciò che ciascun teorema garantisce. I modi principali sono quattro.

Convergenza quasi certa (q.c.). $X_n \to X$ quasi certamente se l’insieme degli esiti $\omega$ per cui la successione di numeri $X_n(\omega)$ converge a $X(\omega)$ nel senso ordinario dell’analisi ha probabilità 1. In parole povere: per quasi ogni storia possibile dell’esperimento, la traiettoria numerica converge davvero. È il modo più forte. La legge forte dei grandi numeri è di questo tipo.

Convergenza in $L^2$ (in media quadratica). $X_n \to X$ in $L^2$ se $E[(X_n - X)^2] \to 0$. In parole povere: l’errore quadratico medio fra $X_n$ e $X$ va a zero. Questo modo è di casa nel machine learning, perché la loss MSE (errore quadratico medio) è esattamente una distanza $L^2$: dire che un predittore converge in $L^2$ è dire che la sua MSE svanisce.

Convergenza in probabilità. $X_n \to X$ in probabilità se, per ogni soglia $\epsilon > 0$, si ha $P(|X_n - X| > \epsilon) \to 0$. In parole povere: fissata una qualunque tolleranza, la probabilità di trovarsi fuori da quella tolleranza svanisce. Attenzione alla differenza con la convergenza quasi certa: qui non si chiede che le singole traiettorie convergano, solo che a ogni $n$ grande sia improbabile stare lontani. La legge debole dei grandi numeri è di questo tipo.

Convergenza in distribuzione (o in legge). $X_n \to X$ in distribuzione se $F_{X_n}(x) \to F_X(x)$ in ogni punto in cui $F_X$ è continua. In parole povere: converge la forma della distribuzione, non i valori delle variabili. È il modo più debole — così debole che due successioni che non si avvicinano mai come numeri possono comunque convergere l’una all’altra in distribuzione, se hanno la stessa legge. Il teorema del limite centrale è di questo tipo.

Le relazioni fra i quattro modi formano una gerarchia, e vale la pena fissarle perché sono fonte continua di errori.

• La convergenza quasi certa implica la convergenza in probabilità. Se quasi ogni traiettoria converge, allora a ogni $n$ grande è improbabile stare lontani.
• La convergenza in $L^2$ implica la convergenza in probabilità. La dimostrazione è una sola riga di Chebyshev: $P(|X_n - X| > \epsilon) \le E[(X_n - X)^2]/\epsilon^2$, e se il numeratore va a zero, va a zero anche il lato sinistro.
• La convergenza in probabilità implica la convergenza in distribuzione.
• Quindi quasi certa e $L^2$ sono entrambe più forti di “in probabilità”, che è più forte di “in distribuzione”.

Due avvertenze chiudono il quadro. La prima: quasi certa e $L^2$ non sono confrontabili fra loro — nessuna delle due implica l’altra in generale (una successione può convergere quasi certamente ma avere errore quadratico che non svanisce, e viceversa).

La seconda: le frecce non si invertono. La convergenza in distribuzione non implica quella in probabilità — controesempio: se $X_n$ ha distribuzione simmetrica, anche $-X_n$ ha la stessa distribuzione, quindi $X_n$ converge in distribuzione a $-X_n$, ma $|X_n - (-X_n)| = 2|X_n|$ non svanisce affatto. La convergenza in probabilità non implica quella quasi certa. C’è un’unica eccezione utile: se il limite è una costante, allora convergere in distribuzione equivale a convergere in probabilità.

Vale la pena vedere da vicino perché “in probabilità” non implica “quasi certa”, perché è l’implicazione mancante più sottile. Si costruisce una successione di variabili indicatrici associate a intervalli che scorrono e si restringono dentro $[0,1]$: il primo copre tutto $[0,1]$, i due successivi le metà $[0,\tfrac{1}{2}]$ e $[\tfrac{1}{2},1]$, i tre dopo i terzi, e così via. Ogni $X_n$ vale 1 se un punto fissato cade nell’intervallo di turno, 0 altrimenti.

La probabilità che $X_n$ valga 1 è la lunghezza dell’intervallo, che tende a zero: quindi $X_n \to 0$ in probabilità. Ma per qualunque punto fissato, gli intervalli che lo contengono ritornano all’infinito — la successione $X_n$ su quel punto continua a fare 1, 0, 0, 1, 0, … per sempre, senza convergere. Nessuna singola traiettoria converge, eppure la successione converge in probabilità. È la differenza esatta fra “a ogni $n$ grande è improbabile sbagliare” e “quasi ogni storia, prima o poi, smette di sbagliare”.

Figura in preparazione

fig-3: diagramma a frecce con quattro nodi etichettati “quasi certa”, “in L2”, “in probabilita”, “in distribuzione”. Frecce che vanno da “quasi certa” e da “in L2” verso “in probabilita”, e da “in probabilita” verso “in distribuzione”. I nodi “quasi certa” e “in L2” sono allo stesso livello, collegati da una freccia barrata “non si implicano”. Ogni freccia etichettata con il teorema corrispondente: la legge forte tocca “quasi certa”, la legge debole “in probabilita”, il CLT “in distribuzione”. Titolo del frame: “La gerarchia dei modi di convergenza”

Legge dei grandi numeri e limite centrale, con più rigore

Il capitolo Legge dei grandi numeri e teorema del limite centrale della Parte V ha presentato i due teoremi con taglio statistico: la media converge al valore vero, l’errore ha forma gaussiana. Ora che abbiamo i modi di convergenza, possiamo dire la stessa cosa con la precisione che merita — e aggiungere il livello che lì mancava.

La legge debole dei grandi numeri afferma: se $X_1, \dots, X_n$ sono iid con media $\mu$ finita, la media campionaria $\bar{X}_n$ converge a $\mu$ in probabilità. Se esiste anche la varianza, la dimostrazione è la riga di Chebyshev vista sopra. Aleksandr Khinchin dimostrò nel 1929 che basta l’esistenza della media, senza richiedere la varianza.

La legge forte dei grandi numeri afferma: sotto la stessa ipotesi — media finita — la media campionaria converge a $\mu$ quasi certamente. Il risultato è di Andrey Kolmogorov, intorno al 1930-1933. È un enunciato più forte, e ora sappiamo dire esattamente in che senso: non solo a ogni $n$ grande è improbabile stare lontani da $\mu$ (legge debole), ma quasi ogni singola traiettoria della media converge davvero a $\mu$, nel senso ordinario dei limiti.

Il teorema del limite centrale (nella forma classica di Lindeberg-Lévy) afferma: se $X_1, \dots, X_n$ sono iid con media $\mu$ e varianza $\sigma^2$ finita e positiva, allora la quantità standardizzata

$\frac{\sqrt{n}\,(\bar{X}_n - \mu)}{\sigma}$

converge in distribuzione a una Normale standard $N(0,1)$. In parole povere: per $n$ grande, la media empirica si comporta come $\mu$ più un rumore gaussiano di deviazione standard $\sigma/\sqrt{n}$. Il CLT non dice dove arriva la media — quello lo dice la legge dei grandi numeri — ma che forma ha la fluttuazione attorno al punto d’arrivo.

Conviene tenere in fila le tre affermazioni, perché rispondono a tre domande diverse. La legge dei grandi numeri dice dove arriva la media: al valore vero $\mu$. Il teorema del limite centrale dice che forma ha l’errore mentre la media ci arriva: gaussiana, di ampiezza $\sigma/\sqrt{n}$. Le disuguaglianze di concentrazione danno una terza cosa, che né l’uno né l’altro teorema offrono: un bound valido per ogni $n$ finito.

Legge dei grandi numeri e limite centrale sono enunciati sul comportamento limite; Hoeffding è un enunciato su questi mille campioni che ho in mano. Per chi costruisce sistemi — che ha sempre un campione finito — è la differenza fra una rassicurazione filosofica e un numero su cui decidere.

Il limite centrale e Hoeffding meritano un confronto diretto, perché entrambi producono barre di confidenza ma in modi diversi. Il limite centrale dà la barra più stretta — è asintoticamente esatto, sfrutta la forma gaussiana, e per la media di variabili in $[0,1]$ produce un intervallo a due deviazioni standard largo circa $2\sigma/\sqrt{n}$. Ma è un risultato approssimato: vale “per $n$ grande”, e quanto grande dipenda dalla distribuzione di partenza il teorema non lo dice — distribuzioni molto asimmetriche convergono lentamente, e con campioni piccoli la barra del limite centrale può essere ottimistica.

Hoeffding dà una barra un po’ più larga ma è una garanzia esatta: vale per ogni $n$, senza condizioni asintotiche, senza assunzioni sulla forma. La scelta pratica è semplice: quando serve una garanzia che regga senza eccezioni — un contratto, un bound di sicurezza, un benchmark da difendere — si usa Hoeffding; quando basta una stima realistica dell’incertezza e $n$ è abbondante, il limite centrale dà l’intervallo più informativo.

C’è infine un fenomeno che il limite centrale spiega e che vale la pena nominare: l’ubiquità della curva gaussiana nei dati reali. Tante grandezze misurabili — errori di misura, rumore di fondo, scarti di produzione — sono di fatto la somma di moltissime piccole cause indipendenti, ciascuna trascurabile da sola.

Il limite centrale dice che la somma di molte cause indipendenti tende a una gaussiana qualunque sia la distribuzione delle singole cause. La campana non compare perché la natura “ama” quella forma, ma perché è la forma a cui converge ogni somma di rumore indipendente. È lo stesso meccanismo per cui la media empirica di un test set, che è una somma di tanti contributi indipendenti, ha incertezza gaussiana.

Esempi

Esempio numerico: la moneta, Chebyshev contro Hoeffding

Lanciamo una moneta equa mille volte e guardiamo la frazione di teste. Ogni singolo lancio è una variabile di Bernoulli: vale 1 con probabilità $0{,}5$ e 0 con probabilità $0{,}5$. La sua media è $\mu = 0{,}5$ e la sua varianza è $\sigma^2 = 0{,}25$. La frazione di teste su mille lanci è la media campionaria $\bar{X}_{1000}$.

Vogliamo controllare la probabilità che la frazione si discosti dal valore vero $0{,}5$ di almeno $\epsilon = 0{,}05$. Con Chebyshev:

$P(|\bar{X}_{1000} - 0{,}5| \ge 0{,}05) \le \frac{0{,}25}{1000 \cdot 0{,}05^2} = \frac{0{,}25}{2{,}5} = 0{,}1$

Chebyshev garantisce: lo scarto supera $0{,}05$ in al più il 10% dei casi. Con Hoeffding, le variabili sono confinate in $[0,1]$, quindi $b - a = 1$:

$P(|\bar{X}_{1000} - 0{,}5| \ge 0{,}05) \le 2\exp\!\big(-2 \cdot 1000 \cdot 0{,}05^2\big) = 2\,e^{-5} \approx 0{,}0135$

Hoeffding garantisce circa l’$1{,}3\%$: una stima quasi otto volte più stretta, a parità di campioni.

Il divario esplode se chiediamo una confidenza alta. Per garantire errore $0{,}05$ con confidenza del 99% — cioè $\delta = 0{,}01$ — Chebyshev richiede $n$ dell’ordine di centomila lanci; Hoeffding ne richiede circa 1060. Due ordini di grandezza di differenza, e dipendono solo da quale teorema si decide di usare: gli stessi dati, lo stesso esperimento, una garanzia cento volte più economica.

Esempio in codice: la convergenza di Monte Carlo

Stimiamo $\pi$ con un metodo Monte Carlo. Si campionano punti uniformi nel quadrato $[0,1] \times [0,1]$; la frazione di punti che cade nel quarto di cerchio di raggio 1 approssima $\pi/4$, perché quel quarto di cerchio ha area $\pi/4$.

def stima_pi(n):
    dentro = 0
    for _ in range(n):
        x, y = random(), random()
        if x*x + y*y <= 1.0:        # punto dentro il quarto di cerchio
            dentro += 1
    frazione = dentro / n           # media empirica di un indicatore in [0,1]
    return 4.0 * frazione

# barra di Hoeffding a confidenza 1 - delta sulla frazione:
#   errore <= sqrt( ln(2/delta) / (2 n) )
# la barra sulla stima di pi vale 4 volte quella sulla frazione

L’oggetto chiave è frazione: è la media empirica di un indicatore — vale 1 se il punto è nel cerchio, 0 altrimenti — quindi una variabile limitata in $[0,1]$. La legge dei grandi numeri garantisce che frazione converge a $\pi/4$. Il teorema del limite centrale dice che l’errore cala come $1/\sqrt{n}$: per guadagnare una cifra decimale servono cento volte più campioni.

Hoeffding dà la barra esplicita: con $n = 10^6$ e $\delta = 0{,}05$, l’errore sulla frazione è sotto $\sqrt{\ln(40)/2\cdot 10^6} \approx 0{,}0014$, e quindi l’errore su $\pi$ è sotto circa $0{,}0054$. C’è un punto che vale più del singolo conto: il tasso $1/\sqrt{n}$ non dipende dalla dimensione dello spazio in cui si campiona. Una quadratura deterministica, che divide lo spazio in una griglia, vede il numero di celle esplodere con la dimensione; Monte Carlo no. È la ragione per cui Monte Carlo è lo strumento di elezione quando le dimensioni sono molte — e nelle applicazioni di machine learning lo sono quasi sempre.

Esempio reale: i due modelli sul test set

Torniamo al confronto da cui è partito il capitolo. Il modello A segna $91{,}3\%$ di accuratezza, il modello B segna $90{,}8\%$, entrambi su un test set di 500 esempi. L’accuratezza è la media di un indicatore “predizione corretta” in $[0,1]$: Hoeffding si applica.

La larghezza della barra di confidenza al 95% per ciascuna accuratezza è $\sqrt{\ln(2/0{,}05)/(2 \cdot 500)} = \sqrt{\ln(40)/1000} \approx 0{,}061$. Ogni accuratezza misurata è dunque circondata da un’incertezza di circa $\pm 6{,}1$ punti percentuali. La differenza osservata fra A e B è di $0{,}5$ punti: è ampiamente dentro il rumore.

Hoeffding dice, con un conto di una riga, che non c’è alcuna evidenza che A sia migliore di B. Per distinguere in modo affidabile una differenza di mezzo punto servirebbe un test set di decine di migliaia di esempi. Questa è la concentrazione al lavoro: trasforma “il primo numero è più grande” in “il primo numero è più grande al di là del rumore”, che è una cosa del tutto diversa — ed è la sola delle due che giustifica un cambio di modello in produzione.

Esempio illustrativo: i quattro modi su un unico oggetto

Un solo esempio mostra tutti e quattro i modi di convergenza. Sia $\bar{X}_n$ la media di $n$ variabili di Bernoulli iid di parametro $p$ — la frazione di successi su $n$ prove.

Converge a $p$ quasi certamente: la legge forte dei grandi numeri lo garantisce, perché la media di Bernoulli è finita. Converge a $p$ in $L^2$: l’errore quadratico medio è la varianza della media, $p(1-p)/n$, che tende a zero. Converge a $p$ in probabilità: è la conseguenza delle due precedenti, ciascuna delle quali implica la convergenza in probabilità.

E infine la quantità standardizzata $\sqrt{n}\,(\bar{X}_n - p)$, divisa per $\sqrt{p(1-p)}$, converge in distribuzione a una Normale standard: è il teorema del limite centrale. Lo stesso oggetto — la frazione di teste — illustra in un colpo solo i quattro sensi in cui una successione aleatoria può convergere.

Applicazioni pratiche

Il filo di tutte le applicazioni è uno solo: nel machine learning ogni numero importante è una media empirica, e le disuguaglianze di concentrazione ne governano l’affidabilità.

Dimensionare un test set o un benchmark. La domanda “quanti esempi mi servono per stimare l’accuratezza con precisione $\epsilon$ e confidenza $1-\delta$?” ha una risposta diretta: invertendo Hoeffding, $n \ge \ln(2/\delta)/(2\epsilon^2)$. Per $\epsilon = 0{,}02$ e $\delta = 0{,}05$ servono circa 4600 esempi. È un calcolo da fare prima di costruire un benchmark, non dopo.

Barre di confidenza sulle metriche. Ogni accuratezza, F1, win rate riportato senza un intervallo di incertezza è mezza misura. Hoeffding e il teorema del limite centrale danno l’intervallo. Un modello al $91{,}3\% \pm 6\%$ e un modello al $90{,}8\% \pm 6\%$ sono indistinguibili; senza la barra, sembrano ordinabili.

Garanzie di generalizzazione e PAC learning. È l’applicazione che chiude il capitolo: le disuguaglianze di concentrazione sono il motore dei bound che legano la performance sul training set alla performance vera.

Monte Carlo per stima e inferenza. Stimare un valore atteso o un integrale campionando e mediando — la tecnica dietro l’inferenza bayesiana approssimata, la stima di metriche complesse, il rendering grafico — produce sempre una media empirica. Il tasso $1/\sqrt{n}$ indipendente dalla dimensione spiega perché Monte Carlo è lo strumento di elezione in spazi ad alta dimensione.

Bandit e reinforcement learning. Gli algoritmi della famiglia UCB (Upper Confidence Bound) per il problema dei multi-armed bandit costruiscono, attorno alla ricompensa media stimata di ciascuna opzione, un intervallo di confidenza ricavato proprio da Hoeffding. L’esplorazione è guidata dalla larghezza di quegli intervalli: si prova l’opzione il cui intervallo arriva più in alto. La concentrazione non è qui un controllo a posteriori, è il principio attivo dell’algoritmo.

A/B testing e early stopping. Decidere quando interrompere un esperimento e dichiarare un vincitore senza gonfiare i falsi positivi richiede bound di concentrazione in versione “anytime” — validi a ogni istante d’arresto, non solo a un $n$ fissato in anticipo. Sono un’estensione diretta degli strumenti di questo capitolo.

Sicurezza delle stime in produzione. Un sistema che valuta sé stesso a runtime — un classificatore che stima la propria accuratezza su un flusso di dati, un agente che misura il proprio tasso di successo sui task — produce continuamente medie empiriche. Le disuguaglianze di concentrazione dicono quando una di quelle medie è scesa abbastanza, e abbastanza a lungo, da poter dichiarare con confidenza che qualcosa si è degradato. Senza un bound esplicito, distinguere un calo reale di prestazioni da una fluttuazione di campionamento diventa una scommessa, e i sistemi che reagiscono al rumore sono fragili quanto quelli che ignorano i segnali veri.

Il ponte verso il machine learning: rischio empirico, generalizzazione, PAC learning

Questa sezione è il motivo per cui il capitolo esiste nella forma che ha. Mette insieme tutti gli strumenti — variabile aleatoria, media empirica, Hoeffding, union bound — per rispondere alla domanda fondamentale del machine learning: perché un modello che funziona sui dati visti dovrebbe funzionare su dati mai visti?

Si comincia da una distinzione. Il rischio vero $R(h)$ di un modello $h$ è il valore atteso della sua loss sulla distribuzione vera dei dati — un integrale rispetto a una distribuzione che non conosciamo e non sapremo mai calcolare. Il rischio empirico $R_{\text{emp}}(h)$ è la media della loss sugli esempi che abbiamo: $R_{\text{emp}}(h) = \tfrac{1}{n}\sum_i \text{loss}(h, x_i)$. Il rischio empirico è una media campionaria. Il rischio vero è il valore atteso che quella media sta cercando di stimare.

La legge dei grandi numeri garantisce che $R_{\text{emp}}(h) \to R(h)$: con abbastanza esempi, il rischio empirico converge al rischio vero. Ma la legge dei grandi numeri è asintotica — non dice quanti esempi. Qui entra Hoeffding. Se la loss è limitata, diciamo in $[0,1]$, allora per una singola ipotesi $h$ fissata in anticipo:

$P\big(|R_{\text{emp}}(h) - R(h)| > \epsilon\big) \le 2\exp(-2n\epsilon^2)$

Con probabilità almeno $1 - 2\exp(-2n\epsilon^2)$, il rischio empirico dista dal rischio vero meno di $\epsilon$. È una garanzia esplicita, valida per ogni $n$.

C’è però un difetto, e individuarlo è il passo concettuale più importante della sezione. Quella garanzia vale per un’ipotesi $h$ scelta prima di vedere i dati. Ma un algoritmo di apprendimento non fa così: guarda i dati e seleziona l’ipotesi che minimizza il rischio empirico, scegliendola fra molte. L’ipotesi finale dipende dai dati.

Applicare Hoeffding come se $h$ fosse fissata in anticipo dà una garanzia ottimistica e falsa. È come misurare la fortuna del vincitore di una lotteria e concludere che chiunque è fortunato: il vincitore è stato selezionato proprio perché era quello con l’esito migliore, e misurare lui non dice nulla sul giocatore medio.

La correzione è lo union bound: la probabilità che almeno una fra più ipotesi abbia uno scarto grande è al più la somma delle singole probabilità. Per una classe finita $H$ di ipotesi:

$P\big(\exists\,h \in H : |R_{\text{emp}}(h) - R(h)| > \epsilon\big) \le 2|H|\exp(-2n\epsilon^2)$

dove $|H|$ è il numero di ipotesi nella classe. Imponendo che questo lato destro sia al più $\delta$ e risolvendo per $n$, si ottiene la complessità campionaria:

$n \ge \frac{1}{2\epsilon^2}\Big(\ln|H| + \ln\frac{2}{\delta}\Big)$

In parole povere: per garantire che il modello selezionato generalizzi entro $\epsilon$ con confidenza $1-\delta$, servono almeno tanti esempi quanti dice questa formula.

E la formula racconta una storia precisa. Il numero di esempi necessari cresce con $\ln|H|$ — più la classe di modelli è ricca, più dati servono; cresce con $1/\epsilon^2$ — chiedere il doppio della precisione costa il quadruplo dei dati; cresce con $\ln(1/\delta)$ — più confidenza si vuole, più esempi servono, ma solo logaritmicamente, quindi a buon mercato.

Un conto concreto dà la misura delle cose. Supponiamo una classe con un milione di ipotesi candidate — $|H| = 10^6$, una classe modesta per gli standard moderni — e di volere generalizzazione entro $\epsilon = 0{,}05$ con confidenza del 95%, cioè $\delta = 0{,}05$. La formula dà $n \ge \tfrac{1}{2 \cdot 0{,}0025}\big(\ln(10^6) + \ln(40)\big) = 200 \cdot (13{,}8 + 3{,}7) \approx 3500$ esempi.

Notiamo due cose. La prima: il termine della confidenza, $\ln(40) \approx 3{,}7$, è piccolo accanto a quello della complessità del modello, $\ln(10^6) \approx 13{,}8$ — alzare la confidenza dal 95% al 99,9% aggiungerebbe appena un altro $\ln(20)$, una manciata di esempi. La seconda: per dimezzare l’errore da $0{,}05$ a $0{,}025$ il fattore $1/\epsilon^2$ quadruplica, e $n$ salta da 3500 a circa 14000. La precisione è cara, la confidenza è a buon mercato: la formula lo dice numero alla mano.

Questo è il nucleo del PAC learning (Probably Approximately Correct), il framework che Leslie Valiant introduce nel 1984. Un algoritmo PAC-apprende se, con probabilità almeno $1-\delta$ — il “probably” — produce un’ipotesi con errore al più $\epsilon$ — l‘“approximately correct”. La formula della complessità campionaria è la traduzione quantitativa di quella promessa, e l’abbiamo derivata con due soli ingredienti: la disuguaglianza di Hoeffding e lo union bound.

Resta un’ultima generalizzazione, da nominare per onestà. La formula sopra vale per classi finite di ipotesi, perché contiene $\ln|H|$. Le classi di modelli reali — tutte le rette, tutte le reti neurali con una data architettura — sono infinite: $|H|$ è infinito e $\ln|H|$ esplode.

La teoria risolve il problema sostituendo $\ln|H|$ con una misura più fine della “ricchezza effettiva” della classe: la dimensione VC (Vapnik-Chervonenkis) o la complessità di Rademacher. L’idea di fondo non cambia — una disuguaglianza di concentrazione, resa uniforme su tutta la classe di ipotesi, controlla il divario fra rischio empirico e rischio vero — e il suo sviluppo appartiene ai capitoli di teoria dell’apprendimento. Ma il mattone resta quello costruito qui: una media empirica si concentra attorno al suo valore atteso, e di quanto lo fa è un teorema.

Dove si rompe

Gli strumenti di questo capitolo sono solidi, ma hanno confini precisi, e l’uso disinvolto fuori da quei confini produce errori concreti e ricorrenti.

La densità scambiata per probabilità. È l’errore più elementare e il più diffuso. La densità $f(x)$ di una variabile continua non è una probabilità: può superare 1 senza che nulla vada storto — la distribuzione uniforme su $[0, \tfrac{1}{2}]$ ha densità costante 2. La probabilità è sempre l’area sotto la curva su un intervallo, mai l’altezza della curva in un punto.

Da qui un fatto che disorienta chi viene dal discreto: per una variabile continua, $P(X = x) = 0$ per ogni singolo valore $x$. Un evento di probabilità zero non è un evento impossibile; è un evento che ha probabilità zero — i due concetti, che nel discreto coincidono, nel continuo si separano.

Legge dei grandi numeri confusa con limite centrale. I due teoremi rispondono a domande diverse e vanno tenuti separati con disciplina. La legge dei grandi numeri dice che la media converge — il punto d’arrivo. Il teorema del limite centrale dice che forma ha l’errore — gaussiana, ampiezza $\sigma/\sqrt{n}$. La legge dei grandi numeri non dice nulla sulla velocità; il limite centrale sì. Usare l’una al posto dell’altro significa, tipicamente, costruire una barra d’errore inventata o non costruirla affatto.

Convergenza in distribuzione scambiata per convergenza dei valori. La convergenza in distribuzione riguarda la funzione di distribuzione cumulativa, non le variabili. Due successioni con la stessa legge convergono in distribuzione l’una all’altra anche se, come numeri, non si avvicinano mai. Dire ”$X_n$ converge in distribuzione a una Normale” non autorizza a trattare $X_n$ come se fosse quella Normale per ogni scopo: lo autorizza solo per gli scopi che dipendono dalla forma della distribuzione.

Hoeffding applicato a variabili non limitate. Hoeffding richiede che ogni variabile stia in un intervallo noto. Su quantità a coda pesante — tempi di latenza, dimensioni di file, ricompense non limitate in un sistema di RL, importi finanziari — l’ipotesi cade e la disuguaglianza non vale. Applicarla comunque dà barre di confidenza troppo strette, cioè una falsa sicurezza.

Per le code pesanti servono altri strumenti: Chebyshev, che chiede solo la varianza; la disuguaglianza di Bernstein, che usa varianza e limite superiore insieme; oppure bound costruiti apposta per le code pesanti. Verificare la limitatezza prima di invocare Hoeffding non è un dettaglio: è la prima cosa da controllare.

Lo union bound dimenticato. È l’errore concettuale più costoso nei bound di generalizzazione, e merita di essere ripetuto. La garanzia di Hoeffding vale per un’ipotesi fissata prima di vedere i dati. Il modello che un algoritmo restituisce è scelto dopo aver visto i dati, fra molte ipotesi.

Senza la correzione dello union bound — o della dimensione VC per le classi infinite — il bound è ottimisticamente sbagliato. Chi misura il gap di generalizzazione con Hoeffding “nudo” si convince che il modello generalizzi meglio di quanto faccia, e lo stesso errore in piccolo si ripresenta ogni volta che si sceglie il migliore fra molti risultati e poi se ne riporta la performance come se fosse stato l’unico candidato.

La sigma-algebra liquidata come tecnicismo. Per esperimenti finiti la sigma-algebra contiene tutto e si può davvero ignorare. Per spazi continui no: senza restringere agli eventi misurabili, la probabilità diventa contraddittoria — esistono insiemi a cui nessuna probabilità coerente può essere assegnata. La sigma-algebra non è un cavillo che i matematici aggiungono per prudenza; è la recinzione che tiene la teoria in piedi.

La legge dei grandi numeri letta come “compensazione”. Dopo una serie di teste, le croci non diventano più probabili per “riequilibrare” — la moneta non ha memoria. È la fallacia del giocatore.

La legge dei grandi numeri non dice che gli scarti passati vengono annullati da scarti futuri di segno opposto; dice che vengono diluiti. Su un milione di lanci, uno squilibrio di cento teste accumulato all’inizio pesa, nella media, un decimillesimo: non è stato cancellato, è stato reso irrilevante dal volume dei lanci successivi. Convergenza per diluizione, non per compensazione.

Il limite centrale invocato con campioni troppo piccoli. Il teorema del limite centrale è asintotico: dice che la media empirica tende a comportarsi come una gaussiana, ma non dice a quale $n$ l’approssimazione diventa buona. Per distribuzioni di partenza ragionevolmente simmetriche bastano poche decine di campioni; per distribuzioni molto asimmetriche o con code pesanti possono servirne migliaia, e con campioni piccoli la barra di confidenza costruita sul limite centrale è ottimistica — più stretta del vero.

La regola pratica “trenta campioni bastano” è una semplificazione didattica, non un teorema. Quando $n$ è piccolo e la distribuzione è sospetta, conviene una garanzia non asintotica come Hoeffding o un metodo di ricampionamento, che non dipendono dall’approssimazione gaussiana.

La media empirica scambiata per il valore vero. Il rischio empirico, l’accuratezza misurata, la stima Monte Carlo: sono tutte medie empiriche, cioè stime rumorose del valore vero, non il valore vero. Trattarle come esatte — confrontare due numeri senza barra, ottimizzare fino all’ultima cifra decimale, riportare un’accuratezza con tre decimali significativi quando il test set ne giustifica al più uno — è l’errore che tutto il capitolo serve a evitare. Una media empirica senza la sua incertezza è un numero a cui manca metà dell’informazione.

Le ipotesi di indipendenza e identica distribuzione, prese per scontate. Tutti i teoremi del capitolo — legge dei grandi numeri, limite centrale, Hoeffding nella forma per variabili iid — assumono che i campioni siano indipendenti e identicamente distribuiti. Nei dati reali questo spesso non vale: esempi correlati nel tempo, dati con drift di distribuzione fra training e produzione, esempi duplicati o quasi-duplicati in un dataset.

Sotto correlazione, la varianza della media non cala più come $\sigma^2/n$ — compare il termine di covarianza visto nella meccanica — e le barre calcolate come se i dati fossero iid sono troppo strette. Esistono versioni dei teoremi per dati dipendenti, ma vanno invocate consapevolmente: l’ipotesi iid è la più silenziosa e la più spesso violata, e va verificata invece che assunta.

Collegamenti

• Distribuzioni, valore atteso, varianza — definisce in versione operativa valore atteso e varianza, qui ripresi e formalizzati dentro lo spazio di probabilità di Kolmogorov.
• Legge dei grandi numeri e teorema del limite centrale — presenta i due teoremi con taglio statistico; questo capitolo li rivisita con più rigore, distinguendo le versioni debole e forte e collocandole nei modi di convergenza.
• Popolazione, campione, stimatore, incertezza — fissa il vocabolario di popolazione, campione e stimatore che il ponte verso il rischio empirico dà per acquisito.
• Intervalli di confidenza — gli intervalli che le disuguaglianze e il limite centrale producono concretamente attorno a una metrica.
• Convessità, Jensen, minimi globali — la disuguaglianza di Jensen è parente delle disuguaglianze di concentrazione: entrambe legano medie e funzioni non lineari.
• Il trade-off bias-varianza — la varianza che compare in Chebyshev è la stessa che entra nel trade-off fra bias e varianza di uno stimatore.
• multi-armed-bandits e ucb-thompson (Parte VII, in preparazione) — gli algoritmi UCB costruiscono intervalli di confidenza sulle ricompense medie usando direttamente Hoeffding.
• ml-definizione e dataset-split (Parte XVIII, in preparazione) — rischio empirico, suddivisione train/test e generalizzazione sono gli oggetti operativi su cui il ponte di questo capitolo si innesta.
• Entropia, cross-entropy, KL divergence — la funzione generatrice dei momenti e i conti esponenziali dietro Hoeffding hanno parentela con la maniera in cui si manipolano logaritmi e valori attesi nell’entropia.
• Reliability diagram, Brier score, confidenza — la calibrazione misura quanto le probabilità stimate siano affidabili, complemento naturale delle garanzie di concentrazione sulle stime.

Per andare oltre

• Wassily Hoeffding, Probability Inequalities for Sums of Bounded Random Variables (Journal of the American Statistical Association, 1963) — il paper originale della disuguaglianza: enunciato, ipotesi di limitatezza, coda sub-gaussiana.
• Leslie Valiant, A Theory of the Learnable (Communications of the ACM, 1984) — l’articolo fondativo del PAC learning, dove le disuguaglianze di concentrazione diventano una definizione di apprendibilità.
• Andrey Kolmogorov, Foundations of the Theory of Probability (traduzione inglese del Grundbegriffe del 1933, Chelsea, 1956) — la monografia che assiomatizza la probabilità come teoria della misura; breve e leggibile nella prima parte.
• Larry Wasserman, All of Statistics (Springer, 2004) — i capitoli su convergenza e disuguaglianze sono una trattazione compatta e moderna, pensata per chi viene dall’informatica.
• Stéphane Boucheron, Gábor Lugosi, Pascal Massart, Concentration Inequalities: A Nonasymptotic Theory of Independence (Oxford University Press, 2013) — il riferimento avanzato sulle disuguaglianze di concentrazione, per chi vuole andare oltre Hoeffding (Bernstein, McDiarmid, metodo dell’entropia).