重学 ML 04：决策树与集成学习

本篇导读：在第一篇、第二篇与第三篇中，从逻辑回归、正则化到支持向量机，我们讨论的都是连续空间中的“全局平滑超平面”。但面对量纲悬殊、充满“IF-THEN”阶梯规则的异构表格数据，平滑曲面往往力不从心。本篇我们切入另一条演化支线——基于递归正交切分的决策树与集成学习：从香农信息熵的柯西方程起源与基尼指数的泰勒近似出发，拆解随机森林如何用特征子空间打破方差相关性地板（$\rho {\sigma }^2$），推演 GBDT 与 XGBoost 在函数空间的梯度提升，并厘清树模型无法跨出历史极值的外推边界。

---

1. 范式的分野：从“全局平滑超平面”到“局部正交分治”

在前三站中，无论是逻辑回归、岭回归/LASSO，还是支持向量机（SVM），它们本质上都属于同一个几何家族——连续空间中的全局平滑代数模型：

• 它们先将所有特征做加权求和 $w^{T}x+b$（或通过核函数计算全局成对内积 $K(x,x_i)$），试图用一条贯穿整个特征空间的平滑直线或高维曲面，一次性切开正负样本。

然而，当我们走出图像、语音等连续同构信号领域，踏入金融风控审批、电商推荐转化、医疗临床检验等真实的异构表格数据（Tabular Data）战场时，平滑超平面模型往往会遭遇三大棘手痛点：

1. 量纲悬殊与长尾分布：表格中第 1 列是“年龄（20~60 岁）”，第 2 列是“年收入（0~5000 万元）”，第 3 列是“近 30 天逾期次数（0, 1, 2…）”。对于依赖欧氏距离或内积的 SVM 和线性模型，如果不做极其精细的归一化与对数变换，大数值特征会瞬间统治梯度与核函数。
2. 强烈的轴平行阶梯规则（Axis-Aligned Step Rules）：人类社会的业务规则往往是“如果年龄 $<25$ 且 负债率 $>70\%$，则高危”，这种边界在几何上是生硬的直角折线，平滑多项式或高斯核要拟合出一个直角阶梯需要极复杂的参数凑合。
3. 非单调与高阶特征交互：某个特征的值只在特定区间有效，且依赖另一个特征的开关状态。

正是在这样的背景下，统计学与人工智能共同孕育出了另一条截然不同的演化支线——基于递归空间切分的决策树（Decision Trees）与集成学习（Ensemble Learning）。

图：特征空间切分范式对比——左图全局平滑模型（LR / SVM）用斜线或平滑超曲面贯穿全局特征空间；右图 CART 决策树通过平行于坐标轴的正交刀片（$x_1=s_1,x_2=s_2$）递归将空间切分为互不重叠的超矩形盒子 $R_1\sim R_4$，天然契合异构表格数据的“IF-THEN”阶梯规则

1.1 什么是“异构表格数据（Tabular Data）”？—— 与同构感知数据的四大本质分野

在现代机器学习落地实践中，绝大多数人接触到的第一个震撼性事实往往是：在计算机视觉（CV）与自然语言处理（NLP）领域所向披靡的深度神经网络，在真实的业务表格数据上，面对以 GBDT、XGBoost、CatBoost 为代表的集成决策树，竟然屡屡败下阵来！

为什么同样在计算机内存中存储为二维浮点矩阵 $\mathbf{X}\in {\mathbb{R}}^{n\times d}$，手写数字的像素矩阵与银行风控宽表的表现会产生如此鸿沟？本质原因在于：两者所处的数据流形与统计几何存在着不可调和的底层分野。

• 同构感知数据（Homogeneous Perceptual Data，图像/音频/文本）：所有网格单元（如像素点、音频采样点）具备完全同构的物理量纲（0~255 的光强或时域振幅）。孤立看第 137 号像素点的数值没有任何现实语义，只有通过局部相邻卷积、多层拓扑级联或全局自注意力机制组合，才能逐步涌现出“边缘、纹理、物体部件”等高级抽象表征。
• 异构表格数据（Heterogeneous Tabular Data，金融风控/电商推荐/临床医疗）：每一列均代表具体明确的业务实体属性，不同特征列之间的数据类型、统计分布和物理含义极端异构。

Grinsztajn, Oyallon & Varoquaux 在 NeurIPS 2022 的经典基准论文 “Why do tree-based models still outperform deep learning on tabular data?” 中，系统性归纳了表格数据阻击深度学习、成就树模型王座的四大结构特征：

1. 列语义独立与高度异构性（Heterogeneous Feature Types & Distributions）： 表格中各列的边际分布截然不同：年收入常呈极端右偏的长尾帕累托分布，年龄呈截断正态分布，学历属于有序类别（Ordinal），职业属于无序枚举（Nominal），而系统故障次数则是大量取值为 0 的极稀疏计数（Sparse Count）。更致命的是，工业宽表充斥着由于业务流程缺陷导致的系统性缺失值（NaN）。神经网络对分布长尾、离散高基数与缺失值极度敏感（权重梯度容易剧烈震荡），而决策树基于分位数独立排序切分，天然对单调量纲变换、离散类别及缺失值完全免疫。
2. 列置换不变性（Permutation Invariance）： 在图像中任意打乱像素排列，会彻底破坏局域纹理与几何拓扑；但在表格中，将第 1 列“年龄”与第 50 列“芝麻信用分”对调位置，数据的联合分布与底层业务逻辑纹丝不动。这意味着图像模型赖以生存的空间归纳偏置（如卷积的局域平移不变性）在表格上完全归零。多层感知机（MLP）为了学习无拓扑特征之间的复杂依赖，必须在密集的全连接权重矩阵中耗费海量参数去盲目拟合无序排列组合，极易陷入过拟合泥潭。
3. 不连续的轴平行阶梯边界（Non-smooth Axis-Aligned Boundaries）与谱偏置（Spectral Bias）： 现实中的信贷风控规则、电商满减策略或临床诊疗指南，本质上是大量人工硬编码的离散分支逻辑（例如：“若年龄 $<22$ 岁且收入 $<3000$ 元，则拒贷”）。这类规则在几何空间中呈现为生硬的轴平行直角阶梯超矩形。深度神经网络由平滑可微的激活函数复合而成，受制于深度学习著名的谱偏置（Spectral Bias / 频率原则）——神经网络在梯度下降中具有天然优先学习平滑低频全局函数的归纳偏置，若要拟合一个垂直跃迁的直角跳变阶梯，必须叠加上百个高频傅里叶分量，导致参数冗余且边缘剧烈振荡（吉布斯现象）；相反，决策树的“正交坐标刀片”机制在几何上生来就是为了拼接阶梯超矩形而存在的。
4. 高比例无关噪声特征与内置特征筛选（Sparsity of Informative Features）： 工业级宽表往往包含数百乃至数千列衍生特征，但对于特定预测目标（如“次日是否复购”），真正具备显著预测能力的往往仅有 10~20 个关键特征，其余绝大多数维度为无信息纯噪声列。神经网络反向传播时，误差梯度会无差别地流经所有权重，导致噪声维度持续向隐藏层注入随机扰动；而决策树在每次节点分裂时均在候选维度中贪心搜寻最大不纯度增益，无关噪声特征由于增益极低天然被算法无视，使树模型具备强悍的自适应特征选择能力。

1.2 决策树的几何本质：正交超矩形切分与局部常数近似

抛开树状流程图的表象，从泛函逼近的几何视角来看，一棵拥有 $M$ 个叶节点的决策树（以工业界最通用的二叉树 CART, Classification and Regression Tree 为例），只在做两件事：

1. 空间正交切分：每次挑选一个特征维度 $j$ 和一个切分阈值 $s$，用超平面 $x^{(j)}=s$ 将当前区域一分为二（左半区 $x^{(j)}\le s$，右半区 $x^{(j)}>s$）。经过递归切分，整个特征空间被互不重叠地划分为 $M$ 个轴平行超矩形盒子（Regions） $R_1,R_2,\dots ,R_M$。
2. 盒内常数预测：在每一个小盒子 $R_m$ 内部，模型不再画任何斜线，而是直接用该盒子内训练样本的统计汇总量（回归问题取均值 $c_m$，分类问题取多数类或类别经验概率）作为统一的常数输出： $f(x)={\sum }_{m=1}^M{c}_m\mathbb{I}(x\in R_m)$ 其中 $\mathbb{I}(\cdot )$ 是指示函数（落在盒子 $R_m$ 内为 $1$，否则为 $0$）。

认知顿悟（为什么树模型天然对特征单调变换免疫？）： 因为决策树的每一刀只关心样本在单个特征上的相对大小排序（Order）！无论你把“收入”特征乘以 $10000$、加上常数，还是取严格单调递增的 $\ln (\text{收入})$，样本在该特征上的先后顺序纹丝不动，切分点 $s$ 只是做了一一对应的坐标换算，切出来的样本子集完全一模一样！这就是为什么在树模型面前，你几乎不需要做特征归一化（Standardization）。

---

2. 单棵决策树的生长与代价：如何选出“最纯”的一刀？

要在成百上千个特征和无数个候选切分阈值 $s$ 中选出“最好的一刀”，我们需要一把数学尺子来衡量：切完之后，左右两个子区域是不是比原来更“纯”（同类样本更集中）了？

2.1 分类树的纯度标尺：信息熵 vs 基尼不纯度

假设当前节点包含 $K$ 个类别的样本，第 $k$ 类样本所占的比例（经验概率）为 $p_k\in [0,1]$，且 ${\sum }_{k=1}^K{p}_k=1$。衡量该节点混乱程度（Impurity，不纯度）有两大经典指标：

1. 香农信息熵（Information Entropy，ID3 / C4.5 采用）： $H(p)=-{\sum }_{k=1}^K{p}_k\ln p_k(\text{或以 }2\text{ 为底})$

   • 物理直觉：编码该节点内样本真实类别所需的平均信息量。当全部属于同一类（如 $p_1=1$）时，毫无悬念，$H=0$（最纯）；当各类别均匀混杂（$p_k=1/K$）时，不确定性最大，$H$ 达到峰值。（关于“为什么信息量必然采取对数函数 $-\ln p$”的香农公理与柯西函数方程推导、二分提问深度物理意义及信息熵极值性质，详见 附录 A）

2. 基尼不纯度（Gini Impurity，CART 树采用）： $\text{Gini}(p)={\sum }_{k=1}^K{p}_k(1-p_k)=1-{\sum }_{k=1}^K{p}_k^2$

   • 物理直觉（盲盒错配概率）：从当前节点的样本池中有放回地随机摸出两个样本，这两个样本属于不同类别的概率！显然，盒子越纯，摸出异类的概率 $\text{Gini}(p)$ 越趋近于 $0$。

深度追问：为什么现代工业界（CART / Scikit-learn）默认偏爱 Gini 而不是信息熵？ 观察信息熵公式中的 $-\ln p_k$：在 $p_k=1$ 附近对 $\ln p_k$ 做一阶泰勒展开，有： $\ln p_k\approx p_k-1⟹-\ln p_k\approx 1-p_k$ 把这个一阶近似直接代入信息熵公式： $H(p)={\sum }_{k=1}^K{p}_k(-\ln p_k)\approx {\sum }_{k=1}^K{p}_k(1-p_k)=\text{Gini}(\mathbf{p})$ 真相大白：基尼不纯度在数学上恰恰就是香农信息熵在 $p=1$ 处的一阶泰勒展开近似！ 两者的函数曲线形态几乎完全贴合（严格误差分析见 附录 A），但基尼指数只需要做简单的加减法和平方乘法，彻底省去了信息熵中极其消耗 CPU 周期的对数运算 $\ln p_k$！

图：左图为二分类下信息熵（缩放后）、基尼不纯度与分类误差率随正类比例 $p$ 的变化曲线，可见基尼指数与信息熵高度重合且均为严格凹函数（开口向下，处处提供非零分裂驱动力）；右图为 CART 决策树通过轴平行超平面递归切分生成的阶梯状分类边界

2.2 回归树的分裂准则与单棵深树的宿命：高方差陷阱

当目标变量 $y\in \mathbb{R}$ 是连续数值（回归问题）时，“纯度”就变成了盒内样本值的集中程度——即均方误差（MSE / 方差）。在切分特征 $j$ 和切分点 $s$ 时，CART 回归树求解如下贪心最小化问题： ${\min }_{j,s}\left[{\min }_{c_1}{\sum }_{x_i\in R_1(j,s)}(y_i-c_1{)}^2+{\min }_{c_2}{\sum }_{x_i\in R_2(j,s)}(y_i-c_2{)}^2\right]$ 由微积分极值性质（详见 附录 A），内层平方和极小化的最优常数预测值正是盒内样本均值 ${\hat{c}}_m=\text{ave}(y_i\mid x_i\in R_m)$。

然而，单棵决策树有着一个与生俱来的致命弱点——极高的方差（High Variance / 不稳定性）：

• 如果你不限制树的深度，决策树会一直贪心地切下去，直到每个叶节点盒子里只剩 $1$ 个样本，训练误差轻松降为 $0$，把训练集的噪声刻画成一个个针尖般的孤立小盒子（严重过拟合）；
• 更要命的是层级级联放大效应：由于决策树是自顶向下贪心生长的，只要训练集中有几个样本发生轻微抖动，导致根节点（第 1 刀）选了另一个特征或阈值，那么整棵树下半截的所有分支结构就会发生雪崩式的重构！
• 统计学家 Leo Breiman 等人曾尝试用代价复杂度剪枝（Cost-Complexity Pruning） $R_{\alpha }(T)=R(T)+\alpha |T|$ 来控制树的大小，但人们很快发现：单棵树始终困在“剪浅了表达能力太差（高偏差），留深了迎风就倒（高方差）”的死胡同里。

为了打破单棵树的宿命，20 世纪 90 年代至 21 世纪初，机器学习界开启了波澜壮阔的“三个臭皮匠顶个诸葛亮”——集成学习（Ensemble Learning）时代。而根据对付的是“方差”还是“偏差”，集成学习分化出了性格迥异的两大绝世流派：

1. Bagging 与随机森林（Random Forest）：用一群“完全长开的深树”并联投票，专治高方差；
2. Boosting（AdaBoost / GBDT / XGBoost）：用一群“克制短小的浅树”串联接力，专治高偏差。

图：集成学习两大范式的拓扑结构与统计学靶心对比——左图 Bagging / 随机森林通过自助采样与特征抽样并联训练多棵深树（低偏差、高方差），经多数投票或平均将发散的弹着点收拢至靶心（降低方差）；右图 Boosting / GBDT 通过串联浅层树桩（高偏差、低方差），令后一棵树专门拟合前一轮的残差 $r_t=y-F_t$，逐步修正系统性偏移逼近靶心（降低偏差）

---

3. 集成第一流派：Bagging 与随机森林 —— 向“高方差”宣战

3.1 统计学的降方差铁律与 Bootstrap 自助采样

在基础数理统计中，有一个人尽皆知的降方差魔法： 设 $Z_1,Z_2,\dots ,Z_B$ 是 $B$ 个相互独立且方差均为 ${\sigma }^2$ 的随机变量，那么它们的算术平均值 $\bar{Z}=\frac{1}{B}{\sum }_{b=1}^B{Z}_b$ 的期望不变，而方差会直接除以 $B$： $\text{Var}(\bar{Z})=\frac{1}{B^2}{\sum }_{b=1}^B\text{Var}(Z_b)=\frac{{\sigma }^2}{B}$

把这一铁律迁移到决策树上：既然单棵深树“偏差很低（表达力极强）、唯独方差极大（容易抖动）”，如果我们能从总体分布中独立抽取 $B$ 个互不相同的训练集，分别训练 $B$ 棵不剪枝的深树 ${\hat{f}}_1(x),\dots ,{\hat{f}}_B(x)$，再把它们的预测求平均： ${\hat{f}}_{\text{avg}}(x)=\frac{1}{B}{\sum }_{b=1}^B{\hat{f}}_b(x)$ 岂不是既保留了深树的低偏差，又把方差压到了原来的 $\frac{1}{B}$？！

理想很丰满，现实却卡在第一步：在真实任务中，我们手里只有唯一的一份包含 $n$ 个样本的训练集 $D$，去哪变出 $B$ 份独立的训练集？ 1996 年，Leo Breiman 引入了统计学家 Bradley Efron 发明的自助采样法（Bootstrap Sampling），提出了 Bagging（Bootstrap AGGregatING）：

• 每次从原始的 $n$ 个样本中有放回地随机抽取 $n$ 次，凑够一个同样大小为 $n$ 的自助训练集 $D_b$（里面有些样本被抽中了多次，有些样本一次都没被抽中）；
• 重复 $B$ 轮得到 $D_1,\dots ,D_B$，各自独立训练一棵深树，最后对 $B$ 棵树做回归平均或分类多数投票。

顺手白嫖的统计礼物：36.8% 的包外估计（Out-of-Bag, OOB Error） 在一次有放回的 $n$ 次抽取中，某个特定样本 $x_i$ 在单次抽取中没被抽中的概率是 $1-\frac{1}{n}$，连续 $n$ 次都没被抽中的概率是： ${\lim }_{n\to \infty }{\left(1-\frac{1}{n}\right)}^n=\frac{1}{e}\approx 0.36788(36.8\%)$ 这意味着每棵树训练时，天然有约 $36.8\%$ 的原始样本完全没有参与这棵树的生长（称为该树的 Out-of-Bag 包外样本）！因此，我们根本不需要额外切分验证集或做耗时 $K$ 倍的交叉验证，只需对每个样本 $x_i$，拿那些“没见过它的树”（约 $B/e$ 棵）对它做预测汇总，就能零成本算出无偏的泛化误差估计——这就是著名的 OOB 误差（严格证明见 附录 B）。

3.2 为什么光靠 Bagging 还不够？—— 相关性地板 $\rho {\sigma }^2$ 与随机森林的灵魂一笔

然而，当人们把 Bagging 用在决策树上时，发现随着树的数量 $B$ 增加，方差下降了一小截后很快就卡死在了一条水平线上，远没有达到理论上的 $\frac{{\sigma }^2}{B}\to 0$。为什么？

因为前面的公式 $\frac{{\sigma }^2}{B}$ 有一个致命前提：$B$ 棵树必须相互独立（Uncorrelated）！ 但所有的自助样本集 $D_1,\dots ,D_B$ 都是从同一个母集 $D$ 里有放回抽出来的，彼此高度重叠。更糟糕的是，假如数据集中存在 1~2 个预测能力极强的“霸权特征”（例如信贷数据里的“历史违约次数”），那么无论你怎么对样本做 Bootstrap 抽样，每一棵树在根节点（第 1 刀）和前几层分裂时，都会不约而同地优先挑这个霸权特征下刀！ 结果就是：你以为你种了 100 棵树，其实它们的主干结构几乎是一个模子刻出来的克隆体！

