Amplification du dégradé

Le gradient boosting est une technique d’apprentissage automatique utilisée dans les tâches de régression et de classification , entre autres. Il donne un modèle de prédiction sous la forme d’un ensemble de modèles de prédiction faibles, qui sont typiquement des arbres de décision . ^{[1] [2]} Lorsqu’un arbre de décision est l’Apprenant faible, l’algorithme résultant est appelé arbres à gradient renforcé ; il surpasse généralement la forêt aléatoire . ^{[1] [2] [3]} Un modèle d’arbres boostés par le gradient est construit par étapes comme dans d’autres méthodes de boosting , mais il généralise les autres méthodes en permettant l’optimisation d’un nombre arbitraire fonction de perte différentiable .

Histoire

L’idée du gradient boosting est née de l’observation de Leo Breiman selon laquelle le boosting peut être interprété comme un algorithme d’optimisation sur une fonction de coût appropriée. ^[4] Des algorithmes explicites de renforcement du gradient de régression ont ensuite été développés par Jerome H. Friedman , ^{[5] [6]} simultanément avec la perspective plus générale de renforcement du gradient fonctionnel de Llew Mason, Jonathan Baxter, Peter Bartlett et Marcus Frean. ^{[7] [8]} Les deux derniers articles ont introduit la vision des algorithmes de boosting comme une descente de gradient fonctionnelle itérativealgorithmes. C’est-à-dire des algorithmes qui optimisent une fonction de coût sur l’espace des fonctions en choisissant de manière itérative une fonction (hypothèse faible) qui pointe dans la direction du gradient négatif. Cette vision du gradient fonctionnel du boosting a conduit au développement d’algorithmes de boosting dans de nombreux domaines de l’apprentissage automatique et des statistiques au-delà de la régression et de la classification.

Présentation informelle

(Cette section suit l’exposition de l’amplification du gradient par Li. ^[9] )

Comme d’autres méthodes de boosting, le gradient boosting combine des “apprenants” faibles en un seul apprenant fort de manière itérative. Il est plus facile à expliquer dans le cadre de la régression des moindres carrés , où le but est “d’enseigner” un modèle F {displaystyle F} prédire des valeurs de la forme y ^ = F ( x ) {displaystyle {chapeau {y}}=F(x)} hat{y} = F(x) en minimisant l’ erreur quadratique moyenne 1 n ∑ i ( y ^ i − y i ) 2 {displaystyle {tfrac {1}{n}}sum _{i}({hat {y}}_{i}-y_{i})^{2}} ${displaystyle {tfrac {1}{n}}sum _{i}({hat {y}}_{i}-y_{i})^{2}}$ ${displaystyle {tfrac {1}{n}}sum _{i}({hat {y}}_{i}-y_{i})^{2}}$ , où i {displaystyle i} index sur un ensemble d’entraînement de taille n {displaystyle n} des valeurs réelles de la variable de sortie y {displaystyle y} :

y ^ i = {displaystyle {hat {y}}_{i}=} ${displaystyle {hat {y}}_{i}=}$ ${displaystyle {hat {y}}_{i}=}$ la valeur prédite F ( x i ) {displaystyle F(x_{i})} ${displaystyle F(x_{i})}$ ${displaystyle F(x_{i})}$
y i = {displaystyle y_{i}=} ${displaystyle y_{i}=}$ ${displaystyle y_{i}=}$ la valeur observée
n {displaystyle n} le nombre d’échantillons dans y {displaystyle y}

Considérons maintenant un algorithme de renforcement de gradient avec M {displaystyle M} étapes. A chaque étape m {displaystyle m} ( 1 ≤ m ≤ M {displaystyle 1leq mleq M} 1 le m le M ) de renforcement du gradient, supposons un modèle imparfait F m {displaystyle F_{m}} F_m (pour les faibles m {displaystyle m} , ce modèle peut simplement retourner y ^ i = y ̄ {displaystyle {hat {y}}_{i}={bar {y}}} ${displaystyle {hat {y}}_{i}={bar {y}}}$ ${displaystyle {hat {y}}_{i}={bar {y}}}$ , où l’ échelle de droite est la moyenne de y {displaystyle y} ). Pour améliorer F m {displaystyle F_{m}} F_m , notre algorithme devrait ajouter un nouvel estimateur, h m ( x ) {displaystyle h_{m}(x)} ${displaystyle h_{m}(x)}$ ${displaystyle h_{m}(x)}$ . Ainsi,

F m + 1 ( x ) = F m ( x ) + h m ( x ) = y {displaystyle F_{m+1}(x)=F_{m}(x)+h_{m}(x)=y} ${displaystyle F_{m+1}(x)=F_{m}(x)+h_{m}(x)=y}$ ${displaystyle F_{m+1}(x)=F_{m}(x)+h_{m}(x)=y}$

ou équivalent,

h m ( x ) = y − F m ( x ) {displaystyle h_{m}(x)=y-F_{m}(x)} ${displaystyle h_{m}(x)=y-F_{m}(x)}$ ${displaystyle h_{m}(x)=y-F_{m}(x)}$ .

Par conséquent, l’amplification du gradient ajustera h au résidu y − F m ( x ) {displaystyle y-F_{m}(x)} y - F_m(x) . Comme dans d’autres variantes de boosting, chaque F m + 1 {displaystyle F_{m+1}} $F_{m+1}$ $F_{m+1}$ tente de corriger les erreurs de son prédécesseur F m {displaystyle F_{m}} F_m . Une généralisation de cette idée aux fonctions de perte autres que l’erreur quadratique et aux problèmes de classification et de classement découle de l’observation que les résidus h m ( x ) {displaystyle h_{m}(x)} ${displaystyle h_{m}(x)}$ ${displaystyle h_{m}(x)}$ pour un modèle donné sont proportionnels aux gradients négatifs de la fonction de perte de l’ erreur quadratique moyenne (MSE) (par rapport à F ( x ) {displaystyle F(x)} F(x) ):

L M S E = 1 n ( y − F ( x ) ) 2 {displaystyle L_{rm {MSE}}={frac {1}{n}}left(yF(x)right)^{2}} ${displaystyle L_{rm {MSE}}={frac {1}{n}}left(y-F(x)right)^{2}}$ − ∂ L M S E ∂ F = 2 n ( y − F ( x ) ) = 2 n h m ( x ) {displaystyle -{frac {partial L_{rm {MSE}}}{partial F}}={frac {2}{n}}(yF(x))={frac {2}{ n}}h_{m}(x)} ${displaystyle -{frac {partial L_{rm {MSE}}}{partial F}}={frac {2}{n}}(y-F(x))={frac {2}{n}}h_{m}(x)}$ ${displaystyle -{frac {partial L_{rm {MSE}}}{partial F}}={frac {2}{n}}(y-F(x))={frac {2}{n}}h_{m}(x)}$ .

Ainsi, l’amplification de gradient pourrait être spécialisée dans un algorithme de descente de gradient , et sa généralisation implique de “brancher” une perte différente et son gradient.

Algorithme

Dans de nombreux problèmes d’apprentissage supervisé , il existe une variable de sortie y et un vecteur de variables d’entrée x , liés les uns aux autres avec une certaine distribution probabiliste. Le but est de trouver une fonction F ^ ( x ) {displaystyle {chapeau {F}}(x)} hat{F}(x) qui se rapproche le mieux de la variable de sortie à partir des valeurs des variables d’entrée. Ceci est formalisé en introduisant une fonction de perte L ( y , F ( x ) ) {displaystyle L(y,F(x))} L(y, F(x)) et en le minimisant :

F ^ = arg ⁡ min F E x , y [ L ( y , F ( x ) ) ] {displaystyle {hat {F}}={underset {F}{arg min }},mathbb {E} _{x,y}[L(y,F(x))]} ${displaystyle {hat {F}}={underset {F}{arg min }},mathbb {E} _{x,y}[L(y,F(x))]}$ ${displaystyle {hat {F}}={underset {F}{arg min }},mathbb {E} _{x,y}[L(y,F(x))]}$ .

La méthode de renforcement du gradient suppose un y à valeur réelle et cherche une approximation F ^ ( x ) {displaystyle {chapeau {F}}(x)} hat{F}(x) sous la forme d’une somme pondérée de fonctions h i ( x ) {displaystyle h_{i}(x)} h_i (x) d’une certaine classe H {displaystyle {mathcal{H}}} {mathcal {H}} , appelés apprenants de base (ou faibles ) :

F ^ ( x ) = ∑ i = 1 M γ i h i ( x ) + const {displaystyle {hat {F}}(x)=sum _{i=1}^{M}gamma _{i}h_{i}(x)+{mbox{const}}} ${displaystyle {hat {F}}(x)=sum _{i=1}^{M}gamma _{i}h_{i}(x)+{mbox{const}}}$ ${displaystyle {hat {F}}(x)=sum _{i=1}^{M}gamma _{i}h_{i}(x)+{mbox{const}}}$ .

On nous donne généralement un ensemble de formation { ( x 1 , y 1 ) , … , ( x n , y n ) } {displaystyle {(x_{1},y_{1}),dots ,(x_{n},y_{n})}} ${(x_{1},y_{1}),dots ,(x_{n},y_{n})}$ ${(x_{1},y_{1}),dots ,(x_{n},y_{n})}$ des valeurs d’échantillon connues de x et des valeurs correspondantes de y . Conformément au principe empirique de minimisation du risque , la méthode tente de trouver une approximation F ^ ( x ) {displaystyle {chapeau {F}}(x)} hat{F}(x) qui minimise la valeur moyenne de la fonction de perte sur l’ensemble d’apprentissage, c’est-à-dire minimise le risque empirique. Pour ce faire, il part d’un modèle constitué d’une fonction constante F 0 ( x ) {displaystyle F_{0}(x)} ${displaystyle F_{0}(x)}$ ${displaystyle F_{0}(x)}$ , et le développe progressivement de manière gourmande :

F 0 ( x ) = arg ⁡ min γ ∑ i = 1 n L ( y i , γ ) {displaystyle F_{0}(x)={underset {gamma }{arg min }}{sum _{i=1}^{n}{L(y_{i},gamma )} }} ${displaystyle F_{0}(x)={underset {gamma }{arg min }}{sum _{i=1}^{n}{L(y_{i},gamma )}}}$ ${displaystyle F_{0}(x)={underset {gamma }{arg min }}{sum _{i=1}^{n}{L(y_{i},gamma )}}}$ , F m ( x ) = F m − 1 ( x ) + a r g m i n h m ∈ H [ ∑ i = 1 n L ( y i , F m − 1 ( x i ) + h m ( x i ) ) ] {displaystyle F_{m}(x)=F_{m-1}(x)+{underset {h_{m}in {mathcal {H}}}{operatorname {arg,min} }} left[{sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}} à droite]} ${displaystyle F_{m}(x)=F_{m-1}(x)+{underset {h_{m}in {mathcal {H}}}{operatorname {arg,min} }}left[{sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}}right]}$ ${displaystyle F_{m}(x)=F_{m-1}(x)+{underset {h_{m}in {mathcal {H}}}{operatorname {arg,min} }}left[{sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}}right]}$ ,

