L’algorithme AdaBoost en Machine Learning

Temps de lecture : 7 minutes

Si tu connais l’expression populaire « l’union fait la force », tu as déjà compris 50% du principe de l’algorithme que je m’en vais te présenter dans cet article : l’AdaBoost (désignation commune pour Adaptive Boosting). Il fait en effet partie des techniques d’ensemble learning. L’idée est d’associer plusieurs modèles d’apprentissage faibles pour créer un modèle ultime fort capitalisant sur les forces de chacun des modèles constitutifs. Tu te souviens des forêts aléatoires que j’avais présentées dans cet article ? Eh bien, c’est un autre exemple d’ensemble learning. Mais comment est-ce que la technique d’AdaBoost s’en démarque t-elle ?

Comme d’habitude, sortons notre exemple loufoque pour illustrer tout ça !😀

Le cas d’étude loufoque… comme d’habitude

Hier, avec 5 autres potes, nous avons eu l’idée « géniale » d’essayer de rentrer dans un club select de Paris à 2h du matin ! Tu sais ce qu’on dit, « qui ne risque rien n’a rien » et Dieu sait que nous, nous aimons le risque 😅. Sauf qu’on était 6 mecs, pas forcément en tenues de luxe, certains arborant même des baskets et cerise sur le gâteau, on ne connaissait aucun videur ou organisateur de la soirée. Bon je te la fais courte, nous avons tous été recalés. Mais pour l’intérêt de cet article, disons que certains ont pu rentrer… (quoi ? on a encore le droit de s’inventer des vies dans ce pays 😛).

Disons que les 3 critères qui déterminent le recalage/ l’entrée (Y = 1 / Y = 0) sont le port d’une tenue de luxe (X_1), le port de basket (X_2), et la connaissance d’un videur (X_3). Au bilan, dans ma nouvelle histoire fictive, 3 personnes sont rentrées et 3 ont été recalées. Les données recueillies ressemblent à ceci :

Tu l’as peut-être deviné, il s’agit à partir de ces données, d’élaborer un modèle pouvant prédire si une personne sera recalée en fonction de nouvelles entrées (X_1, X_2, X_3). Parmi les solutions possibles, on peut opter par exemple pour une forêt aléatoire (random forest) ou pour l’AdaBoost. J’ai déjà écrit un article complet sur le mode d’emploi de la forêt aléatoire. Si je la mentionne autant dans cet article, c’est qu’elle a beaucoup de points en commun avec l’AdaBoost. Commençons donc par un petit rappel pour mieux souligner ses différences avec l’AdaBoost.

La forêt aléatoire (le petit rappel didactique) vs l’AdaBoost

Le principe de la forêt aléatoire est de créer de nombreux arbres de décision indépendants dans un premier temps. On les utilise tous ensuite pour effectuer la prédiction finale en se basant sur la règle du vote majoritaire.

Trois points essentiels de démarcation existent entre la forêt aléatoire et l’AdaBoost :

Indépendance des arbres

Les arbres créés par la forêt aléatoire sont indépendants les uns des autres i.e. la création de l’arbre 2 ne tient pas compte des résultats de l’arbre 1. A l’opposé, la technique de l’AdaBoost est, elle, séquentielle : l’arbre 2 tient compte des résultats de l’arbre 1, le but étant de corriger les erreurs de l’arbre 1 et ainsi de suite… Tous les arbres créés par l’AdaBoost visent donc ainsi à se compléter : ils se « boostent » mutuellement.

Taille des arbres

Dans la forêt aléatoire, tous les arbres créés se suffisent à eux-mêmes. Ce sont des arbres complètement développés avec une grande taille. A l’opposé, chaque arbre créé dans l’AdaBoost est une « souche » (« stump » en anglais) c’est-à-dire possédant une racine et uniquement deux feuilles. Un tel arbre est donc insuffisant à lui seul pour effectuer des prédictions, renforçant par conséquent l’idée de complémentarité avec les autres arbres de l’AdaBoost.

Votes égalitaires

Dans la forêt aléatoire, tous les arbres créés ont le même poids dans les prédictions finales. Si 100 arbres ont été créés et que 60 prédisent oui, et 40 non, le oui l’emporte d’emblée. Dans l’AdaBoost, par contre, tous les arbres n’ont pas les mêmes poids. Certains arbres font plus foi que d’autres et les coefficients de pondération des arbres sont à prendre en compte pour les prédictions finales.

Maintenant que tu connais les grands axes de l’AdaBoost, voyons comment l’implémenter en pratique 🙂.

Implémentation de l’AdaBoost
Etape 1 : ajout de poids aux différents individus

Revenons sur nos merveilleuses données de recalage en club ! Pour l’AdaBoost, on commence d’abord par rajouter une colonne poids (w_i) aux différents individus. L’utilité de ces poids sera plus claire à la prochaine étape, promis ! Pour l’instant contentons-nous de rajouter les mêmes poids à tous les individus de sorte que la somme totale des poids soit égale à 1. Si on appelle n le nombre total d’individus, il ne faut pas être médaillé Fields de maths pour comprendre que chaque individu a un poids \frac{1}{n}. Dans notre cas, ce sera donc \frac{1}{6}\approx0.17.

Etape 2 : création du premier arbre de décision

Ensuite, il faut créer notre premier arbre de décision (ou « souche de décision » si tu préfères). J’ai déjà écrit un article complet sur l’établissement de l’arbre de décision si tu ne l’as pas encore lu 😉. Sans rentrer dans les détails, supposons qu’en utilisant cette première souche, on a réussi à avoir 4 bonnes classifications (individu 1 à 4) et 2 mauvaises classifications (les individus 5 et 6 ont été mal classifiés). Il faut désormais calculer l’erreur totale ET du premier arbre en additionnant les poids des individus mal classifiés soit :

ET = w_5 + w_6 = \frac{1}{3}

Plutôt simple non ? Cette erreur totale va servir à présent à calculer la performance Perfde l’arbre de décision créé. Tu te souviens quand je te disais que chaque arbre avait un poids décisionnel dans la prédiction finale ? Eh bien, ce poids décisionnel, c’est la performance que nous sommes sur le point de calculer en utilisant la formule :

Perf = \frac{1}{2}*\log(\frac{1 - ET}{ET})\approx0.35

Ne te laisse pas impressionner par le log. L’idée essentielle, c’est que pour un arbre qui commet beaucoup d’erreurs, la formule donne une performance faible et donc, un poids plus petit dans la prédiction finale. Tu vois, ce n’est pas sorcier 😀 ! En pratique, on adapte mathématiquement la formule pour prendre en compte les situations où ET = 1 ou ET = 0 mais le principe reste exactement le même. Aller, cap sur la prochaine étape !

Etape 3 : Mise à jour des poids des individus

Je te l’avais dit plus haut : l’idée essentielle de l’AdaBoost c’est de créer des arbres séquentiellement de telle manière que l’arbre actuel puisse essayer de corriger les erreurs de l’arbre précédent. C’est en fait à ça que servent les poids des individus. Dans l’arbre précédent les individus 5 et 6 ont été mal classifiés. Nous allons donc augmenter leur poids pour que le nouvel arbre que nous allons créer puisse se concentrer sur eux prioritairement. Si on appelle w_{n} le nouveau poids et w_{a} l’ancien poids, pour un individu actuellement mal classifié, le nouveau poids est donné par :

w_{n} = w_{a}*\exp(Perf)

L’exponentiel permet donc d’augmenter le poids des individus mal classifiés. En contrepartie, on diminue le poids des individus bien classifiés par l’arbre précédent (de la sorte, le nouvel arbre fait moins attention à eux). La formule de diminution de poids est similaire à la précédente à un ‘moins’ près. En effet, pour un individu mal classifié :

w_{n} = w_{a}*\exp(-Perf)

Le nouveau tableau des poids doit ressembler désormais à ceci :

Petite précision, si on fait la somme des nouveaux poids, on n’a pas forcément 1. Il faut donc normaliser toutes les valeurs par la somme totale des poids pour obtenir les nouveaux poids définitifs.

Etape 4 : Création du second arbre avec les nouveaux poids

Avec ces nouveaux poids, on recommence le processus de création d’un nouvel arbre de décision. Cette fois-ci, on prend en compte les poids des individus en utilisant le coefficient de Gini pondéré par exemple. On peut aussi reconstituer un nouveau jeu de données en piochant aléatoirement dans les données précédentes. Une condition est nécessaire par contre : la probabilité de piocher un individu est égale à son poids. De la sorte, les individus ayant les plus grands poids ont plus de chance d’être piochés plus souvent. Le nouvel arbre de décision essayera donc de les prioriser.

La mécanique « création d’arbre + mise à jour des poids » continue jusqu’à ce qu’on obtienne le nombre total d’arbres désiré. Mais une fois ce nombre atteint, comment exploiter les arbres ?

Etape 5 : Exploitation des arbres

Au terme de la construction des arbres, on se retrouve avec un certain nombre d’arbres de décision (souches de décision). Chacun des arbres possède un poids de décision correspondant à sa performance. Si on a un nouveau triplet (X_1, X_2,X_3) pour lequel il faut prédire la valeur de sortie Y, on recueille les réponses de tous les arbres établis. Ensuite, on additionne les performances de tous ceux qui ont retourné Y = 1 puis les performances de tous ceux qui ont retourné Y=0. Le groupe qui a la somme des performances la plus élevée impose sa décision. Ce n’est donc plus tant la décision de la majorité comme dans la forêt aléatoire, mais plus la décision du groupe qui a le plus de « pouvoir ». Comme quoi, la démocratie n’est pas toujours la solution 😏…

Implémentation d’AdaBoost sur Python

Comme d’habitude, j’ai essayé de détailler la machinerie interne de l’algorithme pour que tu puisses mieux cerner ses rouages mais sur Python, tout est déjà implémenté 🙂. On ira chercher dans la librairie sklearn.ensemble. Dans son usage le plus simple, il faut lui préciser l’estimateur de base qui par défaut est l’arbre de décision avec une profondeur de 1. En fait, ce que j’ai omis de te dire pour des raisons pédagogiques, c’est qu’AdaBoost marche sur tous les estimateurs (SVM, régression logistique…) et pas uniquement avec l’arbre de décision. Dès que tu as un modèle de base que tu veux booster, tu peux faire appel à AdaBoost. Mais gardons simplement ici, l’usage avec l’arbre de décision. Tu peux aussi donc spécifier par la suite le nombre d’arbres que tu désires utiliser… Et c’est tout ! Je t’avais dit que Python se chargeait de tout 😉.

from sklearn.ensemble import AdaBoostClassifier

# AdaBoost avec 100 arbres de décision
modele = AdaBoostClassifier(n_estimators = 100)

# Entrainement
modele.fit(X_entrainement,y_entrainement)

# Utilisation pour prédire sur de nouvelles données X_test
modele.predict(X_test)

Et voilà, le tour est joué ! Tu peux t’amuser à voir ce que ça donne sur mes données de recalage en club – avec l’arbre de décision et ensuite avec d’autres modèles de base. Avec un peu de chances, tu pourrais peut-être trouver le modèle ultime pour éviter une nuit de recalage à un autre groupe de potes 🤐…

Partager

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *