Nei capitoli precedenti è comparsa più volte la stessa avvertenza: un modello che sbaglia poco sui dati di training non è necessariamente un buon modello, e la valutazione onesta richiede dati freschi. Questo capitolo trasforma quell’avvertenza in una teoria e in una cassetta degli attrezzi. La teoria è la bias-variance decomposition (decomposizione bias-varianza): una scomposizione esatta dell’errore atteso di un modello in tre contributi (rumore, bias, varianza) che spiega perché esiste un compromesso tra semplicità e flessibilità, perché la regolarizzazione funziona e perché più dati aiutano sempre. La cassetta degli attrezzi è la pratica della valutazione e selezione dei modelli: training, validation e test set, cross-validation, criteri aggiustati per la complessità, e le tecniche per ridurre la varianza riducendo la dimensionalità (feature selection, Principal Component Analysis o PCA). Il capitolo si chiude con i metodi ensemble, bagging e boosting, che provano ad aggirare il compromesso combinando più modelli, e con una ricca sezione di esercizi d’esame svolti, incluse le domande vero/falso più ricorrenti.

Riferimenti sul testo: Bishop, Pattern Recognition and Machine Learning [PRML], sezioni 3.2, 12.1, 14.2, 14.3; Hastie et al., Elements of Statistical Learning [ESL], sezioni 7.3 e 3.3; James et al., Introduction to Statistical Learning [ISL], sezioni 5.1 e 6.1.3.

1. Da dove viene l’errore di un modello#

1.1 La domanda giusta: errore su quali dati?#

Dato un dataset $\mathcal{D} = \{(\mathbf{x}_i, t_i)\}_{i=1}^N$ e un modello $\hat{t}_i = y(\mathbf{x}_i)$, come si sceglie tra più modelli candidati? La tentazione immediata è usare la loss function (funzione di perdita) calcolata su $\mathcal{D}$: per la regressione, ad esempio, la somma dei quadrati dei residui $RSS_y = \sum_{(\mathbf{x}_i, t_i) \in \mathcal{D}} (t_i - y(\mathbf{x}_i))^2$. Ma questa non è la quantità che interessa. La quantità che interessa è l’errore che il modello commetterà sui dati futuri, cioè l’errore atteso sull’intera distribuzione che genera i dati; con loss quadratica:

$$\mathbb{E}_{(\mathbf{x}, t) \sim p(\mathbf{x}, t)} \big[ (t - y(\mathbf{x}))^2 \big]$$

Il problema è che la distribuzione congiunta $p(\mathbf{x}, t)$ non è nota: se lo fosse, non ci sarebbe nulla da imparare. Tutto il capitolo ruota attorno a due domande: come si scompone questo errore atteso (parte teorica), e come lo si stima senza conoscere $p$ (parte pratica).

1.2 Rischio di popolazione e rischio empirico#

Per capire perché il training error inganna conviene distinguere due problemi di minimizzazione, uno ideale e uno reale.

La differenza cruciale è di natura statistica: $\hat{y}$ è una variabile aleatoria, perché dipende dal training set, che è a sua volta un campione casuale della distribuzione. Con un altro dataset, generato dallo stesso processo, si otterrebbe un $\hat{y}$ diverso. Il minimizzatore di popolazione $y^*$, invece, non dipende da alcun campione ed è sempre lo stesso.

Un esempio sintetico rende tutto tangibile. Si generino i dati con $t = f(x) + \varepsilon$, dove $f$ è una parabola nota e $\varepsilon$ è rumore a media nulla con deviazione standard $\sigma = 0.7$. Si considerino due spazi di ipotesi: $\mathcal{H}_1$, i modelli lineari $y = a + bx$, e $\mathcal{H}_2$, i modelli quadratici $y = a + bx + cx^2$. Entrambi sono modelli lineari nei parametri (basta usare i vettori di feature $(1, x)$ e $(1, x, x^2)$), e $\mathcal{H}_1 \subset \mathcal{H}_2$: basta porre $c = 0$. Risolvendo il problema di popolazione, il miglior quadratico ha esattamente i coefficienti di $f$ (perché $f \in \mathcal{H}_2$), mentre il miglior lineare è un compromesso che non potrà mai coincidere con la parabola. Ripetendo invece la minimizzazione empirica su tanti dataset diversi generati dallo stesso processo si osservano due fatti:

• i minimizzatori empirici si distribuiscono come una nuvola di punti nello spazio dei parametri, centrata attorno al corrispondente minimizzatore di popolazione, che invece non si muove mai;
• ripetendo l’esperimento 100 volte con dataset di 100 campioni la nuvola è larga, con dataset da 10.000 campioni la nuvola è stretta: la media campionaria calcolata su pochi dati è uno stimatore poco affidabile dell’attesa vera, su molti dati è affidabile.

In parole semplici: il modello che si impara dai dati è esso stesso “casuale”: cambia dataset, cambia modello. Con pochi dati questa casualità è grande, con molti dati si riduce. La teoria che segue misura esattamente quanto questa casualità, sommata ai limiti strutturali del modello e al rumore, costa in termini di errore.

1.3 La bias-variance decomposition: derivazione#

Idea chiave: l’errore quadratico atteso di un modello su un punto si scompone esattamente in tre pezzi: il rumore intrinseco dei dati (irriducibile), il quadrato del bias (quanto il modello medio sbaglia rispetto alla funzione vera) e la varianza (quanto il modello ballerà da dataset a dataset).

Le assunzioni del framework sono:

• Dati: $t = f(\mathbf{x}) + \varepsilon$, con $\mathbb{E}[\varepsilon] = 0$ e $\text{Var}[\varepsilon] = \sigma^2$; il rumore è indipendente da campione a campione.
• Modello: $\hat{t} = y(\mathbf{x})$, appreso da un dataset campionato $\mathcal{D}$ (quindi $y$ è aleatorio tramite $\mathcal{D}$).
• Prestazione: l’errore quadratico atteso $\mathbb{E}\big[(t - y(\mathbf{x}))^2\big]$, dove l’attesa è presa sia rispetto ai possibili training set $\mathcal{D}$ sia rispetto alla variabilità del target dato l’input.

Si fissi un punto $\mathbf{x}$ (non aleatorio) e si indichi con $\bar{y}(\mathbf{x}) = \mathbb{E}_{\mathcal{D}}[y(\mathbf{x})]$ il modello medio: la predizione media che si otterrebbe addestrando il modello su infiniti dataset indipendenti e mediando le predizioni. La derivazione usa due volte lo stesso trucco: aggiungere e togliere una quantità e sviluppare il quadrato. Primo passo, si aggiunge e toglie $f(\mathbf{x})$:

$$\mathbb{E}\big[(t - y(\mathbf{x}))^2\big] = \mathbb{E}\big[(t - f(\mathbf{x}) + f(\mathbf{x}) - y(\mathbf{x}))^2\big] = \mathbb{E}\big[(t - f(\mathbf{x}))^2\big] + \mathbb{E}\big[(f(\mathbf{x}) - y(\mathbf{x}))^2\big] + 2\,\mathbb{E}\big[(t - f(\mathbf{x}))(f(\mathbf{x}) - y(\mathbf{x}))\big]$$

Il termine misto si annulla: $t - f(\mathbf{x}) = \varepsilon$ è rumore a media nulla, indipendente dal modello appreso (che è funzione degli altri campioni). Il primo termine è $\mathbb{E}[\varepsilon^2] = \sigma^2$. Secondo passo, nel termine rimanente si aggiunge e toglie il modello medio $\bar{y}(\mathbf{x})$:

$$\mathbb{E}\big[(f(\mathbf{x}) - \bar{y}(\mathbf{x}) + \bar{y}(\mathbf{x}) - y(\mathbf{x}))^2\big] = \big(f(\mathbf{x}) - \bar{y}(\mathbf{x})\big)^2 + \mathbb{E}_{\mathcal{D}}\big[(y(\mathbf{x}) - \bar{y}(\mathbf{x}))^2\big]$$

dove anche qui il doppio prodotto sparisce, perché $f(\mathbf{x}) - \bar{y}(\mathbf{x})$ è una costante e $\mathbb{E}_{\mathcal{D}}[\bar{y}(\mathbf{x}) - y(\mathbf{x})] = 0$ per definizione di $\bar{y}$.

In parole semplici: l’errore futuro di un modello ha tre cause. Primo: i dati stessi sono rumorosi, e su questo nessun modello può fare nulla. Secondo: la famiglia di modelli scelta può essere strutturalmente incapace di rappresentare la verità (bias), come una retta che insegue una parabola. Terzo: il modello appreso balla da dataset a dataset (varianza), e in media questo ballare costa errore. La formula dice che questi tre contributi si sommano, esattamente.

1.4 Lettura dei tre termini#

Ogni termine ha leve di controllo diverse, ed è qui che la decomposizione diventa operativa.

• Rumore ($\sigma^2$): è la varianza intrinseca dei dati, detta errore irriducibile. Non dipende né dal campionamento del dataset né dalla complessità del modello: nessuna scelta di modello lo può ridurre.
• Bias: misura la distanza tra la verità $f$ e ciò che ci si aspetta di imparare, $\mathbb{E}_{\mathcal{D}}[y(\mathbf{x})]$. Dipende solo dallo spazio di ipotesi, non dal numero di campioni: diminuisce (o al più resta uguale) con modelli più complessi, perché uno spazio più ricco può rappresentare funzioni più vicine a $f$. Nell’esempio della sezione 1.2, $\mathcal{H}_2$ (quadratici) ha bias nullo perché contiene $f$; $\mathcal{H}_1$ (lineari) ha bias positivo.
• Varianza: misura quanto il minimizzatore empirico cambia al cambiare del dataset. Diminuisce con modelli più semplici e diminuisce con più campioni. Il caso estremo è illuminante: se lo spazio di ipotesi contiene una sola funzione, la varianza è zero, perché qualunque sia il dataset si “impara” sempre quella funzione (e tutto l’errore riducibile è bias).

1.5 Il tradeoff e la definizione precisa di overfitting e underfitting#

Idealmente si vorrebbero bias basso e varianza bassa, ma le due leve tirano in direzioni opposte: aumentare la complessità del modello riduce il bias e aumenta la varianza; ridurla fa l’opposto. L’errore di predizione, somma dei due contributi più il rumore, ha quindi rispetto alla complessità la classica forma a U: prima scende (domina la riduzione del bias), raggiunge un minimo, poi risale (domina l’esplosione della varianza). Il framework permette di dare finalmente definizioni precise ai due termini usati finora in modo intuitivo.

Scegliere un modello in machine learning significa negoziare questo compromesso, e la scelta ottima dipende da due fattori: quanti dati si hanno (che governano la varianza) e quanto è complessa la funzione da rappresentare (che governa il bias).

In parole semplici: un modello potente impara benissimo i singoli dataset ma “cambia idea” a ogni campione: è instabile, e l’instabilità in media si paga. Un modello povero è stabilissimo ma sbaglia sempre nello stesso modo. Né l’uno né l’altro estremo minimizza l’errore futuro: il punto giusto sta in mezzo, e dove esattamente dipende da quanti dati ci sono.

Va infine detto che questo è un modello teorico: con dati reali non si conoscono né $f$ né $\sigma^2$, quindi bias e varianza non si possono calcolare davvero, salvo eccezioni notevoli. La sezione 2 mostra una di queste eccezioni e una rilettura importante; la sezione 3 affronta il problema pratico.

2. Il tradeoff in azione: due casi di studio#

2.1 Bias e varianza per K-NN#

Il metodo K-nearest neighbors (K-NN) è uno dei pochi per cui la decomposizione si calcola esplicitamente. L’idea del metodo: non c’è una fase di addestramento vera e propria, il “modello” è il dataset stesso. Per predire su un punto nuovo si cercano i $K$ campioni più vicini nel dataset; in classificazione si vota a maggioranza tra le loro classi (con $K = 3$ e vicini di classi triangolo, triangolo, stella, la risposta è triangolo), in regressione si media il loro target:

$$y(\mathbf{x}) = \frac{1}{K} \sum_{k=1}^{K} t_{(k)}$$

dove $\mathbf{x}_{(1)}, \dots, \mathbf{x}_{(K)}$ sono i $K$ vicini di $\mathbf{x}$. Per la regressione con loss quadratica il conto (svolto su ESL, capitolo 7.3) dà:

$$\mathbb{E}\big[(t - y(\mathbf{x}))^2\big] \;=\; \sigma^2 \;+\; \underbrace{\frac{\sigma^2}{K}}_{\text{varianza}} \;+\; \underbrace{\left( f(\mathbf{x}) - \frac{1}{K} \sum_{k=1}^{K} f(\mathbf{x}_{(k)}) \right)^{2}}_{\text{bias}^2}$$

La lettura dei termini rende visibile il tradeoff governato dall’unico parametro $K$:

• il rumore $\sigma^2$ è l’errore irriducibile, come sempre;
• la varianza vale $\sigma^2 / K$ e decresce al crescere di $K$: con un vicinato piccolo ($K = 3$) basta che cambi un solo punto del dataset perché la predizione cambi; con un vicinato grande ($K = 11$) un singolo punto sposta poco la media;
• il bias è la differenza tra $f$ nel punto e la media di $f$ sui vicini, e in generale cresce al crescere di $K$: allargando il vicinato si includono punti sempre più lontani, la cui $f$ può non essere rappresentativa del punto di interesse. Quanto cresce dipende dalla regolarità del problema: se $f$ è liscia il bias cresce poco, se $f$ varia rapidamente cresce molto.

Su un dataset sintetico (dove $f$ e $\sigma$ sono noti) questa formula permette addirittura di predire il valore ottimo di $K$. C’è anche una lettura più generale: $K$ agisce da iperparametro di regolarizzazione. Con $K = 1$ il decision boundary (confine di decisione) è irregolarissimo e insegue ogni punto (anche il rumore: se ci sono punti sovrapposti di classi diverse, l’accuratezza di training di 1-NN non è nemmeno 1); aumentando $K$ le decision region (regione di decisione) diventano via via più regolari, esattamente come aumentare $\lambda$ liscia la soluzione di una ridge regression.

In parole semplici: K-NN risponde “guarda i tuoi K vicini e copia loro”. Con pochi vicini si è reattivi ma nervosi (alta varianza), con molti vicini si è stabili ma si ascoltano anche punti lontani e fuorvianti (alto bias). Il K giusto bilancia le due cose, ed è a tutti gli effetti la manopola della complessità del metodo.

2.2 Perché la regolarizzazione funziona: ridge e lasso riletti#

Nel capitolo sulla regressione lineare la regolarizzazione era stata motivata dal sintomo (pesi che esplodono), non dalla causa. La decomposizione fornisce la spiegazione vera: il coefficiente $\lambda$ controlla il tradeoff bias-varianza. Più forte è la regolarizzazione, più il modello è vincolato, quindi meno probabile è che una piccola variazione nei dati produca un modello drasticamente diverso: la varianza decresce al crescere di $\lambda$. In cambio, il vincolo impedisce al modello di catturare completamente la relazione nei dati: il bias cresce. Esiste quindi un valore intermedio ottimo di $\lambda$, che minimizza la somma dei due contributi ed è il valore che la model selection (selezione del modello) dovrà trovare.

Un esperimento sintetico confronta ridge e lasso al variare della forza di regolarizzazione, tracciando bias, varianza ed errore totale atteso:

• con 45 feature su 45 tutte correlate al target, le curve di ridge e lasso sono quasi sovrapposte: il tradeoff c’è per entrambe e nessuna delle due domina;
• con 2 sole feature rilevanti su 45 (le altre 43 sono puro rumore), il lasso batte nettamente la ridge. Il motivo è la sparsità: nella ridge sia la loss sia la penalità sono forme quadratiche, e il compromesso tra le due contrae tutti i pesi verso zero circa alla stessa velocità, senza mai riuscire a “spegnere” una feature prima delle altre; nel lasso i pesi decrescono a velocità diverse e i pesi delle feature irrilevanti vanno esattamente a zero molto in fretta. Il lasso realizza quindi una selezione automatica delle feature e arriva prima a un modello a bassa varianza che conserva l’informazione utile.

In parole semplici: regolarizzare significa comprare stabilità pagando in fedeltà: il modello balla meno da dataset a dataset (meno varianza) ma è un po’ meno capace di seguire la relazione vera (più bias). Se poi molte feature sono spazzatura, il lasso è la scelta giusta perché le azzera una per una, mentre la ridge le tiene tutte in vita, solo più piccole.

3. Misurare onestamente l’errore: training, validation, test e cross-validation#

3.1 Il training error e perché mente#

In pratica bias e varianza non si calcolano; ciò che si calcola facilmente è il training error: la loss (o una metrica sensata) valutata sui dati di addestramento. Per la regressione, tipicamente la somma o media dei quadrati dei residui; per la classificazione, la frazione di punti mal classificati:

$$L_{train}^{reg} = \frac{1}{N} \sum_{n=1}^{N} \big( t_n - y(\mathbf{x}_n) \big)^2, \qquad L_{train}^{class} = \frac{1}{N} \sum_{n=1}^{N} \mathbb{1}\big( t_n \neq y(\mathbf{x}_n) \big)$$

Il comportamento del training error rispetto alla complessità del modello è del tutto prevedibile: decresce monotonicamente. Il motivo è strutturale: se $\mathcal{H}_1 \subset \mathcal{H}_2$ (per esempio polinomi di grado 3 dentro polinomi di grado 4), tutto ciò che rappresenta il modello semplice lo rappresenta anche il complesso, che in più può fare altro; minimizzando la stessa loss sugli stessi dati in uno spazio più grande, il minimo non può che scendere. Spingendo la complessità abbastanza in alto (per esempio un polinomio di grado pari al numero di punti, o un decision tree (albero di decisione) senza vincoli di profondità) si arriva a training error zero. Scegliere il modello con il training error minimo selezionerebbe quindi sempre il modello più complesso disponibile: una ricetta certa per l’overfitting.

La ragione statistica profonda è quella vista nella sezione 1.2: il minimizzatore empirico $\hat{y}$ è statisticamente dipendente dal training set da cui è stato calcolato. Valutare $\hat{y}$ sugli stessi dati che lo hanno prodotto non fornisce uno stimatore non distorto dell’errore atteso: è come far correggere il compito allo studente che lo ha scritto.

Idea chiave: se si addestra su un dataset, ogni conclusione sulla qualità del modello va tratta su un altro dataset, identicamente distribuito ma statisticamente indipendente. Ogni volta che un insieme di dati viene usato per fare una scelta, l’errore misurato su quell’insieme smette di essere una stima affidabile.

3.2 Il test error#

La soluzione pratica minima: dividere casualmente i dati in un training set, usato per ottimizzare i parametri, e un test set, usato per stimare l’errore di predizione con la stessa metrica (RSS media in regressione, tasso di errore o accuratezza in classificazione). Tracciando training error e test error rispetto alla complessità si osserva il quadro atteso: il training error scende sempre; il test error ha la forma a U prevista dalla teoria, prima scende (il bias cala), poi risale (la varianza esplode). Nell’esempio della selezione del grado di un polinomio, il minimo della curva di test cade su un grado intermedio (per esempio 6), non sul massimo.

Un dettaglio da non dimenticare: la curva del test error è rumorosa. È una stima calcolata su un campione finito, spesso piccolo: a volte per fortuna sta sotto l’errore vero, a volte sopra, e non si sa mai da che parte. Questa osservazione apparentemente innocua è la chiave della sezione 3.4.

