Una delicata introduzione all’algoritmo di Gradient Boosting per l’apprendimento automatico

Ultimo aggiornamento del 15 agosto 2020

Il gradient boosting è una delle tecniche più potenti per costruire modelli predittivi.

In questo post scoprirete l’algoritmo di apprendimento automatico gradient boosting e otterrete una leggera introduzione sulla sua origine e sul suo funzionamento.

Dopo aver letto questo post, saprete:

• L’origine del boosting dalla teoria dell’apprendimento e AdaBoost.
• Come funziona il gradient boosting, compresa la funzione di perdita, gli apprendenti deboli e il modello additivo.
• Come migliorare le prestazioni rispetto all’algoritmo di base con vari schemi di regolarizzazione.

Avvia il tuo progetto con il mio nuovo libro XGBoost With Python, che include tutorial passo dopo passo e i file del codice sorgente Python per tutti gli esempi.

Iniziamo.

• Hai bisogno di aiuto con XGBoost in Python?
• L’origine del Boosting
• AdaBoost the First Boosting Algorithm
• Generalizzazione di AdaBoost come Gradient Boosting
• Come funziona il Gradient Boosting
• Funzione di perdita
• Weak Learner
• Modello additivo
• Miglioramenti al Gradient Boosting di base
• Tree Constraints
• 2. Aggiornamenti ponderati
• Stochastic Gradient Boosting
• Penalized Gradient Boosting
• Gradient Boosting Resources
• Video sul Gradient Boosting
• Gradient Boosting in Textbooks
• Gradient Boosting Papers
• Diapositive di Gradient Boosting
• Pagine web sul Gradient Boosting
• Summary
• Scopri l’algoritmo che vince le competizioni!
• Sviluppa i tuoi modelli XGBoost in pochi minuti
• Porta la potenza di XGBoost nei tuoi progetti

Hai bisogno di aiuto con XGBoost in Python?

Prendi il mio corso gratuito di 7 giorni via email e scopri xgboost (con codice di esempio).

Clicca per iscriverti ora e ottieni anche una versione gratuita del corso in PDF Ebook.

Inizia ora il tuo mini-corso gratuito!

L’origine del Boosting

L’idea del Boosting è nata dall’idea se un allievo debole può essere modificato per diventare migliore.

Michael Kearns ha articolato l’obiettivo come “Hypothesis Boosting Problem” affermando l’obiettivo da un punto di vista pratico come:

… un algoritmo efficiente per convertire ipotesi relativamente povere in ipotesi molto buone

– Thoughts on Hypothesis Boosting , 1988

Un’ipotesi debole o un discente debole è definito come uno la cui performance è almeno leggermente migliore del caso casuale.

Queste idee si basano sul lavoro di Leslie Valiant sull’apprendimento senza distribuzione o probabilmente corretto (PAC), un quadro per indagare la complessità dei problemi di apprendimento automatico.

Hypothesis boosting era l’idea di filtrare le osservazioni, lasciando quelle osservazioni che l’apprendista debole può gestire e concentrandosi sullo sviluppo di nuovi apprendimenti deboli per gestire le rimanenti osservazioni difficili.

L’idea è quella di utilizzare il metodo di apprendimento debole più volte per ottenere una successione di ipotesi, ognuna delle quali rifocalizzata sugli esempi che le precedenti hanno trovato difficili e classificati male. … Nota, tuttavia, non è affatto ovvio come questo possa essere fatto

– Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World, pagina 152, 2013

AdaBoost the First Boosting Algorithm

La prima realizzazione di boosting che ha visto un grande successo applicativo è stato l’Adaptive Boosting o AdaBoost in breve.

Il Boosting si riferisce a questo problema generale di produrre una regola di predizione molto accurata combinando regole del pollice approssimative e moderatamente imprecise.

– Una generalizzazione decisionale dell’apprendimento on-line e un’applicazione al boosting, 1995

Gli apprendisti deboli in AdaBoost sono alberi decisionali con una singola divisione, chiamati decision stumps per la loro brevità.

AdaBoost funziona pesando le osservazioni, dando più peso alle istanze difficili da classificare e meno a quelle già trattate bene. Vengono aggiunti sequenzialmente nuovi apprendisti deboli che concentrano il loro addestramento sui modelli più difficili.

