6. 经典机器学习与树模型: 决策树 / GBDT / XGBoost / SVM
TL;DR
深度学习之前的"机器学习主干"——决策树与集成模型（GBDT/XGBoost）——今天依然是表格数据（结构化特征）上的事实标准：Kaggle 表格赛题、信贷风控、广告 CTR、推荐排序的第一梯队几乎都是树模型而非神经网络。原因一句话：树模型对特征尺度不敏感、天然处理缺失值和类别特征、可解释、训练快。这一章把决策树（ID3/C4.5/CART）、集成（Bagging/RandomForest、Boosting/GBDT）、XGBoost 的目标函数推导、SVM 的对偶与核技巧讲透，并给出"表格数据优先树模型、图像/文本/序列优先深度模型"的工程判断。
读完应能：
- 手推 CART 回归树的分裂准则（MSE 下降）与分类树的基尼/熵分裂。
- 说清 Bagging 为什么能降方差、Boosting 为什么能降偏差，以及随机森林 vs GBDT 的分裂方式差异。
- 从"负梯度拟合"出发理解 GBDT，并看懂 XGBoost 目标函数的二阶泰勒展开与正则项。
- 写出 SVM 的原始问题、对偶形式、KKT 条件直觉，知道核技巧把特征映射藏在哪里。
- 给出表格数据的建模选型决策树：什么时候用 LR/树/XGBoost/深度模型，以及 GBDT 与深度模型的互补用法。
一、回顾: 有监督学习的形式
数据 $(x_i, y_i)$，模型 $f$，损失 $L$，经验风险最小化：
$$\hat{f} = \arg\min_f \frac{1}{N} \sum_{i=1}^{N} L(y_i, f(x_i)) + \lambda \cdot \Omega(f)$$
树模型和神经网络都在这同一个框架里，区别在函数空间 $f$ 的表示方式：
- 神经网络：$f$ 是参数化的可微复合函数（反向传播梯度下降）；
- 决策树：$f$ 是分段常数/分段线性函数（不可微，用贪心分裂代替梯度）；
- GBDT/XGBoost：在"树的加法集合"上做函数空间里的梯度下降。
二、决策树
2.1 分裂准则
树递归地把特征空间切成矩形区域，每个叶子给一个预测值。分裂时选"信息增益最大"的特征/阈值：
| 准则 | 公式 | 特点 |
|---|---|---|
| 信息增益（ID3） | $\text{Gain} = H(D) - \sum_v \frac{|D_v|}{|D|} H(D_v)$ | 偏向取值多的特征 |
| 增益率（C4.5） | $\frac{\text{Gain}}{\text{SplitInfo}}$ | 校正偏置 |
| 基尼指数（CART） | $\text{Gini} = 1 - \sum_k p_k^2$ | 分类默认；二分 |
| MSE 下降（CART 回归） | $\sum (y_i-\bar y)^2 - \sum_{v}(y_i^v-\bar y^v)^2$ | 回归树分裂 |
CART 每次只做二叉分裂，对连续特征枚举候选阈值 $O(n \log n)$（排序后取相邻中点），这也是"树对特征尺度不敏感"的原因——它只比大小，不做距离运算。
2.2 剪枝
完全长成的树过拟合。两类做法：
- 预剪枝：分裂前判断（叶子样本数阈值、增益阈值、深度限制）；
- 后剪枝（CCP，CART 用）：自底向上合并叶子，用损失 + 叶子数惩罚比较：
$$\text{Cost} = \sum_{leaf} \text{impurity} + \alpha \cdot #\text{leaves}$$
$\alpha$ 越大树越小——XGBoost 的正则项 $\gamma T$ 正是这个思想的在线版本。
note
单棵决策树方差大（训练集抖一点结构全变），所以工业上几乎不用单树，而是它的集成。
三、集成: Bagging 降方差, Boosting 降偏差
3.1 Bagging 与随机森林
对训练集有放回抽样（bootstrap）得到 M 份样本，分别训练 M 棵（深）树，预测取平均/投票：
$$\text{Var}(\text{average}) \approx \frac{\rho \sigma^2 + (1-\rho)\sigma^2/M}{M}$$
直觉：基模型方差 $\sigma^2$ 被平均掉 $M$ 倍，但模型间相关 $\rho$ 越高收益越低。随机森林在每次分裂随机选 $m$ 个特征（$m \ll d$），把 $\rho$ 压低——这是随机森林和 Bagging 的本质区别。
3.2 Boosting: AdaBoost → GBDT
Boosting 序列地训练弱模型，每轮给上一个模型分错的样本加权重。AdaBoost 用指数损失给出权重更新闭式解。GBDT 把思路推广：用损失函数在当前模型的负梯度当"伪残差"来拟合新树。
$$\tilde{y}i = -\left.\frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}\right|{f=f_{t-1}}$$
新树 $h_t$ 拟合伪残差，然后 $f_t = f_{t-1} + \eta h_t$（$\eta$ 学习率）。
这是"梯度下降在函数空间"的精确对应：参数空间里每步沿负梯度走，函数空间里每步用一棵树逼近负梯度。
3.3 XGBoost: 把 Boosting 写成可优化的目标
XGBoost 不做近似，直接最小化带正则的逐轮目标：
$$\mathcal{L}^{(t)} = \sum_{i=1}^{N} L(y_i, \hat y_i^{(t-1)} + f_t(x_i)) + \Omega(f_t), \quad \Omega(f) = \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T} w_j^2$$
对损失做二阶泰勒展开（$g_i$ 一阶导、$h_i$ 二阶导），忽略常数后每个叶子 $j$ 的最优权重和分裂增益有闭式解：
$$w_j^* = -\frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda}, \qquad \text{Gain} = \frac{1}{2}\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$$
其中 $G_j = \sum_{i\in I_j} g_i, H_j = \sum_{i\in I_j} h_i$。
由此推出 XGBoost 的工程优势：
- 二阶信息：比只看负梯度的一阶方法收敛更准；
- 预排序 + 分位点近似：对连续特征排序后做加权分位数，支持缺失值学习默认方向；
- 正则项 $\gamma,\lambda$：直接控制叶子数和权重幅度，天然防过拟合；
- 并行：分裂候选按特征并行、直方图化（LightGBM）进一步降内存。
warning
树模型的"并行"是特征/分裂枚举并行，不是样本并行训练多棵树（每棵树依赖上一棵）。想并行跑多棵树用随机森林，想省内存用 LightGBM 直方图 + GOSS，想省显存/大规模用 CatBoost 的对称树。三者是 GBDT 系的不同工程取舍，不是不同算法族。
四、SVM: 最大间隔 + 核技巧
线性 SVM 找最大间隔超平面：
$$\min_{w,b} \frac{1}{2}|w|^2 + C\sum_i \xi_i, \quad \text{s.t. } y_i(w^\top x_i + b) \ge 1 - \xi_i, \xi_i \ge 0$$
对偶形式（拉格朗日）后只依赖内积：
$$\max_\alpha \sum_i \alpha_i - \frac{1}{2}\sum_{i,j}\alpha_i\alpha_j y_i y_j \langle x_i, x_j \rangle, \quad 0 \le \alpha_i \le C$$
于是把内积换成核函数 $K(x_i,x_j) = \langle \phi(x_i), \phi(x_j) \rangle$ 就完成了非线性映射——核技巧的价值是：不需要显式算高维特征 $\phi(x)$，只要内积可算。常用核：RBF $K = e^{-\gamma|x_i-x_j|^2}$、多项式核、线性核。
关键直觉：
- 决策边界只由支持向量（$\alpha_i > 0$ 的点）决定——稀疏性；
- $C$ 控制软间隔惩罚（大 $C$ 严、过拟合风险高；小 $C$ 宽、欠拟合）；
- 核函数本身要满足 Mercer 条件（正半定），否则对偶不收敛；
- RBF 核的 $\gamma$ 大 → 边界崎岖 → 过拟合。
SVM 在表格小数据、低维强特征上依然能打，但工程上已被 GBDT 系取代为主要默认；它今天的主要舞台是核方法理论、Kernel 嵌入、以及少数"线性可分+解释边界"场景。
五、工程选型: 表格数据用什么
| 数据形态 | 默认选择 | 为什么 |
|---|---|---|
| 表格 / 结构化 / 稀疏特征 | XGBoost/LightGBM | 尺度不敏感、缺省值原生、快、可解释 |
| 超高维稀疏（CTR 类） | LR/FM + 深度（Wide&Deep） | 线性模型可在线训练、可解释权重 |
| 图像 / 音频 / 文本 | CNN / Transformer | 局部性与序列结构需要深度特征 |
| 小样本 + 强先验 | SVM / 简单 LR | 方差控制，防过拟合 |
| 混合（特征 + 行为序列） | 树模型提特征 → 深度模型 | 业界主流：GBDT 叶子作为深度模型特征 |
工程纪律：
- 先 baseline 再调参：逻辑回归/单棵 CART 是 0 号选手，GBDT 超参数（树数、深度、学习率、min_child_weight）用早停选；
- 类别特征：GBDT 原生支持/目标编码，别 one-hot 爆维度；
- 特征尺度：树模型不需要归一化；LR/SVM/深度模型需要；
- 解释性：SHAP 值 = 特征归因（树模型自带快路径）。
六、一页速查
决策树: 贪心分裂(CART=基尼/MSE) + 剪枝(CCP), 单树方差大
Bagging: bootstrap 抽样降方差; 随机森林再随机选特征降相关
Boosting: 每轮拟合伪残差(负梯度); XGBoost 二阶泰勒 + 正则闭式解
SVM: 最大间隔 + 对偶只留内积 + 核技巧(不需显式高维)
选型: 表格→GBDT系 / 超高维稀疏→LR/FM / 图像文本→深度
工程: 早停选树数 / SHAP 解释 / 树模型免归一化
下一篇: 8. 强化学习与 RLHF。