où h m ∈ H {displaystyle h_{m}in {mathcal {H}}} ${displaystyle h_{m}in {mathcal {H}}}$ est une fonction d’apprentissage de base.

Malheureusement, choisir la meilleure fonction h à chaque étape pour une fonction de perte arbitraire L est un problème d’optimisation infaisable en termes de calcul en général. Par conséquent, nous limitons notre approche à une version simplifiée du problème.

L’idée est d’appliquer un pas de Descente la plus raide à ce problème de minimisation (descente de gradient fonctionnelle).

L’idée de base derrière la Descente la plus raide est de trouver un minimum local de la fonction de perte en itérant sur la F m ( x ) {displaystyle F_{m}(x)} ${displaystyle F_{m}(x)}$ ${displaystyle F_{m}(x)}$ . En fait, la direction de descente maximale locale de la fonction de perte est le gradient négatif. ^[dix]

Par conséquent, déplacer une petite quantité γ {displaystylegamma} gamma telle que l’approximation linéaire reste valable :

F m ( x ) = F m − 1 ( x ) − γ ∑ i = 1 n ∇ F m − 1 L ( y i , F m − 1 ( x i ) ) {displaystyle F_{m}(x)=F_{m-1}(x)-gamma sum _{i=1}^{n}{nabla _{F_{m-1}}L(y_ {i},F_{m-1}(x_{i}))}} ${displaystyle F_{m}(x)=F_{m-1}(x)-gamma sum _{i=1}^{n}{nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}}$ ${displaystyle F_{m}(x)=F_{m-1}(x)-gamma sum _{i=1}^{n}{nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}}$

Où γ > 0 {displaystylegamma >0} . Cela implique (pour les petites γ {displaystylegamma} gamma : L ( y i , F m ( x i ) ) ≤ L ( y i , F m − 1 ( x i ) ) {displaystyle L(y_{i},F_{m}(x_{i}))leq L(y_{i},F_{m-1}(x_{i}))} ${displaystyle L(y_{i},F_{m}(x_{i}))leq L(y_{i},F_{m-1}(x_{i}))}$ ${displaystyle L(y_{i},F_{m}(x_{i}))leq L(y_{i},F_{m-1}(x_{i}))}$ .

Preuve de la forme fonctionnelle du dérivé
Pour prouver ce qui suit, considérons l’objectif O = ∑ i = 1 n L ( y i , F m − 1 ( x i ) + h m ( x i ) ) {displaystyle O=sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))} } ${displaystyle O=sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}}$ ${displaystyle O=sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}}$ Faire un développement de Taylor au premier ordre O = ∑ i = 1 n L ( y i , F m − 1 ( x i ) + h m ( x i ) ) ≈ ∑ i = 1 n L ( y i , F m − 1 ( x i ) ) + h m ( x i ) ∇ F m − 1 L ( y i , F m − 1 ( x i ) ) + . . {displaystyle O=sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))} approx sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i}))+h_{m}(x_{i})nabla _{ F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}+..} ${displaystyle O=sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}approx sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i}))+h_{m}(x_{i})nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}+..}$ ${displaystyle O=sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}approx sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i}))+h_{m}(x_{i})nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}+..}$ Maintenant différencier wrt à h m ( x i ) {displaystyle h_{m}(x_{i})} ${displaystyle h_{m}(x_{i})}$ ${displaystyle h_{m}(x_{i})}$ il ne reste que la dérivée du second terme ∇ F m − 1 L ( y i , F m − 1 ( x i ) ) {displaystyle nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))} ${displaystyle nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}$ ${displaystyle nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}$ c’est la direction de montée la plus raide et nous devons donc nous déplacer dans le sens négatif de cette direction pour nous déplacer dans la direction de Descente la plus raide. …

Preuve de la forme fonctionnelle du dérivé

Pour prouver ce qui suit, considérons l’objectif O = ∑ i = 1 n L ( y i , F m − 1 ( x i ) + h m ( x i ) ) {displaystyle O=sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))} } ${displaystyle O=sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}}$ ${displaystyle O=sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}}$ Faire un développement de Taylor au premier ordre O = ∑ i = 1 n L ( y i , F m − 1 ( x i ) + h m ( x i ) ) ≈ ∑ i = 1 n L ( y i , F m − 1 ( x i ) ) + h m ( x i ) ∇ F m − 1 L ( y i , F m − 1 ( x i ) ) + . . {displaystyle O=sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))} approx sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i}))+h_{m}(x_{i})nabla _{ F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}+..} ${displaystyle O=sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}approx sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i}))+h_{m}(x_{i})nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}+..}$ ${displaystyle O=sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}approx sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i}))+h_{m}(x_{i})nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}+..}$ Maintenant différencier wrt à h m ( x i ) {displaystyle h_{m}(x_{i})} ${displaystyle h_{m}(x_{i})}$ ${displaystyle h_{m}(x_{i})}$ il ne reste que la dérivée du second terme ∇ F m − 1 L ( y i , F m − 1 ( x i ) ) {displaystyle nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))} ${displaystyle nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}$ ${displaystyle nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}$ c’est la direction de montée la plus raide et nous devons donc nous déplacer dans le sens négatif de cette direction pour nous déplacer dans la direction de Descente la plus raide.

…

De plus, nous pouvons optimiser γ {displaystylegamma} gamma en trouvant le γ {displaystylegamma} gamma valeur pour laquelle la fonction de perte a un minimum :

γ m = arg ⁡ min γ ∑ i = 1 n L ( y i , F m ) ) = arg ⁡ min γ ∑ i = 1 n L ( y i , F m − 1 ( x i ) − γ ∇ F m − 1 L ( y i , F m − 1 ( x i ) ) ) , {displaystyle gamma _{m}={underset {gamma }{arg min }}{sum _{i=1}^{n}{Lleft(y_{i},F_{m })right)}}={underset {gamma }{arg min }}{sum _{i=1}^{n}{Lleft(y_{i},F_{m-1 }(x_{i})-gamma nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))right)}},} ${displaystyle gamma _{m}={underset {gamma }{arg min }}{sum _{i=1}^{n}{Lleft(y_{i},F_{m})right)}}={underset {gamma }{arg min }}{sum _{i=1}^{n}{Lleft(y_{i},F_{m-1}(x_{i})-gamma nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))right)}},}$ ${displaystyle gamma _{m}={underset {gamma }{arg min }}{sum _{i=1}^{n}{Lleft(y_{i},F_{m})right)}}={underset {gamma }{arg min }}{sum _{i=1}^{n}{Lleft(y_{i},F_{m-1}(x_{i})-gamma nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))right)}},}$

Si l’on considère le cas continu, c’est-à-dire où H {displaystyle {mathcal{H}}} est l’ensemble des fonctions différentiables arbitraires sur R {displaystyle mathbb {R} } , nous mettrons à jour le modèle conformément aux équations suivantes

F m ( x ) = F m − 1 ( x ) − γ m ∑ i = 1 n ∇ F m − 1 L ( y i , F m − 1 ( x i ) ) {displaystyle F_{m}(x)=F_{m-1}(x)-gamma _{m}sum _{i=1}^{n}{nabla _{F_{m-1} }L(y_{i},F_{m-1}(x_{i}))}} ${displaystyle F_{m}(x)=F_{m-1}(x)-gamma _{m}sum _{i=1}^{n}{nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}}$ ${displaystyle F_{m}(x)=F_{m-1}(x)-gamma _{m}sum _{i=1}^{n}{nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))}}$ Où: γ m = arg ⁡ min γ ∑ i = 1 n L ( y i , F m − 1 ( x i ) − γ ∇ F m − 1 L ( y i , F m − 1 ( x i ) ) ) , {displaystyle gamma _{m}={underset {gamma }{arg min }}{sum _{i=1}^{n}{Lleft(y_{i},F_{m -1}(x_{i})-gamma nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))right)}},} ${displaystyle gamma _{m}={underset {gamma }{arg min }}{sum _{i=1}^{n}{Lleft(y_{i},F_{m-1}(x_{i})-gamma nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))right)}},}$ ${displaystyle gamma _{m}={underset {gamma }{arg min }}{sum _{i=1}^{n}{Lleft(y_{i},F_{m-1}(x_{i})-gamma nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))right)}},}$

où les dérivées sont prises par rapport aux fonctions F i {displaystyle F_{i}} $F_{i}$ $F_{i}$ pour i ∈ { 1 , . . , m } {displaystyle iin {1,..,m}} , et γ m {displaystyle gamma _{m}} $gamma _{m}$ $gamma _{m}$ est la longueur du pas. Dans le cas discret cependant, c’est-à-dire lorsque l’ensemble H {displaystyle {mathcal{H}}} {mathcal {H}} est finie, on choisit la fonction candidate h la plus proche du gradient de L pour laquelle le coefficient γ peut alors être calculé à l’aide d’une recherche linéaire sur les équations ci-dessus. Notez que cette approche est une heuristique et ne donne donc pas une solution exacte au problème donné, mais plutôt une approximation. En pseudocode, la méthode générique de boosting de gradient est : ^{[5] [2]}

Entrée : ensemble d’entraînement { ( x i , y i ) } i = 1 n , {displaystyle {(x_{i},y_{i})}_{i=1}^{n},} ${displaystyle {(x_{i},y_{i})}_{i=1}^{n},}$ ${displaystyle {(x_{i},y_{i})}_{i=1}^{n},}$ une fonction de perte différentiable L ( y , F ( x ) ) , {displaystyle L(y,F(x)),} nombre d’itérations M .

Algorithme:

Initialiser le modèle avec une valeur constante : F 0 ( x ) = arg ⁡ min γ ∑ i = 1 n L ( y i , γ ) . {displaystyle F_{0}(x)={underset {gamma }{arg min }}sum _{i=1}^{n}L(y_{i},gamma ).} $F_0(x) = underset{gamma}{argmin} sum_{i=1}^n L(y_i, gamma).$ $F_0(x) = underset{gamma}{argmin} sum_{i=1}^n L(y_i, gamma).$
Pour m = 1 à M :
1. Calculer des pseudo-résidus : r i m = − [ ∂ L ( y i , F ( x i ) ) ∂ F ( x i ) ] F ( x ) = F m − 1 ( x ) for i = 1 , … , n . {displaystyle r_{im}=-left[{frac {partial L(y_{i},F(x_{i}))}{partial F(x_{i})}}right]_ {F(x)=F_{m-1}(x)}quad {mbox{pour }}i=1,ldots ,n.} $r_{im} = -left[frac{partial L(y_i, F(x_i))}{partial F(x_i)}right]_{F(x)=F_{m-1}(x)} quad mbox{for } i=1,ldots,n.$ $r_{im} = -left[frac{partial L(y_i, F(x_i))}{partial F(x_i)}right]_{F(x)=F_{m-1}(x)} quad mbox{for } i=1,ldots,n.$
2. Ajuster un apprenant de base (ou un Apprenant faible, par exemple un arbre) fermé sous mise à l’échelle h m ( x ) {displaystyle h_{m}(x)} ${displaystyle h_{m}(x)}$ ${displaystyle h_{m}(x)}$ aux pseudo-résidus, c’est-à-dire l’entraîner à l’aide de l’ensemble d’apprentissage { ( x i , r i m ) } i = 1 n {displaystyle {(x_{i},r_{im})}_{i=1}^{n}} ${(x_i, r_{im})}_{i=1}^n$ ${(x_i, r_{im})}_{i=1}^n$ .
3. Calculer le multiplicateur γ m {displaystyle gamma _{m}} $gamma _{m}$ $gamma _{m}$ en résolvant le problème d’optimisation unidimensionnel suivant : γ m = a r g m i n γ ∑ i = 1 n L ( y i , F m − 1 ( x i ) + γ h m ( x i ) ) . {displaystyle gamma _{m}={underset {gamma }{operatorname {arg,min} }}sum _{i=1}^{n}Lleft(y_{i},F_ {m-1}(x_{i})+gamma h_{m}(x_{i})right).} $gamma_m = underset{gamma}{operatorname{arg,min}} sum_{i=1}^n Lleft(y_i, F_{m-1}(x_i) + gamma h_m(x_i)right).$ $gamma_m = underset{gamma}{operatorname{arg,min}} sum_{i=1}^n Lleft(y_i, F_{m-1}(x_i) + gamma h_m(x_i)right).$
4. Mettez à jour le modèle : F m ( x ) = F m − 1 ( x ) + γ m h m ( x ) . {displaystyle F_{m}(x)=F_{m-1}(x)+gamma _{m}h_{m}(x).} $F_{m}(x)=F_{{m-1}}(x)+gamma _{m}h_{m}(x).$ $F_{m}(x)=F_{{m-1}}(x)+gamma _{m}h_{m}(x).$
Production F M ( x ) . {displaystyle F_{M}(x).}

Amélioration de l’arbre dégradé

L’amplification de gradient est généralement utilisée avec des arbres de décision (en particulier des arbres CART ) d’une taille fixe en tant qu’apprenants de base. Pour ce cas particulier, Friedman propose une modification de la méthode de renforcement du gradient qui améliore la qualité d’ajustement de chaque apprenant de base.

L’augmentation de gradient générique à la m -ième étape correspondrait à un arbre de décision h m ( x ) {displaystyle h_{m}(x)} ${displaystyle h_{m}(x)}$ ${displaystyle h_{m}(x)}$ aux pseudo-résidus. Laisser J m {displaystyle J_{m}} ${displaystyle J_{m}}$ ${displaystyle J_{m}}$ être le nombre de ses feuilles. L’arborescence partitionne l’espace d’entrée en J m {displaystyle J_{m}} ${displaystyle J_{m}}$ ${displaystyle J_{m}}$ régions disjointes R 1 m , … , R J m m {displaystyle R_{1m},ldots ,R_{J_{m}m}} ${displaystyle R_{1m},ldots ,R_{J_{m}m}}$ ${displaystyle R_{1m},ldots ,R_{J_{m}m}}$ et prédit une valeur constante dans chaque région. En utilisant la Notation de l’indicateur , la sortie de h m ( x ) {displaystyle h_{m}(x)} ${displaystyle h_{m}(x)}$ ${displaystyle h_{m}(x)}$ pour l’entrée x peut être écrit comme la somme :

h m ( x ) = ∑ j = 1 J m b j m 1 R j m ( x ) , {displaystyle h_{m}(x)=sum _{j=1}^{J_{m}}b_{jm}mathbf {1} _{R_{jm}}(x),} ${displaystyle h_{m}(x)=sum _{j=1}^{J_{m}}b_{jm}mathbf {1} _{R_{jm}}(x),}$ ${displaystyle h_{m}(x)=sum _{j=1}^{J_{m}}b_{jm}mathbf {1} _{R_{jm}}(x),}$

Learn more.

Isomorphisme

Jul 14, 2022

Premier article sur la théorie des ensembles de Cantor

Jul 12, 2022

Énergie gravitationnelle

Jul 9, 2022

Sphère de Riemann

Jul 8, 2022

où b j m {displaystyle b_{jm}} $b_{jm}$ $b_{jm}$ est la valeur prédite dans la région R j m {displaystyle R_{jm}} $R_{jm}$ $R_{jm}$ . ^[11]

Alors les coefficients b j m {displaystyle b_{jm}} $b_{jm}$ $b_{jm}$ sont multipliés par une certaine valeur γ m {displaystyle gamma _{m}} $gamma _{m}$ $gamma _{m}$ , choisie à l’aide de la recherche linéaire de manière à minimiser la fonction de perte, et le modèle est mis à jour comme suit :

F m ( x ) = F m − 1 ( x ) + γ m h m ( x ) , γ m = a r g m i n γ ∑ i = 1 n L ( y i , F m − 1 ( x i ) + γ h m ( x i ) ) . {displaystyle F_{m}(x)=F_{m-1}(x)+gamma _{m}h_{m}(x),quad gamma _{m}={underset {gamma }{operatorname {arg,min} }}sum _{i=1}^{n}L(y_{i},F_{m-1}(x_{i})+gamma h_{m} (x_{i})).} $F_m(x) = F_{m-1}(x) + gamma_m h_m(x), quad gamma_m = underset{gamma}{operatorname{arg,min}} sum_{i=1}^n L(y_i, F_{m-1}(x_i) + gamma h_m(x_i)).$ $F_m(x) = F_{m-1}(x) + gamma_m h_m(x), quad gamma_m = underset{gamma}{operatorname{arg,min}} sum_{i=1}^n L(y_i, F_{m-1}(x_i) + gamma h_m(x_i)).$

