1 Le boosting

1.1 Introduction

Le fondement théorique du boosting est un article de de 1990 (Shapire (1990)) qui a démontré théoriquement que, sous certaines conditions, il est possible de transformer un modèle prédictif peu performant en un modèle prédictif très performant. Plus précisément, cet article prouve que s’il est possible de construire un modèle simple dont les prédictions ne sont que légèrement meilleures que le hasard (appelé weak learner), alors il est possible de construire un modèle ayant un pouvoir prédictif arbitrairement élevé (appelé strong learner) en améliorant progressivement ce modèle simple. Le boosting est donc une méthode qui combine une approche ensembliste reposant sur un grand nombre de modèles simples avec un entraînement séquentiel: chaque modèle simple (souvent des arbres de décision peu profonds) tâche d’améliorer la prédiction globale en corrigeant les erreurs des prédictions précédentes à chaque étape. Bien qu’une approche de boosting puisse en théorie mobiliser différentes classes de weak learners, en pratique les weak learners utilisés par les algorithmes de boosting sont presque toujours des arbres de décision.

En termes plus techniques, les différentes variantes du boosting partagent toutes trois caractéristiques communes:

• Ils visent à trouver une approximation \(\hat{F}\) d’une fonction inconnue \(F^{\ast}: \mathbf{x} \mapsto y\) à partir d’un ensemble d’entraînement \((y_i, \mathbf{x_i})_{i= 1,\dots,n}\);

• Ils supposent que la fonction \(F^{\ast}\) peut être approchée par une somme pondérée de modèles simples \(f\) de paramètres \(\theta\): \[ F\left(\mathbf{x}\right) = \sum_{m=1}^M \beta_m f\left(\mathbf{x}, \mathbf{\theta}_m\right) \]

• Ils reposent sur une modélisation additive par étapes (forward stagewise additive modeling), qui décompose l’entraînement de ce modèle complexe en une séquence d’entraînements de petits modèles. Chaque étape de l’entraînement cherche le modèle simple \(f\) qui améliore la puissance prédictive du modèle complet, sans modifier les modèles précédents, puis l’ajoute de façon incrémentale à ces derniers:

\[ F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \hat{\beta}_m f(\mathbf{x}_i, \mathbf{\hat{\theta}_m}) \]

METTRE ICI UNE FIGURE EN UNE DIMENSION, avec des points et des modèles en escalier qui s’affinent.

1.2 Les premières approches du boosting

1.2.1 Le boosting par repondération: Adaboost

Dans les années 1990, de nombreux travaux ont tâché de proposer des mise en application du boosting (Breiman (1998), Grove and Schuurmans (1998)) et ont comparé les mérites des différentes approches. Deux approches ressortent particulièrement de cette littérature: Adaboost (Adaptive Boosting, Freund and Schapire (1997)) et la Gradient Boosting Machine (Friedman (2001)). Ces deux approches reposent sur des principes très différents.

Le principe d’Adaboost consiste à pondérer les erreurs commises à chaque itération en donnant plus d’importance aux observations mal prédites, de façon à obliger les modèles simples à se concentrer sur les observations les plus difficiles à prédire. Voici une esquisse du fonctionnement d’AdaBoost:

• Un premier modèle simple est entraîné sur un jeu d’entraînement dans lequel toutes les observations ont le même poids.
• A l’issue de cette première itération, les observations mal prédites reçoivent une pondération plus élevée que les observations bien prédites, et un deuxième modèle est entraîné sur ce jeu d’entraînement pondéré.
• Ce deuxième modèle est ajouté au premier, puis on repondère à nouveau les observations en fonction de la qualité de prédiction de ce nouveau modèle.
• Cette procédure est répétée en ajoutant de nouveaux modèles et en ajustant les pondérations.

L’algorithme Adaboost a été au coeur de la littérature sur le boosting à la fin des années 1990 et dans les années 2000, en raison de ses performances sur les problèmes de classification binaire. Il a toutefois été progressivement remplacé par les algorithmes de gradient boosting mis au point quelques années plus tard.

1.2.2 L’invention du boosting boosting : la Gradient Boosting Machine

