文章目录
1.SVM的基本问题
在样本空间中,划分超平面(又称为决策边界)可以通过如下线性方程表示:
w
T
x
+
b
=
0
w^ Tx+b =0
wTx+b=0
决策边界位于两条虚线超平面的中间,对于位于虚线超平面上的点(称为支持向量),有
w
⋅
x
+
b
=
k
,
w
⋅
x
+
b
=
−
k
w·x+b=k,w·x+b=-k
w⋅x+b=k,w⋅x+b=−k
两个表达式同时除以k,则可以得到:
w
⋅
x
+
b
=
1
,
w
⋅
x
+
b
=
−
1
w·x+b=1,w·x+b=-1
w⋅x+b=1,w⋅x+b=−1
以上就是两条虚线超平面的表达式,1和-1分别表达了这两条虚线到决策超平面的相对距离。
令紫色的支持向量为
x
p
x_{p}
xp,红色的支持向量为
x
r
x_{r}
xr,则有:
w
⋅
x
p
+
b
=
1
,
w
⋅
x
r
+
b
=
−
1
w·x_{p}+b=1, w·x_{r}+b=-1
w⋅xp+b=1,w⋅xr+b=−1
两式相减可得:
w
⋅
(
x
p
−
x
r
)
=
2
w·(x_{p}-x_{r})=2
w⋅(xp−xr)=2
其中
x
p
−
x
r
x_{p}-x_{r}
xp−xr是
x
p
x_{p}
xp、
x
r
x_{r}
xr两点之间的距离,根据线性代数的知识,上式两边同时除以||w||有:
w
⋅
(
x
p
−
x
r
)
∣
∣
w
∣
∣
=
2
∣
∣
w
∣
∣
\frac{w·(x_{p}-x_{r})}{||w||}=\frac{2}{||w||}
∣∣w∣∣w⋅(xp−xr)=∣∣w∣∣2
而
w
⋅
(
x
p
−
x
r
)
∣
∣
w
∣
∣
\frac{w·(x_{p}-x_{r})}{||w||}
∣∣w∣∣w⋅(xp−xr)就是两条虚线之间的距离d,所以有
d
=
2
∣
∣
w
∣
∣
d=\frac{2}{||w||}
d=∣∣w∣∣2
我们的目标是最大化d,那么只要最小化
∣
∣
w
∣
∣
2
||w||^2
∣∣w∣∣2即可。
对于所有紫色的点,有yi=1,w·xi+b≥1;对于所有红色的点,有yi=-1,w·xi+b≤-1。
所以,对所有的点,有yi·(w·xi+b)≥1.
因此SVM求解的问题就转化为:
根据拉格朗日函数及其对偶问题的相关知识,上述问题可以转化为
求出α之后,就可求得w和b,则可得模型
2.核函数
在第一节中,我们假设在当前空间中,这些样本是线性可分的,但有时存在线性不可分的情况;幸运的是,如果原始空间是有限维,即属性数是有限的,那么一定存在一个高维空间使样本线性可分。令Φ(x)表示将x映射到高维空间(称为新空间)后的特征向量,于是在新空间中,划分超平面所对应的模型可表示为
f
(
x
)
=
w
T
Φ
(
x
)
+
b
f(x) = w^TΦ(x)+b
f(x)=wTΦ(x)+b
likewise:
转化为对偶问题
上式涉及到计算Φ(xi)·Φ(xj),由于新空间的维数可能很高,甚至可能是无穷维,因此直接计算是非常困难的,我们使用“核技巧”来解决该问题:
K
(
u
,
v
)
=
Φ
(
u
)
⋅
Φ
(
v
)
K(u,v)=Φ(u)·Φ(v)
K(u,v)=Φ(u)⋅Φ(v)
于是,上面的问题可以写为:
求解后可得到
sklearn中涉及到的核函数有:
3.软间隔
在第一节中,我们所举的样本点,恰好能被一个超平面完全分开,这时称这两类样本点之间存在“硬间隔”;然而,当两组数据几乎完全线性可分,但决策边界在训练集上存在较小的训练误差(比如下图中的红圈样本),这时就成这两类样本点之间存在“软间隔”
这些红圈点并不满足yi·(w·xi+b)≥1,即yi·(w·xi+b)<1。但对于每个红圈点来说,若让决策超平面往上或者往下移动一点(每个点移动的距离不一样),那么就能近似满足约束,即
y
i
⋅
(
w
T
x
+
b
)
≥
1
−
ξ
i
y_{i}·(w^Tx+b)≥1-ξ_i
yi⋅(wTx+b)≥1−ξi
那么我们就把
ξ
i
ξ_i
ξi视为决策超平面对于每个样本点能容忍的犯错程度,当然,在最大化间隔的时候,我们希望不满足约束(即犯错)的样本尽量少,因此优化目标可写为
其中C为用来控制惩罚想的惩罚力度系数。C越大,越不能容忍错误样本点或者说对每个样本点能容忍的犯错程度越小;C越小,能容忍更多的错误样本点或者说对每个样本点能容忍的犯错程度越大。
转化为对偶问题可得: