La précision de la machine augmentant le gradient diminue à mesure que le nombre d'itérations augmente

15

J'expérimente l'algorithme de la machine de renforcement de gradient via le caretpackage en R.

À l'aide d'un petit ensemble de données d'admission à l'université, j'ai exécuté le code suivant:

library(caret)

### Load admissions dataset. ###
mydata <- read.csv("http://www.ats.ucla.edu/stat/data/binary.csv")

### Create yes/no levels for admission. ### 
mydata$admit_factor[mydata$admit==0] <- "no"
mydata$admit_factor[mydata$admit==1] <- "yes"             

### Gradient boosting machine algorithm. ###
set.seed(123)
fitControl <- trainControl(method = 'cv', number = 5, summaryFunction=defaultSummary)
grid <- expand.grid(n.trees = seq(5000,1000000,5000), interaction.depth = 2, shrinkage = .001, n.minobsinnode = 20)
fit.gbm <- train(as.factor(admit_factor) ~ . - admit, data=mydata, method = 'gbm', trControl=fitControl, tuneGrid=grid, metric='Accuracy')
plot(fit.gbm)

et j'ai constaté à ma grande surprise que la précision de validation croisée du modèle a diminué plutôt qu'augmenté à mesure que le nombre d'itérations de renforcement augmentait, atteignant une précision minimale d'environ 0,59 à ~ 450 000 itérations.

entrez la description de l'image ici

Ai-je mal implémenté l'algorithme GBM?

EDIT: Suite à la suggestion d'Underminer, j'ai réexécuté le caretcode ci-dessus mais concentré sur l'exécution de 100 à 5 000 itérations de boost:

set.seed(123)
fitControl <- trainControl(method = 'cv', number = 5, summaryFunction=defaultSummary)
grid <- expand.grid(n.trees = seq(100,5000,100), interaction.depth = 2, shrinkage = .001, n.minobsinnode = 20)
fit.gbm <- train(as.factor(admit_factor) ~ . - admit, data=mydata, method = 'gbm', trControl=fitControl, tuneGrid=grid, metric='Accuracy')
plot(fit.gbm)

Le graphique résultant montre que la précision culmine à près de 0,705 à environ 1800 itérations:

entrez la description de l'image ici

Ce qui est curieux, c'est que la précision n'a pas atteint un plateau à ~ 0,70 mais a plutôt diminué après 5 000 itérations.

RobertF
la source

Réponses:

14

En général, l'augmentation de l'erreur peut augmenter avec le nombre d'itérations, en particulier lorsque les données sont bruyantes (par exemple, les cas mal étiquetés). Cela pourrait être votre problème, mais je ne pourrais pas dire sans en savoir plus sur vos données

Fondamentalement, le renforcement peut «se concentrer» sur la prévision correcte des cas contenant des informations erronées et, ce faisant, dégrader les performances moyennes d'autres cas plus substantiels.

Ce lien ( Boosting and Noise ) montre une meilleure description que je peux fournir du problème.

Cet article ( Random Classification Noise ) de Long et Servedio fournit des détails techniques sur le problème.

Underminer
la source
16

Ce que vous avez affiché est un exemple classique de sur-ajustement. La petite hausse par erreur provient de performances médiocres sur la partie validation de votre ensemble de données à validation croisée. Plus d'itérations devraient presque toujours améliorer l'erreur sur l'ensemble d'apprentissage, mais l'inverse est vrai pour l'ensemble de validation / test.

