2

I have a record of data that contains 1.1 millions observations and 14 variables. The response is 0 or 1. It was suggested to me that I use Gradient Boosted Trees to build my logistic model.

Using xgb.cv from xgboost in R, I'm attempting to estimate the best hyperparameters on a holdout of 2/3 of the data. However, the code takes forever to run. It took me 13 hours for learning rate = 0.5, depth = 7, number of folds = 5 and number of trees = 10000. I can't imagine the time it will take to loop over different learning rates and depths.

How could I make the process faster? I guess that reducing the number of trees to 2500 would make sense, based on my error curve. Will reducing the number of folds help? Is it really necessary to do bootstrapping?

My current code looks like this, for reference :

etas = c(0.75,0.5,0.1)
max.depths = c(11,9,7,5,3)
fitAssessmentLst = list()
lstPos = 0
for(eta in etas){
  for(max.depth in max.depths){
    lstPos = lstPos + 1
    x = xgb.cv(params = list(objective="binary:logistic", eta=eta, 
        max.depth=max.depth, nthread=3),
        data = train_data.xgbdm,
        nrounds = 10000,
        prediction = FALSE,
        showsd = TRUE, 
        nfolds = 5,
        verbose = 0,
        print.every.n = 1,
        early.stop.round = NULL
        )
    fitAssessmentLst[[lstPos]] = list(eta = eta, max.depth = max.depth, assessmentTbl = x)
  }
}
Sycorax
  • 90,934
jgadoury
  • 121
  • 3
    related: http://stats.stackexchange.com/questions/193306/optimization-when-cost-function-slow-to-evaluate/193310#193310 also, you probably have way more trees than are necessary. and row subsampling can dramatically improve training time and create a more robust model – Sycorax Sep 07 '16 at 15:54
  • 1
    Row subsampling doesn't speed xgboost up much at all, I think because it bins IVs upfront for large data. Column subsampling does however have a huge and pretty much linear impact. – Dex Groves Sep 07 '16 at 16:03
  • 1
    I couldn't agree more with the General. A learning rate of 0.5 and 10000 trees seems a bizarre setup. Have you checked the learning curves? Are the 9900 last trees really needed? I would recommend a learning rate of 0.3, 100 trees and features engineering. – Adrien Renaud Sep 07 '16 at 16:24
  • 1
    Also I would be interested in knowing which version of XGBoost you are using. I have seen some performance differences between the master branch and old versions... – Adrien Renaud Sep 07 '16 at 16:31
  • 2
    You should be using early.stop.round along with a hold out or cross validation so that the algorithm will stop short of your 10000 trees. This is a very nice feature of xgboost you should utilize. – Matthew Drury Sep 07 '16 at 16:37
  • One point of boosting is that it doesn't need initial learners to produce good end results. You may find that stumps (depth =1) produces very good results. – meh Sep 07 '16 at 16:46
  • @GeneralAbrial Thanks for that suggestion, there is a very detailed example in the rBayesianOptimization package that uses xgb.cv. I'll give it a shot. – jgadoury Sep 07 '16 at 16:57
  • @AdrienRenaud The error seemed to stabilize after 2000 trees, with a learning rate of 0.5. The version of xgboost is 0.4-4 – jgadoury Sep 07 '16 at 16:58
  • @MatthewDrury I forgot to mention that I am using a 2/3 holdout, I added it to the question. What would be a reasonable k to use for early.stop.round? – jgadoury Sep 07 '16 at 17:00
  • @Sycorax How does row subsampling make a more robust model? I am running xgb.cv using 1/10 of my data, which seems to really decrease the runtime, but I'm worried that my hyperparamaters won't translate well to the full dataset. I tried Bayes Optimization and it was still slow as hell. Around 100 minutes per iteration using 2500 rounds. – jgadoury Sep 08 '16 at 19:35
  • @jgadoury It can increase robustness in a manner analogous to how it works in random forest -- shaking up how the trees get built. The point isn't to identify hyperparameters and then fit a model without subsampling but to use subsampling as part of the model construction. Bayesian opt doesn't make model estimation faster, it just makes hyper-parameter tuning intelligent. Grid search doesn't use info from other models to make decisions about where to go next; BO does. – Sycorax Sep 08 '16 at 19:38
  • @Sycorax How does one do row subsampling in xgb.cv? I tried to find an option that I don't see it. Do you recommend using sample before each iteration? – jgadoury Sep 08 '16 at 19:50
  • I don't know how the R package works. – Sycorax Sep 08 '16 at 20:53

2 Answers2

3

It took me 13 hours for learning rate = 0.5, depth = 7, number of folds = 5 and number of trees = 10000.

The quickest & easiest way to make this faster is to use xgboost's early stopping feature, as suggested in the comments. The way it works is that you supply a hold-out set to the model, and specify a positive integer. The integer specifies the number of rounds to continue boosting even if the loss increases on the hold-out data. For example, if you specify 3, boosting rounds will continue if the loss increases for 2 rounds on the hold-out, but then decreases on the third round. But if the loss increases for three consecutive rounds, boosting terminates. (Boosting will also terminate if you exhaust the number of boosting rounds - in your case, 10000.)

The reason that this is useful is that it provides a principled - in the sense that it stops when hold out performance declines - way for you to terminate training without having to specify the number of boosting rounds ahead of time. The procedure is a little arbitrary in that choosing different integers can dramatically change the number of boosting rounds.

The reason that you specify an integer as part of the procedure is that it's often true that the loss on the holdout data will transiently increase before decreasing again. This pattern persists until the loss consistently increases, where "consistent" is defined in the rather ad hoc manner of the positive integer.

It's not a perfect system, but it works well enough in practice.

As an aside, with a learning rate as high as 0.5, it's often true that early stopping will terminate training in maybe a dozen rounds of boosting. The sweet spot for the learning rate is somewhere between 0.05 and 0.2 in my experience. A decrease in the learning rate often increases the number of boosting rounds (when you're using early stopping) and yields an improved out-of-sample loss. So there's a little bit of a trade-off between how long you want to wait for results, and how many trees you want (more trees makes the model size larger, so it's not always a trivial concern) and how good the model is.

To answer the titular question, I've heard from colleagues that LightGBM is a faster gradient boosted tree package. I don't have any definitive evidence to substantiate that claim.

Sycorax
  • 90,934
1

Try to make your numeric features categorical by digitizing them. If you digitize the features, you can also one-hot-encode them. By that you will get rid of unnecessary floating point as well as having a sparse dataset which will enable you considerable efficiency.

LightGBM is swifter by its natural depth-wise tree approach compared to XGBoost's level-wise approach and thanks to its booster: Gradient-One-Sided-Sampling[1]. Moreover, if you have a sparse dataset, its Effective-Feature-Bundling (EFB) skill will boost the computation efficiency sharply[1]. I recommend you to try LightGBM, it solves speed without losing accuracy[1].

Here is your evidence (also experimented but nevermind):

https://papers.nips.cc/paper/6907-lightgbm-a-highly-efficient-gradient-boosting-decision-tree][1]

Have fun.

Ugur MULUK
  • 172