Skip to content

支持向量机 (SVM) ​

WARNING

🧪 Beta公测版本提示:教程主体已完成,正在优化细节,欢迎大家提Issue反馈问题或建议。

能分开的直线有无数条,SVM 挑最宽那条马路。demo.py 用 SGD + hinge 实现线性 SVM(C 扫几档),再用 sklearn 的 RBF 看 γ。几何间隔 2/∥w∥ 与对偶里的内积,推导在折叠中。

1. 最大间隔分类器 ​

1.1 线性可分情况下的直觉 ​

支持向量机(Support Vector Machine, SVM)的核心思想是:在能正确分类的所有超平面中,找一个离两类数据都"最远"的超平面。

对于线性可分数据集,存在无穷多个分类超平面。但哪个是最好的?SVM 的答案是:最大化**间隔(margin)**的那个。

数学上,分类超平面定义为:

wTx+b=0

其中 w 是法向量(垂直于超平面),b 是偏置。点到超平面的距离为:

|wTx+b|∥w∥2

将正类标签设为 yi=+1,负类标签设为 yi=−1,则分类正确意味着 yi(wTxi+b)>0。

1.2 硬间隔 SVM 的优化问题 ​

几何间隔(Geometric Margin)定义为所有样本点到超平面的最小距离:

γ=miniyi(wTxi+b)∥w∥

SVM 的目标是最大化这个最小间隔:

maxw,b1∥w∥s.t.yi(wTxi+b)≥1,∀i

约束条件 yi(wTxi+b)≥1 保证了所有样本被正确分类且距离超平面至少为 1/∥w∥。落在等号上的样本点就是支持向量(Support Vectors)——它们是距离超平面最近的样本,也是唯一影响 w 和 b 的点。

等价地,可以写成更常见的凸二次规划形式:

minw,b12∥w∥2s.t.yi(wTxi+b)≥1,∀i

最大间隔分类器示意图:展示分类超平面、两个间隔边界(+1 和 -1)、支持向量(圈出)、以及间隔宽度 2/||w||

图解说明:中间实线 w⊤x+b=0,虚线 ±1。只有踩在虚线上的点(支持向量)真正决定 w。马路宽 2/∥w∥。

数字例。 正类 (1,1)、(2,2),负类 (−1,−1)。对称解 w∝(1,1)。约束 yi(w⊤xi+b)≥1 在最近点取等。∥w∥ 越小马路越宽。C→∞ 时 demo 近似硬间隔;C=0.01 时允许点掉进间隔里,边界更钝。

逐步推导:从「最大化间隔」到 min12∥w∥2 与对偶(点击展开)

点到平面距离 |w⊤x+b|/∥w∥。令所有点满足 y(w⊤x+b)≥1(这是缩放自由度:(w,b) 与 (2w,2b) 是同一平面,把最小函数间隔钉成 1)。于是几何间隔 =1/∥w∥,最大化它 ⇔ 最小化 12∥w∥2。

拉格朗日 L=12∥w∥2−∑iαi[yi(w⊤xi+b)−1]。∂wL=0 给出 w=∑iαiyixi;∂bL=0 给出 ∑iαiyi=0。代回去只剩 α 和对 xi⊤xj 的依赖——换成 K(xi,xj) 就是核技巧,不必写出 ϕ(x)。

Hinge:max(0,1−yf)。yf≥1 时子梯度对 w 只有正则项 w(demo 里 2*lambda_*w);掉进间隔或分错才累加 −yx。这就是 LinearSVM.fit 的 if/else。

1.3 对偶问题与 KKT 条件(几何直觉) ​

通过拉格朗日乘子法,原始问题可以转换为对偶问题。引入拉格朗日乘子 αi≥0:

L(w,b,α)=12∥w∥2−∑i=1nαi[yi(wTxi+b)−1]

对 w 和 b 求导并令其为零,得到:

w=∑i=1nαiyixi,∑i=1nαiyi=0

代入拉格朗日函数,得到对偶问题:

maxα∑i=1nαi−12∑i=1n∑j=1nαiαjyiyjxiTxjs.t.αi≥0,∑i=1nαiyi=0

KKT 互补松弛条件告诉我们:

  • 若 αi=0:样本 i 不是支持向量,不影响决策
  • 若 αi>0:样本 i 是支持向量,满足 yi(wTxi+b)=1

这就是"支持向量机"名字的由来——决策只由少数支持向量决定,与其他样本无关。

为什么使用对偶形式?

  1. 对偶问题中样本仅以内积 xiTxj 的形式出现——这为核技巧(Kernel Trick)打开了大门
  2. 对偶问题的变量数 = n(样本数),原始问题的变量数 = d(特征维数)。当 d≫n 时,对偶问题更高效

