ML - 29 - Ensemble Methods

Per capire meglio quanto detto vediamo un caso di classificazione binaria. Supponiamo di avere \(B\) classificatori indipendenti, ciascuno con una percentuale di misclassificazione \(e = 0.4\) piuttosto alta. Consideriamo poi un elemento \(x\) da classificare, e assumiamo senza perdità di generalità che la classe di \(x\) è \(1\). Da questo segue che il \(b\) esimo classificatore predice per \(x\) la classe \(0\) con probabilità \(e=0.4\)

Sia \(B_0 \leq B\) il numero di classificatori che misclassificano l'elemento \(x\). Assumendo che i classificatori sono indipendenti tra loro, il valore di \(B_0\) segue una distribuzione binomiale con parametri \(B, e\)

\[B_0 \sim \text{Binomial}(B, e)\]

La misclassification rate del classificatore bagged (quello complessivo) è quindi data da

\[p\Bigg(B_0 > \frac{B}{2} \Bigg) = \sum\limits_{y = B/2 + 1}^B \binom{B}{k}e^k(1 - e)^{B - k}\]

notiamo che quest'ultima quantità tende a \(0\) al crescere di \(B\).

Nel caso invece della regressione, l'expected error di un modello \(y_i(x)\) rispetto al valore corretto \(h(x)\) è dato da

\[E_x[(y_i(x) - h_(x))^2] = E_x[\epsilon_i(x)^2]\]

L'average expected error rispetto a tutti i modelli considerati separatamente è dato da

\[E_{\text{av}} = \frac{1}{m} \cdot \sum\limits_{i = 1}^m E_x[\epsilon_i(x)^2]\]

Il committe expected errore invece aggregando le varie risposte tra loro è dato da

\[E_c = E_x\Bigg[\Bigg(\frac{1}{m} \sum\limits_{i = 1}^m y_i(x) - h_(x)\Bigg)^2 \Big] = E_x\Bigg[\Bigg(\frac{1}{m} \sum\limits_{i = 1}^m \epsilon_i(x) \Bigg)^2 \Bigg]\]

Andando a sviluppare il quadrato otteniamo due tipologie di fattori:

• Fattori della forma

  \[\frac{1}{m^2} \epsilon_i(x)^2\]

  che sommati assieme ci danno esattamente \(E_{\text{av}}\) a meno di un fattore di \(1/m\).

• E anche fattori della forma

  \[\frac{1}{m^2} \epsilon_i(x) \cdot \epsilon_j(x)\]

Se assumiamo quindi che gli errori sono scorrelati tra loro, ovvero che per \(i \neq j\) si ha \(E_x[\epsilon_i(x) \epsilon_j(x)] = 0\), allora otteniamo che

\[E_c = \frac{1}{m^2} \sum E_x[\epsilon_i(x)^2] = \frac{1}{m} E_{\text{av}}\]

E quindi l'errore che ci viene offerto dal regressore bagged è minore di quello ottenuto facendo la media tra tutti gli errori se i modelli sono indipendenti tra loro.

Observation: Questo però funziona solo teoricamente, in quanto è facile vedere che questi diversi modelli sono ottenuti dallo stesso training set, e dunque non sono completamente indipendenti.

Consideriamo un caso di classificazione binaria con un dataset \((\mathbf{X}, \mathbf{t})\) di size \(n\), con \(t_i \in \{-1, 1\}\).

L'algoritmo adaboost mantiene un insieme di pesi \(w(x) = (w_1, \ldots, w_n)\) associati ai vari elementi del dataset. L'algorimo procede nel seguente modo:

• Si inizializzano i pesi come segue

  \[w_i^{(0)} = \frac{1}{n}, \,\,\, i = 1,\ldots, n\]

