人工智能导论 · 第四章 · 课件 9

统计机器学习 · 支持向量机 全解

从「我完全没听过课」到「能看懂、能推导、能算对期末题」——一份逐步拆解的零基础学习指南。

SVM 间隔最大化 对偶 / KKT 核技巧 2021 真题逐步求解 +ID3 / 朴素贝叶斯附录
SECTION 00

这门课在学什么（先建立大局观）

在钻进公式之前，先用一句话把整章串起来：这一章只讲一件事——怎么造一个「分类器」，把两类点用一条线（面）分开，并且这条线要分得「最稳」。

课件 9 属于第四章「统计机器学习方法」。整章的主角是 支持向量机（SVM, Support Vector Machine）。它按难度分成三层，而这三层是层层递进的：

SVM 的三层结构（难度递增，但骨架完全相同）
层次数据长什么样新增的概念
线性可分 SVM两类点能被一条直线干净分开间隔最大化、对偶、KKT
线性 SVM（软间隔）大体能分，但有几个点「越界」松弛变量 $\xi$、惩罚参数 $C$
非线性 SVM怎么画直线都分不开（如同心圆）映射 $\phi$、核函数 $K$（核技巧）
期末考点定位 根据你给的 2021 真题和考试范式，本章必考的是 第 3 题：非线性 SVM 求解 + 分类一个新点。它考的就是「写出对偶问题 → 解出 $\alpha$ → 求 $b$ → 代入决策函数判正负」这条流水线。本指南第 4~7、9、11 节就是为打通这条流水线而写。决策树 ID3（第 5 题）也属第四章，放在附录 A。
SECTION 01

机器学习与统计学习三要素

这几页是「概念题」素材，理解即可，不用计算。

1.1 什么是机器学习

赫伯特·西蒙的定义：「如果一个系统能够通过执行某个过程改进它的性能，这就是学习。」 统计机器学习，就是计算机系统运用数据 + 统计方法来提高性能。

1.2 把「学习」形式化

课件用一套符号把学习写清楚，请记住这几个字母：

输入 x ∈ X
样本的特征（比如一封邮件的词频向量）。
输出 y ∈ Y
标签（比如「垃圾邮件 / 正常」）。
真实映射 f: X→Y
老天爷手里那个「正确答案函数」，我们看不到。
训练集 T
$T=\{(x_1,y_1),\dots,(x_n,y_n)\}$，由 $f$ 产生（可能带噪音）。
假设空间 H
我们允许的所有候选函数的集合 $H=\{h_k\}$。
学到的函数 g ∈ H
算法最终挑出的那个，希望 $g\approx f$。
学习算法 A
负责从 $H$ 里挑 $g$ 的程序。

一句话总览：学习算法 A 根据训练集 T，从假设空间 H 中挑一个最好的 $g\approx f$。

训练集 T {(x₁,y₁),…,(xₙ,yₙ)} 学习算法 A 从 H 中挑选 学到的函数 g ≈ f 假设空间 H
机器学习的基本框架：数据进，模型出。

1.3 PAC 学习（可能近似正确）—— 了解即可

PAC（Probably Approximately Correct） 是「学得好」的严格定义。直白翻译：

人话翻译 给两个小数 $\epsilon,\delta\in(0,1)$。如果存在算法 $A$ 和一个样本量函数 $n(\epsilon,\delta)$，使得：只要喂给 $A$ 这么多独立同分布(i.i.d.)样本，它输出的 $g$ 能做到——「犯错概率 $\mathbb{E}[f(x)\ne g(x)]\le\epsilon$（近似正确），而且这件好事至少以 $1-\delta$ 的概率发生（可能）」——那就说这个假设类 $H$ 是「PAC 可学习」的。两个词组合起来：「很可能（$1-\delta$）大致正确（$\le\epsilon$）」。

1.4 统计学习三要素（高频概念题）

要素回答什么问题具体内容
模型学什么样的模型？条件概率分布 $P(y|x)$ 或 决策函数 $y=f(x)$
策略用什么准则挑模型？经验风险最小化、结构风险最小化
算法怎么把模型学出来？一般归结为一个最优化问题
两个风险的区别 经验风险＝模型在训练集上的平均损失（追求「背熟」）；结构风险＝经验风险 ＋ 正则项（再加一句「别太复杂」，防止过拟合）。SVM 里 $\tfrac12\|w\|^2$ 就是结构风险中的正则项，而软间隔的 $C\sum\xi_i$ 就是经验风险部分——你看，三要素其实就藏在 SVM 的目标函数里。

分类维度还要记：监督学习（有标签）、无监督学习（无标签，如聚类）、半监督（少量标签）、弱监督（标签粗糙/带噪）。SVM 属于监督学习里的分类模型。

↑ 回目录
SECTION 02

SVM 的直觉：为什么偏偏要「最大间隔」

