XGBoost 算法原理

XGBoost(Extreme Gradient Boosting)最初由华盛顿大学计算机系博士生陈天奇在 2014 年开发,旨在对传统梯度提升算法(GBDT)进行高效实现和优化。2015 年,XGBoost 在 Kaggle 竞赛中表现卓越,当年 29 个 Kaggle 冠军队伍中有 17 队在他们的解决方案中使用了 XGBoost,这使得它几乎横扫了 Kaggle 的众多榜单。凭借卓越的性能和广泛的适用性,XGBoost 很快成为竞赛和工业界的标配算法,被广泛应用于金融风控、推荐系统、广告点击率预测、科研建模等领域。

1. 初步理解

在 GBDT 中,每一棵决策树的目标都是让损失函数尽可能减小。由于没有任何复杂度约束,模型往往会“贪心”地分裂节点,从而易生成深度大、叶子节点数量多的不平衡树。这样的模型虽然在训练集上表现很好,但泛化能力较弱,推理性能也不理想。

XGBoost 在此基础上引入了正则化项,将模型复杂度纳入损失函数的考量范围。这样一来,模型在每次分裂时,不仅追求降低损失,还会权衡树的平衡性与复杂度,从而构建出更稳定、更具泛化能力的树结构。

另一方面,GBDT 在优化过程中只使用损失函数的一阶导数(即负梯度)。一阶导数能告诉我们“该往哪个方向调整”,但它的信息量有限,只能提供方向,而无法反映该方向上“地形”的起伏程度。

可以把它想象成开车导航的过程:你从老家出发去北京,导航告诉你“往北开”——这就像一阶导数,能指明方向,但不知道前方路况。如果前方是陡坡,你仍按平路的节奏前进,结果推进缓慢;如果是下坡,你又保持同样的速度,可能一下子就冲过了目标。这对应到优化中,就是更新幅度不合适——步子有时太小,收敛慢;有时太大,容易震荡。

而二阶导数(Hessian)就像你提前知道了前方路面的坡度:它能告诉你“方向上曲率的陡峭程度”。根据这些信息,你可以自动调整前进的力度——坡陡时放缓,路平时稳步前进。
这就使得模型在每次迭代时,不仅能找准方向(由一阶导提供),还能根据曲率大小智能控制更新幅度(由二阶导修正),从而让整个优化过程更加稳健、高效。

因此,XGBoost 通过引入二阶信息,使得训练不再只是“沿着方向走”,而是能“根据地形调整步伐”,从而收敛更快、更稳定。

2. 公式推导

2.1 损失表示

XGBOOST 的损失函数包含两部分:

  • 训练误差:衡量模型在训练数据上误差
  • 正则化项:用于控制模型复杂度,通常会对树的叶子数、叶子权重等进行惩罚
  • \( T \) 表示叶子节点数量,这一项是考量树的结构复杂度。树的叶子节点数量越多,意味着其结构就越复杂,γ 用于调节树的复杂度,γ 越大,就意味着树的复杂度对最终的损失值影响就越大,当两棵梯度提升树的损失值一样时,优先选择结构更加简单的那棵树。
  • \( w \) 表示叶子节点输出值组成的向量。这一项是考量树的输出复杂度。如果叶子输出值很大,意味着该棵树对预测的贡献就很大,这可能导致训练误差快速下降,但容易过拟合或对异常值敏感。叶子输出值越小,意味着每棵树对总预测的贡献越平稳,配合加法模型和学习率,XGBoost 能稳步拟合,降低过拟合和预测波动的风险。
  • γ越大说明越希望模型简单一些。λ越大说明越希望模型输出平衡一些。

对于损失函数而言,之前的 \( t-1 \) 棵树已经构建完毕,相当于常数,无法进行优化。我们得思考如何构建第 \( t \) 棵树,让损失进一步降低。

我们对损失函数在 \( t-1 \) 位置进行泰勒二阶展开,目的是通过 \( t-1 \) 位置的一阶导和二阶导信息来近似出 \( f_{t} \) 棵树如何进行输出才能进一步降低损失。

注意:\( g_{i} \) 表示样本的一阶导数,\( h_{i} \) 表示样本的二阶导数。

我们把常数项(已经构建好的树)去掉,把优化的目标聚焦到当前要构建的 \( f_{t} \) 上。

我们继续对公式进行转换:

注意:上述公式中,\( w \) 表示叶子节点的输出值。

接下来,目标函数转换为:

上面的式子太复杂了,我们令:

\( G_{i} \) 表示叶子结点上一阶导之和,\( H_{i} \) 表示叶子结点上的二阶导之和。现在我们得到当前要构建的这棵树的损失表示:

当前这棵树的损失,主要是由叶子节点的输出值来决定的。所以,我们通过对 \( w \) 求导来计算叶子节点的最优输出值表示:

此时,将叶子节点输出值得公式代回到 \( L_{t} \) 公式中,得到:

至此,我们就得到了一个用来衡量当前这棵树损失的表示公式。

2.2 分裂增益

我们需要明确一点:\( f_{t} \) 树的损失是由多个叶子节点的损失组成的。根据前面的公式可知,单个叶子节点的损失表示为:

我们再思考一个问题:当进行分裂的时候,是某个节点一分为二了,那么该节点分裂后的损失是由新产生的左节点和右节点的损失组成。

那么,我们可以通过衡量某个节点分列前和分裂后的损失来构建一个分裂增益:

  • 当 Gain > 0,说明分裂后的损失更小
  • 当 Gain <= 0,说明分裂后损失不会下降,不适合分裂

这个公式就是 XGBoot 算法的分裂增益计算公式,在 XGBoost 的树构建过程中,在所有候选切分点中选择分裂增益(Gain)最大的那个进行分裂

3. 计算案例

样本xy
114
225
338
449

损失函数:平方损失,λ = 1, γ = 0

损失函数一阶导和二阶导计算公式:

初始预测取均值:

计算每个样本的一阶导和二阶导值:

样本xy初始预测 \(g_{i}\)\(h_{i}\)
1146.5+2.51
2256.5+1.51
3386.5−1.51
4496.5−2.51

我们以分裂点 x<2.5 为例,计算下其分裂增益:

节点样本集合一阶导和 (G)二阶导和 (H)
左子集(1, 2)2.5+1.5 = 4.01+1=2
右子集(3, 4)-1.5+(-2.5) =-4.01+1=2
父节点(1, 2, 3, 4)2.5+1.5-1.5-2.5 = 01+1+1+1=4

带入到分裂增益计算公式中:

最终得到 5.333 为分裂点 2.5 的信息增益值。假设,我们以 2.5 作为分裂点,得到两个叶子节点,其输出值:

节点GH + λ输出 w
左节点43-1.333
右节点-431.333

未经允许不得转载:一亩三分地 » XGBoost 算法原理
评论 (0)

5 + 1 =