Metodi ensemble - bagging, random forest e boosting

L'albero 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 → è interpretabile e veloce ma è un classificatore ad alta varianza. I metodi ensemble combinano molti modelli semplici (weak learner, di solito alberi) in uno più robusto. Tutti cercano di superare l'overfitting degli alberi singoli (1) costruendo più alberi, (2) imponendo vincoli su dati, feature, struttura o apprendimento, (3) combinandone le uscite. Gli esercizi sono Esercizio - ID3 con potatura e foresta casuale sul dataset Titanic, Esercizio - Gradient boosting per la regressione sul dataset housing, Esercizio - Importanza delle feature di un albero sul dataset wine e Esercizio - Curva ROC e AUC di una foresta casuale e di un albero.

Perché mediare riduce la varianza

Siano $\hat f_1,\dots,\hat f_T$ stimatori (per esempio le previsioni di $T$ alberi) con la stessa varianza $\sigma^2$ e correlazione $\rho$ tra due qualunque di essi. La media $\bar f=\frac1T\sum_t\hat f_t$ ha varianza $$\operatorname{Var}(\bar f)=\frac1{T^2}\Big(\sum_t\operatorname{Var}(\hat f_t)+\sum_{s\ne t}\operatorname{Cov}(\hat f_s,\hat f_t)\Big)=\frac1{T^2}\big(T\sigma^2+T(T-1)\rho\sigma^2\big)=\rho\sigma^2+\frac{1-\rho}T\sigma^2.$$ (Si è usata la varianza di una somma di variabili correlate, Varianza e momentiI momenti E[X^k] e i momenti centrati E[(X − μ)^k] descrivono la forma di una legge; la varianza Var(X) = E[(X − μ)²] = E[X²] − E[X]² misura quanto X si disperde attorno alla media, vale Var(aX + b) = a² Var(X) e Var(X) = 0 solo se X è costante.Varianza e momenti → e Covarianza e coefficiente di correlazioneCov(X, Y) = E[(X − E X)(Y − E Y)] = E[XY] − E[X]E[Y] misura quanto X e Y variano insieme; è bilineare, Cov(X, X) = Var(X), Var(X + Y) = Var X + Var Y + 2Cov(X, Y); ρ = Cov / (σ_X σ_Y) sta in [−1, 1] e vale ±1 solo per legami lineari. Indipendenti ⇒ non correlate, ma non viceversa (tranne per i vettori gaussiani).Covarianza e coefficiente di correlazione →: ci sono $T$ varianze e $T(T-1)$ coppie ordinate, ciascuna con covarianza $\rho\sigma^2$.) Con $\sigma^2=1$: per $\rho=0$ (alberi indipendenti) la varianza è $1/T$, cioè $0{,}1$ con $T=10$ e $0{,}01$ con $T=100$; per $\rho=0{,}5$ vale $0{,}55$ con $T=10$ e $0{,}505$ con $T=100$; per $\rho=1$ (alberi uguali) resta $1$.

La derivazione, un passo alla volta.

