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})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 Dt :

\epsilon_{t} = \min_{h \in \mathcal{H}} \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 Zt 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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article AdaBoost de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • AdaBoost — AdaBoost, short for Adaptive Boosting, is a machine learning algorithm, formulated by Yoav Freund and Robert Schapire. It is a meta algorithm, and can be used in conjunction with many other learning algorithms to improve their performance.… …   Wikipedia

  • AdaBoost — (сокращение от Adaptive Boosting)  алгоритм машинного обучения, предложенный Йоавом Фройндом (en:Yoav Freund) и Робертом Шапирe (en:Robert Schapire). Этот алгоритм может использоваться в сочетании со многими другими алгоритмами обучения для… …   Википедия

  • Méthode de Viola et Jones — Un exemple de détection de visage par la méthode de Viola et Jones. La méthode de Viola et Jones est une méthode de détection d objet dans une image numérique, proposée par les chercheurs Paul Viola et …   Wikipédia en Français

  • BrownBoost — is a boosting algorithm that may be robust to noisy datasets. BrownBoost is an adaptive version of the boost by majority algorithm. As is true for all boosting algorithms, BrownBoost is used in conjunction with other machine learning methods.… …   Wikipedia

  • BrownBoost — BrownBoost  алгоритм бустинга, который показал свою эффективность на зашумленных наборах данных. Как и все алгоритмы бустинга, BrownBoost используется в сочетании с другими алгоритмами машинного обучения. Алгоритм BrownBoost был предложен… …   Википедия

  • Yoav Freund — Infobox Scientist name = Yoav Freund image width = caption = birth date = birth place = residence = nationality = field = Computer Science work institution = University of California, San Diego alma mater = University of California, Santa Cruz… …   Wikipedia

  • Boosting methods for object categorization — Given images containing various known objects in the world, a classifier can be learned from them to automatically categorize the objects in future images. Simple classifiers built based on some image feature of the object tend to be weak in… …   Wikipedia

  • Robert Schapire — Infobox Scientist name = Robert Elias Schapire image width = caption = birth date = birth place = residence = nationality = field = Computer Science work institution = AT T LabsPrinceton University alma mater = Brown UniversityMassachusetts… …   Wikipedia

  • Boosting — is a machine learning meta algorithm for performing supervised learning. Boosting is based on the question posed by KearnsMichael Kearns. Thoughts on hypothesis boosting. Unpublished manuscript. 1988] : can a set of weak learners create a single… …   Wikipedia

  • LPBoost — Linear Programming Boosting (LPBoost) is a supervised classifier from the Boosting family of classifiers. LPBoost maximizes a margin between training samples of different classes and hence also belongs to the class of margin maximizing supervised …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”