La Gradient Boosting Machine (GBM) propose une approche assez différente: elle introduit le gradient boosting en reformulant le boosting sous la forme d’un problème d’optimisation qui se résout par une approche itérative de descente de gradient. Cette approche repose entièrement sur la notion de fonction de perte, qui mesure l’écart entre la variable-cible et la prédiction du modèle. La mécanique de la Gradient Boosting Machine est présentée de façon formelle dans l’encadré ci-dessous; en voici une présentation intuitive:

• Le modèle global est initialisé à partir des données d’entraînement. A ce stade, le modèle prédit en général la moyenne de la variable-cible pour toutes les observations.

• Première itération de boosting:

  • On calcule la dérivée partielle (gradient) de la fonction de perte par rapport à la prédiction pour chaque observation de l’ensemble d’entraînement. Cette dérivée partielle est parfois appelée pseudo-résidu. L’opposé de ce gradient indique à la fois dans quelle direction et dans quelle ampleur la prédiction devrait être modifiée afin de réduire la perte.
  • Un premier arbre est entraîné à prédire l’opposé du gradient de la fonction de perte.
  • Cet arbre est ajouté au modèle global (après multiplication par un facteur d’échelle).

• Deuxième itération de boosting: on calcule à nouveau la dérivée partielle de la fonction de perte par rapport aux nouvelles prédictions du modèle global, puis un deuxième arbre est entraîné à prédire l’opposé du gradient de la fonction de perte, et enfin cet arbre est ajouté au modèle global.

• Cette procédure est répétée en ajoutant de nouveaux modèles et en recalculant le gradient à chaque étape.

• La qualité du modèle final est évaluée sur un ensemble de test.

L’approche de gradient boosting proposée par Friedman (2001) présente deux grands avantages. D’une part, toute la mécanique du gradient boosting est indépendante de la fonction de perte choisie et de la nature du problème modélisé. Autrement dit, cette approche peut être utilisée avec n’importe quelle fonction de perte différentiable, ce qui permet d’appliquer le gradient boosting à de multiples problèmes (régression, classification binaire ou multiclasse, learning-to-rank…). D’autre part, le gradient boosting offre souvent des performances comparables ou supérieures aux autres approches de boosting. Le gradient boosting d’arbres de décision (Gradient boosted Decision Trees - GBDT) est donc devenue l’approche de référence en matière de boosting: toutes les implémentations modernes du gradient boosting comme scikit-learn, XGBoost, LightGBM, et CatBoost sont des extensions et améliorations de la Gradient Boosting Machine.

Présentation formelle de la Gradient Boosting Machine

On dispose d’un jeu de données \({(x_i, y_i)}_{i=1}^n\) avec \(x_i \in \mathbb{R}^m\) et une cible \(y_i\). On définit une fonction de perte \(l\) qui mesure la distance entre la prédiction \(\hat{y}\) et la vraie valeur \(y\). Elle présente généralement les propriétés suivantes: elle est convexe et dérivable deux fois, et atteint son minimum lorsque \(\hat{y} = y\). On veut entraîner un modèle comprenant \(m\) arbres, chacun étant défini par les paramètres \(\mathbf{a_m}\) (règles de décision et valeurs des feuilles terminales):

\[ \hat{y}_{i} =F\left(\mathbf{x}_i\right) = \sum_{k=1}^{K} f_k\left(\mathbf{x}_i\right) \]

Procédure de construction du modèle:

1. Initialiser le modèle avec \(F_0\left(\mathbf{x}\right) = f_0\left(\mathbf{x}\right) = \frac{1}{n}\sum_{i=1}^n y_i\).

2. Pour \(m = 1, \dots, M:\)

   1. Calculer le gradient (les pseudo-résidus) à l’issue des \(m-1\) étapes précédentes: \(g_{im} = \frac{\partial l(y_i, F_{m-1}\left(\mathbf{x}\right))}{\partial F_{m-1}\left(\mathbf{x}\right)}\)

   2. Entraîner le \(m\)-ième weak learner: on cherche l’arbre \(f_m\) qui prédit le mieux l’opposé du gradient de la fonction de perte: \(\mathbf{\hat{a}_m} = \underset{\mathbf{a}}{\arg \min} \sum_{i=1}^n \left(- g_{im} - f_m\left(\mathbf{x}_i, \mathbf{a}\right)\right)^2\)

   3. Mettre à jour le modèle global: \(F_m\left(\mathbf{x}\right) = F_{m-1}\left(\mathbf{x}\right) + \rho f_m\left(\mathbf{x}_i, \mathbf{\hat{a}_m}\right)\) avec \(\rho\) le taux d’apprentissage (learning rate) dont la raison d’être est présentée dans la section Section 1.4.