3.3 Curve di apprendimento: diagnosticare alto bias e alta varianza#

Prima di arrivare alla model selection, il confronto tra training error e test error offre uno strumento diagnostico potente: le curve di errore in funzione della quantità di dati di training $N$, a complessità fissata. I comportamenti di base:

• il training error cresce con $N$: fittare perfettamente pochi punti è facile, fittarne molti richiede compromessi, quindi i residui aumentano;
• il test error decresce con $N$: più dati riducono la varianza del modello appreso;
• le due curve convergono: al limite di infiniti dati di training, l’errore di training coincide per definizione con l’errore di predizione, perché il modello è stato addestrato e valutato su “tutti i dati possibili”.

Dalla forma delle curve si diagnostica il regime in cui si trova il modello:

• Alta varianza (overfitting): il training error è più basso di quanto ci si aspetterebbe e resta un divario ampio e persistente tra training e test error, che si chiude solo lentamente. Rimedi: usare un modello più semplice (ridurre la varianza), oppure procurarsi più dati, cosa raramente possibile nel mondo reale dove si stanno già usando tutti i dati disponibili.
• Alto bias (underfitting): training e test error sono vicini tra loro ma entrambi più alti del livello di errore desiderato: la curva di training raggiunge presto quella di test, su un plateau insoddisfacente. Rimedio: usare un modello più complesso per abbattere il bias; aggiungere dati non serve, perché il problema non è la varianza. Si noti la formulazione corretta: l’obiettivo è ridurre il bias, non “aumentare la varianza”; l’aumento di varianza è il prezzo collaterale, non lo scopo.

In parole semplici: le due curve sono la radiografia del modello. Se c’è un grosso buco tra “quanto sbaglio sui miei dati” e “quanto sbaglio su dati nuovi”, il modello sta imparando a memoria: serve semplificarlo o dargli più esempi. Se le due curve si incollano presto ma in alto, il modello è troppo povero: serve più potenza, e altri dati non aiuteranno.

3.4 Perché il test set non basta: il validation set#

In pratica la model selection si fa così: si addestrano più versioni del modello a complessità crescente (o proprio modelli diversi: rete neurale, albero, K-NN, regressione logistica, oppure lo stesso modello con diversi valori di $\lambda$ o di altri iperparametri come $\alpha$) e si sceglie quella con l’errore stimato minimo. La domanda è: si può usare il test error per questa scelta? La risposta è no, per un motivo sottile e importantissimo.

La stima su un insieme finito è rumorosa: ogni modello confrontato corrisponde a un punto sulla curva rumorosa, a volte sotto la curva vera, a volte sopra. Scegliendo il minimo tra questi punti, si seleziona con probabilità sproporzionata un punto in cui la stima sottostima l’errore vero: il minimo di stime rumorose è sistematicamente ottimista. Se il processo dice “il migliore tra i cinque modelli è il modello 3 con il 90% di accuratezza”, quel 90% è con alta probabilità una sovrastima della vera accuratezza del modello 3. In altre parole, usando il test set per scegliere lo si sta parzialmente overfittando: la stima finale non è più non distorta, perché quei dati sono stati usati per prendere una decisione. E a quel punto non resta alcun dato “pulito” per la valutazione finale.

Idea chiave: servono due insiemi di dati separati dal training set, con ruoli diversi: uno per scegliere (validation set) e uno, mai toccato prima, per valutare una sola volta il modello scelto (test set). Solo un insieme mai usato né per addestrare né per selezionare fornisce una stima non distorta dell’errore di predizione.

La procedura standard con tre insiemi (uno split tipico, non scolpito nella pietra, è 50% / 25% / 25%):

1. Training set: si usano questi dati per apprendere i parametri di ciascun modello candidato (diverse feature, diversi iperparametri, diverse famiglie).
2. Validation set: per ogni modello appreso si calcola l’errore su questi dati (validation error) e si seleziona il modello con validation error minimo. Attenzione al nome: contrariamente all’uso comune della parola, la validazione non è l’ultima cosa che si fa, è lo strumento della model selection.
3. Test set: si valuta solo il modello selezionato, una sola volta, su questi dati: il test error risultante è la stima finale e non distorta della sua qualità.

Due debolezze rimangono. Primo, per essere affidabile il validation set deve essere abbastanza grande, e quei dati sono sottratti al training. Secondo, confrontando molti modelli si può overfittare anche il validation set, finendo per non scegliere davvero il migliore: la scelta resta basata su una stima rumorosa. Sul primo problema interviene la cross-validation.

In parole semplici: i dati vanno divisi in tre mucchi con tre mestieri: imparare, scegliere, giudicare. Chi impara non può scegliersi il voto; chi sceglie consuma l’imparzialità dei suoi dati nel momento stesso in cui sceglie; il giudizio finale spetta a dati che non hanno mai visto nulla. Riutilizzare il giudice per fare scelte corrompe il verdetto.

3.5 Cross-validation: leave-one-out e k-fold#

Il difetto del validation set singolo è che la selezione poggia su una stima troppo rumorosa, calcolata su pochi dati e su un’unica spartizione fortuita. L’idea della cross-validation è ripetere il ciclo train/validation più volte, cambiando ogni volta quali dati fanno da training e quali da validazione, e mediare: la media di tante stime rumorose è molto meno rumorosa di una singola stima.

Leave-one-out (LOO). La versione estrema: il “validation set” è un singolo campione, e il processo si ripete per tutti i campioni.

L’obiezione naturale (“valutare un modello su un solo punto è rumorosissimo”) è disinnescata dalla ripetizione: la media su $N$ prove compensa il rumore delle singole. La stima LOO è quasi non distorta e leggermente pessimistica: ogni modello è addestrato su $N - 1$ campioni invece che $N$, quindi è marginalmente peggiore del modello finale, ma l’effetto è trascurabile per $N$ grande. Il problema di LOO è il costo: richiede $N$ addestramenti completi. Anche se un singolo addestramento durasse un solo secondo, con 100.000 campioni servirebbero 100.000 secondi, più di un giorno.

K-fold cross-validation. Il compromesso standard: messo da parte il test set, il resto dei dati si divide casualmente in $k$ fold (blocchi) $\mathcal{D}_1, \dots, \mathcal{D}_k$; valori tipici sono $k = 10$, o $k = 5$ se le risorse computazionali sono limitate. Per ogni $i$ si addestra il modello su $\mathcal{D} \smallsetminus \mathcal{D}_i$ (gli altri $k-1$ fold) e si calcola l’errore sul fold escluso $\mathcal{D}_i$; la stima finale è la media:

$$L_{k\text{-}fold} = \frac{1}{k} \sum_{i=1}^{k} L_{\mathcal{D}_i}$$

Con $k = 5$, in ogni iterazione l’80% dei dati addestra e il 20% valida; le cinque accuratezze (o RSS) di ogni modello candidato si mediano e si confrontano le medie. Rispetto a LOO la stima è più distorta in senso pessimistico (ogni modello vede solo una frazione $(k-1)/k$ dei dati) ma il costo crolla: $k$ addestramenti invece di $N$. Si noti che LOO è il caso particolare $k = N$. Il compromesso è sempre lo stesso: fold piccoli (fino a LOO) danno selezione più accurata ma costano di più; fold grandi costano meno ma addestrano su meno punti. Con capacità di calcolo parallelo il valore di $k$ può essere alzato, perché i $k$ addestramenti sono indipendenti ed eseguibili in parallelo.

Da ultimo, la selezione può dare risultati diversi a seconda dello stimatore: nello stesso esempio dei polinomi, il minimo del validation error singolo cadeva sul grado 7, quello della cross-validation sul grado 5, mentre il test error aveva il minimo sul grado 6. Non è un errore: sono stime diverse dello stesso oggetto rumoroso, e si rimane vincolati alla scelta fatta dalla procedura scelta.

3.6 Dopo la cross-validation: retraining e impegno sulla scelta#

Un punto pratico spesso trascurato: al termine della cross-validation non esiste “il” modello vincitore già addestrato, ne esistono $k$ versioni (o $N$, con LOO), una per iterazione. La procedura corretta prosegue così:

1. La cross-validation designa il vincitore, per esempio una regressione logistica con $\lambda = 10^{-3}$.
2. Si riaddestra il vincitore su tutto il training data (tutti i fold riuniti): è questo il modello finale.
3. Si valuta il modello riaddestrato una sola volta sul test set: quel numero è la stima finale, statisticamente corretta e non distorta, della sua qualità.

E se il test error finale deludesse? Non si può tornare indietro, provare il secondo classificato e “vedere se va meglio sul test”: si ricadrebbe esattamente nell’errore della sezione 3.4, usando il test set per fare una scelta e distruggendone l’imparzialità. La selezione impegna a una e una sola alternativa; il test set si consuma con un solo utilizzo.

In parole semplici: la cross-validation è il torneo, il retraining su tutti i dati è la preparazione finale del campione, il test set è la finale che si gioca una volta sola. Se il risultato della finale non piace, non si può rigiocarla con un altro concorrente: servirebbe un nuovo stadio, cioè nuovi dati.

3.7 Criteri aggiustati per la complessità#

Se per qualche ragione non ci si può permettere né un validation set né la cross-validation (dati pochissimi, addestramenti costosissimi), la letteratura offre metriche che correggono il training error penalizzandolo in proporzione alla complessità del modello. L’idea comune: un modello complesso avrà un training error ingannevolmente basso, quindi gli si somma una penalità crescente nel numero di parametri $M$; a parità di training error, vince il modello più semplice. Le principali (con $N$ campioni, $M$ parametri, $L$ likelihood (verosimiglianza) massimizzata, $\hat{\sigma}^2$ stima della varianza del rumore):

