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 (Freund et Schapire 1997).

Histoire et principe[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[1].

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[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

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.

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,‎ 1997, p. 119-139

Liens externes[modifier | modifier le code]

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

  1. Page officielle du prix Gödel 2003