1.3 La mécanique du gradient boosting

La méthode de gradient boosting proposée Friedman (2001) a fait l’objet de multiples implémentations, parmi lesquelles XGBoost (Chen and Guestrin (2016)), LightGBM (Ke et al. (2017)), CatBoost (Prokhorenkova et al. (2018)) et scikit-learn. Ces implémentations sont proches les unes des autres, et ne diffèrent que sur des points relativement mineurs. En revanche, elles s’éloignent quelque peu de la formulation initiale de la Gradient Boosting Machine, afin d’optimiser la construction des arbres. Bien comprendre la mécanique interne de ces implémentations s’avère important en pratique, notamment pour appréhender le rôle des multiples hyperparamètres. Cette section présente donc la mécanique d’ensemble de ces implémentations, en s’appuyant sur l’implémentation proposée par XBGoost.¹

1.3.1 Le modèle à entraîner

On dispose d’un jeu de données \({(x_i, y_i)}_{i=1}^n\) avec \(x_i \in \mathbb{R}^m\) et une cible \(y_i\). On veut entraîner un modèle global qui soit une somme de \(K\) arbres de régression ou de classification: \(\hat{y}_i = F\left(\mathbf{x}_i\right) = \sum_{k=1}^K f_k(x_i)\). On rappelle que chaque arbre \(f\) est défini par trois paramètres:

• sa structure qui est une fonction \(q: \mathbb{R}^m \rightarrow \{1, \dots, T\}\) qui à un vecteur \(\mathbf{x}\) de dimension \(m\) associe une feuille terminale de l’arbre;cette structure est définie par l’ensemble des règles de décision de l’arbre;
• son nombre de feuilles terminales \(T\);
• les prédictions figurant sur ses feuilles terminales \(\mathbf{w}\in \mathbb{R}^T\) (appelées poids ou weights).

Le modèle complet est impossible à entraîner en une seule fois, car c’est un problème trop complexe. Le principe du boosting consiste donc à construire le modèle complet de façon itérative, par ajout successif d’arbres. À l’itération \(t\), on ajoute un nouvel arbre \(f_t\) pour améliorer la prédiction actuelle \(\hat{y}_i^{(t-1)}\). Le modèle devient: \[ \hat{y}_i^{(t)} = \hat{y}_i^{(t-1)} + f_t(x_i). \]

L’objectif de l’itération \(t\) est donc de trouver le nouvel arbre \(f_t(x_i)\) qui minimise la fonction-objectif. Pour éviter le sur-ajustement, l’algorithme XGBoost utilise une fonction-objectif qui comporte à la fois une fonction de perte, et un terme de régularisation:

\[ L^{(t)} = \underbrace{\sum_{i=1}^n \ell\left(y_i,\;\hat{y}_i^{(t-1)} + f_t(x_i)\right)}_{\substack{\text{Perte sur les} \\ \text{observations}}} + \underbrace{\sum_k \Omega(f_{k})}_{\substack{\text{Fonction de} \\ \text{régularisation}}}\,\,\text{avec}\,\,\Omega(f) = \gamma T + \frac{1}{2} \lambda \sum_{k=1}^K \sum_{j=1}^{T_k} w_j^2 \tag{1}\]

Dans cette expression:

• La fonction de perte \(\ell\) mesure la distance entre la prédiction \(\hat{y}\) et la vraie valeur \(y\) (exemples: erreur quadratique moyenne, erreur absolue moyenne, perte d’entropie croisée binaire, etc.).
  
• Le terme de régularisation \(\Omega(f)\) pénalise la complexité de l’arbre \(f\) via deux termes: le terme \(\gamma\,T\) pénalise les arbres avec un grand nombre de feuilles (\(T\) élevé) et le terme \(\tfrac{1}{2} \lambda\sum_{j=1}^{T_t} w_j^2\) pénalise les arbres avec des poids élevés (\(w_j\) élevés en valeur absolue). Cette pénalisation privilégie les arbres plus « simples » (moins de feuilles, poids de feuilles plus petits) afin d’éviter le sur-ajustement (overfitting). \(\gamma\) et \(\lambda\) sont des hyperparamètres de régularisation qui contrôlent la complexité de l’arbre.

