AdaBoost e le sue varianti

Figura 5.7: Confronto tra loss function: 0/1-loss, logistica, esponenziale e quadratica

Il problema di Boosting si può generalizzare e può essere visto come un problema dove è necessario cercare dei predittori $f_t(\mathbf{x})$ che minimizzino la funzione costo globale:

$$\sum_{i=1}^{m} \phi \left( y_i \left( f_1(\mathbf{x}_i) + \ldots + f_n(\mathbf{x}_i) \right) \right)$$ (5.109)

dove $\phi \in \mathcal{C}^1$ è una funzione convessa, non crescente con $\lim_{z \to \infty} \phi(z)=0$.

Dal punto di vista analitico, AdaBoost è un esempio di ottimizzatore a discesa del gradiente (coordinate-wise gradient descent) che minimizza la potential function $\phi(z)=e^{-z}$, ottimizzando un coefficiente $\alpha_t$ per volta (LS10), come si vede dall'equazione (5.98).

Un elenco, non esaustivo ma che permette di fare luce su alcune peculiarità di questa tecnica, delle varianti di AdaBoost è:

AdaBoost con astensione

AdaBoost può essere esteso anche a casi di classificatori con astensione, dove le uscite possibili sono $h_j(x_i) \in \{-1,0,+1\}$. Ampliando la definizione (5.101), per semplicità si indichino con $W_{-}$ gli insuccessi, $W_{0}$ le astensioni e $W_{+}$ i successi del classificatore $h_t$.

Anche in questo caso $Z_t$ assume il minimo con lo stesso valore di $\alpha_t$ del caso senza astensione, cfr. (5.107), e con tale scelta $Z_t$ varrebbe

$$Z_t = W_0 + 2 \sqrt{ W_{-} W_{+}}$$ (5.110)

Tuttavia esiste una scelta più conservativa di $\alpha_t$ proposta da Freund e Schapire

$$\alpha_t = \frac{1}{2} \log \left( \frac{W_{+} + 1/2 W_0}{W_{-} + 1/2 W_0} \right)$$ (5.111)

che permette di fissare un limite superiore a $Z_t$.

Real AdaBoost

Real AdaBoost generalizza il caso precedente ma soprattutto generalizza lo stesso modello additivo esteso (FHT00). Invece che usare ipotesi dicotomiche $h_t(x)$ e associare ad esse un peso $\alpha_t$ si cerca direttamente la feature $f_t(x)$ che minimizza l'equazione (5.98).

Real AdaBoost permette di usare classificatori deboli che forniscono la distribuzione di probabilità $p_t(x) = P[y=1 \vert x, w^{(t)} ] \in [0,1]$, probabilità che la classe $y$ sia effettivamente $+1$ data l'osservazione della caratteristica $x$.

Data una distribuzione di probabilità $p_t(x)$, la feature $f_t(x)$, che minimizza l'equazione (5.98), è

$$f_t(x) = \frac{1}{2} \log \frac{ P [y=+1 \vert x, w^{(t)} ... ...ert x, w^{(t)} ] } = \frac{1}{2} \log \frac{p_t(x)}{1-p_t(x)}$$ (5.112)

Tale risultato è pari a metà della trasformazione logistica. Siccome l'obiettivo rimane sempre quello di minimizzare la funzione costo esponenziale, l'aggiornamento dei pesi rimane ancora quello di equazione (5.104).

Sia Discrete che Real AdaBoost, scegliendo un classificatore debole che rispetti l'equazione 5.112, fanno in modo che AdaBoost converga asintoticamente a

$$\lim_{T \to \infty} F_T(x) = \frac{1}{2} \log \frac{P[y=+1\vert x]}{P[y=-1\vert x]}$$ (5.113)

dimostrando come l'algoritmo di AdaBoost sia una procedura iterativa che combina diversi classificatori deboli per approssimare un classificatore Bayesiano.

Real AdaBoost può essere usato anche con un classificatore discreto come il Decision Stump. Applicando direttamente l'equazione (5.112) ai due possibili stati di uscita del Decision Stump (risulta comunque facile ottenere il minimo di $Z_t$ per via algebrica) le risposte del classificatore devono assumere i valori

$$f(x) = \left\{ \begin{array}{ll} \frac{1}{2} \log \frac{... ...og \frac{W_{FN}}{W_{TN}} & x \leq \theta \end{array}\right.$$ (5.114)

con i valori $W_{*}$, somma dei pesi associati ai Falsi Positivi (FP), Falsi Negativi (FN), Veri Positivi (TP) e Veri Negativi (TN). Con questa scelta di valori, $Z_t$ assume come valore notevole

$$Z_t = 2 \left( \sqrt{W_{TP}W_{FP}} + \sqrt{W_{FN}W_{TN}} \right)$$ (5.115)

metrica da usare per scegliere la miglior feature $x$ e soglia $\theta$.

Gentle AdaBoost

I pesi associati agli outlier in Real AdaBoost possono essere molto elevati a causa della presenza del logaritmo in equazione. Risulta in questo caso rendere più “gentile” la regressione.

Gentle AdaBoost generalizza ulteriormente il concetto di Ensemble Learning a modello additivo (FHT00) usando una regressione con passi tipici dei metodi di Newton:

$$F_{T+1}(x) = F_T(x) + f_t(x) = F_T(x) + \E_{w^{(t)}} [ y \vert x ]$$ (5.116)

L'ipotesi $f_t(x)$, da aggiungere al modello additivo all'iterazione $t$, viene scelta fra tutte le possibili ipotesi $f_k$ come quella che ottimizza una regressione ai minimi quadrati pesata

$$f_t = \argmin_{f_k} \sum_i w_i (y_i - f_k(x_i))^2$$ (5.117)

ma per ogni iterazione viene usato l'aggiornamento dei pesi di AdaBoost (5.104), ovvero la funzione costo esponenziale.

Anche Gentle AdaBoost può essere usato con il Decision Stump. In questo caso il minimo di (5.117) dell'algoritmo di decisione assume una forma notevole in

$$f(x) = \left\{ \begin{array}{ll} \frac{W_{TP} - W_{FP} }... ...TN} }{ W_{TN} + W_{FN} } & x \leq \theta \end{array}\right.$$ (5.118)

LogitBoost

Per motivi storici, AdaBoost non nasce da una formulazione probabilistica esplicita. Una prima osservazione è che l'uscita del classificatore non rappresenta direttamente una probabilità: il valore prodotto dalla combinazione dei classificatori deboli può infatti assumere qualsiasi valore reale e non è limitato all'intervallo $[0,1]$.

Inoltre, la funzione costo minimizzata da AdaBoost non deriva direttamente da un principio di massima verosimiglianza, come avviene in molti modelli statistici. Tuttavia, è possibile dimostrare che la funzione esponenziale utilizzata da AdaBoost costituisce una buona approssimazione della perdita logistica e che il classificatore può essere interpretato come un modello additivo per la stima di probabilità.

Questa osservazione conduce naturalmente alla regressione logistica e alla definizione di algoritmi di boosting derivati da criteri statistici. In particolare, LogitBoost costruisce un modello additivo ottimizzando direttamente la verosimiglianza di un modello Bernoulliano.

La regressione logistica additiva assume la forma

$$\log \frac{P(y=+1\vert x)} {P(y=-1\vert x)} = F_T(x) = \sum_{t=1}^{T} f_t(x)$$ (5.119)

dove $F_T(x)$ rappresenta la somma dei classificatori deboli generati durante il processo di boosting.

Invertendo la relazione precedente si ottiene

$$p(x) = P(y=+1\vert x) = \frac{e^{F_T(x)}} {1+e^{F_T(x)}} = \frac{1} {1+e^{-F_T(x)}}$$ (5.120)

che associa una probabilità al modello additivo $F_T(x)$.

L'obiettivo dell'addestramento è quindi stimare la funzione $F_T(x)$ massimizzando la verosimiglianza del modello Bernoulliano. Tale problema è equivalente alla minimizzazione della log-loss

$$L = \sum_{i=1}^{N} \log\!\left( 1+\exp\!\left(-y_iF_T(x_i)\right) \right).$$ (5.121)

LogitBoost costruisce iterativamente il modello additivo mediante passi di Newton applicati alla log-verosimiglianza. A ogni iterazione vengono introdotti una risposta di lavoro (working response) e un insieme di pesi ottenuti dalla corrente stima della probabilità:

$$z_i = \frac{y_i^{*}-p(x_i)} {p(x_i)\left(1-p(x_i)\right)}$$ (5.122)

$$w_i = p(x_i)\left(1-p(x_i)\right)$$ (5.123)

dove

$$y_i^{*}\in\{0,1\}.$$ (5.124)

L'ipotesi debole $f_t(x)$ viene quindi ottenuta come regressione ai minimi quadrati pesati della variabile $z_i$ rispetto alle osservazioni $x_i$, utilizzando i pesi $w_i$. Dopo ogni iterazione, la funzione additiva viene aggiornata e una nuova stima delle probabilità viene calcolata mediante l'equazione (5.120).

A differenza di AdaBoost, che nasce come metodo di ricampionamento adattativo e possiede soltanto una successiva interpretazione statistica, LogitBoost deriva direttamente da un modello probabilistico e ottimizza esplicitamente la Bernoulli log-likelihood.

Asymmetric-AdaBoost

Asymmetric-AdaBoost presenta una variante nella regola di aggiornamento dei pesi (VJ01). Il problema di AdaBoost è che non permette un diretto controllo sul peso da assegnare agli errori di classificazione nelle diverse classi e non permette di minimizzare esplicitamente il numero di falsi positivi, ma solo l'errore di classificazione. Le varianti Asymmetric-AdaBoost modificano invece ad ogni iterazione $t$ i pesi associati ai campioni positivi e negativi di un fattore di costo $c^{(t)}_{+}$ e $c^{(t)}_{-}$ rispettivamente.

Cascade

Il peso associato a un classificatore viene assegnato come $\alpha_t = - \log \beta_t$, valore doppio rispetto al peso assegnato da AdaBoost.M1.

MAdaBoost

L'algoritmo MAdaBoost presenta un aggiornamento diverso dei pesi, per cercare di ridurre il contributo degli outlier (o esempi troppo complessi) nell'addestramento. Il peso $w^{(t)}_i$ massimo che può assumere un campione viene limitato superiormente dal valore $w^{(0)}_i$, valore che assume il peso all'inizio dell'algoritmo.

Questo comportamento può essere rappresentato da una funzione costo del tipo

$$\phi(z)=\left\{\begin{array}{ll} 1-z & z \leq 0 \\ e^{-z} & z > 0 \\ \end{array}\right.$$ (5.125)