假设这 $B$ 棵树各自的方差均为 ${\sigma }^2$，但任意两棵树预测值之间的皮尔逊相关系数为 $\rho >0$。我们来严格计算它们平均值 ${\hat{f}}_{\text{avg}}(x)=\frac{1}{B}{\sum }_{b=1}^B{\hat{f}}_b(x)$ 的真实方差（完整协方差展开见 附录 B）： $\text{Var}\left(\frac{1}{\mathbf{B}}{\sum }_{\mathbf{b}=1}^{\mathbf{B}}{\hat{\mathbf{f}}}_{\mathbf{b}}(\mathbf{x})\right)=\underset{\text{相关性地板（堆树消不掉！）}}{\underbrace{\rho {\sigma }^2}}+\underset{\text{随树数量 }\mathbf{B}\to \infty \text{ 归零}}{\underbrace{\frac{1-\rho }{\mathbf{B}}{\sigma }^2}}$

请死死盯住这个公式，它是理解整个 Bagging 与随机森林演进史的绝对核心方程：

• 当你不断增加树的数量 $B\to \infty$ 时，第二项 $\frac{1-\rho }{B}{\sigma }^2$ 确实会乖乖衰减为 $0$；
• 但是，第一项 $\rho {\sigma }^2$ 与树的数量 $B$ 完全无关！ 只要树与树之间长得很像（相关系数 $\rho$ 居高不下），哪怕你堆上十万棵树，集成模型的总方差也死死卡在 $\rho {\sigma }^2$ 下不去！

图：左图展示理论方差公式 $\text{Var}=\rho {\sigma }^2+\frac{1-\rho }{B}{\sigma }^2$ 中树间相关性 $\rho$ 所决定的“方差不可逾越地板”；右图展示随机森林通过限制每次分裂的候选特征数 $m\approx \sqrt{d}$ 打破强特征垄断，实现比普通 Bagging 更低的测试误差收敛水平

随机森林（Random Forest，Breiman 2001）的神来之笔——“自缚双手”的特征随机抽样： 怎么才能强行把树与树之间的相关系数 $\rho$ 压下去？ Breiman 提出了一个极其反直觉却无比高明的机制：在训练每一棵树的每一个节点准备分裂时，禁止模型查看全部 $d$ 个特征！而是先从 $d$ 个特征中随机抽取一个仅含 $m$ 个特征的小子集（通常取 $m\approx \sqrt{d}$ 或 $d/3$），强制该节点只能在这 $m$ 个候选特征里挑最优的一刀！

• 这样一来，在大多数节点分裂时，那个“霸权特征”大概率根本不在被抽中的 $m$ 个候选名单里！
• 于是，不同的树被迫在根节点和浅层启用各种次优特征、探索完全不同的特征组合路径。虽然这会让单棵树变蠢一点点（单树方差 ${\sigma }^2$ 或偏差略微上升），但它极其暴力地斩断了树与树之间的同质性，让相关系数 $\rho$ 断崖式暴跌，从而一举击穿了 $\rho {\sigma }^2$ 的方差地板！（关于“减小候选特征数 $m$ 虽略微抬高单树方差与偏差，为何仍能令总泛化误差显著下降并在 $m^{\ast }\approx \sqrt{d}$ 处取得极小值”的组合概率不对称性证明与 Breiman $\bar{\rho }/s^2$ 极值定理，详见 附录 B）

---

4. 集成第二流派：Boosting 与 GBDT —— 在“函数空间”做梯度下降

如果说随机森林是“找一群互不盲从的博士（深树），各看各的材料，最后民主投票消弭偏激（降方差）”；那么 Boosting（提升方法） 走的则是完完全全相反的另一条哲学路线：

“只用最简陋的弱学习器（比如深度仅为 1~4 的矮树桩，单棵树表达力极弱、高偏差但极低方差），让它们排成一列纵队串联接力——后面每一棵树都不再重新学全貌，而是专门盯着前面所有树合起来还搞不定的‘错题与残差’进行靶向修补，积小胜为大胜，把高偏差一步步逼向零！”

4.1 从 AdaBoost 的“错题加权”到 GBDT 的“残差接力”

Boosting 家族最早的成名作是 Freund 与 Schapire（1995）提出的 AdaBoost：每一轮把上一轮分错的样本权重调大、分对的样本权重调小，逼迫下一棵弱分类器重点攻坚“错题”。后来统计学家 Friedman 等人证明：AdaBoost 在数学上等价于以指数损失函数 $L(y,F)=e^{-yF(x)}$ 为目标，通过前向分步加法模型（Forward Stagewise Additive Modeling）一棵接一棵地叠加基学习器（推导见 附录 C）。

到了 2001 年，Jerome Friedman 提出了一个更具统治力的直观构想：在回归问题中，与其去折腾复杂的样本权重，不如直接做“残差接力”！ 假设我们要预测一套房子的价格 $y=100$ 万：

1. 第 1 棵矮树 $h_1(x)$：粗略看了一眼地段，预测 ${\hat{y}}^{(1)}=70$ 万。此时还差多少？残差（Residual） $r_1=y-{\hat{y}}^{(1)}=100-70=+30$ 万；
2. 第 2 棵矮树 $h_2(x)$：它的训练标签不再是原房价 $100$ 万，而是直接去拟合第一轮剩下的残差 $+30$ 万！假设它根据户型拟合出了 $h_2(x)=+22$ 万，叠加后总预测变为 ${\hat{y}}^{(2)}=70+22=92$ 万，剩余残差缩小为 $r_2=100-92=+8$ 万；
3. 第 3 棵矮树 $h_3(x)$：继续拟合剩余残差 $+8$ 万……如此串联叠加 $T$ 轮，最终预测就是所有树输出的总和：$F_T(x)={\sum }_{t=1}^T{h}_t(x)$！

4.2 认知核爆：为什么“拟合残差”本质上是在“函数空间做梯度下降”？

“每次拟合上一轮的残差 $y-F_{t-1}(x)$”听起来如此朴素直观，但一个致命问题随之而来：

• 如果我们的损失函数不是平方误差 $L(y,F)=\frac{1}{2}(y-F{)}^2$，而是对异常值鲁棒的绝对值损失 $|y-F|$、或者是分类问题的交叉熵损失 $\ln (1+e^{-yF})$，那“相减的残差 $y-F$”还成立吗？这时候下一棵树到底该去拟合什么？

Friedman 给出了一个石破天惊的数学统一——梯度提升（Gradient Boosting / GBDT）！ 请把我们在第一站学习的参数空间梯度下降，与现在的函数空间梯度下降放在一起做一次跨维度的镜像对比：

现在，让我们用这套“函数空间负梯度”公式，回去检验刚才的平方误差损失 $L(y_i,F(x_i))=\frac{1}{2}(y_i-F(x_i){)}^2$： 对当前预测值 $F(x_i)$ 求偏导并取负号： $r_{ti}=-\frac{\partial }{\partial F(x_i)}\left[\frac{1}{2}(y_i-F(x_i){)}^2\right]=-(F(x_i)-y_i)={\mathbf{y}}_{\mathbf{i}}-\mathbf{F}({\mathbf{x}}_{\mathbf{i}})$

全场起立！ 原来，我们刚才拍脑袋想出来的“用新树去拟合上一轮的残差 $y_i-F_{t-1}(x_i)$”，仅仅是函数空间负梯度 $-\frac{\partial L}{\partial F}$ 在平方误差损失下的一个特例！

• 一旦领悟了这一层，GBDT 瞬间拥有了挂载任意可微损失函数的超能力：
  • 若使用绝对值损失 $L=|y_i-F(x_i)|$，负梯度就是符号函数 $\text{sign}(y_i-F(x_i))\in \{+1,-1\}$，新树只需拟合残差的正负号，天生对极端离群噪点免疫！
  • 若使用二分类对数似然损失 $L=-y_{i}F(x_i)+\ln (1+e^{F(x_i)})$（其中 $y_i\in \{0,1\}$），负梯度恰好就是概率残差 $r_{ti}=y_i-\sigma (F_{t-1}(x_i))=y_i-p_{t-1}(x_i)$！

图：GBDT 前向分步加法模型仿真——上方展示随着浅层回归树不断串联叠加（$M=1\to 3\to 15\to 50$），原本粗糙的阶梯函数逐步逼近真实光滑非线性曲线（偏差持续降低）；下方展示对应轮次待拟合的负梯度残差 $r_{ti}=y_i-F_{t-1}(x_i)$ 幅度逐步衰减至白噪声水平

---

5. 现代工业界霸主：XGBoost —— 二阶泰勒展开与结构正则化

如果说 Friedman 的 GBDT 是利用一阶导数（梯度 $g_i$）在函数空间做梯度下降，那么 2014–2016 年由陈天奇提出的 XGBoost（eXtreme Gradient Boosting），则是把二阶导数（牛顿法海森曲率 $h_i$）与显式树结构正则化 $\Omega (f_t)$ 完美焊死在目标函数里，统治了此后十年的 Kaggle 竞赛与工业界表格数据建模。

5.1 第一重飞跃：把树的结构惩罚 $\Omega (f_t)$ 写进二阶泰勒目标函数

