Algoritmo di Boosting
Il boosting è un algoritmo di apprendimento automatico basata sull'ensemble learning.
Cos'è l'ensemble learning? E' una tecnica di machine learning che costruisce più alberi decisionali, non solo uno, per affrontare lo stesso problema a partire da diverse ipotesi. Poi li consulta tutti per prendere la decisione.
Si chiama boosting perché potenzia ( to boost = potenziamento ) l'albero decisionale sugli esempi che sbaglia.
Come funziona l'algoritmo del boosting
Inizialmente l'algoritmo funziona come un qualsiasi programma per costruire gli alberi decisionali.
Tuttavia, nel caso del boosting l'elaborazione si ripete per più cicli.
Il primo ciclo
L'algoritmo elabora in input un insieme di training ( insieme di addestramento ) composto da N esempi.
Ogni esempio ha lo stesso peso (p=1) ossia ha la stessa importanza.
A partire da questi costruisce il primo albero decisionale ( prima ipotesi ).
Poi verifica l'efficacia dell'albero decisionale appena costruito fornendogli in input gli esempi dello stesso insieme di training.
Per ciascun esempio l'albero decisionale elabora una risposta Yt.
Ad alcuni esempi dell'insieme di test l'algoritmo risponde correttamente ( Yt=Y ) mentre ad altri sbaglia ( Yt≠Y ).
A questo punto l'algoritmo di boosting esegue un nuovo ciclo di feed-back.
Sulla base dei risultati ottenuti nel primo ciclo, l'algoritmo di boosting modifica l'insieme di training iniziale, aumentando il peso agli esempi sbagliati.
Dopo questa modifica l'insieme di training si trasforma in un insieme di addestramento pesato perché ora gli esempi hanno pesi diversi.
Nota. Per questa ragione l'algoritmo si chiama boosting ( to boost ) ossia "potenziamento", perché nel tempo costruisce alberi decisionali in grado di rispondere correttamente agli esempi sbagliati.
Il secondo ciclo
L'algoritmo di boosting esegue un secondo ciclo di elaborazione per costruire il secondo albero decisionale ( seconda ipotesi ).
Questa volta però prende in input l'insieme di training pesato, ossia quello modificato nel ciclo precedente.
Il secondo albero decisionale (B) è diverso dal primo (A) perché ora gli esempi del training hanno pesi diversi.
A questo punto l'algoritmo sottopone il secondo albero decisionale alla verifica con l'insieme di training ed aumenta il peso agli esempi sbagliati.
E così via, il ciclo si ripete per N volte.
Alla fine l'algoritmo avrà prodotto N alberi decisionali a partire da ipotesi diverse ( es. A, B, C, ecc. ).
A cosa servono questi alberi decisionali?
Gli N alberi decisionali possono essere usati per prendere una soluzione tramite la tecnica dell'ensemble learning.
Essendo costruiti a partire da ipotesi diverse, forniscono punti di vista differenti dello stesso problema.
Nota. Una versione dell'algoritmo di ensemble learning molto utilizzato è l'AdaBoost.
