How are samples selected from training data in Xgboost

Question

In Random Forest, each tree is not fed with the full batch of training data, only a sample.

How does this work for Xgboost? If this sampling happens as well, how does it work for this ML algorithm?

Answer 1

In Gradient Boosting the simple tree is built for only a randomly selected sub-sample of the full data set (random without replacement).

While on the other hand, Random Forest the samples for each decision tree are selected via bootstrapping; sampling a dataset with replacement.

Particularly for xgboost (see paper here)the ratio of sampling of each tree can be modified with the following hyperparameter:

• subsample [default=1]

Subsample ratio of the training instances. Setting it to 0.5 means that XGBoost would randomly sample half of the training data prior to growing trees. and this will prevent overfitting. Subsampling will occur once in every boosting iteration.

There are more parameters such as colsample_bytree, colsample_bylevel, colsample_bynode.

Bootstrapping techniques can vary with the implementation and. Normally I use Catboost implementation for several reasons.

You can read about the sampling of cb that you can use in the documentation here

Moreover, a paper that I found interesting a bit ago is Minimal Variance Sampling in Stochastic Gradient Boosting . I will quote one of the sentences from the abstract

Different sampling approaches were proposed, where probabilities are not uniform, and it is not currently clear which approach is the most effective...it leads to a new sampling technique, which we call Minimal Variance Sampling (MVS)...The superiority of the algorithm was confirmed by introducing MVS as a new default option for subsampling in CatBoost

Here the Catboost development team explains what is the new sampling technique that is the default in their algorithm.

Answer 2

I agree with ‘Carlos Mougan,’ and add the comparison with these models.

Basically, GB(Breiman 1996, 1999)、SGB(Friedman 2002) and XGB(Chen and Guestrin 2016) do sampling w/o replacement. GB uses the full sample set for each iteration. Thus, GB performs like sampling w/o replacement. So, the three use sampling w/o replacement by tradition.

However, bagging and RF(Breiman 2001) do sampling w/ replacement. So, the two use sampling w/ replacement by tradition.

---

There are some discussion between sampling w/ or w/o replacement. Binder and Schumacher (2008) run an experiment, model sampling w/o replacement coverge faster.

LGB(using GOSS, play a role of ‘hard example mining’)(Ke et al. 2017) and CatBoost(using Minimal Variance Sampling)(Prokhorenkova et al. 2018; Ibragimov and Gusev 2019) perform sampling by weights, thus both build the subset over iteration w/ replacement.

---

Binder, Harald, and Martin Schumacher. 2008. “Adapting Prediction Error Estimates for Biased Complexity Selection in High-Dimensional Bootstrap Samples.” Statistical Applications in Genetics and Molecular Biology 7 (1).

Breiman, Leo. 1996. “Bagging Predictors.” Machine Learning 24 (2): 123–40.

———. 1999. “Using Adaptive Bagging to Debias Regressions.” Technical Report 547, Statistics Dept. UCB.

———. 2001. “Random Forests.” Machine Learning 45 (1): 5–32.

Chen, Tianqi, and Carlos Guestrin. 2016. “Xgboost: A Scalable Tree Boosting System.” In Proceedings of the 22nd Acm Sigkdd International Conference on Knowledge Discovery and Data Mining, 785–94.

Friedman, Jerome H. 2002. “Stochastic Gradient Boosting.” Computational Statistics & Data Analysis 38 (4): 367–78.

Ibragimov, Bulat, and Gleb Gusev. 2019. “Minimal Variance Sampling in Stochastic Gradient Boosting.” Advances in Neural Information Processing Systems 32: 15087–97.

Ke, Guolin, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu. 2017. “Lightgbm: A Highly Efficient Gradient Boosting Decision Tree.” Advances in Neural Information Processing Systems 30: 3146–54.

Prokhorenkova, Liudmila Ostroumova, Gleb Gusev, Aleksandr Vorobev, Anna Veronika Dorogush, and Andrey Gulin. 2018. “CatBoost: Unbiased Boosting with Categorical Features.” In NeurIPS.