在第 $t$ 轮迭代时，前 $t-1$ 棵树预测值 ${\hat{y}}_i^{(t-1)}$ 已经固定，我们要寻找第 $t$ 棵树 $f_t(x)$，使得带正则项的总目标最小： ${\mathcal{L}}^{(t)}={\sum }_{i=1}^{n}l(y_i,{\hat{y}}_i^{(t-1)}+f_t(x_i))+\Omega (f_t)$ 其中，XGBoost 为单棵树 $f_t$ 精心设计了结构复杂度惩罚项： $\Omega (f_t)=\gamma T+\frac{1}{2}\lambda {\sum }_{j=1}^T{w}_j^2$

• $T$ 是这棵树切出来的叶节点总个数，$\gamma >0$ 是每多切出一个叶子必须缴纳的“开店门票费”（等效于在生长过程中内置了后剪枝！）；
• $w_j$ 是第 $j$ 个叶节点输出的常数预测值，$\frac{1}{2}\lambda \sum w_j^2$ 则是我们第二站无比熟悉的 $L_2$ 岭正则化（防止单个叶子输出极端的步长，压制过拟合方差）。

为了能在任意损失函数 $l(\cdot )$ 下直接算出最优的树结构和叶子权重 $w_j$，XGBoost 对损失函数在 ${\hat{y}}_i^{(t-1)}$ 处做了二阶泰勒展开： ${\mathcal{L}}^{(t)}\approx {\sum }_{i=1}^n\left[l(y_i,{\hat{y}}_i^{(t-1)})+g_i{f}_t(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i)\right]+\gamma T+\frac{1}{2}\lambda {\sum }_{j=1}^T{w}_j^2$ 其中：

• 一阶梯度：$g_i={\partial }_{{\hat{y}}^{(t-1)}}l(y_i,{\hat{y}}_i^{(t-1)})$（指向误差增大的方向）；
• 二阶导数（曲率）：$h_i={\partial }_{{\hat{y}}^{(t-1)}}^{2}l(y_i,{\hat{y}}_i^{(t-1)})$（衡量局部损失碗口的弯曲陡峭程度）。

5.2 第二重飞跃：按叶节点重组的二次函数与“牛顿步长 + 分裂增益”解析解

去掉与当前树 $f_t$ 无关的常数项 $l(y_i,{\hat{y}}_i^{(t-1)})$，并完成一次极其优雅的视角切换——不再按 $n$ 个样本求和，而是按 $T$ 个叶节点盒子归组求和（设落入第 $j$ 个叶节点的样本索引集合为 $I_j$，在这些样本上 $f_t(x_i)\equiv w_j$）： ${\tilde{\mathcal{L}}}^{(t)}={\sum }_{j=1}^T\left[\left({\sum }_{i\in I_j}{g}_i\right)w_j+\frac{1}{2}({\sum }_{i\in I_j}{h}_i+\lambda )w_j^2\right]+\gamma T$

记第 $j$ 个叶节点内所有样本的一阶梯度之和为 $G_j={\sum }_{i\in I_j}{g}_i$，二阶导数之和为 $H_j={\sum }_{i\in I_j}{h}_i$。看！括号里关于叶节点权重 $w_j$ 的表达式，竟然变成了一个初中生都会求极值的一元二次抛物线 $G_j{w}_j+\frac{1}{2}(H_j+\lambda )w_j^2$！ 直接对 $w_j$ 求导令其为 $0$（完整推导见 附录 C），立即解出两个震慑人心的核心公式：

1. 叶节点最优权重解析解（带阻尼的牛顿法步长）： ${\mathbf{w}}_{\mathbf{j}}^{\ast }=-\frac{{\mathbf{G}}_{\mathbf{j}}}{{\mathbf{H}}_{\mathbf{j}}+\lambda }$

   • 物理直觉：分子 $-G_j$ 是盒内所有样本负梯度的合力（想往哪走），分母 $H_j$ 是局部二阶曲率（如果此处损失函数曲率很大、形势凶险，就自动缩小步长 $-\frac{G_j}{H_j}$，这正是第一站讲过的牛顿法 $-H^{-1}g$！），再加上 $\lambda$ 作为防分母过小的 $L_2$ 阻尼器！

2. 将 $w_j^{\ast }$ 代回目标函数，得到树结构的目标值与精确分裂增益（Split Gain）： ${\tilde{\mathcal{L}}}_{\text{opt}}^{(t)}=-\frac{1}{2}{\sum }_{j=1}^T\frac{G_j^2}{H_j+\lambda }+\gamma T$ 由此，当我们考虑把一个父节点（梯度和 $G_L+G_R$，曲率和 $H_L+H_R$）一刀切分成左子节点（$G_L,H_L$）和右子节点（$G_R,H_R$）时，目标函数下降的净收益（分裂增益 Gain）为： $\text{Gain}=\frac{1}{2}\left[\underset{\text{左子树质量得分}}{\underbrace{\frac{{\mathbf{G}}_{\mathbf{L}}^2}{{\mathbf{H}}_{\mathbf{L}}+\lambda }}}+\underset{\text{右子树质量得分}}{\underbrace{\frac{{\mathbf{G}}_{\mathbf{R}}^2}{{\mathbf{H}}_{\mathbf{R}}+\lambda }}}-\underset{\text{不切分时的父节点得分}}{\underbrace{\frac{({\mathbf{G}}_{\mathbf{L}}+{\mathbf{G}}_{\mathbf{R}}{)}^2}{{\mathbf{H}}_{\mathbf{L}}+{\mathbf{H}}_{\mathbf{R}}+\lambda }}}\right]-\underset{\text{新增一叶的复杂度门槛}}{\underbrace{\gamma }}$

   • 算法决策极其纯粹：遍历所有特征与切分点，挑出 $\text{Gain}$ 最大的那一刀；如果连最大的分裂收益都抵不上新增叶子的门票费（即 $\frac{1}{2}\times$括号项 $<\gamma$，$\text{Gain}<0$），则直接停止分裂！信息增益、基尼系数、MSE、剪枝惩罚，在这里被统一成了一个放之四海而皆准的二阶泰勒打分公式！

---

6. 终极复盘：Bagging vs Boosting 与树模型的认知边界

6.1 两大集成流派全景对比矩阵

6.2 树模型的阿喀琉斯之踵：为什么树模型“永远无法外推（Extrapolate）”？

尽管随机森林与 XGBoost 在表格数据上近乎无敌，但你必须清醒地知道它的数学边界：

• 回忆第 1 节：任何决策树（以及千百棵树的加权和）在几何上都是分片常数阶梯函数（Piecewise Constant Function）。
• 在训练数据最大范围 $\max (x_{\text{train}})$ 之外的未知区域，无论测试样本 $x_{\text{test}}$ 往右走多远，它最终落入的永远是最右侧的同一个边界叶节点盒子，输出的预测值永远定死在训练集的最大边界均值上！
• 结论：面对具有明显时间增长趋势（如股票价格长期通胀、销售额逐年线性爬升）的序列任务，如果不先用差分或线性模型剥离趋势项（Detrending），纯粹的树模型（RF / GBDT / XGBoost）绝对无法预测出高于历史最高点哪怕一分钱的数值！

1. 数据趋势形态诊断与差分/变换选型指南

面对带有时间序列增长或宏观趋势的表格数据，树模型建模的根本前提是将非平稳序列变换为平稳序列（Stationary Sequence），彻底剥离宏观确定性趋势项（Detrending）。针对现实世界中不同数学形态的趋势，工业界采用如下标准化消除趋势变换阶梯：

2. 平稳性判定（ADF 单位根检验）与“过度差分”的方差膨胀惩罚

差分虽然能够消除趋势，但绝非“差分阶数越高越好”。工程上必须通过严格的统计检验把控差分停止时机，防范致命的“过度差分（Over-differencing）”陷阱。

(1) 差分停止准则：ADF 单位根检验

在时间序列建模中，必须通过增广迪基-富勒检验（Augmented Dickey-Fuller Test, ADF）量化判定平稳性：

• 检验原假设 $H_0$：序列存在单位根（非平稳过程）；备择假设 $H_1$：序列平稳。
• 最小充分差分准则：差分阶数应遵循“最小充分原则”——每做一阶差分后即执行 ADF 检验，一旦 $p\text{-value}<0.05$（在 95% 置信度下拒绝存在单位根的原假设），表明序列已达到弱平稳状态，必须立即停止差分！

(2) 过度差分（Over-differencing）的方差膨胀严格推导

