AdaBoost

Adaboost (ou adaptive boosting) est une méthode de boosting (intelligence artificielle, apprentissage automatique) introduite par Yoav Freund et Robert Schapire. Ce fut l'une des premières méthodes pleinement fonctionnelles permettant de mettre en œuvre le principe de boosting.

Adaboost repose sur la sélection itérative de classifieur faible en fonction d'une distribution des exemples d'apprentissage. Chaque exemple est pondéré en fonction de sa difficulté avec le classifieur courant.

L'Algorithme

Soit un ensemble d'apprentissage annoté : $(x_{1},y_{1}),\ldots ,(x_{m},y_{m})$ où $x_{i}\in X,$sont les exemples et $\,y_{i}\in Y=\{-1,+1\}$ les annotations.

On initialise la distribution des exemples par $D_{1}(i)={\frac {1}{m}},i=1,\ldots ,m.$

Pour $t=1,\ldots ,T$ :

• Trouver le classifieur $h_{t}:X\to \{-1,+1\}$ qui minimise l'erreur de classification $\epsilon _{t}$ en fonction de la difficulté des exemples $D_{t}$ :

$\epsilon _{t}=\min _{h\in {\mathcal {H}}}\sum _{i=1}^{m}D_{t}(i)[y_{i}\neq h(x_{i})]$ et $h_{t}=\arg \min _{h\in {\mathcal {H}}}\sum _{i=1}^{m}D_{t}(i)[y_{i}\neq h(x_{i})]$

• Si $\epsilon _{min,t}<0.5$ le classifieur est sélectionné, sinon l'algorithme s'arrête
• On choisit alors le poids du classifieur : $\alpha _{t}\in \mathbf {R}$, avec $\alpha _{t}={\frac {1}{2}}{\textrm {ln}}{\frac {1-\epsilon _{t}}{\epsilon _{t}}}$
• On met ensuite à jour la pondération des exemples d'apprentissage

$D_{t+1}(i)={\frac {D_{t}(i)\,e^{-\alpha _{t}y_{i}h_{t}(x_{i})}}{Z_{t}}}$
avec $Z_{t}$ un facteur de normalisation

Le classifieur résultant du processus de sélection est :

$H(x)={\textrm {sign}}\left(\sum _{t=1}^{T}\alpha _{t}h_{t}(x)\right)$

Variantes

Des variantes ont été introduites, et dont les modifications portent essentiellement sur la manière dont les poids sont mis à jour. Parmi ces variantes, Gentle AdaBoost et Real Adaboost sont fréquemment utilisées.

Liens

• Boosting.org, un site sur le boosting en général
• A decision-theoretic generalization of on-line learning and an application to boosting Journal of Computer and System Sciences, no. 55. 1997 (Premier article où adaboost fut introduit par Yoav Freund et Robert E.Schapir)
• A Short Introduction to Boosting Introduction à Adaboost par Freund et Schapire en 1999