09 · 第 9 讲：非参数模型——决策树与支持向量机

北京大学《机器学习概论》（2026 秋）的课程笔记。本篇依据第 9 讲《非参数模型》课件整理。

前面学的线性模型先规定函数大致长什么样，再从数据里估计少量参数。这一讲换一种思路：决策树不断切分输入空间；SVM 则让分类边界尽量远离训练样本。两者都不要求一开始写出完整的概率分布，却各自带着很强的结构假设。

第 1 章：什么叫“非参数”

参数模型并不等于“参数少”，而是模型复杂度在训练前就基本固定。例如 $d$ 维线性回归无论有多少样本，主要只需估计 $d+1$ 个系数。

决策树的叶子数会随数据与停止规则改变；核 SVM 的解也可能由越来越多训练样本共同表示。这里说它们“非参数”，强调的是有效复杂度可随数据增长，而不是说它们没有任何待学习的量。

这种灵活性带来一个共同问题：怎样避免模型把训练集里的偶然噪声也当成规律？决策树靠停止、剪枝和验证集；SVM 靠最大间隔、软间隔参数 $C$ 与核的选择。

第 2 章：决策树把空间切成一块一块

一棵树的内部节点提出一个问题，例如“湿度是否大于 75？”；沿不同答案走向不同子树；叶节点输出类别、类别分布或连续预测值。它本质上把特征空间分割成互不重叠的区域，并在每个区域内做一个很简单的预测。

树的优点是规则可读、能自然处理特征之间的条件关系。例如“先看天气，再看湿度”比一条统一的直线边界更容易表达某些规则。代价是轴对齐切分形成的边界往往呈阶梯状；若真实边界是斜线，可能要用很多次切分近似。

每次分裂都包含两件事：选哪个特征，以及在何处切。分类时希望切完后子节点更“纯”；回归时希望同一叶中的目标值更接近。

第 3 章：ID3 与信息增益

设节点中类别变量为 $Y$，其经验分布为 $p_k$，熵定义为

$$H(D)=-\sum_{k=1}^{K}p_k\log p_k.$$

若一个节点里全是同一类，熵为 0；类别越均匀，熵越大。对离散特征 $f$，按取值 $v$ 把数据分成子集 $D_{f=v}$ 后，条件熵是各子集熵的样本数加权平均：

$$H(D\mid f)=\sum_v\frac{|D_{f=v}|}{|D|}H(D_{f=v}).$$

信息增益就是切分前后不确定性的减少：

$$IG(D,f)=H(D)-H(D\mid f).$$

ID3 每一步选择信息增益最大的特征，然后在每个子节点递归重复。若节点样本已同类、没有剩余特征，或满足预设停止条件，就让它成为叶子；测试样本遇到训练中未出现的特征取值时，常见做法是输出当前节点的多数类或类别分布。

信息增益偏爱“取值很多”的特征。一个几乎唯一的编号可以把训练样本拆得很纯，却未必能泛化；C4.5 用信息增益率缓解这种偏好。课程里更重要的是看清：任何分裂准则都在比较“切完后的加权不纯度”，而不是神秘地挑一个最大数字。

第 4 章：CART：二叉树、基尼指数与回归树

CART（Classification and Regression Tree）统一用二叉切分。对分类节点，基尼指数写作

$$G(D)=1-\sum_{k=1}^{K}p_k^2.$$

它也在类别单一时为 0。若一次切分得到左右子集 $D_L,D_R$，应最小化

$$G_{\text{split}}=\frac{|D_L|}{|D|}G(D_L)+\frac{|D_R|}{|D|}G(D_R).$$

对连续特征，先把该列已观察到的数值排序，在相邻不同值的中点试候选阈值；例如 $x_j\le s$ 进入左子树，否则进入右子树。不能把每一个实数都当成一个离散分支，否则测试时几乎总会遇到没见过的取值。

回归树的叶子通常输出该叶训练标签的均值 $\bar y_R$。在区域 $R$ 内的平方误差为

$$\operatorname{SSE}(R)=\sum_{(x_i,y_i)\in R}(y_i-\bar y_R)^2.$$

因此，候选切分 $(j,s)$ 的目标是最小化左右两边的误差和：

$$\operatorname{SSE}(D_L)+\operatorname{SSE}(D_R).$$

这和线性回归的平方损失并不矛盾：线性回归用一条全局函数拟合；回归树在每个局部区域只预测一个常数。树足够深时能逼近复杂曲线，却也特别容易把噪声切成许多小块。

第 5 章：为什么必须剪枝

若不断分裂，训练误差通常只会下降，甚至可降到 0；但叶子里的样本越来越少，预测会变得不稳定。这就是树过拟合最典型的形态。

前剪枝是在建树过程中提前停下，例如限制最大深度、最小叶样本数、最小不纯度下降，或要求分裂后的验证集收益足够大。它计算便宜，但可能在某个节点过早停下，错过“先做一次看似没用的切分、再做一次有用切分”的组合。

后剪枝先长出一棵较大的树，再从叶子向上比较“保留子树”和“把整棵子树替换成一个叶子”的验证误差或带复杂度惩罚的目标。常用的代价复杂度形式为

$$\mathcal L_\alpha(T)=\sum_{m=1}^{|T|}\sum_{i\in R_m}(y_i-\hat y_{R_m})^2+\alpha|T|,$$

其中 $|T|$ 是叶子数。$\alpha$ 越大，模型越偏好更小的树。分类树也可把第一项换成不纯度或验证误差。超参数不能用测试集挑选：应在训练集内交叉验证，最后只用一次测试集报告泛化表现。

第 6 章：从一条可分直线到最大间隔

现在考虑二分类，标签 $y_i\in\{-1,+1\}$。线性分类器使用

$$f(x)=w^Tx+b,\qquad \hat y=\operatorname{sign}(f(x)).$$

只要 $y_i(w^Tx_i+b)>0$，样本就被正确分类；但许多超平面都可能把训练集分开。SVM 选择其中几何间隔最大的一个，因为边界离样本远一些时，小扰动不容易改变分类结果。

将参数缩放到最靠近边界的点满足 $y_i(w^Tx_i+b)=1$，两条间隔边界为 $w^Tx+b=\pm1$。它们的距离是 $2/\|w\|_2$，所以最大间隔等价于硬间隔 SVM 的原问题：

$$\begin{aligned} \min_{w,b}\quad&\frac12\|w\|_2^2\\ \text{s.t.}\quad& y_i(w^Tx_i+b)\ge1,\quad i=1,\ldots,N. \end{aligned}$$

这里的“1”只是尺度约定；若不固定尺度，$(w,b)$ 同时乘正数不会改变分类边界，所谓函数间隔就没有可比较的绝对大小。

第 7 章：对偶问题与支持向量

给每个约束配拉格朗日乘子 $\alpha_i\ge0$，可得到对偶问题

$$\begin{aligned} \max_{\alpha}\quad&\sum_i\alpha_i-\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_jx_i^Tx_j\\ \text{s.t.}\quad&\alpha_i\ge0,\qquad \sum_i\alpha_i y_i=0. \end{aligned}$$

驻点条件给出

$$w^*=\sum_i\alpha_i^*y_ix_i.$$

互补松弛条件是

$$\alpha_i^*\,[y_i(w^{*T}x_i+b^*)-1]=0.$$

所以远离间隔边界且分类正确的样本通常有 $\alpha_i=0$，不直接出现在最终分类函数里；真正决定边界的是 $\alpha_i>0$ 的支持向量。对任一满足 $0<\alpha_i$ 的硬间隔支持向量，可由 $y_i(w^Tx_i+b)=1$ 求 $b$，实践中常对多个可用支持向量取平均以减小数值误差。

对偶形式不只是换一种写法：它让训练与预测只依赖样本之间的内积 $x_i^Tx_j$，这正好引出核技巧。

第 8 章：噪声下的软间隔与 hinge loss

真实数据常常不可线性完全分开。软间隔引入松弛变量 $\xi_i\ge0$：

$$\begin{aligned} \min_{w,b,\xi}\quad&\frac12\|w\|_2^2+C\sum_i\xi_i\\ \text{s.t.}\quad&y_i(w^Tx_i+b)\ge1-\xi_i. \end{aligned}$$

$\xi_i=0$ 表示点在正确一侧且至少有单位间隔；$0<\xi_i\le1$ 表示虽然分对了但落进间隔带；$\xi_i>1$ 则已经错分。$C$ 控制“边界更平滑”和“更在意训练误差”之间的权衡：$C$ 太小可能欠拟合，太大则可能追着异常点跑。

把 $\xi_i$ 消去，可写成正则化的 hinge loss：

$$\min_{w,b}\ \frac12\|w\|_2^2+C\sum_i\max\bigl(0,1-y_i(w^Tx_i+b)\bigr).$$

不要把它和 Logistic 回归混为一谈。两者都能得到线性分类边界，也都可加 $L_2$ 正则；但 Logistic 损失平滑并对应概率模型，hinge loss 直接强调间隔，标准 SVM 的输出本身不是校准后的概率。

第 9 章：核技巧——在高维空间线性分割

若在特征映射 $\phi(x)$ 后线性可分，SVM 的对偶和预测中只需计算

$$K(x,z)=\phi(x)^T\phi(z).$$

这允许我们不显式构造可能非常高维的 $\phi(x)$。将对偶中的 $x_i^Tx_j$ 全部换成 $K(x_i,x_j)$，预测为

$$f(x)=\sum_i\alpha_i^*y_iK(x_i,x)+b^*.$$

常见核包括：线性核 $K(x,z)=x^Tz$；多项式核 $K(x,z)=(\gamma x^Tz+r)^d$；RBF 核 $K(x,z)=\exp(-\gamma\|x-z\|_2^2)$。核函数不能随便凭直觉拼凑；其核矩阵必须满足半正定等条件，才能对应某个合法的内积空间。

RBF 的 $\gamma$ 大时，每个样本的影响范围小，边界更曲折；$\gamma$ 小时影响范围更广，边界更平滑。它与 $C$ 都会影响复杂度，应一起通过交叉验证选择。高维核空间不自动保证泛化：核参数过激进、特征未标准化或训练集太小，都可能让模型记住样本而不是学习规律。

第 10 章：决策树和 SVM 怎么选

决策树适合规则本身有解释价值、特征中混有离散变量或非线性交互明显的场景；单棵树训练快、可解释，但对数据扰动敏感。后续的随机森林与梯度提升树正是通过集成缓解这种不稳定性。

SVM 对中等规模、高维稠密特征尤其常见，例如文本的词袋或向量表示；最大间隔思想清晰，但核 SVM 的训练和存储可能随样本数快速变重，参数也不像树那样直观。

把这一讲的两条主线放在一起看：树通过递归切分构造局部常数模型，需要剪枝控制复杂度；SVM 通过最大化间隔构造全局边界，需要正则化与核参数控制复杂度。模型选择仍回到第一讲的原则——用训练集拟合，用验证集做选择，用测试集做最后评估。