• $C_p$ di Mallows: $C_p = \dfrac{1}{N}\big( RSS + 2 M \hat{\sigma}^2 \big)$, per la regressione;
• Akaike Information Criterion: $AIC = -2 \ln L + 2M$;
• Bayesian Information Criterion: $BIC = -2 \ln L + M \ln N$;
• Adjusted $R^2$: $\text{Adj-}R^2 = 1 - \dfrac{RSS / (N - M - 1)}{TSS / (N - 1)}$, per la regressione.

AIC e BIC si usano tipicamente quando l’addestramento massimizza una log-likelihood; il BIC penalizza la complessità più dell’AIC (il fattore $\ln N$ supera 2 già per $N > 7$). L’avvertenza è però d’obbligo: queste penalità sono essenzialmente euristiche. Al di fuori di casi specifici non godono di garanzie, e non forniscono la stima statisticamente non distorta che dà una cross-validation ben fatta. Sono molto meglio che scegliere sul training error nudo, ma molto peggio di una validazione vera: vanno considerate l’ultima spiaggia per dataset piccolissimi.

3.8 Quale tecnica in quale scenario#

Il criterio di scelta tra le tecniche dipende da due assi: la dimensione del dataset e il costo computazionale di un singolo addestramento.

• Dataset piccolo, modelli computazionalmente leggeri: leave-one-out. Ci si può permettere $N$ addestramenti, e si ottiene la stima più affidabile possibile addestrando ogni volta sul massimo numero di punti: prezioso proprio quando i dati sono pochi.
• Dataset piccolo, modelli pesanti: criteri aggiustati ($C_p$, AIC, BIC, Adjusted $R^2$). Non ci si può permettere molti addestramenti né sacrificare dati per la validazione: si addestra una volta su tutto e si corregge il training error con la penalità.
• Dataset grande, modelli leggeri: k-fold cross-validation. LOO costerebbe troppo per via di $N$; con abbastanza parallelismo si può alzare $k$, al limite fino a LOO.
• Dataset grande, modelli pesanti: validation set singolo. I dati abbondano, quindi lo split a tre non sacrifica troppo il training; i criteri aggiustati non avrebbero senso potendosi permettere una validazione vera.

In ogni caso, validation e cross-validation servono a scegliere; per la valutazione finale del prescelto serve comunque il test set.

4. La maledizione della dimensionalità#

4.1 Volume, sparsità e dati necessari#

Prima di chiedersi come scegliere le feature, bisogna capire perché averne troppe è un problema. La dimensionalità dello spazio delle feature è una delle cause principali (non l’unica) della varianza di un modello, per un fenomeno con un nome evocativo.

Un esperimento mentale rende il fenomeno concreto. Si prendano dati distribuiti uniformemente e si consideri la regione che copre metà del range di ogni feature:

• in una dimensione, l’intervallo $x \in [0, 0.5]$ su range $[0, 1]$ cattura il 50% dei punti;
• in due dimensioni, il quadrato che copre metà range di $x$ e metà di $y$ cattura il 25%;
• in tre dimensioni il 12.5%, e così via: la frazione di dati catturata si dimezza a ogni dimensione aggiunta, cioè decresce esponenzialmente.

Specularmente, per mantenere la stessa densità di campioni servono esponenzialmente più dati a ogni feature aggiunta. Con la dimensionalità che sale e i dati che restano quelli, lo spazio si svuota: i dati diventano sparsi, le stime locali smettono di essere affidabili e il modello overfitta.

4.2 Più feature non è mai gratis#

Un errore concettuale frequente: “il modello $y = w_0 + w_1 x + w_2 x^2$ è sempre almeno buono quanto $y = w_0 + w_1 x$, perché può sempre porre $w_2 = 0$”. L’argomento dell’inclusione degli spazi di ipotesi ($\mathcal{H}_1 \subset \mathcal{H}_2$) è corretto per il bias e per il training error, ma ignora la varianza: aumentare il numero di feature aumenta la probabilità di overfitting, anche perché i dati disponibili sono gli stessi in uno spazio più grande, dove sono più sparsi. Aggiungere il termine quadratico ha il beneficio di poter catturare relazioni quadratiche, ma ha un costo in varianza: va aggiunto solo se il beneficio supera il costo. Il motto operativo: a parità di prestazioni, scegliere sempre il modello più semplice.

In parole semplici: ogni feature in più allarga lo spazio in cui i dati devono “fare massa”, e i dati non aumentano da soli. Un modello con più feature può sempre imitare quello con meno, quindi sulla carta non perde mai; ma sui dati futuri paga la maggiore libertà con maggiore instabilità. Le feature sono spese, non regali.

Per ridurre la varianza agendo sullo spazio delle feature ci sono tre strade, non mutuamente esclusive e anzi combinabili tra loro:

• Feature selection: scartare le feature meno rilevanti, mantenendo un sottoinsieme di quelle originali (sezione 5);
• Riduzione della dimensionalità: mappare lo spazio di input in uno spazio a dimensione più bassa, usando tutte le feature originali per costruirne di nuove (sezione 6);
• Regolarizzazione: non ridurre la dimensione ma vincolare i parametri, contraendoli verso zero (già vista; con il lasso diventa essa stessa una forma di selezione).

5. Feature selection#

5.1 Best subset selection: la forza bruta impossibile#

Il problema è semplice da enunciare: tra le $M$ feature disponibili, trovare il sottoinsieme che dà il modello con le migliori prestazioni. La soluzione ingenua è esaustiva: per ogni $k = 1, \dots, M$, addestrare tutti i

$$\binom{M}{k} = \frac{M!}{k!\,(M-k)!}$$

modelli con esattamente $k$ feature, valutarli (con una validazione appropriata) e scegliere il migliore. Il totale è $\sum_k \binom{M}{k} = 2^M - 1$ sottoinsiemi: già con poche decine di feature il costo è computazionalmente infattibile, dato che ogni sottoinsieme richiede un addestramento e una valutazione. Servono strategie più furbe, che si dividono in tre famiglie.

5.2 Metodi filter#

Metriche tipiche: per un problema di regressione la correlazione lineare tra la singola feature e il target (si selezionano le feature con correlazione più alta in valore assoluto: una feature con correlazione nulla col target è candidata all’eliminazione); per la classificazione la mutua informazione, che misura il potere discriminante della feature rispetto all’etichetta e cattura anche relazioni non lineari; altre opzioni sono varianza e information gain.

Pregi e difetti sono speculari: i filter sono velocissimi (nessun addestramento, solo statistiche univariate), ma catturano solo parzialmente la relazione tra feature e target e soprattutto ignorano completamente le dipendenze tra feature: non vedranno mai un sottoinsieme di feature che è informativo solo in combinazione, né si accorgeranno che due feature in cima alla classifica portano la stessa informazione. Inoltre non tengono in alcun conto il modello che userà le feature selezionate.

5.3 Metodi wrapper: forward e backward selection#

Rispetto alla forza bruta, i wrapper introducono due semplificazioni. La prima è opzionale: se il modello finale è costosissimo da addestrare (una rete profonda che richiede giorni), lo si può sostituire nella fase di selezione con un modello surrogato più semplice, accettando il rischio di valutare le feature in modo imperfetto pur di rendere la ricerca fattibile. La seconda è strutturale: si rinuncia a esplorare tutti i sottoinsiemi e si procede in modo greedy, prendendo a ogni passo la decisione localmente migliore. Le due strategie classiche:

• Forward stepwise selection: si parte dai sottoinsiemi di una sola feature: si addestra un modello per ciascuna feature ($M$ modelli) e si tiene la migliore, per esempio $x_2$. Poi si prova ad aggiungere a $x_2$ ciascuna delle rimanenti ($M-1$ modelli: $\{x_2, x_1\}$, $\{x_2, x_3\}$, …) e si tiene la coppia migliore; e così via, aggiungendo una feature alla volta finché un criterio d’arresto scatta (per esempio le prestazioni smettono di migliorare).
• Backward stepwise selection: il percorso inverso: si parte dal modello con tutte le feature, si prova a rimuoverne una alla volta (addestrando un modello per ogni feature rimossa), si elimina quella la cui rimozione costa meno (o addirittura giova), e si itera. Esempio tipo: partendo da $\{x_1, x_2, x_3, x_4\}$, la prima iterazione mostra che rimuovere $x_4$ non peggiora l’accuratezza; le iterazioni successive restringono fino a $\{x_2, x_3\}$, dove ogni ulteriore rimozione peggiora le cose, e lì ci si ferma.

Il conto degli addestramenti chiarisce il guadagno: $M + (M-1) + (M-2) + \dots = O(M^2)$ addestramenti invece dei $2^M$ della forza bruta: da esponenziale a quadratico nel numero di feature. Il prezzo è che un algoritmo greedy garantisce solo un ottimo locale: il sottoinsieme trovato può non essere il migliore in assoluto.

5.4 Metodi embedded#

L’esempio canonico è il lasso: la penalità in norma 1 produce soluzioni sparse, e un peso esattamente nullo in un modello lineare equivale ad avere eliminato la feature corrispondente. Anche i decision tree selezionano implicitamente le feature (usano solo quelle su cui conviene fare split). I metodi embedded sono poco costosi (un solo addestramento), ma la selezione che producono è specifica della tecnica usata: le feature scelte dal lasso sono quelle utili a un modello lineare, non necessariamente a un altro modello.

In parole semplici: tre filosofie. Il filter dà un voto a ogni feature da sola, come un provino individuale: rapidissimo ma cieco ai giochi di squadra. Il wrapper prova le squadre vere in campo, aggiungendo o togliendo un giocatore alla volta: costoso ma realistico. L’embedded lascia che sia l’allenamento stesso a tagliare chi non serve, come fa il lasso azzerando i pesi.

6. Riduzione della dimensionalità e PCA#

6.1 Un’idea diversa dalla selezione#

La riduzione della dimensionalità (o feature extraction) condivide l’obiettivo della feature selection, meno dimensioni, ma non il meccanismo: invece di scartare feature originali, cerca una funzione di mappatura dallo spazio di input ad alta dimensione verso uno spazio a dimensione più bassa, le cui coordinate sono feature nuove, costruite combinando (linearmente o non linearmente) tutte quelle originali. Due differenze qualificanti rispetto alla selezione:

• usa tutte le feature originali, che contribuiscono alla costruzione delle nuove;
• è un approccio non supervisionato: la costruzione guarda solo agli input, mai al target.

Le tecniche sono molte (Principal Component Analysis o PCA, ICA, self-organizing maps, autoencoder, ISOMAP, t-SNE, …); la distinzione principale è tra mappature lineari e non lineari. Qui si presenta la più famosa, la Principal Component Analysis (PCA), che è lineare.

6.2 PCA: intuizione e algoritmo#

Idea chiave: trovare un nuovo sistema di assi, combinazioni lineari di quelli originali, ordinati per quantità di varianza dei dati che catturano; tenere solo i primi $k$ assi significa proiettare i dati in $k$ dimensioni perdendo il minimo possibile della loro variabilità.

L’intuizione geometrica: data una nuvola di punti, la prima componente principale è la direzione lungo cui i dati si distendono di più, cioè che cattura la massima varianza; equivalentemente, è la retta che minimizza l’errore commesso sostituendo ogni punto con la sua proiezione su di essa. La seconda componente è la direzione ortogonale alla prima con la seconda varianza più grande, e così via: le componenti sono tutte ortogonali tra loro, e l’operazione complessiva è un semplice cambio di base del sistema di riferimento. La proprietà chiave è l’ordinamento: la varianza catturata decresce di componente in componente, quindi tagliare le ultime componenti butta via poco.

L’algoritmo, per un dataset $\mathbf{X} \in \mathbb{R}^{N \times M}$ ($N$ campioni sulle righe, $M$ feature sulle colonne):

1. Centrare i dati: calcolare $\bar{\mathbf{X}}$ sottraendo da ogni colonna la sua media, così che ogni feature abbia media zero (geometricamente, si porta il baricentro della nuvola nell’origine). Senza questo passo il metodo non funziona.
2. Matrice di covarianza: calcolare $\mathbf{C} = \bar{\mathbf{X}}^T \bar{\mathbf{X}}$, matrice $M \times M$ simmetrica e semidefinita positiva.
3. Autovettori e autovalori: calcolare gli autovettori $\mathbf{e}_1, \dots, \mathbf{e}_M$ di $\mathbf{C}$, ordinati per autovalore decrescente $\lambda_1 \geq \dots \geq \lambda_M \geq 0$. L’autovettore $\mathbf{e}_1$ associato all’autovalore massimo è la prima componente principale, e così via; l’autovalore $\lambda_j$ è la varianza dei dati lungo la componente $j$ (per questo il vettore degli autovalori si chiama anche vettore delle varianze).
4. Trasformazione: raccolti gli autovettori nelle colonne della matrice dei loadings $\mathbf{W} = [\mathbf{e}_1 \,|\, \dots \,|\, \mathbf{e}_M]$, i dati trasformati (detti scores) sono

$$\mathbf{T} = \bar{\mathbf{X}} \, \mathbf{W}$$

Fin qui non c’è riduzione: $\mathbf{T}$ ha le stesse dimensioni $N \times M$ di partenza, è solo il dataset espresso nella nuova base. La trasformazione completa è invertibile: $\mathbf{W}$ è ortogonale (autovettori ortonormali di una matrice simmetrica), quindi $\mathbf{W}^{-1} = \mathbf{W}^T$ e $\bar{\mathbf{X}} = \mathbf{T}\mathbf{W}^T$. La riduzione avviene tenendo solo le prime $k < M$ colonne, $\mathbf{W}_k = [\mathbf{e}_1 \,|\, \dots \,|\, \mathbf{e}_k]$:

$$\mathbf{T}_k = \bar{\mathbf{X}} \, \mathbf{W}_k \in \mathbb{R}^{N \times k}$$

Questa trasformazione non è più invertibile (si è persa informazione, ed è voluto), ma è la migliore possibile nel senso della ricostruzione: la ricostruzione approssimata $\bar{\mathbf{X}} \approx \mathbf{T}_k \mathbf{W}_k^T$ minimizza l’errore di ricostruzione in norma tra tutte le trasformazioni lineari di rango $k$.

In parole semplici: la PCA ruota gli assi per allinearli con le direzioni lungo cui i dati “si allargano” di più, poi tiene solo i primi assi e proietta tutto lì sopra. È come fotografare un oggetto tridimensionale dall’angolazione che ne mostra di più: la foto è 2D, qualcosa si perde, ma si è scelta l’inquadratura che perde meno.

6.3 Quante componenti tenere#

Criteri pratici per scegliere $k$, tutti basati sugli autovalori:

• $k$ fissato a priori, se il vincolo è dimensionale (per esempio per visualizzare in 2D);
• frazione di varianza spiegata cumulata: scegliere il minimo $k$ tale che $\sum_{j \leq k} \lambda_j / \sum_{j} \lambda_j$ superi una soglia, per esempio il 90%;
• soglia sulla singola componente: tenere le componenti la cui frazione di varianza $\lambda_j / \sum_l \lambda_l$ supera per esempio il 5%;
• analisi del gomito (elbow): tracciare la varianza spiegata cumulata in funzione del numero di componenti e fermarsi dove la curva “piega”, cioè dove le componenti successive aggiungono ormai poco. Se la prima componente spiega da sola il 90%, il gomito suggerisce di tenere solo quella.

Sul dataset Iris, per esempio, le prime due componenti principali bastano a separare linearmente le classi in modo pulito, mentre la terza e la quarta non aggiungono praticamente informazione.

6.4 Limiti della PCA (e una trappola sul preprocessing)#

• Linearità: la mappatura è lineare, quindi strutture non lineari nei dati non vengono catturate (per quelle esistono tecniche non lineari come autoencoder o t-SNE).
• Loss di semantica: le feature originali di un problema hanno un significato nel dominio; le componenti principali sono combinazioni lineari di tutte le feature e in generale non hanno un significato leggibile. A volte un’analisi a posteriori riesce a estrarne uno: in un dataset di immagini di volti proiettato con PCA, le nuove variabili catturano direzioni interpretabili come l’orientamento del viso; in un dataset di cifre manoscritte “2”, una componente cattura la presenza del ricciolo nella parte bassa del tratto e un’altra il ricciolo nella parte alta. Ma l’interpretazione non è garantita.
• Non supervisione: la PCA massimizza la varianza degli input, senza guardare il target. Non c’è quindi alcuna garanzia che le direzioni scartate fossero irrilevanti per il problema supervisionato. Il controesempio classico: un problema di classificazione binaria in cui i dati si allungano moltissimo lungo una direzione (che diventa la prima componente) ma le due classi si distinguono solo lungo la direzione ortogonale: proiettando sulla prima componente le classi si mescolano completamente, mentre la seconda componente, quella che la riduzione butterebbe via, è l’unica informativa. In generale il beneficio della riduzione bilancia bene questo rischio, ma il rischio esiste.

Infine una trappola pratica importante: centrare è obbligatorio, standardizzare è pericoloso. Se per “scalare” i dati si intende lo z-score (sottrarre la media e dividere per la deviazione standard), il passo di centratura diventa ridondante ma si è distrutta l’informazione su cui la PCA lavora: dopo lo z-score tutte le feature hanno varianza 1, e le direzioni di massima varianza risultano distorte rispetto a quelle dei dati reali (nel caso estremo le componenti si appiattiscono sugli assi originali). Se invece si è solo scalato senza togliere la media (per esempio min-max o divisione per la deviazione standard), la centratura resta necessaria. Il messaggio del corso: mai standardizzare alla cieca prima della PCA, perché la varianza è esattamente ciò che la PCA misura.

7. Metodi ensemble: bagging e boosting#

7.1 Aggirare il tradeoff#

Tutto il capitolo ha dato per scontato un vincolo: non si può ridurre il bias senza pagare in varianza, e viceversa. I metodi ensemble provano a incrinare questo vincolo con una mossa laterale: se un singolo modello è inchiodato al tradeoff, forse una combinazione di più modelli non lo è. Le due tecniche fondamentali attaccano i due lati opposti:

• Bagging: ridurre la varianza senza aumentare (significativamente) il bias;
• Boosting: ridurre il bias tenendo la varianza sotto controllo.

7.2 Bagging: la saggezza della folla, formalizzata#

Idea chiave: la media di tante stime indipendenti è molto più stabile di ogni singola stima. Se si riuscisse ad addestrare tanti modelli su dataset indipendenti e a mediarne le predizioni, la varianza del modello aggregato crollerebbe di un fattore pari al numero di modelli, senza toccare il bias.

L’intuizione è quella della saggezza della folla: la risposta aggregata di molte persone è spesso più accurata di quella di un singolo esperto. La formalizzazione è un conto elementare sulle variabili aleatorie. Si supponga di avere $N$ dataset indipendenti, di addestrare su di essi $N$ modelli $y_1, \dots, y_N$ e di definire il modello aggregato

$$y_{AGG}(\mathbf{x}) = \frac{1}{N} \sum_{i=1}^{N} y_i(\mathbf{x})$$

Se le predizioni dei modelli sono indipendenti (perché lo sono i dataset), la varianza della media di $N$ variabili aleatorie i.i.d. $x$ è

$$\text{Var}(\bar{x}) = \frac{1}{N^2} \sum_{N} \text{Var}(x) = \frac{\text{Var}(x)}{N}$$

quindi la varianza del modello aggregato è $1/N$ della varianza del singolo modello, mentre il modello medio (e dunque il bias) resta lo stesso. Il risultato non è nemmeno sorprendente: usare $N$ dataset equivale ad avere $N$ volte più dati, e più dati significa meno varianza.