2. 软间隔 SVM ​

2.1 松弛变量与惩罚参数 C ​

现实数据很少完全线性可分。软间隔 SVM(Soft Margin SVM)允许一些样本违反间隔约束,但对此施加惩罚。

引入松弛变量(Slack Variables)ξi≥0,表示样本 i 违反间隔的程度:

minw,b,ξ12∥w∥2+C∑i=1nξis.t.yi(wTxi+b)≥1−ξi,ξi≥0,∀i

其中 C>0 是惩罚参数(Regularization Parameter),控制间隔最大化与分类错误容忍度之间的权衡:

  • C 很大(如 106):对错误的惩罚很重,模型近似硬间隔 SVM,容易过拟合
  • C 很小(如 0.01):允许更多错误,间隔更大,模型更简单

C 是 SVM 最重要的超参数,通常通过交叉验证选择。把本节求和目标除以 Cn>0,得到平均 hinge 损失加 λ∥w∥2,其中 λ=1/(2Cn)。demo.py 的单样本 SGD 使用这个系数,与 SVC 保持同一 C 约定;C 必须有限且严格为正。固定步长、有限轮数的 SGD 不保证已经达到 SVC 的最优解。

软间隔 SVM:展示松弛变量 ξ_i 的含义——正确分类但落在间隔内的点 vs 错误分类的点,对比不同 C 值的决策边界

2.2 从 Hinge Loss 角度理解 ​

SVM 的原始问题等价于以下无约束优化问题:

minw,b12∥w∥2+C∑i=1nmax(0,1−yi(wTxi+b))

其中 max(0,1−yi(wTxi+b)) 就是 Hinge Loss(合页损失)。

Hinge Loss 的特点:

  • 当 yi(wTxi+b)≥1(正确分类且超出间隔),损失为 0
  • 当 0<yi(wTxi+b)<1(正确分类但在间隔内),损失为 1−yi(wTxi+b)
  • 当 yi(wTxi+b)≤0(错误分类),损失为 1+|wTxi+b|(线性增长)

与 logistic regression 的交叉熵损失相比,Hinge Loss 对"有把握的"正确分类不产生损失,更加稀疏。

这个视角对于使用 SGD 优化 SVM 非常有用——可以直接对 Hinge Loss + L2 正则化做梯度下降,避免了二次规划的复杂性。


3. 核技巧(Kernel Trick) ​

3.1 动机:线性不可分问题 ​

现实中的很多分类问题是非线性可分的(如 XOR 问题、同心圆数据)。一种思路是将数据映射到高维空间,使数据在新空间中线性可分。

例如,原始二维空间中的 XOR 问题在线性 SVM 下无法解决,但映射到 ϕ(x1,x2)=(x1,x2,x1x2) 三维空间后就是线性可分的。

3.2 核函数的定义 ​

核函数 K(xi,xj) 直接计算高维空间中两个样本的内积,而不需要显式地做特征映射:

K(xi,xj)=⟨ϕ(xi),ϕ(xj)⟩

注意 SVM 的对偶形式中,样本仅以 xiTxj 形式出现。将 xiTxj 替换为 K(xi,xj),SVM 就自动在高维隐空间中学习,而不需要显式计算 ϕ(x)。

3.3 常用核函数 ​

线性核(Linear Kernel):

K(xi,xj)=xiTxj

不做任何变换,等价于原始的线性 SVM。适用于特征维度高、样本量大的情况(如文本分类)。

多项式核(Polynomial Kernel):

K(xi,xj)=(γxiTxj+r)d

参数 d 为多项式的次数,控制特征交互的阶数。d=1 退化为线性核,d=2 产生所有二阶交互特征。

RBF / 高斯核(Radial Basis Function):

K(xi,xj)=exp⁡(−γ∥xi−xj∥2)

最常用的非线性核。参数 γ 控制每个训练样本的"影响半径":

  • γ 大:每个支持向量的影响范围小,决策边界复杂(容易过拟合)
  • γ 小:影响范围大,决策边界平滑(容易欠拟合)

RBF 核将数据映射到无限维空间(泰勒展开可知),但它极其灵活,几乎可以拟合任何决策边界——前提是选好 C 和 γ。

核的选择:

核函数公式适用场景关键参数
线性xiTxj高维稀疏数据(文本)—
多项式(γxiTxj+r)d已知特征交互阶数d
RBFexp⁡(−γ|xi−xj|2)一般非线性问题(首选)γ
Sigmoidtanh⁡(γxiTxj+r)神经网络类比γ,r

三种核函数对比:线性核(直线边界)、多项式核(曲线边界)、RBF 核(复杂曲线边界),展示对同一非线性可分数集的拟合效果