若对已经平稳的序列机械地施加多余的高阶差分，会导致严峻的方差爆炸与虚假自相关污染： 设一阶差分后的序列已达到平稳白噪声状态： $\Delta y_t=b+e_t,e_t\sim \text{iid}(0,{\sigma }^2)$ 此时随机扰动项的真实方差为 $\mathrm{Var}(e_t)={\sigma }^2$。 若对该平稳序列强行再做一次二阶冗余差分： ${\Delta }^2{y}_t=\Delta y_t-\Delta y_{t-1}=(b+e_t)-(b+e_{t-1})=e_t-e_{t-1}$ 由于 $e_t$ 与 $e_{t-1}$ 独立，二阶差分序列的噪声方差变为： $\mathrm{Var}({\Delta }^2{y}_t)=\mathrm{Var}(e_t-e_{t-1})=\mathrm{Var}(e_t)+\mathrm{Var}(e_{t-1})={\sigma }^2+{\sigma }^2=2{\sigma }^2$ 噪声方差直接翻倍！ 并且在相邻两期之间人为制造出了高达 $\mathrm{Corr}({\Delta }^2{y}_t,{\Delta }^2{y}_{t-1})=\frac{-{\sigma }^2}{2{\sigma }^2}=-0.5$ 的虚假负自相关。 若进一步错误地施加三阶冗余差分： ${\Delta }^3{y}_t={\Delta }^2{y}_t-{\Delta }^2{y}_{t-1}=(e_t-e_{t-1})-(e_{t-1}-e_{t-2})=e_t-2e_{t-1}+e_{t-2}$ 此时的误差方差暴涨为： $\mathrm{Var}({\Delta }^3{y}_t)=(1^2+(-2{)}^2+1^2){\sigma }^2=(1+4+1){\sigma }^2=6{\sigma }^2$ 一般性结论（二项式系数平方和定理）： 根据差分算子展开，对方差为 ${\sigma }^2$ 的白噪声多做 $k$ 阶冗余差分，其误差项方差将膨胀至： $\mathrm{Var}({\Delta }^k{e}_t)={\sum }_{j=0}^k{\left(\genfrac{}{}{0ex}{}{k}{j}\right)}^2{\sigma }^2=\left(\genfrac{}{}{0ex}{}{2k}{k}\right){\sigma }^2$

• $k=1$ 阶冗余差分：方差放大 $\left(\genfrac{}{}{0ex}{}{2}{1}\right)=2$ 倍；
• $k=2$ 阶冗余差分：方差放大 $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ 倍；
• $k=3$ 阶冗余差分：方差放大 $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ 倍！ 过度差分不仅人为毁灭了数据的信噪比（SNR），还在时间序列中生硬注入了不可逆的移动平均单位根（MA Unit Root），严重误导后续树模型对有效微观规律的拟合。

3. 工业界“线性趋势外推 + 树模型残差精修”的混血范式（Hybrid Modeling）

既然纯树模型完全丧失外推能力，而全局平滑线性模型又无法应对高阶非线性交互与特征硬阈值，现代工业界（如能源电网负荷预测、电商大促 GMV 预估、量化多因子资产定价等）通用的破局方案是采用“两阶段混血架构建模（Hybrid Two-Stage Modeling）”：

$\hat{y}(x,t)=\underset{\text{阶段一：全局参数化趋势外推引擎}}{\underbrace{\hat{T}(t)}}+\underset{\text{阶段二：GBDT/XGBoost 局部非线性精修引擎}}{\underbrace{\hat{R}(x)}}$

图：破解树模型无法外推困境的“两阶段混血架构建模”——第一阶段由全局线性模型拟合时间趋势 $\hat{T}(t)=a+bt$ 负责未来区间外推；剥离趋势得到平稳零均值残差 $r_t=y_t-\hat{T}(t)$ 后，第二阶段由 GBDT / XGBoost 利用高维异构表格特征 $x$ 精修局部非线性残差 $\hat{R}(x)$，最终相加合成 $\hat{y}(x,t)=\hat{T}(t)+\hat{R}(x)$

1. 第一阶段：宏观趋势骨干外推（Global Extrapolation Engine） 以显式时间变量 $t$（或宏观经济基准指标）为自变量，使用具备天然外推特性的代数模型（如带弹性网正则化的线性回归、分段线性样条模型或 Prophet）拟合宏观确定性趋势： $\hat{T}(t)=\hat{a}+\hat{b}t$ 线性函数具有无限延伸的斜率，负责承担样本外未知时间跨度的无界外推任务。
2. 第二阶段：微观高维残差精修（Local Tabular Refining Engine） 计算训练集上剥离宏观趋势后的平稳微观残差（Detrended Residuals）： $r_i=y_i-\hat{T}(t_i)$ 由于 $r_i$ 已经消除了均值漂移和趋势异方差，序列转化为平稳数据。此时将全部包含复杂离散类别、长尾分布、交互统计量的高维异构特征 $x_i$ 灌入 GBDT / XGBoost / LightGBM 进行残差接力拟合： $\hat{R}(x)={\sum }_{m=1}^M\eta h_m(x)\approx r$ 树模型在平稳残差空间中全力施展其轴平行切分、缺失值容忍与高阶特征组合的绝技，将预测残差方差压缩至极小。
3. 推断时在线融合： 在对未来样本 $(x_{\text{test}},t_{\text{test}})$ 进行在线打分时，将外推趋势与树模型残差直接相加输出： ${\hat{y}}_{\text{test}}=\hat{T}(t_{\text{test}})+\hat{R}(x_{\text{test}})$

哲学闭环：该混血范式以极高的数学美感，实现了第一站（全局平滑线性模型的强外推力）与第四站（局部正交树模型的异构表格精修力）的世纪联姻，成为解决工业界时间序列与复杂表格复合任务的统治级标配。

从本章迈向下一站：从第一站到第四站，我们走过了传统机器学习的四大支柱——广义线性模型、MLE/MAP 正则化、SVM 核方法，以及统治异构表格数据的决策树与集成学习（RF / GBDT / XGBoost）。下一站我们将站在中场全局俯瞰塔上，用“经验风险 + 结构风险”的大一统方程将这四大门派彻底熔铸闭环，并剖析传统特征工程在图像、语音、自然语言等同构感知信号面前的结构性失效，推开端到端表征学习的大门。

---

📖 深度附录（数学与理论底座）

本附录提供正文主干所依赖的严密数学证明、泰勒近似误差界与目标函数消元推导，供需要严格求证的读者查阅。

附录 A：信息熵公理化推导、泰勒展开等价性及回归树方差分解严格推导

1. 为什么信息熵必然采取对数形式 $-\ln p$？—— 香农公理化推导与核心性质

(1) 香农自信息公理与加性柯西函数方程推导

直觉上，“信息量”应当量化一个事件发生时所带来的“意外程度”或“消除的不确定性大小”。设事件 $E$ 发生的概率为 $P(E)=p\in (0,1]$，用函数 $I(p)$ 表示该事件发生所带来的自信息量（Self-Information）。克劳德·香农（Claude Shannon, 1948）提出，任何符合物理与逻辑直觉的信息量度量 $I(p)$ 必须且只需满足以下三条公理：

1. 确定事件零信息公理：必然发生的事件不包含任何新信息，即 $I(1)=0$；
2. 单调递减公理：事件越罕见（概率 $p$ 越小），其一旦发生所提供的信息量越大；反之概率越高，信息量越小，即当 $p_1<p_2$ 时，$I(p_1)>I(p_2)$；
3. 独立事件信息可加性公理：若两个事件 $A$ 与 $B$ 统计独立（联合发生概率为 $P(A\cap B)=p_A\cdot p_B$），则获知两事件同时发生所获得的总信息量，应严格等于分别获知两事件发生的信息量之和： $I(p_A\cdot p_B)=I(p_A)+I(p_B)$

由上述三条公理，如何唯一确定函数 $I(p)$ 的解析形式？ 由于概率 $p\in (0,1]$，引入可逆变量代换：令 $p=e^{-u}$，其中 $u=-\ln p\in [0,+\infty )$。定义辅助函数： $g(u)\triangleq I(e^{-u}),u\ge 0$ 对于任意 $u,v\ge 0$，令 $p_A=e^{-u},p_B=e^{-v}$，则其联合概率为 $p_A\cdot p_B=e^{-(u+v)}$。根据独立事件可加性公理： $I\left(e^{-(u+v)}\right)=I(e^{-u})+I(e^{-v})⟹g(u+v)=g(u)+g(v)$ 这正是数学分析中经典的加性柯西函数方程（Cauchy's Additive Functional Equation）。在单调递减公理（等价于 $g(u)$ 单调递增）或连续性条件下，加性柯西函数方程在 $[0,+\infty )$ 上的解具有唯一性，必然为正比例线性函数： $g(u)=c\cdot u(c>0\text{ 为任意常数})$ 将 $u=-\ln p$ 还原，即可唯一确定自信息量函数的形式： $I(p)=-c\ln p$ 常数 $c$ 对应于度量信息量的单位基底选择：

• 若以 2 为底（$c=\frac{1}{\ln 2}$），$I(p)=-{\log }_{2}p$，单位为比特（bit / shannon）；
• 若以自然对数 $e$ 为底（$c=1$），$I(p)=-\ln p$，单位为奈特（nat）。

当离散随机变量有 $K$ 个可能类别状态（相应经验概率为 $p_1,\dots ,p_K$）时，整个概率系统的平均不确定性即为自信息量的数学期望，这便唯一导出了香农信息熵（Shannon Entropy）： $H(p)=\mathbb{E}[I(p)]={\sum }_{k=1}^K{p}_{k}I(p_k)=-{\sum }_{k=1}^K{p}_k\ln p_k$

(2) 物理与算法意义：二叉决策树的最优提问深度（编码长度下界）

在决策树模型中，信息熵并非凭空借用的抽象统计量，它在算法物理上具有极其清晰的具象对应：

