1 Le gradient boosting
1.1 Introduction
Le fondement théorique du boosting est un article de 1990 (Schapire (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 tâche d’améliorer la prédiction globale en corrigeant les erreurs commises par l’ensemble des modèles précédents. 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 peu profonds.
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}) \]
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 (ou autrement dit afin de rapprocher la prédiction de la vraie valeur).
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é. Cette approche peut donc ê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.
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 dérivable deux fois, atteint un minimum lorsque \(\hat{y} = y\), et sa dérivée seconde par rapport à \(\hat{y}\) est positive. 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:
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\).
Pour \(m = 1, \dots, M:\)
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)}\)
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\)
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.5.
1.4 Un exemple simple: la régression avec perte quadratique
La présentation qui précède peut donner l’impression que la mécanique du gradient boosting est complexe, abstraite et difficile à comprendre. Celle-ci devient beaucoup plus facile à saisir lorsqu’on l’illustre dans un cas simple et intuitif. Prenons ainsi un problème de régression, où l’on cherche à prédire une variable continue, avec une perte quadratique: \(\ell\left(y,\;\hat{y}\right) = \frac{1}{2} \left(y - \hat{y}\right)^2\) et sans terme de régularisation. Dans ce cas particulier, le gradient de la fonction de perte est égal à l’opposé du résidu du modèle \(\hat{y}-y\), et la hessienne de la fonction de perte est égale à 1. L’équation 4 qui donne le poids optimal de la feuille \(j\) devient donc:
\[ w_j^{\ast} = \frac{\sum_{i \in I_j} y-\hat{y}}{|I_j|} \tag{8}\]
où \(I_j\) désigne le nombre d’observations dans la feuille \(j\). Ce résultat est particulièrement intuitif : la prédiction de l’arbre pour chaque feuille terminale est égale à la moyenne des résidus (erreurs) des observations qui s’y trouvent. Ainsi, à chaque étape, le \(t\)-ième arbre corrige les erreurs laissées par les modèle précédents en annulant le résidu moyen du modèle complet dans chaque feuille terminale.
Cet exemple simple illustre bien la démarche du gradient boosting : améliorer progressivement la qualité des prédictions en corrigeant les erreurs résiduelles, chaque nouvel arbre tâchant de capter ce que les arbres précédents n’ont pas bien appris. Par ailleurs, elle permet de comprendre pourquoi le gradient de la fonction de perte est fréquemment désigné par le terme de pseudo-résidu.
1.5 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 par nature très vulnérables au surajustement. En pratique, ce risque de surajustement croît au cours de l’entraînement: au fur et mesure que le nombre d’arbres augmente, l’algorithme capture de moins en moins de relations pertinentes entre \(X\) et \(y\), et de plus en plus le bruit et les variations aléatoires de l’échantillon d’entraînement.
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 7. Ce facteur d’échelle est appelé taux d’apprentissage (learning rate); il s’agit du paramètre \(\eta\) dans l’équation 7. 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 4 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 6. 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 est inspirée des forêts aléatoires et 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 règles de décision.
1.3 Comment fonctionne le gradient boosting?
La méthode de gradient boosting proposée par 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)) etscikit-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 XGBoost.11.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).
Pour entraîner ce modèle, l’algorithme
XGBoostminimise une fonction-objectif qui comporte à la fois une fonction de perte, et un terme de régularisation:\[ \mathcal{L} = \underbrace{\sum_{i=1}^n \ell\left(y_i,\;F(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.). Elle présente généralement les propriétés suivantes: elle est dérivable deux fois, atteint un minimum lorsque \(\hat{y} = y\), et sa dérivée seconde par rapport à \(\hat{y}\) est positive.
Le terme de régularisation \(\Omega(f)\) pénalise la complexité de chaque 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 terminales, 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 Le principe d’entraînement séquentiel
On pourrait essayer d’entraîner directement ce modèle complet, en déterminant en une seule étape toutes les fonctions \(f\) telles que:
\[ F = \underset{f_1, \dots, f_K}{\arg\min} \left( \sum_{i=1}^n \ell\left(y_i,\;\sum_{k=1}^K f_k(x_i)\right) + \gamma T + \frac{1}{2} \lambda \sum_{k=1}^K \sum_{j=1}^{T_k} w_j^2 \right) \]
En réalité, le modèle complet est impossible à entraîner en une seule fois, car pour cela il faudrait déterminer simultanément \(K\) fonctions relativement complexes. 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)}\). Ainsi, en écrivant la relation, \(\hat{y}_i^{(t)} = \hat{y}_i^{(t-1)} + f_t(x_i)\), on peut réécrire la fonction-objectif 1 comme ceci:
\[ L^{(t)} = \sum_{i=1}^n \ell\left(y_i,\;\hat{y}_i^{(t-1)} + f_t(x_i)\right) + \sum_k \Omega(f_{k}) \tag{2}\]
L’objectif de l’itération \(t\) devient donc de trouver le nouvel arbre \(f_t\) qui minimise cette fonction-objectif. Pour ce faire, l’algorithme doit accomplir deux choses: déterminer la structure de l’arbre (c’est-à-dire choisir les règles de décision qui définissent l’arbre) en tenant compte de la régularisation et calculer la meilleure valeur \(w_j\) pour chaque feuille terminale (c’est-à-dire la valeur qui minimise la fonction de perte).
La construction de l’arbre se fait selon une approche gloutonne, de façon très similaire à la construction d’un arbre CART (voir section sur les arbres CART): on divise les données d’entraînement en sous-régions de plus en plus petites, tant que cela génère une réduction “suffisante” de la fonction de perte. Deux différences notables séparent toutefois le gradient boosting des arbres CART et des forêts aléatoires:
les arbres utilisés dans le gradient boosting sont souvent relativement simples et peu profonds. Ainsi, lors de l’entraînement de chaque arbre le partitionnement récursif des données s’arrête généralement assez tôt, soit lorsqu’est atteinte une des limites de complexité définies a priori (profondeur maximale de l’arbre, nombre maximal de feuilles, nombre minimal d’observations par feuille terminale), soit lorsque l’algorithme ne parvient plus à trouver de partitionnement intéressant (c’est-à-dire qui permette de réduire suffisamment la perte).
l’algorithme de détermination des règles de décision utilise un critère reposant sur le gradient de la fonction de perte plutôt que sur une mesure d’impureté. Ce point est décrit plus précisément dans la section suivante.
1.3.3 La mécanique interne du gradient boosting
Les paragraphes qui suivent détaillent le processus de construction du \(t\)-ième arbre, et les équations utilisées dans ce processus.
1.3.3.1 Étape 1: Faire apparaître le gradient de la fonction de perte
On souhaite construire le \(t\)-ième arbre qui minimise la perte, conditionnellement aux données d’entraînement et aux \(t-1\) arbres déjà construits. Formellement d’après l’équation 2 on cherche un arbre \(f_t\) tel que
\[ \hat{f}_t = \underset{f}{\arg\min} \mathcal{L}^{(t)} = \underset{f}{\arg\min} \sum_{i=1}^n \ell\left(y_i,\;\hat{y}_i^{(t-1)} + f_t(\mathbf{x}_i)\right) + \sum_k \Omega(f_{k}) \]
Pour simplifier la construction de ce \(t\)-ième arbre,
XGBoostreformule la fonction de perte en utilisant une approximation de second ordre. 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. On obtient alors la fonction de perte approchée \(\mathcal{L}^{(t)}\):\[ \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_{k=1}^{t-1}\Omega(f_k)}_{\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 le gradient (dérivée première) et la hessienne (dérivée seconde) de la fonction de perte par rapport à la variable prédite pour l’observation \(i\) à l’issue de la \(t-1\)-ième étape de l’entraînement. Dans cette équation, les termes (A) et (B) sont constants car ils ne dépendent que des \(t-1\) arbres précédents qui ont déjà été entraînés et qui 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{\mathcal{L}}^{(t)}\) qui sera utilisée en pratique pour l’entraînement du \(t\)-ième arbre:
\[ \tilde{\mathcal{L}}^{(t)} = \sum_{i=1}^{n} [g_i f_t(\mathbf{x}_i)+ \frac{1}{2} h_i [f_t(\mathbf{x}_i)]^2] + \Omega(f_t) \tag{3}\]
On cherche donc désormais un arbre \(f_t\) tel que
\[ \hat{f}_t = \arg\min_{f} \tilde{\mathcal{L}}^{(t)} = \arg\min_{f} \sum_{i=1}^{n} [g_i f_t(\mathbf{x}_i)+ \frac{1}{2} h_i [f_t(\mathbf{x}_i)]^2] + \Omega(f_t) \]
1.3.3.2 Étape 2: calculer les poids optimaux conditionnellement à une structure d’arbre
A partir de l’équation 3, il est possible de faire apparaître, puis de calculer les poids \(w_j\) du \(t\)-ième arbre. En effet, l’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 terminale. 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\) la condition du premier ordre \(\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{4}\]
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{5}\]
L’équation 5 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.3 Étape 3: déterminer la structure de l’arbre
La méthode de construction des arbres dans les algorithmes de gradient boosting est très similaire à celle décrite dans la partie sur les arbres de décision: le \(t\)-ième arbre est construit de façon gloutonne (greedy), par un algorithme de détermination des règles de décision (split finding algorithm) qui énumère, évalue et compare les règles de décision possibles par une double boucle sur les variables et les valeurs prises par ces variables. La règle de décision retenue à chaque étape sera simplement celle dont le gain est le plus élevé.
La grande différence avec les arbres CART et les forêts aléatoires est que ces algorithmes utilisent l’équation 5 (et non une mesure d’impureté) pour évaluer les règles de décision candidates. Plus précisément, à partir de l’équation 5 la réduction de perte associée au partitionnement de la feuille \(I\) en deux noeuds-enfants gauche (\(I_L\)) et droit (\(I_R\)) à l’aide d’une certaine règle de décision s’écrit comme: \[ \Delta \tilde{L}^{(t)} = \tfrac12 \biggl[ \underbrace{\frac{\bigl(\sum_{i \in I_L} g_i\bigr)^2}{\sum_{i \in I_L} h_i + \lambda}}_{\text{Perte du noeud-enfant gauche}} + \underbrace{\frac{\bigl(\sum_{i \in I_R} g_i\bigr)^2}{\sum_{i \in I_R} h_i + \lambda}}_{\text{Perte du noeud-enfant droit}} - \underbrace{\frac{\bigl(\sum_{i \in I} g_i\bigr)^2}{\sum_{i \in I} h_i + \lambda}}_{\text{Perte du noeud d'origine}} \biggr] - \gamma \tag{6}\]
Cette réduction de perte est simplement la différence entre la somme des pertes après partitionnement (noeud-enfant gauche + noeud-enfant droit) et la perte avant partitionnement. Le terme \(\gamma\) est le terme de régularisation qui mesure le coût associé à la création d’un noeud supplémentaire. Si pour un noeud donné, la meilleure règle de décision candidate est associée à un \(\Delta \tilde{L}^{(t)}\) strictement positif, alors cette règle de décision fait baisser la perte globale. On peut alors l’utiliser pour définir deux nouveaux noeuds-enfants. Sinon, on renonce à scinder ce noeud.
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 sur les sujets avancés relatifs aux traitement des données pendant l’entraînement.
1.3.3.4 Étape 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 des feuilles terminales 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{7}\]
Puis les valeurs des gradients et hessiennes sont mises à jour pour chaque observation par les formules:
\[ g_i = \frac{\partial l(y_i, \hat{y}_i^{(t)})}{\partial\hat{y}_i^{(t)}} \;\;\text{et}\;\; h_i = \frac{\partial^2 l(y_i, \hat{y}_i^{(t)})}{{\partial \hat{y}_i^{(t)}}^2} \]
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).