Ryan Zotti
la source
Donc, des sur-ajustements de renforcement de gradient basés sur le nombre d'itérations de renforcement? Intéressant. Je pensais que la précision aurait plutôt atteint un plateau après avoir atteint le nombre optimal d'itérations.
RobertF
4
C'est correct. Dans le renforcement de gradient, chaque arbre suivant est construit à partir des résidus des arbres précédents, de sorte que le GBM continuera d'essayer de supprimer l'erreur restante sur l'ensemble de données d'apprentissage, même au prix de pouvoir généraliser aux ensembles de validation / test. C'est pourquoi vous effectuez une validation croisée - parce que l'algorithme d'ajustement ne sait pas nativement quand s'arrêter
Ryan Zotti
1
Gradient Boosting est inspiré par AdaBoost. AdaBoost sur-adapte très rarement et quand c'est le cas, ce n'est que légèrement et après de très nombreuses itérations. Je pense que l'explication @Underminer est plus susceptible d'être représentative de ce qui se passe que ce commentaire, d'autant plus qu'il n'y a aucune référence dans ce commentaire.
Ricardo Cruz
2
@RicardoCruz Je pense qu'il est intéressant que vous ayez rarement vu une sur-amplification augmentant le dégradé. Depuis environ quatre ans que je l'utilise, j'ai vu le contraire - trop d'arbres conduisent à un sur-ajustement. Une fois, j'ai dû prouver quelque chose de similaire à un collègue et j'ai pu réduire l'erreur sur l'ensemble de formation à presque zéro, mais l'erreur de validation a augmenté de manière beaucoup plus importante que celle du GBM non surchargé. Je pense toujours que le renforcement du gradient est un excellent algorithme. C'est généralement le premier algorithme que j'utilise - il suffit de faire attention à trop d'arbres, que vous pouvez suivre via la validation croisée
Ryan Zotti
2
@RyanZotti Je me corrige alors. J'ai lu un tas d'articles sur AdaBoost de Schapire et al parce que j'apprécie sa belle base théorique solide. Les auteurs soutiennent que la stimulation est sujette au sur-ajustement, mais qu'elle est extrêmement difficile. Je n'ai pas beaucoup d'expérience sur son utilisation, et ils n'ont pas de base théorique solide pour argumenter cela, et, bien sûr, les auteurs étant des auteurs, ils sont naturellement zélés de leur invention, donc si vous avez une expérience contraire , Je me suis trompé.
Ricardo Cruz
4

Codes pour reproduire un résultat similaire, sans recherche de grille,

mod = gbm(admit ~ .,
      data = mydata[,-5],
      n.trees=100000,
      shrinkage=0.001,
      interaction.depth=2,
      n.minobsinnode=10,
      cv.folds=5,
      verbose=TRUE,
      n.cores=2)

best.iter <- gbm.perf(mod, method="OOB", plot.it=TRUE, oobag.curve=TRUE, overlay=TRUE)
print(best.iter)
[1] 1487
pred = as.integer(predict(mod, newdata=mydata[,-5], n.trees=best.iter) > 0)
y = mydata[,1]
sum(pred == y)/length(y)
[1] 0.7225
horaceT
la source
3

Le paquet gbm a une fonction pour estimer le nombre optimal d'itérations (= nombre d'arbres ou nombre de fonctions de base),

gbm.perf(mod, method="OOB", plot.it=TRUE, oobag=TRUE, overlay=TRUE)

Vous n'avez pas besoin du train de caret pour cela.

horaceT
la source
Je ne sais pas si cela résout le problème que j'ai - il semble que le nombre optimal d'itérations est de 5 000 dans mon cas, où la précision est à son plus haut, proche de 0,70 (le premier point de données de mon graphique). Mais cela semble faux. Plus d'itérations devraient conduire à une précision plus élevée, pas inférieure, non?
RobertF
1
@RobertF Tout d'abord, je pense que vous n'avez pas besoin de transformer l'admission en facteur. Cela fonctionne aussi bien: mod = gbm (admit ~., Data = mydata [, - 5], n.trees = 100000, shrinkage = 0.001, interaction.depth = 2, n.minobsinnode = 10, cv.folds = 5 , verbose = TRUE, n.cores = 2). Vous pouvez voir où gbm choisit l'iter optimal par: best.iter <- gbm.perf (mod, method = "OOB", plot.it = TRUE, oobag.curve = TRUE, overlay = TRUE). Autrement dit, lorsque le changement de déviance devient négatif (voir le graphique généré à partir de cela).
horaceT
1
@RobertF Encore une chose. En spécifiant n.trees = (un million) dans l'appel gbm, vous auriez exécuté tous les nombres d'itérations de 1 à 1 000 000. Vous n'avez donc pas besoin de curseur pour le faire pour vous.
horaceT
1
@RobertF Plus de suivi. Je viens d'exécuter 100 000 arbres / itérations. La précision que j'ai obtenue en choisissant la meilleure itération avec gbm.perf est de 0,7225, ce qui est assez proche du vôtre avec une grille complète d'itérations.
horaceT