XGBoost

XGBoost (eXtreme Gradient Boosting) est une bibliothèque logicielle open source permettant de mettre en œuvre des méthodes d’amplification de gradient (Gradient boosting), de régularisation en C++, Java, R, Python et Julia^[2]. XGBoost fonctionne aussi bien sur Linux que sur Microsoft Windows ou MacOS^[3].

D'après sa description, le projet vise à offrir une bibliothèque de gradient boosting "conçue pour être évolutive, portable et distribuée. (GBM, GBRT, GBDT)"^[2].

Au milieu des années 2010, XGBoost s’est imposé comme l’algorithme privilégié par de nombreux lauréats de concours de machine learning^[4].

XGBoost applique la méthode de Newton-Raphson dans l’espace des fonctions, contrairement au gradient boosting classique qui utilise la descente de gradient dans ce même espace. Une approximation de Taylor d’ordre deux est intégrée à la fonction de coût pour établir le lien avec la méthode de Newton-Raphson^[5].

Entrée :

${\displaystyle {(x_{i},y_{i})}_{i=1}^{N}}$ avec une fonction de perte différentiable ${\displaystyle L(y,F(x))}$, un nombre d’apprenants faibles (weak learners) ${\displaystyle M}$ et un taux d’apprentissage ${\displaystyle \alpha }$^[5].

Algorithme :

1. Initialisation du modèle avec une constante :

${\displaystyle {\hat {f}}^{(0)}(x)={\underset {\theta }{\arg \min }}\sum _{i=1}^{N}L(y_{i},\theta )}$

Cette étape consiste à choisir la valeur constante (${\displaystyle \theta }$) qui minimise la perte globale sur l’entrée. Par exemple, pour une perte quadratique ${\displaystyle (L(y,\theta )=(y-\theta )^{2})}$, ${\displaystyle \theta }$ est la moyenne des ${\displaystyle y_{i}}$^[6].

Pour ${\displaystyle m=1}$ à ${\displaystyle M}$ :

a. Calcul des gradients et hessiens :

${\displaystyle {\hat {g}}_{m}(x_{i})=\left.{\frac {\partial L(y_{i},f(x_{i}))}{\partial f(x_{i})}}\right|{f(x)={\hat {f}}^{(m-1)}(x)}}$

${\displaystyle {\hat {h}}_{m}(x_{i})=\left.{\frac {\partial ^{2}L(y_{i},f(x_{i}))}{\partial f(x_{i})^{2}}}\right|{f(x)={\hat {f}}^{(m-1)}(x)}}$

Le gradient ${\displaystyle ({\hat {g}}_{m})}$indique la direction de correction. L'hessien ${\displaystyle ({\hat {h}}_{m})}$ mesure la courbure de la perte, ce qui permet d’ajuster plus finement la mise à jour (méthode de Newton-Raphson)^[7].

b. Ajustement d’un apprenant faible : On ajuste un modèle de base (par exemple, un arbre) pour prédire la cible suivante pour chaque ${\displaystyle x_{i}}$^[6]:

${\displaystyle {\tilde {y}}_{i}=-{\frac {{\hat {g}}_{m}(x_{i})}{{\hat {h}}_{m}(x_{i})}}}$

On cherche la fonction ${\displaystyle \phi _{m}}$ qui minimise :

${\displaystyle {\hat {\phi }}_{m}={\underset {\phi \in \Phi }{\arg \min }}\sum _{i=1}^{N}{\frac {1}{2}}{\hat {h}}_{m}(x_{i})\left[\phi (x_{i})+{\frac {{\hat {g}}_{m}(x_{i})}{{\hat {h}}_{m}(x_{i})}}\right]^{2}}$

où ${\displaystyle \Phi }$ est l’ensemble des fonctions possibles (par exemple, tous les arbres de décision d’une certaine profondeur)^[5].

c. Mise à jour du modèle :

${\displaystyle {\hat {f}}^{(m)}(x)={\hat {f}}^{(m-1)}(x)+\alpha {\hat {\phi }}_{m}(x)}$

où ${\displaystyle \alpha }$ est le taux d’apprentissage^[5].

Sortie finale :

${\displaystyle {\hat {f}}(x)={\hat {f}}^{(M)}(x)={\hat {f}}^{(0)}(x)+\sum _{m=1}^{M}\alpha {\hat {\phi }}_{m}(x)}$

La prédiction finale est la somme de la constante initiale et des corrections successives apportées par chaque apprenant faibles^[6].

• Portail des logiciels libres
• Portail des probabilités et de la statistique
• Portail des données