本讲目录

第 02 讲 · 感知机与支持向量机

诞生场景：1957 年，心理学家 Rosenblatt 造出感知机（Perceptron），号称能"学习识别"——《纽约时报》当年的报道说它将来能走路、说话、有意识。这是第一个真正意义上"从数据学出分类器"的算法。而 40 年后，SVM 用严格的数学回答了感知机悬而未决的问题："这么多条能分开数据的线，哪条最好？"——并顺手发明了核方法，成为 1995–2010 年间机器学习的绝对王者，把神经网络压制了整整十五年（第 04 讲讲这段恩怨）。

1. 线性分类器：最简单的假设空间

设定：二分类，\(x \in \mathbb{R}^d\)，\(y \in \{+1, -1\}\)。假设空间取线性函数：

\[ f(x) = \mathrm{sign}(w^\top x + b) \]

几何图像：\(w^\top x + b = 0\) 是一张超平面，\(w\) 是它的法向量，\(b\) 控制平移；超平面把空间切成两半，一半判正一半判负。找函数 = 找 \((w, b)\)。

2. 感知机：第一个学习算法

感知机的策略朴素到令人感动——犯错就修正：

初始化 \(w = 0,\ b = 0\)；
逐个看样本，若 \((x_i, y_i)\) 被分错（即 \(y_i(w^\top x_i + b) \leq 0\)），更新：

\[ w \leftarrow w + y_i x_i, \qquad b \leftarrow b + y_i \]

重复扫数据，直到没有错分点。

更新的几何直觉：分错说明 \(w\) 与"正确方向"夹角太大，往 \(y_i x_i\) 方向掰一把，掰完之后该点的函数值 \(y_i(w^\top x_i + b)\) 增加了 \(y_i^2(x_i^\top x_i + 1) = \|x_i\|^2 + 1 > 0\)，即朝正确方向前进了一步。

2.1 Novikoff 收敛定理（完整证明）

这个看似随意的算法有个漂亮的保证。

定理（Novikoff 1962）：设数据线性可分，即存在单位向量 \(w^*\)（\(\|w^*\| = 1\)）和间隔 \(\gamma > 0\) 使得所有样本满足 \(y_i (w^{*\top} x_i) \geq \gamma\)；又设 \(\|x_i\| \leq R\)。则感知机的总更新次数至多为

\[ k \leq \frac{R^2}{\gamma^2} \]

（为简洁把 \(b\) 吸收进 \(w\)：给每个 \(x\) 补一维常数 1，下同。）

证明：设第 \(k\) 次更新用了样本 \((x, y)\)，更新前的权重为 \(w_k\)，则 \(w_{k+1} = w_k + y x\)。我们从两个方向夹逼 \(\|w_{k+1}\|\)。

下界（每次更新都在正确方向上累积）：

\[ w_{k+1}^\top w^* = w_k^\top w^* + y\, x^\top w^* \geq w_k^\top w^* + \gamma \]

从 \(w_0 = 0\) 累加：\(w_{k+1}^\top w^* \geq (k+1)\gamma\)。由 Cauchy–Schwarz，\(\|w_{k+1}\| \geq w_{k+1}^\top w^* \geq (k+1)\gamma\)。

上界（每次更新长度增长有限）：

\[ \|w_{k+1}\|^2 = \|w_k\|^2 + 2y\, w_k^\top x + \|x\|^2 \leq \|w_k\|^2 + R^2 \]

其中中间项 \(2y\,w_k^\top x \leq 0\)，因为这个点当时被分错了。累加得 \(\|w_{k+1}\|^2 \leq (k+1)R^2\)。

两边夹：\((k+1)^2\gamma^2 \leq \|w_{k+1}\|^2 \leq (k+1)R^2\)，故 \(k + 1 \leq R^2/\gamma^2\)。\(\blacksquare\)

三点回味：

收敛次数与维数 \(d\) 无关，只依赖几何量 \(R/\gamma\)——"间隔"这个量首次登场，它将是 SVM 的灵魂；
数据不可分时，感知机永不停机、来回震荡——这是它的死穴之一；
可分时解有无穷多个，感知机停在哪条线取决于样本顺序，纯属偶然——这是死穴之二，也是 SVM 的出发点。

3. 支持向量机：哪条分界线最好？

SVM 最大间隔 — 图 2.1支持向量机：在能分开两类的直线里，选间隔最宽的那条——间隔越大泛化越稳，边界只由少数支持向量决定。

同样一份可分数据，能画无数条分界线：有的贴着正类样本，有的贴着负类。直觉上，离两边都尽量远的那条最稳妥——新样本有噪声扰动时，离边界远意味着不容易被扰过界。第 01 讲的泛化理论支持这个直觉：间隔越大的分类器，"有效复杂度"越低（间隔 \(\gamma\) 的线性分类器在半径 \(R\) 的球内 VC 维不超过 \(R^2/\gamma^2\) 量级，与维数无关）。

3.1 从几何间隔到原问题

点 \(x_i\) 到超平面 \(w^\top x + b = 0\) 的距离是 \(\dfrac{|w^\top x_i + b|}{\|w\|}\)。对正确分类的点，\(|w^\top x_i + b| = y_i(w^\top x_i + b)\)。定义整个数据集的几何间隔为最近点的距离：

\[ \gamma = \min_i \frac{y_i(w^\top x_i + b)}{\|w\|} \]

SVM 的目标：最大化 \(\gamma\)。注意 \((w, b)\) 同乘常数 \(c>0\) 不改变超平面也不改变 \(\gamma\)——存在一个冗余自由度。利用它做规范化：令最近点满足 \(y_i(w^\top x_i + b) = 1\)（即约束右端定标为 1），则 \(\gamma = 1/\|w\|\)，最大化间隔等价于：

\[ \min_{w, b} \; \frac{1}{2}\|w\|^2 \quad \text{s.t.} \quad y_i(w^\top x_i + b) \geq 1, \; i = 1, \dots, n \]

（取 \(\frac12\|w\|^2\) 而非 \(\|w\|\) 是为了求导好看。）这是一个凸二次规划：目标凸、约束线性——凸优化意味着局部最优即全局最优，没有神经网络那种"卡在坏解"的麻烦。这是 SVM 在 90 年代大受欢迎的原因之一：它是能被彻底理解的。

3.2 拉格朗日对偶（完整推导）

直接解原问题可以，但对偶形式会揭示两件深刻的事：解只依赖少数"支持向量"；以及数据只以内积形式出现——后者是核方法的入口。

引入乘子 \(\alpha_i \geq 0\)，拉格朗日函数：

\[ L(w, b, \alpha) = \frac{1}{2}\|w\|^2 - \sum_{i=1}^n \alpha_i \big[y_i(w^\top x_i + b) - 1\big] \]

原问题等价于 \(\min_{w,b} \max_{\alpha \geq 0} L\)（若某约束被违反，内层 max 可把 \(L\) 推到 \(+\infty\)，故外层 min 必须满足全部约束）。对偶问题是交换 min 与 max：\(\max_{\alpha \geq 0} \min_{w,b} L\)。由于原问题是凸且严格可行（Slater 条件），强对偶成立，两者最优值相等。

内层对 \(w, b\) 求最小：置偏导为零，

\[ \frac{\partial L}{\partial w} = w - \sum_i \alpha_i y_i x_i = 0 \;\Rightarrow\; w = \sum_i \alpha_i y_i x_i \]

\[ \frac{\partial L}{\partial b} = -\sum_i \alpha_i y_i = 0 \;\Rightarrow\; \sum_i \alpha_i y_i = 0 \]

第一式已经很有信息量：最优的 \(w\) 是样本的线性组合，系数是 \(\alpha_i y_i\)。把两式代回 \(L\)：

\[ \begin{aligned} L &= \frac{1}{2}\Big\|\sum_i \alpha_i y_i x_i\Big\|^2 - \sum_i \alpha_i y_i \Big(\sum_j \alpha_j y_j x_j\Big)^{\!\top} x_i - b\underbrace{\sum_i \alpha_i y_i}_{=0} + \sum_i \alpha_i \\ &= \frac{1}{2}\sum_{i,j} \alpha_i \alpha_j y_i y_j x_i^\top x_j - \sum_{i,j} \alpha_i \alpha_j y_i y_j x_i^\top x_j + \sum_i \alpha_i \\ &= \sum_i \alpha_i - \frac{1}{2}\sum_{i,j} \alpha_i \alpha_j y_i y_j \, x_i^\top x_j \end{aligned} \]

得到对偶问题：

\[ \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 \text{s.t.} \quad \alpha_i \geq 0, \;\; \sum_i \alpha_i y_i = 0 \]

盯住一个事实：数据 \(x\) 只以内积 \(\langle x_i, x_j \rangle\) 的形式出现。 先记下，第 4 节引爆它。

3.3 KKT 条件与支持向量

强对偶成立时，最优解满足 KKT 条件，其中互补松弛条件是：

\[ \alpha_i \big[y_i(w^\top x_i + b) - 1\big] = 0, \quad \forall i \]

即对每个样本，\(\alpha_i\) 和"约束的松弛量"至少有一个为零。分两类：

\(y_i(w^\top x_i + b) > 1\)（严格在间隔外侧的点）\(\Rightarrow \alpha_i = 0\)：对 \(w\) 毫无贡献；
\(\alpha_i > 0 \Rightarrow y_i(w^\top x_i + b) = 1\)：这个点恰好压在间隔边界上，称为支持向量（support vector）。

于是 \(w = \sum_{i \in SV} \alpha_i y_i x_i\)——整个模型只由贴着边界的少数样本决定，删掉其余样本解不变。这在几何上极其直观（决定马路宽度的只有路边的房子），在计算上意味着预测只需对支持向量求内积，在统计上呼应"解的稀疏性 = 低复杂度"。\(b\) 可由任意支持向量解出：\(b = y_k - w^\top x_k\)。

3.4 软间隔：现实数据不可分

真实数据有噪声、有离群点，硬性要求全部分对既不可能也不明智（一个标错的点就能毁掉整个间隔）。引入松弛变量 \(\xi_i \geq 0\) 允许违规，但违规要付钱：

\[ \min_{w, b, \xi} \; \frac{1}{2}\|w\|^2 + C\sum_{i=1}^n \xi_i \quad \text{s.t.} \quad y_i(w^\top x_i + b) \geq 1 - \xi_i, \;\; \xi_i \geq 0 \]

\(C > 0\) 是"违规罚款单价"：\(C \to \infty\) 退回硬间隔（零容忍，容易过拟合噪声）；\(C\) 小则宽容（间隔宽、偏差大、方差小）。这正是第 01 讲正则化滑块的 SVM 版本。 对偶推导流程完全一样（自己推一遍，好练习），结果只差一处：约束从 \(\alpha_i \geq 0\) 变成

\[ 0 \leq \alpha_i \leq C \]

另一个等价视角：消去 \(\xi_i\)（最优时 \(\xi_i = \max(0,\, 1 - y_i(w^\top x_i + b))\)），原问题变成无约束形式

\[ \min_{w,b} \; \frac{1}{n}\sum_i \underbrace{\max\big(0,\, 1 - y_i(w^\top x_i + b)\big)}_{\text{hinge 损失}} + \lambda \|w\|^2 \]

——SVM = hinge 损失 + L2 正则的 ERM，完美嵌回第 01 讲的"损失 + 正则"框架。hinge 损失是 0-1 损失的凸上界：0-1 损失没法优化（梯度处处为 0），hinge 是它"可优化的替身"。用凸的替代损失逼近 0-1 损失，这个思想同样支撑着逻辑回归（用交叉熵）和神经网络。

4. 核技巧：升维打击

4.1 动机：线性分不开怎么办

XOR 型数据（第 01 讲末尾的预告）：正类在 \((0,0), (1,1)\)，负类在 \((0,1), (1,0)\)——任何直线都无法分开。但做一个特征映射 \(\phi(x) = (x_1, x_2, x_1 x_2)\) 升到三维，超平面 \(x_1 x_2 = \text{常数}\) 类的分界就轻松解决。一般规律：低维线性不可分的数据，映到足够高维后往往线性可分（Cover 定理：\(N\) 个点在 \(d\) 维随机标注，\(d\) 越大线性可分概率越高）。

问题是代价。想在 \(\mathbb{R}^{100}\) 上用全部三阶多项式特征，\(\phi(x)\) 的维数是 \(\binom{103}{3} \approx 1.8 \times 10^5\)；阶数再高直接爆炸，更别说无穷维。

4.2 核技巧本体

回到 3.2 节记下的事实：对偶问题和预测函数里，数据只以内积形式出现：

\[ f(x) = \mathrm{sign}\Big(\sum_{i \in SV} \alpha_i y_i \langle \phi(x_i), \phi(x)\rangle + b\Big) \]

所以根本不需要算出 \(\phi(x)\) 本身，只需要能算映射后的内积：

\[ K(x, z) = \langle \phi(x), \phi(z) \rangle \]

如果有一个函数 \(K\) 能直接给出这个值，\(\phi\) 是几维、甚至是不是无穷维，都无所谓。例：取 \(K(x,z) = (x^\top z)^2\)，\(x, z \in \mathbb{R}^2\)，展开验证：

\[ (x^\top z)^2 = (x_1 z_1 + x_2 z_2)^2 = x_1^2 z_1^2 + 2 x_1 x_2 z_1 z_2 + x_2^2 z_2^2 = \langle \phi(x), \phi(z)\rangle \]

其中 \(\phi(x) = (x_1^2, \sqrt{2}\,x_1 x_2, x_2^2)\)。算 \(K\) 只要一次内积加一次平方（\(O(d)\)），算 \(\phi\) 再内积是 \(O(d^2)\)；多项式核 \(K(x,z) = (x^\top z + c)^p\) 对应的 \(\phi\) 有 \(\binom{d+p}{p}\) 维，而算 \(K\) 永远是 \(O(d)\)。用低维的计算量，买到高维的表达力——这就是核技巧（kernel trick）。

最著名的是高斯核（RBF 核）：

\[ K(x, z) = \exp\left(-\frac{\|x - z\|^2}{2\sigma^2}\right) \]

它对应的 \(\phi\) 是无穷维的（把指数泰勒展开，\(e^{x^\top z/\sigma^2} = \sum_{k=0}^\infty \frac{(x^\top z)^k}{\sigma^{2k} k!}\)，每一项是 \(k\) 阶多项式特征的内积，无穷级数拼出无穷维特征）。一台 90 年代的电脑，就这样在无穷维空间里训练线性分类器。

4.3 什么样的函数能当核？Mercer 定理

不是随便一个二元函数都是某个 \(\phi\) 的内积。Mercer 定理（有限点集版）：\(K\) 是合法核 \(\iff\) 对任意有限点集 \(\{x_1, \dots, x_n\}\)，Gram 矩阵 \(G_{ij} = K(x_i, x_j)\) 对称半正定。

必要性：若 \(K(x,z) = \langle\phi(x), \phi(z)\rangle\)，则对任意 \(c \in \mathbb{R}^n\)，

\[ c^\top G c = \sum_{i,j} c_i c_j \langle \phi(x_i), \phi(x_j)\rangle = \Big\|\sum_i c_i \phi(x_i)\Big\|^2 \geq 0. \]

充分性（有限维情形）：\(G\) 对称半正定则可谱分解 \(G = U \Lambda U^\top\)（\(\Lambda \geq 0\)），取 \(\phi(x_i) = \Lambda^{1/2} U^\top e_i\) 即得 \(\langle\phi(x_i), \phi(x_j)\rangle = G_{ij}\)。一般情形把求和换成积分算子的谱分解（Mercer 1909），构造出的特征空间称为再生核希尔伯特空间（RKHS）。\(\blacksquare\)

半正定性也保证了对偶问题仍是凸的（目标中的二次型 \(-\frac12 \alpha^\top (\text{diag}(y)\, G\, \text{diag}(y))\, \alpha\) 凹），凸性的免费午餐得以保留。

核方法的历史地位

1995 年软间隔 SVM（Cortes & Vapnik）+ 核技巧 + 严格的统计学习理论（VC 理论正是 Vapnik 的作品）三位一体，让 SVM 成为 1995–2010 年的主流方法：手写数字、文本分类、生物信息，处处是它。同一时期神经网络理论上说不清、调参靠玄学，在学术界几乎被扫进故纸堆——只有少数人还在坚持（第 04 讲）。而核方法的局限也埋在它的优雅里：核矩阵 \(n \times n\)，样本到百万级就存不下算不动；特征仍然是"人选核函数"而非"从数据学出来"。这两条短板，正是深度学习后来翻盘的地方。

5. 多分类怎么办

SVM 天生二分类。多分类的标准做法：一对其余（One-vs-Rest）训练 \(K\) 个二分类器取分数最高者，或一对一（One-vs-One）训练 \(\binom{K}{2}\) 个投票。（对比之下，第 03 讲的决策树和贝叶斯天生多分类，第 04 讲的神经网络用 softmax 天生多分类——这是 SVM 的一个小别扭。）

本讲小结

概念	一句话
感知机	犯错就修正；可分时 \(R^2/\gamma^2\) 步收敛（Novikoff）
最大间隔	在所有可分超平面里选离两类都最远的——泛化更稳
对偶	\(w = \sum \alpha_i y_i x_i\)；数据只以内积出现
支持向量	\(\alpha_i > 0\) 的边界点；模型只由它们决定
软间隔	hinge 损失 + L2 正则；\(C\) 是过拟合滑块
核技巧	只算 \(K(x,z)\) 不算 \(\phi\)；低维计算量买无穷维表达力
Mercer	合法核 \(\iff\) Gram 矩阵半正定

动手：跑 labs/lab02_perceptron_svm.py——从零实现感知机看它收敛，再用 sklearn 的 SVM 对比线性核与 RBF 核的决策边界，把支持向量圈出来，最后调 \(C\) 和 \(\sigma\) 观察过拟合。

延伸阅读：李航《统计学习方法》第 2、7 章（中文里最清楚的 SVM 推导）；Burges "A Tutorial on Support Vector Machines" (1998)。

下一讲换一条思路：不画分界线了。用"一连串 if-else 问题"分类（决策树），或者干脆直接对第 01 讲的贝叶斯最优分类器建模（朴素贝叶斯）。顺便回答一个深刻的小问题：为什么信息要用 \(-\sum p \log p\) 度量？