• 根据信息论中的无失真信源编码定理（Shannon's Source Coding Theorem），以二进制编码离散随机变量时，识别第 $k$ 类样本所需的理论最小平均码长下界正是其自信息量 $-{\log }_2{p}_k$（由哈夫曼前缀编码 Huffman Coding 渐近逼近）。
• 映射到二叉决策树（CART）的提问机制：对样本进行一次“轴平行切分”本质上就是提出一个“是/否（Yes/No）”的二元问题。为了在当前节点中无歧义地定位出属于第 $k$ 类的样本，一个最优的二分检索策略所需提出的平均二元问题数（二叉树的期望分裂深度），恰恰等于 $-{\log }_2{p}_k$。
• 物理本质：节点信息熵 $H(p)={\sum }_{k=1}^K{p}_k(-{\log }_2{p}_k)$，在物理上精确对应于采用最优二分策略将该节点内的所有样本彻底区分开（纯化为单类别叶子）所需的最小期望分裂深度（平均决策代价）。节点信息熵越大，意味着后续需要建立更深的子树分支才能将样本纯化。

(3) 统计学视角的等价性：多项分布极大似然估计（MLE）

除了信息论公理，信息熵在统计参数估计中同样具有深刻的对偶性： 设有 $n$ 个独立同分布的样本，落在包含 $K$ 个类别的节点中。记属于第 $k$ 类的样本频数为 $n_k$（满足 ${\sum }_{k=1}^K{n}_k=n$），其经验样本频率为 $p_k=\frac{n_k}{n}$。 设样本类别标签服从参数为 $\theta =({\theta }_1,\dots ,{\theta }_K)$（满足 ${\sum }_{k=1}^K{\theta }_k=1$）的多项分布（Multinomial Distribution），其联合似然函数为： $L({\theta }_1,\dots ,{\theta }_K)=\frac{n!}{{\prod }_{k=1}^K{n}_k!}{\prod }_{k=1}^K{\theta }_k^{n_k}$ 利用拉格朗日乘子法求极大似然估计（MLE），易得最优参数解恰为样本经验频率 ${\hat{\theta }}_k^{\text{MLE}}=\frac{n_k}{n}=p_k$。将该极大似然解代回对数似然函数（忽略与参数无关的阶乘组合常数项），得到节点在最优拟合下的极值对数似然： $\ln L({\hat{\theta }}^{\text{MLE}})={\sum }_{k=1}^K{n}_k\ln p_k={\sum }_{k=1}^K(n{p}_k)\ln p_k=n{\sum }_{k=1}^K{p}_k\ln p_k$ 对上式两端除以样本总量 $n$ 并取相反数，即得单样本平均极值负对数似然（Profiled Negative Log-Likelihood, NLL）： $-\frac{1}{n}\ln L({\hat{\theta }}^{\text{MLE}})=-{\sum }_{k=1}^K{p}_k\ln p_k=H(p)$ 这表明：在决策树分裂过程中最小化子节点的信息熵，在频率派统计学上完全等价于最大化样本标签在多项分布假设下的极大似然估计（MLE）拟合优度！

(4) 信息熵的三大核心数学性质与证明

信息熵能够作为全局收敛的纯度度量，依赖于以下三条关键数学性质：

1. 非负性（Non-negativity）：$H(p)\ge 0$

   • 证明：对于任意 $p_k\in (0,1]$，自然对数恒有 $\ln p_k\le 0$，故 $-\ln p_k\ge 0$。由于各概率权重 $p_k\ge 0$，线性组合必有 $H(p)={\sum }_{k=1}^K{p}_k(-\ln p_k)\ge 0$。
   • 等号成立当且仅当存在某一类 $p_i=1$ 且其余 $p_k=0(k\ne i)$（约定 $0\ln 0={\lim }_{x\to 0^{+}}x\ln x=0$），即节点内样本 100% 属于同一种类别，系统处于完全确定（零不纯度）的理想纯净状态。

2. 最大熵极值性（Maximum Entropy at Uniform Distribution）：$H(p)\le \ln K$

   • 证明：考察函数 $f(t)=\ln t$。因为二阶导数 $f^{\prime \prime }(t)=-\frac{1}{t^2}<0$，对数函数在 $(0,+\infty )$ 上是严格凹函数。由琴生不等式（Jensen's Inequality），对于任意满足 ${\sum }_{k=1}^K{p}_k=1$ 的概率分布 $p_k>0$： $H(p)={\sum }_{k=1}^K{p}_k\ln \left(\frac{1}{p_k}\right)\le \ln \left({\sum }_{k=1}^K{p}_k\cdot \frac{1}{p_k}\right)=\ln \left({\sum }_{k=1}^{K}1\right)=\ln K$ 由于 $\ln t$ 严格凹，琴生不等式取等号的充要条件为所有自变量取值严格相等： $\frac{1}{p_1}=\frac{1}{p_2}=\cdots =\frac{1}{p_K}⟹p_1=p_2=\cdots =p_K=\frac{1}{K}$
   • 结论：当所有类别均匀混杂（$p_k=1/K$）时，系统处于最大无序状态，信息熵达到全局唯一最大值 $\ln K$（以 2 为底时为 ${\log }_{2}K$）。

3. 严格凹性（Strict Concavity）

   • 证明：直接求信息熵关于概率分量 $p_k$ 的一阶偏导数与二阶偏导数： $\frac{\partial H}{\partial p_k}=-\ln p_k-1,\frac{{\partial }^{2}H}{\partial p_k\partial p_j}=-\frac{1}{p_k}{\delta }_{kj}$ 其中 ${\delta }_{kj}$ 为克罗内克符号。信息熵的 Hessian 矩阵为对角矩阵 $\mathbf{H}=\mathrm{diag}\left(-\frac{1}{p_1},\dots ,-\frac{1}{p_K}\right)$。在开单纯形 $\{p\mid p_k>0\}$ 内，由于每个对角元 $-\frac{1}{p_k}<0$ 恒成立，该 Hessian 矩阵在切空间中是严格负定矩阵。
   • 严格凹性确保了当一个父节点按任意特征划分为左右两个子集（满足样本比例 ${\omega }_L+{\omega }_R=1$ 且子集分布不全同）时，信息增益严格为正： $\text{Gain}=H(p_{\text{parent}})-({\omega }_{L}H(p_L)+{\omega }_{R}H(p_R))>0$ 从几何上杜绝了局部极小停滞，驱动决策树分裂向纯度单调升高的方向收敛。

2. 信息熵的一阶与二阶泰勒展开 vs 基尼不纯度

设节点内 $K$ 个类别的概率分布为 $p=(p_1,\dots ,p_K)$，其中 $p_k\in (0,1]$ 且 ${\sum }_{k=1}^K{p}_k=1$。 对对数函数 $f(t)=-\ln t$ 在 $t=1$ 处进行带皮亚诺余项的泰勒展开： $-\ln p_k=(1-p_k)+\frac{1}{2}(1-p_k{)}^2+\mathcal{O}((1-p_k{)}^3)$ 将其代入香农信息熵 $H(p)={\sum }_{k=1}^K{p}_k(-\ln p_k)$： $H(p)=\underset{\text{一阶近似：恰为 }\text{Gini}(p)}{\underbrace{\sum _{k=1}^K{p}_k(1-p_k)}}+\frac{1}{2}{\sum }_{k=1}^K{p}_k(1-p_k{)}^2+\dots$ 特别地，在二分类（$K=2$，正类概率为 $p$，负类为 $1-p$）情形下：

• 基尼不纯度为二次抛物线：$\text{Gini}(p)=2p(1-p)$，在 $p=0.5$ 处取最大值 $0.5$，二阶导数恒为 ${\text{Gini}}^{\prime \prime }(p)=-4<0$；
• 以 $2$ 为底并乘以 $\frac{1}{2}$ 缩放对齐量纲后的半熵为 $\frac{1}{2}{H}_2(p)=-\frac{1}{2}(p{\log }_{2}p+(1-p){\log }_2(1-p))$，在 $p=0.5$ 处同样取最大值 $0.5$，二阶导数为 $-\frac{1}{2\ln 2\cdot p(1-p)}<0$；
• 分类错误率 $\text{Error}(p)=1-\max (p,1-p)$ 在 $p<0.5$ 和 $p>0.5$ 两侧是斜率恒定的折线，二阶导数为 $0$（非严格凹函数）。 为什么建树分裂时不能直接用“分类错误率”而必须用 Gini 或信息熵？ 因为凹函数满足琴生不等式（Jensen's Inequality）。当一个节点分裂为左右两个子节点（样本占比 ${\omega }_L+{\omega }_R=1$）时，只有严格凹函数（Gini 和熵的二阶导数严格小于 0）才能保证只要左右子节点的概率分布 $p_L\ne p_R$（纯度结构发生改善），分裂后的加权不纯度就必然严格下降： $I(p)-({\omega }_{L}I(p_L)+{\omega }_{R}I(p_R))>0$ 而线性的分类错误率在很多“虽然左右节点多数类没变、但其中一个子节点已经变成 100% 纯净”的关键有益分裂上，给出的增益居然是 $0$，导致树停止生长！

3. 回归树节点最优常数预测值与方差分解

对落入区域 $R_m$ 的 $N_m$ 个样本，求常数 $c_m$ 最小化残差平方和 $S(c_m)={\sum }_{x_i\in R_m}(y_i-c_m{)}^2$： $\frac{dS(c_m)}{d{c}_m}=-2{\sum }_{x_i\in R_m}(y_i-c_m)=0⟹c_m^{\ast }=\frac{1}{N_m}{\sum }_{x_i\in R_m}{y}_i={\bar{y}}_m$ 代入后，该节点的最小残差平方和即为样本方差乘以样本数：$S(c_m^{\ast })=N_m\cdot \text{Var}(y\mid x\in R_m)$。

↩ 返回正文：单棵决策树的生长与纯度标尺

---

