XGBoost è un algoritmo che ha recentemente prevalso nell’apprendimento automatico e nelle competizioni Kaggle per dati strutturati o tabulari.
Ha permesso di ottenere a chi lo ha utilizzato ottimi risultati e prestazioni.
In questo post vedremo l’algoritmo XGBoost e un’introduzione su ciò che è, da dove proviene e un esempio di come funziona l’algoritmo per un problema di regressione.
Cos’è l’algoritmo eXtreme Gradient Boosting?
L’algoritmo XGBoost, acronimo di eXtreme Gradient Boosting, è stato sviluppato come progetto di ricerca presso l’Università di Washington.
Tianqi Chen e Carlos Guestrin hanno presentato il loro articolo alla Conferenza SIGKDD (Special Interest Group on Knowledge Discovery and Data, un’associazione che si dedica alla scoperta della conoscenza e al data mining) nel 2016.
Dalla sua introduzione, questo algoritmo non è stato solo accreditato per aver vinto numerose competizioni Kaggle, ma anche per essere stato la forza motrice di numerose applicazioni all’avanguardia del settore.
L’algoritmo si differenzia nei seguenti modi:
- Un’ampia gamma di applicazioni: può essere utilizzato per risolvere problemi di regressione, classificazione e previsione definiti dall’utente;
- Portabilità: funziona senza problemi sui diversi sistemi operativi Windows, Linux e OS X;
- Lingue: supporta tutti i principali linguaggi di programmazione tra cui C ++, Python, R, Java, Scala e Julia;
- Integrazione cloud: supporta cluster AWS, Azure e Yarn e funziona bene con Flink, Spark e altri ecosistemi.
Gradient Boosting Machines vs. XGBoost
XGBoost è un’implementazione specifica del metodo Gradient Boosting che utilizza approssimazioni più accurate per trovare il miglior modello ad albero.
Impiega una serie di accattivanti trucchi che lo rendono eccezionalmente efficace, in particolare con dati strutturati. I più importanti consistono nel:
1) calcolare i gradienti del secondo ordine, cioè le derivate secondarie parziali della funzione loss (simile al metodo di Newton), che fornisce maggiori informazioni sulla direzione dei gradienti e su come arrivare al minimo della funzione di perdita. Mentre il Gradient Boosting utilizza la funzione di perdita del modello base (ad es. Albero decisionale) per ridurre al minimo l’errore del modello complessivo, XGBoost utilizza la derivata del 2 ° ordine come approssimazione.
2) utilizzare la regolarizzazione (L1 e L2), che migliora la generalizzazione del modello.
XGBoost ha ulteriori vantaggi: la formazione è molto veloce e può essere parallelizzata / distribuita tra i cluster.
Per non parlare poi che è progettato per essere utilizzato con grandi e complessi dataset.
La formazione di un XGBoost è una procedura iterativa che calcola ad ogni passo la migliore suddivisione possibile per il k-esimo albero elencando tutte le possibili strutture ancora disponibili in quel punto del percorso.
Questa enumerazione esaustiva di tutte le possibili divisioni si adatta bene allo scopo di questo articolo ma per grandi set di dati è in pratica irrealizzabile, quindi si vedrà un esempio con un set di dati di poche righe e caratteristiche.
Principio di funzionamento dell’XGBoost
Vediamo un esempio di come funziona l’algoritmo XGBoost in 8 step per problemi di regressione: l’esempio utilizzato valuta il tempo trascorso a studiare e il risultato del test ottenuto (variabile target) per quattro studenti (Matteo, Francesco, Sabrina e Claudia).
Nota Bene: in quest’articolo viene utilizzato il separatore decimale americano, dove le virgole sono rappresentate dai punti e i punti da virgole quindi anziché scrivere 0,5 verrà scritto 0.5.
Step 1: Esegui una previsione
Il primo step dell’algoritmo XGBoost è quello di puntare ad eseguire una previsione. Questa di default è settata a 0.5 sia che si tratti di un problema di regressione che di classificazione.
Step 2: Calcola i residui
Come visto anche per il Gradient Boosting, anche per l’XGBoost calcoliamo i residui, differenza tra valori osservati e valori previsti.
Con una previsione iniziale di 0.5 (ŷ = 0.5), il residuo può essere calcolato con y-ŷ (voto di esame meno previsione, come da tabella sotto).
Step 3: Crea un albero XGBoost
Il terzo passo consiste nell’utilizzare un XGBoost Tree o Albero XGBoost. Questo albero particolare viene costruito in vari modi: uno tra i più diffusi cerca di splittare al meglio i vari figli, considerando due strumenti che ci vengono in aiuto: il Similarity Score e il Gain, che vedremo a breve.
Innanzitutto, i residui vengono posizionati nel nodo radice, uno di fianco all’altro.
Dopodiché viene calcolato un punteggio di similarità (Similarity Score), così calcolato:
Esso viene ricavato definendo la derivata prima e seconda della funzione obiettivo (per i problemi di regressione ad esempio si utilizza la metà dell’errore quadratico: per maggiori informazioni vedi il video di StatQuest che ne spiega i termini matematici).
Lambda è un parametro di regolarizzazione: ipotizziamo al momento e per semplicità che lambda sia pari a 0 (dopo vedremo meglio perché). Otteniamo un punteggio di similarità per il nodo radice pari a:
Costruiamo ora un albero di regressione valutando ipotesi di suddivisione, per scegliere la migliore. Valutiamo ad esempio gli studenti Francesco e Claudia, che hanno preso rispettivamente 10 e 9, per vedere che risultato di similarità otteniamo. Tra i due valori di voto la media risulta 9.5. Avremo la seguente suddivisione:
I residui vengono suddivisi tra le due foglie che si vengono a formare a seconda del voto che ha preso lo studente. Ad esempio Francesco che ha preso 10, ottiene un voto maggiore di 9.5 quindi andrà posizionato nella foglia di destra (risultato falso alla condizione Voto < 9.5). Al contrario per gli altri 3 studenti, i cui residui sono posizionati nella foglia di sinistra, perché i voti dei rispettivi studenti sono minori di 9.5.
Il punteggio di similarità viene calcolato ora sia per la foglia di destra che di sinistra.
Ora utilizziamo il gain per quantificare quanto meglio le foglie raggruppino insieme residui simili utilizzando la formula:
Gain = SS foglia sinistra + SS foglia destra – SS nodo radice
Per la prima suddivisione scelta il Gain1 è pari a 114.08 + 90.25 – 196 = 8.33.
Ora proviamo anche le altre due suddivisioni per scegliere il primo nodo. Tra le tre suddivisioni vince quella che ottiene il gain più elevato. La seconda suddivisione confronta il voto di Claudia (9) con quello di Sabrina (6). La media tra i due voti è 7.5 valore utilizzato per suddividere i dati:
La similarità del nodo radice non cambia, quella che cambia è certamente quella delle foglie. Avremo:
Quindi avremo che Gain2 è pari a 50 + 162 – 196= 16
Infine per l’ultima suddivisione consideriamo il voto di Sabrina (6) con quello di Matteo (5). La media tra i due voti è 5.5 (in questa fase vanno valutate tutte le suddivisioni possibili, dovrebbe essere più chiaro perché si è preso un dataset di piccole dimensioni):
I valori di similarità e gain risultano così:
Gain3 è pari a 20.25 + 184.083 – 196= 8.333
La suddivisione migliore è la seconda di quelle viste con un Gain più alto pari a 16.
Questo sarà il nostro nodo radice (Voto < 7.5). Usando l’albero con il gain più alto, ogni nodo verrà suddiviso in ulteriori nodi figli. I nodi smetteranno di dividersi quando rimane solo 1 residuo o in base al numero minimo definito dall’utente di dati campione in ciascun nodo, iterazioni massime o profondità dell’albero.
Siccome abbiamo già per entrambe le foglie 2 valori, suddividiamo forzatamente i due nodi figli prendendo la media dei rispettivi valori per ogni nodo (il primo nodo a sinistra avrà media 5.5 dato da 6 e da 5 come voti, mentre il secondo 9.5 dai voti 10 e 9). Se avessimo avuto più di 2 residui per ogni nodo foglia, avremmo dovuto procedere come fatto per il nodo radice per scegliere la migliore suddivisione.
Ci si può fermare a due suddivisioni, visto che non è più possibile suddividere ulteriormente l’albero. Si tenga presente che visto che l’XGBoost tratta grandi set di dati, l’albero di regressione che viene creato di default ha 6 livelli di profondità (questo parametro si può comunque settare durante la creazione dell’algoritmo).
Quello creato è l’albero XGBoost, che ci aiuterà nell’ottenere la seconda (e successive) previsione.
Step 4: Definisci una tecnica di pruning
L’XGBoost utilizza una tecnica di Pruning per migliorare ulteriormente le prestazioni dell’albero.
Semplicemente, si tratta di rimuovere i rami che fanno uso di caratteristiche che hanno poca importanza. In questo modo, riduciamo la complessità dell’albero e quindi aumentiamo il suo potere predittivo (fatto che riduce a sua volta il sovradattamento).
Come funziona la potatura?
In pratica si imposta un altro parametro dell’XGBoost, definito dalla lettera gamma γ, e si sottrae questo valore dal gain. Si parte dai nodi più bassi dell’albero e si valuta se questa differenza è positiva o negativa.
Se è positiva non si cancella il ramo in esame, altrimenti nel caso contrario si. Si procede con questa attività fino a risalire l’albero al nodo radice.
Quindi ad esempio impostando in questo caso un valore di gamma pari a 70 avremo:
Gainnodo sinistro – γ = 50 – 70 = -20
Gainnodo destro – γ = 162 – 70 = 92
In pratica dovremo cancellare dal nostro albero creato allo step precedente il nodo sinistro perché ha ottenuto un valore negativo. Otterremo:
È bene notare che in questo caso non avrebbe avuto senso scegliere un numero maggiore di 196, in quanto tutto l’albero verrebbe cancellato.
Un altro aspetto da tenere presente è che anche impostando gamma pari a 0, ci possono essere situazioni in cui il gain risulti negativo. In questo caso il nodo sarebbe cancellato per la tecnica di pruning.
Ci possono essere anche situazioni in cui il gain del nodo radice è inferiore ai gain dei livelli successivi. Ipotizziamo ad esempio brevemente di avere il nodo radice con gain pari a 130 e 162 il primo nodo figlio a destra. In questo caso scegliendo un valore di gamma pari a 140, non si elimina il nodo radice anche se il gain darebbe un risultato negativo (130 – 140 = -10) perché di fatto non viene eliminato il nodo figlio (162 – 140 = 22 > 0).
Il nodo radice si cancella all’estremo, se vengono prima cancellati tutti i nodi figli.
Step 5: Calcola il valore di output per ogni foglia
Il valore di output di ciascuna foglia può essere calcolato utilizzando la formula:
Nel normale GBM, il valore finale è semplicemente la media di tutti i valori residui all’interno di ciascun nodo foglia senza λ.
Un λ diverso da zero nella precedente equazione diminuirà il valore di uscita e il suo contributo alla previsione finale. In questo caso ho preso valore di lambda pari a 0 per comodità e perché si ottengono valori di Gain negativi per lambda maggiori di 1.
Valori di lambda maggiori di uno sono efficaci per ridurre il valore del gain, riducono l’overfitting e servono quando si vuole più facilmente “potare” nodi foglia.
Ipotizzando che l’albero sia il seguente:
Avremo:
Quindi quando lambda è 0 come in questo caso, avremo che il valore finale di ogni foglia rappresenta la media dei residui in tale foglia.
Step 6: Calcola i nuovi residui
La formula per eseguire una previsione è la seguente:
Nuova Previsione = valore previsione iniziale + eta x valore finale di foglia
Con eta che rappresenta il learning rate.
Ipotizziamo in questo caso che eta sia pari a 0.25 e che vogliamo prevedere chi prende 6 all’esame, otteniamo:
Nuova previsione = 0.5 + 0.25 * 5 = 1.75
Questo valore 1.75 rappresenta il valore del residuo che verrà utilizzato per costruire un nuovo albero XGBoost. Eta viene moltiplicato per 5 perché il voto 6 di Sabrina ricade nella prima foglia, e il valore finale di tale foglia è appunto 5.
Il valore del residuo sarà pari al valore osservato meno quello previsto: quindi 6 – 1.75 = 4.25
I nuovi residui vengono calcolati come da tabella sottostante:
Step 7: Ripeti gli step da 3 a 6 fino a quando il numero di iterazioni corrisponde al numero specificato dal parametro (ovvero il numero di stimatori)
Un secondo albero viene creato e adattato sui valori dei residui calcolati allo step precedente e il processo si ripeterà fino a quando i valori residui non diventeranno molto piccoli o quando verrà raggiunta un’iterazione massima (definita dall’utente).
La presenza di un parametro λ riduce il punteggio di somiglianza, il gain e il valore finale di foglia. I valori più piccoli impediscono l’adattamento eccessivo e una migliore precisione e stabilità (più potatura + contributo minore da ciascun albero).
Step 8: esegui la previsione finale
Come visto per il Gradient Boosting, anche l’XGBoost calcola il valore della previsione finale sommando i valori di tutte le previsioni previsti dagli alberi creati in precedenza, tenendo conto del learning rate eta e del valore di previsione iniziale 0.5.
Conclusione
XGBoost è un’implementazione open source popolare ed efficiente dell’algoritmo Gradient Boosting.
Si prefigge di minimizzare una funzione obiettivo regolarizzata (L1 e L2) che combina una funzione di perdita (basata sulla differenza tra i valori osservati e previsti) e un termine di penalità per la complessità del modello (in altre parole, la funzione dell’albero di regressione, il pruning).
L’addestramento procede in modo iterativo, aggiungendo nuovi alberi che predicono i residui, i quali vengono poi combinati con gli alberi precedenti di un fattore eta per eseguire la previsione finale.