想象黑板上有一堆🔴红点（正类）和🟡黄点（负类），它们能被一条直线分开。问题是：能分开的直线有无数条（课件里画的 A、B、C、D 都行），到底选哪条？

A B（歪，离黄点太近） 最大间隔分类器 ✓ 间隔
同样能分开，SVM 选「两侧空地最宽」的那条红线——离最近的点最远。
核心直觉 SVM 的答案是：选那条「两边留白最宽」的线。两边留白越宽，意味着这条线离两类点都「绰绰有余」，将来来一个新点，哪怕有点噪声抖动，也不容易被分错——泛化能力最好。这条「留白宽度」就叫 间隔（margin）。SVM ＝ 间隔最大化的线性分类器。

那些恰好压在留白边界上、决定了这条线位置的点，就叫 支持向量（support vector）。神奇之处在于：只有支持向量起作用，把其它点删掉，最优线纹丝不动。这就是「支持」二字的由来。

↑ 回目录
SECTION 03

数学准备：点到直线（超平面）的距离

这是后面所有推导的地基，务必弄懂。

一条分界线（高维叫超平面）写成：

$$ w\cdot x + b = 0 $$

这里 $w$ 是法向量（垂直于这条线的方向），$b$ 是偏置。$w\cdot x$ 表示内积（对应分量相乘再相加）。

任意一点 $x$ 到这条线的几何距离是：

$$ \text{距离} = \frac{|w\cdot x + b|}{\|w\|} $$

其中 $\|w\|=\sqrt{w\cdot w}$ 是向量长度。分子的绝对值带不带号，决定了点在线的哪一侧。

3.1 用标签 y 巧妙去掉绝对值

规定正类 $y=+1$、负类 $y=-1$。若分类正确，正类点满足 $w\cdot x+b>0$，负类点满足 $w\cdot x+b<0$。于是「标签 × 分数」总是正的：

$$ y(w\cdot x+b) > 0 \quad(\text{分类正确时}) $$

因此可以用 $y(w\cdot x+b)$ 代替 $|w\cdot x+b|$。我们定义：

函数间隔
$\hat\gamma_i = y_i(w\cdot x_i+b)$（没除以 $\|w\|$，会随 $w,b$ 放大缩小）
几何间隔
$\gamma_i = \dfrac{y_i(w\cdot x_i+b)}{\|w\|}$（真实物理距离，不受缩放影响）

整个数据集的间隔 ＝ 离线最近那个点的间隔：$\gamma=\min_i \gamma_i$。SVM 要做的就是 最大化这个 $\gamma$。

↑ 回目录
SECTION 04

线性可分 SVM 的优化问题（从间隔到二次规划）

这一节把「最大化间隔」这句话，一步步翻译成一个可以求解的数学问题。跟着走五步：

  1. 原始目标：最大化几何间隔 $\gamma$，并要求每个点的几何间隔都 $\ge\gamma$。
    $$\max_{w,b}\ \gamma\qquad \text{s.t.}\ \ y_i\!\left(\tfrac{w}{\|w\|}\cdot x_i+\tfrac{b}{\|w\|}\right)\ge\gamma$$
  2. 换成函数间隔：注意 $\gamma=\hat\gamma/\|w\|$，代入后目标变成 $\max\ \hat\gamma/\|w\|$。
  3. 利用「可缩放」：函数间隔 $\hat\gamma$ 可以随意按比例缩放 $w,b$ 而不改变那条线本身。所以干脆令 $\hat\gamma=1$（把尺子标准化）。此时支持向量恰好满足 $y_i(w\cdot x_i+b)=1$。
  4. 翻转目标：最大化 $\dfrac{1}{\|w\|}$ ⟺ 最小化 $\|w\|$ ⟺ 最小化 $\dfrac12\|w\|^2$（加平方和 $\tfrac12$ 是为了求导方便，不影响最优解）。
  5. 得到标准形（原始问题 / Primal）：
    $$\min_{w,b}\ \frac12\|w\|^2 \qquad \text{s.t.}\ \ y_i(w\cdot x_i+b)\ge 1,\ \ i=1,\dots,N$$
这是什么类型的问题 目标 $\tfrac12\|w\|^2$ 是二次的、凸的；约束是线性不等式。所以这是一个 凸二次规划（convex QP）问题，有唯一的全局最优解。这点很重要：SVM 不会像神经网络那样陷入局部最优。

几何上，间隔的宽度恰好是 $\dfrac{2}{\|w\|}$（两条边界线 $w\cdot x+b=\pm1$ 之间的距离），所以「最小化 $\|w\|$」＝「最大化间隔 $\tfrac{2}{\|w\|}$」。

w·x+b=0 w·x+b=+1 w·x+b=−1 2/‖w‖ 支持向量
圈出来的点压在虚线（间隔边界）上，就是支持向量；中间实线是最终分界面。
↑ 回目录
SECTION 05

拉格朗日 → 对偶 → KKT（全章最核心的机制）

直接解上面那个带约束的问题不方便。SVM 用了一招「乾坤大挪移」，把它变成另一个等价、但更好解、还能引入核函数的对偶问题。这一节是理解全章的钥匙，慢慢看。

5.1 第一步：拉格朗日函数（把约束「吸收」进目标）

对每个不等式约束 $1-y_i(w\cdot x_i+b)\le 0$，配一个非负的拉格朗日乘子 $\alpha_i\ge0$，把约束揉进目标函数：

$$ L(w,b,\alpha)=\frac12\|w\|^2+\sum_{i=1}^{N}\alpha_i\big[\,1-y_i(w\cdot x_i+b)\,\big] $$

直觉：$\alpha_i$ 像一个「罚款管理员」。如果某点违反约束（$1-y_i(\cdot)>0$），管理员就把 $\alpha_i$ 调大来加重惩罚。

5.2 第二步：为什么 $\min_{w,b}\max_\alpha L$ 等价于原问题

先固定 $w,b$，对 $\alpha$ 求最大：

所以 $\max_\alpha L = \begin{cases}\tfrac12\|w\|^2,&\text{满足约束}\\ +\infty,&\text{违反约束}\end{cases}$。再对它求 $\min_{w,b}$，违反约束的 $+\infty$ 自动被淘汰——于是 $\min_{w,b}\max_\alpha L$ 与原始问题完全等价。

5.3 第三步：交换 min/max，得到对偶问题

把 $\min\max$ 换成 $\max\min$，得到对偶问题：

$$ \min_{w,b}\max_{\alpha}L \ \xrightarrow{\text{对偶}}\ \max_{\alpha}\min_{w,b}L $$

一般地总有 $\max_\alpha\min_{w,b}L \le \min_{w,b}\max_\alpha L$（弱对偶，min-max 不等式）。但当问题是凸的、且满足 KKT 条件时，等号成立（强对偶），两个问题答案相同。SVM 恰好满足，所以我们可以放心地转去解更简单的对偶问题。

KKT 条件（求解的总开关） 在最优点，下面几条必须同时成立（$i=1,\dots,N$）：
$$\begin{aligned} &\nabla_{w,b}\,L=0 &&\text{(梯度为零)}\\ &\alpha_i\big[\,1-y_i(w\cdot x_i+b)\,\big]=0 &&\text{(互补松弛 ★最关键)}\\ &1-y_i(w\cdot x_i+b)\le0 &&\text{(原约束)}\\ &\alpha_i\ge0 &&\text{(乘子非负)} \end{aligned}$$
带★那条「互补松弛」是判定支持向量的依据，见 6.3。

5.4 第四步：对 w、b 求偏导，消掉它们

解内层 $\min_{w,b}$：令 $L$ 对 $w,b$ 的偏导为 0：

$$ \frac{\partial L}{\partial w}=0\Rightarrow w=\sum_{i=1}^N\alpha_i y_i x_i,\qquad \frac{\partial L}{\partial b}=0\Rightarrow \sum_{i=1}^N\alpha_i y_i=0 $$

把这两个结果代回 $L$，神奇的事发生了：$w,b$ 全部消失，只剩下 $\alpha$。整理后得到对偶问题的最终形式（已把求极大加负号转成求极小）：

$$ \boxed{\ \min_{\alpha}\ \frac12\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_j y_i y_j (x_i\cdot x_j)\;-\;\sum_{i=1}^N\alpha_i\ }$$
$$ \text{s.t.}\quad \sum_{i=1}^N\alpha_i y_i=0,\qquad \alpha_i\ge0,\ i=1,\dots,N $$
为什么要费这么大劲转对偶 三大好处，每条都要会背：
① 原问题变量是 $w$（维度 = 特征数），对偶问题变量是 $\alpha$（维度 = 样本数），把对维度的依赖换成了对样本数的依赖；
② 目标函数里样本只以内积 $x_i\cdot x_j$ 的形式出现——这正是后面核技巧能插进来的入口；
③ 解出来后，只有支持向量的 $\alpha_i>0$，模型稀疏，预测只需用到少数几个点。
↑ 回目录
SECTION 06

解出 α 之后：怎么算 w*、b*，谁是支持向量

6.1 求 $w^*$

$$ w^*=\sum_{i=1}^N \alpha_i^* y_i x_i $$

只有 $\alpha_i^*>0$ 的项有贡献，所以 $w^*$ 实际上只是支持向量的加权和。

6.2 求 $b^*$

挑任意一个 $\alpha_j^*>0$ 的支持向量 $x_j$，它满足 $y_j(w^*\cdot x_j+b^*)=1$。两边乘 $y_j$（注意 $y_j^2=1$）解出：

$$ b^*=y_j-w^*\cdot x_j=y_j-\sum_{i=1}^N\alpha_i^* y_i\,(x_i\cdot x_j) $$
小技巧理论上用任一支持向量算 $b^*$ 结果都一样；考试时可以用两个不同支持向量各算一次，互相验证，对上了说明前面没算错。

6.3 谁是支持向量（互补松弛的威力）

由 KKT 的互补松弛 $\alpha_i[1-y_i(w\cdot x_i+b)]=0$：

结论一句话：$\alpha_i>0$ 对应的样本 $x_i$ 就是支持向量。

6.4 最终分类器

$$ \text{超平面}:\ w^*\cdot x+b^*=0,\qquad \text{决策函数}:\ f(x)=\operatorname{sign}(w^*\cdot x+b^*) $$

$\operatorname{sign}$ 取符号：算出来 $>0$ 判为 $+1$（正类），$<0$ 判为 $-1$（负类）。这就是给新点分类的最后一步。

↑ 回目录
SECTION 07

把流程走一遍：课件经典例题 (3,3)(4,3)(1,1)

这是课件原题，也是线性可分 SVM 的模板题。把它完整算一遍，第 11 节的真题就水到渠成。

题目正例 $x_1=(3,3)^T,\ x_2=(4,3)^T$；负例 $x_3=(1,1)^T$。用对偶问题求线性可分 SVM。（$y_1=y_2=+1,\ y_3=-1$）
  1. 写出对偶目标。先算各内积 $x_i\cdot x_j$，代入 $\tfrac12\sum\sum\alpha_i\alpha_j y_i y_j(x_i\cdot x_j)-\sum\alpha_i$，展开得：
    $$\tfrac12\big(18\alpha_1^2+25\alpha_2^2+2\alpha_3^2+42\alpha_1\alpha_2-12\alpha_1\alpha_3-14\alpha_2\alpha_3\big)-\alpha_1-\alpha_2-\alpha_3$$
    约束：$\alpha_1+\alpha_2-\alpha_3=0$（即 $\sum\alpha_iy_i=0$），$\alpha_i\ge0$。
  2. 用约束消元。由 $\alpha_3=\alpha_1+\alpha_2$ 代入，记为
    $$s(\alpha_1,\alpha_2)=4\alpha_1^2+\tfrac{13}{2}\alpha_2^2+10\alpha_1\alpha_2-2\alpha_1-2\alpha_2$$
  3. 求无约束极值。对 $\alpha_1,\alpha_2$ 求偏导置零，解得极值点 $(\tfrac32,-1)$。但 $\alpha_2=-1<0$ 违反 $\alpha_2\ge0$！说明最小值不在内部，必在边界上。
  4. 查边界。分别令 $\alpha_1=0$、$\alpha_2=0$：
    • $\alpha_1=0$：$s$ 在 $\alpha_2=\tfrac{2}{13}$ 取最小 $-\tfrac{2}{13}\approx-0.154$；
    • $\alpha_2=0$：$s$ 在 $\alpha_1=\tfrac14$ 取最小 $-\tfrac14=-0.25$。
    比较：$-\tfrac14<-\tfrac{2}{13}$，所以最小在 $\alpha_1=\tfrac14,\ \alpha_2=0$。此时 $\alpha_3=\alpha_1+\alpha_2=\tfrac14$。
  5. 回代求参数。 $\alpha_2=0$ 说明 $x_2$ 不是支持向量；$\alpha_1,\alpha_3>0$ 说明 $x_1,x_3$ 是支持向量。
    $$w^*=\alpha_1y_1x_1+\alpha_3y_3x_3=\tfrac14(3,3)-\tfrac14(1,1)=\left(\tfrac12,\tfrac12\right)$$
    用支持向量 $x_1$（$y_1=1$）求 $b^*$：$b^*=y_1-w^*\cdot x_1=1-(\tfrac12\cdot3+\tfrac12\cdot3)=1-3=-2$。

结果：分离超平面 $\tfrac12 x^{(1)}+\tfrac12 x^{(2)}-2=0$，决策函数 $f(x)=\operatorname{sign}\!\big(\tfrac12 x^{(1)}+\tfrac12 x^{(2)}-2\big)$。

本题最值得记的套路三个点时，对偶目标只剩 1~2 个变量，求偏导得到的内部极值点常常违反 $\alpha\ge0$，这时一定要转到边界（令某个 $\alpha=0$）逐个比较。这正是 2021 真题的考点核心。
↑ 回目录
SECTION 08

线性 SVM：软间隔（松弛变量 ξ 与惩罚参数 C）

现实里数据常常大体可分，但混进几个「捣乱」的点，硬要画一条线 100% 分对反而会被噪声带歪。解决办法：允许少数点「越界」，但要付出代价。

8.1 引入松弛变量 ξ

给每个点配一个 $\xi_i\ge0$，把硬约束放松成：

$$ y_i(w\cdot x_i+b)\ge 1-\xi_i,\qquad \xi_i\ge0 $$

$\xi_i$ 衡量「这个点越界了多少」：$\xi_i=0$ 表示老实待在边界外；$\xi_i>0$ 表示越了界。

8.2 加惩罚项，得到软间隔目标

$$ \min_{w,b,\xi}\ \frac12\|w\|^2+C\sum_{i=1}^N\xi_i \qquad \text{s.t.}\ \ y_i(w\cdot x_i+b)\ge1-\xi_i,\ \xi_i\ge0 $$

这叫软间隔最大化。$C>0$ 是惩罚参数，调和「间隔尽量大」与「错分尽量少」两个目标：

C 取值含义后果
C 大对错分惩罚重尽量分对每个点 → 间隔窄，易过拟合
C 小对错分惩罚轻容忍更多错分 → 间隔宽，易欠拟合

8.3 软间隔的对偶问题（只改一处）

推导几乎和硬间隔一样，结果只是把 $\alpha_i\ge0$ 变成了有上界：

$$ \min_{\alpha}\ \frac12\sum_i\sum_j\alpha_i\alpha_j y_iy_j(x_i\cdot x_j)-\sum_i\alpha_i,\quad \text{s.t.}\ \sum_i\alpha_iy_i=0,\ \boxed{0\le\alpha_i\le C} $$

求 $b^*$ 时要挑一个严格在内部的支持向量（$0<\alpha_j^*

↑ 回目录
SECTION 09

非线性 SVM 与核技巧（真题的主战场）

有些数据怎么画直线都分不开（比如一类点围成圈，另一类在圈内）。思路：先把点映射到更高维空间，在那里它们就线性可分了，再用前面的线性 SVM 去分。

x₁ 一维：圆点夹着方点，无法用一个点分开 ⇒ x₂=x₁² x₁x₂ 升维后一条直线就分开了
把一维点按 $x_2=x_1^2$ 抬到二维，原本分不开的点变得线性可分。

9.1 映射 φ 与「维度爆炸」难题

记映射 $\phi(x):X\to H$（把低维点送到高维特征空间）。在新空间做线性 SVM，对偶目标里出现的就是 $\phi(x_i)\cdot\phi(x_j)$。问题：高维空间维度可能极大甚至无穷，直接算 $\phi$ 再做内积会「维度爆炸」。

9.2 核技巧：绕开 φ，直接算内积

核函数定义：若存在映射 $\phi$，使对所有 $x,z$ 都有

$$ K(x,z)=\phi(x)\cdot\phi(z) $$

则称 $K$ 为核函数。妙处在于：我们只需要内积的结果 $K(x,z)$，根本不必真的求出 $\phi$！ 把对偶问题里所有 $x_i\cdot x_j$ 换成 $K(x_i,x_j)$ 即可，计算量回到低维。

展开看：为什么 $K(x,z)=(x\cdot z)^2$ 暗含一个二维→三维映射

设 $x=(x^{(1)},x^{(2)}),\ z=(z^{(1)},z^{(2)})$，则

$$(x\cdot z)^2=(x^{(1)}z^{(1)}+x^{(2)}z^{(2)})^2=(x^{(1)}z^{(1)})^2+2x^{(1)}z^{(1)}x^{(2)}z^{(2)}+(x^{(2)}z^{(2)})^2$$

它正好等于 $\phi(x)\cdot\phi(z)$，其中 $\phi(x)=\big((x^{(1)})^2,\ \sqrt2\,x^{(1)}x^{(2)},\ (x^{(2)})^2\big)^T$。可见 $\phi$ 并不唯一（也可取四维版本），但内积结果都一样——所以我们干脆只关心 $K$。

9.3 非线性 SVM 算法（把内积全换成 K）

$$ \min_{\alpha}\ \frac12\sum_i\sum_j\alpha_i\alpha_j y_iy_j\,K(x_i,x_j)-\sum_i\alpha_i,\quad \text{s.t.}\ \sum_i\alpha_iy_i=0,\ 0\le\alpha_i\le C $$

解得 $\alpha^*$ 后，选一个 $0<\alpha_j^*0$）计算：

$$ b^*=y_j-\sum_{i=1}^N\alpha_i^* y_i\,K(x_i,x_j) $$

最终决策函数（注意：用 $K$，不需要显式 $w$）：

$$ \boxed{\ f(x)=\operatorname{sign}\!\Big(\sum_{i=1}^N \alpha_i^* y_i\,K(x_i,x)+b^*\Big)\ } $$
易错点非线性情形下，给新点分类要用上面这个核展开式，不要去算 $w^*\cdot x+b^*$（因为 $w^*$ 活在高维空间，一般写不出来）。这是真题第 3 题最后一步的关键。
↑ 回目录
SECTION 10

常用核函数 & σ 对拟合的影响

