整篇论文技术实现分两个部分
显而易见，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.
特征重要性，我们一般用来观察不同特征的贡献度。排名靠前的，我们认为是重要的。这一思路，通常被用来做 特征筛选 。剔除贡献度不高的尾部特征，增强模型的鲁棒性，起到特征降维的作用。另一方面，则是用来做模型的课解释性。我们期望的结果是：重要的特征是复合业务直觉的；符合业务直觉的特征排名靠前。在实际操作中，我们一般用树模型的分类点来做文章。常用的就是XGB和其他一般树模型。
XGB内置的三种特征重要性计算方法1--weight
xgb.plot_importance这是我们常用的绘制特征重要性的函数方法。其背后用到的贡献度计算方法为weight。
'weight' - the number of times a feature is used to split the data across all trees.
简单来说，就是在子树模型分裂时，用到的特征次数。这里计算的是所有的树。这个指标在R包里也称为frequency2。
XGB内置的三种特征重要性计算方法2--gain
model.feature_importances_这是我们调用特征重要性数值时，用到的默认函数方法。其背后用到的贡献度计算方法为gain。
'gain'-the average gain across all splits the feature is used in.
gain是信息增益的泛化概念。这里是指节点分裂时，该特征带来信息增益(目标函数)优化的平均值。
XGB内置的三种特征重要性计算方法3--cover
model = XGBRFClassifier(importance_type = 'cover')这个计算方法，需要在定义模型时定义。之后再调用
model.feature_importances_得到的便是基于cover的贡献度。
'cover' - the average coverage across all splits the feature is used in.
cover形象来说，就是树模型在分裂时，特征下的叶子节点涵盖的样本数除以特征用来分裂的次数。分裂越靠近根部，cover值越大。
使用场景
weight将给予数值特征更高的值，因为它的变数越多，树分裂时可切割的空间越大。所以这个指标，会掩盖掉重要的枚举特征。
gain用到了熵增的概念，它可以方便的找出最直接的特征。即如果某个特征下的0,在label下全是0，则这个特征一定会排的靠前。
cover对于枚举特征，会更友好。同时，它没有过度拟合目标函数。不接受目标函数的量纲影响。
调用他们的方式如下
# avaliable importance_types = ['weight','gain','cover','total_gain','total_cover']
f = "gain"
XGBClassifier.get_booster().get_score(importamce_type=f)
在实践中，也会发现，gain排出来的顺序的 头尾部值差距较大 ，这是因为信息增益计算时，后续的优化可能都不是一个量级。类似于神经网络在优化损失函数时，后续的量纲可能是十倍、百倍的差异。所以，综上而言，如果 有下游业务方，更建议用cover的特征重要性计算方法 。当然，如果是单纯的模型调优，gain能指出最重要的特征。这些特征，某些场景下还能总结成硬规则。
其他重要计算方法4 -- permutation
除了上述内置的重要性计算方法外，还有其他其他第三方计算方式。
permutation :如果这个特征很重要，那么我们打散所有样本中的该特征，则最后的优化目标将折损。这里的折损程度，就是特征的重要程度。由于其计算依赖单一特征，所以对非线形模型更友好。同时，如果特征中存在多重共线性，共线性的特征重要性都将非常靠后。这是因为混淆单一特征，不影响另一个特征的贡献。这样的结果是，即使特征很重要，也会排的很靠后。
针对多重共线特征，sklearn文档中提到了一种解决方法：计算特征间的spearman rankk-order correlations,取得每一组中的头部特征，再进行特征重要性计算。这种方法，实际上是在解决特征共线的问题。
其他模型的特征重要性计算方法
对于同样的树模型，Random Forest和GBDT，同样也有内置的特征重要性。Random Forest使用rf.feature_importances_得到特征重要性。其中，分类任务计算的是gini不纯度/信息熵。回归任务计算的是树的方差。这种基于 不纯度 (Mean Decrease in Impurity)的方法，实际上会有两个问题存在：(1)会给予变量空间更大的特征更多的关注，而二分类特征则会靠后。(2)结果的拟合是基于训练集的，存在过拟合风险，没有验证集数据做验证。
针对上述的问题，建议通过out-of-bag(OOB)方法，在剩下数据上做验证，结合Permutation计算特征重要性。此外，GBDT也是基于 不纯度 计算的特征重要性，不过其在单棵树上，是回归树，所以不是基于gini系数，而是MSE或MAE。
至于为什么他们同为树模型，且都是基于不存度计算的重要性，但结果不同。主要有两个，一个是它们树结构不同；第二个则是它们的优化对象不同。
