15
$\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.

$\endgroup$
14
$\begingroup$

In general, boosting error can increase with the number of iterations, specifically when the data is noisy (e.g. mislabeled cases). This could be your issue, but I wouldn't be able to say 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.

$\endgroup$
16
$\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.

$\endgroup$
  • $\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 '16 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 '16 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 Cruz Jun 8 '16 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 '16 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 Cruz Jun 16 '16 at 8:48
4
$\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
$\endgroup$
3
$\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.

$\endgroup$
  • $\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 '16 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 '16 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 '16 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 '16 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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