AdaBoost

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Adaboost (ou adaptive boosting) est une méthode de boosting (intelligence artificielle, apprentissage automatique) introduite par Yoav Freund et Robert Schapire[1].

Principe[modifier | modifier le code]

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 générale Multiplicative Weights Update[2],[3].

Description[modifier | modifier le code]

Soit un ensemble d'apprentissage annoté : (x_{1},y_{1}),\ldots,(x_{m},y_{m})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} = \sum_{i=1}^{m} D_{t}(i)[y_i \ne h(x_{i})] et h_{t} = \arg \min_{h \in \mathcal{H}} \sum_{i=1}^{m} D_{t}(i)[y_i \ne 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[modifier | modifier le code]

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[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

  1. (Freund et Schapire 1997)
  2. Sanjeev Arora, Elad Hazan et Satyen Kale, « The Multiplicative Weights Update Method: a Meta Algorithm and Applications ».
  3. « The Multiplicative Weights Update method », sur Université de Washington.
  4. Page officielle du prix Gödel 2003

Bibliographie[modifier | modifier le code]

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

Liens externes[modifier | modifier le code]