Les méthodes de boosting

add.png

\bullet Présentation:

Le boosting est une famille d’outils d’analyse discriminante très puissants. L’idée est d’améliorer la règle de discrimination d’un classifieur sur plusieurs sous-parties de l’hyperplan formé par (Y, X ^1, \cdots, X ^P) et d’établir la classification finale au travers d’un vote global pondéré. Chaque partie du plan se voit alors attribuer une pondération en fonction de sa performance de discrimination et qui est mise à jour itération par itération afin d’adapter la frontière décisionnelle en fonction des zones les plus difficiles à classer.

Le classifieur utilisé est la plupart du temps la régression linéaire, logistique ou les arbres de décision. Ils portent le nom de « classifieurs fiables » à la fois car ils sont simples d’utilisation mais également car l’objectif du boosting est d’améliorer la règle de discrimination lorsqu’elle est peu performante.

Le boosting appartient à la catégorie des méthodes d’apprentissage statistique nécessitant un jeu de d’apprentissage pour la conception de la règle d’apprentissage et un jeu de test pour sa validation afin de limiter les risques de sur-apprentissage. Comme la plupart d’entre elles, le boosting a le principal défaut de concevoir une règle décisionnelle peu lisible d’où son surnom de boîte noire.

Parmi les méthodes de boosting, la plus célèbre reste l’algorithme AdaBoost conçu par Yoav Freun et Robert Shapire en 1997 et définit pour la discrimination d’une variable réponse Y binaire à partir d’un ensemble de variables continues explicatives \mathbf{X} = (X ^1, \cdots, X ^P).

D’autres algorithmes de boosting sont particulièrement répandus, nous pouvons ainsi citer: l’algorithme Gentle Adaboost, Real Adaboost, MART et RankBoost.

\bullet Les algorithmes de Boosting:

Hypothèse préliminaire: Y binaire ou continue, \mathbf{X} continue.

L’algorithme générale:

Avant d’aborder les algorithmes Adaboost et MART, nous présentons l’algorithme de boosting de base.

– Étape initiale: définir un classifieur faible f et un nombre T d’itérations d’entrainement pour l’optimisation des pondérations.

– Étape 1: Soit \mathbf{E}_1 = \mathbf{E} = [Y \mathbf{X}], la matrice de données d’origine et pour laquelle chaque observation a un poids similaire aux autres et égal à 1.

– Étape 2: Pour t \in \lbrace 2, \cdots, T \rbrace,

—- Nous appliquons notre classifieur faible: h_t = f(\mathbf{E}_1)

—- Nous mesurons le taux d’erreurs de classification de la règle décisionnelle conçue précédemment: \epsilon_t = Pr_{x ~ \mathbf{E}_t, y} I[h_t(x) \neq y]

—- Nous mettons à jour les pondérations et chaque observation mal classée se voit attribuer un poids plus important. Ainsi, \mathbf{E}_t devient \mathbf{E}_{t + 1}

– Étape 3: Nous déterminons la règle décisionnelle finale: H(x) = \mbox{Vote a partir des } h_t(x), \forall t \in [1,T]

L’algorithme AdaBoost

L’Algorithme AdaBoost a été pensé pour le cas où Y est binaire. Il se décline de la manière suivante:

– Étape initiale: initialisation des pondérations associées aux observations,

w_i ^1 = \frac{1}{N}, \forall i \in [1,N]

– Étape 1: \forall t \in [2,T]

—- Application du classifieur paramétré sur le jeu d’apprentissage en utilisant les pondérations w_i ^{t - 1}, \forall i \in [1,N], nous obtenons la règle décisionnelle f_t(x).

—- Calcul du taux d’erreurs de la règle décisionnelle définie précédemment,

\epsilon_t = Pr_{x ~ \mathbf{E}_t, y} I[f_t(x) \neq y]

—-Si \epsilon_t >0.5 alors le classifieur fait mieux qu’une règle aléatoire et nous conservons le modèle, sinon nous ajustons,

  • le coefficient de pondération:

\alpha_t = \frac{1}{2} ln(\frac{1 - \epsilon_t}{\epsilon_t})

  • les pondérations:

w_i ^t = w_i ^{t - 1} e ^{\alpha_t \cdot I_{(y_i \neq f_t (x_i))}}, \forall i \in [1,N]

– Étape 2: Nous obtenons le modèle final,

H(x) = sign[\sum_{t = 1} ^T \alpha_t f_t (x)]

L’algorithme Multiple Additive Regression Trees (MART)

L’Algorithme MART se base sur l’utilisation d’arbres de régression. Par conséquent, il est adapté au cas où Y est continue. Les différentes étapes d’estimation sont les suivantes:

– Étape initiale: Initialiser f_0 (x) = arg min_{\delta} \sum_{i = 1} ^N L(y_i, \delta), avec L fonction de perte à minimiser. Et détermination du nombre d’itérations T.

– Étape 1: Pour t \in [1, T],

— Pour i \in [1, N] calculer,

r_{i,t} = - [\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}]_{f = f_{t - 1}}

— Estimer le modèle par arbre de régression sur r_{i,t} et donnant les régions décisionnelles R_{j,t}, \forall j \in \lbrace 1, \cdots, J_t \rbrace

— Pour j \in \lbrace 1, \cdots, J_t \rbrace, calculer,

\delta_{j,t} = arg min_{\delta} \sum_{x_i \in R_{j,t}} L(y_i, f_{t - 1} (x_i) + \delta)

— Mettre à jour f_t (x) = f_{t - 1} (x) + \sum_{j = 1} ^{J_t} \delta_{j,t} I (x \in R_{j,t})

– Étape 2: Nous avons enfin la règle décisionnelle finale de forme: \hat{f} (x) = f_T (x)

\bullet Annexe théorique:

Cette partie de l’article présente une esquisse de la justification de l’usage de la fonction de perte exponentielle.

L’algorithme AdaBoost se base sur l’idée nouvelle d’une fonction de perte exponentielle dont le principal avantage est computationnel. Ainsi, nous montrons facilement que,

f ^* (x) = arg min_{f(x)} E_{Y|x} (e ^{-Y f(x)}) = \frac{1}{2} log \frac{P(Y = 1 | x)}{P(Y = -1 | x)}

Et équivalent à,

P(Y = 1 | x) = \frac{1}{1 + e ^{-2 f^* (x)}}

De cette manière, l’expansion additive produite par l’algorithme AdaBoost revient à estimer une partie du log-odds de P(Y = 1 | x). Ce qui justifie l’usage de son signe comme règle de classification décrite par la formule,

G(x) = sign (\sum_{m = 1} ^M \alpha_m G_m (x))

Un autre critère de minimisation de perte est la log-vraisemblance de la loi binomial négative (appelée également déviance ou entropie croisée), interprétant f comme une transformation logit. Nous avons,

p(x) = P(Y = 1 | x) = \frac{e ^{f(x)}}{e ^{-f(x)} + e ^{f(x)}}  = \frac{1}{1 + e ^{-2 f(x)}}

, avec Y ' = \frac{Y + 1}{2} \in \lbrace 0, 1 \rbrace. La fonction de perte est alors,

l(Y,p(x)) = Y ' log (p(x)) + (1 - Y ') log(1 - p(x))

Et de déviance,

-l (Y, f(x)) = log (1 + e ^{-2Y f(x)})

De la formule précédente, nous voyons que,

E_{Y|x} [-l(Y,f(x))] = E_{Y|x} [e ^{-Y f(x)}]

\bullet Application informatique:

Procédure SAS: ND.

Package et fonction Rhttps://www.rdocumentation.org/packages/JOUSBoost/versions/2.1.0/topics/adaboost

\bullet Bibliographie:

– The Elements of Statistical Learning de Trevor Hastie, Robert Tibshirani et Jerome Friedman.

– The top ten algorithms in data mining de Xindong Wu et Vipin Kumar.

– Probabilité, analyse des données et Statistique de Gilbert Saporta.

– Data mining et statistique décisionnelle. L’intelligence des données de Stéphane Tufféry.