Questo significa che i campioni difficili da classificare ricevono pesi sempre maggiori fino a quando l’algoritmo identifica un modello che classifica correttamente questi campioni

– Applied Predictive Modeling, 2013

Le previsioni sono fatte con il voto di maggioranza delle previsioni degli apprendisti deboli, ponderate per la loro precisione individuale. La forma di maggior successo dell’algoritmo AdaBoost era per problemi di classificazione binaria ed era chiamato AdaBoost.M1.

Puoi saperne di più sull’algoritmo AdaBoost nel post:

• Boosting e AdaBoost per l’apprendimento automatico.

Generalizzazione di AdaBoost come Gradient Boosting

AdaBoost e gli algoritmi correlati sono stati rifusi in un quadro statistico da Breiman chiamandoli algoritmi ARCing.

Arcing è un acronimo per Adaptive Reweighting and Combining. Ogni passo in un algoritmo arcing consiste in una minimizzazione ponderata seguita da una ricomputazione di e.

– Prediction Games and Arching Algorithms , 1997

Questo quadro fu ulteriormente sviluppato da Friedman e chiamato Gradient Boosting Machines. In seguito chiamato solo gradient boosting o gradient tree boosting.

Il quadro statistico ha lanciato il boosting come un problema di ottimizzazione numerica dove l’obiettivo è quello di minimizzare la perdita del modello aggiungendo apprendenti deboli usando una procedura simile alla discesa del gradiente.

Questa classe di algoritmi è stata descritta come un modello additivo a stadi. Questo perché un nuovo discente debole viene aggiunto alla volta e i discenti deboli esistenti nel modello vengono congelati e lasciati invariati.

Nota che questa strategia stage-wise è diversa dagli approcci stepwise che riaggiustano i termini precedentemente inseriti quando vengono aggiunti quelli nuovi.

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

La generalizzazione ha permesso di utilizzare funzioni di perdita arbitrariamente differenziabili, espandendo la tecnica oltre i problemi di classificazione binaria per supportare la regressione, la classificazione multiclasse e altro ancora.

Come funziona il Gradient Boosting

Il Gradient Boosting comporta tre elementi:

1. Una funzione di perdita da ottimizzare.
2. Un discente debole per fare previsioni.
3. Un modello additivo per aggiungere apprendisti deboli per minimizzare la funzione di perdita.

Funzione di perdita

La funzione di perdita usata dipende dal tipo di problema che viene risolto.

Deve essere differenziabile, ma molte funzioni di perdita standard sono supportate ed è possibile definire la propria.

Per esempio, la regressione può usare un errore quadratico e la classificazione può usare la perdita logaritmica.

Un vantaggio della struttura del gradient boosting è che un nuovo algoritmo di boosting non deve essere derivato per ogni funzione di perdita che potrebbe essere usata, invece, è una struttura abbastanza generica che qualsiasi funzione di perdita differenziabile può essere usata.

Weak Learner

Gli alberi di decisione sono usati come allievo debole nel gradient boosting.

Specificamente si usano alberi di regressione che producono valori reali per le suddivisioni e i cui output possono essere sommati, permettendo di aggiungere gli output dei modelli successivi e “correggere” i residui nelle previsioni.

Gli alberi sono costruiti in modo avido, scegliendo i migliori punti di divisione basati su punteggi di purezza come Gini o per minimizzare la perdita.

Inizialmente, come nel caso di AdaBoost, venivano usati alberi di decisione molto corti che avevano solo una singola divisione, chiamata decision stump. Alberi più grandi possono essere usati generalmente con 4-8 livelli.

E’ comune vincolare gli allievi deboli in modi specifici, come un numero massimo di strati, nodi, spaccature o nodi foglia.

Questo è per assicurare che gli allievi rimangano deboli, ma possano ancora essere costruiti in modo avido.

Modello additivo

Gli alberi vengono aggiunti uno alla volta, e gli alberi esistenti nel modello non vengono cambiati.

Una procedura di discesa a gradiente viene usata per minimizzare la perdita quando si aggiungono alberi.

Tradizionalmente, la discesa a gradiente viene usata per minimizzare un insieme di parametri, come i coefficienti in un’equazione di regressione o i pesi in una rete neurale. Dopo aver calcolato l’errore o la perdita, i pesi vengono aggiornati per minimizzare l’errore.

