Alberi di Regressione, Bagging e Boosting¶

La Storia Dietro la Matematica¶

Negli anni '80, gli statistici affrontavano una crisi crescente. I modelli lineari—regressione lineare, regressione logistica—erano eleganti e interpretabili, ma il mondo reale era disperatamente non lineare. I ricercatori avevano dati con interazioni complesse, soglie e strutture gerarchiche che le equazioni lineari semplicemente non potevano catturare.

Leo Breiman (1928-2005), uno statistico alla UC Berkeley, fu tra i primi a riconoscere che il campo aveva bisogno di un cambiamento di paradigma. Dopo aver lasciato l'accademia per diventare consulente, vide di persona quanto fossero disordinati i dati reali. Nel 1984, co-autorizzò "Classification and Regression Trees" (CART) con Jerome Friedman, Richard Olshen e Charles Stone. La loro intuizione radicale: invece di adattare un'unica equazione globale, partizionare lo spazio dei dati ricorsivamente in regioni più semplici.

Ma gli alberi avevano un difetto fatale—erano instabili. Piccoli cambiamenti nei dati di addestramento potevano produrre alberi drasticamente diversi. Questo problema di varianza limitava il loro uso pratico.

La svolta arrivò nel 1996 quando Leo Breiman introdusse il Bagging (Bootstrap Aggregating). La sua idea era quasi assurda nella sua semplicità: se un albero è instabile, addestra centinaia di alberi su sottoinsiemi casuali di dati e media le loro previsioni. La varianza diminuisce e l'accuratezza aumenta.

Ma la vera rivoluzione fu il Boosting. Nel 1997, Yoav Freund e Robert Schapire pubblicarono AdaBoost, dimostrando che una sequenza di "apprenditori deboli" poteva combinarsi in un "apprenditore forte". Invece di mediare alberi indipendenti, il boosting addestra gli alberi sequenzialmente, con ogni nuovo albero che si concentra sugli esempi che quelli precedenti avevano sbagliato.

Il cambiamento di paradigma: Dal "trovare il miglior modello unico" al "combinare molti modelli semplici". Questo divenne il fondamento dei moderni metodi di ensemble e vinse il Premio Gödel 2003 per la sua significanza teorica.

Perché è Importante¶

I metodi basati su alberi sono ora l'approccio dominante nel machine learning:

Competizioni Kaggle: XGBoost e LightGBM (alberi potenziati) hanno vinto la maggior parte delle competizioni su dati strutturati
Finanza: Valutazione del credito, rilevamento frodi, trading algoritmico
Medicina: Diagnosi di malattie, predizione della risposta ai farmaci, analisi di sopravvivenza
E-commerce: Sistemi di raccomandazione, predizione abbandono, ottimizzazione prezzi
Genomica: Analisi espressione genica, rilevamento SNP
Elaborazione del Linguaggio Naturale: Feature engineering, classificazione testi
IoT: Analisi dati sensori, rilevamento anomalie

Questi metodi sono i cavalli da lavoro del machine learning applicato perché: - Gestiscono tipi di dati misti (numerici, categorici) naturalmente - Catturano relazioni non lineari senza feature engineering esplicito - Forniscono misure di importanza delle feature - Sono robusti agli outlier e valori mancanti - Scalano bene con dataset di grandi dimensioni

Prerequisiti¶

Likelihood-Based-Statistics — Comprensione stima e ottimizzazione
Variance — Concetto chiave per comprendere il tradeoff bias-varianza
Gaussian-Distribution — Per comprendere le funzioni di perdita
Calcolo di base (gradienti, ottimizzazione)
Familiarità con concetti di apprendimento statistico (overfitting, cross-validation)

L'Intuizione di Base¶

La Decomposizione Bias-Varianza¶

Il problema fondamentale nell'apprendimento supervisionato può essere compreso attraverso il tradeoff bias-varianza. Per un modello di previsione $\hat{f}(x)$ della funzione vera $f(x)$, l'errore di previsione atteso si decompone come:

\[ E[(Y - \hat{f}(X))^2] = \text{Bias}^2 + \text{Varianza} + \text{Errore Irreducibile} \]

Dove:

Bias: $E[\hat{f}(X)] - f(X)$ — Quanto la previsione media differisce dalla verità
Varianza: $E[(\hat{f}(X) - E[\hat{f}(X)])^2]$ — Quanto le previsioni variano tra diversi set di addestramento

