« AdaBoost » : différence entre les versions
Contenu supprimé Contenu ajouté
m Ajout rapide de {{portail}} : + probabilités et statistiques ; avec BandeauxPortails |
m LI |
||
| (43 versions intermédiaires par 26 utilisateurs non affichées) | |||
Ligne 1 :
{{Infobox Méthode scientifique}}
En [[intelligence artificielle]] et en [[apprentissage automatique]], '''AdaBoost''' (ou ''adaptive boosting'') est un méta-algorithme de [[boosting]] introduit par [[Yoav Freund]] et [[Robert Schapire]] en 1997<ref>{{harv|Freund|Schapire|1997}}</ref>. AdaBoost améliore les performances de n'importe quel algorithme d'apprentissage appelés ''classifieurs faibles''. Le principe est la [[Sagesse de la foule|sagesse d'une foule]] d'experts. Chaque classifieur faible est un expert. On combine alors leurs prédictions en une somme pondérée qui représente la prédiction finale du classifieur ''boosté''. AdaBoost est ''adaptatif'' dans le sens où les classeurs faibles subséquents sont ajustés en faveur des échantillons mal classés par les classifieurs précédents.
AdaBoost est notablement sensible aux données bruitées ou peu corrélées. Toutefois, dans certains problèmes, il peut s'avérer moins enclin au surapprentissage que d'autres algorithmes. Les sous-classeurs utilisés peuvent être faibles tant qu'ils proposent une performance au moins un peu supérieure à celle d'un classeur aléatoire, auquel cas il peut être prouvé que le modèle final converge vers un classeur fort.
Tous les algorithmes d'apprentissage tendent à correspondre plus à certains types de problèmes qu'à d'autres, et ont typiquement de nombreux paramètres et configurations différents qu'il est nécessaire d'ajuster pour atteindre une performance optimale sur un ensemble d'apprentissage fourni. AdaBoost (avec des [[Arbre de décision (apprentissage)|arbres de décision]] comme classeurs faibles) est souvent désigné comme le meilleur classeur clé-en-main.
== Principes ==
[[Fichier:Adaboost principle.png|vignette|Schéma du principe d'Adaboost. Les exemples sont représentés par des rectangles ; leurs tailles sont proportionnelles à leur poids. On donne un poids plus grand quand un exemple est mal classé (marqué par un X). A la fin, on combine les classifieurs faibles <math>h_1, \dots, h_4</math> pour calculer le classifieur final ''h''.]]
Adaboost repose sur plusieurs principes.
* C'est une technique d'ensemble learning. Ainsi, on calcule plusieurs classifieurs faibles dont on combine alors les résultats. Typiquement, la combinaison s'effectue à l'aide d'un [[vote]] majoritaire. Si par exemple nous avons trois classifieurs, l'un dit "c'est un chat", le deuxième "ce n'est pas un chat", le troisième dit "c'est un chat", alors Adaboost décide que c'est un chat.
* Le calcul des classifieurs est effectivement de manière itérative.
* Durant l'exécution, les exemples sont pondérés. Un exemple est d'autant plus important que le classifieur courant se trompe. On donnera donc plus d'importance à ces exemples récalcitrants. En ce sens, c'est un exemple de la [[méthode des poids multiplicatifs]] (''multiplicative weights update method'')<ref>{{lien web|url=http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf|titre=The Multiplicative Weights Update Method: a Meta Algorithm and Applications|auteur=[[Sanjeev Arora]], Elad Hazan et Satyen Kale}}.</ref>{{,}}<ref>{{lien web|url=http://courses.cs.washington.edu/courses/cse521/10wi/kale-thesis-chap2.pdf|titre=The Multiplicative Weights Update method|site=[[Université de Washington]]}}.</ref>.
* Dans la décision finale, ce n'est pas un vote majoritaire classique mais un vote majoritaire pondéré. Autrement dit, les classifieurs faibles sont eux-mêmes pondérés.
== Description ==
Soit un ensemble d'''observations'' (aussi appelé ''exemples''). Notons les <math>(x_{1},y_{1}),\ldots,(x_{m},y_{m})</math> où <math>x_{i} \in X,</math> sont les caractéristiques de l'individu <math>i</math> et <math>\, y_{i} \in Y = \{-1, +1\}</math> la classe à prédire. On initialise les poids associés aux observations de manière uniforme : le poids de la <math>i</math>-ème observation est <math>D_{t}(i) = \frac{1}{m}</math> pour tout <math>i=1,\ldots,m</math>, avec <math>m</math> est le nombre d'observations. L'algorithme construit alors itérativement <math>T</math> classifieurs faibles <math>h_1, \dots, h_T</math>.
Pour <math>t = 1,\ldots,T</math> :
* Trouver
<math>\epsilon_{t} = \min_{h \in \mathcal{H}} \sum_{i=1}^{m} D_{t}(i)[y_i \ne h(x_{i})]</math>▼
<math>h_{t} = \arg \min_{h \in \mathcal{H}} \sum_{i=1}^{m} D_{t}(i)[y_i \ne h(x_{i})]</math>
* Si <math>\epsilon_{min,t} < 0.5</math> le classifieur est sélectionné, sinon l'algorithme s'arrête ▼
est l'erreur du modèle.
* On choisit alors le poids du classifieur : <math>\alpha_{t} \in \mathbf{R}</math>, avec <math>\alpha_{t}=\frac{1}{2}\textrm{ln}\frac{1-\epsilon_{t}}{\epsilon_{t}}</math> ▼
▲* Si <math>\epsilon_{min,t} < 0.5</math>{{Quoi|date=20 octobre 2023}}
Le classifieur résultant du processus de sélection est :▼
▲* On
* On met ensuite à jour le poids des exemples : <math>D_{t+1}(i) = \frac{ D_{t}(i) \, e^{- \alpha_{t} y_{i} h_{t}(x_{i})} }{ Z_{t} }</math> où <math>Z_{t}</math>est le facteur de normalisation égal à <math> 2 \sqrt{\epsilon_{t} (1-\epsilon_{t}) } </math>
▲
<math>H(x) = \textrm{sign}\left( \sum_{t=1}^{T} \alpha_{t}h_{t}(x)\right)</math>
== 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. 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<ref>[http://www.eatcs.org/index.php/component/content/article/505 Page officielle du prix Gödel 2003]</ref>.
== Notes et références ==
<references />
== Bibliographie ==
* {{Article
| langue = en
| prénom1 = Yoav | nom1 = Freund | lien auteur1 = Yoav Freund
| prénom2 = Robert | nom2 = Schapire | lien auteur2 = Robert Schapire
| titre = A decision-theoretic generalization of on-line learning and an application to boosting
| périodique = Journal of Computer and System Sciences
| volume = 55 | numéro = 1
| année = 1997
| passage = 119-139
}}
== Liens externes ==
* [http://www.boosting.org Boosting.org], un site sur le boosting en général
▲* [http://citeseer.ist.psu.edu/cache/papers/cs/2215/http:zSzzSzwww.first.gmd.dezSzpersonszSzMueller.Klaus-RobertzSzseminarzSzFreundSc95.pdf/freund95decisiontheoretic.pdf 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)
* [http://www.site.uottawa.ca/~stan/csi5387/boost-tut-ppr.pdf A Short Introduction to Boosting] Introduction à Adaboost par Freund et Schapire en 1999
Ligne 37 ⟶ 66 :
[[Catégorie:Algorithme de classification]]
[[Catégorie:Apprentissage automatique]]
| |||