Questo capitolo chiude la parte del corso dedicata all’apprendimento supervisionato con il suo argomento più teorico: la teoria dell’apprendimento computazionale (computational learning theory). Fin qui il corso ha presentato algoritmi e li ha valutati empiricamente; ora la prospettiva si ribalta e si cercano le leggi generali dell’apprendimento induttivo. Le domande a cui si vuole rispondere sono del tipo: quanti campioni di training servono a un learner per convergere, con una certa probabilità, a un’ipotesi con una certa accuratezza minima? Quali prestazioni ci si può aspettare su dati mai visti? Quando un concetto è “imparabile”? Gli strumenti sviluppati per rispondere, il framework PAC, i bound sulla sample complexity e la VC dimension, non sono quasi mai formule da usare direttamente in produzione, ma sono preziosissimi per capire e confrontare famiglie di modelli, e per spiegare perché certe tecniche funzionano meglio di altre su certi problemi. Essendo il capitolo più astratto del corso, ogni concetto viene accompagnato da esempi numerici concreti.

Riferimento sul testo: Mitchell, Machine Learning, capitolo 7 (sezioni 7.1, 7.2, 7.3, 7.4). Per questa parte il riferimento non è il Bishop: il testo di Mitchell, pur datato, tratta l’argomento in modo molto più accessibile.

1. La domanda: quanti dati servono per imparare?#

1.1 Il quadro di riferimento#

Il setting è quello consueto dell’apprendimento supervisionato, ristretto per semplicità alla classificazione binaria (le idee si generalizzano anche alla regressione, ma la classificazione binaria è il contesto in cui la teoria si presenta nel modo più pulito). Un learner $L$, cioè un algoritmo di apprendimento con la sua famiglia di modelli, vuole imparare un concetto $c$ che mappa i punti dello spazio di input $X$ in un target binario. Il learner cerca la soluzione dentro il proprio spazio delle ipotesi $H$, l’insieme di tutte le funzioni $h: X \to \{0, 1\}$ che il modello scelto può rappresentare: ogni ipotesi è una possibile frontiera di decisione che separa punti positivi e negativi nello spazio di input.

Si supponga ora che il learner abbia trovato un’ipotesi $h^*$ che non commette alcun errore sui dati di training. La domanda fondamentale è: quanti campioni di $X$ servono nel training set per poter concludere che $L$ ha davvero imparato il concetto vero, cioè che $h^* \equiv c$?

Se si affronta la domanda in termini completamente generali, senza alcuna assunzione aggiuntiva, la risposta è pessima: servono tutti i punti dello spazio di input. In altre parole, senza assunzioni non si impara, si può solo memorizzare l’intera tabella input-output. Questa risposta scoraggiante ha una formulazione precisa nei teoremi No Free Lunch.

1.2 I teoremi No Free Lunch#

Sia $ACC_G(L)$ l’accuratezza di generalizzazione del learner $L$, cioè l’accuratezza misurata sui campioni che non appartengono al training set, e sia $\mathcal{F}$ l’insieme di tutti i possibili concetti $y = f(\mathbf{x})$.

Cioè: in media su tutti i problemi possibili, qualunque algoritmo di apprendimento va esattamente come il lancio di una moneta. Lo schizzo di dimostrazione è illuminante: per ogni concetto $f$ su cui il learner ottiene accuratezza $0.5 + \delta$, esiste un concetto “specchio” $f'$ su cui ottiene $0.5 - \delta$. Il concetto specchio si costruisce così: $f'(\mathbf{x}) = f(\mathbf{x})$ per ogni $\mathbf{x} \in \mathcal{D}$ (sul training set i due concetti coincidono, quindi il learner produce esattamente la stessa ipotesi) e $f'(\mathbf{x}) \neq f(\mathbf{x})$ per ogni $\mathbf{x} \notin \mathcal{D}$ (fuori dal training set le etichette sono tutte invertite). Ogni punto di accuratezza guadagnato su $f$ viene perso, identico, su $f'$.

Dal teorema segue un corollario ancora più tagliente sul confronto tra algoritmi: per qualunque coppia di learner $L_1$ e $L_2$, se esiste un concetto $f$ su cui $ACC_G(L_1) > ACC_G(L_2)$, allora esiste un concetto $f'$ su cui $ACC_G(L_2) > ACC_G(L_1)$. Non esiste un learner migliore di tutti gli altri su tutti i problemi: in machine learning non c’è un “vincitore assoluto”.

In parole semplici: se si considerano tutti i problemi immaginabili, compresi quelli assurdi in cui le etichette fuori dal training set sono scelte apposta per contraddire il modello, nessun algoritmo può battere il caso. Quindi ogni volta che il machine learning funziona, è perché stiamo sfruttando qualche assunzione sul problema. Il punto non è trovare l’algoritmo perfetto, ma capire quali assunzioni stiamo facendo.

1.3 Il bias induttivo: l’assunzione che rende possibile imparare#

Che cosa c’è di “irragionevole” nel concetto specchio della dimostrazione? Il fatto che due concetti coincidano perfettamente sul training set e siano opposti ovunque altrove viola l’assunzione fondante del machine learning: che il training set sia rappresentativo della distribuzione dei dati. In pratica si applicano metodi di apprendimento solo quando si può raccogliere un dataset abbastanza grande e abbastanza rappresentativo da essere un buon proxy di ciò che accade sull’intero spazio di input. Questa assunzione si chiama bias induttivo: ciò che si osserva sui dati di training si assume valga anche sui dati futuri, perché entrambi provengono dalla stessa distribuzione.

C’è poi un secondo bias, più sottile: la scelta del modello. Quando si sceglie, per esempio, la regressione logistica, si sta implicitamente scommettendo che il problema sia risolvibile ragionevolmente con una frontiera di decisione lineare. Se la scommessa è giusta, quel modello funzionerà bene su quella famiglia di problemi; il No Free Lunch garantisce che sulla famiglia “sbagliata” andrà peggio di altri.

Idea chiave: la teoria PAC che segue non elimina i teoremi No Free Lunch: li aggira dichiarando esplicitamente le assunzioni (bias induttivo, scelta dello spazio delle ipotesi) e derivando, sotto quelle assunzioni, bound quantitativi sull’errore atteso e sul numero di campioni necessari.

