集成算法之GBDT和xgboost

大家知道，我们在进行建模时，会求解一个目标函数；目标函数又称代价函数，在机器学习中普遍存在，一般形式为：
$obj(\theta)=L(\theta)+\Omega(\theta)$obj(θ)=L(θ)+Ω(θ)；
其中：
$L(\theta)$L(θ)为训练误差，衡量模型在训练集上的表现；
$\Omega(\theta)$Ω(θ)是正则化惩罚，衡量模型的复杂度。

训练集误差：$L=\sum_{i=1}^{n}l(y_i,\hat{y_i})$L=∑i=1n​l(yi​,yi​^​)
square loss: $l(y_i,\hat{y_i})=(y_i-\hat{y_i})^2$l(yi​,yi​^​)=(yi​−yi​^​)2
logistic loss：$l(y_i,\hat{y_i})=y_iln(1+e^{-\hat{y_i}})+(1-y_i)ln(1+e^{\hat{y_i}})$l(yi​,yi​^​)=yi​ln(1+e−yi​^​)+(1−yi​)ln(1+eyi​^​)

正则化惩罚：
L2 norm： $\Omega(w)=\lambda||w||^2$Ω(w)=λ∣∣w∣∣2
L1 norm(lasso)： $\Omega(w)=\lambda||w||$Ω(w)=λ∣∣w∣∣

机器学习实际上就是在给定的训练集上学习模型参数：优化训练误差使模型具有预测性；优化正则化让模型更简单，使预测更加稳定，降低过拟合风险。

一、xgboost

XGBoost是boosting算法的其中一种。Boosting算法的思想是将许多弱分类器集成在一起形成一个强分类器。因为XGBoost是一种提升树模型，所以它是将许多树模型集成在一起，形成一个很强的分类器。而所用到的树模型则是CART回归树模型。

xgboost算法思想就是不断地添加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数，去拟合上次预测的残差。当我们训练完成得到k棵树，我们要预测一个样本的分数，其实就是根据这个样本的特征，在每棵树中会落到对应的一个叶子节点，每个叶子节点就对应一个分数，最后只需要将每棵树对应的分数加起来就是该样本的预测值。

xgboost目标函数objective： $\sum_{i=1}^{n}l(y_i,\hat{y_i})+\sum_{k=1}^{k}\Omega(f_k)$∑i=1n​l(yi​,yi​^​)+∑k=1k​Ω(fk​)

1、算法思想：

start from constant prediction, add a new function each time
$\hat y^{(0)}=0$y^​(0)=0
$\hat y^{(1)}=f_1(x_i)=\hat y_i^{(0)}+f_1(x_i)$y^​(1)=f1​(xi​)=y^​i(0)​+f1​(xi​)
$\hat y^{(2)}=f_1(x_i)+f_2(x_i)=\hat y_i^{(1)}+f_2(x_i)$y^​(2)=f1​(xi​)+f2​(xi​)=y^​i(1)​+f2​(xi​)
·······
$\hat y^{(t)}=\sum_{k=1}^{t}f_k(x_i)=\hat y_i^{(t-1)}+f_t(x_i)$y^​(t)=∑k=1t​fk​(xi​)=y^​i(t−1)​+ft​(xi​)

2、算法求解：

以上是整个算法的思路，但现在的问题是怎么决定增加的函数$f$f，所以，我们需要来优化objective。
从以上我们可以看到，在$t$t轮迭代时，预测结果为
$\hat y^{(t)}=\sum_{k=1}^{t}f_k(x_i)=\hat y_i^{(t-1)}+f_t(x_i)$y^​(t)=∑k=1t​fk​(xi​)=y^​i(t−1)​+ft​(xi​)

所以：
$obj^{(t)}=\sum_{i=1}^{n}l(y_i,\hat{y_i}^{(t)})+\sum_{k=1}^{k}\Omega(f_i)=\sum_{i=1}^{n}l(y_i,\hat{y_i}^{(t-1)}+f_t(x_i))+\Omega(f_t)+constant$obj(t)=∑i=1n​l(yi​,yi​^​(t))+∑k=1k​Ω(fi​)=∑i=1n​l(yi​,yi​^​(t−1)+ft​(xi​))+Ω(ft​)+constant

所以我们要求解的最终目标函数为下，并使其最小化：
$obj^{(t)}=(y_i-(\hat{y_i}^{(t-1)}+f_t(x_i)))^2+\Omega(f_t)+constant$obj(t)=(yi​−(yi​^​(t−1)+ft​(xi​)))2+Ω(ft​)+constant

接下来我们利用泰勒展开式对目标函数进行求解。

泰勒展开式：$f(x+\Delta x)\cong f(x)+f'(x)\Delta x+\frac{1}{2}f''(x)\Delta x$f(x+Δx)≅f(x)+f′(x)Δx+21​f′′(x)Δx

令$g_i=\partial\hat y^{(t-1)}l(y_i,\hat y^{(t-1)})$gi​=∂y^​(t−1)l(yi​,y^​(t−1))，$h_i=\partial^2\hat y^{(t-1)}l(y_i,\hat y^{(t-1)})$hi​=∂2y^​(t−1)l(yi​,y^​(t−1))

则：$obj^{(t)}\approx \sum_{i=1}^{n}\left [ l(y_i),\hat y^{(t-1)}+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i) \right ]+\Omega (f_t)+constant$obj(t)≈∑i=1n​[l(yi​),y^​(t−1)+gi​ft​(xi​)+21​hi​ft2​(xi​)]+Ω(ft​)+constant

移除常数项：
$obj^{(t)}\approx \sum_{i=1}^{n}\left [ g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i) \right ]+\Omega (f_t)$obj(t)≈∑i=1n​[gi​ft​(xi​)+21​hi​ft2​(xi​)]+Ω(ft​)

下面我们改进树的定义：

所以树的叶子节点包含两个东西：
1.一个样本实例集；
2.样本实例的分数。
对于$I_j=\left \{ i|q(x_i)=j \right \}$Ij​={i∣q(xi​)=j}表示在叶子节点$j$j上的数据集合。

根据叶子节点重新组合目标函数：

令上式一阶导等于0，得出叶子节点$j$j上的最优权重：
$w^*=-\frac{\sum_{x\in I_j}g_i}{\sum_{x\in I_j}h_i+\lambda}$w∗=−∑x∈Ij​​hi​+λ∑x∈Ij​​gi​​

此时对应的目标函数的最优值为：

$obj=-\frac{1}{2}\frac{(\sum_{x\in I_j}g_i)^2}{\sum_{x\in I_j}h_i+\lambda}+\gamma T$obj=−21​∑x∈Ij​​hi​+λ(∑x∈Ij​​gi​)2​+γT

进行整理，使其简洁一些：
定义：$G_i=\sum_{x\in I_j}g_i$Gi​=∑x∈Ij​​gi​，$H_i=\sum_{x\in I_j}h_i$Hi​=∑x∈Ij​​hi​

则：$obj^{(t)}=\sum_{j=1}^{T}\left [ G_jw_j+\frac{1}{2}(H_j+\lambda)w_j^2 \right ]+\gamma T$obj(t)=∑j=1T​[Gj​wj​+21​(Hj​+λ)wj2​]+γT

最优解：

$w^*=-\frac{G_i}{H_i+\lambda}$w∗=−Hi​+λGi​​

$obj=-\frac{1}{2}\sum_{j=1}^{T}\frac{G_i^2}{H_i+\lambda}+\gamma T$obj=−21​∑j=1T​Hi​+λGi2​​+γT

3、搜寻最佳树结构

在上面的推导中，我们知道了如果我们一棵树的结构确定了，如何求得每个叶子结点的分数。但我们还没介绍如何确定树结构，即每次特征分裂怎么寻找最佳特征，怎么寻找最佳分裂点。

我们不可能去遍历所有树结构，因此，XGBoost使用了和CART回归树一样的想法，利用贪婪算法，遍历所有特征的所有特征划分点，不同的是使用上式目标函数值作为评价函数。具体做法就是分裂后的目标函数值比单子叶子节点的目标函数的增益，同时为了限制树生长过深，还加了个阈值，只有当增益大于该阈值才进行分裂。

在实际应用中，我们从树的深度为0开始，对树的每一个叶子节点尝试进行分裂，分裂后的目标函数变化为：
$Gain=\frac{1}{2}\left [ \frac{G_L^2 }{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right ]-\gamma$Gain=21​[HL​+λGL2​​+HR​+λGR2​​−HL​+HR​+λ(GL​+GR​)2​]−γ

其中：$\frac{G_L^2 }{H_L+\lambda}$HL​+λGL2​​为左节点分数，$\frac{G_R^2}{H_R+\lambda}$HR​+λGR2​​为右节点分数，$\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}$HL​+HR​+λ(GL​+GR​)2​为为分裂分数，$\gamma$γ为分裂的复杂度代价。

在每个节点遍历全部特征，对每个特征按照大小排序，使用线性搜索方法寻找最佳切分点，对所有特征都采用最佳切分点算法。

同时可以设置树的最大深度、当样本权重和小于设定阈值时停止生长去防止过拟合。

4、Shrinkage and Column Subsampling

总结： xgboost算法整个过程为：
在每一次迭代增加一棵树
在每次迭代开始前，计算：
$g_i=\partial\hat y^{(t-1)}l(y_i,\hat y^{(t-1)})$gi​=∂y^​(t−1)l(yi​,y^​(t−1))，$h_i=\partial^2\hat y^{(t-1)}l(y_i,\hat y^{(t-1)})$hi​=∂2y^​(t−1)l(yi​,y^​(t−1))
贪婪的方式增长树：
$obj=-\frac{1}{2}\sum_{j=1}^{T}\frac{G_j^2}{H_i+\lambda}+\gamma T$obj=−21​∑j=1T​Hi​+λGj2​​+γT
$f_t(x)$ft​(x)增加到模型上：$\hat y^{(t)}=\sum_{k=1}^{t}f_k(x_i)=\hat y^{(t-1)}+f_t(x_i)$y^​(t)=∑k=1t​fk​(xi​)=y^​(t−1)+ft​(xi​)

shrinkage
为了防止过拟合，使每一棵树的影响力不会太大，留下更大的空间给后面生成的树去优化模型，在每次迭代中对树的每个叶子结点的分数乘上一个缩减权重$\varepsilon$ε.
所以$\hat y^{(t)}=\sum_{k=1}^{t}f_k(x_i)=\hat y^{(t-1)}+\varepsilon f_t(x_i)$y^​(t)=∑k=1t​fk​(xi​)=y^​(t−1)+εft​(xi​)
$\varepsilon$ε也叫做步长或学习率，通常设置在0.1附近。

Column Subsampling
Column Subsampling类似于随机森林中的选取部分特征进行建树。分为两种，一种是按层随机采样，在对同一层内每个结点分裂之前，先随机选择一部分特征，然后只需要遍历这部分的特征，来确定最优的分割点。另一种是随机选择特征，则建树前随机选择一部分特征然后分裂就只遍历这些特征。一般情况下前者效果更好。

二、GBDT

GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，或GBRT（Gradient Boosting Regression Tree），是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终答案。

GBDT无论是分类问题还是回归问题，都使用CART树作为基础分类器。

GBDT使用了前向分布算法，假设我们前一轮的迭代学到的学习机器是$f_{t-1}(x)$ft−1​(x)，损失函数为$L(y,f_{t-1}(x))$L(y,ft−1​(x))，在本轮迭代中，我们的目标就是找到一个CART树模型的弱学习器$h_t(x)$ht​(x)，使本轮的损失函数$L(y,f_t(x))=L(y,f_{t-1}(x)+h_t(x))$L(y,ft​(x))=L(y,ft−1​(x)+ht​(x))最小。

Friedman提出了使用损失函数的负梯度来拟合本轮损失的近似值。

GBDT算法流程：

• 初始化弱学习器$f_0(x)$f0​(x)，得到使损失函数极小化的一个常数值，此时树仅有一个根节点
• 计算损失函数的负梯度值，以此作为残差的估计
  针对选取的不同的损失函数（平方、绝对值、Huber），计算梯度值；
  算法中嵌套两层循环，分别为迭代轮数m和样本i，精确到每个样本和每个叶子节点求负一阶导。
• 利用计算得到的$(x_i,r_{im})$(xi​,rim​)拟合一棵CART回归树，得到第m轮的回归树，对应的叶子节点区域为$R_{jm},j=1,2,...,J_m$Rjm​,j=1,2,...,Jm​（$J_m$Jm​为回归树t的叶子节点的个数）
• 接着，对叶子区域计算最佳拟合值$\gamma _{jm}$γjm​（损失函数极小化）并更新强学习器$f_m(x)$fm​(x)
• 最后，在迭代结束后输出最终模型$\hat{f}(x)$f^​(x)

GBDT和xgboost的区别

本段选自知乎wepon的回答机器学习算法中 GBDT 和 XGBOOST 的区别有哪些？
作者：wepon
链接：https://www.zhihu.com/question/41354392/answer/98658997
来源：知乎

• 传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
• 传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。
• xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance trade-off角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
• Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）
• 列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
• 对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。
• xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
• 可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。