机器学习 - 提升树（下）- XGBoost 以及与 GBDT 的比较

机器学习 - 提升树（下）- XGBoost 以及与 GBDT 的比较

XGBoost（eXtreme Gradient Boost）

本文介绍 Kaggle 等数据竞赛的大杀器：XGBoost ！

XGBoost（eXtreme Gradient Boost）
1. 原理
  
  XGBoost 的核心原理与之前所讲的提升树是类似的，都是通过学习残差近似来训练模型。不同的是 XGBoost 同时使用了一阶导与二阶导。而且XGBoost 加入了正则项，从某种程度上可以进行预剪枝，所以约束了模型的复杂度。说了这么多，“关键看疗效”，但 XGBoost 真正工程应用上也是非常的棒，陈天奇前辈可谓“华人之光”啊！
  
  对于加法模型与前向分步算法的过程是一样的，那么我们从损失函数来看 XGBoost 的灵性：
  
  我们想构建目标函数，其中包含正则项以及损失函数，那么我就可以先抽象化的定义目标函数：
  
  $Obj=\sum_{i=1}^{n}l(y_i, y_i^{(m-1)}+f_m(x_i))+Ω(f_m)$
  
  其中 $l(y_i, y_i^{(m+1)}+f_m(x_i))$ 为经验损失函数， $y_i$ 为真实值， $y_i^{(m-1)}$ 为第 m-1 次迭代后模型的预测值， $Ω(f_m)$ 为正则项。
  
  那么我们该如何具体地表示残差以及正则项呢，XGBoost 选择使用 泰勒公式的二阶展开！
  
  泰勒公式的二阶展开式为： $f(x+\triangle x)=f(x) + f'(x)\triangle x+\frac{1}{2}f''(x)\triangle x^2$
  
  根据此，我们将经验损失函数 $l(y_i, y_i^{(m+1)}+f_m(x_i))$ 进行泰勒公式的二阶展开:
  
  我们定义：
  
  $一阶导：g_i=\frac{\partial l(y_i, y_i^{(m-1)})}{\partial y_i^{m-1}}，二阶导：h_i=\frac{\partial^2 l(y_i, y_i^{(m-1)})}{\partial (y_i^{m-1})^2}，且恰好 \triangle x=f_m(x_i)$
  
  所以：
  
  $Obj=\sum_{i=1}^{n}[l(y_i, y_i^{(m-1)}+f_m(x))+g_if_m(x_i)+\frac{1}{2}h_if_m^2(x_i)]$
  
  其中 $f_m(x_i)$ 表示对样本 $x_i$ 的预测值。
  
  $[l(y_i, y_i^{(m-1)}+f_m(x))$ 根据上一轮的学习结果计算得到，所以视为常数 $C$ ，那么上式转化为：
  
  $Obj=\sum_{i=1}^{n}[g_if_m(x_i)+\frac{1}{2}h_if_{mt}^2(x_i)]+C$
  
  另外加入正则项 $\frac{1}{2}λ\sum_{t=1}^{T}w_t^2$ ，其中 $w_t$ 为第 $t$ 个叶节点的结构分数。并且对于树的复杂度，我们一般还会考虑叶子结点的个数 |T|，所以引入参数 $γ$ ，最终得到 XGBoost 模型结构损失函数的完整表达式：
  
  $Obj=\sum_{i=1}^{n}[g_if_m(x_i)+\frac{1}{2}h_if_m^2(x_i)]+\frac{1}{2}λ\sum_{t=1}^{T}w_t^2+γ|T|+C$
  
  其中 $\sum_{i=1}^{n}$ 表示遍历所有的样本，考虑将 $f_m(x_i)$ 改写为 $w_{q(x_i)}$ ，遍历每个叶节点进行表示：
  
  $\begin{aligned}Obj=&\sum_{t=1}^{T}[(\sum_{i∈x}g_i)w_t+\frac{1}{2}(\sum_{i∈x}h_i)w_t]+\frac{1}{2}λ\sum_{t=1}^{T}w_t^2+γ|T|+C\\ =&\sum_{t=1}^{T}[(\sum_{i∈x}g_i)w_t+\frac{1}{2}(λ+\sum_{i∈x}h_i)w_t]+γ|T|+C \end{aligned}$
  
  令 $\sum_{i}g_i=G_t，\sum_{i}h_i=H_t$ ，其中 $i$ 表示叶节点 $t$ 中的所有样本，得到：
  
  $l(y_i, y_i^{(m-1)})=\sum_{t=1}^{T}[G_tw_t+\frac{1}{2}(λ+H_t)w_t]+γ|T|+C$
  
  对于中括号内的项，是一个二次函数形式： $ax^2+bx$ ，其最优解为 $x=-\frac{b}{2a}=-\frac{G_i}{λ+H_i}$ ，代入原式并省略常数项得：
  
  $obj=-\frac{1}{2}\sum_{t=1}^{T}(\frac{G_t^2}{λ+H_t})+γ|T|，即结构分数$
  
  而后再对叶节点进行划分。整体思路相当于先对树的整体结构的损失函数进行正则约束优化，找到最优树结构，而后再对叶节点内部样本求解最优划分方式，是贪心策略的二次规划。
  
  对于叶节点的分裂，我们可以通过推导出来的目标函数 $Obj$ 计算结构分数，通过结构分数计算增益 Gain，Gain 值越大分裂效果越好：
  
  $\mathop{}_{~~~~~L,R}^{argmax}Gain=\mathop{}_{~~~~~L,R}^{argmax}\frac{1}{2}[(\frac{G_L^2}{λ+H_L}+\frac{G_R^2}{λ+H_R}-\frac{(G_L+G_R)^2}{λ+H_L+H_R})]-γ$
  
  我们发现在分裂时依赖于损失函数与各样本对于损失函数的一阶二阶导数值，所以我们可以在最开始遍历所有样本对于损失函数的一阶二阶导数值备用，计算分裂时直接取值即可。
  
  xgboost 因为有泰勒二阶展开的存在，所以无论损失函数是怎样的，都可以转换成二次函数，并利用 $x=-\frac{b}{2a}$ 求得目标函数的最优值。
2. 预剪枝
  
  其中正则项的引入是为了约束复杂度，而对于树来讲就意味着剪枝。剪枝又分为预剪枝与后剪枝，在 XGBoost 中加入的正则项起到的是预剪枝的作用。
  
  要想从所有树结构中寻找最优的树结构是一个 NP难问题，因此在实际中往往采用贪心法来构建一个次优树结构，基本思想是从根节点开始，每次对一个叶子结点进行分裂，针对每一种可能的分裂，根据特定的准则选取最优的分裂。
  
  对于准则，ID3 采用了信息增益，C4.5 使用了信息增益比，CART 选择了 Gini 系数，XGBoost 也有自己的准则。
  
  XGBoost 是通过将预测值代入到损失函数中，求出以当前特征分裂时损失函数的最小值，并且容易计算出分列前与分裂后损失函数的差值。XGBoost 采用最大化这个差值作为准则来进行决策树的构建，通过遍历所有特征的所有取值，寻找使得损失函数前后相差最大时对应的分裂方式。此外，由于损失函数前后的差值一定为正，所以此时 $γ$ 起到了一定的预剪枝效果。
  
  实际上 XGBoost 在训练中加入正则项进行预剪枝的思想，与我们一般情况加入 L₁，L₂ 正则项约束模型复杂度，减少过拟合的思想是一致的。只不过对于树结构来说产生了预剪枝的效果。
3. 与 GBDT 的比较
  
  ① GBDT 是机器学习算法，XGBoost 是该算法的工程实现
  
  ② 在使用 CART 作为基分类器时，XGBoost 显式地加入了正则项来控制模型的复杂度，可以通过预剪枝防止过拟合
  
  ③ GBDT 只使用了一阶导数的信息，XGBoost 对损失函数进行泰勒二阶展开，可以同时使用一阶和二阶的信息
  
  ④ 传统的 GBDT 采用 CART 作为基分类器时，XGBoost 支持多种类型的分类器，比如线性分类器
  
  ⑤ 传统的 GBDT 在每轮迭代使用全部数据，XGBoost 则采用了与随机森林相似的策略，支持对数据进行采样
  
  ⑥ 传统的 GBDT 没有设计对缺失值进行处理，XGBoost 能够自动学习出缺失值的处理策略。

机器学习 - 提升树（下）- XGBoost 以及与 GBDT 的比较

机器学习 - 提升树（下）- XGBoost 以及与 GBDT 的比较

XGBoost（eXtreme Gradient Boost）

原理

预剪枝

与 GBDT 的比较

浏览过的版块