AdaBoost

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})$ 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_{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} = \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 $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

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

Boosting.org, un site sur le boosting en général

A decision-theoretic generalization of on-line learning and an application to boosting Journal of Computer and System Sciences, no. 55. 1997 (Premier article où adaboost fut introduit par Yoav Freund et Robert E.Schapir)

A Short Introduction to Boosting Introduction à Adaboost par Freund et Schapire en 1999

Portail de l'informatique théorique

Portail des probabilités et des statistiques

Catégories :
Algorithme de classification
Apprentissage automatique

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

Dictionnaires et Encyclopédies sur 'Academic'

AdaBoost

L'Algorithme

Variantes

Liens

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

AdaBoost

L'Algorithme

Variantes

Liens

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link