查看原文：http://www.wyblog.cn/2016/11/25/xgboost%e6%96%87%e7%8c%ae%e5%ad%a6%e4%b9%a0%e7%ac%94%e8%ae%b0/
XGboost的学习资料主要为以下两个。其一是PPT资料：
http://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf
其二是论文资料:
https://arxiv.org/pdf/1603.02754v3
先看PPT，搞懂了XGboost的原理后，再看论文就轻松多了。
先总结
先总结下xgboost。实际上，xgboost全名叫Extreme Gradient Boosting，是由陈天奇大神开发的。从名字上来看，其实它属于gradien tree的一个分支，它并不是和GBDT处于并列的关系，它是在GBDT上做了算法改进，使得算法适应新更强。那么，具体改进了哪些地方呢？
在模型上，xgboost的泛化能力更强，原因在于其损失函数的构建上。传统的树模型损失函数只考虑了经验损失，即预测值与真实值得偏差作为损失函数的目标，但xgboost在损失函数中加入了正则化项，用于对树结构复杂度的控制，它包含了两项，一项是叶子节点的个数T，另一项是叶子输出score值ω的L2范数，它能够有效地避免过拟合，这也正是文章中反复提到的要平衡 bias-variance tradeoff，即预测准确性以及模型简洁性之间的平衡。
在损失函数上，传统的GBDT采用的是一阶导数，即用的梯度信息，而xgboost用了泰勒公式进行二阶导数的展开，并且，在文章中提到了，损失函数其实是可以自定义的，可以用Square loss，可以用Logistic loss，这也正是它优点之一，scalable。
在每一轮的迭代后，迭代出的树都会被乘以一个小于1的权重ε，它是为了给下一轮及以后的迭代预留大的空间，这其实就是学习速率问题。文献中的建议是尽量减小这个权重ε，然后增大迭代的次数。
对于稀疏的数据，以及可能有缺失项的数据，xgboost在学习时会给一个默认的分类方向。
xgboost支持并行及分布式计算，并且以最少的资源使用进行计算，这对于处理大数据量以及提高计算速度有很大作用。这里的并行计算的粒度并不在树，每一颗树还是串行迭代出来的，并行的粒度在于特征值分割点的计算，它同时开几个线程进行特征分割点计算，大大加快了计算速度。
在进行split点选取时，采用的是贪心算法，它总是去寻找当前迭代情况下的最优分裂点，为了找到这个点，需要先将所有特征的值进行排序，然后再计算每一种分裂可能，最后找出最优值。xgboost非常聪明的先把所有排序值给缓存下来，然后在后边计算时直接调用就行，避免了每一次排序的麻烦。
算法原理
xgboost跟GBDT一样，模型可以表示为：$latex \hat {y_{i}} = \phi (X_{i}) = \sum_{k=1}^{K} f_{k} (X_{i}), \quad f_{k} \in F $其中，$latex F= (f(x)= \omega_{q(x)} ) \quad (q: R^{m} \rightarrow T , \omega \in R^{T})$它是由一连串树串联叠加而成。其中，q(x)是将实例映射到树叶的函数，也就是代表了单棵决策树，ω是对应树叶的权重值，那么，f(x)就是将实例x经过决策树后，得到对应树叶上的权值，最后的预测 $latex \hat {y_{i}}$ 就是将每一颗树得到的权值相加，便是预测值了。注意，这里描述的是普通boost tree的形式，xgboost做了一点改进就是在每一个棵迭代出的树都乘以了一个小于1的ε后，才进行下一轮的迭代的，即$latex \hat {y}^{(t)}= \hat {y}^{(t-1)}+ \varepsilon f_{t}(x_{i}) $。算法的loss function为 $latex L(\phi)=\sum_{i}^{N} l ( y_{i} ,\hat {y_{i}^{(t)}} ) + \sum_{k} \Omega (f_{k}) $，其中，$latex \Omega (f) = \gamma T + \frac {1} {2} \lambda || \omega ^{2} || $。以上损失函数中，第一项l代表预测的经验风险，第二项Ω代表结构风险，其代表了模型的复杂度。T代表了树的叶子节点个数，正则化参数λ可以避免模型的过拟合。对于目标函数的最优化，采用的是启发式方法。目标优化函数为$latex L^{(t)} =\sum_{i=1}^{n} l(y_{i},\hat y_{i}^{(t-1)}+f_{t}(x_{i}))+\Omega (f_{t})$ ，其中 $latex \hat y_{i}^{(t-1)} $ 代表的是第i个训练实例在第t-1轮迭代时的预测值。考虑泰勒二阶展开式，得到$latex L^{(t)} \approx \sum_{i=1}^{n}[ l(y_{i},\hat y_{i}^{(t-1)})+g_{i} f_{t}(x_{i}) + \frac {1}{2} h_{i} f_{i}^{2}(X_{i})]+ \Omega (f_{t}) $，其中系数 $latex g_{i},h_{i}$，分别为上一次损失函数对预测值的一阶偏导与二阶偏导数，即$latex g_{i}=\frac {\partial_{l(y_{i},\hat y^{(t-1)})}}{\partial_{\hat y^{(t-1)}}} $，$latex h_{i}=\frac {\partial_{l(y_{i},\hat y^{(t-1)})}^{2}}{\partial_{\hat y^{(t-1)}}^{2}}$。从这里可以看到，gi与hi的值与损失函数的选取有关，例如，如果选取二次损失函数$latex l=(y-\hat y)^{2} $，那么对它求一阶与二阶偏导，$latex g_{i}=2(\hat y^{(t-1)}-y_{i})$，$latex h_{i}=2$。简化L中固定的的常数项，损失函数最终可表示为$latex \tilde {L} ^{(t)} = \sum_{i=1}^{n} [g_{i} f_{t}(X_{i}) + \frac {1}{2} h_{i} f_{i}^{2}(X_{i})]+ \Omega (f_{t}) +const$。
求得了损失函数表示形式，那么就要开始分析如何来最优化损失函数了。从以上表达式可以看出，优化损失函数要考虑三个问题，一个是gi与hi的值，一个是树的具体形式f(Xi)，还有一个是结构风险Ω。下面一个一个分析。
hi与gi是什么？
上文中已经分析了，hi与gi是经验损失函数的一阶偏导与二阶偏导，它的计算式取决于我们选取的经验损失函数，但是它的值却与预测值有关，所以说，hi与gi实际上也取决于f(xi)，在每一轮迭代树时，它的值都会变化。
如何构造树f(x)呢？
首先要重构一下损失函数。当训练集实例被映射到每一片叶子后，训练集就被分为一块一块的了，定义每一篇叶子j为 $latex I_{j}= (i|q(x_{i})=j) $，这个等式的意思是把第i个实例映射到第j片叶子上。然后，我们把损失函数改为按叶子节点来计算损失的形式：$latex Obj^{(t)} = \sum_{i=1}^{n} [g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}f_{t}^{2}(x_{i})]+\Omega (f_{t})$$latex ..\quad \quad =\sum_{i=1}^{n} [g_{i} \omega_{q(x_{i})}+\frac{1}{2}h_{i}\omega_{q_{(x_{i})}}^{2}]+\gamma T +\lambda \frac{1}{2} \sum_{j=1}^{T} \omega_{j}^{2}$$latex ..\quad \quad =\sum_{j=1}^{T}=[(\sum_{i\in I_{j}}g_{i})\omega_{j}+\frac{1}{2}(\sum_{i\in I_{j}}h_{i}+\lambda)\omega_{j}^{2}+\gamma T$$latex ..\quad \quad =\sum_{j=1}^{T}[G_{j}\omega_{j}+\frac {1}{2}(H_{j}+\lambda)\omega_{j}^{2}]+\gamma T$以上,Hj与Gj分别代表了第j片叶子上的所有实例的hi与gi之和。λ与γ分别为正则化系数。ωj代表映射到第j片叶子上时，所得到的score。而我们要优化的，正是这个score。考虑到二次函数$latex \frac {1}{2} ax^{2}+bx$,其最优解为 $latex argmin_{x}=- \frac {b}{a} ,min_{x}= -\frac {1}{2} \frac {b^{2}}{a} $，所以，目标函数最优解为：$latex Obj=- \frac {1}{2} \sum_{j=1}^{T} \frac {G_{j}^{2}}{H_{j}+ \lambda }+\gamma T $，当$latex \omega_{j}^{*}= - \frac {G_{j}}{H_{j}+ \lambda }$。以上给出了构造boost树的准则，即构造的树的结构要使得Obj最小。传统方式上，可以枚举出所有可能的树的结构，然后去计算每种结构的Obj函数的值，找到最优结构后，再根据$latex \omega_{j}^{ * }$的公式，去计算每一片树叶的score。但可预见的是，这几乎是不可能实现的算法，树的结构形式存在无数种可能性，计算量太大了。所以，xgboost采用了贪心策略。每一棵树都一层一层的增长，在某个feature处，是否split，取决于：$latex Gain = \frac {1}{2} [ \frac {(\sum_{i \in I_{L}} g_{i})^{2}}{ \sum_{i \in I_{L}} h_{i}+\lambda} + \frac {(\sum_{i \in I_{R}} g_{i})^{2}}{ \sum_{i \in I_{R}} h_{i}+\lambda} - \frac {(\sum_{i \in I} g_{i})^{2}}{ \sum_{i \in I} h_{i}+\lambda}]-\gamma$。以上公式是在判断，经过此处split后，与不split相比，是否能降低目标优化Obj函数的值，同时还要扣除增加树叶带来的风险γ(注意这个γ就是正则化项里树叶数量T的系数γ)，如果能降低，那么就split，否则就不变。剩下的问题就是，如何以更好的方法去寻找split点了。xgboost处理的方式是，预先对所有训练实例的每个feature值进行排序，然后进行线性扫描，去寻找每个feature的最佳分割点，当然这里Gain值有可能计算出来每个split点都是负值，自然地，这种情况下当前feature就不用作为split节点了。经过以上处理，建立每一棵树复杂度就变为了O(d k nlogn)，代表d个feature，k层树，排序需要O(nlogn)的复杂度。xgboost在这里进行了进一步优化，例如对缺失值进行默认参数处理，以及提前将所有特征值排序并cache下来。最后，为了避免造成过拟合，除了正则化参数外还有其他方式。第一种是shrinkage，它在每一个被训练出的树上乘以一个参数η以削弱其影响，给后边继续训练的树以训练空间。第二种方式是像随机森林一样，训练时对特征进行随机采样，这样也加快了训练速度。另外，如果一个树深度过大，那么可以进行剪枝，去掉那些Gain值小的分裂点。
查看原文： http://www.wyblog.cn/2016/11/25/xgboost%e6%96%87%e7%8c%ae%e5%ad%a6%e4%b9%a0%e7%ac%94%e8%ae%b0/