AdaBoost e le sue varianti

Figura 4.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)$$ (4.65)

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 (4.54).

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 (4.57), 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. (4.63), e con tale scelta $Z_t$ varrebbe

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

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

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

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 (4.54).

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 (4.54), è

$$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)}$$ (4.68)

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

Sia Discrete che Real AdaBoost, scegliendo un classificatore debole che rispetti l'equazione 4.68, 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]}$$ (4.69)

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 (4.68) 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.$$ (4.70)

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)$$ (4.71)

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 ]$$ (4.72)

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$$ (4.73)

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

Anche Gentle AdaBoost può essere usato con il Decision Stump. In questo caso il minimo di (4.73) 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.$$ (4.74)

LogitBoost

Per motivi storici, AdaBoost non manifesta esplicitamente un formalismo statistico. La prima cosa che si nota è che la risposta del classificatore di AdaBoost non è una probabilità, in quanto non limitata tra $[0,1]$. Oltre a questo problema, parzialmente risolto da Real AdaBoost, minimizzare la loss-function (4.53) non sembra un approccio statistico come lo potrebbe essere invece massimizzare la verosimiglianza. È possibile tuttavia dimostrare che la funzione di costo di AdaBoost massimizza un funzione molto simile alla Bernoulli log-likelihood.

Per queste ragioni è possibile estendere AdaBoost alla teoria della regressione logistica, descritta in sezione 3.7.

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)$$ (4.75)

espressione interessante se confrontata con quella di AdaBoost di equazione (4.69). Invertendo l'equazione (4.75) si ottiene la relazione logistica

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

che associa una stima della probabilità al modello additivo $F(x)$.

Il problema diventa quello di trovare una loss function adeguata a questa rappresentazione, ovvero individuare una variante di AdaBoost che massimizza esattamente la Bernoulli log-likelihood (FHT00).

Massimizzare la verosimiglianza di (4.76) equivale a minimizzare la log-loss

$$\sum_{t=1}^{T} \log \left( 1 + \exp ( -y_i F_T(x_i) ) \right)$$ (4.77)

LogitBoost per primo estende AdaBoost al problema dell'ottimizzazione logistica di una funzione $F_T(x)$ sotto la funzione costo $\phi(z)=\log \left(1 + e^{-z} \right)$, massimizzando la Bernoulli log-likelihood usando iterazioni di tipo Newton.

I pesi associati a ogni campione derivano direttamente dalla distribuzione di probabilità

$$\begin{array}{l} z_i = \frac{y_i^{*} - p(x_i)}{p(x_i) (1 - p(x_i) )} \\ w_i = \frac{ p(x_i) }{1 - p(x_i) } \end{array}$$ (4.78)

con $y^{*}=\left\{0,1\right\}$ e scegliendo l'ipotesi $f_t(x)$ come regressione ai minimi quadrati di $z_i$ a $x_i$ usando i pesi $w_i$. La stima futura di $p(x_i)$ deriva direttamente dall'equazione (4.76).

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

A prescindere dall'utilizzo i meno dei classificatori Cascade (VJ02), i pesi vengono modificati di un fattore $\beta_t = \epsilon_t/(1-\epsilon_t) = W_{-}/W_{+}$ solo nel caso di classificazione corretta, altrimenti i pesi rimangono invariati. 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.$$ (4.79)