Introduction au boosting

Jean-Marc Lasgouttes, Inria de Paris

[email protected]

http://mastere-esd.lasgouttes.net/boosting

Mastère spécialisé
« expert en sciences des
données »

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024.

 I Introduction au cours
II AdaBoost
III Modélisation additive linéaire
IV Gradient Boosting
V XGBoost
 Organisation du cours
Matin Cours (3 heures)
▶ description de AdaBoost
▶ description de Gradient Boosting et XGBoost
▶ packages R implémentant les méthodes
Après midi TP (4 heures)
▶ application des méthodes sur un jeu de données
▶ rédaction d’un rapport rapide décrivant votre approche et vos résultats.
Références
▶ Freund, Y. and Schapire, R., A decision-theoretic generalization of on-line learning
and an application to boosting. Journal of computer and system sciences, 1997,
55 (1), 119-139
▶ J. H. Friedman, Greedy Function Approximation: A Gradient Boosting Machine,
Annals of Statistics, 2001, 29(5):1189-1232.
▶ Zhu, J., Zou, H., Rosset, S. and Hastie, T., Multi-class AdaBoost. Statistics and
its Interface 2009, 2, 349–360.
▶ Hastie, T., Tibshirani, R., & Friedman, J. H. (2009). The elements of statistical
learning: data mining, inference, and prediction. 2nd ed. New York: Springer.

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 2

 Le problème de classification

Observations On dispose de données x ∈ E :

▶ E = Rp : p variables quantitatives (poids, taille, âge...)
▶ E = {1, . . . , n1} × {1, . . . , n2} × · · · × {1, . . . , np} : p variables qualitatives
(couleur des yeux, sexe, métier,...)
▶ ou un mélange de tout cela
La classification À chaque variable x, on cherche à associer une variable y ∈ {−1, 1}
▶ « a survécu au naufrage du Titanic »
▶ « risque de faire un AVC dans l’année qui vient »
▶ « fraude le fisc »
▶ ...
Les données On dispose d’un échantillon de
▶ n observations (x1, . . . , xn) ∈ En,
▶ des classifications (y1, . . . , yn) ∈ {−1, 1}n
Objectif On cherche une fonction G : E 7→ {−1, 1}, telle que G(x) soit une bonne
prédiction du y correspondant

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 3

 Boosting

Classifieurs faibles On se repose sur un ensemble de classifieurs h : E 7→ {−1, 1}

très simples qui permettent de prédire y juste un peu mieux que le hasard :

1
ϵ = P (h(x) ̸= y) ≤ − γ, γ > 0
2

Exemple de classifieur faible Les plus utilisés sont

▶ arbres de décision (CART, Classification And Regression Tree) de faible profon-
deur ;
▶ stumps (souches), c’est-à-dire arbre de profondeur 1, par exemple pour le Titanic

age < 15 =⇒ survie, age ≥ 15 =⇒ décès.

Question Est-on capable de fabriquer séquentiellement un classifieur fort (erreur très

petite) à partir d’un grand nombre de classifieurs faibles (erreur un peu plus petite que
0.5) ?
Réponse C’est le boosting !

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 4

 Les approches ensemblistes
Approche générale on cherche à créer un classifieur fort en combinant plusieurs
classifieurs plus simples
Bagging on entraı̂ne les modèles sur des sous-ensemble des données
▶ approche parallèle
▶ pas très efficace pour réduire le biais
▶ évite le sur-ajustement
Random forest bagging + une partie des variables est utilisée pour chaque arbre
▶ mieux que bagging en tout point de vue
Boosting chaque modèle cherche à corriger les faiblesses du précédent
▶ approche itérative
▶ utilise des modèles très simples
▶ réduit le biais
▶ risque de sur-ajustement
Lequel choisir ? dépend de si le problème avec les données est plus le biais (▶ boos-
ting) ou le sur-ajustement (▶ random forest).
Le (gradient) boosting est plus sensible aux paramètres.

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 5

 I Introduction au cours
II AdaBoost
III Modélisation additive linéaire
IV Gradient Boosting
V XGBoost
 Qu’est-ce que c’est ?

Signification Adaptive boosting