2. Il setting formale: errore vero ed errore empirico#

2.1 Le assunzioni del framework#

Il framework di riferimento richiede alcune definizioni e semplificazioni precise:

• $X$ è lo spazio delle istanze (instance space), l’insieme di tutti i possibili input.
• $H = \{h : X \to \{0,1\}\}$ è lo spazio delle ipotesi del learner $L$: l’insieme dei classificatori che il modello può rappresentare.
• $C = \{c : X \to \{0,1\}\}$ è l’insieme di tutti i possibili concetti target che si potrebbe voler imparare; il problema concreto consiste nell’imparare un particolare $c \in C$.
• Il training set $\mathcal{D}$ è campionato da una distribuzione stazionaria $P(X)$ ed etichettato senza rumore secondo il concetto $c$: la stessa distribuzione genererà anche i dati futuri (questo è il bias induttivo formalizzato) e la funzione che assegna le etichette è deterministica.
• Il learner restituisce sempre l’ipotesi ottima all’interno di $H$ rispetto all’errore di training:

$$h^* = \arg\min_{h \in H} error_{\mathcal{D}}(h)$$

Per modelli semplici come la regressione logistica o lineare quest’ultima è un’assunzione realistica; per una rete neurale, il cui addestramento è un problema di ottimizzazione con molti minimi locali, non è garantita, ma la si accetta per semplicità.

2.2 Errore empirico ed errore vero#

In un problema di classificazione binaria l’errore di un’ipotesi sui dati di training è semplicemente la frazione di punti misclassificati.

Ma, come è stato ripetuto molte volte nel corso, ciò che interessa davvero non è l’errore sul training set: è l’errore sull’intero spazio di input, pesato con la probabilità di incontrare ciascun punto.

Il problema è che $error_{true}$ non è calcolabile: richiederebbe di conoscere la distribuzione $P(X)$ e il concetto $c$ su tutto lo spazio, cioè esattamente le cose che non si hanno. Si dice che $h$ va in overfitting quando $error_{true}(h) > error_{\mathcal{D}}(h)$: la vera questione del capitolo è se si possa limitare (bound) l’errore vero a partire dall’errore empirico.

In parole semplici: l’errore di training si misura contando gli sbagli sui dati che si hanno; l’errore vero è quello che si commetterebbe in media “nel mondo reale”, e nessuno lo può calcolare direttamente. Tutta la teoria di questo capitolo serve a rispondere a una domanda sola: quanto può essere più grande il secondo rispetto al primo?

2.3 Il tentativo ingenuo e perché fallisce#

Un primo tentativo di collegare i due errori usa la statistica elementare. L’evento “il modello sbaglia su un campione estratto a caso” è una variabile aleatoria di Bernoulli con media $error_{true}(h)$; l’errore di training è la media empirica di $N$ osservazioni di questa variabile. Si potrebbe allora costruire il classico intervallo di confidenza al 95% per la media di una Bernoulli:

$$error_{true}(h) \;\approx\; error_{\mathcal{D}}(h) \pm 1.96 \sqrt{\frac{error_{\mathcal{D}}(h)\big(1 - error_{\mathcal{D}}(h)\big)}{N}}$$

dove la costante 1.96 dipende dal livello di confidenza scelto: più confidenza si vuole, più largo diventa l’intervallo.

Questo ragionamento è sbagliato, e capire perché è istruttivo. La derivazione dell’intervallo di confidenza è tecnicamente corretta, ma richiede che le osservazioni siano indipendenti dall’oggetto che si sta valutando. Qui non lo sono affatto: l’ipotesi $h$ non è un modello qualsiasi testato su dati nuovi, è il modello che è stato ottimizzato proprio su $\mathcal{D}$. Tra tutte le ipotesi dello spazio, il learner ha deliberatamente scelto quella con l’errore più basso su quei dati: l’errore di training è quindi una stima sistematicamente ottimistica (distorta verso il basso) dell’errore vero, e il macchinario degli intervalli di confidenza non si applica.

In parole semplici: è come giudicare la preparazione di uno studente facendogli ripetere esattamente gli esercizi su cui ha studiato: il voto sarà gonfiato, perché lo studente si è “adattato” proprio a quegli esercizi. Per avere garanzie oneste serve un ragionamento che tenga conto del fatto che il modello è stato scelto guardando i dati.

Per ottenere bound validi bisogna quindi lavorare sotto assunzioni più strutturate. Si parte dal caso più semplice: il learner trova un’ipotesi con errore di training esattamente zero.

3. Bound per learner consistenti#

3.1 Ipotesi consistenti e version space#

In generale non c’è una sola ipotesi consistente: possono essercene molte (molte frontiere di decisione diverse che classificano perfettamente gli stessi punti). L’insieme di tutte queste ipotesi ha un nome.

Da qui in avanti si considerano learner consistenti: learner che restituiscono sempre un’ipotesi del version space, assumendo che il version space non sia vuoto (assunzione ragionevole se lo spazio delle ipotesi è stato scelto con criterio rispetto al problema).

Per visualizzare la situazione conviene immaginare lo spazio $H$ come una nuvola di punti, ognuno dei quali è un’ipotesi con associata una coppia di errori $(error_{\mathcal{D}}, error_{true})$. Fuori dal version space ci sono ipotesi con, per esempio, $error_{\mathcal{D}} = 0.3$ e $error_{true} = 0.4$; dentro il version space tutte le ipotesi hanno $error_{\mathcal{D}} = 0$, ma i loro errori veri possono essere diversi: una può avere $error_{true} = 0.1$, un’altra $error_{true} = 0.2$. Il learner ne restituisce una, ma non si sa quale: quindi, per limitare l’errore vero dell’ipotesi appresa, bisogna trovare un bound che valga per tutte le ipotesi del version space contemporaneamente. Se il bound vale per tutto il version space, vale in particolare anche per l’ipotesi $h^*$ scelta dal learner.

Idea chiave: non potendo prevedere quale ipotesi consistente verrà restituita, si limita probabilisticamente l’errore vero dell’intero version space: si vuole rendere piccola la probabilità che il version space contenga anche una sola ipotesi “cattiva”, cioè con errore vero sopra una soglia $\varepsilon$.

3.2 Il teorema fondamentale#

Il bound ha esattamente la struttura che serve: la probabilità dell’evento “esiste un’ipotesi con training error zero ma errore vero sopra $\varepsilon$” decresce esponenzialmente con il numero di campioni $N$ e con la soglia $\varepsilon$, e cresce (solo linearmente) con la taglia dello spazio delle ipotesi $|H|$, che gioca il ruolo di misura di complessità del modello.

3.3 Dimostrazione#

La dimostrazione è una catena di maggiorazioni, ognuna delle quali sostituisce la quantità corrente con qualcosa di più semplice e più grande; alla fine si ottiene un’espressione calcolabile che maggiora la probabilità di partenza. I passaggi sono quattro.

Passo 1 (union bound). La quantità da limitare è la probabilità che almeno una ipotesi in $H$ sia contemporaneamente consistente e cattiva. La probabilità dell’unione di eventi non supera la somma delle probabilità dei singoli eventi (la probabilità di “A oppure B oppure C” non è mai maggiore di $P(A) + P(B) + P(C)$):

$$\Pr\Big[ \exists h \in H : error_{\mathcal{D}}(h) = 0 \wedge error_{true}(h) > \varepsilon \Big] \;\leq\; \sum_{h \in H} \Pr\Big[ error_{\mathcal{D}}(h) = 0 \wedge error_{true}(h) > \varepsilon \Big]$$

Passo 2 (regola del prodotto). Ogni termine della somma è una probabilità congiunta, che si riscrive come prodotto tra una condizionata e una marginale; scartando la marginale (che è al più 1) si ottiene una maggiorazione:

$$\Pr\big[ error_{\mathcal{D}}(h) = 0 \wedge error_{true}(h) > \varepsilon \big] \;\leq\; \Pr\big[ error_{\mathcal{D}}(h) = 0 \mid error_{true}(h) > \varepsilon \big]$$

Passo 3 (calcolo della condizionata). Se un’ipotesi ha errore vero maggiore di $\varepsilon$, la probabilità che classifichi correttamente un singolo campione estratto a caso è minore di $1 - \varepsilon$. Perché risulti consistente deve “avere fortuna” $N$ volte di fila su campioni indipendenti:

$$\Pr\big[ error_{\mathcal{D}}(h) = 0 \mid error_{true}(h) > \varepsilon \big] \;\leq\; (1 - \varepsilon)^N$$

Passo 4 (conteggio e disuguaglianza esponenziale). La somma del passo 1 ha al più $|H|$ termini (non si sa quante ipotesi soddisfino le condizioni, quindi si prende l’opzione più conservativa: tutte). Infine si applica la disuguaglianza $1 - \varepsilon \leq e^{-\varepsilon}$, valida per ogni $\varepsilon \in [0, 1]$:

$$\Pr\Big[ \exists h \in VS_{H,\mathcal{D}} : error_{true}(h) > \varepsilon \Big] \;\leq\; |H| (1 - \varepsilon)^N \;\leq\; |H| \, e^{-\varepsilon N}$$

che è la tesi. $\blacksquare$

In parole semplici: un’ipotesi con errore vero del 10% ha probabilità $0.9^N$ di azzeccare per caso tutti gli $N$ esempi di training, e questa probabilità crolla in fretta al crescere di $N$. Moltiplicando per il numero di ipotesi si copre il caso peggiore in cui tutte le ipotesi cattive tentano la fortuna. Se il prodotto è piccolo, è quasi impossibile che il training error zero sia un colpo di fortuna.

3.4 Dal bound alle formule pratiche#

Il bound diventa operativo dando un nome alla probabilità di fallimento. Si chiami $\delta$ la probabilità (massima tollerata) che un’ipotesi consistente abbia errore vero maggiore di $\varepsilon$:

$$|H| \, e^{-\varepsilon N} \;\leq\; \delta$$

Il parametro $\varepsilon$ misura l’accuratezza richiesta (quanto errore vero si è disposti a tollerare), mentre $1 - \delta$ misura la confidenza (con quale probabilità si vuole che la garanzia valga). Fissati due dei tre parametri $(\varepsilon, \delta, N)$, si ricava il terzo risolvendo la disuguaglianza.

Fissando accuratezza e confidenza si ottiene la sample complexity, cioè il numero minimo di campioni:

Fissando invece il numero di campioni disponibili e la confidenza, si ottiene un bound sull’errore vero raggiungibile:

Come si ricavano le due formule dal bound

Si parte da $|H| e^{-\varepsilon N} \leq \delta$ e si isola l’esponenziale: $e^{-\varepsilon N} \leq \delta / |H|$. Prendendo il logaritmo naturale di entrambi i membri (funzione crescente, quindi il verso non cambia) si ottiene $-\varepsilon N \leq \ln \delta - \ln |H|$, cioè $\varepsilon N \geq \ln |H| - \ln \delta = \ln |H| + \ln \frac{1}{\delta}$. Dividendo per $\varepsilon$ si ricava la sample complexity; dividendo per $N$ si ricava il bound su $\varepsilon$.

Due osservazioni sulla struttura di queste formule:

• La dipendenza da $|H|$ è logaritmica, il che sembra rendere quasi irrilevante la complessità del modello. Non è così: per i modelli tipici $|H|$ cresce esponenzialmente con il numero di feature, quindi $\ln|H|$ cresce linearmente con il numero di feature. Il logaritmo mitiga, non cancella, il costo della complessità.
• La dipendenza da $\delta$ è anch’essa logaritmica: chiedere una confidenza molto più alta (per esempio passare dal 99% al 99.9%) costa relativamente poco in termini di campioni aggiuntivi. La dipendenza da $\varepsilon$ è invece del tipo $1/\varepsilon$: dimezzare l’errore tollerato raddoppia i campioni necessari.

In parole semplici: la formula è un contratto a tre voci: quanto errore accetti ($\varepsilon$), quanta fiducia vuoi nella garanzia ($\delta$) e quanti dati ti servono ($N$). Modelli più ricchi (più ipotesi) chiedono più dati, ma per fortuna solo attraverso un logaritmo; essere più esigenti sull’errore, invece, si paga in proporzione diretta.

