支持向量机之硬间隔(一步步推导,通俗易懂)
ML经典算法:支持向量机(1)中对支持向量机的理论知识进行了总结,这里再进行详细的数学梳理!
支持向量机随着任务的复杂度,主要有三部分知识:硬间隔、软间隔和核函数,这里先讲硬间隔!
硬间隔(hard-margin)
硬间隔主要应用在可以完美线性分类的任务中,如下图所示,“x”和“o”表示两种类别,共
m
m
m个样本:
现在我们要对其进行分类,那么有很多条直线可以完全区分这两类:
如何找到一条“最优”的直线:
g
(
x
)
=
w
x
+
b
g(x)=wx+b
g(x)=wx+b来分类呢?该直线应该可以正确分类,标签
y
i
∈
(
1
,
−
1
)
y_i \in(1,-1)
yi∈(1,−1)表示两类,即:
- w x i + b > = 1 wx_i+b>=1 wxi+b>=1时, y i = 1 y_i=1 yi=1
- w x i + b < = 1 wx_i+b<=1 wxi+b<=1时, y i = − 1 y_i=-1 yi=−1
即: y i ( w x i + b ) > = 1 y_i(wx_i+b)>=1 yi(wxi+b)>=1
当我们将分类线向两种类别平移时,可以看到图中有一些特殊的点,如下图红圈中:
这些特殊的点离分类线最近,分类线再平移就无法完美的分类,这些点称为“支持向量”(support vector))。在二维空间中,点
x
x
x 到直线
g
(
x
)
=
w
x
+
b
g(x)=wx+b
g(x)=wx+b的距离为:
则异类支持向量的距离为:
异类支持向量的距离也被称为间隔,不难看出,当间隔最大时,该分类线是最优的,鲁棒性最强,比如,我们在一座海上大桥上行驶,当然是行驶在最中间是最安全的。
即找到能满足式中约束的参数
w
w
w 和
b
b
b , 使得
r
r
r 最大:
问题可以转换为(求平方是为了后续求导求解方便):
如何根据上述条件求
w
和
b
w和b
w和b呢?
可以采用拉格朗日乘子法求得对偶问题(有等式约束时求解最优化问题的一种方法):
得到对偶问题:
注意:
x
i
x
j
x_ix_j
xixj为内积,这个很重要,在后续核函数中非常重要,上式可以写为:
现在
w
w
w 知道了,
b
b
b 怎么求呢?
由于对于任意支持向量
(
x
s
,
y
s
)
(x_s,y_s)
(xs,ys) 都有:
y
s
(
w
x
s
+
b
)
=
1
y_s(wx_s+b)=1
ys(wxs+b)=1,我们可以通过任意支持向量求得
b
b
b ,但有一个更为合适鲁棒的方法,即通过所有支持向量求b的平均值作为
b
b
b:
举个最简单的例子,来对硬间隔有个更为清晰的概念:
如下图所示为一个分类任务,一个样本为(1,1,+1),另一个样本为(0,0,-1),最后一个值为标签:
利用支持向量机原理进行分类:
由:
代入有:
Σ
α
i
−
1
/
2
(
Σ
α
T
H
α
)
=
α
1
+
α
2
−
1
/
2
(
[
α
1
,
α
2
]
∗
H
∗
[
α
1
,
α
2
]
T
)
=
α
1
+
α
2
−
1
/
2
(
α
1
2
+
α
2
2
)
=
0
(
1
)
\Sigma\alpha_i-1/2(\Sigma\alpha^TH\alpha)=\alpha_1+\alpha_2-1/2([\alpha_1,\alpha_2]*H*[\alpha_1,\alpha_2]^T)=\alpha_1+\alpha_2-1/2(\alpha_1^2+\alpha_2^2)=0(1)
Σαi−1/2(ΣαTHα)=α1+α2−1/2([α1,α2]∗H∗[α1,α2]T)=α1+α2−1/2(α12+α22)=0(1)
由: Σ α i y i = α 1 ∗ 1 + α 2 ∗ ( − 1 ) = 0 \Sigma\alpha_iy_i=\alpha_1*1+\alpha_2*(-1)=0 Σαiyi=α1∗1+α2∗(−1)=0得到 α 1 − α 2 = 0 \alpha_1-\alpha_2=0 α1−α2=0即 α 1 = α 2 ( 2 ) \alpha_1=\alpha_2(2) α1=α2(2)
由式(1)(2)得 α 1 = α 2 = 1 \alpha_1=\alpha_2=1 α1=α2=1
则 w = Σ α i y i x i = α 1 ∗ 1 ∗ [ 1 , 1 ] + α 2 ∗ ( − 1 ) ∗ [ 0 , 0 ] = α 1 ∗ [ 1 , 1 ] = [ 1 , 1 ] w=\Sigma\alpha_iy_ix_i=\alpha_1*1*[1,1]+\alpha_2*(-1)*[0,0]=\alpha_1*[1,1]=[1,1] w=Σαiyixi=α1∗1∗[1,1]+α2∗(−1)∗[0,0]=α1∗[1,1]=[1,1]
将
w
w
w和(1,1,+1),(0,0,-1)代入得:
b
=
1
/
2
(
−
1
+
(
−
1
)
)
=
−
1
b = 1/2(-1+(-1))=-1
b=1/2(−1+(−1))=−1
故: g ( x ) = w x + b = x 1 + x 2 − 1 g(x)=wx+b=x_1+x_2-1 g(x)=wx+b=x1+x2−1