Qui ? Cet algorithme a été introduit en 1996 par Yoav Freund and Rob Shapire (prix
Gödel 2003)
Quoi ? C’est le premier algorithme qui montre que les idées du boosting peuvent être
implémentées de manière simple et efficaces
Caractéristiques d’AdaBoost
▶ produit une classification forte à partir de classifications faibles
▶ fonctionne en donnant plus d’importance aux observations difficiles à prédire
▶ très peu de paramètres (nombre de pas, complexité des classifieurs faibles)
▶ évite le sur-ajustement dans certain modèles
▶ peut aussi être utilisé pour des problèmes de régression

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 7

 Exemple simple

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 8

 Exemple simple

▶ première règle faible : stump sur l’ordonnée

▶ 3 éléments sont mal classifiés

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 9

 Exemple simple

▶ première règle faible : stump sur l’ordonnée

▶ 3 éléments sont mal classifiés ; on augmente leur poids

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 10

 Exemple simple

▶ deuxième règle faible : stump sur l’abscisse

▶ 3 éléments sont mal classifiés

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 11

 Exemple simple

▶ deuxième règle faible : stump sur l’abscisse

▶ 3 éléments sont mal classifiés ; on augmente leur poids

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 12

 Exemple simple

▶ troisième règle faible : stump sur l’abscisse

▶ toujours 3 éléments mal classifiés

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 13

 Exemple simple

▶ règles faibles : stump sur l’abscisse ou l’ordonnée

▶ on augmente le poids des éléments mal classifiés à chaque itération
▶ Le classifieur final est une combinaison linéaire des classifieurs construits au fur
et à mesure.

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 14

 Algorithme AdaBoost

Entrée Les éléments nécessaires sont

▶ un échantillon (x1, y1), (x2, y2), . . . , (xn, yn)
▶ un ensemble de règles faibles
▶ le nombre M d’itérations
Initialisation on se donne des poids (w1, . . . , wn) uniformes

1
wi ← , i = 1, . . . , n,
n

qui vérifient évidemment w1 + · · · + wn = 1.

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 15

 Algorithme AdaBoost (suite)
Itération pour m = 1 à M
1. ajuster un classifieur faible gm(x) sur l’échantillon pondéré par les poids wi
2. calculer le taux d’erreur
n
X
ϵm ← wi1{yi̸=gm(xi)}
i=1

