ADAptive BOOSTing

Uno dei classificatori Ensemble che ha attirato più interesse da parte dei ricercatori negli ultimi anni è sicuramente AdaBoost (FS95). L'idea base di AdaBoost è quella di costruire una lista di classificatori assegnando, in maniera iterativa, un peso ad ogni nuovo classificatore considerando la sua capacità di riconoscere campioni non correttamente identificati dagli altri classificatori già coinvolti nell'addestramento. Tutti questi classificatori coinvolti voteranno con il peso loro assegnato e la scelta finale avverà per maggioranza.

Le tecniche di Boosting permettono di generare un classificatore nella forma di modello additivo:

$$F_T(\mathbf{x}) = f_1(\mathbf{x}) + f_2(\mathbf{x}) + \ldots + f_T(\mathbf{x}) = \sum_{t=1}^{T} f_t(\mathbf{x})$$ (4.52)

con $f_1,\ldots,f_T$ singoli classificatori.

Esaminiamo il caso di classificazione binaria, e sia $S=(\mathbf{x}_1,y_1) \ldots (\mathbf{x}_m, y_m) \in (\mathbb{X} \times \{-1,1\} )$ l'insieme degli $m$ campioni disponibili per l'addestramento.

Una scelta abbastanza diffusa nell'ambito di fitting di modelli è quella di usare la regressione ai minimi quadrati (metrica ottima in caso di rumore gaussiano per esempio) per ottenere il modello additivo $F_T(\mathbf{x})$, minimizzando la quantità $\sum \left( y_i - F_T(\mathbf{x}_i) \right)^2$. Tuttavia, a seguito di numerosi esperimenti, si è visto che la funzione costo quadratica non è la scelta ottima nei problemi di classificazione.

L'approccio di AdaBoost suggerisce invece che l'unione di tutti questi classificatori minimizzi una funzione costo differente, migliore, ovvero la funzione di perdita esponenziale (exponential loss):

$$\min_{F} \sum_{i=1}^{m} e^{-y_i F(\mathbf{x}_i)}$$ (4.53)

Siccome la minimizzazione globale della funzione (4.53) solitamente è impossibile, si può procedere in due modi

• ottimizzando un classificatore per volta in maniera ciclica fino a giungere a una situazione stabile (generalized backfitting algorithm);
• aggiungendo un nuovo classificatore per volta al modello additivo (“greedy” forward stepwise approach)

AdaBoost affronta il problema della classificazione attraverso il secondo approccio.

Sotto queste considerazioni l'obiettivo del processo di addestramento si riduce a individuare un classificatore addizionale $f(\mathbf{x})$ che minimizzi di volta in volta la quantità