3.5 Esempio 1: congiunzioni di letterali booleani#

Si consideri un problema di classificazione con spazio delle istanze $X = \langle x_1, x_2, x_3, x_4 \rangle$, dove ogni $x_i$ è una variabile booleana. Ogni ipotesi è una regola della forma

$$\text{if } (x_1 = 1, \; x_2 = ?, \; x_3 = 0, \; x_4 = 1) \text{ then } y = 1, \text{ otherwise } y = 0$$

dove per ogni variabile la regola può richiedere il valore 0, il valore 1, oppure usare il jolly “?” che significa “qualunque valore va bene”. La regola dell’esempio classifica come positivi tutti e soli i punti con $x_1 = 1$, $x_3 = 0$, $x_4 = 1$, qualunque sia $x_2$.

Calcolo di $|H|$: per ciascuna delle 4 variabili ci sono 3 scelte possibili (0, 1 oppure ?), quindi

$$|H| = 3^4 = 81$$

Domanda: quanti campioni $N$ servono per garantire, con probabilità almeno 0.99, che l’errore vero di un’ipotesi consistente non superi 0.05?

Soluzione: si pone $\delta = 0.01$ (confidenza 99%) e $\varepsilon = 0.05$, e si applica la formula della sample complexity:

$$N \;\geq\; \frac{1}{0.05} \left( \ln 81 + \ln \frac{1}{0.01} \right) = 20 \cdot (4.394 + 4.605) \approx 180$$

Servono almeno 180 campioni. In questo caso specifico il risultato rivela un problema: con 4 variabili booleane esistono solo $2^4 = 16$ istanze distinte in tutto lo spazio! Il bound richiede più campioni di quante istanze diverse esistano, quindi con questo problema minuscolo la garanzia richiesta (99% di confidenza, errore sotto il 5%) non è raggiungibile: bisognerebbe abbassare la confidenza o alzare l’errore tollerato. Il bound, essendo costruito con maggiorazioni molto conservative, è pessimistico soprattutto sui problemi piccoli.

Scalabilità: la situazione cambia radicalmente al crescere del numero di variabili $M$, perché $|H| = 3^M$ e quindi $\ln|H| = M \ln 3$ cresce solo linearmente:

• con $M = 10$: $N \geq 20 \cdot (10 \ln 3 + \ln 100) \approx 312$;
• con $M = 100$: $N \geq 20 \cdot (100 \ln 3 + \ln 100) \approx 2290$.

Con 100 variabili lo spazio delle istanze contiene $2^{100}$ punti, un numero astronomico, eppure bastano circa 2290 campioni per garantire che un classificatore consistente abbia, con confidenza 99%, errore vero sotto il 5%. Questo è il potere del bias induttivo: la struttura ristretta dello spazio delle ipotesi (solo congiunzioni) rende il concetto imparabile con una frazione infinitesimale dei dati possibili.

3.6 Esempio 2: alberi di decisione di profondità 2#

Stesso schema con un modello diverso: lo spazio delle istanze è $X = \langle x_1, \dots, x_M \rangle$ con variabili booleane, e ogni ipotesi è un albero di decisione di profondità 2 che usa esattamente due variabili: una variabile $x_i$ alla radice e una variabile $x_j$ in entrambi i nodi del secondo livello; le quattro foglie contengono le etichette (0 o 1).

Calcolo di $|H|$: i gradi di libertà sono la scelta della coppia di variabili e l’etichettatura delle foglie. Le coppie di variabili possibili sono $\frac{M(M-1)}{2}$, e ciascuna delle 4 foglie può essere etichettata in 2 modi, per $2^4 = 16$ etichettature:

$$|H| = \frac{M(M-1)}{2} \cdot 16$$

Domanda: con $M = 10$ variabili, quanti campioni servono per garantire con probabilità almeno 0.99 che l’errore di un’ipotesi consistente non superi 0.05?

Soluzione: $|H| = \frac{10 \cdot 9}{2} \cdot 16 = 720$, quindi

$$N \;\geq\; \frac{1}{0.05} \left( \ln 720 + \ln 100 \right) = 20 \cdot (6.579 + 4.605) \approx 224$$

L’esempio mostra che l’unico ingrediente che cambia da modello a modello è il modo di contare $|H|$: identificare i gradi di libertà del modello (quali variabili, quali soglie, quali etichette) e contare le combinazioni. È un’abilità richiesta esplicitamente all’esame.

3.7 La definizione di PAC-learnability#

Il quadro sviluppato fin qui culmina nella definizione che dà il nome al framework: apprendimento PAC, Probably Approximately Correct. Il nome racconta esattamente il contenuto: non si può pretendere un’ipotesi esattamente corretta (servirebbero tutti i dati), e nemmeno la certezza assoluta (il training set potrebbe essere sfortunato); ci si accontenta di un’ipotesi approssimativamente corretta (errore vero al più $\varepsilon$) probabilmente (con probabilità almeno $1 - \delta$).

Colpisce che la definizione parli di tempo di calcolo: la PAC-learnability è dunque solo una questione di complessità computazionale? E la complessità rispetto al numero di campioni $N$? Le due cose sono legate: ogni campione va almeno processato, quindi il tempo di apprendimento è almeno proporzionale al numero di campioni. In pratica, una condizione sufficiente per dimostrare la PAC-learnability è mostrare che il learner richiede solo un numero polinomiale di esempi di training (in $1/\varepsilon$, $1/\delta$, $M$, $size(c)$) e un tempo di elaborazione polinomiale per esempio. Ecco perché i bound sulla sample complexity della sezione 3.4 sono lo strumento centrale: se il numero di campioni richiesto dal bound è polinomiale, il concetto è PAC-learnable.

In parole semplici: un concetto è “imparabile” nel senso PAC se si può raggiungere qualunque livello di accuratezza e confidenza pagando un prezzo ragionevole (polinomiale, non esponenziale) in dati e tempo di calcolo. La definizione trasforma la domanda filosofica “si può imparare?” in una domanda quantitativa con una risposta calcolabile.

4. Apprendimento agnostico: quando l’errore di training non è zero#

4.1 Rilassare la richiesta di consistenza#

I bound della sezione 3 hanno un difetto pratico: valgono solo per learner consistenti, cioè solo se esiste (e viene trovata) un’ipotesi con errore di training esattamente zero. Fin qui si è implicitamente assunto che $c \in H$, o quantomeno che il version space non fosse vuoto. In generale non è così: anche su problemi semplici trovare errore zero può essere impossibile, per esempio perché il concetto vero non appartiene allo spazio delle ipotesi scelto. Un learner agnostico non fa alcuna assunzione del tipo $c \in H$: si limita a restituire l’ipotesi con l’errore di training minimo, che in generale sarà $error_{\mathcal{D}}(h) > 0$.

La domanda diventa: si può limitare $error_{true}(h)$ a partire da un $error_{\mathcal{D}}(h)$ non nullo? La forma naturale del bound cambia: non si limita più l’errore vero in assoluto, ma di quanto l’errore vero può superare quello di training.

4.2 La disuguaglianza di Hoeffding#

Lo strumento tecnico è un risultato classico di teoria della probabilità sulle medie empiriche.

Applicata al nostro contesto: per una singola ipotesi $h$ fissata a priori, l’errore di training è la media empirica di $N$ Bernoulli con media $error_{true}(h)$, quindi

$$\Pr\big[ error_{true}(h) > error_{\mathcal{D}}(h) + \varepsilon \big] \;\leq\; e^{-2N\varepsilon^2}$$

Ma attenzione: usato così, questo bound ricadrebbe esattamente nell’errore del tentativo ingenuo della sezione 2.3. L’ipotesi restituita dal learner non è fissata a priori: è stata ottimizzata per rendere l’errore di training il più piccolo possibile, quindi la stima empirica non è indipendente dall’ipotesi e il bound sulla singola $h$ non si applica a $h^*$. La correzione è la stessa della sezione 3: si richiede che il bound valga simultaneamente per tutte le ipotesi dello spazio, tramite union bound, così da coprire anche quella che il learner sceglierà.

4.3 Il bound agnostico#

La struttura è parallela al caso consistente: fattore $|H|$ dall’union bound su tutto lo spazio, decadimento esponenziale in $N$. La differenza cruciale è che l’esponente contiene $\varepsilon^2$ invece di $\varepsilon$: a parità di garanzie servirà un numero di campioni che scala come $1/\varepsilon^2$ invece che come $1/\varepsilon$. Rinunciare alla consistenza costa: la garanzia diventa quadraticamente più esosa in dati.

4.4 Sample complexity e bound sull’errore vero#

Procedendo come nella sezione 3.4, si pone $\delta \geq |H| e^{-2N\varepsilon^2}$ e si risolve. La sample complexity diventa:

$$N \;\geq\; \frac{1}{2\varepsilon^2} \left( \ln |H| + \ln \frac{1}{\delta} \right)$$

Risolvendo invece per $\varepsilon$, si ottiene il bound sull’errore vero: con probabilità almeno $1 - \delta$, per ogni $h \in H$,

Questa formula realizza finalmente, in modo corretto, il progetto fallito della sezione 2.3: limitare l’errore vero a partire dall’errore di training osservato.

Vale la pena leggerla con attenzione, perché ha una struttura familiare: è una decomposizione in stile bias-varianza. Il primo termine, l’errore di training, misura quanto bene il modello riesce ad adattarsi ai dati: è alto se il modello è troppo semplice per il problema (comportamento da bias). Il secondo termine cresce con la complessità del modello ($\ln|H|$) e decresce con la quantità di dati ($N$): misura quanto la stima empirica può discostarsi dal valore vero (comportamento da varianza). Un modello più complesso abbassa il primo termine ma alza il secondo: il compromesso bias-varianza incontrato empiricamente nel corso riemerge qui come conseguenza di un teorema.

In parole semplici: l’errore sul mondo reale è al massimo “errore misurato sul training più un margine di sicurezza”. Il margine si allarga se il modello è complicato (tante ipotesi tra cui una potrebbe aver barato) e si restringe se i dati sono tanti. Scegliere il modello giusto significa bilanciare le due voci: un modello che azzera l’errore di training ma ha margine enorme non dà nessuna garanzia.

5. Il limite del conteggio: spazi di ipotesi infiniti#

5.1 Il problema: $|H| = \infty$ quasi sempre#

Tutti i bound visti finora contengono $|H|$, la cardinalità dello spazio delle ipotesi, come misura della complessità del modello. Il problema pratico è che per la maggior parte dei modelli reali questa quantità è infinita. Perfino per la regressione logistica, uno dei modelli più semplici del corso, i parametri sono numeri reali: le possibili frontiere di decisione lineari sono infinite, quindi $|H| = \infty$ e i bound diventano vuoti.

C’è anche un problema concettuale più profondo: l’intuizione dice che la regressione logistica è meno complessa di una rete neurale profonda, ma se si misura la complessità con $|H|$ i due modelli risultano indistinguibili, entrambi con “taglia infinita”. Serve una misura di complessità diversa, capace di discriminare tra spazi infiniti.

5.2 Memorizzare non è imparare#

L’intuizione giusta per costruire la nuova misura viene dal caso finito. Sia $|X| = N$ uno spazio di istanze finito: i concetti binari possibili su $X$ sono $|C| = 2^N$. Se lo spazio delle ipotesi contiene tutte le $2^N$ funzioni possibili, allora per qualunque etichettatura del training set esiste un’ipotesi con $error_{\mathcal{D}}(h) = 0$: la consistenza è sempre raggiungibile. Ma proprio per questo non dice più nulla: un errore di training pari a zero non fornisce alcuna informazione sull’errore sugli altri campioni di $X$, perché il modello può semplicemente aver memorizzato la tabella delle etichette. In termini di bound: con $|H| = 2^N$ si ha $\ln|H| = N \ln 2$, e la sample complexity diventa proporzionale a $N$, cioè bisogna vedere praticamente tutto lo spazio. La teoria conferma che quel modello non impara: memorizza.