附录 B：Bootstrap 包外样本比例 $e^{-1}$ 与随机森林方差公式完整证明

1. 包外样本（OOB）渐近比例证明

设有含 $n$ 个样本的数据集 $D$。Bootstrap 进行 $n$ 次独立有放回均匀抽样：

• 任意指定样本 $x_i$ 在单次抽样中被选中的概率为 $\frac{1}{n}$，未被选中的概率为 $1-\frac{1}{n}$；
• 由于 $n$ 次抽样相互独立，$x_i$ 在全部 $n$ 次抽样中从未被选中的概率为： $P(x_i\notin D_b)={\left(1-\frac{1}{n}\right)}^n$ 由高等数学重要极限（对数展开 $\ln {\left(1-\frac{1}{n}\right)}^n=n\left(-\frac{1}{n}-\frac{1}{2n^2}-\dots \right)\to -1$）： ${\lim }_{n\to \infty }{\left(1-\frac{1}{n}\right)}^n=e^{-1}\approx 0.367879$ 反之，每个自助样本集 $D_b$ 平均包含原始数据集中约 $1-e^{-1}\approx 63.2\%$ 的不同样本。

2. 同分布相关随机变量均值的方差公式推导

设 $Z_1,Z_2,\dots ,Z_B$ 为 $B$ 棵随机生成的树在测试点 $x$ 处的预测随机变量（随机性来自 Bootstrap 抽样与特征子集抽样）。因为每棵树的生成机制完全同分布（Identically Distributed），设：

• 每棵树的方差均为 $\text{Var}(Z_b)={\sigma }^2(\forall b=1,\dots ,B)$；
• 任意两棵不同树之间的皮尔逊相关系数均为 $\text{Corr}(Z_b,Z_{b^{\prime }})=\rho (\forall b\ne b^{\prime })$，故协方差为 $\text{Cov}(Z_b,Z_{b^{\prime }})=\rho {\sigma }^2$。

根据期望与方差的双线性性质，计算均值 $\bar{Z}=\frac{1}{B}{\sum }_{b=1}^B{Z}_b$ 的方差： $\begin{array}{rl}\text{Var}\left(\frac{1}{B}\sum _{b=1}^B{Z}_b\right)& =\frac{1}{B^2}\text{Cov}\left(\sum _{b=1}^B{Z}_b,\sum _{b^{\prime }=1}^B{Z}_{b^{\prime }}\right)\\ & =\frac{1}{B^2}\left[\underset{\text{对角线共 }B\text{ 项}}{\underbrace{\sum _{b=1}^B\text{Var}(Z_b)}}+\underset{\text{非对角线共 }B(B-1)\text{ 项}}{\underbrace{\sum _{b=1}^B\sum _{b^{\prime }\ne b}\text{Cov}(Z_b,Z_{b^{\prime }})}}\right]\\ & =\frac{1}{B^2}[B{\sigma }^2+B(B-1)\rho {\sigma }^2]\\ & =\frac{{\sigma }^2}{B}+\frac{B-1}{B}\rho {\sigma }^2\\ & =\rho {\sigma }^2+\frac{1-\rho }{B}{\sigma }^2\end{array}$ 证毕！该式严格表明：当 $B\to \infty$ 时，极限方差为 ${\lim }_{B\to \infty }\text{Var}(\bar{Z})=\rho {\sigma }^2$。

3. 候选特征数 $m$ 的博弈极值证明：组合概率不对称性与 Breiman $\bar{\rho }/s^2$ 上界定理

(1) 极限泛化误差关于候选特征数 $m$ 的三项分解

在随机森林中，减小节点候选特征数 $m$（例如从全量 $d$ 缩减为 $\sqrt{d}$）会同时对偏差、单树方差以及树间相关性施加相反方向的作用力。为了精确刻画这一权衡，考察包含不可约噪声的回归任务： $y=f(x)+\epsilon ,\mathbb{E}[\epsilon ]=0,\mathrm{Var}(\epsilon )={\sigma }_{\epsilon }^2$ 设第 $b$ 棵随机树在测试点 $x$ 处的输出为随机变量 $Z_b(x;m)$。由于每棵树的训练过程（Bootstrap 抽样与特征随机子空间选择）是独立同分布的，其单树期望预测值记为 $\mu (x;m)\triangleq \mathbb{E}[Z_b(x;m)]$。 根据期望的线性性质，对 $B$ 棵同分布树的预测均值 $\bar{Z}(x;m)=\frac{1}{B}{\sum }_{b=1}^B{Z}_b(x;m)$ 求数学期望： $\mathbb{E}[\bar{Z}(x;m)]=\frac{1}{B}{\sum }_{b=1}^B\mathbb{E}[Z_b(x;m)]=\mu (x;m)$ 结论：多树集成求平均无法改变模型的数学期望，因此随机森林的整体预测偏差恒等于单棵树的预测偏差： $\mathrm{Bias}(\bar{Z};m)=\mathbb{E}[\bar{Z}(x;m)]-f(x)=\mu (x;m)-f(x)\equiv \mathrm{Bias}(m)$ 根据均方误差的偏差-方差分解定理： $\mathrm{MSE}(B;m)=\mathbb{E}\left[\right(y-\bar{Z}(x;m){)}^2]={\sigma }_{\epsilon }^2+{\mathrm{Bias}}^2(m)+\mathrm{Var}(\bar{Z}(x;m))$ 代入前述附录 B.2 推导的同分布相关变量方差公式 $\mathrm{Var}(\bar{Z})=\rho (m){\sigma }^2(m)+\frac{1-\rho (m)}{B}{\sigma }^2(m)$，当树数量充分大（$B\to \infty$）时，随机森林的极限泛化均方误差为： ${\mathrm{MSE}}_{\infty }(m)={\sigma }_{\epsilon }^2+{\mathrm{Bias}}^2(m)+\rho (m){\sigma }^2(m)$ 由于不可约噪声 ${\sigma }_{\epsilon }^2$ 是数据固有属性，最优候选特征数 $m^{\ast }$ 的本质是求解如下三项博弈极小化： ${\min }_{m\in [1,d]}[{\mathrm{Bias}}^2(m)+\rho (m){\sigma }^2(m)]$

(2) 根节点撞衫率二次方暴跌 vs 深树路径指数补偿的不对称性

直觉上，限制每个节点可选的特征数 $m$ 会削弱每个分裂节点的表达能力，从而抬高单树偏差 ${\mathrm{Bias}}^2(m)$ 与单树方差 ${\sigma }^2(m)$。然而，统计学习理论与实验一致表明：将 $m$ 从 $d$ 缩减到 $\sqrt{d}$ 时，总泛化误差不仅没有上升，反而大幅下降。这一反直觉现象源于“根节点分裂相关性”与“深树路径特征捕获”在组合概率上的剧烈不对称性。

1. 根节点克隆概率的二次方暴跌

设在全部 $d$ 个特征中存在一个对目标变量起统治性解释力的主导特征 $X_{\text{top}}$（例如信贷风控中的征信黑名单）。 在单棵树的任意节点，从 $d$ 个特征中无放回随机抽取 $m$ 个候选特征，根据超几何分布，抽中集合包含 $X_{\text{top}}$ 的概率为： $p=\frac{\left(\genfrac{}{}{0ex}{}{d-1}{m-1}\right)}{\left(\genfrac{}{}{0ex}{}{d}{m}\right)}=\frac{\frac{(d-1)!}{(m-1)!(d-m)!}}{\frac{d!}{m!(d-m)!}}=\frac{m}{d}$ 由于各树在根节点独立抽取特征子空间，任意两棵不同的树在根节点（第 1 刀，决定整棵树全局拓扑骨干）同时命中并选用 $X_{\text{top}}$ 的联合概率为： $P(\text{根节点克隆})=p^2={\left(\frac{m}{d}\right)}^2$

• 当 $m=d$（普通 Bagging）时，$P(\text{根节点克隆})=1$（$100\%$ 撞衫），所有树在根节点全部沿 $X_{\text{top}}$ 切分，导致后续分支拓扑高度同质，树间相关系数 $\rho (d)$ 居高不下；
• 当引入随机特征子空间取 $m=\sqrt{d}$（例如 $d=100,m=10$）时： $P(\text{根节点克隆})={\left(\frac{10}{100}\right)}^2=\frac{1}{100}=1\%$
• 撞衫率由 $100\%$ 断崖式暴跌至 $1\%$！ 这意味着高达 $99\%$ 的树被迫在根节点探索不同的次级特征与正交切分超平面，直接将树间相关性 $\rho (m)$ 强行从极高水平打入谷底。

2. 深树判定路径的指数级冗余补偿

强特征在根节点被屏蔽是否会导致模型丧失核心辨识力、引发偏差剧增？ 答案是不会。因为随机森林采用完全生长、不剪枝的深树（Deep Trees）。设从根节点到某一叶节点的典型判定分支路径长度为 $L$（树深度，通常 $L\approx {\log }_{2}n$）： 在单条分支路径连续经历的 $L$ 次独立节点分裂中，该路径至少命中一次强特征 $X_{\text{top}}$ 的概率为： $P(\text{路径捕获 }{X}_{\text{top}})=1-{\left(1-\frac{m}{d}\right)}^L$ 同样以 $d=100,m=10$ 为例（单节点命中率 $\frac{m}{d}=0.1$）：

