这周的论文笔记是『A Tutorial on Support Vector Machines for Pattern Recognition』，说是这周，其实是贪心导师一个月前步骤的作业了(捂脸ing)，由于双十一前后公司各种上线，导致每天只能看看录播课程，不过接下来到年前应该都有时间，所以赶紧充（装）实（bi）起来！
摘要
关于这篇论文，堪称SVM最佳，而之所以最佳，在于它不同于一般论文直接从SVM概念入手，开篇即谈分类模型，而是先从VC维和结构风险化概述开始，通过这两个概念来阐述用于可分离和不可分离数据的线性支持向量机（SVMs），接下来通过一个机械类比（将两个或两类性质根本不同、仅有某些表面相似的对象进行类比的逻辑错误），讨论SVM在何时会是全局唯一解。然后讲解如何进行支持向量训练。再然后最重要的来了，详细的讨论了用于构造数据中非线性支持向量机解的核映射技术，后面还介绍SVMs如何支持超高VC维（甚至是无穷维），通过计算齐次多项式和高斯函数的VC维的径向基函数核等等。也正因此，支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础之上的。
简介
支持向量机（SVM）是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；支持向量机也包括核技巧，这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化，即可转化成一个求解凸二次规划问题，亦可等价于一个正则化的合页损失函数的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。
核函数
当输入控件为欧式空间或离散集合、特征空间为希尔伯特空间时，核函数表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。
核技巧
通过使用核函数可以学习非线性支持向量机，等价于隐式地在高维的特征空间中学习线性支持向量机。
核方法
比支持向量机更为一般的机器学习方法。
结构风险最小化
置信风险：分类器对未知样本进行分类，得到的误差
经验风险：训练好的分类器，对训练样本重新分类得到的误差（即样本误差）。它是模型关于训练样本集的平均损失。当样本容量很大时，经验风险最小化能保证有很好的学习效果，比如：极大似然估计（MLE）就是经验风险最小化的例子。当模型是条件概率分布，损失函数是对数损失函数时，经验风险最小化就是等于极大似然估计。但当样本容量过小时，经验风险最小化学习的效果未必会很好，会产生过拟合现象。而结构风险最小化（Structural Risk Minimization, SRM）则是为了防止过拟合而提出的策略。
结构风险：置信风险 + 经验风险
结构风险最小化是为了防止过拟合而提出的一种策略，它等价于正则化。贝叶斯估计中最大后验概率估计就是结构风险最小化的一个例子。当模型的条件概率分布、损失函数是对数损失函数、模型复杂度由模型先验概率表示时，结构风险最小化等价于最大后验概率估计。监督学习问题变成经验风险或结构风险函数的最优化问题，这时经验风险或结构风险函数是最优化的目标函数。
VC维
将N个点进行分类，如分成两类（二维线性分类器），那么有$2^N$中分法。若存在这样一种假设H，它能准确的将$2^N$种问题进行分类。那么这些点的数量N，就是假设H的VC维，表示VC(H)。简单讲：只要存在N个样本能够被成功打散（Shatter），并且不存在N+1个样本能够被打散（随机划分类别）的话，就称这一函数集合的VC维是N。它反映一个模型（假设空间中的一个函数）的学习能力，VC维越大，则模型的容量越大。若H能够打散任意大小的集合，那么VC(H)为无穷大。
有关研究工作
SVM学习模型
Cortes与Vapnik提出非线性支持向量机，Boser、Cuyon与Vapnik又引入核技巧，提出非线性支持向量机。
线性可分支持向量机
线性可分支持向量机处理的是严格线性可分的数据集
给定线性可分训练集，通过间隔最大化或者等价地求解相应的凸二次规划问题学习得到的分离超平面为
$w^{*}·x + b^{*} = 0$
以及相应的分类决策函数
$f(x) = sign(w^{*}·x + b^{*})$
或者
$f(x) = sign(\sum_{i=1}^{N} \alpha ^{*} y ^{*}< x_i, x > + b ^{*})$
称为线性可分支持向量机
其学习的优化问题如下：
$\min_{w,b}$ $\frac{1}{2}\left | w \right |^{2}$
s.t. $y_i(w·x_i) - 1 \geq 0，i = 1,2,…,N$
线性支持向量机
线性支持向量机处理的是线性不可分的数据集。对于线性支持向量机的优化问题，就是在线性可分支持向量机的基础上加一个松弛变量。
其学习的优化问题如下：
$\min_{w,b,\xi}$ $\frac{1}{2}\left | w \right |^{2} + C\sum_{i=1}^{N}\xi_i$
s.t. $y_i(w_i + b) \geq 1，i = 1,2,…,N$
$\xi_i \geq 0，i = 1,2,…,N$
所求的分类超平面和决策函数与线性可分支持向量机相同
这里要简单介绍一下KKT条件（Karush-Kuhn-Tucker Conditions）和 拉格朗日乘子法，这个在SVM推导中需要用到
介绍之前，先了解一些定义（部分在周作业中证明过）
凸集定义： 欧式空间中，对于集合中的任意两点的连线，连线上任意一点都在集合中，那么这个集合就是凸集。
凸函数定义： 对于任意属于[0, 1]的 m 和 任意属于凸集上的两点$c_1$和$c_2$，有$f(mc_1 + (1-m)c_2) \leq mf(c_1) + (1-m)f(c_2)$，几何上的意义就是两点连线上的某点函数值，大于等于两点之间某点的函数值。凸函数上的任一局部最小点均是全局极小点。
半正定矩阵： 特征值大于等于0的实对称矩阵。
半正定矩阵的充要条件： 行列式（n阶顺序主子式）等于0，行列式的i阶顺序主子式 $\geq$ 0，i 从1到 n-1。
凸函数的充要条件： 如果f(x)在开凸集S上具有二阶连续偏导数，且f(x)的海森矩阵（二阶偏导矩阵）在S上处处半正定，则f(x)为S上的凸函数。
- 什么是KKT条件
对于具有等式和不等式约束的一般优化问题
$$\left\{\begin{matrix} \min f(x) & 最值问题\\ s.t. g_j(x) \leq 0 (j = 1,2,3,...,m); & 不等式约束\\ h_k(x) = 0 (k = 1,2,3,...,l) & 等式约束 \end{matrix}\right.$$KKT条件给出了判断 $\mathbf{x}^{*}$是否为最优解的必要条件，即：
$$\left\{\begin{matrix} \frac{\partial f}{\partial x_i} + \sum_{j=1}^{m}\mu _j\frac{\partial g_i}{\partial x_i} + \sum_{k=1}^{l}\lambda _k \frac{\partial h_k}{\partial x_i} = 0\\ \\ h_k(x) = 0, (k = 1,2,3,...,l)\\ \\ \mu_jg_j(x) = 0, (j = 1,2,3,...,m)\\ \\ \mu_j \geq 0 \end{matrix}\right.$$
- 1、关于等式约束优化问题，这里其实就是拉格朗日乘子法
- 2、关于不等式优化问题，就是将不等式约束条件转换为等式约束条件（做法：引入松弛变量）
- 什么是拉格朗日乘子法
简单点就是，一个无约束问题，加上一个被$\lambda$乘上的约束条件问题，当无约束问题的极值点梯度与约束条件问题的切线垂直，那么这个$\lambda$就是拉格朗日乘子。这样就将原来的无约束问题转换为在拉格朗日乘子处理之后的等式约束优化问题了。而对于不等式约束优化问题就交托给上面的KKT条件了。
非线性支持向量机
非线性支持向量机引入了核函数。
分类决策函数如下：
$f(x) = sign(\sum_{i=1}^{N}\alpha ^{*} _i y_i \kappa (x_i, x) + b^ *)$
模式识别与机器学习的泛化性能边界
假设有$\varphi$个样本，每个样本包含如下一对数据$(x_i, y_i)$，其中，向量$\vec{x}_i \in R^n$，i=1，2，…，$\varphi$，$y_i$为给定的标签。
以树的识别问题来说，$\vec{x}_i$表示的是一个像素灰度值的向量，则 $y_i$ = 1（若图中有树）和 $y_i$ = -1（若图中无树）；
假设这些数据中存在未知的概率分布$P(\vec{x}, y)$，并且数据满足独立同分布（Independently Identically Distribution, IID）。【注】$P$代表累积概率分布，$p$代表密度分布。
这个假设相比于对每个$\vec{x}$给定一个标签$y$更加一般化：它允许对于给定的$\vec{x}$都有一个$y$的分布，在这种情况下，可靠源将会依照由$\vec{x}_i$而产生的固定分布对$y_i$进行赋值。即这将对每个给定的$\vec{x}$赋予一个固定的$y$。
现在假设我们有一个机器的任务：学习将$\vec{x}_i$映射到$y_i$上。这个机器实际上是通过一系列可能的映射$\vec{x}_i$ → $f(\vec{x}, \alpha)$来定义的。其中，函数$f(\vec{x}, \alpha)$通过可以调节的参数$\alpha$来标示的。$\alpha$的一个特别的选择生成了我们所谓的”训练机”。因此，一个有着固定的结构和确定权重偏量的神经网络被称为”学习机”。
故一个训练机的测试误差的期望值如下：
$R(\alpha) = \int \frac{1}{2}\left | y - f(\vec{x}, \alpha) \right |dP(\vec{x}, y)$
当概率密度函数$p(\vec{x},y)$有值时，$dP(\vec{x}, y) = p(\vec{x}, y)\mathrm{d} x\mathrm{d} y$
$R(\alpha)$被称为期望风险。
$R_{emp}(\alpha)$则被称为经验风险：训练集测量的平均误差率（针对固定且有限的观测样本）
$R_{emp}(\alpha) = \int \frac{1}{2\varphi}\sum_{i=1}^{\varphi}\left | y_i - f(\vec{x}, \alpha) \right |$
$R_{emp}$是一个针对特定 $\alpha$ 的选择 和 一个特定训练集 ${x_i, y_i}$ 的固定数值。
而$\frac{1}{2\varphi}\left | y_i - f(\vec{x}, \alpha) \right |$则被称为损失。对于此种情形，这里的损失只可以取值0和1。
现在选择一些 $\eta$ 满足 $0\leq \eta\leq1$，对于选取这些值的损失，有概率 $1-\eta$，将会有如下所示边界：
$R(\alpha) \leq R_{emp}(\alpha) + \sqrt{\frac{h(\log(\frac{2\varphi}{h} + 1)) - \log (\frac{\eta}{4})}{\varphi}}$
其中，h是一个非负整数，即Vapnik Chervonenkis（VC）维数，上式右边称为”Risk Bound风险边界“，$\sqrt{\frac{h(\log(\frac{2\varphi}{h} + 1)) - \log (\frac{\eta}{4})}{\varphi}}$**称为”VC置信”**。
关于风险边界有三个特征：
$P(\vec{x}, y)$的独立性；
计算左侧通常是不可能的；
如果我们知道VC维数，就可以很轻易的计算出右侧的值。
这样给定几个不同的学习机，选择一个固定的且相当小的 $\eta$ ，就可以选择能最小化右边式子的机器（函数），我们就可以给出实际风险最小边界的机器（函数）了。
支持向量机的VC维
在讲SVM的VC维之前，首先介绍一下影响置信风险的因素，这其中有：训练样本数目和分类函数的VC维。
因为训练样本数目，即样本越多，那么得到的误差又可以越小（置信风险就可以很小）；VC维越大，问题的解的种类就越多，推广泛化能力就越差，置信风险也就越大。因此增加样本数，降低VC维，才能降低置信风险。而一般的分类函数却需要提高VC维（即样本的特征数量），来降低经验风险，如多项式风雷函数。
结构风险最小化SRM就是同时兼顾经验风险和结构风险。在小样本情况下，能取得比较好的分类效果。**保证分类精度（经验风险）的同时，降低学习机器的VC维**。正因如此，SVM就是这样一种努力最小化结构风险的算法。
SVMs的泛化性能
这里引用一下维基百科介绍：在机器学习中，SVMs是具有相关学习算法的监督学习模型。它是用于分析分类和回归分析的数据的。而SVM的分类模型却可大致分成这四种：
最大边界分类器
使用核函数的分类器
软边缘分类器
软边缘 + 核函数分类器
可以发现，SVM既可以做线性分类，也可以做非线性分类，和线性回归等等，相较于逻辑回归、线性回归、决策树等模型，它的效果都是在它们之上的。
在sklearn中，是配有一个超参数C，来控制模型复杂度的。C越大，容忍度（泛化程度）越小，反之C越小，容忍度越高。而这个超参数C中，正是通过一个正则量，来控制SVM的泛化能力的，防止过拟合（一般使用grid search网格搜索，一种常用找最优超参数的算法）。
下面介绍SVM一些实现方法
LinearSVC
线性分类支持向量机，优点：简单 缺点：不支持核函数 复杂度：$O(m*n)$
最经典的就是手写体识别和鸢尾花识别
import numpy as np |
对于非线性数据的分类
无非两种处理方法：构造高维特征 和 构造相似度特征
- 使用高维空间特征：即映射高维空间上，利用Kernel思想
from sklearn.preprocessing import PolynomialFeatures |
这种核技巧可以极大地简化模型，不需要显式的处理高维特征，并且可以计算出较复杂的情况。但是模型越复杂，过拟合风险就越大，泛化性能就越差。
这里使用SVC（基于libsvm库，支持核函数，但是缺点是不能使用大规模数据，复杂度：$$O(m^2*n) - O(m^3*n)$$）
其中coef0参数表示：高次与低次权重
from sklearn.svm import SVC |
- 构造相似度特征：计算高斯距离（Gaussian RBF Kernel径向基函数）
高斯距离定义：
Gaussian RBF等式
$\phi \gamma (\mathbf{X},\iota )=exp(-\gamma \left || \mathbf{X},\iota |\right | ^2)$$\gamma$是用来控制高斯曲线形状的，对于数据点之间的距离才会发挥它应有的作用。
rbf_kernel_svm_clf = Pipeline(( |
上面分别展示了线性SVM、多项式核SVM、以及RBF核SVM的sklearn基本用法。但要真正理解SVM的内部机制并能在实际项目中灵活调参，还需要深入掌握以下核心知识点。
SVM 对偶问题推导（Dual Problem Derivation）
SVM的原始优化问题（Primal Problem）是一个带约束的凸优化问题。为了高效求解并引入核技巧，需要将其转化为对偶问题。
从原始问题到拉格朗日函数
对于线性可分SVM，原始问题为：
$$\min_{w,b} \frac{1}{2}\|w\|^2$$
$$\text{s.t. } y_i(w \cdot x_i + b) \geq 1, \quad i = 1,2,...,N$$
引入拉格朗日乘子 $\alpha_i \geq 0$，构造拉格朗日函数：
$$L(w, b, \alpha) = \frac{1}{2}\|w\|^2 - \sum_{i=1}^{N}\alpha_i[y_i(w \cdot x_i + b) - 1]$$
根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：
$$\max_{\alpha} \min_{w,b} L(w, b, \alpha)$$
求解 $\min_{w,b} L(w, b, \alpha)$
对 $w$ 和 $b$ 求偏导并令其为 0：
$$\frac{\partial L}{\partial w} = w - \sum_{i=1}^{N}\alpha_i y_i x_i = 0 \quad \Rightarrow \quad w = \sum_{i=1}^{N}\alpha_i y_i x_i$$
$$\frac{\partial L}{\partial b} = -\sum_{i=1}^{N}\alpha_i y_i = 0 \quad \Rightarrow \quad \sum_{i=1}^{N}\alpha_i y_i = 0$$
将 $w$ 代入拉格朗日函数，得到对偶问题：
$$\max_{\alpha} \sum_{i=1}^{N}\alpha_i - \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i \alpha_j y_i y_j (x_i \cdot x_j)$$
$$\text{s.t. } \sum_{i=1}^{N}\alpha_i y_i = 0, \quad \alpha_i \geq 0, \quad i = 1,2,...,N$$
KKT条件与支持向量识别
对偶问题的解必须满足KKT条件。对于原始问题，KKT条件为：
- Stationarity（平稳性）: $\nabla_w L = 0$, $\nabla_b L = 0$
- Primal feasibility（原始可行性）: $y_i(w \cdot x_i + b) \geq 1$
- Dual feasibility（对偶可行性）: $\alpha_i \geq 0$
- Complementary slackness（互补松弛性）: $\alpha_i[y_i(w \cdot x_i + b) - 1] = 0$
其中互补松弛条件是最关键的：当 $\alpha_i > 0$ 时，必须有 $y_i(w \cdot x_i + b) = 1$，即该样本点正好落在间隔边界上。这些样本点就是支持向量（Support Vectors）。绝大多数 $\alpha_i = 0$ 的样本点对决策边界没有贡献。
最终的决策函数可以只用支持向量表示：
$$f(x) = sign\left(\sum_{i \in SV}\alpha_i y_i (x_i \cdot x) + b\right)$$
对于软间隔SVM（引入松弛变量 $\xi_i$），对偶问题的唯一变化是约束条件变为 $0 \leq \alpha_i \leq C$，其中 $C$ 是惩罚参数。
SMO 算法（Sequential Minimal Optimization）
求解SVM对偶问题的最经典算法是SMO（序列最小最优化），由John Platt于1998年提出。其核心思想是：将大的二次规划（QP）问题分解为一系列最小的QP子问题（每次只优化两个变量），从而可以解析求解，避免了数值QP求解器的高昂开销。
算法动机
对偶问题有 $N$ 个变量 $\alpha_i$，且受等式约束 $\sum \alpha_i y_i = 0$。如果每次只优化一个变量，等式约束会迫使该变量无法改变。因此SMO每次选择两个变量 $\alpha_i$ 和 $\alpha_j$ 进行优化，固定其余所有变量。
两变量优化子问题
假设选定 $\alpha_1$ 和 $\alpha_2$ 进行优化，其余 $\alpha_k (k \geq 3)$ 固定。约束条件：
$$\alpha_1 y_1 + \alpha_2 y_2 = -\sum_{k=3}^{N}\alpha_k y_k = \zeta \quad \text{(常数)}$$
$$0 \leq \alpha_i \leq C \quad (i = 1,2)$$
由此可将 $\alpha_1$ 用 $\alpha_2$ 表示：$\alpha_1 = y_1(\zeta - \alpha_2 y_2)$。代入目标函数后，转化为关于 $\alpha_2$ 的单变量二次函数，可直接求解析解并裁剪到 $[L, H]$ 区间内。
裁剪边界求解：
若 $y_1 \neq y_2$：
- $L = \max(0, \alpha_2^{old} - \alpha_1^{old})$
- $H = \min(C, C + \alpha_2^{old} - \alpha_1^{old})$
若 $y_1 = y_2$：
- $L = \max(0, \alpha_2^{old} + \alpha_1^{old} - C)$
- $H = \min(C, \alpha_2^{old} + \alpha_1^{old})$
未裁剪的 $\alpha_2$ 更新公式：
$$\alpha_2^{new,unc} = \alpha_2^{old} + \frac{y_2(E_1 - E_2)}{\eta}$$
其中 $E_i = f(x_i) - y_i$ 是第 $i$ 个样本的预测误差，$\eta = K_{11} + K_{22} - 2K_{12}$（$K_{ij} = \kappa(x_i, x_j)$ 是核函数值）。
变量选择策略
SMO的性能高度依赖于变量选择策略：
**第一个变量 $\alpha_1$**：在所有违反KKT条件的样本中选择。KKT条件违反判据：$\alpha_i = 0$ 时 $y_i f(x_i) \geq 1$；$0 < \alpha_i < C$ 时 $y_i f(x_i) = 1$；$\alpha_i = C$ 时 $y_i f(x_i) \leq 1$。通常遍历所有支持向量候选（$0 < \alpha_i < C$）来找违反者。
**第二个变量 $\alpha_2$**：选择能使 $|E_1 - E_2|$ 最大化的变量，因为更新步长与误差差值的绝对值成正比。实践中维护一个误差缓存（Error Cache），从中选取使步长最大的 $\alpha_2$。
阈值 $b$ 的更新
优化 $\alpha_1, \alpha_2$ 后需更新阈值 $b$：
若 $0 < \alpha_1^{new} < C$：
$$b^{new} = b^{old} - E_1 - y_1(\alpha_1^{new} - \alpha_1^{old})K_{11} - y_2(\alpha_2^{new} - \alpha_2^{old})K_{12}$$
若 $0 < \alpha_2^{new} < C$，则使用对称公式。若两者都在边界上，则取两者的平均值。
收敛条件
SMO算法的收敛条件是所有 $\alpha_i$ 在给定容忍度 $\epsilon$（通常 $10^{-3}$）内满足KKT条件。即对任意 $i$：
- $\alpha_i < C \Rightarrow y_i f(x_i) \geq 1 - \epsilon$
- $\alpha_i > 0 \Rightarrow y_i f(x_i) \leq 1 + \epsilon$
算法复杂度
SMO每次迭代的计算代价主要在于更新误差缓存，复杂度为 $O(N)$。实际运行中，SMO的迭代次数通常介于此间，总体经验复杂度约为 $O(N^2)$，远优于通用QP求解器的 $O(N^3)$。
核方法深度剖析（Kernel Methods Deep Dive）
核方法是SVM能够处理非线性问题的核心武器。其数学基础是Mercer定理：任何半正定核函数都对应某个特征空间中的内积。
Mercer 条件
对于对称函数 $\kappa: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$，它是有效核函数的充要条件是：对任意有限样本集 ${x_1,…,x_n}$，其Gram矩阵 $\mathbf{K}_{ij} = \kappa(x_i, x_j)$ 是半正定的。满足Mercer条件的核函数隐含地定义了一个再生核希尔伯特空间（RKHS），其中 $\kappa(x_i, x_j) = \langle \phi(x_i), \phi(x_j) \rangle$。
RBF 核参数分析
RBF（径向基函数）核是最常用的核函数：
$$\kappa(x_i, x_j) = \exp(-\gamma \|x_i - x_j\|^2)$$
$\gamma$ 参数对决策边界的影响：
- $\gamma$ 很大（如 $\gamma = 100$）：每个支持向量的影响范围极小，决策边界会高度弯曲以紧密拟合每个训练点 → 过拟合风险极高。此时RBF核近似于1-NN分类器。
- $\gamma$ 很小（如 $\gamma = 0.01$）：每个支持向量的影响范围极大，决策边界趋近于线性 → 欠拟合风险。极端情况下RBF-SVM退化为线性SVM。
- $\gamma$ 适中：在拟合能力和泛化能力之间取得平衡。
$\gamma$ 的经验选择：通常设置 $\gamma = 1/d$（$d$ 为特征维度），或通过GridSearch从 ${10^{-3}, 10^{-2}, …, 10^{3}}$ 中对数均匀采样。
RBF核的VC维：RBF核对应无穷维特征空间，其VC维理论上可以无穷大。但实际中通过最大化间隔（相当于最小化 $|w|^2$）实现了正则化，使得有效VC维被控制。
多项式核参数分析
$$\kappa(x_i, x_j) = (\gamma x_i^T x_j + r)^d$$
- **degree $d$**：控制决策边界的复杂度。$d=1$ 退化为线性核；$d=2$ 可拟合二次曲面；$d$ 过高会剧烈过拟合。
- **coef0 $r$**：控制高阶项与低阶项的相对权重。$r$ 越大，低阶项权重越大，模型倾向于更平滑。
- **$\gamma$**：缩放因子，控制内积的尺度。
多项式核的劣势：当 $d$ 较大或特征维度较高时，数值计算容易溢出或出现极端值（因为内积的 $d$ 次幂）。与RBF核相比，多项式核在大多数实际场景中表现不如RBF核，因为RBF核具有局部性好、数值稳定性高的优势。
如何选择核函数
一个实用的决策流程：
- 特征数远大于样本数（如文本分类，n_features >> n_samples）：使用线性核。此时数据在高维空间中很可能线性可分，使用非线性核容易过拟合。
- 特征数和样本数都适中（如典型的表格数据）：优先尝试RBF核。RBF核是最通用、表现最稳健的非线性核。
- 样本数远大于特征数：可以考虑RBF核，但需要注意训练复杂度 $O(N^2)$ 对大规模数据的压力。可以先尝试线性SVM作为baseline。
- 特征具有特殊结构（如字符串、图、序列）：使用对应的专用核——string kernel、graph kernel、Fisher kernel等。
经验法则：永远先试线性核（快、可解释），再用RBF核作为非线性baseline。多项式核和sigmoid核很少在实际中超越RBF核。
常用核函数速查表
| 核函数 | 数学形式 | 适用场景 |
|---|---|---|
| Linear | $x_i^T x_j$ | 高维稀疏数据（文本）、线性可分 |
| RBF | $\exp(-\gamma|x_i-x_j|^2)$ | 通用非线性（首选） |
| Polynomial | $(\gamma x_i^T x_j + r)^d$ | 图像（有时）、低维多项式关系 |
| Sigmoid | $\tanh(\gamma x_i^T x_j + r)$ | 历史遗留，实际很少用 |
多分类 SVM 策略（Multi-class SVM Strategies）
SVM原生是二分类器。将SVM扩展到多分类有以下几种策略：
一对其余（One-vs-Rest, OvR）
训练 $K$ 个二分类器（$K$ 为类别数），第 $k$ 个分类器将第 $k$ 类视为正类，其余视为负类。预测时选择决策函数值最大的类别：
$$\hat{y} = \arg\max_k (w_k^T x + b_k)$$
- 训练复杂度：$K$ 个二分类器，每个使用全部 $N$ 个样本
- 优点：实现简单，分类器数量线性增长
- 缺点：每个分类器面临严重类别不平衡（正类约 $N/K$，负类约 $N(K-1)/K$），可能影响边界的准确性
一对一（One-vs-One, OvO）
为每对类别 $(i, j)$ 训练一个二分类器，共 $K(K-1)/2$ 个。预测时采用投票机制：每个分类器对样本投票给 $i$ 类或 $j$ 类，最终得票最多的类别胜出。
- 训练复杂度：$K(K-1)/2$ 个分类器，但每个只使用两个类的样本（约 $2N/K$）
- 优点：单个分类器规模小、训练快；scikit-learn 的
SVC默认使用此策略 - 缺点：分类器数量随 $K$ 二次增长，$K$ 大时不可行；存在平票情况
DAG-SVM（有向无环图SVM）
Platt等人提出。训练阶段与OvO相同，共 $K(K-1)/2$ 个分类器。预测阶段使用一个有向无环图：从根节点开始，每次排除一个类别，经过 $K-1$ 次比较后到达叶子节点。
- 预测速度：只需 $K-1$ 次分类器评估（OvO需要 $K(K-1)/2$ 次）
- 缺点：预测结果依赖DAG的节点排列顺序，存在误差累积风险
Crammer-Singer 多分类SVM
Crammer和Singer（2001）提出了原生多分类SVM公式，同时学习 $K$ 个超平面 ${w_1, …, w_K}$：
$$\min_{w,\xi} \frac{1}{2}\sum_{k=1}^{K}\|w_k\|^2 + C\sum_{i=1}^{N}\xi_i$$
$$\text{s.t. } w_{y_i}^T x_i - w_k^T x_i \geq 1 - \delta_{y_i,k} - \xi_i, \quad \forall i,k$$
- 训练复杂度：$O(K \cdot N^2)$，一个QP问题包含所有类别
- 优点：理论上更优雅，单一优化目标
- 缺点：实现复杂度高，大规模不可行
各策略复杂度对比
| 策略 | 分类器数量 | 训练样本/分类器 | 预测评估次数 | scikit-learn |
|---|---|---|---|---|
| OvR | $K$ | $N$ | $K$ | OneVsRestClassifier(SVC()) |
| OvO | $K(K-1)/2$ | $\approx 2N/K$ | $K(K-1)/2$ | SVC(decision_function_shape='ovo') |
| DAG-SVM | $K(K-1)/2$ | $\approx 2N/K$ | $K-1$ | 需自行实现 |
| Crammer-Singer | 1（联合） | $N$ | $K$ | 需自行实现 |
实际建议：对于大多数中小规模多分类任务，scikit-learn 默认的 OvO 表现稳定。当 $K > 10$ 时，OvR 更优先（因为 OvO 的分类器数量会爆炸到 45+ 个）。
完整 sklearn 实战流程（Practical sklearn Workflow）
以下展示一个完整的SVM分类器构建流程，包括数据预处理、特征缩放、超参数调优和模型评估。
完整 Pipeline 示例
import numpy as np |
为什么特征缩放对SVM至关重要
SVM的优化目标是最小化 $|w|^2$，这对特征尺度高度敏感。如果特征 $x_1$ 的范围是 $[0, 1]$ 而 $x_2$ 是 $[0, 10000]$，则 $x_2$ 将主导 $|w|$ 的计算，导致决策边界被少数特征劫持。StandardScaler 将每个特征标准化为 $\mu=0, \sigma=1$，确保所有特征在优化过程中被平等对待。
超参数调优建议
- C 参数：控制对误分类的惩罚。$C$ 越小 → 间隔越大 → 模型越简单（正则化更强）。典型的搜索范围：${10^{-3}, 10^{-2}, …, 10^{3}}$。
- $\gamma$ 参数（RBF核）：控制单个样本的影响半径。$\gamma$ 越大 → 决策边界越复杂。与 $C$ 存在交互效应：大 $C$ + 大 $\gamma$ 极易过拟合。
- GridSearch 策略：建议先做粗粒度搜索（如 ${0.01, 1, 100}$）定位大致范围，再做细粒度搜索。对大规模数据优先使用
RandomizedSearchCV。 - 交叉验证：对于类别不均衡数据，使用
StratifiedKFold确保每折的类别比例与原始数据一致。
SVM 与其他分类器的对比
详细对比表
| 维度 | SVM | Logistic Regression | Random Forest | Neural Networks |
|---|---|---|---|---|
| 决策边界 | 最大间隔超平面（可非线性） | 线性决策边界 | 分段常数（轴平行） | 任意复杂曲面 |
| 可解释性 | 中等（支持向量） | 高（特征系数即odds比） | 中高（特征重要性） | 低（黑箱） |
| 小样本表现 | 优秀（SRM原理） | 一般 | 较差 | 差 |
| 高维数据 | 优秀（核技巧+最大化间隔） | 一般（需要正则化） | 一般（维度诅咒） | 好（需要大量数据） |
| 训练速度 | 慢（$O(N^2) - O(N^3)$） | 快（$O(ND)$） | 中等 | 极慢（GPU加速后快） |
| 预测速度 | 中等（取决于支持向量数） | 极快 | 中等 | 快 |
| 超参数调优 | 中等（C, $\gamma$, 核选择） | 少 | 中等 | 多（架构+优化器） |
| 处理缺失值 | 需预处理 | 需预处理 | 天然支持 | 需预处理 |
| 类别不平衡 | 可用类别权重 | 可用类别权重 | 可用类别权重 | 可用类别权重 |
| 概率输出 | Platt scaling | 原生 | 投票比例 | 原生（softmax） |
| 最优场景 | 小到中型、高维、需要强泛化 | 需要概率+可解释的baseline | 表格数据、特征工程有限 | 海量数据、图像/语音/文本 |
何时SVM优于其他模型
- 小样本高维数据：如基因表达分类（n_samples < 1000, n_features > 10000），SVM的间隔最大化和SRM原则效果显著。
- 需要强理论保证：SVM的凸优化保证全局最优解（神经网络只有局部最优）。
- 非线性边界但数据量中等：RBF核SVM在几千到几万样本的场景下表现优异，且调参比神经网络简单。
- 文本分类：线性SVM在TF-IDF特征上长期是文本分类的SOTA baseline。
何时SVM不如其他模型
- 超大规模数据（$N > 10^5$）：训练复杂度 $O(N^2)$ 变得不可接受，此时随机森林或线性模型（如LibLinear）更合适。
- 需要概率校准：虽然可以通过Platt scaling获取概率，但不如logistic regression原生。
- 在线学习/增量更新：SVM不支持增量学习（需要重新训练），此时用SGDClassifier更合适。
SVM 在现代场景中的发展（SVM in Modern Context）
大规模线性SVM：LibLinear
Fan等人（2008）提出的LibLinear专门针对大规模线性分类优化，其核心是坐标下降法（Coordinate Descent），每次只优化一个 $\alpha_i$（对线性SVM而言，不需要保证等式约束的两个变量联动）。配合L1/L2正则化和dual/primal求解器的自适应选择，LibLinear可以在百万级样本上秒级完成训练。scikit-learn中的 LinearSVC 底层即基于LibLinear。
近似核方法
对于非线性SVM，传统核矩阵计算和存储为 $O(N^2)$，这在大规模场景下不可接受。两类重要的近似方法：
Nystrom 方法：随机采样 $m \ll N$ 个样本，计算 $m \times m$ 的核矩阵和 $N \times m$ 的交叉核矩阵，用低秩近似逼近完整的 $N \times N$ 核矩阵：$\mathbf{K} \approx \mathbf{K}{nm} \mathbf{K}{mm}^{-1} \mathbf{K}_{mn}$。复杂度降为 $O(Nm^2)$。
随机傅里叶特征（Random Fourier Features, RFF）：Rahimi和Recht（2007）基于Bochner定理，将RBF核近似为显式的随机傅里叶特征映射：
$$\kappa_{RBF}(x_i, x_j) \approx \frac{1}{D}\sum_{d=1}^{D}\cos(\omega_d^T x_i + b_d)\cos(\omega_d^T x_j + b_d)$$
其中 $\omega_d \sim \mathcal{N}(0, 2\gamma I)$，$b_d \sim \mathcal{U}[0, 2\pi]$，$D$ 为傅里叶特征维度（通常 $D = 500 \sim 2000$）。这等价于先在 $D$ 维的随即空间中做显式映射，再训练线性SVM，完美避开了核矩阵计算。
SVM vs Deep Learning：什么场景下SVM依然更优？
- 数据量有限（$N < 10000$）：深度学习需要大量数据才能展现优势，SVM在小样本下有理论保证。
- 特征已手工提取：当使用SIFT、TF-IDF等经过验证的手工特征时，SVM往往优于端到端的深度学习。
- 可解释性要求高：SVM的支持向量和决策边界可以被几何解释。
- 满足于凸优化保证：在某些安全关键领域（医疗、金融），凸优化带来的全局最优保证比深度学习的黑箱更受青睐。
- 计算资源受限：在边缘设备上进行离线训练时，SVM的算力需求远低于深度学习。
总结
要说SVM的这篇论文阐述的知识，确实可以称得上是”细致入微”，而SVM的优势就在于解决小样本、非线性、以及高维的回归和二分类问题。在与问题复杂度上，SVM要求的样本是相对较少的；而在样本数据线性不可分上，SVM也是比较擅长的，通过核函数和松弛变量来实现；即使在样本维度很高情况下，SVM依然保持着优势，它产生的分类器简洁，用到样本信息还少，几乎可以有效的避免过拟合问题。基于种种，接下来还是需要结合实战，再配备这篇教程，好好体验一下SVM的强大。
面试常见问题（Interview Q&A）
Q1: 为什么SVM要最大化间隔？间隔最大化与泛化能力之间有什么关系？
答：最大化间隔（Margin Maximization）是SVM最核心的设计思想。根据统计学习理论中的泛化误差界，对于一个能够以间隔 $\rho$ 正确分类所有训练样本的分类器，其期望泛化误差上界与 $\sqrt{h/\rho^2}$ 成正比（$h$ 为VC维）。因此，更大的间隔等价于更紧的泛化误差界，即更好的泛化能力。
几何直觉：间隔是决策边界到最近样本点的距离。间隔越大，意味着允许更多的噪声/扰动出现在样本中而不会导致误分类。极端情况下，一个间距为零的分类器（如过拟合的多项式边界），数据点稍有扰动就可能被分错。
从优化角度看，最小化 $|w|^2$ 等价于最大化间隔 $2/|w|$，这天然构建了结构风险最小化的框架——在保证经验风险为零（或很小）的前提下，最小化模型容量（限制VC维）。
Q2: 为什么SVM对偶问题中的 $\alpha$ 大多是0？只有支持向量才有 $\alpha > 0$？
答：这由KKT条件的互补松弛性（Complementary Slackness）解释：$\alpha_i[y_i(w \cdot x_i + b) - 1] = 0$。
对于非支持向量，$y_i(w \cdot x_i + b) > 1$（样本落在间隔之外），要满足等式，必须 $\alpha_i = 0$。只有恰好落在间隔边界上的样本（$y_i(w \cdot x_i + b) = 1$）才允许 $\alpha_i > 0$。对于软间隔SVM，$\alpha_i = C$ 的样本是误分类或在间隔内的点。
这个性质有重要的实际意义：SVM的解是稀疏的——预测时只需要计算与支持向量的核函数值，不需要使用全部训练样本。通常支持向量只占总训练样本的一小部分（5%～20%），大大加速了预测。同时，这也意味着SVM天然进行了一种样本选择。
Q3: RBF核的 $\gamma$ 参数和正则化参数 $C$ 分别控制什么？两者如何交互影响模型？
答：
- $C$（正则化参数倒数）：控制模型对误分类的容忍度。$C$ 越大，惩罚越重 → 模型越复杂 → 过拟合风险越高。$C$ 越小，允许更多误分类 → 模型越简单（更大间隔）→ 可能欠拟合。
- $\gamma$（RBF核宽度倒数）：控制每个训练样本的影响范围。$\gamma$ 越大 → 影响范围越小（高斯曲线越窄）→ 决策边界越复杂 → 过拟合。$\gamma$ 越小 → 影响范围越大 → 决策边界越平滑 → 欠拟合。
交互效应：$C$ 和 $\gamma$ 有倍增效应。大 $C$ + 大 $\gamma$ = 极度过拟合（每个样本都有自己的小岛）。小 $C$ + 小 $\gamma$ = 极度欠拟合（近似线性）。正确的调参策略是联合搜索（如GridSearchCV中的笛卡尔积搜索），因为最优的 $C$ 通常与 $\gamma$ 强相关。
Q4: 线性可分SVM的对偶问题中的等式约束 $\sum_{i=1}^{N}\alpha_i y_i = 0$ 的物理含义是什么？
答：这个等式约束来源于拉格朗日函数对偏置 $b$ 求偏导并令其为0的结果：
$$\frac{\partial L}{\partial b} = -\sum_{i=1}^{N}\alpha_i y_i = 0$$
物理上，这个约束确保了正负类支持向量的总权重相等，即决策边界不会向某一类偏移。它是SVM解的对称性保证。没有了这个约束，对偶问题的最优解将不对应于原始问题的最优解。在SMO算法中，这个约束是每次必须选择两个变量同时更新的根本原因——如果只更新一个 $\alpha_i$，等式约束将被破坏。
Q5: 如何处理SVM中的类别不平衡问题？
答：有多种策略：
类别权重（class_weight）：scikit-learn中设置
class_weight='balanced'，自动按类别样本数反比设置不同的 $C$ 值：少数类的 $C_{minor} = C \times \frac{N_{total}}{K \times N_{minor}}$。这使得少数类的误分类惩罚更大，从而拉回决策边界。重采样：对少数类进行SMOTE过采样或对多数类进行欠采样。
调整决策阈值：训练后在预测时调低少数类的决策阈值。
评估指标选择：不使用准确率（Accuracy），而使用F1-score、AUC-ROC、Precision-Recall曲线。
Q6: 为什么在文本分类中，即使特征维度很高，线性SVM也能取得很好的效果？
答：文本分类经TF-IDF或词袋模型编码后，特征维度通常达到 $10^4 \sim 10^6$ 级别，远超样本数。在这种”高维稀疏”场景下：
- 数据在高维空间中天然趋向于线性可分——Cover定理表明，将数据非线性投影到更高维空间后会变得更可分。
- 虽然维度极高，但有效特征（非零特征）很少，每篇文档通常只有几十到几百个词出现。
- 线性SVM复杂度为 $O(N \times d)$（$d$ 为特征维度），对于稀疏矩阵的优化已高度成熟（LibLinear的坐标下降法可秒级处理百万维特征）。
- 额外使用非线性核（如RBF）反而可能在高维稀疏空间过拟合，且计算成本不值得。
事实上，在BERT等预训练模型出现之前，线性SVM + TF-IDF 一直是文本分类的工业标准baseline。
Q7: SMO算法为什么每次必须选择两个变量进行优化？
答：因为对偶问题中的等式约束 $\sum \alpha_i y_i = 0$。如果只选一个变量 $\alpha_i$ 更新，要保持等式约束成立，则 $\alpha_i^{new} y_i = \alpha_i^{old} y_i$，即 $\alpha_i^{new} = \alpha_i^{old}$（因为 $y_i \in {\pm 1}$）。这意味着只优化一个变量时它根本无法改变，算法将停滞。选择两个变量后，可以通过一个变量补偿另一个的变化来满足等式约束：$\alpha_1^{new}y_1 + \alpha_2^{new}y_2 = \alpha_1^{old}y_1 + \alpha_2^{old}y_2$。这正是”最小优化”——两个是可以优化的最少变量数。