1.3.2 L’entraînement du modèle

1.3.2.1 Principe

A chaque étape de l’entraînement du modèle, l’algorithme de gradient boosting va construire un arbre en faisant deux choses:

1. Déterminer la structure de l’arbre en tenant compte de la régularisation (c’est-à-dire choisir les règles de décision qui définissent l’arbre);

2. Calculer la meilleure valeur \(w_j\)​ pour chaque feuille (c’est-à-dire la valeur qui minimise la fonction de perte).

La construction de l’arbre se fait selon une approche gloutonne, nœud après nœud: on divise les données d’entraînement en feuilles de plus en plus petites, tant que cela génère une réduction “suffisante” de la fonction de perte. Cette approche peut être résumée ainsi:

1. On part d’une feuille unique (l’arbre de profondeur 0) qui contient toutes les données d’entraînement.

2. Pour chaque feuille de l’arbre, on essaie de trouver un partitionnement optimal:

   • On teste toutes les règles de décision possibles (en faisant une boucle sur toutes les variables, et sur les différents seuils possibles).
   • Pour chaque règle de décision candidate, on calcule le gain associé (c’est-à-dire la réduction de la perte globale si l’on retient cette règle de décision).
   • Si la meilleure règle de décision apporte un gain suffisamment élevé, on crée deux nouvelles feuilles.

3. On répète le processus récursivement (en partant des feuilles nouvellement créées) jusqu’à :

   • soit atteindre les limites de complexité définies a priori (profondeur maximale de l’arbre, nombre maximal de feuilles, nombre minimal d’observations par feuille);
   • soit ne plus trouver de partitionnement intéressant (c’est-à-dire qui permette de réduire suffisamment la perte).

Les paragraphes qui suivent détaillent ce processus et les équations utilisées.

1.3.2.2 Étape 1: Faire apparaître le gradient de la fonction de perte

Pour simplifier la construction du \(t\)-ième arbre, XGBoost utilise une approximation de second ordre de la fonction de perte \(L^{(t)}\). Plus précisément, on fait un développement limité d’ordre 2 de \(l(y_i, \hat{y}_{i}^{(t-1)} + f_{t}(\mathbf{x}_i))\) au voisinage de \(\hat{y}_{i}^{(t-1)}\), en considérant que la prédiction du \(t\)-ième arbre \(f_{t}(\mathbf{x}_i)\) est un incrément de petite taille:

\[ \mathcal{L}^{(t)} \approx \sum_{i=1}^{n} [\underbrace{l(y_i, \hat{y}_{i}^{(t-1)})}_{\text{(A)}} + g_i f_t(\mathbf{x}_i)+ \frac{1}{2} h_i f^2_t(\mathbf{x}_i)] + \underbrace{\sum_{j=1}^{t-1}\Omega(f_j)}_{\text{(B)}} + \Omega(f_t) \]

avec

\[ g_i = \frac{\partial l(y_i, \hat{y}_i^{(t-1)})}{\partial\hat{y}_i^{(t-1)}} \;\;\text{et}\;\; h_i = \frac{\partial^2 l(y_i, \hat{y}_i^{(t-1)})}{{\partial \hat{y}_i^{(t-1)}}^2} \]

Les termes \(g_i\) et \(h_i\) désignent respectivement la dérivée première (le gradient) et la dérivée seconde (la hessienne) de la fonction de perte par rapport à la variable prédite pour l’observation \(i\). Dans cette équation, les termes (A) et (B) sont constants car les \(t-1\) arbres précédents ont déjà été entraînés et ne sont pas modifiés par l’entraînement du \(t\)-ième arbre. On peut donc retirer ces termes pour obtenir la fonction-objectif simplifiée \(\tilde{L}^{(t)}\) qui sera utilisée pour l’entraînement du \(t\)-ième arbre:

$ ^{(t)} = _{i=1}^{n} [g_i f_t(_i)+ h_i [f_t(_i)]^2] + (f_t) $ {#eq-fct-obj-final}

1.3.3 Étape 2: calculer les poids optimaux conditionnellement à la structure de l’arbre

A partir de l’équation ?@eq-fct-obj-final, il est possible de faire apparaître les poids \(w_j\) du \(t\)-ième arbre. Chaque arbre \(f_t\) peut être vu comme une fonction constante par morceaux du type \(f_t(x) = w_{\,q(x)}\) où \(q(x)\) est une fonction qui assigne un indice de feuille (un entier entre 1 et \(T\)) à chaque observation \(x\), et \(w_j\) est le poids (valeur de sortie) de la \(j\)-ième feuille. En regroupant les observations \(i\) tombant dans la feuille \(j\) dans l’ensemble \(I_j = \{i\mid q(x_i)=j\}\), la fonction de perte approchée peut être réécrite sous la forme:

\[ \begin{align*} \tilde{L}^{(t)} =& \sum_{j=1}^{T} \sum_{i\in I_{j}} \bigg[g_i f_t(\mathbf{x}_i)\phantom{\frac{1}{2}} &+ \frac{1}{2} h_i [f_t(\mathbf{x}_i)]^2\bigg]&+ \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_i^2 \\ &= \sum_{j=1}^{T} \sum_{i\in I_{j}} \bigg[g_i w_j &+ \frac{1}{2} h_i w_j^2\bigg] &+ \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_i^2 \\ &= \sum^T_{j=1} \bigg[w_j\sum_{i\in I_{j}} g_i &+ \frac{1}{2} w_j^2 \left( \sum_{i \in I_{j}} h_i + \lambda \right) \bigg] &+ \gamma T \end{align*} \]

Dans la dernière expression, la fonction de perte simplifiée se reformule comme une combinaison quadratique des poids \(w_j\), dans laquelle les dérivées première et seconde de la fonction de perte interviennent sous forme de pondérations (\(\sum_{i \in I_j} g_i\) et \(\sum_{i \in I_j} h_i\)). Cette expression peut elle-même s’écrire comme la somme sur l’ensemble des feuilles de la fonction de perte relative à chaque feuille \(j\) : \[ \tilde{L}^{(t)} = \sum_{j=1}^T k(w_j) + \gamma\,T \]

avec \(k(w_j)\) la perte relative à la feuille \(j\) : \[ k(w_j) = \sum_{i \in I_j} \bigl(g_i\,w_j + \tfrac12\,h_i\,w_j^2\bigr) + \tfrac12\,\lambda w_j^2 \]

Pour un arbre de structure donnée, la valeur optimale \(w_j^{\ast}\) de la feuille \(j\), c’est-à-dire la valeur qui minimise la contribution de la feuille à la fonction de perte globale se calcule facilement (en résolvant pour chaque feuille \(j\), \(\frac{\partial k}{\partial w_j} = 0\)):

\[ w_j^{\ast} = -\frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda} \tag{2}\]

On déduit alors, pour une structure d’arbre \(q\) donnée, la valeur optimale de la fonction-objectif pour le \(t\)-ième arbre:

\[ \tilde{L}^{(t)}(q) = -\,\tfrac12 \sum_{j=1}^T \frac{\bigl(\sum_{i \in I_j} g_i\bigr)^2}{\sum_{i \in I_j} h_i + \lambda} + \gamma\,T \tag{3}\]

L’équation 3 est utile en pratique car elle permet de comparer la qualité de deux arbres candidats, et de déterminer immédiatement lequel est le meilleur. On pourrait même penser que cette équation est à elle seule suffisante pour choisir le \(t\)-ième arbre: il suffirait d’énumérer les arbres possibles, de calculer la qualité de chacun d’entre eux, et de retenir le meilleur. En réalité, cette approche est inemployable en pratique car le nombre d’arbres possibles est extrêmement élevé. Par conséquent, cette équation n’est pas utilisée telle quelle, mais sert à comparer les règles de décision possibles à chaque étape d’une optimisation gloutonne, de façon à trouver la structure \(q^\ast\) du \(t\)-ième arbre.

1.3.3.1 Étape 3: déterminer la structure de l’arbre

La méthode de construction des arbres dans les algorithmes de gradient boosting est identique à celle décrite dans la partie REFERENCE A LA PARTIE CART/RF: le \(t\)-ième arbre n’est pas défini en une fois, mais construit de façon gloutonne (greedy). On part d’une feuille unique qui contient toutes les données d’entraînement, et à chaque étape on partitionne les feuilles de l’arbre en choisissant la règle de décision qui maximise la réduction de la perte. Le processus est réitéré jusqu’à ce que l’arbre atteigne un critère d’arrêt, ou jusqu’à ce que plus aucune scission ne permette de réduire la fonction de perte.

La grande différence avec les arbres CART et les forêts aléatoires est que ces algorithmes utilisent l’équation 3 pour choisir la règle de décision (split) à chaque étape de la construction de l’arbre, et non une mesure d’hétérogénéité. Pour chaque noeud, l’algorithme de détermination des règles de décision (split finding algorithm) consiste en une double boucle sur les variables et les valeurs prises par ces variables, qui énumère un grand nombre de règles de décision possibles et mesure le gain associé à chacun d’entre elles avec l’équation 4. La règle de décision retenue sera simplement celui dont le gain est le plus élevé.

Plus spécifiquement, la réduction de perte associée au partitionnement de la feuille \(I\) en deux feuilles gauche (\(I_L\)) et droite (\(I_R\)) à l’aide d’une certaine règle de décision s’écrit (à partir de l’équation 3) : \[ \Delta \tilde{L}^{(t)} = \tfrac12 \Bigl[ \underbrace{\frac{\bigl(\sum_{i \in I_L} g_i\bigr)^2}{\sum_{i \in I_L} h_i + \lambda}}_{\text{Perte de la feuille gauche}} + \underbrace{\frac{\bigl(\sum_{i \in I_R} g_i\bigr)^2}{\sum_{i \in I_R} h_i + \lambda}}_{\text{Perte de la feuille droite}} - \underbrace{\frac{\bigl(\sum_{i \in I} g_i\bigr)^2}{\sum_{i \in I} h_i + \lambda}}_{\text{Perte de la feuille d'origine}} \Bigr] - \gamma \tag{4}\]

La réduction de perte permise par le partitionnement est simplement la différence entre la somme des pertes après partitionnement (feuille gauche + feuille droite) et l’ancienne perte avant partitionnement. Le terme \(\gamma\) est le terme de régularisation qui mesure le coût associé à la création d’une feuille supplémentaire. Si \(\Delta \tilde{L}^{(t)}\) est positive et suffisamment grande, alors la scission fait baisser la perte globale et on la retient. Sinon, on renonce à scinder cette feuille.

Note

L’algorithme de détermination des règles de décision est le composant le plus intense en calcul des algorithmes de gradient boosting. Les différentes implémentations du gradient boosting proposent donc de multiples améliorations et optimisations visant à le rendre le plus efficace possible. Certaines de ces optimisations sont présentées dans la partie LIEN A LA PARTIE HISTOGRAMME/CATVAR.

1.3.3.2 Etape 4: Ajouter des arbres jusqu’à atteindre un critère d’arrêt

Une fois que la structure du \(t\)-ième arbre a été définie et que les valeurs de chaque feuilles ont été calculées, cet arbre est ajouté au modèle global, et la prédiction est mise à jour par la formule suivante:

\[ F_{t}(x)=F_{t-1}(x)+ \eta f_{t}(x) \tag{5}\]

Il est alors possible de commencer l’entraînement de l’arbre suivant, selon la même logique que précédemment. Le processus de construction des arbres se poursuit jusqu’à atteindre soit le nombre maximum d’arbres autorisé dans le modèle (\(K\)), soit un autre critère d’arrêt (par exemple, une réduction de perte minimale par arbre).

1.4 Le grand ennemi du gradient boosting: le surajustement

Une différence majeure entre les forêts aléatoires et les algorithmes de boosting est que ces derniers ne contiennent en eux-mêmes aucune limite au surajustement, bien au contraire: le gradient boosting est un algorithme conçu pour approximer le plus précisément possible la relation entre \(X\) et \(y\) telle qu’elle apparaît dans les données d’entraînement, qu’il s’agisse d’un signal pertinent ou d’un bruit statistique. Par conséquent, tous les algorithmes de gradient boosting sont très vulnérables au surajustement. Plus précisément, il y a deux raisons à cela. D’une part, lors de l’entraînement d’un modèle de gradient boosting, chaque nouvel arbre essaie de réduire l’erreur résiduelle en s’ajustant toujours plus finement aux données. Ainsi, au fur et mesure que le nombre d’arbres augmente, l’algorithme capture non seulement des relations pertinentes entre \(X\) et \(y\), mais aussi le bruit et les particularités aléatoires de l’échantillon d’entraînement. D’autre part, les arbres de décision utilisés sont très flexibles et conçus pour refléter les relations entre \(X\) et \(y\) présentes dans les données d’entraînement, y compris celles qui ne se généralisent pas bien aux nouvelles données. Par exemple, un arbre très profond peut correspondre finement aux données d’entraînement, mais risque de manquer de robustesse sur les données de test.

La lutte contre le surajustement est donc un enjeu majeur de l’entraînement des modèles de gradient boosting. De multiples méthodes ont été proposées pour lutter contre le surajustement:

• la technique de réduction (shrinkage technique) consiste à réduire l’influence de chaque arbre sur le modèle global en multipliant la prédiction de cet arbre par un facteur d’échelle compris entre 0 et 1 au moment de mettre à jour le modèle par l’équation 5. Ce facteur d’échelle est appelé taux d’apprentissage (learning rate); il s’agit du paramètre \(\eta\) dans l’équation 5. L’avantage principal de cette technique est que le modèle s’ajuste progressivement aux données, et est moins altéré par les erreurs dues à des variations aléatoires ou au bruit dans les données. Un taux d’apprentissage bas et un nombre d’itérations suffisant permettent souvent d’obtenir un modèle final plus performant sur des données de test. L’inconvénient est que réduire le taux d’apprentissage nécessite d’augmenter le nombre d’itérations pour obtenir des performances comparables, ce qui peut rallonger le temps d’entraînement.

• l’hyperparamètre de régularisation \(\lambda\) intervient dans l’équation 2 et réduit la valeur absolue des poids des feuilles terminales. Cet hyperparamètre contribue à ce que chaque arbre prédise des valeurs peu élevées. L’intuition est la suivante: lorsqu’une feuille terminale contient un poids \(w_i\) élevé en valeur absolue, ce poids est probablement dû au moins en partie à des observations inhabituelles ou aberrantes (et dont le gradient \(g_i\) prend une valeur extrême); il est donc préférable de réduire légèrement ce poids pour ne pas donner trop d’importance à ces points aberrants.

• l’hyperparamètre de régularisation \(\gamma\) intervient dans l’équation 4. Ce paramètre mesure la réduction minimale de la perte requise pour qu’un nœud soit divisé; une valeur plus élevée aboutit à des arbres moins profonds et contribue à limiter le surajustement en empêchant l’algorithme de créer des splits dont l’apport est très faible et potentiellement dû à des variations non significatives des données d’entraînement.

• la dernière approche consiste à entraîner les arbres sur un échantillon d’observations et/ou de variables. L’échantillonnage des observations permet de réduire l’influence des éventuels points extrêmes contenus dans les données (car ils n’apparaissent pas dans les données d’entraînement de certains arbres); l’échantillonnage des variables permet de varier les variables utilisées dans les splits.

References

Breiman, Leo. 1998. “Rejoinder: Arcing Classifiers.” The Annals of Statistics 26 (3): 841–49.

Chen, Tianqi, and Carlos Guestrin. 2016. “Xgboost: A Scalable Tree Boosting System.” In Proceedings of the 22nd Acm Sigkdd International Conference on Knowledge Discovery and Data Mining, 785–94.

Freund, Yoav, and Robert E Schapire. 1997. “A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting.” Journal of Computer and System Sciences 55 (1): 119–39.

Friedman, Jerome H. 2001. “Greedy Function Approximation: A Gradient Boosting Machine.” Annals of Statistics, 1189–1232.

Grove, Adam J, and Dale Schuurmans. 1998. “Boosting in the Limit: Maximizing the Margin of Learned Ensembles.” In AAAI/IAAI, 692–99.

Ke, Guolin, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu. 2017. “Lightgbm: A Highly Efficient Gradient Boosting Decision Tree.” Advances in Neural Information Processing Systems 30.

Prokhorenkova, Liudmila, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin. 2018. “CatBoost: Unbiased Boosting with Categorical Features.” Advances in Neural Information Processing Systems 31.

Shapire, R. 1990. “The Strength of Weak Learning.” Machine Learning 5 (2).

Footnotes

1. Cette partie reprend la structure et les notations de la partie 2 de Chen and Guestrin (2016).