xgboost论文发表在

优化的分布式梯度提升算法，end-to-end 不需要特征抽取。输入原始数据，就能输出目标结果。 整篇论文技术实现分两个部分显而易见，xgboost是非线性(Tree)的加法模型如果是回归问题则可能是：                                                                                    而分类问题则应该是交叉熵, 此处 ： 二分类问题： 多分类问题： 这里review一下，对于多分类及二分类，交叉熵及soft公式，二分类均是多分类的特例 : ： 原文描述：Default direction, 按我的理解应该是：每轮迭代，每颗树对待一个特征缺失的方向处理应该是一致的，但是不同特征的缺失方向是随机的；不同的迭代子树，策略也是随机的在建树的过程中，最耗时是找最优的切分点，而这个过程中，最耗时的部分是 将数据排序 。为了减少排序的时间，Xgboost采用 Block结构 存储数据(Data in each block is stored in the compressed column (CSC) format, with each column sorted by the corresponding feature value) 对于approximate算法来说，Xgboost使用了多个Block，存在多个机器上或者磁盘中。每个Block对应原来数据的子集。不同的Block可以在不同的机器上计算。该方法对Local策略尤其有效，因为Local策略每次分支都重新生成候选切分点。使用Block结构的一个缺点是取梯度的时候，是通过索引来获取的，而这些梯度的获取顺序是按照特征的大小顺序的。这将导致非连续的内存访问，可能使得CPU cache缓存命中率低，从而影响算法效率在非近似的贪心算法中， 使用 缓存预取（cache-aware prefetching） 。具体来说，对每个线程分配一个连续的buffer，读取梯度信息并存入Buffer中（这样就实现了非连续到连续的转化），然后再统计梯度信息 在近似 算法中，对Block的大小进行了合理的设置。 定义Block的大小为Block中最多的样本数 。设置合适的大小是很重要的，设置过大则容易导致命中率低，过小则容易导致并行化效率不高。经过实验，发现2^16比较好当数据量太大不能全部放入主内存的时候，为了使得out-of-core计算称为可能，将数据划分为多个Block并存放在磁盘上。计算的时候，使用独立的线程预先将Block放入主内存，因此可以在计算的同时读取磁盘。但是由于磁盘IO速度太慢，通常更不上计算的速度。因此，需要提升磁盘IO的销量。Xgboost采用了2个策略： Block压缩（Block Compression）：将Block按列压缩（LZ4压缩算法？），读取的时候用另外的线程解压。对于行索引，只保存第一个索引值，然后只保存该数据与第一个索引值之差(offset)，一共用16个bits来保存 offset，因此，一个block一般有2的16次方个样本。 Block拆分（Block Sharding）：将数据划分到不同磁盘上，为每个磁盘分配一个预取（pre-fetcher）线程，并将数据提取到内存缓冲区中。然后，训练线程交替地从每个缓冲区读取数据。这有助于在多个磁盘可用时增加磁盘读取的吞吐量。[1]  R. Bekkerman. The present and the future of the kdd cup competition: an outsider’s perspective. (xgboost应用) [2]  R. Bekkerman, M. Bilenko, and J. Langford. Scaling Up Machine Learning: Parallel and Distributed Approaches. Cambridge University Press, New York, NY, USA, 2011.(并行分布式设计) [3]  J. Bennett and S. Lanning. The netflix prize. In Proceedings of the KDD Cup Workshop 2007, pages 3–6, New York, Aug. 2007.(xgboost应用) [4]  L. Breiman. Random forests. Maching Learning, 45(1):5–32, Oct. 2001.(Breiman随机森林论文) [5]  C. Burges. From ranknet to lambdarank to lambdamart: An overview. Learning, 11:23–581, 2010. [6]  O. Chapelle and Y. Chang. Yahoo! Learning to Rank Challenge Overview. Journal of Machine Learning Research - W & CP, 14:1–24, 2011.(xgboost应用) [7]  T. Chen, H. Li, Q. Yang, and Y. Yu. General functional matrix factorization using gradient boosting. In Proceeding of 30th International Conference on Machine Learning(通过梯度提升的方法来实现general的矩阵分解) (ICML’13), volume 1, pages 436–444, 2013. [8] T. Chen, S. Singh, B. Taskar, and C. Guestrin. Efficient second-order gradient boosting for conditional random fields. In Proceeding of 18th Artificial Intelligence and Statistics Conference (AISTATS’15), volume 1, 2015.(二阶导boost实现的条件随机场) [9] R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin. LIBLINEAR: A library for large linear classification. Journal of Machine Learning Research, 9:1871–1874, 2008.(xgboost应用) [10] J. Friedman. Greedy function approximation: a gradient boosting machine. Annals of Statistics, 29(5):1189–1232, 2001.(gbm的贪心算法实现) [11] J. Friedman. Stochastic gradient boosting. Computational Statistics & Data Analysis, 38(4):367–378, 2002. (随机梯度下降) [12] J. Friedman, T. Hastie, and R. Tibshirani. Additive logistic regression: a statistical view of boosting. Annals of Statistics, 28(2):337–407, 2000.(叠加式的逻辑回归方式) [13] J. H. Friedman and B. E. Popescu. Importance sampled learning ensembles, 2003.(采样学习) [14] M. Greenwald and S. Khanna. Space-efficient online computation of quantile summaries. In Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, pages 58–66, 2001. [15] X. He, J. Pan, O. Jin, T. Xu, B. Liu, T. Xu, Y. Shi, A. Atallah, R. Herbrich, S. Bowers, and J. Q. n. Candela. Practical lessons from predicting clicks on ads at facebook. In  Proceedings of the Eighth International Workshop on Data Mining for Online Advertising, ADKDD’14, 2014.(xgboost应用) [16] P. Li. Robust Logitboost and adaptive base class (ABC) Logitboost. In Proceedings of the Twenty-Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI’10), pages 302–311, 2010.(logitboost) [17] P. Li, Q. Wu, and C. J. Burges. Mcrank: Learning to rank using multiple classification and gradient boosting. In Advances in Neural Information Processing Systems 20, pages 897–904. 2008.(多分类应用) [18] X. Meng, J. Bradley, B. Yavuz, E. Sparks, S. Venkataraman, D. Liu, J. Freeman, D. Tsai, M. Amde, S. Owen, D. Xin, R. Xin, M. J. Franklin, R. Zadeh, M. Zaharia, and A. Talwalkar. MLlib: Machine learning in apache spark.  Journal of Machine Learning Research, 17(34):1–7, 2016.(分布式机器学习设计) [19] B. Panda, J. S. Herbach, S. Basu, and R. J. Bayardo. Planet: Massively parallel learning of tree ensembles with mapreduce. Proceeding of VLDB Endowment, 2(2):1426–1437, Aug. 2009.(分布式机器学习设计) [20] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python.  Journal of Machine Learning Research, 12:2825–2830, 2011.(sklearn) [21] G. Ridgeway. Generalized Boosted Models: A guide to the gbm package. [22] S. Tyree, K. Weinberger, K. Agrawal, and J. Paykin. Parallel boosted regression trees for web search ranking. In Proceedings of the 20th international conference on World wide web, pages 387–396. ACM, 2011. [23] J. Ye, J.-H. Chow, J. Chen, and Z. Zheng. Stochastic gradient boosted distributed decision trees. In Proceedings of the 18th ACM Conference on Information and Knowledge Management, CIKM ’09. [24] Q. Zhang and W. Wang. A fast algorithm for approximate quantiles in high speed data streams. In Proceedings of the 19th International Conference on Scientific and Statistical Database Management, 2007.(数据处理加速计算) [25] T. Zhang and R. Johnson. Learning nonlinear functions using regularized greedy forest. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(5), 2014.

