9
CAPITOLO 1.
1. Machine Learning e modelli ensemble.
Nella teoria del Machine Learning, un ‘learner’ (allievo) cerca di identificare
un concetto non noto della realtà di interesse. Per compiere tale operazione esso si
basa sull’analisi di esempi concreti del concetto generale (maestro), selezionati
casualmente dalla popolazione. Tale concetto può essere descritto da una qualsiasi
funzione, anche Booleana, che lega una serie di attributi a una o più variabili risposta
(di tipo quantitativo o categorico). La difficoltà nel selezionare e implementare il
giusto algoritmo di apprendimento sta nel fatto che non si conosce a priori la forma
della distribuzione che ha generato il campione di esempi estratto. In ambito
statistico, di solito si fanno delle ipotesi sulla forma funzionale di tale distribuzione
che servono per stabilire il metodo di stima del modello; nel Machine Learning, per
definizione, si adottano invece approcci svincolati da decisioni umane.
Fra tutti quelli proposti, spicca l’approccio modellistico PAC (Probabilmente
Approssimativamente Corretto) spiegato da Schapire nel suo articolo del 1990 (16),
il quale viene definito un modello ‘distribution-free’, perché non necessita di ipotesi
sulla distribuzione di probabilità del campione estratto. L’obiettivo dell’allievo è
trovare all’interno dell’insieme di tutte le possibili funzioni o regole (definite di
seguito ipotesi) quella che meglio si avvicina al concetto non noto, ovvero la più
approssimativamente corretta. La difficoltà da superare negli algoritmi realizzati,
risiedeva nella capacità di individuare modelli di apprendimento forti, capaci cioè di
trovare ipotesi o regole di previsione con bassi tassi di errore sia per l’insieme di
esempi usato nell’addestramento dell’algoritmo, sia per ogni altro possibile
campione di esempi estratto successivamente dalla popolazione.
I processi di apprendimento computazionale generati e consolidati
nell’ambito del Machine Learning, hanno dimostrato grande successo e notevoli
potenzialità. A differenza dei sistemi computazionali che implementano programmi
precodificati, i processi di apprendimento macchina, cercano di costruire modelli
capaci di interpretare classi di concetti della realtà circostante, in maniera autonoma.
Tutto ciò avviene, mediante particolari algoritmi di apprendimento, i quali
costruiscono i modelli di apprendimento sulla base di insiemi di dati, definiti esempi
dei concetti. Poiché tali algoritmi devono essere applicati a fenomeni naturali, le loro
10
strutture cercano proprio di imitare la realtà. Difatti sono stati ideati, per fare degli
esempi, algoritmi degli alberi di classificazione, a reti neurali (che imitano la rete di
connessioni sinaptiche del cervello), algoritmi genetici e così via.
I fenomeni reali presentano una grande complessità. Similmente, tali
algoritmi hanno strutture molto complesse e generano infatti singoli modelli
estremamente complessi e quindi difficilmente interpretabili, i quali, spesso,
adattandosi così bene ai dati di input, diventano poco generalizzabili all’intera
popolazione di riferimento.
Per ovviare a questi inconvenienti e superare altri limiti computazionali, in
alternativa, sono state proposte e applicate a partire dagli anni ’90 tecniche di
apprendimento che si basano su schemi aggregativi. Questi schemi aggregativi,
chiamati solitamente schemi ensemble (di complesso o di raggruppamento), sfruttano
una combinazione dei modelli semplici i quali non hanno la preoccupazione di
raggiungere da soli un buon livello di accuratezza, e insieme riescono a trovare il
modo di generalizzare bene. Esistono molti metodi ensemble in letteratura: essi
mostrano alcune differenze ma anche delle similarità. Fra tutti i metodi ensemble
finora diffusi e presenti in letteratura sono illustrati nel dettaglio, nel presente lavoro,
il boosting, il bagging, la generalizzazione stacked, la variante dello stackingC (altri
metodi affini) e le foreste casuali. In generale esistono metodi ensemble che
generano modelli di apprendimento andando a manipolare i dati di apprendimento,
come nel caso del boosting e del bagging. Altri invece vanno a modificare gli
attributi di input, altri ancora operano modificando la variabile target oppure
effettuando una iniezione di casualità nell’algoritmo di apprendimento, come
succede nelle foreste casuali. Nel metodo stacking e sue varianti invece si generano
modelli, applicando algoritmi di apprendimento eterogenei allo stesso dataset ed
effettuando delle combinazioni di questi insiemi di modelli base per ottenere alla fine
un modello complessivo altamente performante.
11
CAPITOLO 2.
2.1 Il Machine Learning e le origini del Boosting.
Nell’articolo di Schapire (16) si dimostra che è possibile, tramite un
opportuno meccanismo di boosting (potenziamento o miglioramento) delle ipotesi,
partire da modelli di apprendimento ‘deboli’, che presentano un’accuratezza
lievemente migliore dell’indovinare a caso, e ottenere alla fine modelli aggregati di
apprendimento ‘forti’, perché dotati di tassi di errore inferiori. Nella trattazione, i
modelli di apprendimento sono definiti ‘deboli’ in quanto non rispettano il requisito
di dover essere in grado di raggiungere un livello di accuratezza elevato. Il
meccanismo di boosting in questo caso, utilizza nei vari passaggi un metodo di
filtraggio per alterare la distribuzione degli esempi in maniera tale da costringere
tramite alcune simulazioni, il modello di apprendimento debole a focalizzarsi sulle
parti più difficili della distribuzione. L’impiego del filtraggio durante i vari passaggi
del meccanismo di boosting originario serviva, alla fine, per ottenere i risultati delle
stime mediante un voto di maggioranza, espresso dal comitato dei singoli modelli di
apprendimento, per la attribuzione di etichette di classificazione all’insieme di
esempi. Pertanto tale intuizione di utilizzare più modelli anche deboli assieme, è stata
il punto di partenza per l’approccio ensemble in generale sia all’interno dei modelli
di apprendimento computazionale, che più nello specifico nell’adattamento di
modelli statistici di stima e previsione, come sarà dimostrato successivamente.
2.2 Metodi di Boosting.
I metodi di boosting sviluppati e implementati anche nei più noti algoritmi,
come l’Adaboost, proposto da Freund e Shapire (11), a differenza dell’originario
meccanismo di boosting delle ipotesi prima accennato, utilizzano un unico modello
di apprendimento di base. Questo modello viene applicato a un insieme di dati di
addestramento che viene riponderato di volta in volta nelle successive iterazioni.
In generale si è osservato che, per applicare le metodologie di boosting, è
possibile utilizzare l’algoritmo di discesa del gradiente tipico dell’ottimizzazione
numerica (6). I metodi di boosting che utilizzano al loro interno questo algoritmo
12
divengono effettivamente metodi particolarmente versatili, per l’adattamento di
modelli statistici di classificazione e soprattutto di regressione, a differenza dei primi
algoritmi di boosting che si occupavano solo della classificazione.
2.2.1 L’Algoritmo ADABOOST
L’algoritmo ADABOOST, una delle implementazioni più celebri del
boosting, è stato introdotto da Freund e Shapire nel 1995 (11). L’acronimo Adaboost
sta per adptive boosting, infatti esso genera più stime di funzione o previsioni
multiple che terminano con uno stimatore aggregato, che è loro combinazione
lineare. L’Adaboost inoltre si definisce adattivo in quanto, a differenza
dell’originaria proposta di Schapire, esso prevede l’estrazione iniziale di un solo
campione dalla popolazione, il quale viene riponderato più volte nelle diverse
iterazioni di stima, come mostrato nella Fig. 2.1 (13).
Pertanto tali metodi possono definirsi contemporaneamente adattivi e additivi
(dove additivo non si riferisce alla struttura lineare delle variabili esplicative del
singolo modello di stima, ma proprio alla combinazione lineare o media combinata
delle diverse versioni del singolo classificatore o predittore). Lo stimatore aggregato
finale G(x), della parte in alto nella fig. 2.1, consiste di una ipotesi finale H, che è un
voto di maggioranza delle M ipotesi deboli corrispondenti agli M classificatori
individuali G
m
(x) per j=1,..M.
I pesi con cui vengono moltiplicati i singoli elementi della matrice di dati di esempi
ad ognuno degli M stadi d’iterazione, sono calcolati mediante una particolare
formula matematica, sulla base delle stime dell’errore (si veda il punto 3
dell’algoritmo 2.1). Tali stime dell’errore per ogni esempio, infatti, dipendono da una
somma normalizzata di trasformazioni esponenziali della funzione indicatrice della
differenza tra valore vero e valore stimato dal modello allo stadio j-esimo. Questa è
appunto una caratteristica peculiare del boosting.
Nel seguito viene proposta la versione standard dell’algoritmo Adaboost (6),
dove si parte da un campione di n esempi, a cui corrispondono n vettori di valori
misurati, con variabile risposta Y dicotomica, che assume valori in oppure, di
solito, in
.
13
Fig. 2.1 - Lo schema ricorsivo adattivo dell’algoritmo ADABOOST.
____________________________________________________________________
Algoritmo ADABOOST:
1. Inizializza gli n pesi al passo 0 dell’algoritmo:
per i = 1,…,n. Fissa m = 0.
2. Aumenta m di 1 . Scegli una procedura base per la
classificazione binaria. Effettua una stima di modello
mediante l’insieme dei dati pesati con i pesi ,
ottenendo il classificatore
3. Calcola il tasso di errata classificazione nel campione:
14
e aggiorna i pesi:
dove la somma al denominatore è il fattore di
normalizzazione (la somma di tutti i pesi deve essere
pari a 1)
4. Itera i passi 2. e 3. fino a quando m= M
stop
e costruisci
il classificatore aggregato, tramite la votazione pesata
di maggioranza seguente:
____________________________________________________________________
Algoritmo 2.1 – ADABOOST.
L’indice err
[m]
nell’algoritmo ADABOOST è un valore atteso del tasso di
errata classificazione nel campione degli n esempi considerati, mentre
[m]
è una
trasformazione logaritmica di tale valore atteso, entrambi calcolati per ogni m-esima
iterazione dell’algoritmo. Al punto 2. dell’algoritmo 2.1 si effettua l’aggiornamento
dei pesi, che servono a ponderare in maniera ricorsiva l’indice err
[m]
, il quale serve
infine a calcolare le ponderazioni
[m]
dei singoli classificatori o stimatori che
costituiscono l’assemblea di voto finale.
Per fare un esempio del suo funzionamento, si considerino 5 iterazioni
dell’algoritmo Adaboost, che hanno fornito come valori di ponderazione: α[1]=0.2,
α[2]=0.15, α[3]=0.3, α[4]=0.22, α[5]=0.1; inoltre siano date le stime della variabile
Y, nei 5 modelli addestrati per il solo esempio i-esimo del dataset: = 0 ,
= 1, = 1, = 0, = 0. Si procede a stabilire quale dei
15
due valori, 0 o 1 corrispondenti alle due classificazioni ottiene il voto di
maggioranza. In base alla prima equazione contenuta nel punto 4 dell’Algoritmo 1.1,
per la modalità y = 0 il voto sarà: 1*0.2+0*0.15+0*0.3+1*0.22+1*0.1 = 0.52; invece
per la modalità y = 1, tale voto sarà: 0*0.2+1*0.15+1*0.3+0*0.22+0*0.1 = 0.45 . Il
voto ponderato più elevato è raggiunto dalla modalità y = 0, pertanto questa modalità
sarà attribuita all’unità i-esima come stima di boosting.
2.2.2 Il Boosting con discesa del gradiente.
Friedman, Hastie e Tibshirani (2000) negli anni successivi, tramite i loro studi
e applicazioni hanno permesso di comprendere che gli algoritmi di boosting, incluso
l’Adaboost, possono essere visti come metodi di ottimizzazione numerica (6), come
già accennato. In termini matematici tali algoritmi seguono al loro interno il processo
tipico dell’algoritmo della discesa del gradiente nello spazio di funzione allo scopo di
trovare il minimo di una funzione matematica. La scelta nell’ambito della ottimiz-
zazione numerica della discesa del gradiente è motivata dal fatto che nell’ottica di
dover minimizzare una funzione generica f(x), la stessa funzione raggiunge più
velocemente il punto di minimo, seguendo dal passo r al successivo la direzione del
gradiente negativo calcolato come derivata prima rispetto al vettore x:
(2.1)
dove a
r
è un certo valore di x, opportunamente calcolato e la funzione f deve essere
differenziabile e convessa. Volendo applicare tale principio in ambito statistico
probabilistico, in sostanza si vuole stimare un modello che sia in grado di rendere
minimo il valore atteso di una qualche funzione di perdita L(Y, f(X)):
(2.2)
Una funzione di perdita serve a dare una misura dell’errore di previsione, ovvero è
una funzione dello scostamento tra i valori assunti per la variabile risposta Y e i
16
valori assunti dalla particolare funzione scelta, che individua il modello di
previsione, applicata al vettore X di variabili di input.
L’Algoritmo 2.2 è il prototipo dell’algoritmo a discesa del gradiente che
solitamente viene implementato nella metodologia di boosting (2).
____________________________________________________________________
Algoritmo BOOSTING CON DISCESA DEL GRADIENTE:
1. Inizializza , ad esempio per gli
n esempi selezionati. Fissa m=0
2. Aumenta m di 1. Calcola il vettore del gradiente
negativo della funzione di perdita sostituendo a f,
:
per i=1,..,n
3. Adatta il vettore del gradiente negativo al
vettore di esempi mediante la procedura base di
regressione ; in altri termini addestra un modello
base usando come variabile target il vettore del
gradiente negativo.
4. Aggiorna lo stimatore boosting allo stadio m:
5. Itera i passi da 2 a 4 fino a quando m = M
stop
.
_________________________________________________________
Algoritmo 2.2 – BOOSTING CON FUNZIONE DI DISCESA DEL GRADIENTE
Al punto 4 dell’algoritmo 2.2, è un fattore per controllare la lunghezza del passo
dell’algoritmo. Questo fattore compreso tra 0 e 1 , deve essere scelto abbastanza
piccolo, di solito = 0.1, per mantenere un buon livello di accuratezza predittiva
anche se a costo di un più ampio numero di iterazioni. Il numero intero M
stop
viene
stabilito secondo gli stessi criteri visti per l’Algoritmo 2.1.
17
2.2.3 Il Boosting per la regressione.
Quando si vuole applicare il metodo di boosting a problemi di regressione,
dove la variabile target Y è a valori reali, si utilizzano la funzione di perdita
dell’errore al quadrato, oppure la funzione di perdita dell’errore assoluto che ha
proprietà di robustezza, ma non è differenziabile quando y = f; oppure si utilizza, in
ultima analisi, un abbinamento delle due funzioni di perdita, chiamato funzione di
perdita di Huber. Le forme di queste 3 funzioni sono mostrate di seguito:
1. per la f. perdita dell’errore al quadrato scalata di 1/2:
(2.3)
2. per la f. perdita dell’errore assoluto:
(2.4)
3. per la f. perdita di Huber:
(2.5)
dove viene fissato a priori, oppure viene calcolato in modo adattivo, ad
esempio come mediana dell’errore assoluto alla m-esima iterazione.
Quindi nella regressione tramite boosting si ricorre sempre all’algoritmo 2.2 con
discesa del gradiente, del paragrafo precedente, inserendo al suo interno
generalmente una delle funzioni di perdita dell’errore al quadrato prima elencate.
2.2.4 La classificazione binaria e il Boosting.
Analizzando l’Algoritmo 2.2, è evidente che la parte variabile riguarda la
scelta della funzione di perdita e della procedura base di stima, la quale naturalmente
deve essere compatibile con la natura dei dati di input. Tali scelte dipendono dal
fenomeno che si vuole conoscere. In questo paragrafo sono descritte le due principali
funzioni di perdita che si usano nel caso della costruzione di modelli di boosting per
la classificazione binaria. Nella classificazione binaria, se la variabile target assume
18
due valori etichetta 0 e 1, la funzione di perdita per l’errata classificazione dovrebbe
essere la funzione indicatrice a destra della seguente equazione:
(2.6)
Quindi la funzione di perdita (2.6) è funzione del cosiddetto margine
che in caso di errata classificazione assume valore 0 o -1. Tuttavia la funzione perdita
L
0-1
non è convessa e tantomeno differenziabile, quindi non può essere usata nel
calcolo del gradiente al punto 2 dell’Algoritmo 2.2. Si ovvia a questo inconveniente
usando delle funzioni di perdita surrogate, che per definizione rappresentano delle
approssimazioni convesse superiori della funzione di perdita 0-1. Nell’articolo di
Bulham e Hothorn (6) vengono utilizzate in particolare due funzioni di perdita per y
= 0,1:
1. la funzione di log-verosimiglianza binomiale negativa:
(2.7)
2. la funzione esponenziale: (2.8)
Differenti funzioni di perdita danno luogo a differenti algoritmi di boosting. Infatti se
viene applicata la funzione di perdita di log verosimiglianza negativa si ottiene
l’algoritmo noto come LogitBoost (10) per modelli additivi di regressione logistica
(Friedman, Hastie e Tibshirani, 2001), mentre applicando la funzione di perdita
esponenziale si ottiene l’algoritmo Adaboost già visto in precedenza. Vista la sua
importanza, il seguente paragrafo è dedicato alla variante dell’algoritmo LogitBoost.
2.2.5 Modelli di regressione logistica additiva e il
LOGITBOOST (10) .
Secondo l’approccio bayesiano, nel problema di classificazione, bisogna
calcolare la probabilità P(y= j | x), cioè la probabilità che la variabile y assuma il
19
valore di classe j, condizionato ai dati di input x rilevati dal campione. Quindi si
devono stimare le probabilità a posteriori o condizionate di classe. Purtroppo,
adoperare il processo regressivo classico al problema di classificazione comporta
degli inconvenienti. Infatti, le stime non restano confinate all’intervallo di dominio
[0,1], anche perché le variabili di input spesso sono di natura continua, o discreta e
assumono valori in un range più ampio dell’intervallo [0,1].
Per superare questo limite, si ricorre al noto modello additivo di regressione
logistica. Tale modello ha la seguente forma:
(2.9)
La trasformazione logit, a sinistra dell’equazione (2.9), è monotona e garantisce che
per ogni valore di , ossia della somma di singole funzioni di
regressione, collocata a destra dell’equazione, le stime di probabilità cadano
nell’intervallo di dominio [0, 1] . Il corrispondente algoritmo di boosting per
l’addattamento di modelli additivi di regressione logistica per la classificazione
binaria, noto come LogitBoost, fa ricorso alla ottimizzazione della log-
verosimiglianza di Bernoulli e viene di seguito presentato (la variabile risposta y
assume valori 0 e 1):
____________________________________________________________________
Algoritmo LOGIT BOOST:
1. Inizializza i pesi inoltre, e
le stime di probabilità sono fissate inizialmente a
;
2. ripeti per m= 1, …, M:
a. calcola i valori risposta per l’adattamento
iterativo:
e i pesi:
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