1. La media è un multiplo di una somma: $\bar f=\frac1T S$ con $S=\sum_t\hat f_t$. Una costante $a$ esce dalla varianza al quadrato, $\operatorname{Var}(aS)=a^2\operatorname{Var}(S)$ (Varianza e momentiI momenti E[X^k] e i momenti centrati E[(X − μ)^k] descrivono la forma di una legge; la varianza Var(X) = E[(X − μ)²] = E[X²] − E[X]² misura quanto X si disperde attorno alla media, vale Var(aX + b) = a² Var(X) e Var(X) = 0 solo se X è costante.Varianza e momenti →), quindi $\operatorname{Var}(\bar f)=\frac1{T^2}\operatorname{Var}(S)$: da qui il fattore $\frac1{T^2}$.
2. La varianza di una somma di variabili non indipendenti è la somma di tutte le covarianze: $\operatorname{Var}(S)=\sum_{s}\sum_{t}\operatorname{Cov}(\hat f_s,\hat f_t)$, dove i termini con $s=t$ sono le varianze ($\operatorname{Cov}(X,X)=\operatorname{Var}(X)$) e gli altri le covarianze (Covarianza e coefficiente di correlazioneCov(X, Y) = E[(X − E X)(Y − E Y)] = E[XY] − E[X]E[Y] misura quanto X e Y variano insieme; è bilineare, Cov(X, X) = Var(X), Var(X + Y) = Var X + Var Y + 2Cov(X, Y); ρ = Cov / (σ_X σ_Y) sta in [−1, 1] e vale ±1 solo per legami lineari. Indipendenti ⇒ non correlate, ma non viceversa (tranne per i vettori gaussiani).Covarianza e coefficiente di correlazione →). Con $T$ variabili ci sono $T$ termini diagonali e $T^2-T=T(T-1)$ termini fuori diagonale.
3. Il coefficiente di correlazione è $\rho=\operatorname{Cov}(\hat f_s,\hat f_t)/(\sigma\cdot\sigma)$, quindi ogni covarianza vale $\rho\sigma^2$. Allora $\operatorname{Var}(S)=T\sigma^2+T(T-1)\rho\sigma^2$.
4. Si divide per $T^2$ e si separa: $\dfrac{T\sigma^2}{T^2}+\dfrac{T(T-1)\rho\sigma^2}{T^2}=\dfrac{\sigma^2}T+\dfrac{(T-1)\rho\sigma^2}T=\dfrac{\sigma^2}T+\rho\sigma^2-\dfrac{\rho\sigma^2}T=\rho\sigma^2+\dfrac{(1-\rho)\sigma^2}T.$ Casi limite: se gli stimatori sono indipendenti ($\rho=0$) i termini fuori diagonale sono nulli e resta $\sigma^2/T$ (varianza della media di $T$ variabili indipendenti, lo stesso risultato visto per il k-NN in Classificazione e k-nearest neighborsNella classificazione l'uscita $y$ è una categoria (con $C$ classi; $C=2$ è il caso binario). Il classificatore più semplice è il k-nearest neighbors: una nuova osservazione prende la classe più frequente (voto di maggioranza) tra i suoi $k$ vicini più prossimi nel training, con distanza euclidea $\sqrt{\sum(A_i-B_i)^2}$ o di Manhattan $\sum|A_i-B_i|$ (per la regressione si fa la media dei vicini). $k$ è un iperparametro: $k$ piccolo dà bordi frastagliati e overfitting, $k$ grande underfitting. È un metodo basato su istanze e «pigro» (nessun addestramento, costo alla predizione), sensibile a scala e feature irrilevanti e alla maledizione della dimensionalità; gli ingressi categorici si codificano con one-hot. Approfondimento: non nel programma di Telecomunicazioni.Classificazione e k-nearest neighbors →); se sono identici ($\rho=1$) restano $\sigma^2$ per qualunque $T$, perché la media di $T$ copie dello stesso numero è quel numero. Una simulazione con numpy di $T=10$ stimatori gaussiani con $\sigma^2=1$ e $\rho=0{,}5$ (400 000 prove) dà varianza della media $0{,}548$, contro il valore teorico $0{,}55$.

Quindi mediare riduce la varianza, ma solo se gli alberi sono poco correlati: la parte $\rho\sigma^2$ non scompare aumentando $T$. Tutto il bagging serve a rendere gli alberi diversi.

Perché serve anche abbassare $\rho$, non solo aumentare $T$ (errore atteso contro numero di alberi). L'errore quadratico atteso di una previsione si scompone in $\text{bias}^2+\text{varianza}$ (più il rumore non eliminabile). La media di alberi ha lo stesso bias di un albero e la varianza $\rho\sigma^2+\frac{1-\rho}T\sigma^2$, quindi l'errore previsto in funzione di $T$ è $\text{bias}^2+\rho\sigma^2+\frac{1-\rho}T\sigma^2$: una curva che scende rapidamente per i primi alberi e si appiattisce su un valore finale. Con valori di esempio $\text{bias}^2=0{,}2$, $\sigma^2=1$, $\rho=0{,}3$ (foresta casuale) oppure $\rho=0{,}7$ (alberi simili, bagging senza feature bagging): errore con $T=1$: $1{,}2$ in entrambi i casi (un solo albero: $0{,}2+1$); con $T=10$: $0{,}2+0{,}3+0{,}07=0{,}57$ contro $0{,}2+0{,}7+0{,}03=0{,}93$; con $T=\infty$: $0{,}5$ contro $0{,}9$. Le curve sono un modello teorico, non un risultato di laboratorio; coincidono con quanto si osserva: l'errore di una foresta smette di calare dopo qualche decina di alberi e non risale (nessun overfitting da $T$).

Bagging

Definizione (bagging, bootstrap aggregating). Per costruire una foresta di $T$ alberi: per ciascun albero si estrae dal training di $n$ campioni un campione bootstrap, cioè $n$ campioni con rimpiazzo (ogni estratto è rimesso nell'urna prima della successiva); si addestra un albero su ciascun campione; per classificare si fa il voto di maggioranza (la moda), per la regressione la media.

Con il rimpiazzo alcuni campioni compaiono più volte e altri mai. La probabilità che un dato campione non sia mai estratto in $n$ estrazioni è $(1-\frac1n)^n$, che tende a $e^{-1}=0{,}368$ (Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →; per $n=10$ vale $0{,}349$, per $n=100$ $0{,}366$): ogni albero vede circa il $63\%$ dei campioni distinti, e il restante $37\%$ (out-of-bag) può servire come validazione.

Esempio: con $n=5$ un campione bootstrap possibile è $\{1,1,3,4,4\}$ (i campioni 2 e 5 sono fuori).

Il calcolo, passo per passo.

1. In una singola estrazione ogni campione ha probabilità $\frac1n$ di uscire (spazio uniforme: Spazi di probabilità discreti e uniformiIn uno spazio discreto la probabilità è determinata dalla densità discreta p(ω) = P({ω}), con somma 1, e P(A) è la somma di p(ω) sugli esiti di A; negli spazi uniformi (esiti equiprobabili) P(A) = |A| / |Ω|, casi favorevoli su casi possibili.Spazi di probabilità discreti e uniformi →), quindi probabilità $1-\frac1n$ di non uscire (Misura di probabilità e sue proprietàUna misura di probabilità è una funzione P: F → [0,1] con P(Ω) = 1 e σ-additiva; ne seguono P(Aᶜ) = 1 − P(A), P(∅) = 0, monotonia, P(A ∪ B) = P(A) + P(B) − P(A ∩ B) e la formula di inclusione-esclusione.Misura di probabilità e sue proprietà →, evento complementare).
2. Le $n$ estrazioni sono indipendenti (si rimette il campione nell'urna), quindi la probabilità di non uscire mai è il prodotto delle $n$ probabilità uguali (Indipendenza di eventiA e B sono indipendenti se P(A ∩ B) = P(A) P(B), cioè se sapere che uno si è verificato non cambia la probabilità dell'altro; l'indipendenza passa ai complementari, non va confusa con l'incompatibilità, e per più eventi va richiesta su ogni sottofamiglia.Indipendenza di eventi →): $(1-\frac1n)^n$.
3. Il limite per $n\to\infty$ è il limite notevole $\big(1+\frac xn\big)^n\to e^x$ con $x=-1$ (Limiti notevoli di funzioniI limiti notevoli per le forme 0/0 (log(1+x)/x, (e^x − 1)/x, ((1+x)^α − 1)/x, sin x/x, (1 − cos x)/x², arctan x/x...) con le dimostrazioni, e la loro forma come asintoticità: log(1+f) ~ f, e^f − 1 ~ f, sin f ~ f, 1 − cos f ~ f²/2 quando f → 0.Limiti notevoli di funzioni →, Limiti di successioniUna successione ha limite l se, da un certo indice in poi, i suoi termini stanno vicini a l quanto si vuole; definizioni con epsilon, limiti infiniti e unicità.Limiti di successioni →). Si può vedere anche con i logaritmi: $n\ln(1-\frac1n)\approx n\cdot(-\frac1n)=-1$, perché $\ln(1+u)\approx u$ per $u$ piccolo (Sviluppi di Mac-Laurin notevoliTabella degli sviluppi di Mac-Laurin da sapere a memoria (e^x, sin, cos, log(1+x), (1+x)^alpha, arctan, sinh, cosh, tan) e regole per combinarli: algebra degli o piccoli, prodotti, funzioni composte, quanti termini tenere.Sviluppi di Mac-Laurin notevoli →); quindi la potenza tende a $e^{-1}$.
4. Il complementare, la probabilità che un campione compaia almeno una volta, è $1-e^{-1}=0{,}632$, e il numero atteso di campioni distinti in un bootstrap è $n(1-(1-\frac1n)^n)$, per esempio $6{,}51$ su $n=10$ (la linearità del valore atteso somma $n$ probabilità uguali: Valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso →).

Il bagging riduce la varianza senza aumentare il bias: la previsione di un solo albero è molto sensibile al rumore del suo training, la media di molti alberi non lo è, finché non sono correlati; il bootstrap «decorrela» gli alberi mostrando a ciascuno un training diverso.

Perché il voto di maggioranza aiuta (classificazione). Se $T$ alberi sono indipendenti e ciascuno indovina con probabilità $p>\tfrac12$, il numero di alberi corretti è una variabile binomiale (Prove ripetute e modello binomialen prove indipendenti, ciascuna con probabilità di successo p: una sequenza con k successi ha probabilità p^k (1−p)^(n−k), e la probabilità di esattamente k successi è (n su k) p^k (1−p)^(n−k) (modello binomiale); il primo successo alla prova k ha probabilità (1−p)^(k−1) p.Prove ripetute e modello binomiale →) e la maggioranza è giusta quando i corretti sono almeno $\lfloor T/2\rfloor+1$. Con $T=3$ e $p=0{,}7$: $P=\binom32 0{,}7^2\,0{,}3+\binom33 0{,}7^3=3\cdot0{,}49\cdot0{,}3+0{,}343=0{,}441+0{,}343=0{,}784$. Con $T=5$ sale a $0{,}837$, con $T=11$ a $0{,}922$, con $T=101$ a $0{,}99999$: l'accuratezza della maggioranza supera quella del singolo albero ($0{,}7$). Il calcolo vale solo con alberi indipendenti, che nella pratica non sono ($\rho>0$): per questo l'aumento è più lento, come nel grafico precedente, e si deve decorrelare.

Esempio di voto. Con $T=4$ alberi che predicono $[2,2,1,2]$ per un campione: classe $2$ con $3$ voti su $4$, «confidenza» $0{,}75$ (la frazione di voti per la classe vincente). Nel laboratorio (dataset wine, $T=4$ alberi di profondità 2) l'accuracy sul test è $0{,}919$ e gli errori hanno confidenza $0{,}75$ o $0{,}5$.

Random forest

Definizione (random forest). Bagging in più: a ogni split di ogni albero, invece di valutare tutte le feature se ne estrae a caso un sottoinsieme (tipicamente $\sqrt p$, con $p$ feature) e si sceglie lo split migliore solo tra queste (feature bagging).

Perché. Se una o poche feature sono predittori molto forti, compaiono nella radice di quasi tutti gli alberi e li rendono correlati (cioè $\rho$ alto): la riduzione di varianza svanisce. Il feature bagging obbliga ad esplorare altre feature e abbassa $\rho$.

Caratteristiche. Iperparametro principale: il numero di alberi $T$ (ne basta «abbastanza»; più alberi non causano overfitting ma costano di più). Pro: multiclasse, nessuna normalizzazione dei dati, parte costosa fatta offline, classificazione quasi immediata, accuratezza molto alta. Contro: calcolo oneroso (ma parallelizzabile), minore interpretabilità (non del tutto: vedi l'importanza delle feature). Si usa anche per la regressione (media).

Esempio (laboratorio, wine, feature bagging, $T=10$). Accuracy sul test $0{,}973$ con profondità 2 e 4 e $1{,}0$ con profondità 10; un solo albero di profondità 2-3 dava $0{,}946$-$0{,}973$.

Importanza delle feature

Definizione (importanza di una feature). La misura di quanto una feature è utile alle previsioni, basata su quanto riduce l'impurità quando è usata per dividere. È un approccio «globale» di intelligenza artificiale spiegabile (Explainable AI (XAI)approfondimento: non nel programma di Telecomunicazioni. L'interpretabilità è l'arte di produrre descrizioni di un modello abbastanza semplici da essere capite da un umano; la spiegabilità aggiunge la completezza (permettere di anticipare la previsione). I metodi si classificano in intrinseci o post-hoc, agnostici o specifici del modello, globali o locali. Modelli intrinsecamente interpretabili: regressione lineare (pesi $\beta_j$, intervalli di confidenza, LASSO per la sparsità), regressione logistica ($\log\frac y{1-y}=\beta_0+\sum\beta_jx_j$), alberi. Importanza nelle foreste: MDI $=\sum_{\text{nodi}}\frac{n_p}{n_{TOT}}\Delta Gini$ (con feature selection bias). Metodi agnostici: permutation importance (aumento dell'errore dopo aver mescolato una feature), PDP $\hat f_S(x_S)=\frac1n\sum_if(x_S,x_C^{(i)})$ (media delle curve ICE), LIME (modello semplice locale pesato sui punti perturbati), SHAP (valori di Shapley: media dei contributi marginali su tutti gli ordini, somma $=f(x)-f(\text{base})$). Per le reti profonde: mappe di salienza, Grad-CAM, occlusione. Valutazione: livello applicativo, umano, funzionale. Lab: cardiopatia AHD con logistica, LASSO, random forest, ICE, PDP, SHAP.Explainable AI (XAI) →): dà informazioni sull'intero modello.

Con la Gini, per ogni albero: (1) a ogni nodo interno $p$ la riduzione di impurità è $\Delta\operatorname{Gini}=\operatorname{Gini}(\text{genitore})-\big(\frac{n_{sx}}{n_p}\operatorname{Gini}(\text{sx})+\frac{n_{dx}}{n_p}\operatorname{Gini}(\text{dx})\big)$, pesata per $\frac{n_p}{N}$ ($N$ campioni totali); (2) l'importanza di una feature è la somma di queste riduzioni sui nodi che la usano; (3) nella foresta si media sugli alberi; (4) (opzionale) si normalizza a somma $1$.

I due primi valori, calcolati. Radice: $50$ per classe, $\operatorname{Gini}=1-3\cdot(\tfrac13)^2=\tfrac23=0{,}6667$ (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 →); la divisione isola le $50$ setosa (Gini $0$) dalle altre $100$ ($50$ versicolor e $50$ virginica, Gini $1-2\cdot\frac14=0{,}5$), quindi $\Delta\operatorname{Gini}=0{,}6667-\big(\tfrac{50}{150}\cdot0+\tfrac{100}{150}\cdot0{,}5\big)=0{,}6667-0{,}3333=0{,}3333$, e il peso $\frac{n_p}{N}=\frac{150}{150}=1$. Nodo con $100$ campioni: figli di $54$ ($49$ versicolor e $5$ virginica, Gini $1-(\tfrac{49}{54})^2-(\tfrac5{54})^2=0{,}1680$) e di $46$ (Gini $0{,}0425$): $\Delta\operatorname{Gini}=0{,}5-\big(0{,}54\cdot0{,}1680+0{,}46\cdot0{,}0425\big)=0{,}5-0{,}1103=0{,}3897$, con peso $\frac{100}{150}$, da cui $0{,}2598$. Il peso $\frac{n_p}{N}$ conta quanta parte del training attraversa il nodo: una grande riduzione in un nodo con pochi campioni vale poco.

Esempio (iris, albero di profondità 3). Nodi: radice (150 campioni) con la larghezza del petalo: $\frac{150}{150}\cdot0{,}3333=0{,}3333$; nodo «larghezza $>0{,}8$» (100 campioni, di nuovo larghezza): $\frac{100}{150}\cdot0{,}3897=0{,}2598$; due nodi con la lunghezza del petalo: $\frac{54}{150}\cdot0{,}0824=0{,}0297$ e $\frac{46}{150}\cdot0{,}0135=0{,}0042$. Importanza grezza: larghezza $0{,}3333+0{,}2598=0{,}5931$, lunghezza $0{,}0297+0{,}0042=0{,}0339$; normalizzando (divisione per la somma $0{,}6270$): $0{,}946$ e $0{,}054$ (coincide con feature_importances_ di scikit-learn). Sul dataset wine le feature più importanti sono proline, intensità del colore e flavonoidi.

Come usarla. Per eliminare le feature quasi irrilevanti, capire il fenomeno, guidare la raccolta dati.

Boosting: l'idea

Definizione (boosting). Si costruisce un modello forte (strong learner) combinando in sequenza molti modelli deboli (alberi con pochi split); ciascun nuovo modello cerca di correggere gli errori dei precedenti. La combinazione è una somma pesata.

Il bagging addestra gli alberi in parallelo e riduce la varianza; il boosting li addestra in sequenza e riduce il bias, ma è sensibile al rumore.

Gradient boosting (regressione)

Si ripete: (1) si parte da una predizione costante (la media dei target); (2) si calcolano i residui $r_i=y_i-F(x_i)$; (3) si addestra un albero di regressione che predice i residui, con un vincolo sul numero massimo di foglie (da 8 a 32 in pratica; 4 nell'esempio); (4) si aggiorna $F\leftarrow F+\eta\,h$, con il tasso di apprendimento $\eta$ piccolo (per esempio $0{,}1$); (5) si ripete finché i residui sono piccoli o si raggiunge il numero massimo di alberi. Nella foglia con più residui si mette la media dei residui.

Formula (gradient boosting). $F_0=\bar y$, $\ r_i=y_i-F_{m}(x_i)$, $\ F_{m+1}(x)=F_m(x)+\eta\,h_m(x)$. Predizione finale: $F_M(x)=F_0+\eta\sum_mh_m(x)$.

Perché si chiama «gradient». Per la perdita quadratica $\ell=\tfrac12(y-F)^2$ il gradiente rispetto alla predizione è $\partial\ell/\partial F=-(y-F)$, quindi il residuo è il gradiente negativo della perdita (Differenziabilità e gradientef è differenziabile in x0 se f(x) = f(x0) + ∇f(x0)·(x − x0) + o(‖x − x0‖): vicino a x0 il grafico si confonde con il piano tangente z = f(x0) + ∇f(x0)·(x − x0). Differenziabile ⇒ continua, derivabile e D_v f = ∇f·v; derivate parziali continue ⇒ differenziabile. Il gradiente indica la direzione di massima crescita (pendenza ‖∇f‖) ed è ortogonale alle curve di livello.Differenziabilità e gradiente →): ogni nuovo albero fa un passo di discesa del gradiente nello spazio delle funzioni (LASSO e discesa del gradienteIl LASSO è la regressione regolarizzata con penalità $L_1$: minimizza $\sum_i(y_i-x_i^T\beta)^2+\lambda\sum_{j\ge1}|\beta_j|$. A differenza della ridge, porta alcuni coefficienti esattamente a zero (soluzione sparsa, selezione delle feature): geometricamente le curve di livello dell'errore toccano il vincolo $\sum|\beta_j|\le s$ (un rombo) in uno spigolo. Non ha formula chiusa, quindi si minimizza con la discesa del gradiente $W\leftarrow W-\eta,\nabla J(W)$, usando il subgradiente $\operatorname{sign}(\beta_j)$ per il valore assoluto (nel punto 0 qualunque valore in $[-1,1]$). Il passo $\eta$ è critico: per l'errore quadratico converge se $\eta<1/\mu_{\max}(X^TX)$; si può usare $\eta_t=\eta_0/(1+\gamma t)$. L'Elastic Net combina le penalità $L_1$ e $L_2$ con $\lambda_1=\alpha\lambda$, $\lambda_2=(1-\alpha)\lambda$.LASSO e discesa del gradiente →). Per la classificazione con log-verosimiglianza si adattano gli pseudo-residui $y-p$ ($p=\sigma(F)$, la probabilità prevista) e la probabilità finale è $p=\sigma(F_M(x))$ (Regressione logistica e softmaxLa regressione lineare non è adatta alla classificazione (valori fuori da [0,1], retta tirata dai punti lontani). La regressione logistica passa il predittore lineare dalla sigmoide $\sigma(z)=1/(1+e^{-z})$ e interpreta $\hat y=\sigma(x^T\beta)$ come $P(y=1\mid x)$: si predice la classe 1 se $\hat y\ge0{,}5$, cioè $x^T\beta\ge0$ (bordo lineare). L'errore quadratico dà una funzione non convessa; si usa la log-verosimiglianza negativa $-\sum[y\log\hat y+(1-y)\log(1-\hat y)]$, convessa, con gradiente $X^T(\hat y-y)$ e nessuna formula chiusa (discesa del gradiente). Per più classi: one-vs-one ($C(C-1)/2$ classificatori, voto), one-vs-all ($C$ classificatori, massima probabilità), o la softmax $p_c=e^{z_c}/\sum_ke^{z_k}$ con cross-entropia. Si può regolarizzare (ridge, LASSO, Elastic Net) e la cross-validation si fa stratificata. Approfondimento: non nel programma di Telecomunicazioni.Regressione logistica e softmax →).

Esempio (dalle slide). Pesi osservati $y=[88,76,56,73,77,57]$ (altezza, colore preferito, genere come feature). Predizione iniziale: la media $71{,}2$ (esattamente $71{,}17$). Residui: $[16{,}8;\ 4{,}8;\ -15{,}2;\ 1{,}8;\ 5{,}8;\ -14{,}2]$. Primo albero con 4 foglie: $\{-14{,}2,-15{,}2\}\to-14{,}7$ (media), $\{4{,}8\}\to4{,}8$, $\{1{,}8,5{,}8\}\to3{,}8$, $\{16{,}8\}\to16{,}8$. Con $\eta=0{,}1$ la prima osservazione passa da $71{,}2$ a $71{,}2+0{,}1\cdot16{,}8=72{,}88$ e il nuovo residuo è $88-72{,}88=15{,}12$ (prima $16{,}8$: ha fatto un «piccolo passo» nella direzione giusta). Residui dopo il primo albero: $[15{,}1;\ 4{,}3;\ -13{,}7;\ 1{,}4;\ 5{,}4;\ -12{,}7]$. Secondo albero: foglie $-13{,}2$, $4{,}3$, $3{,}4$, $15{,}1$; residui dopo il secondo: $[13{,}6;\ 3{,}9;\ -12{,}4;\ 1{,}1;\ 5{,}1;\ -11{,}4]$. Ad ogni albero i residui si riducono (l'errore quadratico medio sul training passa da $129$ a circa $105$ e $85$).

Perché piccoli passi. Con $\eta=0{,}1$ si perde accuratezza sul training (si usa solo una piccola parte di ciascun albero) nella speranza di una migliore generalizzazione (meno overfitting e meno varianza): l'evidenza empirica mostra che «molti piccoli passi nella direzione giusta» danno previsioni migliori sul test. Gli iperparametri tipici: numero di alberi, tasso di apprendimento, profondità o numero di foglie.

Nel laboratorio (wine). GradientBoostingClassifier(n_estimators=100, learning_rate=0.1, max_depth=3): accuracy sul test $1{,}0$; implementazione da zero per la regressione con alberi a criterio MSE e foglie con media.

AdaBoost

AdaBoost (adaptive boosting) è molto simile ma con due differenze: (1) usa solo stump, alberi con una sola decisione (2 foglie); (2) i modelli hanno pesi diversi nella somma finale (nel gradient boosting tutti gli alberi sono scalati dallo stesso fattore). I campioni mal classificati ricevono più peso nello stump successivo. Le formule standard (non nelle slide), per classi $\pm1$ e pesi $w_i$ che sommano a $1$: $$\varepsilon_t=\sum_{i\,\text{errati}}w_i,\qquad\alpha_t=\frac12\ln\frac{1-\varepsilon_t}{\varepsilon_t},\qquad w_i\leftarrow\frac{w_i\,e^{\mp\alpha_t}}{Z_t}\ (\times\,e^{+\alpha_t}\text{ se errato, }\times\,e^{-\alpha_t}\text{ se corretto}),\qquad H(x)=\operatorname{sign}\Big(\sum_t\alpha_th_t(x)\Big),$$ con $Z_t$ che normalizza i pesi.

Da dove viene $\alpha_t$ (passaggi). AdaBoost minimizza la perdita esponenziale $\sum_iw_ie^{-\alpha y_ih(x_i)}$, dove $y_ih(x_i)=+1$ se lo stump è corretto sul campione $i$ e $-1$ se è errato. Raggruppando i campioni corretti (peso totale $1-\varepsilon$) e quelli errati (peso totale $\varepsilon$): $Z(\alpha)=(1-\varepsilon)e^{-\alpha}+\varepsilon e^{\alpha}$. Si deriva rispetto ad $\alpha$ (Regole di derivazioneDerivate delle funzioni elementari e delle loro inverse (arcsin, arctan, settcosh...) e regole di calcolo: linearità, prodotto (Leibniz), quoziente, funzione composta (regola della catena), funzione inversa, f(x)^g(x).Regole di derivazione →; $(e^{\alpha})'=e^{\alpha}$): $Z'(\alpha)=-(1-\varepsilon)e^{-\alpha}+\varepsilon e^{\alpha}=0$, quindi $e^{2\alpha}=\frac{1-\varepsilon}{\varepsilon}$ e, prendendo il logaritmo (Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →), $\alpha=\frac12\ln\frac{1-\varepsilon}{\varepsilon}$. La derivata seconda $Z''=(1-\varepsilon)e^{-\alpha}+\varepsilon e^{\alpha}>0$ garantisce che sia un minimo (Massimi e minimi relativi e teorema di Fermatx0 è punto di minimo (massimo) relativo se f(x0) ≤ f(x) (≥) per gli x del dominio vicini a x0. I candidati sono gli estremi del dominio, i punti dove f non è derivabile e i punti interni con f'(x0) = 0 (punti critici o stazionari). Teorema di Fermat: in un punto interno di minimo o massimo relativo dove f è derivabile, f'(x0) = 0. È solo una condizione necessaria: x³ in 0.Massimi e minimi relativi e teorema di Fermat →). Il valore minimo è $Z=2\sqrt{\varepsilon(1-\varepsilon)}$, che è anche la costante di normalizzazione dei pesi. Se $\varepsilon=\tfrac12$ (stump che indovina a caso) si ha $\alpha=0$: voto nullo; se $\varepsilon\to0$, $\alpha\to\infty$.

Esempio. 5 campioni con pesi $0{,}2$ e uno stump che ne sbaglia uno: $\varepsilon=0{,}2$, $\alpha=\tfrac12\ln\frac{0{,}8}{0{,}2}=\tfrac12\ln4=0{,}693$. Il campione errato passa a $0{,}2\,e^{0{,}693}=0{,}4$, gli altri a $0{,}2\,e^{-0{,}693}=0{,}1$ (somma $0{,}8$): dopo la normalizzazione l'errato pesa $0{,}5$ e ciascuno degli altri $0{,}125$. Il prossimo stump è addestrato in modo che l'errore precedente conti metà del totale.

XGBoost

XGBoost è un approccio di stato dell'arte, pieno di trucchi implementativi; qui si vede la parte concettuale. Sfrutta: (1) il boosting (alberi in sequenza); (2) un modo nuovo di costruire gli alberi, sempre basato sui residui; (3) la regolarizzazione.

Punteggio di similarità e guadagno. Si parte da una predizione iniziale (per esempio $0{,}5$) e si calcolano i residui. Un nodo con residui simili (stesso segno e grandezza) è «buono». Per misurarlo:

Formula (similarity score, gain, output). Con $\lambda$ parametro di regolarizzazione: $$\text{Similarity}=\frac{\big(\sum\text{residui}\big)^2}{N_{\text{residui}}+\lambda},\qquad \text{Gain}=\text{Sim}_{\text{sx}}+\text{Sim}_{\text{dx}}-\text{Sim}_{\text{genitore}},\qquad \text{Output}=\frac{\sum\text{residui}}{N_{\text{residui}}+\lambda}.$$ Attenzione: nell'output la somma non è al quadrato.

Da dove vengono le formule (passaggi, perdita quadratica). In una foglia con $N$ residui $r_i$ si cerca l'output $o$ che minimizza $L(o)=\sum_i(r_i-o)^2+\lambda o^2$ (l'ultimo termine è la regolarizzazione che penalizza output grandi, come nella ridge: 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 →).

1. Derivata: $L'(o)=-2\sum_i(r_i-o)+2\lambda o=-2\sum_ir_i+2No+2\lambda o$.
2. Si pone $L'(o)=0$ (Massimi e minimi relativi e teorema di Fermatx0 è punto di minimo (massimo) relativo se f(x0) ≤ f(x) (≥) per gli x del dominio vicini a x0. I candidati sono gli estremi del dominio, i punti dove f non è derivabile e i punti interni con f'(x0) = 0 (punti critici o stazionari). Teorema di Fermat: in un punto interno di minimo o massimo relativo dove f è derivabile, f'(x0) = 0. È solo una condizione necessaria: x³ in 0.Massimi e minimi relativi e teorema di Fermat →): $(N+\lambda)o=\sum_ir_i$, cioè $o^*=\dfrac{\sum r_i}{N+\lambda}$. Con $\lambda=0$ è la media dei residui, come nel gradient boosting; con $\lambda>0$ la media è «ristretta» verso $0$. $L''=2(N+\lambda)>0$: è un minimo.
3. Si sostituisce $o^*$ in $L$ e si confronta con $L(0)=\sum r_i^2$ (nessuna correzione): la riduzione di perdita è $L(0)-L(o^*)=\sum r_i^2-\Big[\sum r_i^2-2o^*\sum r_i+(N+\lambda)o^{*2}\Big]=2o^*\sum r_i-(N+\lambda)o^{*2}$. Poiché $(N+\lambda)o^*=\sum r_i$, i due termini valgono $2\frac{(\sum r)^2}{N+\lambda}$ e $\frac{(\sum r)^2}{N+\lambda}$, e la differenza è $\dfrac{(\sum r_i)^2}{N+\lambda}$: ecco la similarità, cioè la riduzione di perdita ottenuta da una foglia. Il gain è la riduzione ottenuta dividendo il nodo in due foglie (somma delle due similarità) meno quella che si avrebbe senza dividere (similarità del genitore); è positivo quando i due figli «spiegano» più residuo del genitore.

Si provano tutte le soglie e si sceglie quella con gain massimo.

Esempio (dalle slide). Dosaggi $[10,20,25,35]$ mg, efficacia $[-10,7,8,-7]$, predizione iniziale $0{,}5$: residui $[-10{,}5;\ 6{,}5;\ 7{,}5;\ -7{,}5]$, con $\lambda=0$. Radice: somma $=-4$, similarità $\frac{(-4)^2}{4}=4$. Soglia «dosaggio $<15$»: sinistra $\{-10{,}5\}$: $\frac{110{,}25}{1}=110{,}25$; destra $\{6{,}5;\ 7{,}5;\ -7{,}5\}$ (somma $6{,}5$): $\frac{42{,}25}{3}=14{,}08$; gain $=110{,}25+14{,}08-4=\mathbf{120{,}33}$. Soglia «$<22{,}5$»: sinistra $\{-10{,}5;\ 6{,}5\}$ (somma $-4$): $\frac{16}{2}=8$; destra $\{7{,}5;\ -7{,}5\}$ (somma 0): $0$; gain $=8+0-4=4$. Soglia «$<30$»: sinistra (somma $3{,}5$): $\frac{12{,}25}{3}=4{,}08$; destra $\{-7{,}5\}$: $56{,}25$; gain $=4{,}08+56{,}25-4=56{,}33$. Si sceglie «dosaggio $<15$». Il ramo destro $\{6{,}5;7{,}5;-7{,}5\}$ si divide ancora con «$<30$»: sinistra $\{6{,}5;7{,}5\}$ (somma 14): $\frac{196}2=98$; destra $\{-7{,}5\}$: $56{,}25$; gain $=98+56{,}25-14{,}08=140{,}17$ (profondità massima 2 nell'esempio; in pratica 6).

Potatura con $\gamma$. Una volta costruito l'albero si pota dal basso verso l'alto: si sceglie una soglia $\gamma$ (iperparametro di XGBoost) e si toglie un ramo se $\text{Gain}-\gamma<0$. Con $\gamma=130$: il nodo con gain $140{,}17$ ha $140{,}17-130=10{,}17>0$, quindi resta; la radice ha gain $120{,}33<130$, ma non si può potare perché il ramo sotto non è stato potato. Con $\gamma=150$: $140{,}17-150<0$ (si pota) e poi $120{,}33-150<0$ (si pota anche la radice): l'albero scompare. Un valore alto di $\gamma$ previene l'overfitting.

Regolarizzazione $\lambda$. Con $\lambda>0$ le similarità sono più piccole, e la riduzione è tanto maggiore quanto meno residui ha il nodo ($\lambda=1$: radice $\frac{16}{4+1}=3{,}2$; sinistra $\frac{110{,}25}{2}=55{,}12$; destra $\frac{42{,}25}{4}=10{,}56$; gain $=55{,}12+10{,}56-3{,}2=62{,}48$). Questo rende più facile potare e riduce la sensibilità a singole osservazioni.

Predizione. In inferenza ogni foglia restituisce $\text{Output}=\frac{\sum r}{N+\lambda}$ (non è la similarità): per la foglia con residui $6{,}5;\ 7{,}5;\ -7{,}5$ ed $\lambda=1$: $\frac{6{,}5}{3+1}=1{,}625$; con $\lambda=0$ è la media: $\{6{,}5;7{,}5\}\to7$, $\{-10{,}5\}\to-10{,}5$, $\{-7{,}5\}\to-7{,}5$. La nuova predizione è $\text{vecchia}+\varepsilon\cdot\text{Output}$, con $\varepsilon$ (eta) il tasso di apprendimento (default $0{,}3$ in XGBoost): per il dosaggio $10$: $0{,}5+0{,}3\cdot(-10{,}5)=-2{,}65$ (residuo $-10-(-2{,}65)=-7{,}35$, minore di prima); per i dosaggi $20,25$: $0{,}5+0{,}3\cdot7=2{,}6$; per $35$: $0{,}5+0{,}3\cdot(-7{,}5)=-1{,}75$. Si continua ad aggiungere alberi finché i residui sono molto piccoli o si raggiunge il massimo.

Altre caratteristiche citate: penalità $L_1$ e $L_2$ (regolarizzazione come nella ridgeUna 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 → e nel LASSOIl LASSO è la regressione regolarizzata con penalità $L_1$: minimizza $\sum_i(y_i-x_i^T\beta)^2+\lambda\sum_{j\ge1}|\beta_j|$. A differenza della ridge, porta alcuni coefficienti esattamente a zero (soluzione sparsa, selezione delle feature): geometricamente le curve di livello dell'errore toccano il vincolo $\sum|\beta_j|\le s$ (un rombo) in uno spigolo. Non ha formula chiusa, quindi si minimizza con la discesa del gradiente $W\leftarrow W-\eta,\nabla J(W)$, usando il subgradiente $\operatorname{sign}(\beta_j)$ per il valore assoluto (nel punto 0 qualunque valore in $[-1,1]$). Il passo $\eta$ è critico: per l'errore quadratico converge se $\eta<1/\mu_{\max}(X^TX)$; si può usare $\eta_t=\eta_0/(1+\gamma t)$. L'Elastic Net combina le penalità $L_1$ e $L_2$ con $\lambda_1=\alpha\lambda$, $\lambda_2=(1-\alpha)\lambda$.LASSO e discesa del gradiente →), algoritmo basato su istogrammi per cercare gli split più velocemente, potatura in profondità, passo adattivo, campionamento di colonne e righe. LightGBM è più veloce con crescita per foglia, CatBoost tratta nativamente le variabili categoriche.

Codice

from sklearn.ensemble import RandomForestClassifier, GradientBoostingClassifier
from xgboost import XGBClassifier

rf  = RandomForestClassifier(n_estimators=200, max_features="sqrt", random_state=0).fit(X_train, y_train)
gb  = GradientBoostingClassifier(n_estimators=100, learning_rate=0.1, max_depth=3, random_state=0).fit(X_train, y_train)
xgb = XGBClassifier(n_estimators=100, learning_rate=0.1, random_state=0).fit(X_train, y_train)
print(rf.feature_importances_)            # importanza globale delle feature (Gini)

# bagging da zero: campione bootstrap e voto di maggioranza
def bootstrap_sample(X, y):
    idx = np.random.choice(len(X), size=len(X), replace=True)   # con rimpiazzo
    return X[idx], y[idx]

Errori tipici

• Pensare che aggiungere alberi a una random forest faccia overfitting: la varianza si stabilizza.
• Dimenticare il feature bagging: senza di esso gli alberi sono molto correlati.
• Usare $\eta$ troppo grande nel boosting: si impara troppo in fretta e si va in overfitting.
• Confondere similarity score (numeratore al quadrato, per scegliere gli split) e output della foglia (numeratore non al quadrato).
• Confrontare bagging e boosting come se riducessero la stessa cosa: il primo riduce la varianza, il secondo il bias.
• Interpretare l'importanza delle feature (basata sulla Gini) come causalità: misura solo quanto servono al modello, ed è distorta per feature con molti valori.