AdaBoost

AdaBoost (ou adaptive boosting) est, en intelligence artificielle et en apprentissage automatique, un méta-algorithme de boosting introduit par Yoav Freund et Robert Schapire. Il peut être utilisé en association avec de nombreux autres types d'algorithmes d'apprentissage afin d'en améliorer les performances. Les sorties des autres algorithmes (appelés classeurs faibles) sont combinées en une somme pondérée qui représente la sortie finale du classeur boosté. AdaBoost est adaptatif dans le sens où les classeurs faibles subséquents sont ajustés en faveur des échantillons mal classés par les classeurs précédents.

AdaBoost est notablement sensible aux données bruitées ou peu corrélées. Toutefois, dans certains problèmes, il peut s'avérer moins enclin au surapprentissage que d'autres algorithmes. Les sous-classeurs utilisés peuvent être faibles tant qu'ils proposent une performance au moins un peu supérieure à celle d'un classeur aléatoire, auquel cas il peut être prouvé que le modèle final converge vers un classeur fort.

Tous les algorithmes d'apprentissage tendent à correspondre plus à certains types de problèmes qu'à d'autres, et ont typiquement de nombreux paramètres et configurations différents qu'il est nécessaire d'ajuster pour atteindre une performance optimale sur un ensemble d'apprentissage fourni. AdaBoost (avec des arbres de décision comme classeurs faibles) est souvent désigné comme le meilleur classeur clé-en-main.

Principe

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. C'est un exemple de la méthode des poids multiplicatifs (multiplicative weights update method).

Description

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_{t}(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}=\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 égal à $2{\sqrt {\epsilon _{t}(1-\epsilon _{t})}}$

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. Citons aussi RankBoost.

Histoire

Ce fut l'une des premières méthodes pleinement fonctionnelles permettant de mettre en œuvre le principe de boosting. Les auteurs ont reçu le prestigieux prix Gödel en 2003 pour leur découverte.

Bibliographie

• (en) Yoav Freund et Robert Schapire, « A decision-theoretic generalization of on-line learning and an application to boosting », Journal of Computer and System Sciences, vol. 55, n^o 1,‎ 1997, p. 119-139 (lire en ligne)

Liens externes

• Boosting.org, un site sur le boosting en général
• A Short Introduction to Boosting Introduction à Adaboost par Freund et Schapire en 1999