但问题来了:这无数条直线中应该选择哪一条作为最优决策边界呢?我想作为一个具有机器学习算法常识的人来说,虽然对SVM还不了解,但凭直觉一定会选择
H
3
H_{3}
H3。之所以不选择
H
2
H_{2}
H2是因为,边界
H
2
H_{2}
H2过于靠近一些训练数据,那么这些靠近边界的数据受噪声或干扰影响时,得到的真实数据就更容易从一个类别跳到另一个类别,导致分类错误和泛化性能下降。相比之下,边界
H
3
H_{3}
H3对训练数据局部扰动的“容忍性”最好,换言之,边界
H
3
H_{3}
H3所产生的分类结果是最鲁棒的,对未见示例的泛化能力最强
其中
ω
=
(
ω
1
;
ω
2
;
.
.
.
;
ω
d
)
\omega=(\omega_{1};\omega_{2};...;\omega_{d})
ω=(ω1;ω2;...;ωd)为法向量,决定了超平面的方向,
b
b
b为位移项,决定了超平面与原点之间的距离。显然,划分超平面可由法向量
ω
\omega
ω和位移
b
b
b确定。将其记为
(
ω
,
b
)
(\omega,b)
(ω,b),样本空间中任意点
x
x
x到超平面
(
ω
,
b
)
(\omega,b)
(ω,b)的距离可以写为
r
=
∣
∣
w
T
x
+
b
∣
∣
∣
∣
ω
∣
∣
r=\frac{||w^{T}x+b||}{||\omega||}
r=∣∣ω∣∣∣∣wTx+b∣∣
假设超平面
(
ω
,
b
)
(\omega,b)
(ω,b)能将训练样本正确分类,即对于
(
x
i
,
y
i
)
∈
D
(x_{i},y_{i})\in D
(xi,yi)∈D,则有
记为(1)式
{
w
T
x
i
+
b
⩾
+
1
,
y
i
=
+
1
w
T
x
i
+
b
⩽
−
1
,
y
i
=
−
1
\left\{\begin{array}{ll}\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b \geqslant+1, & y_{i}=+1 \\\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b \leqslant-1, & y_{i}=-1\end{array}\right.
{wTxi+b⩾+1,wTxi+b⩽−1,yi=+1yi=−1
如下图所示,距离超平面最近的这几个训练样本点使上式等号成立,它们被称为支持向量,两个异类支持向量到超平面的距离之和为
g
a
m
m
a
=
2
∣
∣
ω
∣
∣
gamma=\frac{2}{||\omega||}
gamma=∣∣ω∣∣2,称其为间隔
支持向量机的基本思想就是找出能够正确划分数据集并且具有最大几何间隔的分离超平面。欲找到具有最大间隔的划分超平面,也就是要找到能满足(1)式中约束的参数
ω
\omega
ω和
b
b
b,使得
γ
\gamma
γ最大,也即
记为(2)式
max
w
,
b
2
∥
w
∥
s.t.
y
i
(
w
T
x
i
+
b
)
⩾
1
,
i
=
1
,
2
,
…
,
m
.
\begin{aligned}\max _{\boldsymbol{w}, b} & \frac{2}{\|\boldsymbol{w}\|} \\\text { s.t. } & y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1, \quad i=1,2, \ldots, m .\end{aligned}
w,bmax s.t. ∥w∥2yi(wTxi+b)⩾1,i=1,2,…,m.
min
w
,
b
1
2
∥
w
∥
2
s.t.
y
i
(
w
T
x
i
+
b
)
⩾
1
,
i
=
1
,
2
,
…
,
m
.
\begin{array}{ll}\min _{\boldsymbol{w}, b} & \frac{1}{2}\|\boldsymbol{w}\|^{2} \\\text { s.t. } & y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1, \quad i=1,2, \ldots, m .\end{array}
minw,b s.t. 21∥w∥2yi(wTxi+b)⩾1,i=1,2,…,m.
m
i
n
.
f
(
x
)
=
c
T
x
min.f(x)=c^{T}x
min.f(x)=cTx
约束条件为
A
x
≥
b
,
x
≥
0
Ax \geq b,x\geq 0
Ax≥b,x≥0
其中
c
,
b
c, b
c,b 和
A
A
A 是已知的向量和矩阵,
x
x
x 是变量向量。现在,我们可以将其转换为一个对偶问题,如下所示
m
a
x
.
g
(
y
)
=
b
T
y
max.g(y)=b^{T}y
max.g(y)=bTy
在约束条件下
A
T
y
≤
c
,
y
≥
0
A^{T}y\leq c,y\geq 0
ATy≤c,y≥0
这里的关键点在于构建一个与原问题等价的对偶问题。对偶问题可以从原问题中的约束条件中产生,每个约束条件都对应着对偶问题中的一个变量。在上述线性规划问题中,我们有两组约束条件,所以我们需要两个对偶变量
y
1
y_1
y1 和
y
2
y_2
y2。在对偶问题中,约束条件的符号与原问题中的符号相反。对于不等式约束,它在对偶问题中变为等式约束;对于等式约束,它在对偶问题中变为不等式约束。在这个例子中,我们可以通过求解对偶问题来确定原问题的最优解,同时我们也可以通过求解原问题来确定对偶问题的最优解
(3)式本身是个凸二次规划问题,求解起来比较轻松,但是借助拉格朗日乘子,此问题就可以改写为所谓的广义拉格朗日函数。具体来说,对(3)式的每条约束添加拉格朗日乘子
α
i
≥
0
\alpha_{i}\geq 0
αi≥0,则该问题的拉格朗日函数可写为
这个式子从另一个角度说明了为什么最优决策边界只取决于几个支持向量:对于不是支持向量的数据点来说,等式右边的
1
−
y
i
(
ω
T
x
i
+
b
)
1-y_{i}(\omega^{T}x_{i}+b)
1−yi(ωTxi+b)是大于0的,因此在让
L
(
ω
,
b
,
α
)
L(\omega,b,\alpha)
L(ω,b,α)最小化时,就必须把这些点的贡献给去除掉,去除的方式就是让系数
α
i
=
0
\alpha_{i}=0
αi=0
L
(
w
,
b
,
α
)
=
1
2
∥
w
∥
2
+
∑
i
=
1
m
α
i
(
1
−
y
i
(
w
T
x
i
+
b
)
)
L(\boldsymbol{w}, b, \boldsymbol{\alpha})=\frac{1}{2}\|\boldsymbol{w}\|^{2}+\sum_{i=1}^{m} \alpha_{i}\left(1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)\right)
L(w,b,α)=21∥w∥2+i=1∑mαi(1−yi(wTxi+b))
然后令
L
(
ω
,
b
,
α
)
L(\omega,b,\alpha)
L(ω,b,α)对
ω
\omega
ω和
b
b
b的偏导为零可得
分别记为(5)式和(6)式
ω
=
∑
i
=
1
m
α
i
y
i
x
i
,
0
=
∑
i
=
1
m
α
i
y
i
\omega=\sum_{i=1}^{m}\alpha_{i}y_{i}x_{i},0=\sum_{i=1}^{m}\alpha_{i}y_{i}
ω=i=1∑mαiyixi,0=i=1∑mαiyi
将(5)式代入(4)式,可将
ω
\omega
ω和
b
b
b消去,再考虑(6)式的约束,就可以得到(3)式的对偶问题如下
记为(7)式
max
α
∑
i
=
1
m
α
i
−
1
2
∑
i
=
1
m
∑
j
=
1
m
α
i
α
j
y
i
y
j
x
i
T
x
j
s.t.
∑
i
=
1
m
α
i
y
i
=
0
,
α
i
⩾
0
,
i
=
1
,
2
,
…
,
m
.
\begin{aligned}\max _{\boldsymbol{\alpha}} & \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} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j} \\\text { s.t. } & \sum_{i=1}^{m} \alpha_{i} y_{i}=0, \\& \alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m .\end{aligned}
αmax s.t. i=1∑mαi−21i=1∑mj=1∑mαiαjyiyjxiTxji=1∑mαiyi=0,αi⩾0,i=1,2,…,m.
虽然现在我们将原问题转变为了其对偶问题,但是这两者之间是否能够完全划等号还是一个未知数。仔细看,原函数求出的是
L
(
ω
,
b
,
α
)
L(\omega,b,\alpha)
L(ω,b,α)最大值的下界,对偶函数求出的是
L
(
ω
,
b
,
α
)
L(\omega,b,\alpha)
L(ω,b,α)最小值的下界,因此后者肯定不会大于前者,但也不是无条件相等。好在数学上可以证明,当上述过程满足KKT条件(Karush-Kuhn-Tucker)时,原问题和对偶问题才能殊途同归。如下,KKT条件要求
记为(8)式
{
α
i
⩾
0
;
y
i
f
(
x
i
)
−
1
⩾
0
;
α
i
(
y
i
f
(
x
i
)
−
1
)
=
0
\left\{\begin{array}{l}\alpha_{i} \geqslant 0 ; \\y_{i} f\left(\boldsymbol{x}_{i}\right)-1 \geqslant 0 ; \\\alpha_{i}\left(y_{i} f\left(\boldsymbol{x}_{i}\right)-1\right)=0\end{array}\right.
⎩⎨⎧αi⩾0;yif(xi)−1⩾0;αi(yif(xi)−1)=0
于是,对于任意训练样本
(
x
i
,
y
i
)
(x_{i},y_{i})
(xi,yi),总有
α
i
=
0
\alpha_{i}=0
αi=0或
y
i
f
(
x
i
)
=
1
y_{i}f(x_{i})=1
yif(xi)=1
若
α
i
=
0
\alpha_{i}=0
αi=0,则该样本不会对
f
(
x
)
f(x)
f(x)有任何影响(前面已经说明)
若
α
i
>
0
\alpha_{i}>0
αi>0,则必有
y
i
f
(
x
i
)
=
1
y_{i}f(x_{i})=1
yif(xi)=1,所对应的样本点位于最大间隔边界上,是一个支持向量。和前面叙述一致,这显示输出了支持向量机的一个重要性质:训练完成后,大部分训练样本都不需要保留,最终模型仅与支持向量有关
max
α
∑
i
=
1
m
α
i
−
1
2
∑
i
=
1
m
∑
j
=
1
m
α
i
α
j
y
i
y
j
ϕ
(
x
i
)
T
ϕ
(
x
j
)
\max _{\boldsymbol{\alpha}} \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} \phi\left(\boldsymbol{x}_{i}\right)^{\mathrm{T}} \phi\left(\boldsymbol{x}_{j}\right)
αmaxi=1∑mαi−21i=1∑mj=1∑mαiαjyiyjϕ(xi)Tϕ(xj)