• Per \(j = 1,\ldots,m\)

  • Si addestra uno weak learner \(y_j(x)\) su \(\mathbf{X}\) in modo da minimizzare la misclassificazione rispetto a \(w^{(j)}(x)\).

  • Sia quindi

    \[e^{(j)} = \frac{\sum\limits_{x_i \in \xi^{(j)}} w_i^{(j)}}{\sum\limits_i w_i^{(j)}}\]

    dove \(xi^{(j)}\) è l'insieme degli elementi del dataset classificati male da \(y_j(x)\).

  • A questo puno se \(e^{(j)} > 1/2\), allora considero il reverse learner, ovvero il classificatore che ritorna la predizione opposta rispetto a quella di \(y_j(x)\) per ogni elementi. Così facendo posso considerare in ogni caso \(e^{(j)}\) come un valore di probabilità, e in particolare lo interpreto come il valore di probabilità che estraendo un elemento random dal training set questo viene classificato male, assumendo che l'elemento \(x_i\) può essere campionato con probabilità \(\frac{w_i^{(j)}}{\sum_i w_i^{(j)}}\).

  • A partire da \(e^{(j)}\) posso calcolare \(\alpha_j\) nel seguente modo (escludendo il caso limite \(e^{(j)} = 1/2\))

    \[\alpha_j = \log{\frac{1 - e^{(j)}}{e^{(j)}}} > 0\]

  • Infine, per ogni \(x_i\) aggiorno il peso corrispondente come segue

    \[w_i^{(j+1)} = \begin{cases} w_i^{(j)} e^{\alpha_j} > w_i^{(j)} &,\,\,\, x_i \in \xi^{(j)} \\ w_i^{(j)} &,\,\,\, \text{ otherwise } \\ \end{cases}\]

    notiamo quindi come i pesi degli elementi classificati male dal classificatore \(j\) vengono aumentati per formare il nuovo training set del classificatore \(j+1\).

• La predizione finale è quindi ottenuta come segue

  \[y(x) = \text{sng}\Bigg(\sum\limits_{j = 1}^m\alpha_j y_j(x) \Bigg)\]

  dato che \(y_j(x) \in \{-1, 1\}\), questo corrisponde ad una procedura di voto in cui la predizione di ciascun modello viene pesato rispetto alla confidenza del modello stesso (rappresentata dal coefficiente \(\alpha_j)\).

Notiamo che una bassa learner confidence è inversamente proporzionale alla probabilità di misclassification. Inoltre,

\[w_i^{(t)} = \frac{1}{n} \prod\limits_{j \in \mathcal{B}_i} \frac{1 - e^{(j)}}{e^{(j)}}\]

dove \(\mathcal{B}_i\) è l'insieme dei "bad" weak learners rispetto a \(x_i\), ovvero dei weak learners che misclassificano \(x_i\). Dato che \(1 - e^{(j)} > e^{(j)}\), ne segue che i "bad" learners aumentano l'importanza di un elemento mentre i "good" learners la lasciano invariata.

Così facendo con l'aumentare delle iterazioni ciascun classificatore si deve concentrare nella parte del training set che è stato classificato male dai precedenti classificatori.

Il seguente schema mostra una classificazione binaria in uno spazio bidimensionale tramite adaboost.

I weak learners utilizzati sono alberi di decisione di altezza 1, ovvero effettuano una sola partizione dello spazio delle features. Questi alberi sono anche detti stamps.

Come è possibile vedere il peso dei vari elementi, caratterizzato dalla dimensione dei simboli \(+, -\), tende ad aumentare quando il classificatore sbaglia predizione, e a diminuire quando effettua correttamente la predizione.

La predizione finale è ottenuta nel seguente modo

Passando al caso caso dei modelli additivi, per addestrare questi modelli si definisce una appropriata loss function da minimizzare rispetto al training data

\[\underset{c_j, \mathbf{w}_j}{\min} \;\; \sum\limits_{i = 1}^n L\Big(t_i, \sum\limits_{k = 1}^m c_k \overline{y}(x_i; \mathbf{w}_k)\Big)\]

Tipicamente però per molte funzioni loss \(L\) e per molti predittori \(\overline{y}\) minimizzare questa funzione risulta troppo difficile. L'idea quindi è quella di apprendere questo modello in modo iterativo.