Il problema è che $N$ dataset indipendenti non ci sono: c’è un solo dataset. Se ci fossero davvero tanti dati, converrebbe semplicemente addestrare un solo modello su tutti. La mossa del bagging è fingere di averli.

I dataset bootstrap non sono indipendenti (contengono la stessa informazione ricombinata: non si sta creando informazione nuova) ma non sono nemmeno identici, quindi producono modelli diversi. Il risultato è una riduzione di varianza reale ma inferiore al fattore $N$ teorico, senza aumento significativo del bias. Varianti pratiche: si possono estrarre copie più piccole dell’originale (nel qual caso ha senso anche il campionamento senza reinserimento; con copie della stessa dimensione, senza reinserimento si otterrebbero solo cloni del dataset), e si può aumentare la randomizzazione differenziando ulteriormente i modelli, per esempio usando sottoinsiemi diversi di feature in ogni dataset o perturbando gli iperparametri dell’algoritmo: il principio generale è sempre “genera modelli diversi con un processo randomizzato, poi aggregali”.

Quando funziona il bagging? Con i learner instabili: modelli che cambiano significativamente anche per piccole variazioni del dataset, cioè modelli a basso bias e alta varianza, con tendenza all’overfitting (alberi profondi, reti neurali). È proprio la varianza che il bagging riduce, quindi serve che ce ne sia. Funziona bene anche con dati rumorosi, dove i modelli a bassa polarizzazione soffrono di più. Non aiuta invece con learner stabili (alto bias, bassa varianza): non c’è varianza da mediare via. In generale il bagging quasi mai peggiora le prestazioni, ma non ci si devono aspettare miracoli: il miglioramento è tipicamente moderato.

In parole semplici: il bagging fotocopia il dataset tante volte “mischiando le carte” (alcuni esempi doppi, altri mancanti), addestra un modello per fotocopia e fa votare tutti. I singoli modelli sono nervosi e ognuno overfitta a modo suo, ma i loro errori casuali si compensano nella media: l’insieme è più calmo di ogni suo membro, senza essere meno espressivo.

7.3 Boosting: costruire un modello forte da tanti modelli deboli#

Il boosting attacca il lato opposto del tradeoff: l’obiettivo è ottenere un bias piccolo usando weak learner, modelli così semplici da avere alto bias e bassa varianza (l’esempio canonico è un classificatore a soglia con decision boundary parallelo agli assi, il decision stump).

Idea chiave: addestrare in sequenza una serie di weak learner, dove ogni iterazione si concentra sui campioni sbagliati dall’iterazione precedente; il modello finale è la combinazione di tutti i weak learner addestrati. La varianza resta bassa (i mattoni sono semplici), ma il bias della combinazione scende a ogni passo.

La procedura iterativa, di cui AdaBoost è l’esempio più noto:

1. Si assegna a tutti i campioni del training set lo stesso peso e si addestra un primo weak learner: per esempio uno split lineare che separa alla meglio le due classi, commettendo alcuni errori.
2. Si aumenta il peso dei campioni mal classificati (e si riduce quello dei campioni corretti): gli errori diventano più importanti. Un trucco semplice per pesare senza toccare l’algoritmo è duplicare i campioni da pesare di più (per learner che ammettono perdite pesate, come la regressione lineare con pesi sui singoli errori quadratici, si pesano direttamente i termini della loss; in alternativa si ricampiona il dataset con probabilità proporzionali ai pesi).
3. Si addestra un nuovo weak learner sul dataset ripesato, che quindi cerca di correggere gli errori del predecessore; si aggiornano di nuovo i pesi e si itera.
4. Il modello finale è la combinazione di tutti i weak learner addestrati, ciascuno con un coefficiente stabilito dall’algoritmo: l’insieme delle tre (o più) decisioni semplici, combinate, produce un decision boundary che nessuno dei singoli learner avrebbe potuto rappresentare.

In alcuni scenari il boosting funziona sorprendentemente bene, raggiungendo prestazioni impossibili per il singolo weak learner e in genere senza overfittare. I suoi limiti sono speculari a quelli del bagging: funziona con learner stabili (alto bias, bassa varianza), mentre soffre con dati molto rumorosi, perché concentrandosi iterativamente sugli errori può finire per inseguire il rumore. Ed è un processo intrinsecamente sequenziale: ogni learner dipende dai pesi prodotti dal precedente, quindi non si parallelizza, al contrario del bagging dove gli $N$ addestramenti sono indipendenti e naturalmente paralleli.

7.4 Bagging vs boosting: il confronto#

In parole semplici: bagging e boosting sono strategie opposte con lo stesso trucco (tanti modelli invece di uno). Il bagging prende modelli già bravi ma nervosi e li calma facendoli votare in parallelo. Il boosting prende modelli scarsi ma tranquilli e li fa lavorare in catena, ognuno sugli errori del precedente, finché la squadra diventa brava. Sbagliare abbinamento (bagging con modelli deboli, boosting con modelli potenti) rende la tecnica inutile.

8. Esercizi d’esame svolti#

8.1 Da modello lineare a quadratico: effetto sui termini dell’errore#

Traccia. Si sta usando un modello lineare e si valuta il passaggio a un modello quadratico (modello lineare con feature quadratiche). Dire quali affermazioni sono vere:

1. il modello quadratico riduce l’errore irriducibile;
2. il modello quadratico riduce il bias;
3. il modello quadratico riduce la varianza;
4. il modello quadratico riduce l’errore di predizione.

Svolgimento. Lo strumento è la decomposizione $\mathbb{E}[(t-y)^2] = \sigma^2 + \text{bias}^2 + \text{varianza}$ e l’inclusione tra spazi di ipotesi: definendo $\mathcal{H}_{lin} = \{w_0 + w_1 x\}$ e $\mathcal{H}_{quad} = \{w_0 + w_1 x + w_2 x^2\}$ al variare dei pesi in $\mathbb{R}$, vale $\mathcal{H}_{lin} \subset \mathcal{H}_{quad}$ (basta $w_2 = 0$).

1. Falsa. L’errore irriducibile è il rumore che corrompe il target: viene dal processo di generazione dei dati e non è influenzato da alcuna scelta del modello.
2. Vera. Con $\mathcal{H}_{lin} \subset \mathcal{H}_{quad}$ il bias del quadratico è sempre minore o al più uguale a quello del lineare: ogni funzione rappresentabile dal lineare lo è anche dal quadratico, quindi la distanza minima dalla funzione vera non può aumentare. Attenzione: il bias non dipende dai dati, ma solo dal rapporto tra funzione vera e spazio di ipotesi.
3. Falsa. Per lo stesso argomento a segno invertito: con l’inclusione tra spazi, la varianza del modello più ricco è sempre maggiore o al più uguale. Modelli più complessi hanno più parametri da stimare e maggiore variabilità da dataset a dataset.
4. Dipende: non si può concludere. È l’essenza stessa del tradeoff: l’esito sulla somma dipende da quanto scende il bias e quanto sale la varianza. Caso particolare istruttivo: se si sapesse che la funzione vera è lineare, la risposta sarebbe “falsa”, perché il bias non scenderebbe affatto (è già minimo) mentre la varianza salirebbe.

8.2 Stesso modello, più campioni#

Traccia. Si mantiene il modello lineare ma si aumenta il numero di campioni (indipendenti) del training set. Che cosa succede a errore irriducibile, bias, varianza, errore riducibile?

Svolgimento.

• Errore irriducibile: invariato. Non dipende né dal modello né dai dati di training.
• Bias: invariato. Il bias dipende solo dallo spazio di ipotesi, che non è cambiato; il numero di campioni non lo tocca.
• Varianza: diminuisce. La varianza dipende dalla complessità del modello (fissa) e dal numero di campioni: con più dati la media campionaria minimizzata è più affidabile e il minimizzatore empirico balla meno.
• Errore riducibile ($\text{bias}^2 + \text{varianza}$): diminuisce, perché il bias resta fermo e la varianza scende. È la ragione precisa per cui, potendo, aumentare i dati conviene sempre. Precisazione necessaria: aumentare i campioni significa aggiungere campioni indipendenti; duplicare campioni già presenti non produce alcun effetto.

8.3 Ridge regression: comportamento al crescere di $\lambda$#

Traccia. Si stima una regressione lineare con la ridge, $\mathbf{w}^* = \arg\min_{\mathbf{w}} \, RSS(\mathbf{w}) + \lambda \lVert \mathbf{w} \rVert_2^2$. Descrivere il comportamento, al crescere di $\lambda$ da 0 a $\infty$, di: (1) RSS di training; (2) RSS di test; (3) varianza; (4) bias al quadrato; (5) errore irriducibile.

Svolgimento.

1. RSS di training: cresce sempre (monotona). Per $\lambda = 0$ i pesi minimizzano esattamente la RSS di training: è il minimo assoluto raggiungibile. Aumentando $\lambda$ la funzione obiettivo dà peso crescente al regolarizzatore, i pesi ottimi si spostano progressivamente da quelli che minimizzavano la RSS verso l’origine, e la RSS di training, valutata proprio sulla quantità che si sta smettendo di minimizzare, può solo aumentare.
2. RSS di test: prima decresce, poi cresce (forma a U). Per $\lambda = 0$ il modello ha bias minimo e varianza alta; aumentando $\lambda$ la varianza scende più di quanto il bias salga, e l’errore su dati indipendenti migliora; oltre il punto ottimo il bias domina e l’errore risale. Il valore di $\lambda$ nel minimo è quello che una procedura di validazione dovrebbe scegliere.
3. Varianza: decresce (monotona). Più regolarizzazione significa modello più vincolato e meno sensibile ai dati. Al limite $\lambda \to \infty$ conta solo il regolarizzatore, minimizzato da $\mathbf{w} = \mathbf{0}$: il modello è sempre lo stesso qualunque sia il dataset, varianza zero.
4. Bias al quadrato: cresce (monotono). Specularmente, il vincolo allontana il modello medio dalla funzione vera; al limite $\lambda \to \infty$ il modello è la costante zero, con bias massimo.
5. Errore irriducibile: costante. Non è influenzato da $\lambda$ (né da nient’altro).

Questo esercizio e il precedente mostrano i due meccanismi standard con cui si sposta il tradeoff: cambiare lo spazio di ipotesi (inclusione lineare/quadratico) e regolare l’iperparametro di regolarizzazione ($\lambda$; per K-NN il ruolo analogo lo gioca $K$).

8.4 Scegliere la tecnica di valutazione per lo scenario#

Traccia. Quale tecnica usare per valutare/selezionare tra più modelli (validation set, k-fold cross-validation, leave-one-out, criteri aggiustati) nei seguenti scenari? “Semplice” e “complesso” si riferiscono qui al costo computazionale dell’addestramento.

1. Dataset piccolo, modelli semplici.
2. Dataset piccolo, modelli complessi.
3. Dataset grande, modelli semplici.
4. Dataset grande, modelli complessi.

Svolgimento.

1. Leave-one-out. LOO richiede tanti addestramenti quanti sono i campioni: con dataset piccolo e addestramenti economici è fattibile, e restituisce la stima più affidabile possibile perché ogni modello è addestrato sul massimo numero di punti ($N-1$), cosa preziosa proprio quando i punti sono pochi.
2. Criteri aggiustati ($C_p$, AIC, BIC, Adjusted $R^2$). Non ci si possono permettere né i molti addestramenti della cross-validation né LOO (modelli costosi), e non si vuole sacrificare una fetta del già piccolo dataset per la validazione: si addestra una sola volta su tutto e si corregge il training error con la penalità di complessità, accettando che sia un’euristica.
3. K-fold cross-validation. LOO è precluso non dal costo del singolo addestramento ma dal numero di campioni $N$; la k-fold dà una buona stima con soli $k$ addestramenti. Con sufficienti capacità di calcolo parallelo si può alzare $k$ (i $k$ addestramenti sono indipendenti), al limite fino a LOO: il valore giusto di $k$ si calibra su grado di parallelismo e costo del singolo addestramento.
4. Validation set singolo. I dati abbondano, quindi lo split a tre parti lascia comunque abbastanza dati per l’addestramento e una stima di validazione affidabile; i criteri aggiustati, approssimati per natura, non avrebbero senso potendosi permettere una validazione vera; CV e LOO costerebbero troppo con modelli pesanti.

8.5 Trasformazioni delle feature e bias/varianza#

Traccia. Problema di regressione con variabili di input $x_1, x_2, x_3$ linearmente indipendenti. Dire se le seguenti affermazioni sul tradeoff bias-varianza sono vere o false, motivando:

1. in una regressione lineare, sostituendo $x_1$ con $x_1 + x_2$ non si cambia il bias del modello;
2. in una regressione lineare, sostituendo $x_1$ con $x_1^2 / 100$ si potrebbe aumentare la varianza del modello;
3. per un modello arbitrario, rimuovendo la variabile $x_2$ non si aumenta la varianza;
4. per un modello arbitrario, aggiungendo la variabile $x_3^2$ non si aumenta il bias.

Svolgimento.

Affermazione 1: vera. Le nuove variabili $\{x_1 + x_2,\; x_2,\; x_3\}$ sono ancora linearmente indipendenti e generano lo stesso spazio delle originali: tutta l’informazione su $x_1$ è ancora disponibile (come combinazione di $x_1 + x_2$ e $x_2$). Formalmente, il modello sulle nuove variabili

$$w_1 (x_1 + x_2) + w_2 x_2 + w_3 x_3 = w_1 x_1 + (w_1 + w_2)\, x_2 + w_3 x_3$$

è, a meno di una ridenominazione dei coefficienti, esattamente il modello lineare originale: lo spazio di ipotesi non cambia, quindi né bias né varianza cambiano. Due cautele importanti: (a) l’argomento vale per la regressione lineare, non per un modello arbitrario, perché sfrutta la linearità del modello nelle variabili; per altri modelli una sostituzione del genere può cambiare il bias; (b) se il modello fosse privo di termine costante, sostituire $x_1$ con $x_1$ più una costante cambierebbe invece il bias (si starebbe di fatto introducendo un’intercetta).

Affermazione 2: vera. Sostituendo (non aggiungendo) $x_1$ con la trasformazione non lineare $x_1^2/100$, i due spazi di ipotesi non sono più confrontabili per inclusione: si guadagna la capacità di rappresentare il termine quadratico ma si perde quella di rappresentare il termine lineare in $x_1$. In generale non si può dire come cambino bias e varianza; ma l’affermazione dice “si potrebbe aumentare la varianza”, e questo è vero. Confronto utile: se invece si aggiungesse $x_1^2$ tenendo anche $x_1$ (variabili $x_1^2, x_1, x_2, x_3$), lo spazio includerebbe strettamente l’originale, quindi bias minore o uguale e varianza maggiore o uguale. Attenzione anche a non confondere il singolo monomio quadratico con il “modello quadratico completo” sulle variabili originali, che conterrebbe $x_1, x_2, x_3, x_1^2, x_2^2, x_3^2, x_1 x_2, x_2 x_3, x_1 x_3$ e sarebbe strettamente più potente del lineare.

Affermazione 3: vera. Sopprimere una variabile di input restringe lo spazio dei modelli rappresentabili: qualunque sia il modello (anche una rete neurale complessa), lo spazio ottenuto senza $x_2$ è contenuto in quello con $x_2$. Uno spazio più piccolo non può avere varianza maggiore: la varianza diminuisce o al più resta uguale.

Affermazione 4: vera. Simmetricamente, aggiungere una feature (non sostituirla) amplia lo spazio dei modelli rappresentabili, e uno spazio più ampio non può avere bias maggiore: il bias diminuisce o al più resta uguale (la varianza, quella sì, può aumentare).

Regola riassuntiva da esame: aggiungere feature riduce (o lascia uguale) il bias e aumenta (o lascia uguale) la varianza; rimuovere feature fa l’opposto; sostituire una feature con un’altra non permette conclusioni generali, salvo il caso della regressione lineare con sostituzioni lineari invertibili, dove non cambia nulla.

8.6 Leggere un frammento di codice: wrapper e insidie del training error#

Traccia. È dato uno pseudo-codice che: (riga 1-2) istanzia una regressione logistica e la addestra su tutto $(\mathbf{X}, \mathbf{y})$, con $\mathbf{X} \in \mathbb{R}^{N \times M}$; (riga 3) ne calcola l’accuratezza confrontando le predizioni su $\mathbf{X}$ con $\mathbf{y}$; (riga 4+) in un ciclo for su $i = 1, \dots, M$ costruisce $\mathbf{X}_{-i}$ rimuovendo la feature $i$-esima, riaddestra il classificatore su $\mathbf{X}_{-i}$, predice e accoda l’accuratezza a una lista. Domande:

1. che tipo di procedura di model selection implementa il codice?
2. dopo l’esecuzione, conviene tenere il classificatore con l’accuratezza massima nella lista: vero o falso?
3. il classificatore addestrato alla riga 2 (tutte le feature) ha bias più grande di quello addestrato senza una feature: vero o falso?
4. il costo computazionale del frammento scala linearmente con $M$: vero o falso?

Svolgimento.

1. È feature selection (si scartano feature originali: non è feature extraction, che ne costruirebbe di nuove, né regolarizzazione). Più precisamente è un metodo wrapper: per ogni sottoinsieme candidato si addestra un modello e lo si valuta. Ancora più precisamente, è il primo passo di una backward stepwise selection: si parte da tutte le feature e si prova a rimuoverne una alla volta.
2. Falso, ed è il punto cruciale: tutte le accuratezze del ciclo sono calcolate sui dati di training. La model selection non si può fare sul training error: con questo criterio vincerebbe (quasi) sempre il modello con tutte le feature, perché è il più complesso e a parità di dati di valutazione il training error decresce con la complessità. Per usare correttamente il codice bisogna separare i dati (train/validation), oppure usare cross-validation, leave-one-out o criteri aggiustati, e calcolare le accuratezze del confronto sui dati di validazione, non su quelli di addestramento.
3. Falso. Il modello con tutte le feature è il più complesso: può sempre porre a zero il peso della feature in questione, il che equivale ad averla rimossa, quindi il suo spazio di ipotesi include l’altro e il suo bias è minore o uguale, mai maggiore.
4. Falso (o quantomeno impreciso). Il numero di iterazioni del ciclo è $M$, ma il costo di ogni iterazione non è costante: ogni addestramento della regressione logistica ha un costo che dipende a sua volta da $M$ (e da $N$). Il costo totale è quindi lineare in $M$ solo nel numero di addestramenti, non complessivamente.

8.7 Vero/falso sulla PCA#

Traccia. Dire se le seguenti affermazioni sulla PCA sono vere o false, motivando:

1. dati solo gli scores $\mathbf{T}$ (i dati trasformati) senza i loadings $\mathbf{W}$, non c’è modo di ricostruire un’approssimazione ragionevole dei dati originali;
2. ha senso eseguire la PCA solo con un numero di componenti $k$ minore o uguale al numero di feature originali $M$;
3. la PCA è suscettibile di ottimi locali, quindi conviene eseguirla più volte con inizializzazioni casuali diverse.

Svolgimento.

1. Vera. La ricostruzione richiede i loadings: con la matrice completa $\mathbf{W}$ (ortogonale, quindi $\mathbf{W}^{-1} = \mathbf{W}^T$) la trasformazione si inverte esattamente, $\bar{\mathbf{x}}_i = \mathbf{W} \mathbf{t}_i$; con i primi $k$ loadings si ottiene la migliore approssimazione di rango $k$ in norma. Ma senza $\mathbf{W}$ gli scores sono coordinate in una base ignota: nessuna ricostruzione è possibile.
2. Vera. Le componenti principali sono gli autovettori della matrice di covarianza $M \times M$: ne esistono al più $M$. Considerare più componenti delle feature originali non ha senso; il caso estremo $k = M$ è la pura rotazione senza riduzione.
3. Falsa. La PCA non ha alcuna componente casuale né iterativa da inizializzare: centratura dei dati, matrice di covarianza, autovalori e autovettori sono calcoli deterministici. Eseguirla più volte dà sempre lo stesso risultato; il concetto di ottimo locale non si applica.

8.8 Vero/falso su un’implementazione della PCA#

Traccia. È dato un frammento di codice che: (riga 1) centra i dati sottraendo la media per colonna; (riga 2) calcola $\bar{\mathbf{X}}^T \bar{\mathbf{X}}$; (riga 3) ne estrae autovalori e autovettori $\mathbf{W}$; (riga 4) calcola $\mathbf{T} = \bar{\mathbf{X}}\mathbf{W}$. Dire se le seguenti affermazioni sono vere o false:

1. il codice implementa una tecnica di feature selection;
2. la centratura è superflua se i dati $\mathbf{X}$ sono già stati scalati;
3. usare come input del modello le prime $k$ componenti principali invece delle feature originali non può peggiorare le prestazioni;
4. tenendo le prime 2 componenti su 5, dagli scores $\mathbf{T}_2$ si può recuperare esattamente la $\mathbf{X}$ originale.

Svolgimento.

1. Falsa. È feature extraction (riduzione della dimensionalità): non si selezionano feature originali, se ne costruiscono di nuove come combinazioni lineari di tutte.
2. Dipende dal significato di “scalati”, quindi in generale falsa. Se scalare significa z-score (media sottratta e divisione per la deviazione standard), la centratura diventa ridondante perché la media è già zero; ma se significa solo dividere per la deviazione standard, o mappare in $[0, 1]$ col min-max, la media non è zero e la centratura resta necessaria. Domanda collegata e importante: conviene standardizzare prima della PCA? No, non alla cieca: portare tutte le feature a varianza 1 distrugge esattamente l’informazione di varianza su cui la PCA si basa, distorcendone le direzioni (nel caso limite le componenti si appiattiscono sugli assi).
3. Falsa. La rappresentazione a $k < M$ dimensioni contiene meno informazione del dataset completo, e poiché la PCA è non supervisionata nessuno garantisce che l’informazione scartata fosse irrilevante per il target: le prestazioni possono peggiorare (si ricordi il controesempio in cui solo la seconda componente discrimina le classi).
4. Falsa. Con i primi 2 loadings su 5 la trasformazione non è invertibile: $\mathbf{T}_2 \mathbf{W}_2^T$ è solo la migliore approssimazione di rango 2 dei dati centrati, non la $\mathbf{X}$ esatta. Il recupero esatto richiede tutte le $M$ componenti.

8.9 Vero/falso su bagging e boosting#

Traccia. Dire se le seguenti affermazioni sono vere o false, motivando:

1. sia il bagging sia il boosting possono essere parallelizzati;
2. il bagging andrebbe applicato con weak learner;
3. l’idea centrale del boosting è generare dataset con il bootstrap e addestrare i modelli su di essi;
4. non è una buona idea usare una rete neurale profonda come weak learner in un algoritmo di boosting.

Svolgimento.

1. Falsa. Solo il bagging è naturalmente parallelo: gli $N$ dataset bootstrap e i relativi addestramenti sono indipendenti tra loro. Il boosting è intrinsecamente sequenziale: i pesi dei campioni usati per addestrare il learner $k$-esimo dipendono dagli errori del learner $(k-1)$-esimo, quindi ogni passo deve attendere il precedente (il confronto sistematico è nella tabella bagging vs boosting).
2. Falsa. Il bagging riduce la varianza; un weak learner ha varianza piccola e bias grande, quindi non c’è quasi nulla da ridurre: mediare tanti modelli tutti sbagliati nello stesso modo lascia il bias intatto. Il bagging va usato con learner instabili (basso bias, alta varianza); i weak learner sono la materia prima del boosting.
3. Falsa. Il bootstrap con aggregazione in parallelo è l’idea centrale del bagging. L’idea centrale del boosting è diversa: addestrare i weak learner in sequenza, ripesando a ogni iterazione i campioni sbagliati dall’iterazione precedente, e combinare alla fine tutti i learner.
4. Vera. Una rete profonda non è un weak learner: ha basso bias e alta varianza. Il boosting serve a ridurre il bias combinando modelli semplici ad alto bias; applicarlo a un modello già a basso bias non ha senso (e con la varianza alta della rete si rischia di amplificare l’overfitting, specialmente su dati rumorosi).

Glossario#

Termine	Definizione
Errore di predizione	Errore atteso del modello sull’intera distribuzione dei dati, $\mathbb{E}_{(\mathbf{x},t)\sim p}[L(t, y(\mathbf{x}))]$: la quantità che si vorrebbe minimizzare ma non si può calcolare direttamente.
Rischio di popolazione	Errore atteso minimizzato conoscendo $p(\mathbf{x}, t)$; il suo minimizzatore $y^*$ è deterministico.
Rischio empirico	Media campionaria della loss sul training set; il suo minimizzatore $\hat{y}$ è una variabile aleatoria dipendente dal dataset.
Errore irriducibile ($\sigma^2$)	Varianza del rumore che corrompe il target; non dipende né dal modello né dai dati di training.
Bias	Distanza tra la funzione vera $f$ e il modello medio $\bar{y} = \mathbb{E}_{\mathcal{D}}[y]$; dipende solo dallo spazio di ipotesi, decresce con la complessità.
Varianza (del modello)	Variabilità $\mathbb{E}_{\mathcal{D}}[(y - \bar{y})^2]$ del modello appreso al variare del dataset; decresce con modelli più semplici e con più campioni.
Bias-variance decomposition	Identità $\mathbb{E}[(t - y(\mathbf{x}))^2] = \sigma^2 + \text{bias}^2 + \text{varianza}$.
Overfitting / underfitting	Regimi rispettivamente ad alta varianza con basso bias, e ad alto bias con bassa varianza.
K-NN	Metodo che predice da i $K$ campioni più vicini (majority vote o media); varianza $\sigma^2/K$, bias crescente con $K$; $K$ agisce da iperparametro di regolarizzazione.
Training error	Loss valutata sui dati di addestramento; decresce monotonicamente con la complessità e non stima l’errore di predizione.
Test set / test error	Insieme indipendente mai usato per addestrare né per scegliere; usato una sola volta, dà una stima non distorta dell’errore di predizione.
Validation set	Insieme separato usato per la model selection (confronto tra modelli/iperparametri); split tipico 50/25/25.
Model selection	Scelta tra modelli o iperparametri alternativi in base all’errore stimato su dati di validazione.
Cross-validation (k-fold)	Divisione dei dati in $k$ fold; per ogni fold si addestra sugli altri e si valuta su di esso; stima $L_{k\text{-}fold} = \frac{1}{k}\sum_i L_{\mathcal{D}_i}$; $k$ tipico 5 o 10.
Leave-one-out (LOO)	Cross-validation con $k = N$: si esclude un campione alla volta; stima quasi non distorta (lievemente pessimistica) ma costosissima.
$C_p$, AIC, BIC, Adjusted $R^2$	Criteri che penalizzano il training error in proporzione al numero di parametri; euristiche da usare quando la validazione non è praticabile.
Maledizione della dimensionalità	Crescita esponenziale del volume dello spazio di input con il numero di feature: dati sempre più sparsi, fabbisogno esponenziale di campioni, varianza in crescita.
Feature selection	Riduzione della dimensionalità scartando feature originali; famiglie: filter, wrapper, embedded.
Filter	Selezione univariata: le feature sono ordinate indipendentemente con metriche (correlazione, mutua informazione) e si tengono le migliori; veloce ma cieca alle dipendenze tra feature.
Wrapper	Ricerca (tipicamente greedy) tra sottoinsiemi di feature, ognuno valutato addestrando un modello; forward e backward stepwise, costo $O(M^2)$ addestramenti.
Embedded	Selezione integrata nell’addestramento (lasso, decision tree); economica ma specifica del metodo.
Riduzione della dimensionalità	Mappatura (non supervisionata) dello spazio di input in uno spazio a dimensione minore usando tutte le feature originali.
PCA	Cambio di base lineare verso direzioni ortogonali ordinate per varianza catturata; autovettori della matrice di covarianza dei dati centrati.
Loadings / scores	Rispettivamente la matrice $\mathbf{W}$ degli autovettori (nuove direzioni) e i dati trasformati $\mathbf{T} = \bar{\mathbf{X}}\mathbf{W}$.
Varianza spiegata	Frazione $\sum_{j \le k}\lambda_j / \sum_j \lambda_j$ usata per scegliere il numero di componenti (soglia, gomito).
Ensemble	Combinazione di più modelli per migliorare il tradeoff bias-varianza.
Bootstrap	Generazione di copie del dataset per campionamento con reinserimento.
Bagging	Bootstrap aggregation: modelli addestrati in parallelo su dataset bootstrap e aggregati (media/voto); riduce la varianza; adatto a learner instabili.
Weak learner	Modello semplice ad alto bias e bassa varianza (es. decision stump); mattone del boosting.
Learner instabile	Modello a basso bias e alta varianza, molto sensibile a piccole variazioni dei dati; beneficia del bagging.
Boosting	Addestramento sequenziale di weak learner con ripesatura dei campioni sbagliati; riduce il bias mantenendo la varianza contenuta; sequenziale, sensibile al rumore.
AdaBoost	Algoritmo di boosting canonico basato sull’aggiornamento iterativo dei pesi dei campioni e sulla combinazione pesata dei weak learner.

Dispensa Machine Learning · Politecnico di Milano