Intuizione chiave: C'è un tradeoff. I modelli semplici (regressione lineare) hanno alto bias ma bassa varianza. I modelli complessi (alberi profondi) hanno basso bias ma alta varianza. I metodi di ensemble riducono la varianza senza aumentare il bias mediando più modelli.

Alberi di Regressione¶

Cos'è un Albero di Regressione?¶

Un albero di regressione è una funzione costante a tratti che partiziona lo spazio di input in regioni rettangolari e assegna una previsione costante a ciascuna regione.

\[ \hat{f}(x) = \sum_{m=1}^{M} c_m \cdot \mathbb{1}_{R_m}(x) \]

Dove $R_1, \ldots, R_M$ sono le regioni e $c_m$ è la previsione nella regione $R_m$.

Costruire un Albero: L'Algoritmo Greedy¶

Passo 1: Criterio di Suddivisione

In ogni nodo, cerchiamo la suddivisione che minimizza la somma degli errori quadrati:

\[ \min_{j,s} \left[ \min_{c_1} \sum_{x_i \in R_1(j,s)} (y_i - c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i - c_2)^2 \right] \]

Dove: - $j$ è la feature su cui suddividere - $s$ è il punto di suddivisione - $R_1(j,s) = \{X | X_j \leq s\}$ e $R_2(j,s) = \{X | X_j > s\}$

Passo 2: Previsione Ottimale in Ogni Regione

La costante ottimale $c_m$ è semplicemente la media delle risposte in quella regione:

\[ \hat{c}_m = \frac{1}{n_m} \sum_{x_i \in R_m} y_i = \bar{y}_{R_m} \]

Passo 3: Suddivisione Ricorsiva

Ripetere il processo di suddivisione su ogni nuova regione finché non si raggiunge un criterio di arresto (es. minimo campioni per foglia, profondità massima, o nessun miglioramento nella perdita).

Perché l'errore quadratico? Porta alla media campionaria come previsione ottimale. Altre perdite portano a previsioni diverse (es. errore assoluto porta alla mediana).

Perché gli Alberi Hanno Alta Varianza¶

Gli alberi sono instabili perché: 1. Il processo di suddivisione greedy è sensibile a piccoli cambiamenti dei dati 2. La natura gerarchica compone gli errori: le suddivisioni iniziali causano effetti a cascata 3. La struttura costante a tratti crea discontinuità

Un albero con profondità $d$ ha approssimativamente $2^d$ foglie, rendendolo molto flessibile—ma la flessibilità ha il costo della varianza.

Bagging (Bootstrap Aggregating)¶

Il Principio del Bootstrap¶

Il bootstrap è una tecnica di ricampionamento. Dato un dataset di dimensione $n$, creiamo $B$ campioni bootstrap campionando con ripetizione. Ogni campione bootstrap ha anche dimensione $n$ ma contiene approssimativamente il $63.2\%$ delle osservazioni uniche (il resto sono duplicati).

Perché $63.2\%$? La probabilità che una data osservazione non sia selezionata in un'estrazione è $(1 - 1/n)$. Per $n$ estrazioni:

\[ P(\text{non selezionata}) = \left(1 - \frac{1}{n}\right)^n \approx e^{-1} \approx 0.368 \]

Quindi la probabilità di essere selezionata almeno una volta è $1 - 0.368 = 0.632$.

L'Algoritmo Bagging¶

Passo 1: Generare Campioni Bootstrap

Per $b = 1, \ldots, B$: - Campiona $n$ osservazioni con ripetizione dai dati di addestramento

Passo 2: Addestrare Apprenditori Base

Per ogni campione bootstrap $b$, addestra un albero di regressione $\hat{f}_b(x)$.

Passo 3: Aggregare le Previsioni

Per la regressione, media le previsioni:

\[ \hat{f}_{\text{bag}}(x) = \frac{1}{B} \sum_{b=1}^{B} \hat{f}_b(x) \]

Per la classificazione, prendi il voto di maggioranza.

Perché il Bagging Funziona: Riduzione della Varianza¶

Teorema Chiave: Se $\hat{f}_b$ sono identicamente distribuiti con varianza $\sigma^2$ e correlazione pari a $\rho$, allora:

\[ \text{Var}\left(\frac{1}{B} \sum_{b=1}^{B} \hat{f}_b\right) = \rho \sigma^2 + \frac{1 - \rho}{B} \sigma^2 \]

Dimostrazione:

Sia $Z_b = \hat{f}_b(x)$. Allora:

\[ \text{Var}\left(\frac{1}{B} \sum_{b=1}^{B} Z_b\right) = \frac{1}{B^2} \sum_{i=1}^{B} \sum_{j=1}^{B} \text{Cov}(Z_i, Z_j) \]

Ci sono $B$ termini di varianza e $B(B-1)$ termini di covarianza:

\[ = \frac{1}{B^2} \left[ B \cdot \sigma^2 + B(B-1) \cdot \rho \sigma^2 \right] \]

\[ = \frac{\sigma^2}{B} + \frac{B(B-1)\rho \sigma^2}{B^2} \]

\[ = \frac{\sigma^2}{B} + \rho \sigma^2 \left(1 - \frac{1}{B}\right) \]

\[ = \rho \sigma^2 + \frac{(1 - \rho)\sigma^2}{B} \]

Interpretazione: - Per $B \to \infty$, la varianza si avvicina a $\rho \sigma^2$ (la correlazione irriducibile) - Se gli alberi fossero incorrelati ($\rho = 0$), la varianza andrebbe a zero come $1/B$ - Il campionamento bootstrap crea alberi diversi mantenendoli ragionevolmente accurati

Stima dell'Errore Out-of-Bag¶

Ogni osservazione appare in approssimativamente il $63.2\%$ dei campioni bootstrap. Il rimanente $36.8\%$ è out-of-bag (OOB).

Per l'osservazione $i$, la previsione OOB è:

\[ \hat{f}_{\text{OOB}}(x_i) = \frac{1}{B_i} \sum_{b: i \notin S_b} \hat{f}_b(x_i) \]

Dove $B_i$ è il numero di alberi dove $i$ era out-of-bag. L'errore OOB è una stima non distorta dell'errore di test—nessuna cross-validation necessaria!

Random Forest¶

Il Problema con il Bagging di Alberi¶

Gli alberi in bagging sono ancora correlati perché usano tutti le stesse feature forti per le suddivisioni iniziali. Questo limita la riduzione della varianza.

Random Forest: Decorrelazione tramite Sottocampionamento delle Feature¶

Ad ogni suddivisione, Random Forest considera solo un sottoinsieme casuale di $m \ll p$ feature.

Algoritmo: 1. Per $b = 1, \ldots, B$: - Estrai campione bootstrap $S_b$ - Addestra albero $\hat{f}_b$ dove ogni suddivisione considera solo $m$ feature selezionate casualmente 2. Media le previsioni: $\hat{f}_{\text{rf}}(x) = \frac{1}{B} \sum_{b=1}^{B} \hat{f}_b(x)$

Valore tipico: $m = \sqrt{p}$ per classificazione, $m = p/3$ per regressione.

Perché questo riduce la correlazione: - Se una feature è molto predittiva, tutti gli alberi in bagging la useranno per la prima suddivisione - Random Forest forza gli alberi a considerare altre feature, creando diversità - Correlazione $\rho$ più bassa significa varianza di ensemble più bassa

Boosting¶

La Differenza Fondamentale¶

Mentre il bagging addestra gli alberi indipendentemente e li media, il boosting addestra gli alberi sequenzialmente, con ogni albero che si concentra sugli errori dei precedenti.

AdaBoost (Adaptive Boosting)¶

Idea di Base: Addestra una sequenza di apprenditori deboli, ponderando ogni osservazione in base a quanto male gli apprenditori precedenti l'hanno classificata.

Algoritmo:

Inizializza i pesi delle osservazioni: $w_i = 1/n$ per tutti gli $i$.

Per $m = 1, \ldots, M$:

Adatta apprenditore debole $G_m(x)$ ai dati di addestramento pesati
Calcola l'errore pesato:

\[ \text{err}_m = \frac{\sum_{i=1}^{n} w_i \cdot \mathbb{1}_{[y_i \neq G_m(x_i)]}}{\sum_{i=1}^{n} w_i} \]

Calcola il peso dell'apprenditore:

\[ \alpha_m = \log\left(\frac{1 - \text{err}_m}{\text{err}_m}\right) \]

Aggiorna i pesi delle osservazioni:

\[ w_i \leftarrow w_i \cdot \exp(\alpha_m \cdot \mathbb{1}_{[y_i \neq G_m(x_i)]}) \]

Normalizza i pesi per sommare a 1.

Classificatore finale:

\[ G(x) = \text{sign}\left(\sum_{m=1}^{M} \alpha_m G_m(x)\right) \]

Perché pesi esponenziali? AdaBoost minimizza la perdita esponenziale:

\[ L(y, f(x)) = \exp(-y \cdot f(x)) \]

Dove $f(x) = \sum_m \alpha_m G_m(x)$ è il modello additivo.

Gradient Boosting¶

AdaBoost è per la classificazione. Per la regressione, il Gradient Boosting generalizza l'idea.

Idea di Base: Adatta nuovi alberi al gradiente negativo (pseudo-residui) della funzione di perdita.

Algoritmo:

Inizializza: $\hat{f}_0(x) = \arg\min_c \sum_{i=1}^{n} L(y_i, c)$
Per $m = 1, \ldots, M$:

a. Calcola i pseudo-residui:

$$ r_{im} = -\left[\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}\right]{f = \hat{f} $$}

b. Adatta albero di regressione ai residui $r_{im}$, ottenendo regioni terminali $R_{jm}$

c. Calcola la previsione ottimale in ogni regione:

$$ c_{jm} = \arg\min_c \sum_{x_i \in R_{jm}} L(y_i, \hat{f}_{m-1}(x_i) + c) $$

d. Aggiorna il modello:

$$ \hat{f}m(x) = \hat{f}}(x) + \nu \cdot \sum_{j} c_{jm} \cdot \mathbb{1{R(x) $$}

  Dove $\nu \in (0, 1]$ è il learning rate (shrinkage).

Per la perdita quadratica: $L(y, f) = (y - f)^2$

Il pseudo-residuo è:

\[ r_{im} = -\frac{\partial}{\partial f} (y_i - f)^2 \bigg|_{f = \hat{f}_{m-1}(x_i)} = 2(y_i - \hat{f}_{m-1}(x_i)) \]

Quindi adattiamo gli alberi ai residui correnti!

Perché lo Shrinkage Aiuta¶

Il learning rate $\nu$ rallenta l'apprendimento:

\[ \hat{f}_m(x) = \hat{f}_{m-1}(x) + \nu \cdot h_m(x) \]

Tradeoff: $\nu$ più piccolo richiede più alberi $M$ ma tipicamente ottiene una generalizzazione migliore. È come la discesa del gradiente con un passo più piccolo—più lenta ma più precisa.

Valori tipici: $\nu = 0.01$ a $0.1$, con $M = 100$ a $1000$ alberi.

Confronto dei Metodi¶

Aspetto	Albero Singolo	Bagging	Random Forest	Boosting
Addestramento	Modello singolo	Parallelo	Parallelo	Sequenziale
Bias	Basso (se profondo)	Come l'albero	Come l'albero	Basso (ridotto)
Varianza	Alta	Ridotta	Ulteriormente ridotta	Ridotta
Overfitting	Sì	Meno	Ancora meno	Possibile (controlla con $\nu$)
Outlier	Sensibile	Robusto	Robusto	Sensibile
Interpretabilità	Alta	Bassa	Bassa	Bassa
Velocità Addestramento	Veloce	Parallelizzabile	Parallelizzabile	Lenta (sequenziale)
Velocità Previsione	Veloce	Lenta ($B$ alberi)	Lenta ($B$ alberi)	Lenta ($M$ alberi)

Importanza delle Feature¶

Mean Decrease in Impurity (MDI)¶

Per metodi basati su alberi, l'importanza della feature $j$ è:

\[ \text{Importance}_j = \frac{1}{B} \sum_{b=1}^{B} \sum_{t \in T_{b,j}} n_t \cdot \Delta i(t) \]

Dove: - $T_{b,j}$ è l'insieme delle suddivisioni sulla feature $j$ nell'albero $b$ - $n_t$ è il numero di campioni che raggiungono il nodo $t$ - $\Delta i(t)$ è la diminuzione di impurità dalla suddivisione

Permutation Importance¶

Più affidabile ma computazionalmente costosa:

Addestra il modello, calcola l'errore di base
Per ogni feature $j$:
Permuta casualmente i valori della feature $j$ nel set di validazione
Calcola il nuovo errore
Importanza = aumento dell'errore

Linee Guida Pratiche¶

Quando Usare Cosa¶

Albero Singolo: Quando l'interpretabilità è fondamentale e le relazioni sono semplici

Random Forest: - Scelta predefinita per dati tabellari - Buon baseline prima di provare metodi più complessi - Robusto, funziona bene out-of-the-box - Stima errore OOB integrata

Gradient Boosting (XGBoost, LightGBM, CatBoost): - Quando serve l'accuratezza massima - Dataset grandi (il boosting scala meglio) - Disposti a fare tuning degli iperparametri - Competizioni Kaggle

Tuning degli Iperparametri¶

Random Forest: - n_estimators: Più è meglio (finché converge), tipicamente 100-500 - max_features: $\sqrt{p}$ per classificazione, $p/3$ per regressione - min_samples_leaf: 1 per default, aumenta per ridurre overfitting - max_depth: None (cresci completamente), o limita per regolarizzazione

Gradient Boosting: - learning_rate ($\nu$): 0.01-0.1 (più piccolo = più alberi necessari) - n_estimators ($M$): 100-1000+ (dipende dal learning rate) - max_depth: 3-6 (alberi superficiali prevengono overfitting) - subsample: 0.5-1.0 (stochastic gradient boosting)

Regolarizzazione nel Boosting¶

Le implementazioni moderne includono diverse tecniche di regolarizzazione:

Shrinkage (learning rate): Apprendimento lento previene overfitting
Subsampling: Addestra ogni albero su sottoinsieme casuale (come bagging)
Sottocampionamento colonne: Usa sottoinsiemi casuali di feature (come Random Forest)
Regolarizzazione L1/L2: Penalizza i valori delle foglie
Early stopping: Ferma quando l'errore di validazione smette di migliorare

Concetti Erronei Comuni¶

"Più alberi è sempre meglio": Per bagging/Random Forest, sì. Per boosting, troppi alberi possono overfittare (a meno di non usare early stopping).
"Il boosting batte sempre Random Forest": Non necessariamente. Su alcuni dataset, Random Forest performa meglio, specialmente con iperparametri di default.
"Gli alberi non hanno bisogno di scaling delle feature": Vero per alberi singoli, ma per ensemble con regolarizzazione, lo scaling può comunque aiutare.
"L'importanza delle feature ti dice le relazioni causali": No! L'importanza misura il potere predittivo, non la causalità. Le feature correlate si spartiscono l'importanza.
"Gli outlier non influenzano gli alberi": Gli alberi singoli sono robusti, ma il boosting può essere sensibile agli outlier perché si concentra sugli esempi difficili.

Concetti Correlati¶

Teorema-Limite-Centrale — Sottostante la media negli ensemble
Likelihood-Based-Statistics — Fondamento per le funzioni di perdita nel boosting
Variance — Chiave per comprendere il tradeoff bias-varianza
Gaussian-Distribution — Perdita quadratica e assunzione normale
Sample-Mean-Estimator — Previsione ottimale nelle foglie degli alberi (errore quadratico)

Riferimenti¶

Breiman, L., Friedman, J., Olshen, R., & Stone, C. (1984). Classification and Regression Trees. Wadsworth.
Breiman, L. (1996). "Bagging predictors." Machine Learning, 24(2):123-140.
Breiman, L. (2001). "Random forests." Machine Learning, 45(1):5-32.
Freund, Y., & Schapire, R. E. (1997). "A decision-theoretic generalization of on-line learning and an application to boosting." Journal of Computer and System Sciences, 55(1):119-139.
Friedman, J. H. (2001). "Greedy function approximation: A gradient boosting machine." Annals of Statistics, 29(5):1189-1232.
Friedman, J. H. (2002). "Stochastic gradient boosting." Computational Statistics & Data Analysis, 38(4):367-378.
Chen, T., & Guestrin, C. (2016). "XGBoost: A scalable tree boosting system." KDD.
Ke, G., et al. (2017). "LightGBM: A highly efficient gradient boosting decision tree." NIPS.