Il modellamento additivo viene effettuato a passi in avanti, considerando i modelli dal primo all'ultimo, e aggiungendo una basis function alla volta in modo greedy. In particolare si procede come segue:

• Si imposta \(y_0(x) = 0\).

• Per ogni \(k = 1,\ldots,m\):

  • Si calcola

    \[(\hat{c}_k, \hat{\mathbf{w}}_k) = \underset{c_k, \mathbf{w}_k}{\text{argmin}} \sum\limits_{i = 1}^n L(t_i, y_{k-1}(x_i) + c_k \overline{y}(x_i;\mathbf{w}_k))\]

  • Si imposta

    \[y_k(x) = y_{k-1}(x) + \hat{c}_k \overline{y}(x;\mathbf{w}_k)\]

In particolare quindi si apprende di volta in volta senza cambiare i termini precedentemente aggiunti.

Adaboost può essere interpretato come l'apprendimento di un modello additivo con funzione di loss esponenziale

\[L(y, f(x)) = e^{-tf(x)}\]

Perché c'è la parola "gradient" nell'espressione "gradient boosting"? Come è correlata la procedura appena descritta con la gradient descent?

Consideriamo la square loss function \(L(t, y) = 1/2(t - y)^2\). Il nostro obiettivo è quello di minimizzare il rischio \(R = \sum_{i = 1}^n L(t_i, y_i)\) andando ad agire sui vari \(y_i\).

Considerando \(y_i\) come parametri del modello, calcolando le derivate otteniamo

\[\frac{\partial R}{\partial y_i} = y_i - t_i\]

I residui possono quindi essere considerati come gradienti negativi

\[t_i - y_i = - \frac{\partial R}{\partial y_i}\]

Il modello \(\overline{y}(x)\) può dunque essere derivato considerando il dataset

\[(x_i, t_i - y_i) = \Bigg(x_i, - \frac{\partial R}{\partial y_i} \Bigg), \,\,\, i=1,\ldots,n\]

L'algoritmo può quindi essere formalizzato come segue

• Inizialmente settiamo il primo predittore nel seguente modo

  \[y^{(1)}(x) = \frac{1}{n} \sum\limits_{i = 1}^n t_i\]

• Per \(k=1,\ldots,m\):

  • Calcoliamo i gradienti negativi

    \[-g_i^{(k)} = -\frac{\partial R}{\partial y_i} \Bigg|_{y_i = y^{(k)}(x_i)} = -\frac{\partial }{\partial y_i} L(t_i, y_i)\Bigg|_{y_i = y^{(k)}(x_i)} = t_i - y^{(k)}(x_i)\]

  • Successivamente si allena un weak learner \(y^{(k)}(x)\) rispetto ai gradienti negativi considerando il dataset \((x_i, -g_i^{(k)})\) per \(i=1,\ldots,n\)

  • A partire dal weak learner definamo il nuovo classificatore

    \[y^{(k+1)}(x) = y^{(k)}(x) + \overline{y}^{(k)}(x)\]

Una volta che abbiamo espresso l'algoritmo tramite il gradiente possiamo applicarlo anche ad altre loss functions. Questo ci permette quindi di applicare questa tecnica del gradient boosting anche per problemi di regressione.

Dato che la square loss non è robusta ad outliers, ovvero ad elementi che sono statisticamente molto eccentrici rispetto agli altri, potrei pensare a considerare altre funzioni di loss, tra cui

• Absolute loss

  \[\begin{split} L(t, y) &= |t - y| \\ -g &= \text{sgn}(t - y) \\ \end{split}\]

• Huber loss

  \[\begin{split} L(t, y) &= \begin{cases} \frac12 (t - y)^2 & |t - y| \leq \delta \\ \delta(|t - y|) - \frac{\delta}{2} & |t - y| > \delta \\ \end{cases} \\ \\ -g &= \begin{cases} y - t & |t - y | \leq \delta \\ \delta \cdot \text{sgn}(t - y) & |t - y| > \delta \\ \end{cases} \end{split}\]

Lo stesso algoritmo può essere applicato anche nel caso di classificazione multiclasse con \(K\) classi diverse.

In particolare...