XGBoost 原理及公式推导

                          *单位：东北大学*   *作者：王文举*

1. xgboost描述

      xgboost算法将各种弱评估器结合，是一种可扩展性提升树算法，弱评估器一般为CART树。
      CART 树是基于类别的条件概率分布模型，其模型结构为二叉树。CART既可以用于分类也能用于回归，对于CART回归树来说，其预测结果为叶结点上所有样本的均值。对CART分类树来说，可以采用投票的方法确定类别标签。
      xgboost算法是在梯度提升树(GBDT)的基础上改进而来。相同点都是采用前向分布加法模型，多个弱评估器加权累加，使目标预测值逐渐逼近真值，两者都是参数估计形式来表示模型。
不同点主要为：
（1）GBDT优化过程，采用损失函数的一阶导数信息，而XGBoost是对损失函数泰勒级数展开，利用二阶导。
（2）XGBoost在损失函数中引入正则化，限制叶节点数以及每个节点上的预测得分。
（3）XGBoost支持多线程，在划分节点是时，每个特征并行计算，提高运算迅速。同时，也引入随机森林列采样思想，节点划分时，只考虑部分属性。
（4）GBDT中预测值是由所有弱分类器上的预测结果的加权求和，其中每个样本上的预测结果就是样本所在的叶子节点的均值。而XGBT中的预测值是所有弱分类器上的叶子权重直接求和得到，也称为预测得分。
XGBoost的目标函数为：
$L(\phi)=\sum_{i = 1}^nl( \hat y_{i},y_{i} )+\Omega(f_k)$L(ϕ)=i=1∑n​l(y^​i​,yi​)+Ω(fk​)$\Omega(f_k) = \gamma T+\frac{1}{2}\lambda||w||^2$Ω(fk​)=γT+21​λ∣∣w∣∣2 函数 $l$l是损失函数，$l(\hat y_i,y_i)$l(y^​i​,yi​) 可以用来计算预测值 $\hat y_i$y^​i​和真实值$\ y_i$ yi​差别程度。函数 Ω 为正则项，可以用来减少模型的复杂度，防止过拟合的发生。$\Omega(f_k)$Ω(fk​)中包含两项，$\gamma T$γT与$\lambda||w||^2$λ∣∣w∣∣2。其中 T 为树模型中叶节点的数量，这部分提供了对叶节点数目的控制。$\lambda||w||^2$λ∣∣w∣∣2表示正则项，ω 为叶节点的权重，这部分控制了叶节点的权重，保证了不会因为过大的权重而导致过拟合现象的产生。当正则项被置为 0 时，XGBoost 目标函数就退化为提升树的目标函数。
      右侧第一项$l(\hat y_i-y_i)$l(y^​i​−yi​)是衡量我们的偏差，模型越不准确，第一项就会越大。第二项$\Omega(f_k)$Ω(fk​)是衡量我们的方差，模型越复杂，模型的学习就会越具体，方差就会越大。所以其实在求解方差与偏差的平衡点，以求模型的泛化误差最小。
      由于模型通过叠加的方式来训练，在迭代的每一步过程中都添加一个基分类器$f_t$ft​。则第t轮模型的预测结果为:
$\hat y^t (x_{i})=\hat y^{t -1}+f_t(x_{i})$y^​t(xi​)=y^​t−1+ft​(xi​)      则目标损失函数改写为：
$Obj^{(t)}=\sum_{i = 1}^nl(y_{i},\hat y^{t-1}+f_{t}(x_{i}))+\Omega(f_t)+constant$Obj(t)=i=1∑n​l(yi​,y^​t−1+ft​(xi​))+Ω(ft​)+constant

2.损失函数求解

根据泰勒级数展开公式
$f(x+\Delta x)\simeq f(x)+f^{'}(x)\Delta x+\frac{1}{2}f^{''}(x)\Delta x^2$f(x+Δx)≃f(x)+f′(x)Δx+21​f′′(x)Δx2将$\Delta x$Δx替换为$f_{t}(x_{i})$ft​(xi​),则目标函数可以写成为
$Obj^{(t)}\simeq \sum_{i = 1}^n[l(y_{i},\hat y^{t-1})+g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}{f_{t}}^{2}(x_{i})]$Obj(t)≃i=1∑n​[l(yi​,y^​t−1)+gi​ft​(xi​)+21​hi​ft​2(xi​)] $+\Omega(f_t)+constant$+Ω(ft​)+constant 上式定义: $g_{i} =\vartheta_{\hat y^{t-1}} l(y_{i},\hat y^{t-1})$gi​=ϑy^​t−1​l(yi​,y^​t−1) $h_{i} ={\vartheta}^{2}_{\hat y^{t-1}} l(y_{i},\hat y^{t-1})$hi​=ϑy^​t−12​l(yi​,y^​t−1)

3.参数估计

      XGBoost所用的弱评估器为CART树，即每个样本数据最终会落入CART决策树的叶结点上，故每次迭代产生的弱评估器$f_{t}$ft​可以用参数形式表示。
     在依次迭代中，假设样本$x_{i}$xi​落入第$j$j个叶结点中，写为$j =q(x_{i})$j=q(xi​)。则样本在$j$j叶节点上预测分数（又称叶子权重）可以写成$w_{q(x_{i})}$wq(xi​)​，$q(x_{i})$q(xi​)表示落在哪个叶节点上。以参数估计方式，可知$w_{q(x_{i})} =f_{t}(x_{i})$wq(xi​)​=ft​(xi​) 。此外，还需要做一步转化，原目标在样本数据上遍历，可以转化为在叶子节点上遍历。
$Obj^{(t)}\simeq \sum_{i = 1}^n[g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}{f_{t}}^{2}(x_{i})]+\Omega(f_t)$Obj(t)≃i=1∑n​[gi​ft​(xi​)+21​hi​ft​2(xi​)]+Ω(ft​) $= \sum_{i = 1}^n[g_{i}w_{q(x_{i})})+\frac{1}{2}h_{i}{w_{q(x_{i})}^{2}}]+ \gamma T+\frac{1}{2}\lambda\sum_{j = 1}^T{w_j^{2}}$=i=1∑n​[gi​wq(xi​)​)+21​hi​wq(xi​)2​]+γT+21​λj=1∑T​wj2​$= \sum_{j = 1}^T[(\sum_{i\subset I_{j}} g_{i})w_{j}+\frac{1}{2}(\sum_{i\subset I_{j}} h_{i}+\lambda){w_j^{2}}]+ \gamma T$=j=1∑T​[(i⊂Ij​∑​gi​)wj​+21​(i⊂Ij​∑​hi​+λ)wj2​]+γT令$G_j=\sum_{i\subset I_{j}} g_{i}$Gj​=∑i⊂Ij​​gi​,$H_j =\sum_{i\subset I_{j}} h_{i}$Hj​=∑i⊂Ij​​hi​，替换后，对损失函数求倒数，求解新的评估器${w^*_j}$wj∗​，并将其带入损失函数
即：$Obj = \gamma T-\frac{1}{2}\sum_{j= 1}^T\frac{G^2_j}{H_j +\gamma}$Obj=γT−21​j=1∑T​Hj​+γGj2​​这里，$G_j,H_j$Gj​,Hj​是由$g_j,h_j$gj​,hj​有关，而$g_j,h_j$gj​,hj​又是通过损失函数$l$l对前一棵树求导而来。所以当$l$l确定后，文中二分类采用binary:logistic，$G_j,H_j$Gj​,Hj​就固定。所以，整个损失函数只和树的结构T有关。
     上述目标函数是基于每个叶子节点，也就是树的结构来计算。所以，我们的目标函数又叫做“结构分数”，分数越低，树整体的结构越好。如此，就建立了树的结构（叶子）和模型效果的直接联系。

4.树的结构分裂

     由于决策树的建模属于 NP 问题，因此 XG-Boost 采用贪心思想来建模。假设 $I_L$IL​和$I_R$IR​是数据集经过某个节点判断之后分裂的两个集合，$I = I_L∪ I_R$I=IL​∪IR​，计算
     根据$L_{split}$Lsplit​最大，选取最佳的树结构，在这种树结构下，计算$G_j,H_j$Gj​,Hj​。就可以求解每棵树叶子的权重${w^*_j}$wj∗​。

     以上为整个XGBoost基本理论与原理，对比分析XGBoost与决策树的区别：
使用指标：决策树采用信息熵或者基尼指数，XGBoost采用目标函数Obj。在选取特征上，决策树采用信息增益最大，而XGBoost采用$L_{split}$Lsplit​最大进行特征分裂。决策树中当信息增益小于给定阈值$\epsilon$ϵ时停止分裂，而XGBoost中$L_{split}$Lsplit​小于$\gamma$γ时停止分裂。