Invece dei parametri, abbiamo sottomodelli deboli di apprendimento o più specificamente alberi decisionali. Dopo aver calcolato la perdita, per eseguire la procedura di discesa del gradiente, dobbiamo aggiungere un albero al modello che riduce la perdita (cioè seguire il gradiente). Lo facciamo parametrizzando l’albero, poi modifichiamo i parametri dell’albero e ci muoviamo nella giusta direzione (riducendo la perdita residua.

Generalmente questo approccio è chiamato discesa a gradiente funzionale o discesa a gradiente con funzioni.

Un modo per produrre una combinazione ponderata di classificatori che ottimizza è la discesa a gradiente nello spazio delle funzioni

– Boosting Algorithms as Gradient Descent in Function Space , 1999

L’output del nuovo albero viene poi aggiunto all’output della sequenza esistente di alberi nel tentativo di correggere o migliorare l’output finale del modello.

Un numero fisso di alberi viene aggiunto o l’addestramento si ferma quando la perdita raggiunge un livello accettabile o non migliora più su un set di dati di validazione esterno.

Miglioramenti al Gradient Boosting di base

Il Gradient Boosting è un algoritmo avido e può sovradimensionare rapidamente un set di dati di allenamento.

Può beneficiare di metodi di regolarizzazione che penalizzano varie parti dell’algoritmo e generalmente migliorano le prestazioni dell’algoritmo riducendo l’overfitting.

In questa sezione vedremo 4 miglioramenti al gradient boosting di base:

1. Tree Constraints
2. Shrinkage
3. Random sampling
4. Penalized Learning

Tree Constraints

E’ importante che gli allievi deboli abbiano abilità ma rimangano deboli.

Ci sono diversi modi in cui gli alberi possono essere vincolati.

Una buona euristica generale è che più la creazione degli alberi è vincolata, più alberi saranno necessari nel modello, e il contrario, dove meno alberi sono vincolati, meno alberi saranno necessari.

Di seguito ci sono alcuni vincoli che possono essere imposti alla costruzione di alberi di decisione:

• Numero di alberi, in genere aggiungere più alberi al modello può essere molto lento per l’overfit. Il consiglio è di continuare ad aggiungere alberi fino a quando non si osservano ulteriori miglioramenti.
• Profondità degli alberi, gli alberi più profondi sono alberi più complessi e sono preferiti gli alberi più corti. Generalmente, i risultati migliori si vedono con 4-8 livelli.
• Numero di nodi o numero di foglie, come la profondità, questo può vincolare la dimensione dell’albero, ma non è vincolato ad una struttura simmetrica se vengono utilizzati altri vincoli.
• Il numero di osservazioni per scissione impone un vincolo minimo sulla quantità di dati di formazione in un nodo di formazione prima che una scissione possa essere considerata
• Il miglioramento minimo alla perdita è un vincolo sul miglioramento di qualsiasi scissione aggiunta ad un albero.

2. Aggiornamenti ponderati

Le previsioni di ogni albero sono sommate in modo sequenziale.

Il contributo di ogni albero a questa somma può essere ponderato per rallentare l’apprendimento dell’algoritmo. Questa ponderazione è chiamata restringimento o tasso di apprendimento.

Ogni aggiornamento è semplicemente scalato dal valore del “parametro del tasso di apprendimento v”

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

L’effetto è che l’apprendimento è rallentato, a sua volta richiede più alberi da aggiungere al modello, che a sua volta richiede più tempo per l’addestramento, fornendo un trade-off di configurazione tra il numero di alberi e il tasso di apprendimento.

Diminuendo il valore di v aumenta il valore migliore per M.

– Greedy Function Approximation: A Gradient Boosting Machine , 1999

È comune avere piccoli valori nell’intervallo da 0,1 a 0,3, così come valori inferiori a 0,1.

Simile al tasso di apprendimento nell’ottimizzazione stocastica, il restringimento riduce l’influenza di ogni singolo albero e lascia spazio ai futuri alberi per migliorare il modello.

– Stochastic Gradient Boosting , 1999

Stochastic Gradient Boosting

Una grande intuizione negli ensemble di bagging e nelle foreste casuali è stata quella di permettere agli alberi di essere creati avidamente da sottocampioni del dataset di allenamento.

Questo stesso vantaggio può essere usato per ridurre la correlazione tra gli alberi nella sequenza nei modelli di boosting a gradiente.

Questa variazione del boosting è chiamata boosting a gradiente stocastico.

Ad ogni iterazione un sottocampione dei dati di allenamento viene estratto a caso (senza sostituzione) dal set completo di dati di allenamento. Il sottocampione selezionato a caso viene poi usato, invece del campione completo, per adattare il discente di base.

– Stochastic Gradient Boosting , 1999

Alcune varianti dello stochastic boosting che possono essere usate:

• Sottocampiona le righe prima di creare ogni albero.
• Sottocampiona le colonne prima di creare ogni albero
• Sottocampiona le colonne prima di considerare ogni split.

Generalmente, un sottocampionamento aggressivo come la selezione di solo il 50% dei dati ha dimostrato di essere vantaggioso.

Secondo il feedback degli utenti, usare il sottocampionamento delle colonne previene l’over-fitting ancor più del tradizionale sottocampionamento delle righe

– XGBoost: A Scalable Tree Boosting System, 2016

Penalized Gradient Boosting

Sugli alberi parametrizzati possono essere imposti ulteriori vincoli oltre alla loro struttura.

Gli alberi decisionali classici come CART non sono usati come apprendisti deboli, invece viene usata una forma modificata chiamata albero di regressione che ha valori numerici nei nodi delle foglie (chiamati anche nodi terminali). I valori nelle foglie degli alberi possono essere chiamati pesi in alcuni testi.

Come tali, i valori dei pesi delle foglie degli alberi possono essere regolarizzati usando funzioni di regolarizzazione popolari, come:

• L1 regolarizzazione dei pesi.
• L2 regolarizzazione dei pesi.

Il termine di regolarizzazione aggiuntivo aiuta a lisciare i pesi finali appresi per evitare l’over-fitting. Intuitivamente, l’obiettivo regolarizzato tenderà a selezionare un modello che impiega funzioni semplici e predittive.

– XGBoost: A Scalable Tree Boosting System, 2016

Gradient Boosting Resources

Il gradient boosting è un algoritmo affascinante e sono sicuro che vuoi approfondire.

Questa sezione elenca varie risorse che puoi usare per imparare di più sull’algoritmo gradient boosting.

Video sul Gradient Boosting

• Gradient Boosting Machine Learning, Trevor Hastie, 2014
• Gradient Boosting, Alexander Ihler, 2012
• GBM, John Mount, 2015
• Learning: Boosting, MIT 6.034 Artificial Intelligence, 2010
• xgboost: An R package for Fast and Accurate Gradient Boosting, 2016
• XGBoost: A Scalable Tree Boosting System, Tianqi Chen, 2016

Gradient Boosting in Textbooks

• Section 8.2.3 Boosting, page 321, An Introduction to Statistical Learning: with Applications in R.
• Sezione 8.6 Boosting, pagina 203, Applied Predictive Modeling.
• Sezione 14.5 Stochastic Gradient Boosting, pagina 390, Applied Predictive Modeling.
• Sezione 16.4 Boosting, pagina 556, Machine Learning: A Probabilistic Perspective
• Capitolo 10 Boosting and Additive Trees, pagina 337, The Elements of Statistical Learning: Data Mining, Inference, and Prediction

Gradient Boosting Papers

• Thoughts on Hypothesis Boosting , Michael Kearns, 1988
• A decision-theoretic generalization of on-line learning and an application to boosting , 1995
• Arcing the edge , 1998
• Stochastic Gradient Boosting , 1999
• Boosting Algorithms as Gradient Descent in Function Space , 1999

Diapositive di Gradient Boosting

• Introduzione agli alberi boosted, 2014
• Un’introduzione gentile al Gradient Boosting, Cheng Li

Pagine web sul Gradient Boosting

• Boosting (machine learning)
• Gradient Boosting
• Gradient Tree Boosting in scikit-learn

Summary

In questo post avete scoperto l’algoritmo gradient boosting per la modellazione predittiva nel machine learning.

In particolare, hai imparato:

• La storia del boosting nella teoria dell’apprendimento e AdaBoost.
• Come funziona l’algoritmo gradient boosting con una funzione di perdita, apprendenti deboli e un modello additivo.
• Come migliorare le prestazioni del gradient boosting con la regolarizzazione.

Hai qualche domanda sull’algoritmo di gradient boosting o su questo post? Fai le tue domande nei commenti e farò del mio meglio per rispondere.