3.4 Mercer 条件 ​

不是任意二元函数都可以作为核函数。Mercer 定理指出:一个函数 K(x,y) 是合法核函数,当且仅当对于任意有限样本集,其 Gram 矩阵 Kij=K(xi,xj) 是半正定的。

在实践中,常用的核函数(线性、多项式、RBF、Sigmoid)都满足 Mercer 条件,可以放心使用。


4. 从零实现线性 SVM(Hinge Loss + SGD) ​

4.1 核心思路 ​

使用 Hinge Loss + L2 正则化的形式,通过 SGD 优化:

python
class LinearSVM:
    def fit(self, X, y):
        for epoch in range(n_epochs):
            for each sample (x_i, y_i):
                if y_i * (w^T x_i + b) < 1:  # 违反间隔
                    grad_w = 2 * lambda_ * w - y_i * x_i
                    grad_b = -y_i
                else:  # 在间隔外
                    grad_w = 2 * lambda_ * w
                    grad_b = 0
                w -= lr * grad_w
                b -= lr * grad_b

4.2 梯度推导 ​

Hinge Loss 对 w 的子梯度:

∂max(0,1−y(f(x)))∂w={−yxif y⋅f(x)<10otherwise

加上 L2 正则化项:总梯度 = 2λw + Hinge Loss 梯度。

4.3 支持向量的识别 ​

训练完成后,支持向量可以通过以下条件识别:

python
margin = y_i * (w^T x_i + b)
sv_mask = margin <= 1.01  # 软间隔候选集,包含间隔内部与误分类点
# 或使用对偶变量: alpha_i > 0 的样本

软间隔不能只保留间隔边界上的点。KKT 条件为 αi(mi−1+ξi)=0、(C−αi)ξi=0,其中 mi=yif(xi)。若 mi<1,则 ξi=1−mi>0,所以 αi=C>0;这些误分类或间隔内部点也是支持向量。只有 0<αi<C 才必有 mi=1。SGD 没有直接输出对偶系数,margin <= 1.01 只是含容差的可视化候选集,不能替代精确的 αi>0 判定。

复现说明。 核对比先划分数据,再仅在训练集拟合标准化参数,避免测试集泄漏;支持向量候选与 C 缩放已修正,相关输出图片尚未重新生成。

对照 demo.py。 线性可分点云上 C=105 近似硬间隔,支持向量少、马路宽。C 减小后更多点掉进间隔。moons/circles 上线性核失败,RBF 能弯。γ 过大决策岛碎成一块块。卡点:标签必须是 ±1 不是 {0,1},否则 hinge 的 y⋅f 符号全错。



本章总结 ​

概念公式/描述关键点
最大间隔max1/|w| s.t. yi(wTxi+b)≥1选择离数据最远的超平面
支持向量αi>0 的样本唯一影响决策的训练样本
对偶问题maxα∑αi−12∑αiαjyiyjxiTxj仅以内积形式出现
KKT 条件αi(yifi−1+ξi)=0,(C−αi)ξi=0软间隔包含间隔违例支持向量
松弛变量ξi≥0允许违反间隔
惩罚参数 CC∑ξiC 大 → 硬间隔;C 小 → 软间隔
Hinge Lossmax(0,1−yf(x))SGD 可优化形式
核函数K(xi,xj)=⟨ϕ(xi),ϕ(xj)⟩隐式高维映射
RBF 核exp⁡(−γ|xi−xj|2)最常用非线性核,无限维
Mercer 条件Gram 矩阵半正定核函数的合法性判定

参考 ​

  1. Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine Learning, 20(3), 273-297. DOI: 10.1007/BF00994018
  2. Boser, B. E., Guyon, I. M., & Vapnik, V. N. (1992). A training algorithm for optimal margin classifiers. COLT '92, 144-152. DOI: 10.1145/130385.130401
  3. Scholkopf, B., & Smola, A. J. (2002). Learning with Kernels. MIT Press. ISBN: 9780262194754
  4. Burges, C. J. C. (1998). A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 2(2), 121-167. DOI: 10.1023/A:1009715923555
  5. Cristianini, N., & Shawe-Taylor, J. (2000). An Introduction to Support Vector Machines. Cambridge University Press. DOI: 10.1017/CBO9780511801389
  6. Hsu, C. W., Chang, C. C., & Lin, C. J. (2003). A practical guide to support vector classification. Technical Report, National Taiwan University. Link
  7. Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer. DOI: 10.1007/978-0-387-45528-0 第 7 章
  8. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed.). Springer. DOI: 10.1007/978-0-387-84858-7 第 12 章

📥 Code ​

上一章: ml03 朴素贝叶斯 ​

下一章: ml05 决策树 ​