AdaBoost

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)[2] - [3].

Soit un ensemble d'observations. Notons les : ${\displaystyle (x_{1},y_{1}),\ldots ,(x_{m},y_{m})}$ où ${\displaystyle x_{i}\in X,}$ sont les caractéristiques de l'individu ${\displaystyle i}$ et ${\displaystyle \,y_{i}\in Y=\{-1,+1\}}$ la variable à prédire.

On initialise le poids associé à ${\displaystyle i}$, ${\displaystyle D_{t}(i)={\frac {1}{m}},i=1,\ldots ,m.}$

Pour ${\displaystyle t=1,\ldots ,T}$ :

• Trouver la fonction ${\displaystyle h_{t}:X\to \{-1,+1\}}$ qui minimise l'erreur de classification ${\displaystyle \epsilon _{t}}$ en fonction des poids ${\displaystyle D_{t}}$. C'est-à-dire ${\displaystyle h_{t}}$qui vérifie le programme de minimisation suivant :

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

${\displaystyle \epsilon _{t}=\sum _{i=1}^{m}D_{t}(i)[y_{i}\neq h(x_{i})]}$ est l'erreur du modèle.

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

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

Quand l'algorithme s'arrête à l'itération ${\displaystyle M}$, le classifieur résultant du processus de sélection est :

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

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.

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[4].

• (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)

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