Esercizio - Cross-validation annidata con alberi (laboratorio di ripasso)

Questa pagina non ha ancora la versione ripasso: qui sotto c'è il testo completo.

Testo (laboratorio di ripasso, dataset Iris con $150$ campioni e un albero di decisione). Si valuti un albero con la K-fold cross-validation e poi con la cross-validation annidata per scegliere gli iperparametri max_depth $\in\{2,3,4\}$ e min_impurity_improvement $\in\{0;\,0{,}01\}$.

1. In una K-fold con $K=5$ su $150$ campioni, quanti campioni ha ciascuna fold? E con $103$ campioni e $K=5$?
2. Scrivere la procedura della K-fold per stimare l'accuratezza di un albero con max_depth=3.
3. Perché per scegliere gli iperparametri non basta la K-fold semplice e cosa fa la cross-validation annidata? Quanti addestramenti servono con $10$ fold esterne, $3$ interne e la griglia da $3\cdot2=6$ combinazioni?
4. Perché la cross-validation di un albero non è un random forest?

Teoria usata: Overfitting, ridge regression e cross-validationUna buona prestazione sul training non basta: serve stimare quella su dati nuovi. La cross-validation (K-fold: $k$ parti, ciascuna a turno come test, errore medio; Monte Carlo: $k$ divisioni casuali con quota di test $q$; leave-one-out se $k=n$) evita di dipendere da una sola divisione casuale. L'errore atteso si scompone in $\text{bias}^2+\text{varianza}+\sigma^2$: i modelli semplici fanno underfitting (bias alto), quelli complessi overfitting (varianza alta). La regolarizzazione aggiunge alla perdita una penalità: la ridge regression minimizza $|y-X\beta|^2+\lambda\sum_{j\ge1}\beta_j^2$ e ha soluzione $\beta=(X^TX+\lambda\tilde I)^{-1}X^Ty$ (l'intercetta non si penalizza, le feature si standardizzano): riduce i coefficienti, rende l'inversa stabile con feature collineari, e $\lambda$ è un iperparametro scelto con la validazione (cross-validation annidata per non contaminare il test).Overfitting, ridge regression e cross-validation →, Alberi di decisioneUn albero di decisione partiziona i dati con una sequenza di regole su una sola variabile alla volta (nodi interni = regole, foglie = predizioni: classe più frequente, oppure media del target in regressione). Si costruisce in modo ricorsivo scegliendo a ogni nodo la divisione che rende i figli più «puri»: con l'entropia $H=-\sum p_i\log_2p_i$ e il guadagno d'informazione $IG=H(S)-\sum\frac{|S_v|}{|S|}H(S_v)$ (ID3), oppure con l'indice di Gini $1-\sum p_i^2$ e soglie $x\le t$ su variabili numeriche (CART); in regressione con MSE o riduzione di varianza. Un albero pienamente sviluppato fa overfitting (varianza alta): si limita con la profondità massima (pre-potatura) o con la potatura a costo-complessità $R_\alpha(T)=R(T)+\alpha|T|$ (post-potatura). Pro: interpretabile, niente normalizzazione, predizione immediata; contro: varianza alta, da cui le foreste. Programma di Telecomunicazioni: Decision Trees e Random Forests.Alberi di decisione →, Metodi ensemble - bagging, random forest e boostingUn albero da solo ha varianza alta; un ensemble combina molti modelli deboli. Bagging: ogni albero è addestrato su un campione bootstrap (n estrazioni con rimpiazzo, circa il 63% di campioni distinti) e si vota o si fa la media: riduce la varianza, perché la media di $T$ stimatori con varianza $\sigma^2$ e correlazione $\rho$ ha varianza $\rho\sigma^2+(1-\rho)\sigma^2/T$. Random forest = bagging + a ogni split solo $\sqrt p$ feature casuali (alberi meno correlati); l'importanza di una feature è la somma delle riduzioni di Gini pesate sui nodi in cui è usata. Boosting: alberi in sequenza, ciascuno corregge gli errori dei precedenti, e si riduce il bias. Gradient boosting: $F\leftarrow F+\eta h$ con $h$ albero sui residui (gradiente negativo della perdita), $\eta$ piccolo; AdaBoost: stump e pesi sui campioni sbagliati; XGBoost: similarity score $\frac{(\sum r)^2}{N+\lambda}$, gain, potatura con $\gamma$, output $\frac{\sum r}{N+\lambda}$. Programma di Telecomunicazioni: Random Forests; boosting come approfondimento.Metodi ensemble - bagging, random forest e boosting →.

