跳至内容

XGBoost推导

XGBoost 用损失的一阶、二阶导数计算叶子输出，再用分裂增益选择划分。

发布于 更新于 约 15 分钟阅读 浏览 — 次
  • 机器学习
  • 集成学习
  • XGBoost
  • 复杂度
  • 正则化
  • 损失函数

XGBoost（Extreme Gradient Boosting）是一个梯度提升库，可用于回归、分类等任务。 其中的树模型逐轮增加一棵回归树，用新树修正已有预测，并在目标函数中加入正则化项，限制模型复杂度。

训练每棵新树时，需要确定两件事：

  1. 树怎样划分样本：选择哪些特征和切分点，让样本分别落入哪些叶子。
  2. 每个叶子输出多少：落入同一叶子的样本，共用一个预测修正量。

XGBoost 用损失函数的二阶近似求解：先假定树的结构已确定，求出各叶子的最优输出；再用这些最优输出计算分裂增益，选择划分。本文讨论单输出回归和二分类。

1. 每轮在已有模型上增加一棵树

回归树通过特征条件逐步划分样本，每个叶子保存一个实数。预测时，样本沿分支到达某个叶子，取出这个数作为树的输出。

设训练集有 nn 个样本，xix_i 是第 ii 个样本的特征，yiy_i 是它的真实标签。尚未加入任何树时，模型先给出初始预测 F0(x)F_0(x)；例如平方损失回归可以从训练标签的均值开始。第 tt 轮加入新树 ftf_t 后：

Ft(x)=Ft−1(x)+ft(x)=F0(x)+∑k=1tfk(x).F_t(x)=F_{t-1}(x)+f_t(x)=F_0(x)+\sum_{k=1}^{t}f_k(x).

上一轮预测 Ft−1F_{t-1} 包含初始预测和此前所有树的输出。 训练新树时，旧模型保持不变，本轮只学习 ftf_t 的结构和叶子值。这就是树提升使用的加法模型。上式先令学习率为 1，后文再加入学习率。

用 qt(x)q_t(x) 表示样本 xx 落入的叶子编号，TT 表示本轮树的叶子数，wjw_j 表示第 jj 个叶子的输出：

ft(x)=wqt(x),qt(x)∈{1,…,T}.f_t(x)=w_{q_t(x)},\qquad q_t(x)\in\{1,\ldots,T\}.

对于平方损失回归，累加结果 Ft(x)F_t(x) 就是预测值。对于二分类，标签取 yi∈{0,1}y_i\in\{0,1\}，模型先累加原始分数，再通过 sigmoid 函数转成正类概率：

pt(x)=σ(Ft(x))=11+e−Ft(x).p_t(x)=\sigma(F_t(x))=\frac{1}{1+e^{-F_t(x)}}.

最后再用概率阈值决定类别。分类任务中的树也输出实数修正量：正值提高当前分数，负值降低当前分数，叶子本身不直接输出最终类别。

2. 目标函数：拟合误差与树复杂度

用 ℓ(yi,Ft(xi))\ell(y_i,F_t(x_i)) 衡量模型预测与真实标签之间的误差，用 Ω(fk)\Omega(f_k) 衡量第 kk 棵树的复杂度。第 tt 轮的完整目标为：

J(t)=∑i=1nℓ(yi,Ft(xi))+∑k=1tΩ(fk).\mathcal{J}^{(t)}=\sum_{i=1}^{n}\ell\bigl(y_i,F_t(x_i)\bigr)+\sum_{k=1}^{t}\Omega(f_k).

训练时最小化 J(t)\mathcal{J}^{(t)}。树的复杂度由叶子数量和叶子输出的大小共同衡量；这里对叶子输出只考虑 L2 正则化，不加入 L1 项：

Ω(f)=γT+λ2∑j=1Twj2,γ,λ≥0.\Omega(f)=\gamma T+\frac{\lambda}{2}\sum_{j=1}^{T}w_j^2,\qquad \gamma,\lambda\ge 0.
  • γT\gamma T 惩罚叶子数量。 每增加一个叶子，目标函数就增加 γ\gamma，分裂带来的改善需要抵消这项成本。
  • L2 项惩罚叶子值的幅度。 同样的拟合改善下，较小的叶子值受到的惩罚更低。

两棵树都有两个叶子，叶值分别为 (50,50)(50,50) 和 (0,100)(0,100)。它们的叶子值平方和分别为 50005000 和 1000010000，因此 L2 惩罚分别为 2500λ2500\lambda 和 5000λ5000\lambda。

两棵树的叶子数量惩罚相同。在预测损失也相同且 λ>0\lambda>0 时，第一棵树的总目标值更小。

3. 二阶展开：把损失化为本轮树的函数

记上一轮的预测分数为 si=Ft−1(xi)s_i=F_{t-1}(x_i)，本轮加入新树后变为 si+ft(xi)s_i+f_t(x_i)。在 sis_i 处对损失做二阶泰勒展开：

ℓ(yi,si+ft(xi))≈ℓ(yi,si)+gift(xi)+12hift(xi)2.\ell\bigl(y_i,s_i+f_t(x_i)\bigr)\approx\ell(y_i,s_i)+g_i f_t(x_i)+\frac{1}{2}h_i f_t(x_i)^2.

其中 gig_i、hih_i 是损失对预测分数的一阶、二阶导数，均在上一轮预测处计算：

gi=∂ℓ(yi,s)∂s∣s=si,hi=∂2ℓ(yi,s)∂s2∣s=si.g_i=\left.\frac{\partial\ell(y_i,s)}{\partial s}\right|_{s=s_i},\qquad h_i=\left.\frac{\partial^2\ell(y_i,s)}{\partial s^2}\right|_{s=s_i}.

gig_i 决定局部的下降方向：gi>0g_i>0 时，减小分数有利于降低损失；gi<0g_i<0 时，应增大分数。hih_i 描述损失曲线的弯曲程度，与正则化系数共同影响修正量的大小。

平方损失回归采用 ℓ(y,s)=12(y−s)2\displaystyle\ell(y,s)=\frac12(y-s)^2，因此：

gi=si−yi,hi=1.g_i=s_i-y_i,\qquad h_i=1.

二分类采用二元交叉熵。令 p=σ(s)p=\sigma(s)，损失及其在当前分数处的导数为：

ℓ(y,s)=−yln⁡p−(1−y)ln⁡(1−p),gi=pi−yi,hi=pi(1−pi),pi=σ(si).\begin{aligned} \ell(y,s)&=-y\ln p-(1-y)\ln(1-p),\\ g_i&=p_i-y_i,\qquad h_i=p_i(1-p_i),\qquad p_i=\sigma(s_i). \end{aligned}

平方损失本身是二次函数，二阶展开是精确的；对二元交叉熵，这里得到的是局部近似，后续计算的分裂增益也以这个近似目标为依据。

本轮训练时，ℓ(yi,si)\ell(y_i,s_i) 和旧树的复杂度都是与 ftf_t 无关的常数，去掉它们后得到：

J~(t)=∑i=1n[gift(xi)+12hift(xi)2]+Ω(ft).\widetilde{\mathcal{J}}^{(t)}=\sum_{i=1}^{n}\left[g_i f_t(x_i)+\frac12h_i f_t(x_i)^2\right]+\Omega(f_t).

旧模型的影响仍然保留在 sis_i、gig_i 和 hih_i 中。

4. 按叶子汇总，求最优输出

固定当前树的结构 qtq_t，每个样本属于哪个叶子就确定了。同一叶子中的样本共享输出 wjw_j，因此可以把按样本求和改成按叶子求和。

令 Ij={i:qt(xi)=j}I_j=\{i:q_t(x_i)=j\} 为落入叶子 jj 的样本下标集合。代入 ft(xi)=wjf_t(x_i)=w_j，并展开正则化项：

J~(t)=∑i=1n[gift(xi)+12hift(xi)2]+γT+λ2∑j=1Twj2=∑j=1T[∑i∈Ijgiwj+12∑i∈Ijhiwj2]+γT+λ2∑j=1Twj2=∑j=1T[(∑i∈Ijgi)wj+12(∑i∈Ijhi+λ)wj2]+γT.\begin{aligned} \widetilde{\mathcal{J}}^{(t)} &=\sum_{i=1}^{n}\left[g_i f_t(x_i)+\frac12h_i f_t(x_i)^2\right] +\gamma T+\frac\lambda2\sum_{j=1}^{T}w_j^2\\ &=\sum_{j=1}^{T}\left[\sum_{i\in I_j}g_iw_j+\frac12\sum_{i\in I_j}h_iw_j^2\right] +\gamma T+\frac\lambda2\sum_{j=1}^{T}w_j^2\\ &=\sum_{j=1}^{T}\left[\left(\sum_{i\in I_j}g_i\right)w_j +\frac12\left(\sum_{i\in I_j}h_i+\lambda\right)w_j^2\right]+\gamma T. \end{aligned}

第二行按叶子分组；第三行把同一叶子的 wjw_j 提到求和外，并将损失中的二次项与 L2 项合并。每个叶子只需要保留两个统计量：

Gj=∑i∈Ijgi,Hj=∑i∈Ijhi.G_j=\sum_{i\in I_j}g_i,\qquad H_j=\sum_{i\in I_j}h_i.

分别表示该叶子中一阶、二阶导数的总和。于是目标简化为：

J~(t)=∑j=1T[Gjwj+12(Hj+λ)wj2]+γT.\widetilde{\mathcal{J}}^{(t)}=\sum_{j=1}^{T}\left[G_jw_j+\frac12(H_j+\lambda)w_j^2\right]+\gamma T.

当 Hj+λ>0H_j+\lambda>0 时，每个叶子对应一个关于 wjw_j 的凸二次函数，不同叶子的输出可以分别求解。对 wjw_j 求导并令导数为零：

Gj+(Hj+λ)wj=0⟹wj∗=−GjHj+λ.G_j+(H_j+\lambda)w_j=0 \quad\Longrightarrow\quad w_j^*=-\frac{G_j}{H_j+\lambda}.

wj∗w_j^* 是固定树结构下叶子 jj 的最优输出。 固定 GjG_j 时，Hj+λH_j+\lambda 越大，输出的绝对值越小。

以平方损失为例，HjH_j 就是叶子里的样本数，−Gj-G_j 是残差之和。因此 λ=0\lambda=0 时，最优叶子值就是该叶子内的平均残差；λ>0\lambda>0 时，输出会向 0 收缩。

再把 wj∗w_j^* 代回单个叶子的目标项：

Gj(−GjHj+λ)+12(Hj+λ)(−GjHj+λ)2=−Gj22(Hj+λ).G_j\left(-\frac{G_j}{H_j+\lambda}\right) +\frac12(H_j+\lambda)\left(-\frac{G_j}{H_j+\lambda}\right)^2 =-\frac{G_j^2}{2(H_j+\lambda)}.

对所有叶子求和，加上叶子数量惩罚，就得到当前树结构 qtq_t 的评分：

J~∗(qt)=−12∑j=1TGj2Hj+λ+γT.\widetilde{\mathcal{J}}^*(q_t)=-\frac12\sum_{j=1}^{T}\frac{G_j^2}{H_j+\lambda}+\gamma T.

这个评分是当前树结构下二阶近似目标的最小值，越小越好。

5. 分裂增益：比较分裂前后的目标

将一个叶子分成左右两个叶子，分别汇总得到 (GL,HL)(G_L,H_L)、(GR,HR)(G_R,H_R)。原叶子的统计量是两者之和。

其余叶子保持不变，比较时可以消去它们的目标项，只看这个叶子分裂前后的变化：

J前∗=−12(GL+GR)2HL+HR+λ+γ,J后∗=−12[GL2HL+λ+GR2HR+λ]+2γ.\begin{aligned} \mathcal{J}_{\text{前}}^* &=-\frac12\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}+\gamma,\\ \mathcal{J}_{\text{后}}^* &=-\frac12\left[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}\right]+2\gamma. \end{aligned}

定义分裂增益 = 分裂前目标 − 分裂后目标，相减得到：

Gain=12[GL2HL+λ+GR2HR+λ−(GL+GR)2HL+HR+λ]−γ.\mathrm{Gain}=\frac12\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.

括号中比较“左右叶子分别输出”与“原叶子共用一个输出”的效果，其中已包含 L2 正则化。末尾的 −γ-\gamma 对应新增一个叶子的成本。

这里的 Gain 已经扣除 γ；有收益的条件是 Gain > 0。 实际分裂还需满足深度、子节点权重等约束。

一个数值例子

假设候选划分得到 GL=−4,HL=2G_L=-4,H_L=2，GR=4,HR=2G_R=4,H_R=2，并设置 λ=1,γ=1\lambda=1,\gamma=1。

原叶子的梯度总和为 0，因此原输出为 0；分开后，两个叶子的最优输出分别为 43\displaystyle\frac43 和 −43\displaystyle-\frac43。代入增益公式：

Gain=12(163+163−0)−1=133>0.\mathrm{Gain}=\frac12\left(\frac{16}{3}+\frac{16}{3}-0\right)-1=\frac{13}{3}>0.

分裂前，两组相反的梯度相互抵消，只能共用修正量 0；分裂后，两组样本分别得到正、负修正。保持划分和 λ\lambda 不变，若把 γ\gamma 提高到 6，净增益就变成 163−6=−23<0\displaystyle\frac{16}{3}-6=-\frac23<0，说明改善不足以抵消新增叶子的惩罚。

怎样找到候选划分

对数值特征，精确贪心方法按特征值排序，移动候选阈值时累计左右两侧的 GG、HH，比较各阈值的增益。直方图方法先把值归入有限个桶，再比较桶边界，以减少搜索成本。

训练从简单的树开始，在当前叶子上比较允许的候选划分，逐步增加分支。因此，叶子值是在固定结构下求最优，树结构则通过贪心搜索确定，并没有枚举所有树。

训练后，Booster.get_score 可以按不同口径统计特征重要性：

  • weight：该特征用于分裂的次数。
  • gain：使用该特征的各次分裂的平均增益。
  • total_gain：这些分裂增益的总和。

这里的 gain、total_gain 汇总的是实现记录的分裂分数。它与上文净增益的缩放不同，且未扣除 γ\gamma，不能直接用上文的 Gain 数值求平均或求和。

6. 学习率与其他训练机制

学习率与采样

学习率 η\eta 缩小新树对模型的贡献。前文先求一棵树的更新，再按比例加入：

Ft(x)=Ft−1(x)+ηft(x).F_t(x)=F_{t-1}(x)+\eta f_t(x).

上一节左叶子的输出为 43\displaystyle\frac43，取 η=0.1\eta=0.1 后，实际加到已有分数上的量约为 0.1330.133。

下一轮用更新后的模型重新计算 gig_i、hih_i，再训练下一棵树。较小学习率通常需要更多轮次，二者应结合验证集表现选择。

采样则改变本轮使用的数据和可选特征：

  • subsample 控制每轮使用的训练样本比例。
  • colsample_bytree 按树选择特征子集。
  • colsample_bylevel、colsample_bynode 分别按层和节点选择特征，比例会累积作用；colsample_bynode 不适用于 exact。

生长限制与剪枝

  • max_depth 限制树的最大深度。
  • min_child_weight 要求每个子节点的二阶导数总和 HjH_j 达到阈值。对本文未加样本权重的平方损失，hi=1h_i=1，它才对应最少样本数；二分类时 hi=pi(1−pi)h_i=p_i(1-p_i)，就不能这样解释。

prune 更新器会删除损失改善不足或深度超限的分裂。

缺失值的默认方向

树模型可以为分裂学习一个缺失值默认方向。对于某个候选阈值，步骤如下：

  1. 按阈值划分非缺失样本，固定它们所在的左右两侧。
  2. 将该特征缺失的样本全部计入左侧，重新汇总两侧的 GG、HH 并计算增益。
  3. 再将这些缺失样本全部计入右侧，计算另一方案的增益，选择更好的方向。

预测时，若样本在这个分裂特征上缺失，就沿保存的默认方向继续走。方向属于每个分裂节点，因此不同节点可以选择不同方向。

模型学到的是“缺失样本如何分支”，没有恢复丢失的特征值。缺失比例和线上缺失方式变化带来的影响，仍需验证。

评论

使用 GitHub 登录后参与讨论，评论将公开保存在 GitHub。

阅读到这里时加载评论。