Introduction au boosting

Jean-Marc Lasgouttes, Inria de Paris

[Link]@[Link]

[Link]

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

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

 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
▶ 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 2021-2022. 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 2021-2022. 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 2021-2022. 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 2021-2022. 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 2021-2022. 7

 Exemple simple

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2021-2022. 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 2021-2022. 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 2021-2022. 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 2021-2022. 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 2021-2022. 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 2021-2022. 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 2021-2022. 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 2021-2022. 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 2021-2022. 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 X
Ln(ĝM ) = 1yi̸=ĝM (xi) ≤ exp −2 γ 2m ≤ exp(−2M γ²)
n i=1 i=1

Mastère spécialisé ESD — Méthodes d’arbres en apprentissage statistique — année 2021-2022. 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 2021-2022. 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 2021-2022. 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 2021-2022. 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 2021-2022. 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 2021-2022. 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 2021-2022. 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 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 2021-2022. 24

 Adaboost en R avec adabag

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

▶ la 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
model <- 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 : faire du bootstrap (pas sûr que ce soit utile)
▶ mfinal : nombre total d’arbres M

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

 Adaboost en R avec adabag (suite)

Choix des arbres on utilise le paramètre control de la fonction boosting

..., control=[Link](maxdepth=10, ...)
▶ maxdepth contrôle la profondeur totale des arbres
▶ pour les autres arguments, voir la documentation de [Link].
Prédiction
pred <- predict(object, newdata)
▶ object est retourné par la fonction boosting
▶ newdata contient les données à tester
Le résultat pred contient notamment les champs
▶ 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 2021-2022. 26

 Adaboost en R avec adabag (suite)

Influence du nombre d’arbres on considère tous les modèles intermédiaires qui ont
été construits
evol <- errorevol(object, newdata)
▶ object est retourné par la fonction boosting
▶ newdata contient les données à tester
Affichage
[Link](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

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

 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 2021-2022. 29

 Algorithme Forward staging additive modeling

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 ĝ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 2021-2022. 30

 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

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 2021-2022. 31

 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 2021-2022. 32

 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 2021-2022. 34

 Algorithme de Gradient Boosting

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

▶ un échantillon (x1, y1), (x2, y2), . . . , (xn, yn)
▶ 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(y, g).
Itération pour m = 1 à M
1. calculer l’opposé du gradient aux points d’observation
 
∂L(y, g)
rim = −
∂g y=yi ,g=ĝm−1 (xi )

2. ajuster une règle faible de régression gm sur l’ensemble (x1, r1m), . . . , (xn, rnm)
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 2021-2022. 35

 Calcul des gradients

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

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

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

 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 2021-2022. 37

 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 2021-2022. 38

 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 0.4 pour des petits jeux de
données (≈ 500) et 0.6 pour une taille modérée (≈ 5000)

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

 Gradient boosting en R avec gbm

Pourquoi gbm
▶ implemente le gradient boosting standard
▶ gbm est un bon équilibre entre simplicité et fonctionnalité
Modélisation
model <- gbm(formula, distribution = "bernoulli", data, [Link] = 100,
[Link] = 1, shrinkage = 0.001,
[Link] = 0.5, [Link] = 1.0, ...)
▶ formula, data : comme pour adaboost
▶ distribution : "bernoulli" pour le coût logistique, "adaboost" pour
l’exponentiel, "huberized"
▶ [Link] : nombre d’itérations M
▶ [Link] : profondeur des arbres (stumps : 1)
▶ shrinkage : paramètre de régularisation λ
▶ [Link] : fraction f de données à utiliser (gradient boosting stochastique)
▶ [Link] : 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 2021-2022. 40

 Gradient boosting en R avec gbm (suite)

Prédiction predict(model, newdata, [Link], ...)

▶ model : l’objet retourné par gbm
▶ newdata : les données de test
▶ [Link] : 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 2021-2022. 41

 gbm : choix du nombre d’arbres
Méthode on cherche le meilleur sous modèle d’un modèle trop fourni
Fonction [Link] Calcule le nombre d’arbres idéal et trace des graphes d’erreur
[Link](model, [Link]=TRUE, method)
▶ model : l’objet retourné par gbm
▶ [Link] : 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

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

 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, [Link], plotit = TRUE, ...)
▶ object : l’objet retourné par gbm
▶ cBars : nombre des plus grandes valeurs à retenir (défaut : toutes)
▶ [Link] : 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 2021-2022. 43

 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 2021-2022. 45

 Principe

Approximation on suppose qu’on a un 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) 1 (2) 2
L yi, ĝm−1(xi)) + rim gm(xi) + rim gm (xi) ,
i=1
2

avec
2
   
(1) ∂L(y, g) (2) ∂ L(y, g)
rim = et rim = .
∂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 2021-2022. 46

 Évaluation et optimisation d’arbres
Paramétrisation de l’arbre si gm est un arbre à T feuilles, 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) 1 (2)
Rjmwj + Rjm + λ wj2 + γT,


obj =
j=1
2

qui est minimal pour

h i2
(1) (1)
Rjm 1 Rjm
∗
wj∗ =− (2)
, obj = − (2) + γT.
Rjm +λ 2R + λ
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 2021-2022. 47

 Utilisation de XGBoost en R

Modélisation
model <- 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
▶ 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 2021-2022. 48

 Utilisation de XGBoost en R (suite)

Prédiction
newlabel <- predict(model, newdata, ...)
▶ model : 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 2021-2022. 49

 É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 2021-2022. 50