1. Dimensione delle fold

Con $n=150$ e $K=5$: $150/5=30$ campioni per fold. Con $n=103$ non è divisibile: la quota base è $\lfloor103/5\rfloor=20$ e restano $103-5\cdot20=3$ campioni, assegnati uno ciascuno alle prime tre fold: dimensioni $21,21,21,20,20$ (è la regola usata nel codice del laboratorio: base + (1 if i < remainder else 0)).

2. K-fold

Si mescolano gli indici (shuffle, per non avere fold con una sola classe nei dataset ordinati), si divide in $K$ fold; per ogni fold: training sulle altre $K-1$, test su quella; si media l'accuratezza.

from sklearn.model_selection import KFold
kf = KFold(n_splits=5, shuffle=True, random_state=0)
acc = []
for tr, te in kf.split(X):
    tree = DecisionTreeClassifier(max_depth=3, random_state=0).fit(X[tr], y[tr])
    acc.append((tree.predict(X[te]) == y[te]).mean())
print(np.mean(acc))

Nel laboratorio le cinque accuratezze sono $0{,}9667;\ 0{,}9000;\ 1{,}0000;\ 0{,}9667;\ 0{,}9333$ e la media $0{,}9533$. (Controllo: $(0{,}9667+0{,}9+1+0{,}9667+0{,}9333)/5=0{,}9533$ ✓.) Ogni campione è usato esattamente una volta per il test: la stima non dipende da una particolare divisione fortunata.

La cross-validation stima la prestazione, non migliora il modello: alla fine si riaddestra un solo albero su tutti i dati.

3. Perché serve la cross-validation annidata

Se gli iperparametri si scelgono con la stessa K-fold con cui si riporta l'accuratezza, la stima è ottimistica: il punteggio della combinazione migliore è stato selezionato guardando proprio quei dati di test (anche una divisione fissa in training/validazione/test dà una stima rumorosa).

Struttura a due cicli:

• ciclo interno (con $K_{in}=3$): sul solo training dell'esterno, per ogni combinazione si calcola l'accuratezza media di validazione e si sceglie la migliore;
• ciclo esterno (con $K_{out}=10$): si riaddestra l'albero con la combinazione scelta su tutto il training esterno e lo si valuta sulla fold esterna, mai vista né per l'addestramento né per la scelta degli iperparametri.

La stima finale è la media delle $10$ accuratezze esterne; il modello definitivo si riaddestra su tutti i dati con la combinazione scelta più spesso.

Costo. Per ogni fold esterna: $3\cdot6=18$ addestramenti interni più $1$ riaddestramento: $19$. In totale $10\cdot19=190$ addestramenti (con le interne $180$). Per questo con modelli pesanti (boosting, reti) si usa con cautela.

Risultati nel laboratorio sull'Iris: media delle accuratezze esterne $0{,}9400$ con scikit-learn e $0{,}9333$ con l'implementazione a mano (le scelte casuali delle fold sono diverse); nelle fold stampate le combinazioni scelte sono max_depth $3$ o $4$ con min_impurity_improvement$=0$.

4. Cross-validation e random forest

La cross-validation misura la capacità di generalizzare di un albero. Un random forest costruisce molti alberi su campioni bootstrap e feature casuali e ne combina i voti: è un modello diverso, che riduce la varianza e di solito generalizza meglio. Un albero singolo ha alta varianza (basta cambiare pochi dati per cambiare l'albero), e la cross-validation lo rivela; non lo corregge.