• 当树深度达到 $L=20$ 时： $P(\text{路径捕获 }{X}_{\text{top}})=1-(1-0.1{)}^{20}=1-(0.9{)}^{20}\approx 1-0.1216=87.84\%$
• 当树深度达到 $L=30$ 时，捕获概率高达 $1-(0.9{)}^{30}\approx 95.76\%$！

非对称性机制小结：深树由浅入深的纵向级联结构构成了一个天然的“指数级冗余重试池”。强特征虽然在顶层根节点被概率错开（压制 $\rho$），但在中深层几乎 $100\%$ 会被重新捕获并完成精细切分。因此，随着 $m$ 适度缩小，单树偏差 ${\mathrm{Bias}}^2(m)$ 与单树方差 ${\sigma }^2(m)$ 仅以极其平缓的线性斜率微弱上升，而树间相关性 $\rho (m)$ 却由于顶层解耦而发生平方级剧烈坍缩。两者的不对称博弈产生了极其丰厚的净降方差收益。

(3) 极端小 $m$ 的纯噪声陷阱与 Breiman $\bar{\rho }/s^2$ 极值定理

1. 极端小 $m$ 下的纯噪声陷阱

既然减小 $m$ 能降低相关性，是否能无限缩小至 $m=1$？ 设真实数据中仅包含 $K$ 个与目标相关的有效特征，其余 $d-K$ 个维度均为无信息的纯随机噪声。当节点随机抽取 $m$ 个候选特征时，抽中集合全部属于噪声特征的概率为： $P(\text{纯噪声分裂})=\frac{\left(\genfrac{}{}{0ex}{}{d-K}{m}\right)}{\left(\genfrac{}{}{0ex}{}{d}{m}\right)}={\prod }_{j=0}^{m-1}\frac{d-K-j}{d-j}\approx {\left(1-\frac{K}{d}\right)}^m$

• 当 $m\to 1$ 且有效特征稀疏（$K\ll d$）时，该概率逼近 $1$。每个节点几乎注定只能在纯噪声特征中抓阄切分，决策树彻底丧失对有效模式的辨别力，导致单树偏差 ${\mathrm{Bias}}^2(m)$ 呈指数级恶化爆炸。

2. 一阶极值驻点与 U 型泛化误差曲线

对极限泛化误差 ${\mathrm{MSE}}_{\infty }(m)$ 关于候选特征数 $m$ 求一阶连续导数并令其为 0： $\frac{d{\mathrm{MSE}}_{\infty }(m)}{dm}=\underset{<0\text{ (增大 }m\text{ 单树更强，偏差单调减小)}}{\underbrace{\frac{d{\mathrm{Bias}}^2(m)}{dm}}}+\underset{>0\text{ (增大 }m\text{ 树间同质化，集成方差单调上升)}}{\underbrace{{\rho }^{\prime }(m){\sigma }^2(m)+\rho (m)({\sigma }^2{)}^{\prime }(m)}}=0$ 两股力量在 $m\in [1,d]$ 区间内必然相交于唯一的极小值驻点，呈现出标准的 U 型泛化误差曲线。

3. Leo Breiman (2001) 分类泛化误差上界定理

Leo Breiman 在奠基论文 Random Forests (2001, Theorem 1.2) 中，通过大数定律与切比雪夫型不等式，从理论上推导出了随机森林在分类任务中的泛化误差（Generalization Error, $P{E}^{\ast }$）严格上界： $P{E}^{\ast }\le \frac{\bar{\rho }(m)(1-s(m{)}^2)}{s(m{)}^2}$ 其中：

• $s(m)\triangleq {\mathbb{E}}_{X,Y}[\mathrm{mr}(X,Y)]\in (0,1]$ 为单树边际强度（Margin Strength），衡量单棵分类树输出正确类别相比最大竞争错误类别的平均置信边际（$s(m)$ 随 $m$ 增大而单调上升）；
• $\bar{\rho }(m)$ 为不同树分类边际函数之间的平均皮尔逊相关系数（$\bar{\rho }(m)$ 随 $m$ 减小而单调下降）。

根据该上界定理，最小化泛化误差等价于寻找最优超参数 $m^{\ast }$，使树间相关性与单树强度平方之比达到全局极小： ${\min }_m\frac{\bar{\rho }(m)}{s(m{)}^2}$

• 分类问题推荐 $m^{\ast }=\lfloor \sqrt{d}\rfloor$：由于分类投票对单树强度阈值较为宽容（单树只需多数胜出即可），相关系数 $\bar{\rho }$ 的权重更大，因此较小的 $\lfloor \sqrt{d}\rfloor$ 正好落在 U 型谷底的最深处；
• 回归问题推荐 $m^{\ast }=\lfloor d/3\rfloor$：回归平均要求单树提供准确的数值拟合，单树强度 $s(m)$ 权重更高，因而最优折中点向右平移至约三分之一特征维度处。

↩ 返回正文：Bagging 与随机森林降方差机制

---

附录 C：AdaBoost 指数损失等价性与 XGBoost 二阶目标函数完整推导

1. 为什么 AdaBoost 等价于指数损失下的前向分步加法模型？

设前向分步加法模型为 $F_t(x)=F_{t-1}(x)+{\alpha }_t{h}_t(x)$，其中 $y\in \{-1,+1\}$，$h_t(x)\in \{-1,+1\}$。 若定义损失函数为指数损失（Exponential Loss） $L(y,F)=\exp (-yF(x))$，则在第 $t$ 步固定 $F_{t-1}$，需最小化： ${\min }_{{\alpha }_t,h_t}{\sum }_{i=1}^n\exp (-y_i(F_{t-1}(x_i)+{\alpha }_t{h}_t(x_i)\left)\right)={\sum }_{i=1}^n\underset{\text{定义为第 }t\text{ 轮样本权重 }{\bar{w}}_{ti}}{\underbrace{\exp (-y_i{F}_{t-1}(x_i))}}\exp (-y_i{\alpha }_t{h}_t(x_i))$ 注意：上一轮累积的指数损失 ${\bar{w}}_{ti}=e^{-y_i{F}_{t-1}(x_i)}$ 恰恰就是 AdaBoost 中的样本权重！如果上一轮分错了（$y_i{F}_{t-1}(x_i)<0$），指数权重 ${\bar{w}}_{ti}$ 就会自动呈指数级放大。 将样本分为被 $h_t$ 分对的集合（$y_i{h}_t(x_i)=+1$）和分错的集合（$y_i{h}_t(x_i)=-1$），记加权错误率为 $e_t=\frac{{\sum }_{y_i\ne h_t(x_i)}{\bar{w}}_{ti}}{{\sum }_{i=1}^n{\bar{w}}_{ti}}$，对 ${\alpha }_t$ 求导令其为 $0$： $-e^{-{\alpha }_t}(1-e_t)+e^{{\alpha }_t}{e}_t=0⟹e^{2{\alpha }_t}=\frac{1-e_t}{e_t}⟹{\alpha }_t^{\ast }=\frac{1}{2}\ln \frac{1-e_t}{e_t}$ 这与 Freund & Schapire 从博弈论导出的 AdaBoost 话语权公式分毫不差！

2. XGBoost 二阶泰勒目标函数消元与最优叶权重推导

设第 $t$ 棵树 $f_t(x)$ 将空间划分为 $T$ 个互不相交的叶节点区域，样本集划分为 $I_1,\dots ,I_T$。 对于第 $j$ 个叶节点，其内部子目标函数为： ${\varphi }_j(w_j)=G_j{w}_j+\frac{1}{2}(H_j+\lambda )w_j^2,\text{其中 }{G}_j={\sum }_{i\in I_j}{g}_i,H_j={\sum }_{i\in I_j}{h}_i$ 对凸二次函数 ${\varphi }_j(w_j)$（在凸损失函数下 $h_i\ge 0$ 且 $\lambda >0$，故 $H_j+\lambda >0$）求一阶导数并令其为 $0$： $\frac{d{\varphi }_j(w_j)}{d{w}_j}=G_j+(H_j+\lambda )w_j=0⟹w_j^{\ast }=-\frac{G_j}{H_j+\lambda }$ 将最优权重 $w_j^{\ast }$ 代回 ${\varphi }_j(w_j)$： ${\varphi }_j(w_j^{\ast })=G_j\left(-\frac{G_j}{H_j+\lambda }\right)+\frac{1}{2}(H_j+\lambda ){\left(-\frac{G_j}{H_j+\lambda }\right)}^2=-\frac{G_j^2}{H_j+\lambda }+\frac{1}{2}\frac{G_j^2}{H_j+\lambda }=-\frac{1}{2}\frac{G_j^2}{H_j+\lambda }$ 对全部 $T$ 个叶节点求和并加上节点个数惩罚 $\gamma T$，即得该树结构下的最小结构损失（Structure Score）： ${\tilde{\mathcal{L}}}_{\text{opt}}^{(t)}=-\frac{1}{2}{\sum }_{j=1}^T\frac{G_j^2}{H_j+\lambda }+\gamma T$ 分裂前单节点的损失为 $-\frac{1}{2}\frac{(G_L+G_R{)}^2}{H_L+H_R+\lambda }+\gamma$，分裂后左右两子节点的损失之和为 $-\frac{1}{2}\left(\frac{G_L^2}{H_L+\lambda }+\frac{G_R^2}{H_R+\lambda }\right)+2\gamma$。用“分裂前损失 $-$ 分裂后损失”，即得正文中的分裂增益公式 $\text{Gain}$。

↩ 返回正文：XGBoost 二阶泰勒展开与结构正则化