16
$\begingroup$

I'm experimenting with the gradient boosting machine algorithm via the caret package in R.

Using a small college admissions dataset, I ran the following code:

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)

and found to my surprise that the model's cross-validation accuracy decreased rather than increased as the number of boosting iterations increased, reaching a minimum accuracy of about .59 at ~450,000 iterations.

enter image description here

Did I incorrectly implement the GBM algorithm?

EDIT: Following Underminer's suggestion, I've rerun the above caret code but focused on running 100 to 5,000 boosting iterations:

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)

The resulting plot shows that the accuracy actually peaks at nearly .705 at ~1,800 iterations:

enter image description here

What's curious is that the accuracy didn't plateau at ~.70 but instead declined following 5,000 iterations.

Improve this question
$\endgroup$

4 Answers 4

Reset to default
14
$\begingroup$

In general, boosting error can increase with the number of iterations, specifically when the data is noisy (e.g. mislabeled cases). I wouldn't be able to say if this is your problem without knowing more about your data

Basically, boosting can 'focus' on correctly predicting cases that contain misinformation, and in the process, deteriorate the average performance on other cases that are more substantive.

This link (Boosting and Noise) shows a better description than I can provide of the issue.

This paper (Random Classification Noise) by Long and Servedio provides more technical details of the issue.

Improve this answer
$\endgroup$
0
18
$\begingroup$

What you have displayed is a classic example of overfitting. The small uptick in error comes from poorer performance on the validation portion of your cross-validated data set. More iterations should nearly always improve the error on the training set, but the opposite is true for the validation/test set.

Improve this answer
$\endgroup$
5
  • $\begingroup$ So gradient boosting overfits based on # of boosting iterations? Interesting. I thought the accuracy would have instead plateaued after hitting the optimal # of iterations. $\endgroup$
    – RobertF
    Jun 1, 2016 at 18:06
  • 4
    $\begingroup$ That's correct. In gradient boosting, each subsequent tree is built off of the previous trees' residuals, so the GBM will continue to try cutting away at the remaining error on the training data set even at the cost of being able to generalize to validation/test sets. That's why you perform cross validation -- because the fitting algorithm doesn't natively know when to stop $\endgroup$
    – Ryan Zotti
    Jun 1, 2016 at 18:28
  • 1
    $\begingroup$ Gradient Boosting is inspired by AdaBoost. AdaBoost very rarely overfits and when it does, it's only slightly and after many, many iterations. I think that @Underminer explanation is more likely to be representative of what is going on than this comment, especially considering there is no references in this comment. $\endgroup$
    – Ricardo Magalhães Cruz
    Jun 8, 2016 at 8:07
  • 2
    $\begingroup$ @RicardoCruz I think it's interesting that you've rarely seen gradient boosting overfit. Over the four or so years that I've been using it, I've seen the opposite -- too many trees leads to overfitting. I once had to prove something similar to a colleague and I was able to reduce error on the training set to nearly zero, but the validation error went up significantly more than that of the non overfit GBM. I still think gradient boosting is a great algorithm. It's usually the first algorithm I use - you just have to be careful about too many trees, which you can track via cross validation $\endgroup$
    – Ryan Zotti
    Jun 8, 2016 at 14:03
  • 2
    $\begingroup$ @RyanZotti I stand corrected then. I have read a bunch of papers on AdaBoost from Schapire et al because I enjoy its beautiful strong theoretical basis. The authors argue that boosting is prone to overfitting, but that it is extremely difficult. I don't have much experience on using it, and they don't have a solid theoretical basis for arguing this, and, of course, authors being authors, they are naturally zealous of their invention, so if you have experience to the contrary, I stand corrected. $\endgroup$
    – Ricardo Magalhães Cruz
    Jun 16, 2016 at 8:48
6
$\begingroup$

Codes to reproduce a similar result, without grid search,

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
Improve this answer
$\endgroup$
0
5
$\begingroup$

The gbm package has a function to estimate the optimal # of iterations (= # of trees, or # of basis functions),

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

You don't need caret's train for that.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't know if that solves the issue I'm having - it appears the optimal # of iterations is 5,000 in my case where the accuracy is at its highest, close to 0.70 (the first data point in my plot). But that seems wrong. More iterations should lead to a higher accuracy, not lower, right? $\endgroup$
    – RobertF
    Jun 1, 2016 at 17:44
  • 1
    $\begingroup$ @RobertF First, I think you don't need to turn admit into a factor. It works just as well : 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). You can see where gbm chooses the optimal iter by : best.iter <- gbm.perf(mod, method="OOB", plot.it=TRUE, oobag.curve=TRUE, overlay=TRUE). That is, when the change in deviance turns negative (see the plot generated from this). $\endgroup$
    – horaceT
    Jun 1, 2016 at 18:09
  • 1
    $\begingroup$ @RobertF One more thing. By specifying n.trees=(one million) in the gbm call, you would have run all numbers of iterations from 1 to 1,000,000. So you don't need caret to do that for you. $\endgroup$
    – horaceT
    Jun 1, 2016 at 18:29
  • 1
    $\begingroup$ @RobertF More follow up. I just ran 100k trees/iterations. The accuracy I got by choosing the best iteration with gbm.perf is 0.7225, which is pretty close to yours running a full grid of iterations. $\endgroup$
    – horaceT
    Jun 1, 2016 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.