前言： xgboost是大规模并行boosted tree的工具，它是目前最快最好的开源boosted tree工具包，比常见的工具包快10倍以上。在数据科学方面，有大量kaggle选手选用它进行数据挖掘比赛，其中包括两个以上kaggle比赛的夺冠方案。在工业界规模方面，xgboost的分布式版本有广泛的可移植性，支持在YARN, MPI, Sungrid Engine等各个平台上面运行，并且保留了单机并行版本的各种优化，使得它可以很好地解决于工业界规模的问题。 花了几天时间粗略地看完了xgboost原论文和作者的slide讲解，仅仅是入门入门入门笔记。给我的感觉就是xgboost算法比较复杂，针对传统GBDT算法做了很多细节改进，包括损失函数、正则化、切分点查找算法优化、稀疏感知算法、并行化算法设计等等。本文主要介绍xgboost基本原理以及与传统gbdt算法对比总结，后续会基于Python版本做了一些实战调参试验。想详细学习xgboost算法原理建议通读作者原始论文与slide讲解。 相关文献资料： Xgboost Slides XGBoost中文版原理介绍 原始论文XGBoost: A Scalable Tree Boosting System XGBoost Parameters (official guide) 精彩博文： XGBoost浅入浅出——wepon xgboost: 速度快效果好的boosting模型 Complete Guide to Parameter Tuning in XGBoost (with codes in Python) 一、xgboost基本原理介绍 1.提升方法是一种非常有效的机器学习方法，在前几篇笔记中介绍了提升树与GBDT基本原理，xgboost（eXtreme Gradient Boosting）可以说是提升方法的完全加强版本。xgboost算法在各大比赛中展现了强大的威力，引用原论文中的一段描述： The impact of the system has been widely recognized in a number of machine learning and data mining challenges. Take the challenges hosted by the machine learning competition site Kaggle for example. Among the 29 challenge winning solutions published at Kaggle’s blog during 2015, 17 solutions used XGBoost. Among these solutions, eight solely used XGBoost to train the model,while most others combined XGBoost with neural nets in ensembles. For comparison, the second most popular method,deep neural nets, was used in 11 solutions. The success of the system was also witnessed in KDDCup 2015, where XGBoost was used by every winning team in the top-10.Moreover, the winning teams reported that ensemble methods outperform a well-configured XGBoost by only a small amount. 2.Regression Tree and Ensemble (What are we Learning，得到学习目标) （1）.Regression Tree (CART)回归树 （2）.Regression Tree Ensemble 回归树集成 在上面的例子中，我们用两棵树来进行预测。我们对于每个样本的预测结果就是每棵树预测分数的和。 （3）.Objective for Tree Ensemble 得到学习目标函数 这里是构造一个目标函数，然后我们要做的就是去尝试优化这个目标函数。读到这里，感觉与gbdt好像没有什么区别，确实如此，不过在后面就能看到他们的不同了（构造（学习）模型参数）。 3.Gradient Boosting (How do we Learn，如何学习) （1）.So How do we Learn? 目标函数： （2）.Additive Training（3）.Taylor Expansion Approximation of Loss 泰勒近似展开把平方损失函数的一二次项带入原目标函数，你会发现与之前那张ppt的损失函数是一致的 （4）.Our New Goal 得到新的学习目标函数 从这里就可以看出xgboost的特点了，目标函数保留了泰勒展开的二次项。 （5）.Refine the definition of tree 重新定义每棵树（6）.Define the Complexity of Tree 树的复杂度项从图中可以看出，xgboost算法中对树的复杂度项增加了一个L2正则化项，针对每个叶结点的得分增加L2平滑，目的也是为了避免过拟合。 （7）.Revisit the Objectives （8）.The Structure Score 这个score你可以理解成类似于信息增益的一个指标，在切分点查找算法中用到。 （9）切分点查找算法（贪心算法） 上图中G都是各自区域内的gi总和，此外，作者针对算法设计对特征进行了排序，有兴趣的可以阅读原始论文，这里不做详解。二、xgboost特点（与gbdt对比） 说明一下：这部分内容参考了知乎上的一个问答—机器学习算法中GBDT和XGBOOST的区别有哪些？，答主是wepon大神，根据他的总结我自己做了一理解和补充。 1.传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。 —可以通过booster [default=gbtree]设置参数:gbtree: tree-based models/gblinear: linear models 2.传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。 —对损失函数做了改进（泰勒展开，一阶信息g和二阶信息h,上一章节有做介绍） 3.xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性 —正则化包括了两个部分，都是为了防止过拟合，剪枝是都有的，叶子结点输出L2平滑是新增的。 4.shrinkage and column subsampling —还是为了防止过拟合，论文2.3节有介绍，这里答主已概括的非常到位 （1）shrinkage缩减类似于学习速率，在每一步tree boosting之后增加了一个参数n（权重），通过这种方式来减小每棵树的影响力，给后面的树提供空间去优化模型。 （2）column subsampling列(特征)抽样，说是从随机森林那边学习来的，防止过拟合的效果比传统的行抽样还好（行抽样功能也有），并且有利于后面提到的并行化处理算法。 5.split finding algorithms(划分点查找算法)：—理解的还不够透彻，需要进一步学习 （1）exact greedy algorithm—贪心算法获取最优切分点 （2）approximate algorithm— 近似算法，提出了候选分割点概念，先通过直方图算法获得候选分割点的分布情况，然后根据候选分割点将连续的特征信息映射到不同的buckets中，并统计汇总信息。详细见论文3.3节 （3）Weighted Quantile Sketch—分布式加权直方图算法，论文3.4节 这里的算法（2）、（3）是为了解决数据无法一次载入内存或者在分布式情况下算法（1）效率低的问题，以下引用的还是wepon大神的总结： 可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。 6.对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。 —稀疏感知算法，论文3.4节，Algorithm 3: Sparsity-aware Split Finding 7.Built-in Cross-Validation（内置交叉验证) XGBoost allows user to run a cross-validation at each iteration of the boosting process and thus it is easy to get the exact optimum number of boosting iterations in a single run. This is unlike GBM where we have to run a grid-search and only a limited values can be tested. 8.continue on Existing Model（接着已有模型学习） User can start training an XGBoost model from its last iteration of previous run. This can be of significant advantage in certain specific applications. GBM implementation of sklearn also has this feature so they are even on this point. 9.High Flexibility（高灵活性） **XGBoost allow users to define custom optimization objectives and evaluation criteria. This adds a whole new dimension to the model and there is no limit to what we can do.** 10.并行化处理 —系统设计模块,块结构设计等 xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。 此外xgboost还设计了高速缓存压缩感知算法，这是系统设计模块的效率提升。 当梯度统计不适合于处理器高速缓存和高速缓存丢失时，会大大减慢切分点查找算法的速度。 （1）针对 exact greedy algorithm采用缓存感知预取算法 （2）针对 approximate algorithms选择合适的块大小 我觉得关于xgboost并行化设计仅仅从论文PPT博客上学习是远远不够的，有时间还要从代码层面去学习分布式 xgboost的设计理念。 三、xgboost参数详解 官方参数介绍看这里： Parameters (official guide) General Parameters（常规参数） 1.booster [default=gbtree]：选择基分类器，gbtree: tree-based models/gblinear: linear models 2.silent [default=0]:设置成1则没有运行信息输出，最好是设置为0. 3.nthread [default to maximum number of threads available if not set]：线程数 Booster Parameters（模型参数） 1.eta [default=0.3]:shrinkage参数，用于更新叶子节点权重时，乘以该系数，避免步长过大。参数值越大，越可能无法收敛。把学习率 eta 设置的小一些，小学习率可以使得后面的学习更加仔细。 2.min_child_weight [default=1]:这个参数默认是 1，是每个叶子里面 h 的和至少是多少，对正负样本不均衡时的 0-1 分类而言，假设 h 在 0.01 附近，min_child_weight 为 1 意味着叶子节点中最少需要包含 100 个样本。这个参数非常影响结果，控制叶子节点中二阶导的和的最小值，该参数值越小，越容易 overfitting。 3.max_depth [default=6]: 每颗树的最大深度，树高越深，越容易过拟合。 4.max_leaf_nodes:最大叶结点数，与max_depth作用有点重合。 5.gamma [default=0]：后剪枝时，用于控制是否后剪枝的参数。 6.max_delta_step [default=0]：这个参数在更新步骤中起作用，如果取0表示没有约束，如果取正值则使得更新步骤更加保守。可以防止做太大的更新步子，使更新更加平缓。 7.subsample [default=1]：样本随机采样，较低的值使得算法更加保守，防止过拟合，但是太小的值也会造成欠拟合。 8.colsample_bytree [default=1]：列采样，对每棵树的生成用的特征进行列采样.一般设置为： 0.5-1 9.lambda [default=1]：控制模型复杂度的权重值的L2正则化项参数，参数越大，模型越不容易过拟合。 10.alpha [default=0]:控制模型复杂程度的权重值的 L1 正则项参数，参数值越大，模型越不容易过拟合。 11.scale_pos_weight [default=1]：如果取值大于0的话，在类别样本不平衡的情况下有助于快速收敛。 Learning Task Parameters（学习任务参数） 1.objective [default=reg:linear]：定义最小化损失函数类型，常用参数： binary:logistic –logistic regression for binary classification, returns predicted probability (not class) multi:softmax –multiclass classification using the softmax objective, returns predicted class (not probabilities) you also need to set an additional num_class (number of classes) parameter defining the number of unique classes multi:softprob –same as softmax, but returns predicted probability of each data point belonging to each class. 2.eval_metric [ default according to objective ]： The metric to be used for validation data. The default values are rmse for regression and error for classification. Typical values are: rmse – root mean square error mae – mean absolute error logloss – negative log-likelihood error – Binary classification error rate (0.5 threshold) merror – Multiclass classification error rate mlogloss – Multiclass logloss auc: Area under the curve 3.seed [default=0]： The random number seed. 随机种子，用于产生可复现的结果 Can be used for generating reproducible results and also for parameter tuning. 注意: Python sklearn style参数名会有所变化 eta –> learning_rate lambda –> reg_lambda alpha –> reg_alpha 四、实战 官方样例： XGBoost Python API Reference (official guide) XGBoost Demo Codes (xgboost GitHub repository) xgboost参数设置代码示例：