Friedman propose de modifier cet algorithme afin qu’il choisisse une valeur optimale distincte γ j m {displaystyle gamma _{jm}} ${displaystyle gamma _{jm}}$ ${displaystyle gamma _{jm}}$ pour chacune des régions de l’arbre, au lieu d’un seul γ m {displaystyle gamma _{m}} $gamma _{m}$ $gamma _{m}$ pour tout l’arbre. Il appelle l’algorithme modifié “TreeBoost”. Les coefficients b j m {displaystyle b_{jm}} $b_{jm}$ $b_{jm}$ de la procédure d’ajustement d’arbre peut alors être simplement ignorée et la règle de mise à jour du modèle devient :

F m ( x ) = F m − 1 ( x ) + ∑ j = 1 J m γ j m 1 R j m ( x ) , γ j m = a r g m i n γ ∑ x i ∈ R j m L ( y i , F m − 1 ( x i ) + γ ) . {displaystyle F_{m}(x)=F_{m-1}(x)+sum _{j=1}^{J_{m}}gamma _{jm}mathbf {1} _{R_ {jm}}(x),quad gamma _{jm}={underset {gamma }{operatorname {arg,min} }}sum _{x_{i}in R_{jm}} L(y_{i},F_{m-1}(x_{i})+gamma ).} ${displaystyle F_{m}(x)=F_{m-1}(x)+sum _{j=1}^{J_{m}}gamma _{jm}mathbf {1} _{R_{jm}}(x),quad gamma _{jm}={underset {gamma }{operatorname {arg,min} }}sum _{x_{i}in R_{jm}}L(y_{i},F_{m-1}(x_{i})+gamma ).}$ ${displaystyle F_{m}(x)=F_{m-1}(x)+sum _{j=1}^{J_{m}}gamma _{jm}mathbf {1} _{R_{jm}}(x),quad gamma _{jm}={underset {gamma }{operatorname {arg,min} }}sum _{x_{i}in R_{jm}}L(y_{i},F_{m-1}(x_{i})+gamma ).}$

Taille des arbres

J {displaystyle J} , le nombre de nœuds terminaux dans les arbres, est le paramètre de la méthode qui peut être ajusté pour un ensemble de données à portée de main. Il contrôle le niveau d’ interaction maximal autorisé entre les variables du modèle. Avec J = 2 {displaystyle J=2} J = 2 ( souches de décision ), aucune interaction entre les variables n’est autorisée. Avec J = 3 {displaystyle J=3} le modèle peut inclure les effets de l’interaction entre jusqu’à deux variables, et ainsi de suite.

Hastie et al. ^[2] commentaire qui typiquement 4 ≤ J ≤ 8 {displaystyle 4leq Jleq 8} 4 leq J leq 8 fonctionnent bien pour booster et les résultats sont assez insensibles au choix de J {displaystyle J} dans cette gamme, J = 2 {displaystyle J=2} J = 2 est insuffisant pour de nombreuses applications, et J > 10 {displaystyle J>10} J > 10 est peu susceptible d’être nécessaire.

Régularisation

Un ajustement trop serré de l’ensemble d’apprentissage peut entraîner une dégradation de la capacité de généralisation du modèle. Plusieurs techniques dites de régularisation réduisent cet effet de surajustement en contraignant la procédure d’ajustement.

Un paramètre naturel de régularisation est le nombre d’itérations de renforcement de gradient M (c’est-à-dire le nombre d’arbres dans le modèle lorsque l’apprenant de base est un arbre de décision). L’augmentation de M réduit l’erreur sur l’ensemble d’apprentissage, mais une valeur trop élevée peut entraîner un surajustement. Une valeur optimale de M est souvent sélectionnée en surveillant l’erreur de prédiction sur un ensemble de données de validation séparé. Outre le contrôle de M , plusieurs autres techniques de régularisation sont utilisées.

Un autre paramètre de régularisation est la profondeur des arbres. Plus cette valeur est élevée, plus le modèle est susceptible de surajuster les données d’apprentissage.

Rétrécissement

Une partie importante de la méthode de gradient boosting est la régularisation par rétrécissement qui consiste à modifier la règle de mise à jour comme suit :

F m ( x ) = F m − 1 ( x ) + ν ⋅ γ m h m ( x ) , 0 < ν ≤ 1 , {displaystyle F_{m}(x)=F_{m-1}(x)+nu cdot gamma _{m}h_{m}(x),quad 0<nu leq 1,} $F_m(x) = F_{m-1}(x) + nu cdot gamma_m h_m(x), quad 0 < nu leq 1,$ $F_m(x) = F_{m-1}(x) + nu cdot gamma_m h_m(x), quad 0 < nu leq 1,$

où paramètre ν {displaystylenu } s’appelle le “taux d’apprentissage”.

Empiriquement, il a été constaté que l’utilisation de petits taux d’apprentissage (tels que ν < 0.1 {displaystylenu <0.1} nu < 0.1 ) apporte des améliorations spectaculaires dans la capacité de généralisation des modèles par rapport à l’amplification de gradient sans rétrécissement ( ν = 1 {displaystylenu =1} nu = 1 ). ^[2] Cependant, cela se fait au prix d’une augmentation du Temps de calcul à la fois pendant l’apprentissage et l’ interrogation : un taux d’apprentissage plus faible nécessite plus d’itérations.

Renforcement du gradient stochastique

