Bagging (Bootstrap Aggregating)
- Introdotto da
- Breiman, L.
- Anno
- 1996
- Tipo
- Ensemble meta-algorithm (variance reduction via bootstrap aggregation)
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
Il Bagging, abbreviazione di Bootstrap Aggregating, è un meta-algoritmo di ensemble introdotto da Leo Breiman nel 1996 che addestra più copie di un "learner" di base su campioni bootstrap estratti indipendentemente dai dati di addestramento e combina le loro predizioni — tramite media per la regressione o voto a maggioranza per la classificazione — per produrre un predittore finale con una varianza sostanzialmente inferiore rispetto a qualsiasi singolo "learner" di base.
L’intuizione alla base del metodo
Immaginate di chiedere un'opinione a un esperto: la sua risposta dipende fortemente dalle sue esperienze particolari. Ora immaginate di chiedere a cento esperti, ognuno con un background leggermente diverso, e di fare una media delle loro risposte. Le peculiarità individuali si annullano e il consenso del gruppo è molto più affidabile. Il Bagging fa esattamente questo per i modelli di machine learning: genera molti set di addestramento leggermente diversi ricampionando i dati originali con reimmissione, addestra un modello per ogni set e unisce tutte le predizioni. Ogni modello vede una fetta diversa della realtà, quindi i loro errori individuali tendono a non allinearsi, e l'aggregato è molto più stabile di qualsiasi singolo modello.
Storia
Leo Breiman pubblicò "Bagging Predictors" in Machine Learning nel 1996, motivato dall'osservazione che i "learner" instabili — quelli il cui output cambia sostanzialmente sotto piccole perturbazioni dei dati — potevano essere stabilizzati mediando su repliche bootstrap del set di addestramento. La giustificazione teorica si basa sulla decomposizione bias-varianza: la media riduce la varianza lasciando il bias invariato. Breiman dimostrò miglioramenti consistenti nell'accuratezza rispetto ai singoli alberi decisionali su una serie di benchmark di classificazione e regressione. Il Bagging divenne rapidamente una tecnica di ensemble fondamentale e ispirò direttamente Random Forest (Breiman, 2001), che aggiunge il sottocampionamento casuale delle caratteristiche ad ogni split per decorrelare ulteriormente gli alberi e ottenere una riduzione della varianza ancora maggiore. Oggi, il Bagging funge da spina dorsale concettuale per un'ampia famiglia di metodi di ensemble ed è un argomento standard nei curricula di machine learning a livello universitario.
Quando usarlo
Il Bagging è appropriato ogni volta che l'algoritmo di apprendimento di base ha un'elevata varianza — cioè, è sensibile a piccole perturbazioni nei dati di addestramento — e la riduzione di tale varianza è la principale fonte di errore. Gli alberi decisionali completamente sviluppati e non potati sono l'esempio canonico. Il Bagging è adatto sia per la classificazione che per la regressione su dati tabulari, non richiede assunzioni sulla distribuzione dei dati e gestisce tipi di caratteristiche miste. È più vantaggioso quando il dataset è sufficientemente grande da supportare B campioni bootstrap indipendenti di qualità (almeno circa 30 osservazioni è un limite inferiore pratico, sebbene centinaia siano preferibili). Il Bagging non è vantaggioso quando il "learner" di base è già stabile (come la regressione lineare su problemi ben specificati) o quando la fonte di errore dominante è il bias piuttosto che la varianza — in tali casi i metodi di "boosting" sono più appropriati.
Limiti e considerazioni
- Non riduce il bias: se il "learner" di base sottostima, il Bagging non può correggerlo.
- Le predizioni dell'ensemble sono più difficili da interpretare rispetto a un singolo modello; non esiste un analogo della struttura visiva di un singolo albero decisionale.
- La memoria e l'archiviazione crescono linearmente con B: mantenere centinaia di modelli di grandi dimensioni in memoria può essere proibitivo.
- I guadagni diminuiscono rapidamente all'aumentare di B; le prestazioni di solito si stabilizzano ben prima di B = 500.
- Su "learner" di base stabili (ad esempio, regressione lineare con specifica corretta) il Bagging produce un miglioramento trascurabile.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Riduce direttamente la varianza dello stimatore senza aumentare il bias, producendo predizioni più stabili rispetto a qualsiasi singolo modello di base.
- Trivialmente parallelizzabile: ogni iterazione bootstrap è indipendente, rendendo i grandi ensemble computazionalmente trattabili.
- La stima dell'errore OOB integrata fornisce una stima di generalizzazione attendibile senza costi aggiuntivi di dati.
- Meta-algoritmo indipendente dal modello: compatibile con qualsiasi "learner" di base sufficientemente instabile (alberi, reti neurali, vicini più prossimi).
- Robusto agli outlier nel set di addestramento: qualsiasi singola osservazione insolita è assente dalla maggior parte dei campioni bootstrap.
Applicazioni
- Costruire modelli di classificazione e regressione stabili su dati tabulari rumorosi dove un singolo albero decisionale sarebbe soggetto a overfitting.
- Generare intervalli di predizione ispezionando la diffusione delle predizioni tra i B "learner" di base.
- Stima dell'importanza delle caratteristiche tramite la diminuzione dell'accuratezza OOB quando ogni caratteristica viene permutata attraverso l'ensemble.
- Riferimento di base dell'ensemble: un benchmark rapido per quantificare quanto un metodo più sofisticato (boosting, stacking) migliori rispetto alla semplice aggregazione.
Come funziona
Come funziona
Vengono estratti B campioni bootstrap indipendenti dal set di addestramento originale di dimensione n. Ogni campione è generato estraendo n osservazioni con reimmissione dai dati originali, quindi in media ogni campione contiene circa il 63,2% delle istanze di addestramento uniche; il restante ~36,8% viene lasciato fuori e forma il set out-of-bag (OOB) per quella iterazione.
Formula
\mathcal{D}_b = \{(\mathbf{x}_i^*, y_i^*)\}_{i=1}^{n}, \quad (\mathbf{x}_i^*, y_i^*) \overset{\text{i.i.d.}}{\sim} \hat{F}_n, \quad b = 1, \dots, BUn algoritmo di apprendimento di base — molto spesso un albero decisionale cresciuto a piena profondità, ma qualsiasi "learner" sufficientemente instabile è idoneo — viene adattato indipendentemente su ogni campione bootstrap, producendo B modelli distinti. Il requisito chiave è l'instabilità: se piccole perturbazioni dei dati causano grandi cambiamenti nel modello, il Bagging produce la maggiore riduzione della varianza.
Formula
\hat{f}_b = \mathcal{A}(\mathcal{D}_b)Per i compiti di regressione, gli output dei B modelli vengono mediati. Questo passaggio di media è il meccanismo primario per la riduzione della varianza: sotto ipotesi di indipendenza, la varianza della media di B modelli identicamente distribuiti è 1/B della varianza di un singolo modello, e anche sotto correlazione positiva la riduzione è sostanziale.
Formula
\hat{f}_{\text{bag}}(\mathbf{x}) = \frac{1}{B} \sum_{b=1}^{B} \hat{f}_b(\mathbf{x})Per i compiti di classificazione, ogni "learner" di base esprime un voto per un'etichetta di classe, e la classe con il maggior numero di voti viene restituita come predizione finale. I pareggi vengono risolti arbitrariamente. Il voto a pluralità è asintoticamente equivalente alla media delle stime di probabilità di classe prodotte da ogni "learner" di base.
Formula
\hat{y}(\mathbf{x}) = \underset{k}{\operatorname{arg\,max}} \sum_{b=1}^{B} \mathbf{1}\!\left[\hat{f}_b(\mathbf{x}) = k\right]Poiché ogni "learner" di base è addestrato su circa il 63,2% dei dati, le osservazioni rimanenti possono servire come un set di test "held-out" per quel "learner". La media di queste predizioni OOB su tutti i "learner" che non hanno visto ogni osservazione fornisce una stima quasi imparziale dell'errore di generalizzazione senza richiedere una "validation fold" separata o la convalida incrociata.
Formula
\widehat{\text{Err}}_{\text{OOB}} = \frac{1}{n} \sum_{i=1}^{n} L\!\left(y_i,\; \frac{1}{|\mathcal{B}_i^c|} \sum_{b \in \mathcal{B}_i^c} \hat{f}_b(\mathbf{x}_i)\right)Errori comuni
- Applicare il Bagging a un "learner" di base a bassa varianza (come la regressione Ridge) e aspettarsi grandi guadagni di accuratezza.
- Impostare B troppo piccolo (ad esempio, B < 10) in modo che l'aggregato sia ancora rumoroso e le stime OOB siano inaffidabili.
- Ignorare lo squilibrio di classe: il Bagging preserva la distribuzione di classe dei dati originali in ogni campione bootstrap, quindi un grave squilibrio viene replicato in tutti i "learner".
- Confondere il Bagging con il Boosting: il Bagging addestra i modelli in parallelo su campioni indipendenti per ridurre la varianza, mentre il Boosting addestra i modelli sequenzialmente per ridurre il bias — affrontano diverse fonti di errore.
- Trattare l'errore OOB come un sostituto di una corretta valutazione "held-out" quando il dataset è molto piccolo, poiché le stime OOB possono essere ottimistiche in quel regime.
Domande frequenti
Quanti campioni bootstrap B dovrei usare?
Breiman (1996) ha riscontrato che le prestazioni si stabilizzano relativamente rapidamente; B = 50 a 100 è spesso sufficiente per gli alberi decisionali. Aumentare B oltre qualche centinaio produce rendimenti decrescenti. Monitorare l'errore OOB all'aumentare di B e fermarsi quando si stabilizza.
Qual è la differenza tra Bagging e Random Forest?
Random Forest estende il Bagging aggiungendo il sottocampionamento casuale delle caratteristiche ad ogni split di ogni albero. Questa ulteriore randomizzazione decorrela ulteriormente i "learner" di base, riducendo la varianza oltre quanto il solo Bagging riesce a ottenere. Il Bagging con alberi completamente sviluppati è quindi un caso speciale di Random Forest in cui tutte le caratteristiche sono considerate ad ogni split.
Il Bagging può essere applicato a "learner" diversi dagli alberi decisionali?
Sì. Qualsiasi "learner" che sia instabile — le cui predizioni cambiano sostanzialmente quando i dati di addestramento cambiano leggermente — può beneficiare del Bagging. Reti neurali, k-nearest neighbours e alberi di regressione non potati sono tutti idonei. I "learner" stabili come la regressione lineare con un modello ben specificato beneficiano poco perché c'è poca varianza da ridurre.
L'errore OOB è un sostituto affidabile della convalida incrociata?
Per dataset di dimensioni moderate o grandi, l'errore OOB è una stima quasi imparziale dell'errore di generalizzazione ed è computazionalmente gratuito poiché non sono richiesti adattamenti di modelli aggiuntivi. Su dataset molto piccoli (n inferiore a circa 50) le stime OOB possono essere ottimistiche e la convalida incrociata è preferibile.
Metodi correlati
Fonti
Breiman, L. (1996). Bagging Predictors. Machine Learning, 24(2), 123–140.
Apri il riferimento DOICopiato.Hastie, T., Tibshirani, R. & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed., Ch. 8.7). Springer.
ISBN: 978-0-387-84857-0Copiato.James, G., Witten, D., Hastie, T. & Tibshirani, R. (2013). An Introduction to Statistical Learning (Ch. 8.2). Springer.
ISBN: 978-1-4614-7138-7Copiato.