Che succede invece se con $H$ si è in grado di classificare correttamente, qualunque sia il concetto, non più di 2 campioni di training? Allora osservare la consistenza su molti più di 2 campioni è informativo: il modello non aveva la capacità di memorizzare tutte le etichettature, quindi la sua coerenza con i dati testimonia una reale corrispondenza con il concetto.

Idea chiave: la complessità utile di uno spazio di ipotesi non è quante ipotesi contiene, ma quanti punti riesce a etichettare in tutti i modi possibili. Un modello capace di riprodurre qualunque etichettatura di un insieme di punti, su quei punti sta potenzialmente memorizzando; la sua capacità di generalizzare si misura sul numero massimo di punti per cui questo può accadere. Questa misura è la VC dimension.

6. Shattering e VC dimension#

6.1 Dicotomie#

Un insieme di $d$ punti ammette esattamente $2^d$ dicotomie distinte: ogni punto può ricevere una delle due etichette, indipendentemente dagli altri.

6.2 Shattering#

In altre parole: $S$ è shattered da $H$ se, comunque si scelga di etichettare i punti di $S$, c’è sempre un’ipotesi che li classifica tutti correttamente. Lo shattering cattura esattamente la capacità di “riprodurre qualunque etichettatura” della sezione 5.2.

In parole semplici: immaginare di sfidare il modello: un avversario etichetta i punti nel modo più cattivo possibile, e il modello deve trovare nel suo repertorio una frontiera che li separi tutti correttamente. Se il modello vince la sfida per ogni possibile etichettatura, quell’insieme di punti è shattered: su quei punti il modello può fare qualunque cosa, quindi non sta dimostrando di aver capito nulla.

6.3 VC dimension#

Alcune osservazioni immediate sulla definizione:

• La richiesta è che esista un insieme di quella taglia shattered da $H$: non serve che tutti gli insiemi di quella taglia lo siano.
• $VC(H) = d$ significa due cose insieme: esiste almeno un insieme di $d$ punti shattered, e nessun insieme di $d + 1$ punti è shattered.
• La VC dimension non dipende dal concetto target né dalla distribuzione dei dati: è una proprietà intrinseca dello spazio delle ipotesi.

6.4 Esempio guida: il classificatore lineare nel piano#

Si consideri un classificatore lineare in uno spazio di input 2D: ogni ipotesi è una retta che divide il piano, con un lato positivo e uno negativo. Qual è la sua VC dimension?

Lower bound: 3 punti si possono shatterare. Si prendano 3 punti non allineati, per esempio i vertici di un triangolo. Le dicotomie possibili sono $2^3 = 8$: tutti positivi, tutti negativi, uno positivo e due negativi (3 casi), due positivi e uno negativo (3 casi). Per ognuna esiste una retta consistente: se le etichette sono tutte uguali basta una retta esterna che lasci i tre punti dallo stesso lato; se un punto ha etichetta diversa dagli altri due, basta una retta che lo separi dagli altri, e con punti non allineati questa retta esiste sempre. Quindi $VC \geq 3$.

Upper bound: 4 punti non si possono mai shatterare. Bisogna mostrare che, comunque si scelgano 4 punti nel piano, esiste almeno una dicotomia impossibile per una retta. I casi sono due:

• Un punto dentro il triangolo degli altri tre (o tre punti allineati, caso ancora più semplice): si etichettino i tre vertici come positivi e il punto interno come negativo. Qualunque semipiano contenga i tre vertici contiene, per convessità, l’intero triangolo, e quindi anche il punto interno: la dicotomia è irrealizzabile.
• Quattro punti in posizione convessa (vertici di un quadrilatero): si etichettino i punti alternandoli lungo il perimetro, positivo-negativo-positivo-negativo, in modo che i due positivi siano su una diagonale e i due negativi sull’altra. I segmenti che congiungono i due positivi e i due negativi si intersecano; se esistesse una retta separatrice, i due segmenti starebbero in semipiani opposti e non potrebbero incrociarsi: contraddizione. Questa è esattamente la configurazione del problema XOR, storicamente famosa perché dimostra che il percettrone (classificatore lineare) non può rappresentare la funzione XOR, l’osservazione che congelò per anni la ricerca sulle reti neurali.

Conclusione: un classificatore lineare in 2D ha $VC(H) = 3$. Il risultato si estende: si può dimostrare che un classificatore lineare in uno spazio di input $M$-dimensionale ha

$$VC(H) = M + 1$$

È interessante notare che $M + 1$ è esattamente il numero di parametri del classificatore lineare ($M$ pesi più il bias): per i modelli lineari la VC dimension coincide con il numero di gradi di libertà. Questa corrispondenza è una buona intuizione ma non una legge generale: la VC dimension misura la capacità espressiva effettiva, non il conteggio dei parametri, ed esistono famiglie di ipotesi con un solo parametro reale e VC dimension infinita. Per i modelli trattati nel corso, comunque, la VC dimension cresce con la ricchezza parametrica del modello, ed è questo che la rende una misura di complessità sensata.

In parole semplici: una retta nel piano può “accontentare” qualunque etichettatura di 3 punti ben piazzati, ma con 4 punti c’è sempre un’etichettatura (quella a scacchiera dello XOR) che nessuna retta può realizzare. Quel numero di soglia, 3, è la VC dimension: il punto in cui il modello smette di poter fare tutto e comincia, volente o nolente, a esprimere un’opinione sui dati.

6.5 Proprietà generali#

VC dimension per spazi finiti. La VC dimension si può applicare anche quando $H$ è finito (dove non sarebbe strettamente necessaria, visto che si possono usare i bound con $|H|$). In quel caso vale sempre

$$VC(H) \;\leq\; \log_2 |H|$$

La ragione è un semplice conteggio: se $VC(H) = d$, esiste un insieme di $d$ istanze shattered, e per realizzare tutte le sue $2^d$ dicotomie servono almeno $2^d$ ipotesi distinte (ipotesi diverse per dicotomie diverse). Quindi $|H| \geq 2^d$, da cui $d \leq \log_2 |H|$.

VC dimension infinita. Se per ogni $d$ esiste un insieme di $d$ punti shattered da $H$, allora $VC(H) = \infty$: è il caso del modello che memorizza, per il quale nessuna garanzia di generalizzazione è possibile. Un modello utile deve avere VC dimension finita.