Peu de temps après l’introduction de l’amplification de gradient, Friedman a proposé une modification mineure de l’algorithme, motivée par la méthode d’ Agrégation bootstrap (“bagging”) de Breiman . ^[6] Plus précisément, il a proposé qu’à chaque itération de l’algorithme, un apprenant de base soit ajusté sur un sous-échantillon de l’ensemble d’apprentissage tiré au hasard sans remplacement. ^[12] Friedman a observé une amélioration substantielle de la précision de l’amplification du gradient avec cette modification.

La taille du sous-échantillon est une fraction constante f {displaystyle f} de la taille de l’ensemble d’apprentissage. Lorsque f = 1 {displaystyle f=1} f=1 , l’algorithme est déterministe et identique à celui décrit ci-dessus. Des valeurs plus petites de f {displaystyle f} introduire du caractère aléatoire dans l’algorithme et aider à prévenir le surajustement , agissant comme une sorte de régularisation . L’algorithme devient également plus rapide, car les arbres de régression doivent être adaptés à des ensembles de données plus petits à chaque itération. Friedman ^[6] a obtenu que 0.5 ≤ f ≤ 0.8 {displaystyle 0.5leq fleq 0.8} conduit à de bons résultats pour les ensembles d’entraînement de petite et moyenne taille. Donc, f {displaystyle f} est généralement défini sur 0,5, ce qui signifie que la moitié de l’ensemble de formation est utilisée pour construire chaque apprenant de base.

De plus, comme dans le bagging, le sous-échantillonnage permet de définir une erreur hors sac de l’amélioration des performances de prédiction en évaluant les prédictions sur les observations qui n’ont pas été utilisées dans la construction de l’apprenant de base suivant. Les estimations prêtes à l’emploi permettent d’éviter le besoin d’un ensemble de données de validation indépendant, mais sous-estiment souvent l’amélioration réelle des performances et le nombre optimal d’itérations. ^{[13] [14]}

Nombre d’observations dans les feuilles

Les implémentations de renforcement d’arbre de gradient utilisent souvent également la régularisation en limitant le nombre minimum d’observations dans les nœuds terminaux des arbres. Il est utilisé dans le processus de construction de l’arborescence en ignorant toutes les scissions qui conduisent à des nœuds contenant moins que ce nombre d’instances d’ensemble d’apprentissage.

L’imposition de cette limite permet de réduire la variance des prédictions au niveau des feuilles.

Pénaliser la complexité de l’arbre

Une autre technique de régularisation utile pour les arbres à gradient boosté consiste à pénaliser la complexité du modèle appris. ^[15] La complexité du modèle peut être définie comme le nombre proportionnel de feuilles dans les arbres appris. L’optimisation conjointe de la perte et de la complexité du modèle correspond à un algorithme de post-élagage pour supprimer les branches qui ne parviennent pas à réduire la perte d’un seuil. D’autres types de régularisation tels qu’un l 2 {displaystyle ell _{2}} $ell _{2}$ $ell _{2}$ une pénalité sur les valeurs des feuilles peut également être ajoutée pour éviter le surajustement .

Usage

Le gradient boosting peut être utilisé dans le domaine de l’apprentissage du classement . Les moteurs de recherche Web commerciaux Yahoo ^[16] et Yandex ^[17] utilisent des variantes de gradient boosting dans leurs moteurs de classement appris par machine. L’amplification du gradient est également utilisée en physique des hautes énergies dans l’analyse des données. Au Large Hadron Collider (LHC), des variantes des réseaux de neurones profonds (DNN) à amplification de gradient ont réussi à reproduire les résultats de méthodes d’analyse sans apprentissage automatique sur des ensembles de données utilisés pour découvrir le boson de Higgs . ^[18]

Des noms

La méthode porte une variété de noms. Friedman a présenté sa technique de régression en tant que “Gradient Boosting Machine” (GBM). ^[5] Mason, Baxter et al. a décrit la classe abstraite généralisée d’algorithmes comme “amplification de gradient fonctionnel”. ^{[7] [8]} Friedman et al. décrire une avancée des modèles boostés par le gradient en tant qu’arbres de régression additive multiple (MART) ; ^[19] Elith et al. décrivent cette approche comme des “arbres de régression boostés” (BRT). ^[20]

Une implémentation open source populaire pour R l’appelle un “modèle de boosting généralisé”, ^[13] cependant les packages développant ce travail utilisent BRT. ^[21] Encore un autre nom est TreeNet, après une première mise en œuvre commerciale de Dan Steinberg de Salford System, l’un des chercheurs qui a été le pionnier de l’utilisation des méthodes basées sur les arbres. ^[22] XGBoost est une autre implémentation moderne populaire de la méthode avec quelques extensions, comme l’optimisation de second ordre.

Désavantages

Alors que le boosting peut augmenter la précision d’un apprenant de base, tel qu’un arbre de décision ou une régression linéaire, il sacrifie l’intelligibilité et l’ interprétabilité . ^{[1] [23]} Par exemple, suivre le chemin qu’un arbre de décision emprunte pour prendre sa décision est trivial et explicite, mais suivre les chemins de centaines ou de milliers d’arbres est beaucoup plus difficile. Pour atteindre à la fois les performances et l’interprétabilité, certaines techniques de compression de modèle permettent de transformer un XGBoost en un seul arbre de décision “né de nouveau” qui se rapproche de la même fonction de décision. ^[24] De plus, sa mise en œuvre peut être plus difficile en raison de la demande de calcul plus élevée.

Voir également

AdaBoost
Forêt aléatoire
Catboost
LightGBM
XGBoost
Apprentissage de l’arbre de décision

Références