核函数公式特点
多项式核$K(x,z)=(x\cdot z+1)^p$$p$ 越大越能拟合复杂边界（真题用的 $(1+x^Ty)^2$ 就是 $p=2$ 版本）
高斯核 (RBF)$K(x,z)=\exp\!\big(-\dfrac{\|x-z\|^2}{2\sigma^2}\big)$最常用；隐含无穷维映射

高斯核里的 $\sigma$ 控制「每个点的影响半径」，直接决定拟合程度：

类比记忆$\sigma$ 之于高斯核，就像软间隔里的 $C$——都是控制「模型复杂度 / 拟合程度」的旋钮，调过头就过拟合或欠拟合。
↑ 回目录
SECTION 11 · ★必考

2021 真题第 3 题：非线性 SVM 全程求解

原题 正例 $x_1=(0,0)^T$；负例 $x_2=(1,1)^T,\ x_3=(-1,-1)^T$。核函数 $K(x,y)=(1+x^T y)^2$。求 SVM 参数，并给出 $(0,1)^T$ 的分类。
（标签：$y_1=+1,\ y_2=-1,\ y_3=-1$）

这就是第 9 节流水线的实战。一步步来，每一步都给出数字。

  1. 算核矩阵 $K(x_i,x_j)$。先算内积 $x_i^Tx_j$，再套 $(1+\cdot)^2$：
    $$\begin{aligned} &K_{11}=(1+0)^2=1,\quad K_{12}=(1+0)^2=1,\quad K_{13}=(1+0)^2=1\\ &K_{22}=(1+2)^2=9,\quad K_{23}=(1+(-2))^2=1,\quad K_{33}=(1+2)^2=9 \end{aligned}$$
    （例如 $x_2^Tx_2=1\!\cdot\!1+1\!\cdot\!1=2$，故 $K_{22}=(1+2)^2=9$；$x_2^Tx_3=1\!\cdot\!(-1)+1\!\cdot\!(-1)=-2$，故 $K_{23}=(1-2)^2=1$。）
  2. 写对偶目标。代入 $\tfrac12\sum_i\sum_j\alpha_i\alpha_j y_iy_jK_{ij}-\sum_i\alpha_i$。注意 $y_1y_2=y_1y_3=-1,\ y_2y_3=+1$：
    $$W=\tfrac12\big(\alpha_1^2+9\alpha_2^2+9\alpha_3^2-2\alpha_1\alpha_2-2\alpha_1\alpha_3+2\alpha_2\alpha_3\big)-(\alpha_1+\alpha_2+\alpha_3)$$
    约束：$\alpha_1y_1+\alpha_2y_2+\alpha_3y_3=0\Rightarrow \alpha_1-\alpha_2-\alpha_3=0\Rightarrow \boxed{\alpha_1=\alpha_2+\alpha_3}$，且 $\alpha_i\ge0$。
  3. 消元代入。把 $\alpha_1=\alpha_2+\alpha_3$ 代进去（含 $\alpha_1$ 的项全部展开）。逐项合并后，交叉项 $\alpha_2\alpha_3$ 的系数恰好抵消为 0，只剩平方项：
    $$W(\alpha_2,\alpha_3)=4\alpha_2^2+4\alpha_3^2-2\alpha_2-2\alpha_3$$
    展开看这步的合并细节

    方括号内代入后：$\alpha_1^2=\alpha_2^2+2\alpha_2\alpha_3+\alpha_3^2$；$-2\alpha_1\alpha_2=-2\alpha_2^2-2\alpha_2\alpha_3$；$-2\alpha_1\alpha_3=-2\alpha_2\alpha_3-2\alpha_3^2$。把这些和 $+9\alpha_2^2+9\alpha_3^2+2\alpha_2\alpha_3$ 相加：$\alpha_2^2$ 系数 $=1+9-2=8$；$\alpha_3^2$ 系数 $=1+9-2=8$；$\alpha_2\alpha_3$ 系数 $=2-2-2+2=0$。所以方括号 $=8\alpha_2^2+8\alpha_3^2$，乘 $\tfrac12$ 得 $4\alpha_2^2+4\alpha_3^2$。线性项 $\alpha_1+\alpha_2+\alpha_3=2\alpha_2+2\alpha_3$。合起来即上式。

  4. 求极小。这次两变量解耦，分别求偏导置零：
    $$\frac{\partial W}{\partial\alpha_2}=8\alpha_2-2=0\Rightarrow\alpha_2=\tfrac14,\qquad \frac{\partial W}{\partial\alpha_3}=8\alpha_3-2=0\Rightarrow\alpha_3=\tfrac14$$
    两者都 $\ge0$，满足约束（不像课件例题那样跑到边界），可直接采用。再由约束 $\alpha_1=\alpha_2+\alpha_3=\tfrac12$。
    $$\boxed{\ \alpha^*=\left(\tfrac12,\ \tfrac14,\ \tfrac14\right)\ }\quad\text{三个点 }\alpha_i^*>0\text{，全是支持向量。}$$
  5. 求 $b^*$。用支持向量 $x_1$（$y_1=+1$）：$b^*=y_1-\sum_i\alpha_i^* y_i K(x_i,x_1)$。
    $$\sum_i\alpha_i^*y_iK(x_i,x_1)=\tfrac12(1)(1)+\tfrac14(-1)(1)+\tfrac14(-1)(1)=\tfrac12-\tfrac14-\tfrac14=0$$
    所以 $b^*=1-0=\boxed{1}$。
    验算用 $x_2$（$y_2=-1$）：$\sum=\tfrac12(1)(1)+\tfrac14(-1)(9)+\tfrac14(-1)(1)=\tfrac12-\tfrac94-\tfrac14=-2$，则 $b^*=-1-(-2)=1$。一致，✓。
  6. 对新点 $x=(0,1)^T$ 分类。先算它与三个支持向量的核：
    $$\begin{aligned} K(x_1,x)&=(1+(0,0)\!\cdot\!(0,1))^2=(1+0)^2=1\\ K(x_2,x)&=(1+(1,1)\!\cdot\!(0,1))^2=(1+1)^2=4\\ K(x_3,x)&=(1+(-1,-1)\!\cdot\!(0,1))^2=(1+(-1))^2=0 \end{aligned}$$
    代入决策函数：
    $$g(x)=\sum_i\alpha_i^*y_iK(x_i,x)+b^*=\tfrac12(1)(1)+\tfrac14(-1)(4)+\tfrac14(-1)(0)+1=\tfrac12-1+0+1=\tfrac12$$
    $g(x)=\tfrac12>0$，故 $f(x)=\operatorname{sign}(\tfrac12)=+1$。
最终答案 $\alpha^*=(\tfrac12,\tfrac14,\tfrac14)$，$b^*=1$，三点均为支持向量。决策函数 $f(x)=\operatorname{sign}\!\big(\sum_{i=1}^3\alpha_i^*y_iK(x_i,x)+1\big)$。新点 $(0,1)^T$ 的判别值 $g=\tfrac12>0$，分类为正类 (+1)。
检查训练点也都分对 $x_1$：$g=0+1=1>0$ → +1 ✓；$x_2$：$g=-2+1=-1<0$ → −1 ✓；$x_3$（对称）：$g=-2+1=-1<0$ → −1 ✓。三个训练点全部正确，答案可信。
↑ 回目录
SECTION 12

SMO / 多分类 / 文本分类 / tf-idf（概念题素材）

12.1 SMO 算法

SVM 的对偶问题是凸二次规划，有全局最优解；但样本多时通用解法太慢。SMO（序列最小最优化）由微软的 Platt 于 1998 年提出，当时最快。核心思想：每次只挑两个 $\alpha$ 来优化、固定其余（因为约束 $\sum\alpha_iy_i=0$ 至少要动两个才能保持成立），不断迭代直到收敛。考试一般只问「是谁提的、解决什么、基本思想」。

12.2 SVM 做多分类

策略做法
一对多 (OvR)每个类训一个「本类 vs 其余」SVM；预测取分类函数值最大的类
一对一 (OvO)任意两类训一个 SVM，共 $\binom{k}{2}$ 个；预测时投票，得票多者胜
层次法先把所有类分成两大组，每组再二分，逐层下去

12.3 文本分类与 tf-idf

向量空间模型：把一篇文档表示成向量 $(w_{1j},w_{2j},\dots,w_{nj})^T$，$w_{ij}$ 是词项 $i$ 在文档 $j$ 中的权重。权重常见两种：

实际流程概念：分类体系建立 → 数据收集 → 预处理（分词、去停用词、词干化 Stemming、特征选择）→ 训练 SVM。

↑ 回目录
APPENDIX A

附录 A：决策树 ID3（第 5 题用得上）

真题第 5 题要求用 ID3 建决策树、给出根节点及其子节点、标出叶节点类别。ID3 的核心就一句话：每次选「信息增益最大」的特征来分裂。

A.1 三个公式

经验熵
$H(D)=-\sum_{k}\dfrac{|C_k|}{|D|}\log_2\dfrac{|C_k|}{|D|}$　（数据集 $D$ 按类别 $C_k$ 的混乱程度，越大越乱）
条件熵
$H(D|A)=\sum_{v}\dfrac{|D_v|}{|D|}H(D_v)$　（用特征 $A$ 把 $D$ 切成若干子集 $D_v$ 后的平均熵）
信息增益
$g(D,A)=H(D)-H(D|A)$　（用 $A$ 分裂后「混乱减少了多少」，越大越好）

A.2 解题步骤

  1. 算总体经验熵 $H(D)$（按正负例比例）。
  2. 对每个候选特征 $A$，算条件熵 $H(D|A)$，再得信息增益 $g(D,A)=H(D)-H(D|A)$。
  3. 选 $g$ 最大的特征作根节点，按它的取值长出分支。
  4. 对每个分支的子集递归。若某子集已全是同一类，停下来标成叶节点（类别即该类）。
考试小贴士$\log_2$ 常用值背一下：$\log_2 2=1$，$\log_2 3\approx1.585$，$\log_2\tfrac13\approx-1.585$。题目往往只要根节点和它的子节点，算 1~2 层即可，别被吓到。比较信息增益时，因为 $H(D)$ 对所有特征相同，谁的条件熵 $H(D|A)$ 最小，谁的信息增益就最大，可省一步。
↑ 回目录
APPENDIX B

附录 B：朴素贝叶斯（范式里提到，比较简单）

「朴素」＝假设各特征相互独立。对新样本 $x=(x^{(1)},\dots,x^{(n)})$，比较每个类别 $c_k$ 的「后验」大小，取最大者：

$$ \hat y=\arg\max_{c_k}\ P(y=c_k)\prod_{j=1}^{n}P\big(x^{(j)}\mid y=c_k\big) $$

其中先验 $P(y=c_k)=\dfrac{\text{类 }c_k\text{ 的样本数}}{N}$，条件概率 $P(x^{(j)}|c_k)=\dfrac{\text{类 }c_k\text{ 中第 }j\text{ 特征取该值的数}}{\text{类 }c_k\text{ 的样本数}}$。

拉普拉斯平滑若某条件概率为 0 会让整个乘积归零。修正：分子 $+\lambda$、分母 $+\lambda\times(\text{该特征取值个数})$，常取 $\lambda=1$。

套路：① 数出各类先验；② 对新样本每个特征，分别算两类的条件概率；③ 两条乘积线各乘一遍，比大小，大的那类就是答案。纯数数，不难。

↑ 回目录
SECTION 15

考前速查表 & 做题模板

15.1 必背公式一页纸

名称公式
原始问题(硬)$\min \tfrac12\|w\|^2$, s.t. $y_i(w\cdot x_i+b)\ge1$
原始问题(软)$\min \tfrac12\|w\|^2+C\sum\xi_i$, s.t. $y_i(w\cdot x_i+b)\ge1-\xi_i,\ \xi_i\ge0$
对偶(线性)$\min_\alpha \tfrac12\sum\sum\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum\alpha_i$, s.t. $\sum\alpha_iy_i=0$，硬:$\alpha_i\ge0$／软:$0\le\alpha_i\le C$
对偶(核)把 $(x_i\cdot x_j)$ 换成 $K(x_i,x_j)$
$w^*$$\sum\alpha_i^*y_ix_i$（核情形不显式求）
$b^*$$y_j-\sum\alpha_i^*y_iK(x_i,x_j)$，取 $0<\alpha_j^*(
决策函数$f(x)=\operatorname{sign}\!\big(\sum\alpha_i^*y_iK(x_i,x)+b^*\big)$
支持向量$\alpha_i^*>0$ 的样本

15.2 SVM 计算题通用模板（照抄即可）

  1. 列出样本、标签 $y$；线性题算内积矩阵，核题算核矩阵 $K_{ij}$。
  2. 写对偶目标 $\tfrac12\sum\sum\alpha_i\alpha_jy_iy_jK_{ij}-\sum\alpha_i$，写约束 $\sum\alpha_iy_i=0$。
  3. 用约束消去一个 $\alpha$，目标变成 1~2 元二次函数。
  4. 求偏导置零找极值点。检查 $\alpha\ge0$（及 $\le C$）：满足就用；违反就转边界（令某 $\alpha=0$）逐个比较取最小。
  5. 得 $\alpha^*$，$\alpha_i^*>0$ 的是支持向量；用某支持向量求 $b^*$，再用另一个验算。
  6. 写决策函数；要分类新点就代入算 $g(x)$，看符号定正负。
易错清单（考前再扫一眼） ① 标签务必用 $\pm1$，正负别搞反；
② 核题里 $w^*$ 不显式求，分类用核展开式；
③ 内部极值点违反 $\alpha\ge0$ 时一定要查边界；
④ 求 $b^*$ 要挑支持向量（$\alpha_j^*>0$；软间隔取 $0<\alpha_j^* ⑤ $\operatorname{sign}$ 看的是符号，不是数值大小；
⑥ 概念题记牢：三要素、对偶三大好处、C 与 σ 对过/欠拟合的方向。
一句话收尾 整章的灵魂只有两件事：「最大间隔」的几何直觉 + 「对偶 + 核」的求解机制。把第 11 节的真题闭卷默写两遍，再用 15.2 的模板把课件 (3,3)(4,3)(1,1) 例题独立做对，这门课的计算部分就稳了。祝考试顺利！
↑ 回到顶部