XGBoost 提升树原理精讲：从监督学习三要素到结构分数与分裂增益的完整推导

XGBoost 提升树原理精讲从监督学习三要素到结构分数与分裂增益的完整推导【免费下载链接】xgboostScalable, Portable and Distributed Gradient Boosting (GBDT, GBRT or GBM) Library, for Python, R, Java, Scala, C and more. Runs on single machine, Hadoop, Spark, Dask, Flink and DataFlow项目地址: https://gitcode.com/gh_mirrors/xg/xgboost导读本文以 XGBoost 官方教程《Introduction to Boosted Trees》为骨架系统讲解 XGBoostExtreme Gradient Boosting背后的提升树Boosted Trees数学原理——从监督学习的模型、参数与目标函数三要素出发逐步推导出树集成模型、加法训练、二阶泰勒展开、模型复杂度、结构分数与分裂增益公式并将每一步与当前仓库的 C 源码实现src/tree/param.h、src/gbm/gbtree.cc、include/xgboost/objective.h相互印证。读完本文你将彻底理解gamma、lambda、eta、min_child_weight等超参数在底层到底如何影响树的生长与剪枝也能掌握 XGBoost 为何能统一支持回归、分类、排序等各类自定义损失函数。一、为什么值得从数学原理而不是API 用法开始理解 XGBoost市面上绝大多数 XGBoost 教程都是从如何调用xgb.train调参讲起。而官方这份 model.rst 教程选择了一条更根本的路线用监督学习的通用语言把提升树从头推导一遍。这样的好处在于你将能清晰说出梯度提升树Gradient Boosted Trees与随机森林Random Forests模型相同、训练方式不同这一关键区别你将理解pruning剪枝、smoothing平滑这类启发式技巧背后形式化的目标函数推导而不是死记硬背经验规则你会明白为什么 XGBoost 的目标函数被设计成训练损失 正则化两部分以及这种设计如何同时服务于简单与预测能力强这两个目标即机器学习中著名的bias-variance tradeoff偏差-方差权衡。本文所有公式均来自官方教程原文并用仓库源码给出对应的实现证据做到公式有出处、实现有落点。二、监督学习的三个基本要素2.1 模型Model与参数Parameters在监督学习中模型描述的是从输入特征x_i得到预测值y_i的数学结构。最常见的例子是线性模型y_hat_i Σ_j θ_j · x_ij即对加权输入特征做线性组合。预测值本身可以有多种解释方式取决于任务类型回归直接作为目标值分类经过 logistic 变换后得到正类概率排序直接作为 ranking score 用于输出排序。参数则是模型中需要从数据中学习的未知部分。在线性回归中参数就是系数θ。习惯上我们统一用θ泛指模型的所有参数虽然实际模型中参数往往很多这里的定义是宽松的。2.2 目标函数训练损失 正则化训练模型的本质是寻找能最好拟合训练数据(x_i, y_i)的参数θ。为此需要定义**目标函数objective function**来衡量拟合好坏。XGBoost 目标函数的一个显著特征是它由两部分组成obj(θ) L(θ) Ω(θ)L(θ)训练损失training loss衡量模型对训练数据的可预测性。常用的选择包括均方误差MSE用于回归L(θ) Σ_i (y_i − ŷ_i)²logistic 损失用于逻辑回归L(θ) Σ_i [y_i·ln(1e^(−ŷ_i)) (1−y_i)·ln(1e^(ŷ_i))]Ω(θ)正则化项regularization term控制模型复杂度帮助避免过拟合。这是很多人最容易忽略的部分。官方教程用一个拟合阶梯函数的示意图图片链接见 model.rst来说明偏差-方差权衡面对同样的数据点三个候选的阶梯函数中那个既简单又能解释数据的解图中红色标记才是最佳拟合。总原则是我们既想要简单的模型又想要预测能力强的模型。2.3 为什么要把原理形式化把上述要素形式化有几个直接收益它构成了机器学习工具包的自然构建模块——掌握了这套语言你可以轻松描述梯度提升树与随机森林的异同它能帮助你理解我们到底在优化什么目标以及pruning剪枝、smoothing平滑等启发式技巧为什么会有效。三、决策树集成Decision Tree EnsemblesXGBoost 的模型选择3.1 CART 与普通决策树的区别XGBoost 的模型是决策树集成由一组**分类回归树CARTClassification and Regression Trees**组成。CART 与普通决策树有一个关键区别CART 的每个叶子节点关联一个实数分数score而不仅仅是决策值。官方教程用预测某家庭成员是否会喜欢电脑游戏 X的例子说明每个成员根据特征被划分到不同叶子每个叶子赋予一个分数表示该叶子对应样本的预测贡献这种叶子带实数值的设计让 CART 拥有超越分类的丰富解释力也为后续统一的、有原则的优化提供了基础。3.2 集成多棵树求和单棵树往往不够强实际使用的是集成模型——把多棵树的预测相加。官方教程给出一个由两棵 CART 组成的集成示例并强调一个关键事实两棵树试图互相互补complement。数学上树集成模型可以写成ŷ_i Σ_{k1}^{K} f_k(x_i), f_k ∈ F其中K是树的数目f_k是函数空间F所有可能的 CART 集合中的一个函数。对应的目标函数为obj(θ) Σ_{i1}^{n} l(y_i, ŷ_i) Σ_{k1}^{K} ω(f_k)其中ω(f_k)是树f_k的复杂度其具体定义将在后文展开。3.3 有趣的推论随机森林与提升树是同一个模型这里官方教程提出了一个巧妙的问题随机森林的模型是什么答案也是树集成因此随机森林与梯度提升树在模型层面完全相同区别只在于训练方式这意味着如果你为树集成编写一个预测服务它可以同时服务于随机森林和梯度提升树模型这也是为什么监督学习三要素这套语言如此有用——它让你看穿不同算法表面差异下的共同结构。从当前仓库的源码结构看这一设计得到了印证src/tree/目录下的各个 updater如 updater_quantile_hist.cc、updater_colmaker.cc、updater_gpu_hist.cu都实现了同一个 TreeUpdater 接口而模型结构统一存放在 tree_model.cc 中训练方式hist、approx、exact只是可插拔的生长策略。四、树提升Tree Boosting加法训练与二阶泰勒展开确定了模型之后问题变成如何学习这些树答案与所有监督学习模型一致——定义目标函数并优化它设第t步的目标函数为obj Σ_{i1}^{n} l(y_i, ŷ_i^(t)) Σ_{k1}^{t} ω(f_k)其中t是当前集成中树的数目每一步训练添加一棵新树因此第t步时K t。4.1 加法训练Additive Training树学习的难点在于树的参数是函数f_k包含树的结构与叶子分数学习树结构远比传统上直接求梯度的优化问题困难一次性学习所有树在计算上是不可行的intractable。因此 XGBoost 采用加法策略additive strategy固定已学到的部分每一步只新增一棵树。设第t步的预测值为ŷ_i^(t)则ŷ_i^(0) 0 ŷ_i^(1) f_1(x_i) ŷ_i^(0) f_1(x_i) ŷ_i^(2) f_1(x_i) f_2(x_i) ŷ_i^(1) f_2(x_i) ... ŷ_i^(t) Σ_{k1}^{t} f_k(x_i) ŷ_i^(t-1) f_t(x_i)那么每一步该选择哪棵树自然是能让目标函数最优的那棵。第t步的目标可以改写为obj^(t) Σ_{i1}^{n} l(y_i, ŷ_i^(t-1) f_t(x_i)) ω(f_t) constant4.2 MSE 下的友好形式如果损失函数取均方误差MSE目标函数会呈现非常友好的形式——只有一阶项即残差和二次项obj^(t) Σ_{i1}^{n} [2(ŷ_i^(t-1) − y_i)·f_t(x_i) f_t(x_i)²] ω(f_t) constant4.3 通用情形损失函数二阶泰勒展开但对其他损失如 logistic 损失很难得到这样漂亮的形式。因此 XGBoost 在一般情形下对损失函数做二阶泰勒展开obj^(t) Σ_{i1}^{n} [l(y_i, ŷ_i^(t-1)) g_i·f_t(x_i) (1/2)·h_i·f_t(x_i)²] ω(f_t) constant其中一阶梯度g_i与二阶梯度h_i定义为g_i ∂/∂ŷ_i^(t-1) l(y_i, ŷ_i^(t-1)) h_i ∂²/∂(ŷ_i^(t-1))² l(y_i, ŷ_i^(t-1))去掉所有常数项后第t步的具体目标为Σ_{i1}^{n} [g_i·f_t(x_i) (1/2)·h_i·f_t(x_i)²] ω(f_t)这是全文最核心的结论之一新树的目标函数值只依赖g_i和h_i这两个统计量。正是这一点让 XGBoost 得以支持任意自定义损失函数——无论 logistic 回归还是 pairwise ranking只要提供每个样本的一阶、二阶梯度就可以使用完全相同的求解器来优化。这一设计在源码中体现得淋漓尽致目标函数抽象为 include/xgboost/objective.h 中的ObjFunction基类其核心虚函数正是GetGradient(preds, info, iter, out_gpair)——输出每个样本的梯度对GradientPair即g_i与h_i各内置目标函数通过XGBOOST_REGISTER_OBJECTIVE宏注册例如src/objective/squared_error_obj.cc中的XGBOOST_REGISTER_OBJECTIVE(SquaredErrorRegression, reg:squarederror)、src/objective/logistic_obj.cc中的binary:logistic以及src/objective/lambdarank_obj.cc中的rank:ndcg/rank:pairwise等树的生长阶段完全不感知具体损失函数只消费梯度对——这正是文档所说用同一个求解器优化所有损失的实现方式。五、模型复杂度Model Complexity正则化的形式化定义训练步骤已经就绪但还缺一个重要部件正则化项。为了定义树的复杂度ω(f)首先需要把树的定义精确化f_t(x) w_{q(x)}, w ∈ R^T, q: R^d → {1, 2, ..., T}w叶子分数向量q把每个数据点分配到对应叶子的函数T叶子数量。在 XGBoost 中复杂度定义为ω(f) γT (1/2)·λ·Σ_{j1}^{T} w_j²这个定义在实践中有两个作用γT惩罚叶子数量鼓励更浅/更小的树(1/2)λΣw_j²对叶子分数做 L2 正则鼓励分数更平滑。官方教程特别指出很多树类包对正则化的处理不够谨慎甚至直接忽略。传统树学习只强调降低不纯度impurity复杂度控制靠启发式。而 XGBoost 通过形式化定义复杂度让我们更清楚自己在学什么从而在真实数据上得到更好的模型。在源码中这一公式与 src/tree/param.h 的参数一一对应gamma内部字段min_split_loss别名gamma对应公式中的γ即产生进一步划分所需的最小损失减少量默认值0.0下限0.0lambda内部字段reg_lambda别名lambda对应公式中的λ叶子权重的 L2 正则系数默认值1.0下限0.0alpha内部字段reg_alpha别名alphaL1 正则系数公式推导中默认λ项实际实现还支持 L1默认值0.0。下面这段从 src/tree/param.h 摘取的参数声明代码清晰展示了gamma与lambda的默认值与语义DMLC_DECLARE_FIELD(min_split_loss) .set_lower_bound(0.0f) .set_default(0.0f) .describe(Minimum loss reduction required to make a further partition.); DMLC_DECLARE_FIELD(reg_lambda) .set_lower_bound(0.0f) .set_default(1.0f) .describe(L2 regularization on leaf weight);六、结构分数The Structure Score衡量一棵树好坏的标准这是整个推导中魔术般的一步。重新整理树模型后第t棵树的目标函数值可以写成obj^(t) ≈ Σ_{i1}^{n} [g_i·w_{q(x_i)} (1/2)·h_i·w_{q(x_i)}²] γT (1/2)·λ·Σ_{j1}^{T} w_j² Σ_{j1}^{T} [(Σ_{i∈I_j} g_i)·w_j (1/2)·(Σ_{i∈I_j} h_i λ)·w_j²] γT其中I_j {i | q(x_i) j}是分配到第j个叶子的数据点索引集合。注意第二行把求和下标从样本换成了叶子——因为同一叶子上的所有数据点共享同一个分数。进一步压缩记号定义G_j Σ_{i∈I_j} g_i、H_j Σ_{i∈I_j} h_i得到obj^(t) Σ_{j1}^{T} [G_j·w_j (1/2)·(H_j λ)·w_j²] γT由于各w_j相互独立而G_j·w_j (1/2)(H_jλ)w_j²是关于w_j的二次型因此给定树结构q(x)时的最优叶子分数与能达到的最佳目标值分别为w_j* −G_j / (H_j λ) obj* −(1/2)·Σ_{j1}^{T} G_j²/(H_j λ) γT最后一个等式衡量的就是一棵树结构q(x)有多好。官方教程配图说明了它的计算方法对于给定的树结构把统计量g_i、h_i推到它们所属的叶子上求和后用公式计算树的好坏。这个分数就像决策树中的不纯度度量但额外把模型复杂度也考虑了进去。这个公式在源码中有着精确的对应实现。src/tree/param.h 中的CalcGain、CalcWeight、ThresholdL1三个设备函数直接实现了上述数学式并扩展了 L1 与max_delta_step约束// calculate weight given the statistics template typename TrainingParams, typename T XGBOOST_DEVICE std::enable_if_tstd::is_floating_point_vT, T CalcWeight(TrainingParams const p, T sum_grad, T sum_hess) { if (sum_hess 0.0) return 0.0; T dw -ThresholdL1(sum_grad, p.reg_alpha) / (sum_hess p.reg_lambda); if (p.max_delta_step ! 0.0f ::fabs(dw) p.max_delta_step) { dw ::copysign(p.max_delta_step, dw); } return dw; }注意w_j* −G_j/(H_j λ)在实现中对应-ThresholdL1(sum_grad, reg_alpha) / (sum_hess reg_lambda)当reg_alpha 0时ThresholdL1退化为恒等与文档公式完全一致reg_alpha 0时则引入了 L1 的软阈值soft threshold处理。七、学习树结构分裂增益、剪枝与高效分裂搜索7.1 分裂增益公式与剪枝的由来有了衡量树好坏的标准后理想情况是枚举所有可能的树结构挑最好的——但实践中不可行intractable。于是 XGBoost 采用逐层贪心策略一次只优化树的一层。具体地把一片叶子分裂成两片时获得的增益为Gain (1/2)·[G_L²/(H_Lλ) G_R²/(H_Rλ) − (G_LG_R)²/(H_LH_Rλ)] − γ这个公式可以分解为四部分新左叶子的分数G_L²/(H_Lλ)新右叶子的分数G_R²/(H_Rλ)原叶子的分数(G_LG_R)²/(H_LH_Rλ)额外叶子的正则化惩罚γ。由此得到一个重要事实如果增益小于γ那么不加这个分支会更好。这正是树模型中剪枝pruning技术的精确由来官方教程强调通过监督学习的原理我们能够自然地推导出这些技巧之所以有效的理由。在源码中剪枝逻辑被显式实现。同样位于 src/tree/param.h 的NeedPrune函数[[nodiscard]] bool NeedPrune(double loss_chg, int depth) const { return loss_chg this-min_split_loss || (this-max_depth ! 0 depth this-max_depth); }即当损失变化小于gammamin_split_loss或深度超过max_depth时触发剪枝。同时src/tree/updater_prune.cc中还存在一个独立的pruneupdater负责在精确算法exact流程中做后剪枝。而CalcGain函数src/tree/param.h在reg_alpha 0且max_delta_step 0时的实现正是return common::Sqr(sum_grad) / (sum_hess p.reg_lambda);这与增益公式中的核心项G²/(Hλ)完全对应——分裂左右两侧的G²/(Hλ)之和减去父节点的值再减去γ即为分裂净增益。7.2 高效分裂搜索排序后从左到右扫描对于实值特征通常需要搜索最优切分点。为了高效实现XGBoost 把所有实例按特征值排序然后从左到右扫描一次即可计算出所有可能切分方案的结构分数从而高效找到最优切分。官方教程的示意图直观展示了这一过程图片链接见 model.rst。在实现层面这一从左到右扫描逻辑体现在分裂枚举器EnumerateSplit中例如 src/tree/hist/evaluate_splits.h 中GradStats梯度统计的EnumerateSplit与 updater_quantile_hist.cc 的贪心分裂循环。对于hist方法特征值被分箱bin量化后每个箱子累积(G, H)统计扫描时逐步累加形成左侧统计、用父节点统计做差得到右侧统计从而在线性时间内评估所有候选切分点。这也是 XGBoost 能在大规模数据上高效训练的关键。7.3 加法树学习的局限性官方说明由于枚举所有可能的树结构不可行XGBoost 每次只添加一个分裂一次只考虑一个特征维度。官方教程明确指出这种方法的局限在大多数情况下工作良好但在某些边缘场景下会失败——例如当问题本质上需要跨多个特征维度的组合运算如简单的算术运算时逐特征贪心可能导致退化的模型。教程引用了一个名为 Can Gradient Boosting Learn Simple Arithmetic? 的经典案例来说明这一点。这提醒使用者提升树的表达能力依赖单特征分裂的组合对于需要特征间显式运算的极端问题可能需要其他建模手段。八、公式与源码参数速查表以下速查表把教程公式中的符号与 XGBoost 实际训练参数定义见 src/tree/param.h 与 src/gbm/gbtree.h一一对应便于实战调参时查阅公式符号含义XGBoost 参数内部字段/别名默认值取值范围γ复杂度中叶子数惩罚 / 分裂所需最小损失减少gammamin_split_loss0.0[0, ∞)λ叶子分数的 L2 正则系数lambdareg_lambda1.0[0, ∞)α叶子分数的 L1 正则系数alphareg_alpha0.0[0, ∞)T树中叶子数量由max_depth默认60表示不限制与max_leaves约束——w_j叶子分数由CalcWeight计算——η学习率每棵树的步长缩放etalearning_rate0.3[0, 1]—子节点所需最小 Hessian权重和min_child_weight1.0[0, ∞)—叶子权重更新的最大步长约束max_delta_step0.0无约束[0, ∞)—行采样比例subsample1.0(0, 1]—列采样比例按树/层/节点colsample_bytree/colsample_bylevel/colsample_bynode1.0(0, 1]补充说明几个与推导密切相关的参数行为eta的缩放在 src/gbm/gbtree.cc 的BoostNewTrees中学习率会根据并行树数量缩放tree_param_.learning_rate / new_trees.size()保证多棵树并行生长时总体步长等价于etamin_child_weight的作用分裂合法性检查IsValidSplitsrc/tree/param.h要求左右子节点的 Hessian 和均不小于min_child_weight这本质上是把H_L、H_R的下限写成了显式约束防止在 Hessian 过小的节点上继续分裂tree_method与 updater 的映射src/gbm/gbtree.cc 的MapTreeMethodToUpdaters把hist/auto映射到grow_quantile_histmakerCPU或grow_gpu_histGPU把approx映射到grow_histmaker把exact映射到grow_colmaker,prune——后者印证了精确算法中独立pruneupdater 的存在。九、从原理到实战如何在当前仓库中动手验证原理讲完后可以在当前仓库中实际运行与验证阅读官方教程原文完整推导见 doc/tutorials/model.rst阅读核心实现参数与公式对应关系见 src/tree/param.hCalcGain、CalcWeight、NeedPrune、TrainParam树提升主流程见 src/gbm/gbtree.cc目标函数接口见 include/xgboost/objective.h分裂枚举见 src/tree/hist/evaluate_splits.h尝试自定义损失函数按照XGBOOST_REGISTER_OBJECTIVE宏的注册模式参考 src/objective/squared_error_obj.cc 与 plugin/example/custom_obj.cc实现自己的目标函数——只需提供GetGradient输出每个样本的g_i、h_i即可无缝接入同一套树学习求解器这正是目标函数只依赖g_i和h_i这一设计的最直观体现通过 Python 侧体验参数效果使用xgboost.train或XGBClassifier调整gamma、lambda、min_child_weight、max_depth等参数观察验证集表现随参数的变化即可切身感受正则化对偏差-方差权衡的调节作用。十、总结XGBoost 是原理驱动的工程实现官方教程在结尾给出了对 XGBoost 的定位总结这里完整继承并加以说明XGBoost 正是由本教程所介绍的形式化原理驱动的工具——其目标函数设计训练损失 正则化、加法训练、二阶近似、结构分数与剪枝规则全部可以在 src/tree/param.h 与 src/gbm/gbtree.cc 中找到对应的代码实现同时它在系统优化与机器学习原理两方面都做了深入考量目标是打造一个scalable可扩展、portable可移植、accurate准确的库从监督学习三要素出发的整套推导最终都收敛到了 XGBoost 训练管线中最朴素的一环每一步只新增一棵让目标函数最优的树而目标函数只依赖每个样本的梯度统计(g_i, h_i)与树的复杂度正则项。理解了这一点你就掌握了 XGBoost 全部核心超参数的设计动机也具备了阅读其源码src/tree/、src/gbm/、src/objective/的完整知识地图。延伸阅读本文聚焦于提升树的数学原理关于树生长策略hist/approx/exact与参数调优的实操细节可继续阅读 doc/tutorials/param_tuning.rst 与 doc/treemethod.rst。【免费下载链接】xgboostScalable, Portable and Distributed Gradient Boosting (GBDT, GBRT or GBM) Library, for Python, R, Java, Scala, C and more. Runs on single machine, Hadoop, Spark, Dask, Flink and DataFlow项目地址: https://gitcode.com/gh_mirrors/xg/xgboost创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考