^ ^un ^bc ^Piryonesi , S. Madeh; El-Diraby, Tamer E. (2020-03-01). “Analyse des données dans la gestion des actifs : prévision rentable de l’indice d’état des chaussées” . Journal des systèmes d’infrastructure . 26 (1): 04019036. doi : 10.1061/(ASCE)IS.1943-555X.0000512 . ISSN 1943-555X . S2CID 213782055 .
^ ^un ^bcde ^Hastie , ^T^.;Tibshirani, R.; Friedman, JH (2009). “10. Arbres de boosting et additifs” . Les éléments de l’apprentissage statistique (2e éd.). New York : Springer. pp. 337–384. ISBN 978-0-387-84857-0. Archivé de l’original le 10/11/2009.
^ Piryonesi, S. Madeh; El-Diraby, Tamer E. (2021-02-01). “Utilisation de l’apprentissage automatique pour examiner l’impact du type d’indicateur de performance sur la modélisation flexible de la détérioration de la chaussée” . Journal des systèmes d’infrastructure . 27 (2): 04021005. doi : 10.1061/(ASCE)IS.1943-555X.0000602 . ISSN 1076-0342 . S2CID 233550030 .
^ Breiman, L. (juin 1997). “Arcer le bord” (PDF) . Rapport technique 486 . Département de statistiques, Université de Californie, Berkeley.
^ ^un ^{bc Friedman,} ^JH (février 1999). “Rapproximation de la fonction gourmande: une machine à booster de gradient” (PDF) .
^ ^un ^{bc Friedman,} ^JH (mars 1999). “Amélioration du gradient stochastique” (PDF) .
^ ^un ^b Mason, L.; Baxter, J.; Bartlett, PL; Frean, Marcus (1999). “Boosting Algorithms as Gradient Descent” (PDF) . Dans SA Solla et TK Leen et K. Müller (éd.). Progrès dans les systèmes de traitement de l’information neuronale 12 . Presse du MIT. p. 512–518.
^ ^un ^b Mason, L.; Baxter, J.; Bartlett, PL; Frean, Marcus (mai 1999). “Boosting Algorithms as Gradient Descent in Function Space” (PDF) . Archivé de l’original (PDF) le 2018-12-22.
^ Cheng Li. “Une introduction en douceur à l’amplification des dégradés” (PDF) .
^ Lambers, Jim (session d’été 2011-12). “La méthode de Descente la plus raide” (PDF) . {{cite web}}: Vérifier les valeurs de date dans : |date=( aide )CS1 maint: url-status (link)
^ Remarque: dans le cas des arbres CART habituels, les arbres sont ajustés en utilisant la perte des moindres carrés, et donc le coefficient b j m {displaystyle b_{jm}} $b_{jm}$ $b_{jm}$ pour la région R j m {displaystyle R_{jm}} $R_{jm}$ $R_{jm}$ est égal à la valeur de la variable de sortie, moyennée sur toutes les instances d’entraînement dans R j m {displaystyle R_{jm}} $R_{jm}$ $R_{jm}$ .
^ Notez que ceci est différent de l’ensachage, qui échantillonne avec remplacement car il utilise des échantillons de la même taille que l’ensemble d’apprentissage.
^ ^un ^b Ridgeway, Greg (2007). Modèles boostés généralisés : guide du package gbm.
^ Apprendre Gradient Boosting Algorithm pour de meilleures prédictions (avec des codes en R)
^ Tian Qi Chen. Introduction aux arbres boostés
^ Cossock, David et Zhang, Tong (2008). Analyse statistique du classement optimal des sous-ensembles de Bayes Archivé le 07/08/2010 sur la Wayback Machine , page 14.
^ Entrée du blog d’entreprise Yandex sur le nouveau modèle de classement “Snezhinsk” (en russe)
^ Lalchand, Vidhi (2020). “Extraire plus des arbres de décision boostés: une étude de cas de physique des hautes énergies”. arXiv : 2001.06033 [ stat.ML ].
^ Friedman, Jérôme (2003). “Arbres de régression additive multiple avec application en épidémiologie”. Statistiques en médecine . 22 (9): 1365-1381. doi : 10.1002/sim.1501 . PMID 12704603 .
^ Élith, Jane (2008). “Un guide de travail pour les arbres de régression boostés” . Journal d’écologie animale . 77 (4): 802–813. doi : 10.1111/j.1365-2656.2008.01390.x . PMID 18397250 .
^ Élith, Jane. “Arbres de régression boostés pour la modélisation écologique” (PDF) . CRAN . CRAN . Récupéré le 31 août 2018 .
^ “Exclusif : Entretien avec Dan Steinberg, président de Salford Systems, Data Mining Pioneer” .
^ Wu, Xindong; Kumar, Vipin ; Ross Quinlan, J.; Gosh, Joydeep ; Yang, Qiang; Motoda, Hiroshi; McLachlan, Geoffrey J.; Ng, Angus ; Liu, Bing ; Yu, Philip S.; Zhou, Zhi-Hua (2008-01-01). “Les 10 meilleurs algorithmes d’exploration de données”. Connaissances et systèmes d’information . 14 (1): 1–37. doi : 10.1007/s10115-007-0114-2 . manche : 10983/15329 . ISSN 0219-3116 . S2CID 2367747 .
^ Sagi, Omer; Rokach, Lior (2021). “Rapprocher XGBoost avec un arbre de décision interprétable”. Sciences de l’information . 572 (2021): 522-542. doi : 10.1016/j.ins.2021.05.055 .

Lectures complémentaires

Boehmke, Bradley; Greenwell, Brandon (2019). “Amélioration du dégradé”. Apprentissage automatique pratique avec R . Chapman & Hall. p. 221–245. ISBN 978-1-138-49568-5.

Liens externes

Comment expliquer le gradient boosting
Arbres de régression boostés par gradient
LightGBM