7. Bound PAC basati sulla VC dimension#

7.1 Il bound per learner consistenti#

Con la VC dimension come nuova misura di complessità si possono riscrivere i bound della teoria PAC in una forma valida anche per spazi di ipotesi infiniti. Le dimostrazioni sono molto più tecniche di quelle viste per il caso finito e non vengono richieste; i risultati mantengono però la stessa struttura concettuale, con il termine $\ln|H|$ sostituito da un termine che dipende da $VC(H)$.

La corrispondenza con il bound finito $N \geq \frac{1}{\varepsilon}\big(\ln|H| + \ln\frac{1}{\delta}\big)$ è evidente: stesso fattore $1/\varepsilon$ davanti, stessa dipendenza logaritmica dalla confidenza $\delta$, e il ruolo di $\ln|H|$ è preso da $VC(H)$ (moltiplicata per un fattore logaritmico in $1/\varepsilon$). Il messaggio è identico: il numero di campioni necessari cresce linearmente con la complessità del modello, ora misurata dalla VC dimension.

7.2 Il bound agnostico#

Anche il bound agnostico ha la sua versione basata sulla VC dimension: con probabilità almeno $1 - \delta$, ogni ipotesi $h \in H$ soddisfa

$$error_{true}(h) \;\leq\; error_{\mathcal{D}}(h) + \sqrt{\frac{VC(H)\left( \ln \frac{2N}{VC(H)} + 1 \right) + \ln \frac{4}{\delta}}{N}}$$

La lettura è la stessa della sezione 4.4: errore di training più un termine di complessità che cresce con $VC(H)$ e si riduce con $N$, con il minimo del bound in corrispondenza della complessità giusta per i dati disponibili. Questa disuguaglianza è la base concettuale della structural risk minimization (SRM): invece di minimizzare solo l’errore empirico (primo termine), si può scegliere il modello minimizzando l’intero lato destro, cioè la somma di errore empirico e penalità di complessità. È la giustificazione teorica di ciò che nella pratica si fa con la regolarizzazione e con la selezione del modello: pagare un po’ di errore sul training in cambio di un modello più semplice, se questo riduce il bound complessivo sull’errore vero.

7.3 Conseguenze pratiche#

Dai bound con la VC dimension discendono alcune conclusioni operative che è bene fissare:

• La complessità va commisurata ai dati. A parità di dati $N$, aumentare $VC(H)$ allarga il termine di scarto tra errore di training ed errore vero: un modello più capace dà garanzie più deboli. Il rapporto rilevante è $VC(H)/N$: finché è piccolo, l’errore di training è un indicatore affidabile; quando si avvicina a 1, il training error non dice più nulla.
• I bound sono strumenti di confronto, non oracoli. Le maggiorazioni usate nelle dimostrazioni (union bound su tutto lo spazio, caso peggiore su ogni ipotesi) rendono i numeri assoluti molto pessimistici. Il valore dei bound sta nelle dipendenze funzionali: come scala il fabbisogno di dati con la complessità, con l’accuratezza, con la confidenza.
• La VC dimension permette di confrontare modelli con spazi infiniti. La regressione logistica in $M$ dimensioni ($VC = M + 1$) e una rete neurale profonda hanno entrambe $|H| = \infty$, ma VC dimension molto diverse: la teoria recupera l’intuizione che la seconda è più complessa e richiede più dati.

In parole semplici: la teoria conferma con formule un principio che nel corso è già emerso ovunque: più il modello è potente, più dati servono per fidarsi di quello che ha imparato. La VC dimension è il “numero magico” che quantifica la potenza del modello, e i bound dicono quanto conto in dati presenta.

8. Guida d’esame: calcolare la VC dimension passo-passo#

Gli esercizi d’esame su questo capitolo sono tipicamente di due specie: dimostrare che una certa famiglia di ipotesi ha $VC(H) = d$, e applicare i bound numerici. Questa sezione fissa il metodo e lo esercita.

8.1 La strategia in due mosse#

Dimostrare $VC(H) = d$ richiede sempre due dimostrazioni separate, con quantificatori opposti:

1. Lower bound ($VC(H) \geq d$): esibire un insieme specifico di $d$ punti e mostrare che tutte le sue $2^d$ dicotomie sono realizzabili da qualche ipotesi di $H$. Qui si ha piena libertà nella scelta dei punti: conviene sceglierli nella posizione più comoda possibile.
2. Upper bound ($VC(H) < d + 1$): mostrare che per ogni insieme di $d + 1$ punti esiste almeno una dicotomia che nessuna ipotesi di $H$ può realizzare. Qui la libertà scompare: l’argomento deve coprire tutte le configurazioni possibili di $d+1$ punti, tipicamente distinguendo un numero finito di casi geometrici.

La parte difficile è quasi sempre l’upper bound, perché richiede un ragionamento universale invece dell’esibizione di un esempio.

8.2 Esercizio svolto: soglie sulla retta ($VC = 1$)#

Spazio delle ipotesi: $H = \{ h_\theta : h_\theta(x) = 1 \text{ se } x \geq \theta, \; 0 \text{ altrimenti}, \; \theta \in \mathbb{R} \}$, i classificatori a soglia sulla retta reale con orientamento fisso (positivi a destra).

Lower bound ($VC \geq 1$): si prenda un punto qualsiasi, per esempio $x_1 = 0$. Le dicotomie sono 2: per etichettarlo positivo si sceglie $\theta = -1$ (infatti $0 \geq -1$); per etichettarlo negativo si sceglie $\theta = 1$. Entrambe le dicotomie sono realizzate, quindi il punto è shattered.

Upper bound ($VC < 2$): si prendano due punti qualsiasi $x_1 < x_2$ e si consideri la dicotomia $(+, -)$, cioè $x_1$ positivo e $x_2$ negativo. Per avere $h_\theta(x_1) = 1$ serve $\theta \leq x_1$; ma allora $\theta \leq x_1 < x_2$ implica $h_\theta(x_2) = 1$: impossibile etichettare $x_2$ negativo. La dicotomia è irrealizzabile per qualunque coppia di punti (l’argomento usa solo $x_1 < x_2$, che vale sempre a meno di rinominare i punti), quindi nessun insieme di 2 punti è shattered.

