• 15 heures
  • Moyenne

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 01/02/2019

Initiez-vous aux méthodes séquentielles et au Boosting

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Dans cette seconde partie, intéressons-nous à la seconde famille de méthodes ensemblistes, les méthodes séquentielles.

Le méthodes séquentielles, qu'est-ce que c'est ?

Imaginez le problème suivant : on veut déterminer si un champignon est toxique ou pas, à partir de certaines caractéristiques (couleur, taille, odeur, etc).

Alors, une idée ?
Alors, une idée ?

Pour cela, nous disposons d’un jeu de données d’entraînement contenant un vecteur d’observations de différents champignons X, ainsi qu’un label binaire  $\(y \in \{-1,1\}\)$ indiquant s’il est effectivement toxique

Un modèle de classification C(X) retourne la prédiction binaire “toxique” ou “non toxique”. Ca peut être n’importe quel modèle de classification étudié précédemment (réseau de neurones, SVM, etc). De la même manière que les algorithme de bagging, les algorithmes de boosting utilisent des algorithmes de classification dits “faibles” qui performent à peine mieux qu’un classifieur aléatoire.

On entraîne donc un premier classifieur $\(G_1\)$ sur le jeu de données. Comme il effectue un certain nombre d’erreurs, on décide d’augmenter le poids $\(w\)$ associé aux observations qui induisent en erreur, afin de leur donner plus d’importance dans l’entraînement. On entraîne ainsi un second classifieur $\(G_2\)$ avec ce nouveau jeu de données pondéré, ce qui lui permet de se concentrer sur ces observations qui induisent en erreur $\(G_1\)$ . On créé de la sorte une suite de classifieurs $\(G_1, G_2, ... G_M\)$ qui s’appuient chacun sur les erreurs effectuées par le classifieur précédent pour repondérer un nouveau dataset sur lequel s’entraîner.

On peut maintenant combiner ces différents classifieur afin d’obtenir notre classifieur final le plus performant.

Adaboost

Pour obtenir ce classifieur final, il nous suffit d’effectuer la somme pondérée des différents classifieurs

$\(\sum_1^M G_m(x)\)$

Comme un classifieur binaire retourne une réponse binaire, on récupère le signe de cette somme

$\(\text{sign} \{ \sum_1^M C_m(x) \}\)$

Il manque quelque chose. C’est dommage de donner autant d’importance à chacun des classifieurs, même ceux qui performant mal au global. Voyons ce qu’on peut faire. Chaque classifieur $\(G_m\)$  possède son taux d’erreur sur le jeu de données pondéré :

$\(\text{err}_m = \frac{\sum_{i=1}^N w_i I (y_i \neq G_m (x_i) }{\sum_{i=1}^N w_i}\)$

Pour accorder une plus grande importance à ceux qui ont le taux d’erreur global $\(\text{err}\)$ le plus faible, on pondère notre somme par le poids $\(\alpha_m = log(\frac{1 - \text{err}}{\text{err}})\)$ .

On a donc notre classifieur final

 $\(\text{sign} \sum_{m=1}^M \alpha_m G_m(x)\)$

Il nous reste une dernière question... Comment pondérer le jeu de données à chaque étape ? Chaque classifieur est entraîné sur un jeu de donnée pondéré qui accorde plus d’importance aux observations qui ont induit en erreur le classifieur précédent. On va donc utiliser notre poids $\(\alpha_m\)$ . Pour chaque observation $\(x_i\)$, on pondère par le poids

$\(w_i^{(m)} = w_i^{(m-1)} \text{exp}( \alpha_m I(y_i \neq G_m(x_i)))\)$

L’algorithme final du Adaboost pour une classification binaire est donc :

L’Adaboost peut aussi être utilisé en régression ou en classification multiclasse, mais le principe reste le même.

Je rappelle les différents choix et hyperparamètres qui caractérisent l’algorithme :

  • la fonction de perte utilisée

  • le type de classifieur. Le plus utilisé est l’arbre de décision mais on pourrait techniquement utiliser un réseau de neurones ou un SVM).

  • la taille M de la séquence de classifieurs.

Boosting d'arbres aléatoires

Avec l’Adaboost, on va le plus souvent utiliser nos bons vieux apprenants faibles que sont les arbres aléatoires. Mais on va même faire encore plus simple que ça, on va utiliser ce qu’on appelle en anglais des stumps c’est à dire des arbres qui ne font qu’une seule séparation, avec un seul noeud !

Un stump est un arbre de décision très simple
Un stump est un arbre de décision très simple

Conclusion

Maintenant qu'on a une meilleure idée de la technique du boosting originale, on peut passer à la plus utilisée de nos jours : le gradient boosting !

Exemple de certificat de réussite
Exemple de certificat de réussite