支持向量机

  支持向量机（Support Vector Mechine, SVM）是由统计学习之父弗拉基米尔·瓦普尼克提出的。他在 1963 年就提出了相关概念，但由于他当时身在苏联且当时苏联学术界几乎不与西方交流，所以并未得到重视。1990 年他前往美国，他将之前的研究工作整理发表，支持向量机很快就变得火热。
  本文只是对 SVM 进行浅显的讨论，适合 SVM 的应用者，而非 SVM 的研究者。

基本思想

  支持向量机可以说是一种有监督的二分类模型，主要用于完成分类任务。我们首先来看一个简单的分类任务。

  在上图的二维平面中有两类点，我们的任务就是找一条直线将这两类分割开来。将两类点分割开的直线有很多，如下图所示：

  在上图的众多分割线当中，我们主观上感觉图中的红线是最优的分割线，因为它在“正中间”。图中的各点仅是训练集给出的，当使用训练集之外的数据时，红线的预测效果也是最佳的。因为训练集中多少会存在一些噪声点，而这些分割线中的红线受噪声的影响是最小的。换而言之，红线是泛化性能最好的分割线。那么我们如何找到最佳分割线呢？或者说我们如何定义最佳分割线？
  我们以某条分割线的为基础，在其左右两侧各构造一条平行线，将这两条线以同样的步长不断向外移动直到碰到样本点时停止，如下图所示。

  图中蓝色虚线即为红线两侧的平行线，它们到红线的距离是相等的。我们称蓝线触碰到的样本点为红线的支持向量（support vector），两条蓝线之间的距离为红线的间隔（margin）。我们认为最佳分割线就是拥有最大间隔（maximum margin）的分割线。图示中给出的是二维的样本点，我们使用直线进行分割；如果是三维样本点，我们使用平面分割；在更高的维度，我们使用超平面（hyperplane）进行分割。在学术上，统一将其称之为超平面。SVM 的训练任务就是在训练集上寻找拥有最大间隔的的超平面。

硬间隔

  我们这里先给出线性可分的定义：面对一个二分类数据集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x m , y m ) ∣ x i ∈ R n , y i = ± 1 } D=\left\{(\boldsymbol{x}_1,y_1), (\boldsymbol{x}_2,y_2), \cdots, (\boldsymbol{x}_m,y_m) | \boldsymbol{x}_i \in \mathbb{R}^n, y_i = \pm 1 \right\} D={(x1​,y1​),(x2​,y2​),⋯,(xm​,ym​)∣xi​∈Rn,yi​=±1}，如果存在一个线性方程 ${\mathbf{w}}^{\top }\mathbf{x}+b=0$，对于任意 $({\mathbf{x}}_i,y_i)\in D$，若 $y_i=1$，则 ${\mathbf{w}}^{\top }{\mathbf{x}}_i+b>0$；若 $y_i=-1$，则 ${\mathbf{w}}^{\top }{\mathbf{x}}_i+b<0$，则称二分类数据集 $D$ 是线性可分的。
  这里的 ${\mathbf{x}}_i$ 就是我们向分类模型输入的特征向量，$y_i$ 就是 $x_i$ 对应的标签。由于是二分类任务，所以 $y_i$ 的取值只有两个 $1$ 或 $-1$。我们在上文的图中提到的分类任务就是线性可分的。需要注意的是，如果一个训练集是线性可分的，那么必然存在无数个可以对其进行分割的超平面，我们这里不进行证明。现在我们的任务就是将寻找拥有最大间隔的超平面的任务使用数学语言描述出来。
  我们给出线性可分的二分类数据集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x m , y m ) ∣ x i ∈ R n , y i = ± 1 } D=\left\{(\boldsymbol{x}_1,y_1), (\boldsymbol{x}_2,y_2), \cdots, (\boldsymbol{x}_m,y_m) | \boldsymbol{x}_i \in \mathbb{R}^n, y_i = \pm 1 \right\} D={(x1​,y1​),(x2​,y2​),⋯,(xm​,ym​)∣xi​∈Rn,yi​=±1}，并设进行分割的超平面的线性方程如下：
$${\mathbf{w}}^{\top }\mathbf{x}+b=0\text{\hspace{1em}(1)}$$  我们寻找拥有最大间隔的超平面的过程其实就是确定 $\mathbf{w}$ 和 $b$ 的过程，现在我们将该超平面记作 $(\mathbf{w},b)$。我们知道空间内任意一点 $\mathbf{x}$ 到 $(\mathbf{w},b)$ 的距离 $r$ 为：
$$r=\frac{\left|{\mathbf{w}}^{\top }\mathbf{x}+b\right|}{\Vert \mathbf{w}\Vert }\text{\hspace{1em}(2)}$$  根据线性可分的定义，如果 $(\mathbf{w},b)$ 能将训练集正确分割，那么它必须满足如下限制条件：
$$\{\begin{array}{ll}{\mathbf{w}}^{\top }{\mathbf{x}}_i+b>0,& y_i=1\\ {\mathbf{w}}^{\top }{\mathbf{x}}_i+b<0,& y_i=-1\end{array}\text{\hspace{1em}(3)}$$  根据定义我们可以得到支持向量 ${\mathbf{x}}^{\ast }$ 为：
$${\mathbf{x}}^{\ast }=\underset{\mathbf{x}}{\mathrm{argmin}}\frac{\left|{\mathbf{w}}^{\top }\mathbf{x}+b\right|}{\Vert \mathbf{w}\Vert }\text{\hspace{1em}(4)}$$  记 $a=\left|{\mathbf{w}}^{\top }{\mathbf{x}}^{\ast }+b\right|$，我们以支持向量所在平面（上文图中的蓝色虚线）作为分割依据，则有如下条件成立：
$$\{\begin{array}{ll}{\mathbf{w}}^{\top }{\mathbf{x}}_i+b⩾a,& y_i=1\\ {\mathbf{w}}^{\top }{\mathbf{x}}_i+b⩽-a,& y_i=-1\end{array}\text{\hspace{1em}(5)}$$  由于 $\mathbf{w}$ 和 $b$ 取确定值时，$a$ 也就随之确定，所以令 $\tilde{\mathbf{w}}=\frac{\mathbf{w}}{a}$，$\tilde{b}=\frac{b}{a}$，则可得如下条件成立：
$$\{\begin{array}{ll}{\tilde{\mathbf{w}}}^{\top }{\mathbf{x}}_i+\tilde{b}⩾1,& y_i=1\\ {\tilde{\mathbf{w}}}^{\top }{\mathbf{x}}_i+\tilde{b}⩽-1,& y_i=-1\end{array}\text{\hspace{1em}(6)}$$  可以进一步写作：
$$y_i\left({\tilde{\mathbf{w}}}^{\top }{\mathbf{x}}_i+\tilde{b}\right)⩾1\text{\hspace{1em}(7)}$$  因为条件 $(3)$ 是条件 $(7)$ 的前提条件，所以 $(7)$ 成立时，$(3)$ 必然成立。因此，我们使用 $(7)$ 作为新的限制条件。我们的目的是要在如上条件下寻找最大间隔，即：
$$\begin{array}{rl}& \underset{\mathbf{w},b}{\max }\frac{\left|{\mathbf{w}}^{\top }{\mathbf{x}}^{\ast }+b\right|}{\Vert \mathbf{w}\Vert }=\underset{\tilde{\mathbf{w}},\tilde{b}}{\max }\frac{1}{\Vert \tilde{\mathbf{w}}\Vert }⟺\underset{\tilde{\mathbf{w}},\tilde{b}}{\min }\frac{1}{2}\Vert \tilde{\mathbf{w}}{\Vert }^2\\ & s.t.y_i\left({\tilde{\mathbf{w}}}^{\top }{\mathbf{x}}_i+\tilde{b}\right)⩾1,i=1,2,\cdots ,m\end{array}\text{\hspace{1em}(8)}$$  我们可以看出 ${\tilde{\mathbf{w}}}^{\top }{\mathbf{x}}_i+\tilde{b}=0$ 与 ${\mathbf{w}}^{\top }{\mathbf{x}}_i+b=0$ 是同一个超平面，所以我们不妨将最终表达式写作：
$$\begin{array}{rl}& \underset{\mathbf{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2\\ & s.t.y_i\left({\mathbf{w}}^{\top }{\mathbf{x}}_i+b\right)⩾1,i=1,2,\cdots ,m\end{array}\text{\hspace{1em}(8)}$$  上述是一个凸二次优化问题，求出解即完成线性 SVM 的训练，这里我们不再讨论求解过程。训练完成后，可按照如下公式对模型进行测试：
$$\hat{y}=\mathrm{sgn}\left({\mathbf{w}}^{\top }\mathbf{x}+b\right)\text{\hspace{1em}(9)}$$

软间隔

  现在我们设想这样一个情况：我们要完成的分类任务实际上是线性可分的，但是由于训练集中存在个别噪声样本，使得训练集变为线性不可分，如下图所示。显然表达式 $(8)$ 在下图所示的含有噪声的训练集上是无解的。那我们能否对表达式进行一些改造，使其能够容忍一定的噪声，从而在该训练集上有解？

  我们也可以设想另一种情况：也许某个训练集中的噪声并没有那么“过分”，两个类别的噪声虽然靠的非常近，但是训练集仍然是线性可分的。然而，算法将噪声点当作支持向量进行训练，最终会导致过拟合现象，如下图所示。

  SVM 为了解决噪声造成的不可解以及过拟合现象，对表达式 $(8)$ 作出了如下改动：
$$\begin{array}{rl}& \underset{\mathbf{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C\sum _{i=1}^m{\xi }_i\\ & \begin{array}{rlr}s.t.& y_i\left({\mathbf{w}}^{\top }{\mathbf{x}}_i+b\right)⩾1-{\xi }_i,& i=1,2,\cdots ,m\\ & {\xi }_i⩾0,& i=1,2,\cdots ,m\end{array}\end{array}\text{\hspace{1em}(10)}$$  其中 ${\xi }_i$ 称为松弛变量（slack variables），它松弛了限制条件 $y_i\left({\mathbf{w}}^{\top }{\mathbf{x}}_i+b\right)⩾1-{\xi }_i$。因此，当 ${\xi }_i$ 足够大时，${\mathbf{x}}_i$ 就可以“越过”支持向量（下图中的蓝线）甚至超平面（下图中的红线）。但是，${\xi }_i$ 并不能无限制的变大，最小化表达式中引入了其累加和 ${\sum }_{i=1}^m{\xi }_i$，使得其在优化过程中被抑制增大。$C$ 是一个常数，用于调节对松弛变量的抑制力，当其趋向于正无穷大时，表达式 $(10)$ 也就等价于表达式 $(8)$。下图就是引入松弛变量的效果示意图。

  表达式 $(10)$ 就是常用的软间隔支持向量机，而表达式 $(8)$ 就相应地被称为硬间隔支持向量机，二者最明显的区别就是是否允许部分样本点“越过”支持向量。此外，软间隔支持向量机在测试时仍然使用表达式 $(9)$。

核函数

  在上文的所有讨论中，我们始终假设训练集是线性可分的或者“近似”线性可分的。然而，现实中有些问题不是线性可分的，最经典的就是异或问题。如下图所示的异或问题，我们无法找到一个超平面将其正确划分。

  解决此问题的一种思路是：使用多个有限的超平面，将它们拼接起来，形成一种近似的“超曲面”来进行分割。然而，SVM 的思路却比以上想法高明的多，它将样本通过函数映射到更高的维度，然后在高维度用超平面进行分割。针对上图中的问题，我们定义二维向三维的映射 $\varphi$ 的表达式为 $[x_1,x_2{]}^{\top }\stackrel{\varphi }{\to }[x_1,x_2,x_1\cdot x_2{]}^{\top }$，那么使用超平面 $[-1,-1,2]\cdot \mathbf{x}+0.5=0$ 就可以将其分割，如下图所示。

  胡浩基教授说，存在如下定理：将某维度中随机生成的有限个点，随机分为两类，而后将其转化为更高维度的点。维度越高，点集被正确线性分割的概率越大。当维度为无穷大时，点集被正确线性分割的概率为 $1$。
  我们引入自低维向高维的映射 $\varphi$ 后，表达式 $(8)$ 变为如下形式：
$$\begin{array}{rl}& \underset{\mathbf{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2\\ & s.t.y_i\left({\mathbf{w}}^{\top }\varphi ({\mathbf{x}}_i)+b\right)⩾1,i=1,2,\cdots ,m\end{array}\text{\hspace{1em}(11)}$$  测试时使用的表达式 $(9)$ 变为如下形式：
$$\hat{y}=\mathrm{sgn}\left({\mathbf{w}}^{\top }\varphi (\mathbf{x})+b\right)\text{\hspace{1em}(12)}$$  为了尽可能的增大训练集被正确线性分割的概率，SVM 采用的某些映射 $\varphi$ 可以将有限维度映射到超高维度甚至无穷大维度。这也就意味着 $\mathbf{w}$ 将有超多个分量甚至无穷个分量，显然这在现实中是难以应用的。为此 SVM 引入了核函数（kernel function），下面给出表达式：
$$\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)=\varphi ({\mathbf{x}}_i{)}^{\top }\varphi ({\mathbf{x}}_j)\text{\hspace{1em}(13)}$$  这样我们就可以通过一个核函数运算来代替两个超高维甚至是无限维的向量内积运算。常见的核函数有以下几个：

• 线性核
  $$\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)={\mathbf{x}}_i^{\top }{\mathbf{x}}_j$$  通过表达式可以看出，使用线性核等价于没有使用高维映射 $\varphi$。
• 多项式核
  $$\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)={\left({\mathbf{x}}_i^{\top }{\mathbf{x}}_j\right)}^d,d⩾1$$  其中 $d$ 是常数，代表着多项式的次数。多项式核代表着向有限维度的映射 $\varphi$。
• 高斯核
  $$\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)=\exp \left(-\frac{{\Vert {\mathbf{x}}_i-{\mathbf{x}}_j\Vert }^2}{2{\sigma }^2}\right),\sigma >0$$  其中 $\sigma$ 是常数，代表高斯核的带宽。高斯核代表着向无限维度的映射 $\varphi$。

  根据泛函分析中的 Mercer 定理，某函数 $\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)$ 可以写成 $\varphi ({\mathbf{x}}_i{)}^{\top }\varphi ({\mathbf{x}}_j)$ 的充要条件是其具有交换性和半正定性。
  如果我们能通过等价转换将表达式 $(11)$ 和 $(12)$ 中的 $\mathbf{w}$ 和 $\varphi$ 替换成含核函数 $\kappa$ 的表达式，也就解决了超高维度甚至无限维度映射无法应用的问题。下面我们给出表达式 $(11)$ 的等价表达式（对偶问题）：
$$\begin{array}{rl}& \underset{\mathbf{\alpha }}{\max }\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)\\ & \begin{array}{rlr}s.t.& \sum _{i=1}^m{\alpha }_i{y}_i=0,& i=1,2,\cdots ,m\\ & {\alpha }_i⩾0,& i=1,2,\cdots ,m\end{array}\end{array}\text{\hspace{1em}(14)}$$  其中 $\mathbf{\alpha }=[{\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_m{]}^{\top }$ 是新引入的待定参数向量。上式的具体推导过程这里不讨论，感兴趣的读者可以学习凸优化理论后自行推导。测试表达式 $(12)$ 可以等价转化为如下形式：
$$\hat{y}=\mathrm{sgn}\left(\sum _{i=1}^m{\alpha }_i{y}_i\kappa ({\mathbf{x}}_i,\mathbf{x})+b\right)$$

概率化输出

  SVM 在测试时可以将 ${\sum }_{i=1}^m{\alpha }_i{y}_i\kappa ({\mathbf{x}}_i,\mathbf{x})+b$ 的值通过变换输入到 Sigmoid 函数中，而后将 Sigmoid 的输出作为最终结果，从而实现了 SVM 预测结果的概率化输出。感性兴趣的读者可以参考Platt 的论文《Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods》。

优缺点

  优点：

• SVM 的训练过程仅依靠支持向量，所以在训练集很小的情况下，SVM 预测的泛化性能要优于其他模型。

  缺点：

• SVM 面都大规模训练样本的效率很低。一方面，核函数 SVM 每次预测时都需要与整个训练集进行运算；另一方面，在大规模训练样本上对 SVM 的超平面求解过程很复杂。
• SVM 调参过程复杂。SVM 的分类效果与核函数的选择关系很大，即使选择了恰当的核函数，也可能需要再对核函数内的超参数进行调节。
• 经典 SVM 仅支持二分类。虽然后来研究人员将 SVM 推广到了多分类甚至是回归任务，但效果并不理想。

参考文献

周志华《机器学习》
胡浩基《浙江大学支持向量机》课程视频
《机器学习：支持向量机（SVM）》博客

附录

  以下是生成基本原理、硬间隔和软间隔章节中示意图的代码：

from matplotlib import pyplot as plt
import numpy as np

np.random.seed(123456)
ax = plt.gca()
ax.set(xticks=(), yticks=())
# 生成两类随机散点图
[x, y] = np.random.rand(2, 20)
y = y + x + 0.2
ax.scatter(x, y, marker='o', color='yellow', label='Class One')
[x, y] = np.random.rand(2, 20)
x = x + y + 0.2
ax.scatter(x, y, marker=',', color='limegreen', label='Class Two')
# 画出支持向量
# x = np.random.rand(3)
# x = x * 1.5
# y = x + 0.2
# ax.scatter(x, y, marker='o', color='orange', label='Support Vector of Class One')
# x = np.random.rand(3)
# x = x * 1
# y = x - 0.2
# ax.scatter(x, y, marker=',', color='green', label='Support Vector of Class Two')
# # 画出其它可行的分割线
# x = np.linspace(0, 1.5, 100)
# y = x * 0.5 + 0.35
# ax.plot(x, y, color='black')
# y = x * 1.45 - 0.3
# ax.plot(x, y, color='black')
# 画出最大间隔
x = np.linspace(0, 1.5, 100)
y = x + 0.2
ax.plot(x, y, '--', color='blue', label='Parallel Hyperplane')
y = x - 0.2
ax.plot(x, y, '--', color='blue')
# 画出超平面
y = x
ax.plot(x, y, color='red', label='Hyperplane')
# 画出第一种噪声点
# ax.scatter([1.0, 0.8], [0.5, 0.4], marker='o', color='none', edgecolor='yellow', label='Noise of Class One')
# ax.scatter([0.5, 0.4], [1.0, 0.8], marker=',', color='none', edgecolor='limegreen', label='Noise of Class Two')
# 画出第二种噪声点及其造成的过拟合分割线
x = np.array([0.5, 0.6])
y = x * 0.5 + 0.4
ax.scatter(x, y, marker='o', color='none', edgecolor='yellow', label='Noise of Class One')
y = x * 0.5 + 0.3
ax.scatter(x, y, marker=',', color='none', edgecolor='limegreen', label='Noise of Class Two')
# x = np.linspace(0, 1.5, 100)
# y = x * 0.5 + 0.35
# ax.plot(x, y, color='black', label='Hyperplane')

ax.legend()
plt.show()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

  以下为生成核函数章节中第一幅插图的代码：

from matplotlib import pyplot as plt
import numpy as np

ax = plt.gca()
ax.set(xticks=(0, 1), yticks=(0, 1))
ax.axis('equal')
ax.scatter([0, 1], [1, 0], marker='o', color='yellow', label='Class One')
ax.scatter([0, 1], [0, 1], marker=',', color='limegreen', label='Class Two')
# 画出椭圆
t = np.arange(0, 2 * np.pi, 0.01)
a = 1
b = 0.5
c = np.sqrt(a**2 - b**2)
e = c / a
r = a * (1 - e**2) / (1 - e * np.cos(t + np.pi / 4))
x = r * np.cos(t) - np.sqrt(c**2 / 2) + 0.5
y = r * np.sin(t) + np.sqrt(c**2 / 2) + 0.5
ax.plot(x, y, color='red', label='Non-hyperplane')

ax.legend()
plt.show()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

  以下为生成核函数章节中第二幅插图的代码：

from matplotlib import pyplot as plt
import numpy as np

ax = plt.gca(projection='3d')
ax.scatter([0, 1], [0, 1], [0, 1], color='limegreen', edgecolor='black', zorder=1, label='Class Two')
ax.scatter([0, 1], [1, 0], [0, 0], color='yellow', edgecolor='black', zorder=1, label='Class One')
x, y = np.meshgrid(np.linspace(-0.2, 1.2, 100), np.linspace(-0.2, 1.2, 100))
z = 0.5 * x + 0.5 * y - 0.25
ax.plot_surface(x, y, z, alpha=0.3, zorder=0)

ax.view_init(30, 10)
ax.legend()
plt.show()

1
2
3
4
5
6
7
8
9
10
11
12
13
14