La maggior parte dei problemi di machine learning si focalizzano sull’eseguire una predizione con un singolo modello.
In altri casi è possibile avvalersi dei risultati di più predizioni di modelli diversi per ottenere il risultato finale.
Questo è ciò che fanno gli algoritmi Boosting. In particolare in questa sede ci concentriamo su un tipo di algoritmo che rientra in questa tipologia: l’algoritmo Adaptive Boosting (conosciuto anche come AdaBoost).
Vediamo prima un po’ meglio cosa fanno gli algoritmi Boosting.
Algoritmi Boosting
Il termine “Boosting” si riferisce a una famiglia di algoritmi che converte un modello a bassa accuratezza (detto weak learner o classificatore debole) in modelli ad alta accuratezza (in gergo “strong learner” o classificatore forte).
Il Boosting è un metodo di ensemble per migliorare le previsioni del modello di un determinato algoritmo di apprendimento. L’idea che ne è alla base è quella di formare sequenzialmente weak learner, ognuno cercando di correggere il suo predecessore.
Questo viene fatto creando prima un modello dai dati di addestramento, in seguito viene creato un secondo modello che tenta di correggere gli errori dal primo modello.
I modelli vengono aggiunti fino a quando il set di addestramento non viene previsto perfettamente o non viene aggiunto un numero massimo di modelli.
Cos’è l’algoritmo AdaBoost?
AdaBoost, acronimo di “Adaptive Boosting” e proposto da Freund e Schapire nel 1996, è stato il primo algoritmo di boosting di grande successo sviluppato per la classificazione binaria.
Rappresenta una tecnica di boosting popolare che ti aiuta a combinare più “classificatori deboli” in un unico “classificatore forte”.
Per intenderci, un classificatore debole è semplicemente un classificatore che funziona male, ma funziona meglio di un’ipotesi casuale.
Un semplice esempio di classificatore debole potrebbe essere la classificazione di una persona come classe “maschio” o “femmina” in base alla sua altezza. Si potrebbe dire che chiunque sia più alto di 185 cm sia un maschio e chiunque sotto quella altezza sia una femmina. In questo modo classificherai molte persone in modo errato, ma la tua precisione sarà comunque superiore al 50%.
Mettendo insieme tanti modelli di questo tipo, l’AdaBoost riesce a generare un modello che complessivamente è migliore dei singoli classificatori deboli presi singolarmente.
Come classificatore debole da addestrare l’Adaboost si avvale di tanti alberi decisionali ad un livello di profondità, definiti decision stumps, tanti quanti sono le caratteristiche del modello.
Ad ogni iterazione, un nuovo classificatore debole viene introdotto in sequenza e mira a compensare le “carenze” dei modelli precedenti per creare un forte classificatore. L’obiettivo generale di questo esercizio è quello di adattare consecutivamente nuovi modelli per fornire stime più accurate della nostra variabile di risposta.
In realtà l’AdaBoost non accetta solo alberi decisionali come weak learners: qualsiasi algoritmo di apprendimento automatico può essere utilizzato come classificatore di base se accetta pesi sul set di allenamento.
Principio di funzionamento dell’AdaBoost
Vediamo come funziona l’algoritmo in 7 step.
Vorrei far notare che online esistono diverse rappresentazioni di come funziona quest’algoritmo. Pertanto, ho cercato in questa sede di utilizzare i termini matematici meno complessi per far capire nel modo più semplice come l’algoritmo è progettato. Se si è interessati ad approfondire, potete vedere i link di approfondimento che lascio a fine articolo.
Bene, fatta questa premessa, possiamo iniziare.
Step 1: Calcola il peso di ogni data point
Il concetto alla base di Adaboost è stabilire i pesi dei classificatori e addestrare il campione di dati in ciascuna iterazione in modo tale da garantire previsioni accurate di osservazioni insolite. Per cominciare, viene addestrato un classificatore debole e a tutti i campioni di dati di esempio viene assegnato lo stesso peso.
Quindi, dato un set di dati con n data point, dove
Xi ∈ ℝd, yi ∈ {-1,1}
-1 indica la classe negativa mentre 1 rappresenta quella positiva e Xi rappresentano numeri reali.
Inizializza il peso per ciascun punto dati come:
Ad esempio, ipotizziamo di avere un dataset con 7 campioni come il seguente:
Il peso del campione iniziale sarà pari a 1/7 per ogni riga del dataset. In questo esempio, uomo rappresenta la classe positiva (+1), donna la classe negativa (-1).
Step 2: Scegli il weak learner
Ipotizziamo che ogni classificatore debole sia un albero decisionale con livello di profondità pari a uno (decision stump).
Per ogni caratteristica a disposizione avremo un decision stump, l’adaboosting sceglie tra tutti quello con minor entropia (o quello con il minor coefficiente di Gini).
L’entropia è una formula che puoi calcolare avvalendoti delle frequenze tra due o più attributi. In questo caso, ad esempio per la caratteristica Altezza si ha che per istanze maggiori o uguali di 180 cm ho due risultati “Uomo” e uno “Donna” (la somma di queste due istanze è pari a 3), contro i 3 uomo e una donna se tale altezza è < di 180 (la somma di queste due invece risulta pari a 4):
L’entropia totale dell’altezza è pari a:
E(genere, altezza) = P(altezza >=180) * E (2,1) + P(altezza < 180) * E(3,1)
Con E(2,1) = – 2/3 * log2 (2/3) – 1/3 * log2(1/3) = 0,9183
Ed E(3,1) = – ¾ * log2 (3/4) – ¼ *log2(1/4) = 0,8112
Mentre la probabilità che l’altezza sia >= 180 è pari a 3/7 perché solo 3 istanze superano i 180 cm, al contrario la probabilità di avere istanze minori di 180 è pari a 4/7.
Quindi E(genere, altezza) = 3/7 * 0,9183 + 4/7 * 0,8112 = 0,8571
Analogamente per la caratteristica peso si ha che per istanze maggiori o uguali di 75 kg ho quattro risultati “Uomo” e nessuno “Donna” (la somma di queste due istanze è pari a 4), contro l’uno uomo e due donna se tale peso è < di 75 (la somma di queste due invece risulta pari a 3):
L’entropia totale del peso invece è pari a:
E(genere, peso) = P(peso >=75) * E (4,0) + P(peso< 75) * E(1,2)
Con E(4,0) = – 4/4 * log2 (4/4) – 0/4 * log2(0/4) = 0
Ed E(1,2) = – 1/3 * log2 (1/3) – 2/3 *log2(2/3) = 0,9183
Mentre la probabilità che il peso sia >= 75 è pari a 4/7 perché solo 4 istanze superano i 75kg, al contrario la probabilità di avere istanze minori di 75 kg è pari a 3/7.
Quindi E(genere, peso) = 4/7 * 0 + 3/7 * 0,9183 = 0,3936
Mentre per la caratteristica Età abbiamo che per istanze maggiori o uguali di 30 anni ho quattro risultati “Uomo” e uno “Donna” (la somma di queste due istanze è pari a 5), contro l’uno uomo e uno donna se tale età è < di 30 (la somma di queste due invece risulta pari a 2):
L’entropia totale dell’età invece è pari a:
E(genere, età) = P(età >=30) * E (4,1) + P(età< 30) * E(1,1)
Con E(4,1) = – 4/5 * log2 (4/5) – 1/5 * log2(1/5) = 0,7219
Ed E(1,1) = – 1/2 * log2 (1/2) – 1/2 *log2(1/2) = 1
Mentre la probabilità che l’età sia >= 30 è pari a 5/7 perché 5 istanze superano i 30 anni, al contrario la probabilità di avere istanze minori di 30 anni è pari a 2/7.
Quindi E(genere, età) = 5/7 * 0,7219 + 2/7 * 1 = 0,8014
Come primo weak learner scegliamo il peso, perché ha minore entropia tra le tre caratteristiche (0,8571 vs 0,3936 vs 0,8014).
In generale, il weak learner scelto è quello che ottiene un tasso di errore di previsioni minore tra tutti i decision stump.
Step 3: Calcola l’Amount of Say del weak learner precedentemente scelto
Successivamente è importante calcolare la performance del decision stump (PS, chiamata anche Amount of Say). Per capire come trovare questo valore dobbiamo trovare prima il Total Error (TE), dato dal numero di previsioni errate rispetto al totale dei data points utilizzati.
A seconda del valore di quest’ultimo, l’amount of say può essere:
- Positivo: per valori di TE > di 0,5;
- Nullo: per valore di TE pari a 0,5;
- Negativo: per valori di TE < di 0,5;
Ipotizziamo che il modello abbia classificato erroneamente solo la terza istanza:
Avremo che l’errore totale è pari a 1/7.
Una volta calcolato l’errore totale possiamo calcolare la performance del decision stump, data dalla seguente espressione:
PS = ½ ln ((1 – TE) / TE)
Con ln logaritmo naturale di base e (numero di Nepero e pari a 2,7182…).
Nell’esempio, la performance dello stump sarà pari a:
PS = ½ ln ((1 – 1/7) / 1/7) = ½ ln (6) = 0,896
Step 4: Calcola il nuovo peso delle istanze
Per l’algoritmo AdaBoost, le classificazioni errate avranno un peso più elevato delle classificazioni corrette. La formula per calcolare il peso per le classificazioni errate sarà la seguente:
Con WE new il nuovo peso per la classificazione errata, w old il vecchio valore del peso per l’istanza i-esima e TE l’errore totale del modello.
Quindi per l’esempio proposto il nuovo peso è pari a 1/7 /(2 * 1/7) = 0,5. Per le classificazioni corrette la formula del calcolo del nuovo peso (WC new) si modifica leggermente e risulta pari a:
Per l’esempio avremo che il nuovo peso è pari a:
Di conseguenza, avremo che i pesi saranno pari a 0,0833 per le istanze previste correttamente e 0,50 per le istanze previste errate.
I nuovi pesi così calcolati rappresentano i pesi normalizzati per ogni istanza che si andranno a sostituire ai precedenti (1/n).
Step 5: Crea un nuovo dataset considerando i nuovi pesi
Dividiamo il dataset in una distribuzione di valori compresa tra 0 e 1 utilizzando i pesi appena creati. Ciò significa che la prima riga ricade dentro il range 0 – 0,083, la seconda 0,083 e 0,167 (0,083 + 0,083) e così via fino a raggiungere per l’ultima istanza valore 1 (vedi l’ultima colonna nell’immagine successiva).
Ciò ci serve perché occorre creare un nuovo dataset con stessa grandezza del precedente. Selezioniamo un numero random compreso tra 0 e 1 tante volte quante sono le righe che abbiamo nel dataset (nel nostro esempio 7). Le righe di questo nuovo dataset sono identiche a quelle del dataset precedente, ma vengono decise dal valore che viene estratto casualmente.
Infatti, ad ogni risultato casuale ottenuto, inseriamo la riga rientrante nel range individuato nel nuovo dataset.
Ad esempio, se dalla prima estrazione esce 0,25, selezioniamo la terza riga come prima riga del nuovo dataset (perchè 0,25 rientra nell’intervallo tra 0,167 e 0,667). Se alla seconda iterazione esce 0,42 idem, reinseriamo tale riga nel nuovo dataset (0,42 rientra sempre nell’intervallo 0,167 – 0,667). E così via finché non si crea il nuovo dataset (di 7 righe nell’esempio).
Con le seguenti estrazioni casuali:
Otterremo il nuovo dataset:
Come possiamo notare, la prima, la seconda, la quarta e la sesta istanza sono quelle previste erroneamente dalla prima iterazione. Questo nuovo dataset verrà testato e verificato da un nuovo decision stump.
Step 6: Ripeti gli step da 2 a 5
Questo processo viene ripetuto dal punto 2 fino al punto 5 n volte, fino a quando i dati di addestramento non ottengono nessun miglioramento o fino al raggiungimento del numero massimo di stimatori specificato (n).
Due considerazioni: prima di tutto, il peso dei nuovi campioni viene aggiornato ad ogni iterazione e l’errore totale (TE) cambierà a seconda delle nuove previsioni fatte dal nuovo decision stump.
In secondo luogo, il peso dei nuovi campioni per l’iterazione i-esima influenzerà il valore del peso dell’iterazione successiva (i-esima +1), perchè l’algoritmo tiene conto dei pesi ottenuti dalle iterazioni precedenti. Col valore di questi ultimi pesi, si riforma poi un nuovo dataset, e si riparte con la creazione di un nuovo decision stump, finchè una condizione di stop non viene raggiunta.
Step 7: Costruisci il classificatore finale
Una volta completate tutte le iterazioni, tutti i weak learner vengono combinati con i loro pesi per formare un forte classificatore.
Questo classificatore esegue la previsione calcolando la somma delle performance degli stump calcolati agli step precedenti, suddivise per classe, che ogni weak learner prevede. Viene scelto come risultato della previsione la classe che ha la somma di PS più alta tra le due.
Ad esempio, 5 classificatori deboli possono prevedere i valori Uomo, Uomo, Donna, Uomo, Donna. Da un voto di maggioranza, sembra che il modello preveda un valore di Uomo o la prima classe (3 volte previsto uomo, contro donna previsto due volte).
Però, questi stessi 5 classificatori deboli possono avere rispettivamente valori PS (Performance degli stump) di 0,24, 0,51, 0,89, 0,24 e 0,89.
- Sommando i valori della classe positiva abbiamo: 0,24 + 0,51 +0,24 = 0,99
- Sommando i valori della classe negativa abbiamo: 0,89 + 0,89 = 1,78
La classe predetta è Donna, perché la somma della classe negativa 1,78 è maggiore di quella positiva 0,99.
Conclusione
In questo articolo abbiamo visto cos’è l’algoritmo AdaBoost e un esempio di come esso funziona.
Questo algoritmo rientra nei metodi di ensemble learning e può essere utilizzato per risolvere una varietà di problemi del mondo reale, come la previsione dell’abbandono dei clienti e la classificazione dei tipi di prodotti cui clienti si interessano.
In generale è un algoritmo veloce, semplice e facile da programmare, utilizzato per risolvere i problemi di classificazione, data la sua relativa facilità di implementazione in linguaggi come R e Python.
Nel prossimo articolo vedremo un esempio di applicazione dell’algoritmo in linguaggio Python.
Per maggiori approfondimenti sull’AdaBoost puoi vedere:
