- 引言
- 支持向量机介绍
- 支持向量机构建的朴素思想
- 硬间隔SVM的模型构建
- 场景描述
- 模型构建过程
- 小插曲：函数间隔
从本节开始，将介绍支持向量机，主要包括模型思路构建和模型最优参数的求解过程。
支持向量机介绍支持向量机(Support Vector Machine,SVM)是一种基于监督学习的对数据进行 二元分类 的广义线性分类器(Generalized Linear Classifier)。
从线性分类的角度观察，支持向量机是一个硬分类模型，在机器学习笔记之线性分类——感知机算法中介绍过，硬分类模型使用的激活函数是非连续的。下面对支持向量机的模型 进行表示。
基于分类任务的性质，线性分类本质上就是使用直线(超平面)对样本空间进行划分，从而实现各样本在对应样本子空间的分类效果。
定义该直线(超平面) 的表达式为 W T x + b = 0 ( x ∈ { x ( i ) ∣ i = 1 , 2 , ⋯ , N } ) \mathcal W^{T}\mathcal x + b = 0 \quad(x \in \left\{x^{(i)}|_{i=1,2,\cdots,N}\right\}) WTx+b=0(x∈{x(i)∣i=1,2,⋯,N})。基于硬分类模型的性质，定义支持向量机的模型表达如下： f ( W ) = s i g n ( W T x + b ) ( x ∈ { x ( i ) ∣ i = 1 , 2 , ⋯ , N } ) f(\mathcal W) = sign(\mathcal W^{T}\mathcal x + b) \quad(x \in \left\{x^{(i)}|_{i=1,2,\cdots,N}\right\}) f(W)=sign(WTx+b)(x∈{x(i)∣i=1,2,⋯,N}) 其中 s i g n sign sign表示符号函数： s i g n ( a ) = { 1 i f a ≥ 0 − 1 e l s e sign(a) = \begin{cases} 1 \quad if \quad a \geq 0 \\ -1 \quad else \end{cases} sign(a)={1ifa≥0−1else 因此，支持向量机是一个纯粹的判别模型。(注意：这里要和线性分类中软分类的概率判别模型区分开)：
- 判别模型 在这里的意思主要指 模型映射结果与真实标签的特征空间相同，区别于软分类的概率结果；
判别模型的定义和硬分类的定义相类似，‘模型预测过程’和‘概率’没有关联关系。 - 概率判别模型 指的是对后验概率 P ( Y ∣ X ) P(\mathcal Y \mid \mathcal X) P(Y∣X)直接进行求解，并直接对结果进行比较。两者不是一个概念。
可以看出，支持向量机的模型描述和感知机(Perceptron)、线性判别分析(Linear Discriminant Analysis,LDA)相同，就是一个 基于硬分类的线性模型。
支持向量机构建的朴素思想从几何角度观察，线性分类的本质即样本点在被划分后的样本子空间中被分类正确。但分类正确的直线(超平面)并不唯一。具体图像实例如下(图源：机器学习(周志华著))： 
从图中可以看出，上述所有直线均可以将样本正确划分，如何从众多直线中找出一条最优直线，使得样本划分效果最优？
上述问题中隐含了一个评判标准：满足什么标准的直线是划分效果优的直线，如果存在这么一个标准(策略)，将这个标准满足到极致——就可以得到划分效果最优的直线。
从机器学习的角度出发，在机器学习笔记——极大似然估计与最大后验概率估计中介绍到，样本集合 X = { x ( 1 ) , x ( 2 ) , ⋯ , x ( N ) } \mathcal X = \{x^{(1)},x^{(2)},\cdots,x^{(N)}\} X={x(1),x(2),⋯,x(N)}可以理解为基于概率模型 P ( X ; θ ) P(\mathcal X;\theta) P(X;θ)生成样本 x ( i ) x^{(i)} x(i)组成的集合。因此，给定概率模型 P ( X ; θ ) P(\mathcal X;\theta) P(X;θ)条件下，可以 源源不断地生成样本——相反，想要估计概率模型 P ( X ; θ ) P(\mathcal X;\theta) P(X;θ)，却只能基于有限的数据集合进行估计。
因此，在线性分类中，基于有限的数据集合，我们不仅要关注模型是否会将样本正确划分，还要关注模型自身的鲁棒性：鲁棒性差的模型可能在训练集上可能得到一个不错的结果，但如果对一个不在训练集内部的新数据进行预测，其结果可能并不会满意。 过拟合(Overfitting)同样也是模型鲁棒性差的一种体现。
言归正传，如何通过模型的某些性质衡量模型的鲁棒性呢？观察上图中的直线1和直线2：
相比于直线2，直线1对于 数据集合样本空间边界的样本点的距离更加靠近，这种现象会导致直线1对应的模型鲁棒性更差。解释：如果在样本空间边界附近新增新的样本点(图中的红色样本点)，该样本点和原始样本之间可能只存在极小的噪声差距，但最终却被直线1错误分类。由此看出：相比于直线2，直线1对于样本噪声的容忍度更低，泛化误差更大。
支持向量机 策略构建的的朴素思想是：找出一条直线，使得位于数据集合的各样本子空间的样本点到该直线的距离均最大即可。
我们将满足上述思想的策略 称作 最大间隔分类器，其对应模型称为硬间隔SVM模型(hard-margin SVM)。
硬间隔SVM的模型构建 场景描述在模型构建之前，照例对场景进行部署： 数据集合 D a t a = { ( x ( i ) , y ( i ) ) } i = 1 N Data = \left\{(x^{(i)},y^{(i)})\right\}_{i=1}^N Data={(x(i),y(i))}i=1N，其中任意 x ( i ) ( i = 1 , 2 , ⋯ , N ) x^{(i)}(i=1,2,\cdots,N) x(i)(i=1,2,⋯,N)是 p p p维向量，对应 y ( i ) y^{(i)} y(i)是一个标量，并针对二分类任务性质进行如下表示： x ( i ) = { x 1 ( i ) , x 2 ( i ) , ⋯ , x p ( i ) } T y ( i ) ∈ { − 1 , 1 } x^{(i)} = \left\{x_1^{(i)},x_2^{(i)},\cdots,x_p^{(i)}\right\}^{T} \\ y^{(i)} \in \{-1,1\} x(i)={x1(i),x2(i),⋯,xp(i)}Ty(i)∈{−1,1}
模型构建过程基于最大间隔分类器朴素思想，对其进行解析：
-
首先要满足的条件：基于当前样本点，需要分类正确； { W T x ( i ) + b > 0 → y ( i ) = 1 W T x ( i ) + b < 0 → y ( i ) = − 1 \begin{cases}\mathcal W^{T}x^{(i)} + b > 0 \quad \to \quad y^{(i)} = 1 \\ \mathcal W^{T}x^{(i)} + b < 0 \quad \to \quad y^{(i)} = -1 \end{cases} {WTx(i)+b>0→y(i)=1WTx(i)+b 0 ( i = 1 , 2 , ⋯ , N ) y^{(i)}(\mathcal W^{T}x^{(i)} + b) > 0 \quad (i=1,2,\cdots,N) y(i)(WTx(i)+b)>0(i=1,2,⋯,N)
-
在样本点分类正确的基础上，使各样本子空间的样本点到该直线的距离均最大。
但实际上，样本点是数据集合给定的，即样本点在 p p p维样本空间的位置固定不变。因此，如果在 p p p维样本空间中任意产生一条直线，在该直线确定的条件下，那么空间中的 N N N个样本点到该直线的距离均固定不变。
因此，可以将上述思想转化为：从能够将样本点分类正确的直线中找出这样一条直线，该直线与 N N N个样本点对应的 N N N个距离中找出长度最小的距离，而基于该直线找出最小距离比其他直线的都要大，该直线就是我们要找的直线。
基于上述思想，对符号进行定义：
- 定义样本点
x
(
i
)
x^{(i)}
x(i)到直线
W
T
x
+
b
=
0
\mathcal W^{T}\mathcal x + b = 0
WTx+b=0的距离
D
\mathcal D
D表示如下：
点到直线的距离公式~D ( W , b , x ( i ) ) = 1 ∣ ∣ W ∣ ∣ ∣ W T x ( i ) + b ∣ \mathcal D(\mathcal W,b,x^{(i)}) = \frac{1}{||\mathcal W||} \left|\mathcal W^{T}x^{(i)} + b\right| D(W,b,x(i))=∣∣W∣∣1 WTx(i)+b - 长度最小距离 M ( W , b ) \mathcal M(\mathcal W,b) M(W,b)表示如下： M ( W , b ) = min W , b , x ( i ) D ( W , b , x ( i ) ) \mathcal M(\mathcal W,b) = \mathop{\min}\limits_{\mathcal W,b,x^{(i)}} \mathcal D(\mathcal W,b,x^{(i)}) M(W,b)=W,b,x(i)minD(W,b,x(i))
- 至此，长度最小距离已经得到，最终通过调整 W , b \mathcal W,b W,b使得 M ( W , b ) \mathcal M(\mathcal W,b) M(W,b)达到最大： max M ( W , b ) \max \mathcal M(\mathcal W,b) maxM(W,b)
对上面步骤进行整理，可以得到如下表示： max W , b min x ( i ) ∣ i = 1 N 1 ∣ ∣ W ∣ ∣ ∣ W T x ( i ) + b ∣ \mathop{\max}\limits_{\mathcal W,b} \mathop{\min}\limits_{x^{(i)}|_{i=1}^N} \frac{1}{||\mathcal W||} \left|\mathcal W^{T}x^{(i)} + b\right| W,bmaxx(i)∣i=1Nmin∣∣W∣∣1 WTx(i)+b
至此，我们可以将步骤2视为目标函数，目标1视为约束条件，表达结果如下： { max W , b min x ( i ) ∣ i = 1 N 1 ∣ ∣ W ∣ ∣ ∣ W T x ( i ) + b ∣ s . t . y ( i ) ( W T x ( i ) + b ) > 0 \begin{cases}\mathop{\max}\limits_{\mathcal W,b} \mathop{\min}\limits_{x^{(i)}|_{i=1}^N} \frac{1}{||\mathcal W||} \left|\mathcal W^{T}x^{(i)} + b\right| \\ s.t. \quad y^{(i)}(\mathcal W^{T}x^{(i)} + b) > 0\end{cases} ⎩ ⎨ ⎧W,bmaxx(i)∣i=1Nmin∣∣W∣∣1 WTx(i)+b s.t.y(i)(WTx(i)+b)>0
观察目标函数：
- 由于 y ( i ) ∈ { − 1 , 1 } y^{(i)} \in \{-1,1\} y(i)∈{−1,1}且 y ( i ) ( W T x ( i ) + b ) y^{(i)}(\mathcal W^{T}x^{(i)} + b) y(i)(WTx(i)+b)结果恒正。因此，将 ∣ W T x ( i ) + b ∣ |\mathcal W^{T}x^{(i)} + b| ∣WTx(i)+b∣进行如下变换： ∣ W T x ( i ) + b ∣ = y ( i ) ( W T x ( i ) + b ) |\mathcal W^{T}x^{(i)} + b| = y^{(i)}(\mathcal W^{T}x^{(i)} + b) ∣WTx(i)+b∣=y(i)(WTx(i)+b)
- 由于 1 ∣ ∣ W ∣ ∣ \frac{1}{||\mathcal W||} ∣∣W∣∣1和 x ( i ) x^{(i)} x(i)无关，因此可以将 1 ∣ ∣ W ∣ ∣ \frac{1}{||\mathcal W||} ∣∣W∣∣1提前，最终表达为如下形式： max W , b 1 ∣ ∣ W ∣ ∣ min x ( i ) ∣ i = 1 N y ( i ) ( W T x ( i ) + b ) \mathop{\max}\limits_{\mathcal W,b} \frac{1}{||\mathcal W||}\mathop{\min}\limits_{x^{(i)}|_{i=1}^N} y^{(i)}\left(\mathcal W^{T}x^{(i)} + b\right) W,bmax∣∣W∣∣1x(i)∣i=1Nminy(i)(WTx(i)+b)
观察约束条件： y ( i ) ( W T x ( i ) + b ) y^{(i)}\left(\mathcal W^{T}x^{(i)} + b\right) y(i)(WTx(i)+b)是由 ∣ W T x ( i ) + b ∣ |\mathcal W^{T}x^{(i)} + b| ∣WTx(i)+b∣转化而来，原因是：
- y ( i ) ∈ { − 1 , 1 } y^{(i)} \in \{-1,1\} y(i)∈{−1,1}
- y ( i ) y^{(i)} y(i)与 W T x ( i ) + b \mathcal W^{T}x^{(i)} + b WTx(i)+b同号。
但在超平面
W
T
X
+
b
=
0
\mathcal W^{T}\mathcal X + b = 0
WTX+b=0确定的条件下，
∣
W
T
x
(
i
)
+
b
∣
|\mathcal W^{T}x^{(i)} + b|
∣WTx(i)+b∣可以相对地表示： 样本点
x
(
i
)
x^{(i)}
x(i)距离超平面
W
T
X
+
b
=
0
\mathcal W^{T}\mathcal X + b = 0
WTX+b=0远近程度的一种描述。 需要注意的点，
∣
W
T
x
(
i
)
+
b
∣
|\mathcal W^{T}x^{(i)} +b|
∣WTx(i)+b∣它不是距离，它只是一种对‘距离’趋势的描述。如果
∣
W
T
x
(
i
)
+
b
∣
|\mathcal W^{T}x^{(i)} +b|
∣WTx(i)+b∣较大，那么样本点
x
(
i
)
x^{(i)}
x(i)距离超平面距离较远，反之同理。
抛开 最大间隔分类器的条件， y ( i ) ( W T x ( i ) + b ) y^{(i)}\left(\mathcal W^{T}x^{(i)} + b\right) y(i)(WTx(i)+b)结果正负均有可能：
- y ( i ) ( W T x ( i ) + b ) > 0 y^{(i)}\left(\mathcal W^{T}x^{(i)} + b\right) > 0 y(i)(WTx(i)+b)>0，样本 ( x ( i ) , y ( i ) ) (x^{(i)},y^{(i)}) (x(i),y(i))分类正确；
-
y
(
i
)
(
W
T
x
(
i
)
+
b
)
<
0
y^{(i)}\left(\mathcal W^{T}x^{(i)} + b\right) < 0
y(i)(WTx(i)+b)
0
\mathcal H^{(i)} = y^{(i)}\left(\mathcal W^{T}x^{(i)} + b\right) >0
H(i)=y(i)(WTx(i)+b)>0，则有：
∃
γ
>
0
→
min
(
x
(
i
)
,
y
(
i
)
)
i
=
1
N
y
(
i
)
(
W
T
x
(
i
)
+
b
)
=
min
(
x
(
i
)
,
y
(
i
)
)
i
=
1
N
H
(
i
)
=
γ
\exists \gamma > 0 \to \mathop{\min}\limits_{(x^{(i)},y^{(i)})_{i=1}^N} y^{(i)}(\mathcal W^{T}x^{(i)} + b) = \mathop{\min}\limits_{(x^{(i)},y^{(i)})_{i=1}^N} {\mathcal H}^{(i)} = \gamma
∃γ>0→(x(i),y(i))i=1Nminy(i)(WTx(i)+b)=(x(i),y(i))i=1NminH(i)=γ
由于超平面的等比例缩放对函数间隔产生的影响，因此 γ \gamma γ可能是大于0的任意值。 为了消除等比例缩放的影响，我们需要对 γ \gamma γ设定一个具体值，为了方便计算，设定 γ = 1 \gamma = 1 γ=1。 在确定 γ \gamma γ后意味着无论缩放成什么情况，都可以映射为最小值是1的那个函数间隔。
至此，对上述结论进行整理：
- y ( i ) ( W T x ( i ) + b ) > 0 y^{(i)}(\mathcal W^{T}x^{(i)} + b) > 0 y(i)(WTx(i)+b)>0，为消除等比例缩放对函数间隔的影响，转化为： min ( x ( i ) , y ( i ) ) i = 1 N y ( i ) ( W T x ( i ) + b ) = 1 \mathop{\min}\limits_{(x^{(i)},y^{(i)})_{i=1}^N} y^{(i)}(\mathcal W^{T}x^{(i)} + b) = 1 (x(i),y(i))i=1Nminy(i)(WTx(i)+b)=1 或者： y ( i ) ( W T x ( i ) + b ) ≥ 1 y^{(i)}(\mathcal W^{T}x^{(i)} + b) \geq 1 y(i)(WTx(i)+b)≥1
- 基于步骤1，将目标函数改写如下：
max
W
,
b
1
∣
∣
W
∣
∣
min
x
(
i
)
∣
i
=
1
N
y
(
i
)
(
W
T
x
(
i
)
+
b
)
=
max
W
,
b
1
∣
∣
W
∣
∣
⋅
1
=
max
W
,
b
1
∣
∣
W
∣
∣
\mathop{\max}\limits_{\mathcal W,b} \frac{1}{||\mathcal W||}\mathop{\min}\limits_{x^{(i)}|_{i=1}^N} y^{(i)}\left(\mathcal W^{T}x^{(i)} + b\right) = \mathop{\max}\limits_{\mathcal W,b} \frac{1}{||\mathcal W||} \cdot 1 = \mathop{\max}\limits_{\mathcal W,b} \frac{1}{||\mathcal W||}
W,bmax∣∣W∣∣1x(i)∣i=1Nminy(i)(WTx(i)+b)=W,bmax∣∣W∣∣1⋅1=W,bmax∣∣W∣∣1 消除范式格式、分数形式：
1
2
\frac{1}{2}
21
是用于简化计算添加的一个系数，由于和W \mathcal W W无关。因此不影响W \mathcal W W的最终取值。这里同样省略了一个根号，因为根号在当前定义域中式‘单调递增函数’，可能最后的‘最小值结果’是不同的，但不影响其结果是‘最小值’这个信息。max W , b 1 ∣ ∣ W ∣ ∣ ⇒ min W , b ∣ ∣ W ∣ ∣ ⇒ min W , b W T W ⇒ min W , b 1 2 W T W \mathop{\max}\limits_{\mathcal W,b} \frac{1}{||\mathcal W||} \Rightarrow \mathop{\min}\limits_{\mathcal W,b} ||\mathcal W|| \Rightarrow \mathop{\min}\limits_{\mathcal W,b} \sqrt{\mathcal W^{T}\mathcal W} \Rightarrow \mathop{\min}\limits_{\mathcal W,b} \frac{1}{2}\mathcal W^{T}\mathcal W W,bmax∣∣W∣∣1⇒W,bmin∣∣W∣∣⇒W,bminWTW ⇒W,bmin21WTW
最终，化简后公式表示如下： { min W , b 1 2 W T W s . t . y ( i ) ( W T x ( i ) + b ) ≥ 1 ( ∀ i = 1 , 2 , ⋯ , N ) \begin{cases}\mathop{\min}\limits_{\mathcal W,b} \frac{1}{2}\mathcal W^{T}\mathcal W \\ s.t. \quad y^{(i)}(\mathcal W^{T}x^{(i)} + b) \geq 1 \quad (\forall i = 1,2,\cdots,N)\end{cases} ⎩ ⎨ ⎧W,bmin21WTWs.t.y(i)(WTx(i)+b)≥1(∀i=1,2,⋯,N)
通过观察，该公式本质上是凸优化问题，并包含 N N N个约束条件。下一节将介绍如何基于上式求解最优模型参数。
相关参考： 机器学习-支持向量机1-硬间隔SVM-模型定义(最大间隔分类器) 函数间隔与几何间隔
