论文题目：
《XGBoost: A Scalable Tree Boosting System》
提升树算法就是将不同的树做加法模型, 在GBDT里面，基本树模型是CART树： \(\hat{y_{i}}=\phi(x_{i})=\sum_{k=1}^{K}f_{k}(x_{i})\) GBDT的损失函数： \(\mathcal{L}^{(t)}=\sum_{i=1}^{n}l(y_{i}, \hat{y_{i}}^{(t-1)}+f_{t}(x_{i})) + \Omega(f_{t})\) 其中，正则项：$\Omega(f)=\gamma T + \frac{1}{2}{||w||}^{2}$
就是在前面$t-1$棵树的基础上，增加一棵树，使得总损失函数最小。
$f_t(x_{i})$是什么？它其实就是$f_t$的某个叶子节点的值，叶子节点的值是可以作为模型的参数的。
CART树的另一番定义： \(\mathcal{F}={f(x)=\omega_{q}(x)}(q:\mathbb{R}^{m}\rightarrow T, \omega \in {\mathbb {R}^{T}})\label{eq1}\) 这里操作$q$将样本$x$从$m$维空间映射成树$f$的$T$个叶子节点中的一个，即代表了树的结构，因此$\omega_{q}(x)$和$f(x)$一样都是某个叶子节点的值。
在XGBoost论文中，正则化项$\Omega(f_{t})$的具体形式是： \(\Omega(f_{t})=\gamma T + \frac{1}{2}\lambda\sum_{j=1}^{T}\omega_{j}^{2}\) 将上式做二阶泰勒展开 \(\mathcal{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_{t}^{2}(x_{i})] + \Omega(f_{t})\label{eq2}\) 其中： \(g_{i} = \partial_{\hat{y_{i}(t-1)}}l(y_{i}, \hat{y_{i}})\)
\[g_{i} = \partial_{\hat{y_{i}(t-1)}}^{2}l(y_{i}, \hat{y_{i}})\]要特别注意这里是损失函数对前$t-1$棵树的预测结果取偏导。
利用公式$\eqref{eq1}$ , 将泰勒展开得到的公式$\eqref{eq2}$变形，得到： \(\mathcal{L}^{(t)}\approx\sum_{j=1}^{T}\sum_{i\in I_{j}}[g_{i}\omega_{j} + \frac{1}{2}h_{i}\omega_{j}] + \gamma T + \sum_{j=1}^{T}\frac{1}{2}\lambda\omega_{j}^{2}\\ =\sum_{j=1}^{T}[(\sum_{i\in I_{j}}g_{i})w_{j}+\frac{1}{2}(\sum_{i\in I_{j}}h_{i}+\lambda)w_{j}^{2})] + \gamma T\)
对于确定的树结构$q$，最佳叶节点值和对应的优化值容易得出(求关于$w_{j}$的偏导数)： \(\omega_{j}^{*}=-\frac{\sum_{i\in I_{j}}g_{i}}{\sum_{i\in I_{j}}h_{i}+\lambda}\)
\[{\tilde{\mathcal{L}}^{(t)}(q)}=-\frac{1}{2}\sum_{j=1}^{T}\frac{(\sum_{i\in I_{j}}g_{i})^{2}}{\sum_{i\in I{j}}h_{i}+\lambda}\]优化值的大小可以类似决策树树的纯度一样用来衡量树的结构好坏的标准。XGBoost是用一种从单叶子节点开始的不断计算分割目标值是否变小的贪心算法来确定最优树结构，具体来说就是从单也是节点开始，一层一层的通过目标值的变化确定结构的好坏，贪心地永远选取使目标值最小的分割结构。CART树的分割，目标值减少的评价函数是： \(\mathcal{L}_{split}=\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\) $\gamma$是模型参数，它的值越大，代表对切分后模型的下降幅度要求越高。
XGBoost运用到的两种防止过拟合的方法：Shrinkage 和 Column Subsampling。Shrinkage方法就是在每次迭代中对树的每个叶子结点的分数乘上一个缩减权重$\eta$，这可以使得每一棵树的影响力不会太大，留下更大的空间给后面生成的树去优化模型。Column Subsampling类似于随机森林中的选取部分特征进行建树。其可分为两种，一种是按层随机采样，在对同一层内每个结点分裂之前，先随机选择一部分特征，然后只需要遍历这部分的特征，来确定最优的分割点。另一种是随机选择特征，则建树前随机选择一部分特征然后分裂就只遍历这些特征。一般情况下前者效果更好。
参考博客：