Conclusione: $VC(H) = 1$.

8.3 Esercizio svolto: intervalli sulla retta ($VC = 2$)#

Spazio delle ipotesi: $H = \{ h_{a,b} : h_{a,b}(x) = 1 \text{ se } a \leq x \leq b, \; 0 \text{ altrimenti} \}$, i classificatori che etichettano come positivi i punti dentro un intervallo $[a, b]$.

Lower bound ($VC \geq 2$): si prendano $x_1 = 0$ e $x_2 = 1$. Le 4 dicotomie sono tutte realizzabili: $(+,+)$ con l’intervallo $[-1, 2]$ che li contiene entrambi; $(-,-)$ con l’intervallo $[5, 6]$ che non ne contiene nessuno; $(+,-)$ con $[-0.5, 0.5]$ che contiene solo $x_1$; $(-,+)$ con $[0.5, 1.5]$ che contiene solo $x_2$. L’insieme è shattered.

Upper bound ($VC < 3$): si prendano tre punti qualsiasi $x_1 < x_2 < x_3$ e si consideri la dicotomia $(+, -, +)$. Un intervallo che contiene $x_1$ e $x_3$ contiene, per definizione di intervallo, ogni punto compreso tra essi, quindi anche $x_2$: la dicotomia è irrealizzabile per qualunque terna di punti.

Conclusione: $VC(H) = 2$. Si noti il pattern: la dicotomia “assassina” per gli intervalli è quella alternata, che sfrutta il vincolo strutturale della famiglia (la convessità dell’intervallo). Come utile generalizzazione da provare per esercizio: l’unione di $k$ intervalli disgiunti ha $VC = 2k$, perché $2k$ punti alternati si coprono con $k$ intervalli, ma $2k + 1$ punti con etichette alternate a partire dal positivo richiederebbero $k + 1$ intervalli.

8.4 Esercizio svolto: classificatore lineare in 2D ($VC = 3$)#

È l’esempio guida della sezione 6.4, riorganizzato nello schema d’esame.

Lower bound ($VC \geq 3$): si scelgono 3 punti non allineati (per esempio $(0,0)$, $(1,0)$, $(0,1)$). Per ciascuna delle 8 dicotomie si esibisce una retta separatrice: etichette tutte uguali, retta esterna al triangolo; un punto diverso dagli altri due, retta che taglia tra quel punto e il lato opposto. Tutte le dicotomie sono realizzabili.

Upper bound ($VC < 4$): per ogni insieme di 4 punti si distinguono i casi: se un punto è interno al guscio convesso degli altri (o tre punti sono allineati), la dicotomia “guscio positivo, interno negativo” è irrealizzabile per convessità dei semipiani; se i punti sono in posizione convessa, la dicotomia alternata sulle diagonali (XOR) è irrealizzabile perché i segmenti che uniscono le coppie omologhe si intersecano.

Conclusione: $VC(H) = 3$, e in generale $M + 1$ in dimensione $M$.

8.5 Errori tipici da evitare#

• Verificare solo alcune dicotomie nel lower bound. Per dimostrare lo shattering bisogna coprire tutte le $2^d$ etichettature, non solo quelle “difficili”; per simmetria si possono raggruppare i casi, ma il conto deve tornare a $2^d$.
• Confondere i quantificatori. Trovare un insieme di $d+1$ punti non shatterabile non dimostra $VC < d + 1$: per esempio 3 punti allineati non sono shatterabili da una retta (la dicotomia alternata fallisce), ma la VC del classificatore lineare 2D è comunque 3, perché basta che esista un altro insieme di 3 punti (non allineati) shattered. Il lower bound chiede “esiste un insieme”, l’upper bound chiede “per ogni insieme”.
• Scegliere punti degeneri nel lower bound. Punti coincidenti o in configurazioni degeneri (allineati, quando la geometria lo punisce) rendono impossibile lo shattering: nel lower bound conviene sempre scegliere punti in posizione generale.
• Dimenticare metà della dimostrazione. “$VC(H) = d$” senza l’upper bound vale metà dei punti: mostrare l’insieme shattered prova solo $VC \geq d$.

8.6 Esercizi numerici sui bound#

Esercizio 1 (sample complexity, caso consistente). Congiunzioni booleane su $M = 20$ variabili; si vuole confidenza 95% ($\delta = 0.05$) ed errore massimo $\varepsilon = 0.1$. Quanti campioni servono?

Soluzione

Lo spazio delle ipotesi ha $|H| = 3^{20}$ (per ogni variabile: 0, 1 oppure “?”), quindi con la formula della sample complexity:

$$N \;\geq\; \frac{1}{0.1} \left( \ln 3^{20} + \ln \frac{1}{0.05} \right) = 10 \cdot (21.97 + 3.00) \approx 250$$

Esercizio 2 (bound sull’errore, caso consistente). Stesso spazio di ipotesi, ma sono disponibili $N = 1000$ campioni e si vuole confidenza 99%. Quale errore vero si può garantire per un’ipotesi consistente?

Soluzione

$$\varepsilon \;\geq\; \frac{1}{1000} \left( 20 \ln 3 + \ln 100 \right) = \frac{21.97 + 4.61}{1000} \approx 0.027$$

Con probabilità almeno 99%, l’errore vero non supera circa il 2.7%.

Esercizio 3 (sample complexity con VC dimension). Classificatore lineare in 2D, quindi $VC(H) = 3$; si vuole $\varepsilon = 0.1$ e $\delta = 0.05$ per un learner consistente.

Soluzione

Si applica il bound della sezione 7.1:

$$N \;\geq\; \frac{1}{0.1} \left( 4 \log_2 \frac{2}{0.05} + 8 \cdot 3 \cdot \log_2 \frac{13}{0.1} \right) = 10 \cdot (4 \cdot 5.32 + 24 \cdot 7.02) \approx 1900$$

Il numero è volutamente conservativo (i bound VC sono ancora più pessimistici di quelli finiti), ma mostra il meccanismo: raddoppiando la VC dimension il fabbisogno di campioni cresce circa linearmente.

Glossario#

Dispensa Machine Learning · Politecnico di Milano