$$f_{T+1} = \argmin_{f} \sum_{i=1}^{m} e^{-y_i \left( F_T(\m... ...= \argmin_{f} \sum_{i=1}^{m} w_i e^{-y_i f(\mathbf{x}_i)}$$ (4.54)

avendo definito $w_i = e^{-y_i F_T(\mathbf{x}_i) }$ e sfruttando le proprietà dell'esponenziale.

AdaBoost è una tecnica che risponde a tutte queste esigenze.

Si supponga pertanto di avere a disposizione $\mathcal{H}=\{h_1, \ldots, h_T\}$ classificatori binari, ognuno dei quali, valutando la caratteristica $\mathbf{x}_i$, con $1 \leq i \leq m$, restituisca una opinione $y_i=\{-1,+1\}$.

Sia la funzione $F_T(\mathbf{x};\boldsymbol\alpha)$, definita come

$$F_T(\mathbf{x};\alpha_1, \ldots, \alpha_T) = \sum_{t=1}^{T} \alpha_t h_t(\mathbf{x})$$ (4.55)

una funzione il cui segno rappresenta l'ipotesi di classificazione e la sua magnitudine riflette la bontà della predizione. Il modello di equazione (4.55) è chiamato Extended Additive Model o Adaptive Basis-Function Model.

L'obiettivo è ottenere un classificatore forte $H(\mathbf{x}_i)$ come somma lineare pesata dei classificatori $h_t$, il cui segno determini l'ipotesi globale:

$$H(\mathbf{x}_i) = \sgn \left( \sum^{T}_{t=1} \alpha_t h_t(\mathbf{x}_i) \right) = \sgn F_T(\mathbf{x}_i;\boldsymbol\alpha)$$ (4.56)

Questa è una votazione per maggioranza: viene scelto come vincitrice l'ipotesi votata da più classificatori, ognuno con peso differente $\alpha_t$. Sono proprio le costanti $\alpha_t$, i pesi assegnati a ogni classificatore, il risultato fornito da questa tecnica di addestramento.

Per permettere di assegnare un voto al classificatore, è necessario che a ogni campione in ingresso $x_i$ sia assegnato un certo peso $w_i$: più il peso è alto più il campione è stato classificato in maniera non corretta fino a questo punto dell'addestramento mentre più il peso è basso più è stato classificato correttamente. Alla prima iterazione, tutti i pesi sono posti uguali, pari a $w_i^{(0)}=1/m$, in modo da avere una esatta distribuzione statistica. Varianti come l'Asymmetric AdaBoost assegnano pesi differenti alle diverse categorie coinvolte.

Sia $u_i=y_i h_t(\mathbf{x}_i)$ la funzione che esprime il successo ($+1$) o il fallimento ($-1$) del classificatore $h_t$ a valutare il campione $x_i$. Dati i pesi associati a ogni campione, è possibile per ogni classificatore calcolare $W_{-1}$, la somma dei pesi associati gli insuccessi, e $W_{+1}$, la somma dei pesi associati alle classificazioni corrette, ovvero attraverso la definizione di $u_i$, in forma compatta

$$W_b = \sum_{ u_i = b } w_i$$ (4.57)

con $b=+1$, successo, e $b=-1$, insuccesso.

Sia $\epsilon_t$ la misura dell'errore del classificatore $h_t$ calcolata come

$$\epsilon_t = \sum_{y_i \neq h_t(i) } w_i^{(t)} = \sum_{u_i=-1} w_i^{(t)} = W_{-}$$ (4.58)

somma dei pesi associati ai soli campioni classificati in maniera errata, e sia

$$r_t = W_{+}-W_{-} = \sum_{i=1}^{m} w^{(t)}_i u_i$$ (4.59)

la media ponderata, usando i pesi $w_i$, delle performance $u_i$ di classificazione.

Le iterazioni dell'algoritmo di AdaBoost sono le seguenti:

1. un Oracolo fornisce un classificatore $h_t$ (la scelta è di fatto lasciata all'utente, cercando di selezionare il classificatore che minimizza l'errore $\epsilon_t$, ma non è obbligatorio che debba essere per forza il migliore);
2. viene calcolato l'errore $\epsilon_t$ prodotto del classificatore $h_t$ sui campioni in ingresso. Quando non si riesce a trovare un classificatore per il quale $\epsilon_t > 1/2$, l'addestramento non può proseguire e deve venire pertanto terminato;
3. dato l'errore, al classificatore $h_t$ viene assegnato un peso $\alpha_t$, calcolato come descritto in seguito;
4. ad ogni campione $x_i$ la distribuzione associata $w_i^{(t+1)}$ viene aggiornata attraverso la funzione
   

   $$w_i^{(t+1)} = \frac{1}{Z_t} w_i^{(t)} e^{ - \alpha_t u_i } = \frac{1}{Z_t} w_i^{(t)} e^{ - y_i f_t (\mathbf{x}_i) }$$ (4.60)

   
   
   Il peso associato ai campioni che hanno avuto successo nella classificazione viene diminuito di una quantità proporzionale a $e^{-\alpha_t}$, mentre ai campioni che sono stati classificati in maniera errata il peso è aumentato di $e^{\alpha_t}$. $Z_t$ è un fattore di normalizzazione scelto in modo tale che $\sum w_i^{(t)}=1$ ma assume anche un significato importante come spiegato immediatamente sotto.

Il parametro di normalizzazione $Z_t$ vale

$$Z_t = \sum_{i=1}^{m} w_i^{(t)} e^{ - \alpha_t u_i } = e^{ - \alpha_t} W_{+} + e^{ \alpha_t} W_{-}$$ (4.61)

e, risultato importante di AdaBoost, si può dimostrare che l'errore di classificazione viene limitato superiormente da

$$\frac{1}{m} \{ i : H(x_i) \neq y_i \} \leq \prod_{t=1}^{T} Z_t$$ (4.62)

Per questo motivo $Z_t$ è esattamente la quantità da minimizzare per ottenere il classificatore ottimo. Conseguenza diretta di questo risultato, si può vedere AdaBoost come uno schema che minimizza $\prod_t Z_t$.

La scelta ottima di $\alpha_t$ (e di riflesso quella di $h_t$) è quella dove la funzione (4.61) assume il minimo, ovvero

$$\alpha_t = \frac{1}{2} \log \left( \frac{1-\epsilon_t}{\ep... ...W_{-} } = \frac{1}{2} \log \left( \frac{1+r_t}{1-r_t} \right)$$ (4.63)

Con questa particolare scelta di $\alpha_t$, $Z_t$ assume il minimo e vale

$$Z_t = 2 \sqrt{ \epsilon_t (1-\epsilon_t) } = 2 \sqrt{ W_{-} W_{+} }$$ (4.64)

Dall'equazione (4.64) si evince che $Z_t$ viene minimizzato scegliendo il classificatore $h_t$ che ha il minore valore di $\epsilon_t$ ovvero massimo $W_{+}$.

Scegliendo come peso quello di equazione (4.63) che minimizza $Z_t$, dopo ogni iterazione di AdaBoost i pesi associati a campioni identificati correttamente vengono diminuiti di un fattore $\exp(-\alpha_t)$ ovvero $\sqrt{ W_{-} / W_{+} }$, mentre i pesi associati a campioni valutati erroneamente dall'ipotesi $h_t$ vengono aumentati di un fattore $\exp(\alpha_t)$ ovvero $\sqrt{ W_{+} / W_{-} }$.

Questo algoritmo è quello che viene definito in letteratura AdaBoost.M1 o Discrete AdaBoost (FHT00). Le ipotesi $h_t(\mathbf{x})$ usate da AdaBoost sono feature che possono assumere i soli valori $\{+1,-1\}$.

Il funzionamento intuitivo di AdaBoost è molto semplice: AdaBoost per ogni nuovo classificatore aggiunto alla serie si concentra sui pattern in ingresso che finora sono stati classificati peggio.

AdaBoost ha diverse interpretazioni: come classificatore che massimizza il margine, regressione logistica a un modello additivo, come minimizzatore a discesa del gradiente a passi discreti ma anche come regressione con tecnica di Newton.

AdaBoost, come SVM, ottiene come risultato quello di massimizzare il margine di separazione tra le classi, anche se con metriche differenti. In questo modo, entrambi, riescono ad essere meno sensibile a problemi come l'overfitting.