p
3. calculer le poids de l’itération m : αm ← log (1 − ϵm)/ϵm
4. mettre à jour les poids des observations
(
1 1 e−αm , si yi = gm(xi),
wi ← wi exp [−αmyigm(xi)] = wi × αm
Zm Zm e sinon.

Sortie c’est le signe de la combinaison linéaire

M
X
ĝM (x) = sign αmgm(x)
m=1

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 16

 Remarques
Ajustement L’étape 1 dépend évidemment des règles faibles choisies
▶ En général on cherche à minimiser ϵm
▶ Si on ne peut pas avoir de poids (arbres CART), on tire n valeurs (avec remise)
de l’échantillon, suivant les poids wi
Constante de normalisation pour que la somme des wi reste 1. calcul de Zm :
n
X h i
Zm = wi e−αm 1{yi=gm(xi)} + eαm 1{yi̸=gm(xi)}
i=1
p p p
= (1 − ϵm) ϵm/(1 − ϵm) + ϵm (1 − ϵm)/ϵm = 2 (1 − ϵm)ϵm.

Règle faible Elles ne doivent pas être trop faibles... On demande ϵm = 0.5 − γm,
avec γm ≥ γ
Erreur empirique d’apprentissage Freund & Shapire ont montré que

n
" M
#
1 X
2
X
Ln(ĝM ) = 1yi̸=ĝM (xi) ≤ exp −2 γm ≤ exp(−2M γ²)
n i=1 i=1

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 17

 Erreur de généralisation

Définition C’est l’erreur moyenne attendue sur un échantillon de test

L(ĝM ) = P(Y ̸= ĝM (X))

Borne obtenue par Freund & Shapire

r !
MV
L(ĝM ) ≤ Ln(ĝM ) + O ,
n

où V est la dimension de Vapnik-Chervonenkis de la famille de classifieurs faibles (3

dans l’exemple simple)
Interprétation Il peut y avoir du sur-ajustement
▶ si M est trop grand par rapport à n
▶ d’autant plus que V est grande (elle est grande si les règles peuvent être très
complexes)

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 18

 Problèmes de sur-ajustement (rappel)

Qu’est-ce que c’est ? C’est ce qui se passe quand en complexifiant le modèle l’erreur
d’apprentissage baisse, alors que l’erreur de généralisation se remet à augmenter.

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 19

 Dimension de Vapnik-Chervonenkis

Qu’est-ce que c’est ? C’est une mesure de la capacité d’un algorithme de classifica-
tion statistique.
▶ cardinal du plus grand ensemble de points que l’algorithme peut pulvériser
Pulveriser ? ? Un modèle de classification fθ pulvérise un ensemble de données
E = (x1, x2, . . . , xn) si, pour tout étiquetage de E, il existe θ tel que fθ ne fasse
aucune erreur dans l’évaluation de cet ensemble de données.
Exemple Une droite en dimension 2
On peut pulvériser 3 points Mais pas 4 points !

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 20

 Dimension de Vapnik-Chervonenkis (suite)

Conséquence un modèle de dimension VC trop haute risque le sur-apprentissage par

un modèle complexe trop adapté aux données d’apprentissage
Exemple Ici la ligne verte représente un modèle qui fait du sur-ajustement, la noire
est meilleure.

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 21

 SAMME : AdaBoost multi-classes

Principe On ne prédit plus une variable binaire mais y ∈ {1, . . . , K}

SAMME ? Stagewise Additive Modeling using a Multi-class Exponential loss function

Entrée Les éléments nécessaires sont

▶ un échantillon (x1, y1), (x2, y2), . . . , (xn, yn)
▶ un ensemble de règles faibles meilleures que le hasard

1
P (h(x) = y) ≥ + γ, γ > 0
K
▶ le nombre M d’itérations
Initialisation on calcule les poids de départ

1
wi ← , i = 1, . . . , n
n

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 22

 SAMME : AdaBoost multi-classes (suite)
Itération pour m = 1 à M
1. ajuster un classifieur faible gm(x) sur l’échantillon pondéré par les poids wi
2. calculer le taux d’erreur
n
X
ϵm ← wi1{yi̸=gm(xi)}
i=1

3. calculer le poids de l’itération m : αm ← log(1 − ϵm)/ϵm + log(K − 1)

4. mettre à jour les poids des observations
 
1
wi ← wi exp αm1 , Zm constante de normalisation.
Zm yi ̸=gm (xi )

Sortie elle est encore calculée à partir d’une combinaison linéaire

M
X
ĝM (x) = arg max α m 1
k gm (x)=k
m=1

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 23

 SAMME : AdaBoost multi-classes (suite)
Itération pour m = 1 à M
1. ajuster un classifieur faible gm(x) sur l’échantillon pondéré par les poids wi
2. calculer le taux d’erreur
n
X
ϵm ← wi1{yi̸=gm(xi)}
i=1
p
3. calculer le poids de l’itération m : αm ← log (1 − ϵm)/ϵm + log(K − 1)
4. mettre à jour les poids des observations
 
1
wi ← wi exp αm1 , Zm constante de normalisation.
Zm y i ̸
= g m ( x i )

Sortie elle est encore calculée à partir d’une combinaison linéaire

M
X
ĝM (x) = arg max α m 1
k gm (x)=k
m=1

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 24

 Adaboost en R avec adabag

Plusieurs packages mais tous n’implémentent pas la version originale (adaboost.M1 ).

▶ le plus rapide : fastAdaboot (écrit en C++), mais fonctionnalités assez basiques
▶ on choisit adabag qui implémente Adaboost et le bagging
Apprendre un modèle on récupère un objet de classe boosting
object <- boosting(formula, data, boos = TRUE,
mfinal = 100, control,...)

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 25

 Adaboost en R avec adabag

Plusieurs packages mais tous n’implémentent pas la version originale (adaboost.M1 ).

▶ le plus rapide : fastAdaboot (écrit en C++), mais fonctionnalités assez basiques
▶ on choisit adabag qui implémente Adaboost et le bagging
Apprendre un modèle on récupère un objet de classe boosting
object <- boosting(formula, data, boos = TRUE,
mfinal = 100, control,...)

▶ Question : qu’est-ce que cela veut dire ?

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 26

 Parenthèse : description des fonctions R
Exemple on obtient avec ?boosting ou help(boosting) la description suivante
object <- boosting(formula, data, boos = TRUE,
mfinal = 100, control,...)
Comment lire ça ?
▶ les paramètres peuvent avoir une valeur par défaut (TRUE pour boos)
Seuls les deux premiers paramètres sont obligatoires ici
▶ Si la valeur par défaut d’un paramètre vous convient, pas la peine de le spécifier
▶ si on ne donne pas le nom, ce sera le premier, le second. . .
▶ on peut abréger le nom si ce n’est pas ambigu (mfi pour mfinal, par ex.)
▶ en général, on ne donne que quelques paramètres
▶ La signification des paramètres est précisée dans l’aide, c’est utile de la lire
Formes équivalentes on écrit comme on préfère
object <- boosting(Y~., mesdonnees)
object <- boosting(Y~., mesdonnees, TRUE)
object <- boosting(formula = Y~.,
data = mesdonnees, boos = T)
object <- boosting(dat = mesdonnees, for = Y~.)

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 27

 Adaboost en R avec adabag

Apprendre un modèle on récupère un objet de classe boosting

object <- boosting(formula, data, boos = TRUE,
mfinal = 100, control,...)
▶ formula : en général « Y~. » si Y est la variable qu’on veut prédire (doit être
un facteur)
▶ data : les données d’entraı̂nement
▶ boos : quand TRUE (le défaut), on utilise un échantillon de bootstrap en utilisant
le poids de chaque observation ; sinon, on utilise l’ensemble des données associées
à leur poids.
▶ mfinal : nombre total d’arbres M
Choix des arbres on utilise le paramètre control de la fonction boosting
..., control=rpart.control(maxdepth=10, ...)
▶ maxdepth contrôle la profondeur totale des arbres
▶ pour les autres arguments, voir la documentation de rpart.control.

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 28

 Adaboost en R avec adabag (suite)

Prédiction avec la fonction predict.boosting (on peut utiliser juste predict

parce que le premier argument est de classe boosting)
pred <- predict(object, newdata,
newmfinal=length(object$trees), ...)
▶ object est retourné par la fonction boosting
▶ newdata contient les données à tester
▶ newmfinal est le nombre d’arbres du modèle à utiliser (pour utiliser un modèle
plus léger)
Résultat pred contient notamment les champs
▶ class : la classe prédite pour chaque individu de newdata
▶ prob : la probabilité a posteriori de chaque classe pour chaque individu
▶ error : l’erreur moyenne de prédiction
▶ confusion : la matrice de confusion

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 29

 Adaboost en R avec adabag (fin)

Influence du nombre d’arbres on considère tous les modèles intermédiaires qui ont
été construits
evol <- errorevol(object, newdata, newmfinal=mfinal)
▶ object est retourné par la fonction boosting
▶ newdata contient les données à tester
▶ newmfinal est le nombre d’arbres à utiliser (tous les arbres par défaut)
On affiche avec la fonction plot.errorevol
plot(x, y = NULL, ...)
▶ x est un objet retourné par errorevol, par exemple sur les données de test
▶ y (optionnel) est un objet retourné par errorevol, typiquement sur les données
d’apprentissage
Importance des variables avec la fonction importanceplot
importanceplot(object, ...)

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 30

 I Introduction au cours
II AdaBoost
III Modélisation additive linéaire
IV Gradient Boosting
V XGBoost
 Modélisation additive linéaire

Contexte Presque le même que pour AdaBoost

▶ On a toujours une variable y ∈ {−1, 1} à inférer à partir de règles faibles.
▶ Cette fois-ci, on se donne un fonction de coût (ou déviance) L(y, g) que l’on
cherche à minimiser
Approche On modélise à chaque fois le résidu produit par la solution précédente, on
a donc
M
X
ĝM (x) = βmgm(x) = ĝM −1(x) + βM gM (x)
m=1

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 32

 Algorithme Forward staging additive modeling

Entrée Les éléments nécessaires sont

▶ un échantillon (x1, y1), (x2, y2), . . . , (xn, yn)
▶ une fonction de coût L(y, g)
▶ un ensemble de règles faibles
▶ le nombre M d’itérations
Initialisation ĝ0(x) = 0.
Itération pour m = 1 à M
1. choisir une règle faible gm et un coefficient βm qui minimise
n
X

L yi, ĝm−1(xi) + βmgm(x)
i=1

2. ĝm(x) = ĝm−1(x) + βmgm(x)

Sortie la prédiction est sign ĝM (x)

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 33

 Les marges

Qu’est-ce que c’est ? Si on a une prédiction sign g(x) de la variable binaire y, alors
la marge est la valeur yg(x)
Propriétés
▶ la marge est positive si l’objet est bien classifié, et négative sinon
▶ une grande marge positive est meilleure : elle sera peu sensible au bruit
Conséquences pour la fonction de coût
▶ elle doit pénalise les marges négatives. . .
▶ . . . mais si elle les pénalise trop, elle sera fragile par rapport aux données
d’entraı̂nement avec des labels faux
Pour Adaboost avec la package R adabag, on peut les calculer et les représenter
avec les fonctions margins et plot.margins
plot(margins(object))

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 34

 Fonctions de coût pour la classification

Exponentielle L(y, g) = exp(−yg)

▶ On peut prouver qu’on retrouve Ada-

Boost ! !
▶ pourtant l’idée est très différente
Logistique déviance binomiale

L(y, g) = log(1 + exp(−2yg))

▶ Similaire à AdaBoost a priori
▶ Moins sensible aux observations mal
classifiées

Quadratique L(y, g) = (y − g)2, avec y ∈ R

▶ pas bon, puisque le coût devient plus important quand yg est grand
▶ la fonction de coût doit être décroissante

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 35

 Fonction de coût pour la régression

Qu’est-ce que c’est ? C’est le même

problème, sauf que maintenant y ∈ R
Quadratique L(y, g) = 12 (y − g)2
▶ sensible aux valeurs aberrantes
(outliers)
Linéaire L(y, g) = |y − g|
▶ Plus robuste, mais moins précis pour
les petites erreurs

Huber Utilisé pour les statistiques robustes

(
(y − g)2 si |y − g| ≤ δ
L(y, g) =
2δ|y − g| − δ 2 sinon

▶ combine les bonnes propriétés des deux fonctions précédentes

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 36

 I Introduction au cours
II AdaBoost
III Modélisation additive linéaire
IV Gradient Boosting
V XGBoost
 Principe

Descente de gradient en analyse réelle

▶ on chercher le minimum d’une fonction convexe u : R 7→ R,
▶ on fixe le paramètre λ > 0 et on utilise la récurrence

xm = xm−1 − λu′(xm−1)

Adaptation à notre problème

▶ Ici, on n’a plus un gradient sur une fonction, mais un gradient fonctionnel
▶ On cherche une fonction minimale, pas un point
▶ il est facile de calculer le gradient aux points d’observation où y est connu
▶ par contre, on ne sait pas le faire aux autres points
Idée on va utiliser une règle faible pour modéliser le gradient

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 38

 Algorithme de Gradient Boosting

Entrée Les éléments nécessaires sont

▶ un échantillon (x1, y1), (x2, y2), . . . , (xn, yn)
▶ une fonction de coût L(y, g)
▶ un ensemble de règles de régression faibles
▶ le nombre M d’itérations, le coefficient λ
Pn
Initialisation ĝ0(x) = arg ming i=1 L(yi, g(xi)).
Itération pour m = 1 à M
1. calculer le gradient aux points d’observation
 
∂L(y, g)
ṙim =
∂g y=yi ,g=ĝm−1 (xi )

2. ajuster une règle faible de régression gm sur l’ensemble (x1, ṙ1m), . . . , (xn, ṙnm)
3. ĝm(x) = ĝm−1(x) − λgm(x)
Sortie ĝM (x) pour une régression, sign ĝM (x) pour une classification

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 39

 Calcul des gradients

Contexte coût ∂L(y, g)/∂g

1
Régression 2 (g − y)2 g−y
|g − y| sign(g − y)
(
g−y si |y − g| ≤ δ
Huber
δ sign(g − y) sinon
2y
Classification Logistique −
1 + exp(2yg)

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 40

 Coefficient de régularisation

Qu’est-ce que c’est ? il réduit l’influence des nouveaux termes durant l’itération
Utilisation le coefficient de régularisation (shrinkage) λ fixe le risque d’apprentissage
▶ λ petit (≪ 1) : l’algorithme est plus lent mais limite le sur-apprentissage
▶ plus λ est petit, plus le nombre d’itérations M doit être grand
▶ λ vaut 1 pour Adaboost
Autres paramètres importants Il y a finalement assez peu de paramètres
▶ Nombre d’itérations M
▶ profondeur des arbres de décision : un stump est très rapide à calculer, mais un
arbre plus profond est plus précis

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 41

 Cas multi-classe

Modèle on écrit la probabilité d’être dans la classe k ∈ {1, . . . , K} comme

K
e gk (x ) X
pk (x) = PK , avec gℓ(x)=0.
ℓ=1 e gℓ (x ) ℓ=1

Adaptation de l’algorithme on calcule les fonctions ĝm = (ĝm1, . . . , ĝmK ) en

même temps.
Coût la fonction de coût et son gradient pour la k-ième composante sont

K
X ∂L(y, g)
L(y, g) = − 1{y=k} log pk (x), = 1{y=k} − pk (x)
∂gk
k=1

Sortie on calcule les pk (x) correspondant à ĝM et la prédiction est arg maxk pk (x).

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 42

 Stochastic Gradient Boosting

Idée on n’utilise qu’une parte des données pour calculer les estimateurs gm
▶ À chaque fois qu’on doit estimer le gradient, on sélectionne aléatoirement sans
remplacement une fraction f des données
▶ L’algorithme n’est donc plus déterministe !
Propriétés le gain est double :
▶ exécution plus rapide
▶ meilleure précision, par réduction de la variance et du sur-ajustement
Valeur typique Friedman (2002), propose une valeur de f = 0.4 pour des petits
jeux de données (≈ 500) et f = 0.6 pour une taille modérée (≈ 5000)

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 43

 Gradient boosting en R avec gbm

Pourquoi gbm
▶ implemente le gradient boosting standard
▶ gbm est un bon équilibre entre simplicité et fonctionnalité
Modélisation
object <- gbm(formula, distribution = "bernoulli", data, n.trees = 100,
interaction.depth = 1, shrinkage = 0.1,
bag.fraction = 0.5, train.fraction = 1.0, ...)
▶ formula, data : comme pour adaboost
▶ distribution : "bernoulli" pour le coût logistique, "adaboost" pour
l’exponentiel, "huberized"
▶ n.trees : nombre d’itérations M
▶ interaction.depth : profondeur des arbres (stumps : 1)
▶ shrinkage : paramètre de régularisation λ
▶ bag.fraction : fraction f de données à utiliser (gradient boosting stochastique)
▶ train.fraction : proportion des données à utiliser pour l’apprentissage
▶ et d’autres paramètres à voir dans l’aide

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 44

 Gradient boosting en R avec gbm (suite)

Prédiction avec predict.gbm

pred <- predict(object, newdata, n.trees, ...)
▶ model : l’objet retourné par gbm
▶ newdata : les données de test
▶ n.trees : le nombre d’arbres à utiliser. On peut spécifier un vecteur de tailles
pour tout calculer à la fois.
▶ valeur retournée : liste de prédictions, positif pour valeur 1, négatifs sinon

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 45

 gbm : choix du nombre d’arbres
Méthode on cherche le meilleur sous modèle d’un modèle trop fourni
Fonction gbm.perf Calcule le nombre d’arbres idéal et trace des graphes d’erreur
best.trees <- gbm.perf(model, plot.it=TRUE, method)
▶ model : l’objet retourné par gbm
▶ plot.it : si vrai, trace un plot de l’erreur sur l’échantillon de apprentissage
(noir) et sur l’échantillon de test (rouge)
▶ method : indique la méthode utilisée pour calculer le nombre optimal d’itérations.
"OOB" calcule l’estimé out-of-the-bag et "test" utilise la base de test
▶ valeur retournée : nombre optimal d’arbres

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 46

 gbm : importance relative des variables
Méthode On ne l’expliquera pas ici, mais elle est décrite dans Friedman (2001).
Importance des variables Calcule et représente l’importance relative des variables
dans la fonction de coût
summary(object, cBars, n.trees, plotit = TRUE, ...)
▶ object : l’objet retourné par gbm
▶ cBars : nombre des plus grandes valeurs à retenir (défaut : toutes)
▶ n.trees : le nombre d’arbres à utiliser (défaut : tous ceux du modèle)
▶ plotit : si TRUE, représenter les barres graphiquement
▶ valeur retournée : une table des influences relatives.

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 47

 I Introduction au cours
II AdaBoost
III Modélisation additive linéaire
IV Gradient Boosting
V XGBoost
 eXtreme Gradient Boosting

Historique c’est une variante du gradient boosting qui a été utilisée par beaucoup de
gagnants des compétitions en apprentissage
Particularités
▶ utilisation de l’algorithme de Newton-Raphson au lieu du gradient,
▶ pénalisation de la complexité des arbres,
▶ paramètre de randomisation,
▶ contraction proportionnelle du poids des feuilles.
Implémentation cet algorithme est utilisable de manière efficace dans python, R,
Julia et Scala.

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 49

 Principe

Approximation on suppose qu’on a une fonction ĝm−1(x) et on cherche à minimiser

n
X

L yi, ĝm−1(xi) + gm(xi)
i=1

que l’on développe au second ordre comme

n  
X 1 2
L yi, ĝm−1(xi)) + ṙimgm(xi) + r̈imgm (xi) ,
i=1
2

avec
2
   
∂L(y, g) ∂ L(y, g)
ṙim = et r̈im = .
∂g y=yi ,g=ĝm−1 (xi ) ∂g 2 y=yi ,g=ĝm−1 (xi )

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 50

 Évaluation et optimisation d’arbres
Paramétrisation de l’arbre si gm est un arbre à T feuilles et w1, . . . , wT les scores
de chaque feuille, on note

gm(x) = wq(x), pour w ∈ RT , q : En 7→ {1, . . . , T }

PT
Pénalisation on ajoute un coût γT + 12 λ 2
j=1 wj , qui décourage les arbres complexes
Forme quadratique en combinant les deux termes et en enlevant les termes constants,
on a un objectif de la forme
T  
X 1
Ṙjmwj + R̈jm + λ wj2 ,


obj = γT +
j=1
2

qui est minimal pour

T 2
Ṙjm 1 X Ṙjm
∗
wj = − , obj∗ = γT − .
R̈jm + λ 2 j=1 R̈jm + λ

Utilisation sélection du meilleur arbre par un algorithme glouton.

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 51
 Utilisation de XGBoost en R

Modélisation
object <- xgboost(data, label, params=list(), nrounds,
verbose = 1 ...)
▶ data : les données d’apprentissage
▶ label : les réponses souhaitées (0 ou 1 pour une classification simple)
▶ params : les paramètres de la méthode (dans une liste).
▶ objective : la fonction de coût. Le défaut est "reg:squarederror", pour
une classification on prend "binary:logistic"
▶ max depth : profondeur maximale pour les arbres (défaut : 6)
▶ nthread : nombre de processus à lancer en parallèle (par défaut, tous les
cœurs disponibles)
▶ et d’autres paramètres à voir dans l’aide
▶ nrounds : nombre maximum d’itérations
▶ verbose : si 1, donne des informations sur la performance
▶ et d’autres paramètres à voir dans l’aide

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 52

 Utilisation de XGBoost en R (suite)

Prédiction avec predict.xgb.Booster

newlabel <- predict(object, newdata, ...)
▶ object : l’objet retourné par xgboost
▶ newdata : les données de test
▶ et d’autres paramètres à voir dans l’aide
Résultat
▶ les valeurs estimées pour une régression
▶ pour une classification binaire, un vecteur de valeurs entre 0 et 1
newlabel > 0.5 donne une liste de valeurs binaires

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 53

 Épilogue : le choix des paramètres

Ça dépend Les différents auteurs de packages ont chacun leur approche !
gbm Par défaut on utilise des stumps, λ = 0.001 et M = 100. Dans la documentation,
l’auteur dit « en pratique je mets λ à la plus petite valeur possible et je sélectionne M
par validation croisée. La performance est meilleure quand λ est le plus petit possible,
avec une utilité marginale décroissante quand λ décroı̂t. (...) Je vise en général 3 000 à
10 000 itérations avec un λ entre 0.01 et 0.001. »
xgboost Par défaut, les arbres sont de profondeur maximale 6 et λ = 0.3. Il n’y a
pas de valeur par défaut pour M .
Owen Zhang (vainqueur de la compétition « Avito » de Kaggle) propose
▶ M = 10 à 100, selon la taille des données
▶ λ = 2M à 10

▶ profondeur maximale des arbres parmi [4, 6, 8, 10].

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2023-2024. 54