之前写过一篇关于SVM的文章，但是不够详细，推导过程和思路有些混乱，有些知识忽略了。在阿里云的机器学习算法详解课程中又遇到了这个知识点，感觉讲得很清晰，很有条理，所以写了这篇文章，尽可能将SVM的原理和推导过程讲明白，一些较难的部分课程中没有证明，但不影响使用SVM。本文第一章介绍了支持向量机的原理与问题转化，涉及简单的数学推导。第二章介绍了不等式约束条件下求极值的方法，涉及高等数学的知识，有一定难度；如果看明白最好，可以为以后解决问题提供思路，但是看不明白也不影响SVM的使用。第三章介绍了SVM分类超平面。第四章介绍了核函数与松弛变量。

---

---

1. 支持向量机（SVM）

1.1 SVM 简介

SVM主要应用于模式识别领域，具有坚实的统计学理论基础，也就是VC-Dimention和结构化风险最小。

对于一个线性可分的数据集，定义样本到分割超平面的最短距离为间隔。间隔越大，分割超平面对两个类别的划分越稳定，不容易受噪声影响。支持向量机的目标即寻找间隔最大的超平面。那么，可以决定分隔平面划分的关键样本点，就是支持向量。支持向量机就是一种寻找一个最优的分类器来划分最大的超平面的算法。

如图所示，左图中有两类数据（红圈和蓝三角），三条线是对两类数据的划分超平面（根据超平面的定义知，二维空间，超平面是一维，即直线）。右图中，假设白色实线是分割超平面，并且到两条虚线的距离相等，定义直线到虚线的距离为d，两条虚线之间的距离定义为margin。若能使得图中两条虚线的间隙（margin）最大，即可保证分类器具有最优的性能。SVM就是根据margin最大去找最大分隔超平面（分割直线）的过程。落在margin（虚线）上的样本点就是支持向量。

假设右图中的白实线（两条虚线之间的中心线）的方程为向量 $\omega·x + b = 0$ω⋅x+b=0。则另外两条虚线的方程分别为：$\omega·x + b = 1$ω⋅x+b=1（左上），$\omega·x + b = -1$ω⋅x+b=−1（右下）。why？

• 假设左上的虚线方程为 $\omega·x + b = c$ω⋅x+b=c（ $c$c 为非零常数）
• 方程两边同时除以 $c$c，则有:
• $\frac{w}{c}·x + \frac{b}{c} = 1$cw​⋅x+cb​=1
• 令 $\frac{w}{c} = w$cw​=w，$\frac{b}{c} = b$cb​=b，则有
• $w·x + b = 1$w⋅x+b=1
• 同理可推知知 $w·x + b = 0$w⋅x+b=0 和 $w·x + b = -1$w⋅x+b=−1。

其实这里对两条虚线中方程中的 $1$1 或者 $-1$−1 可以设为任意非零常数，两条虚线的方程互换有没有问题，只是为了计算方便。

---

1.2 SVM 问题分析

先明确 **超平面（Hyperplane）**的定义：

• 超平面：指n维线性空间中维度为n-1的子空间。它可以把线性空间分割成不相交的两部分。
• 比如，二维空间中，把平面分成了两部分的直线（一维）是超平面；三维空间中，把空间分成了两部分的平面（二维）是超平面。
• 法向量：垂直于超平面的向量。
  
  注意法向量 $w^T$wT 与分割超平面是垂直的，$\gamma$γ 表示原点到分割超平面的距离。

间隔：从支持向量对应的点到分类超平面的垂直距离的两倍，即有：$W=2d$W=2d。

保证分类正确，若以红色为正类，则有： 当 $w^T·x + \gamma > 0$wT⋅x+γ>0时，令 $y_i = +1$yi​=+1 ；若以蓝色为负类，则有：当 $w^T·x + \gamma < 0$wT⋅x+γ<0时，令 $y_i = -1$yi​=−1 。此处的 $w^T·x + \gamma$wT⋅x+γ 其实就是 $w_1 \cdot x_1 + w_2 \cdot x_2 + \cdots + w_n \cdot x_n$w1​⋅x1​+w2​⋅x2​+⋯+wn​⋅xn​，只不过写成了矩阵形式。但是此处的约束条件0是比较宽松的条件，实际上的约束条件应该是 $d$d 。

继续推导：

其实就是等式两边同时乘了系数，看似两个超平面，其实是同一个。所以，可将不等式统一为：

$y_i(\omega^T \cdot x + \gamma) \ge 1 （分类正确的约束条件）$yi​(ωT⋅x+γ)≥1（分类正确的约束条件）

1.3 SVM 转化为优化问题

不等式 $y_i(\omega^T \cdot x + \gamma) \ge 1$yi​(ωT⋅x+γ)≥1 中，只有分隔超平面上的点（支持向量）才满足等号成立的条件，即样本为支持向量时，等号才成立。

$s.t.$s.t. 的意思是 “使得”。进一步转化：

---

2. 不等式约束条件下求极值

2.1 求极值常见的几种情况

上图中，凸函数可以用本节所讲的知识求极值；但是非凸函数不可以使用本节内容求解。

2.2 无约束条件求极值

---

2.3 等约束条件求极值

分别对变量（注意拉格朗日乘子 $\lambda$λ 也是变量）求偏导，联立解方程组，解出极值。

上图中的实线是约束条件 $x_1 + x_2 + x_3 + x_4 - 1 = 0$x1​+x2​+x3​+x4​−1=0 （四维）在 $x_1, x_2$x1​,x2​ 组成的二维平面上的表示，那么所求极值就是约束条件（实线）与等高线（虚线圆）的切点。求极值的过程，可以理解为两个维度中的直线逼近等高线的过程，直到出现切点。

---

2.3 不等式约束条件求极值

2.3.1 KKT条件

互补松弛条件中“松弛”的理解：互补松弛条件是两个条件的乘积，该条件只要满足其中一个等于0，那么另一个可以任意取值，这就比单个条件的限制松弛了很多。

2.3.2 拉格朗日函数

注意，如果全局极值不满足等式约束时，则符合条件的极值会出现在不等约束的边界上。

已知 $x_4 \le c$x4​≤c

第二种情况，可能需要重新求满足约束条件的极值（常常在边界上）。

构造拉格朗日函数

解方程：

第一种情形：

第二种情形：

第三种情形

2.3.3 拉格朗日对偶

推导过程：



上图中的该结论，课程中并未证明，但不影响SVM使用。

---

3. 求解SVM分类超平面

3.1 解决间隔优化问题

此时，公式中只剩下 $\mu_i,\mu_j$μi​,μj​ 变量。求出 $\mu$μ 即可求出 $\omega,\gamma$ω,γ。

3.2 SMO算法

3.3 求解超平面

---

4. 核函数与松弛变量

如图所示，左图中，一维空间中的超平面为点，但是找不出一个点将图中所有的点分为两类，因此这是一种典型的线性不可分的情况。那么想办法将一维空间映射到二维空间，实现线性可分。如图，使用正弦函数，正好可以实现一维到二维的映射，并可以用一条直线（图中橙色虚线）将这些点分开。

右图中，二维空间中的超平面为直线，但是找不出一条直线将所有点划分为二分类。因此，找到一种映射关系，将这些点映射到三维空间，则可用一个平面可以将这些点分开。

4.1 核函数

核函数的例子

4.2 核函数的分类和选择

最常用的核函数是RBF和线性核函数。

4.3 异常点造成的线性不可分

4.4 松弛变量

4.5 SVM多分类

SVM是为二分类问题设计的，但可以通过构造合适的多分类器实现多分类：

总结

第一章介绍了支持向量机的原理与问题转化。
第二章介绍了不等式约束条件下求极值的方法。
第三章介绍了SVM分类超平面。
第四章介绍了核函数与松弛变量。