赞
踩
支持向量机(Support Vector Machine,简称SVM)算法是一种分类算法,SVM算法的基本想法就是在特征空间中找到一个超平面将不同类别的样本分开,它的基本模型是指在特征空间中,使得不同类的样本的间隔最大的线性分类器。SVM算法是用来解决二分类问题的有监督学习算法,在引入了核方法后其也可以用来解决非线性问题。本文主要围绕线性可分支持向量机展开。 由于其在解决小样本、非线性及高维数据集中展现出许多特有的优势,因此其被广泛应用于各个领域。
给定样本集
D
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
m
,
y
m
)
}
D=\{(x_1,y_1),(x_2,y_2),\ldots,(x_m,y_m)\}
D={(x1,y1),(x2,y2),…,(xm,ym)},
y
i
∈
{
−
1
,
1
}
y_i\in\{-1,1\}
yi∈{−1,1},其中
x
i
x_i
xi表示样本特征,
y
i
y_i
yi表示样本标签。学习的目的就是在特征空间中可以找到一个分离超平面,能将样本进行分类,分离超平面对应于方程则为
ω
⋅
x
+
b
=
0
\omega\cdot x+b=0
ω⋅x+b=0,它是由法向量
ω
\omega
ω和截距
b
b
b决定,可以表示为
(
ω
,
b
)
(\omega,b)
(ω,b)。
此时,存在无数个超平面可以将样本分类。一个好的分离超平面应该是有较好的“冗余度”,如上图所示,对于黑色超平面,假如新的样本点比较靠近超平面,那么对其影响就会很大,而对红色超平面的影响就较小,因为红色超平面相对居中,即间隔较大。因此,我们利用最大化间隔来求得最优的分离超平面。接下来本文将对间隔进行介绍。
如下图所示,三角形和圆形分别表示正负样本,其中
◯
\bigcirc
◯表示正类,
△
\triangle
△表示负类,且训练集线性可分,中间的实线则表示使正负样本间隔正确划分且间隔最大的分离超平面。
假如需要预测
A
A
A,
B
B
B,
C
C
C三个点的类别,可以看到,点
A
A
A距离分离超平面比较远,如果预测点
A
A
A为负类样本,那么其预测准确度较高;点
C
C
C距离分离超平面比较近,如果预测点
C
C
C为负类样本,那么其预测准确度较低;点
B
B
B的预测精确度则处于
A
A
A与
C
C
C之间。
我们可以认为,一个点的分类预测的准确度与该点到分类超平面的距离大小是相关的。在分离超平面
ω
⋅
x
+
b
=
0
\omega\cdot x+b=0
ω⋅x+b=0确定的前提下,
∣
ω
⋅
x
+
b
∣
|\omega\cdot x+b|
∣ω⋅x+b∣可以相对地表示该点到超平面的距离大小,然后
ω
⋅
x
+
b
\omega\cdot x+b
ω⋅x+b的符号与标签
y
y
y的符号是否一致可以表示该点的分类是否正确,如果两者符号一致,则表明分类正确,反之即表明分类错误。将两者相结合,
y
(
ω
⋅
x
+
b
)
y(\omega\cdot x+b)
y(ω⋅x+b)既可以表示分类的正确性还可以表示分类的准确度,这个就是函数间隔(functional margin)。
对于函数间隔,给定训练集
D
D
D和超平面
(
ω
,
b
)
(\omega,b)
(ω,b),样本点
(
x
i
,
y
i
)
(x_i,y_i)
(xi,yi)所对应的函数间隔为:
γ
^
i
=
y
i
(
ω
⋅
x
i
+
b
)
\widehat{\gamma}_i=y_i(\omega\cdot x_i+b)
γ
i=yi(ω⋅xi+b)而对于训练集
D
D
D的函数间隔,这里取训练集
D
D
D中全部样本的函数间隔的最小值,即:
γ
^
=
min
γ
^
i
\widehat{\gamma}=\min\widehat{\gamma}_i
γ
=minγ
i 然而在选择最优分离超平面时,仅靠函数间隔是不够的的,因为只要成比例的改变
ω
\omega
ω和
b
b
b,例如将它们改为
3
ω
3\omega
3ω和
3
b
3b
3b,该超平面没有改变,但是函数间隔却变成了原来的3倍。这样子的话,就不能保证最优分离超平面的唯一性。为了解决该状况,我们对分离超平面的法向量
ω
\omega
ω加一定的约束限制,如规范化,令
∣
∣
ω
∣
∣
=
1
||\omega||=1
∣∣ω∣∣=1,使得间隔是确定的,此时函数间隔就变成了几何间隔(geometric margin)。
如果给出超平面
(
ω
,
b
)
(\omega,b)
(ω,b)以及其法向量
ω
\omega
ω,那么一个点到该超平面的距离为:
γ
i
=
ω
∣
∣
ω
∣
∣
⋅
x
i
+
b
∣
∣
ω
∣
∣
\gamma_i=\frac{\omega}{||\omega||}\cdot x_i+\frac{b}{||\omega||}
γi=∣∣ω∣∣ω⋅xi+∣∣ω∣∣b其中
∣
∣
ω
∣
∣
||\omega||
∣∣ω∣∣表示
ω
\omega
ω的
L
2
L_2
L2范数,当然上式是在
y
i
=
+
1
y_i=+1
yi=+1时的距离。
因此对于给定的样本集
D
D
D和超平面
(
ω
,
b
)
(\omega,b)
(ω,b),定义超平面
(
ω
,
b
)
(\omega,b)
(ω,b)关于样本点
(
x
i
,
y
i
)
(x_i,y_i)
(xi,yi)的几何间隔为:
γ
i
=
y
i
(
ω
∣
∣
ω
∣
∣
⋅
x
i
+
b
∣
∣
ω
∣
∣
)
\gamma_i=y_i(\frac{\omega}{||\omega||}\cdot x_i+\frac{b}{||\omega||})
γi=yi(∣∣ω∣∣ω⋅xi+∣∣ω∣∣b)而对于训练集
D
D
D的几何间隔,这里取训练集
D
D
D中全部样本的几何间隔的最小值,即:
γ
=
min
γ
i
\gamma=\min\gamma_i
γ=minγi 我们可以看到,函数间隔与几何间隔有以下的关系:
γ
i
=
γ
^
i
∣
∣
ω
∣
∣
\gamma_i=\frac{\widehat{\gamma}_i}{||\omega||}
γi=∣∣ω∣∣γ
i
γ
=
γ
^
∣
∣
ω
∣
∣
\gamma=\frac{\widehat{\gamma}}{||\omega||}
γ=∣∣ω∣∣γ
从以上关系可以看到,如果
∣
∣
ω
∣
∣
=
1
||\omega||=1
∣∣ω∣∣=1,那么函数间隔与几何间隔相等。此时,如果
ω
\omega
ω和
b
b
b成比例扩大缩小,函数间隔也成比例扩大缩小,但是几何间隔不变。
SVM的基本思路是找到可以正确划分训练集且几何间隔最大的分离超平面。间隔最大化的直观解释是:对训练数据集找到几何间隔最大的超平面意味着以充分大的准确度对训练数据进行分类。通俗的讲,不仅将正负样本完成分类,而且对最难分类的样本(离超平面最近的点)也有足够大的准确度将它们分开。这样的超平面对未知的新样本也有很好的分类预测能力。
为了去找到这一个几何间隔最大的分离超平面,这个问题可以表示为一个约束优化问题:
max
ω
,
b
γ
s
.
t
.
y
i
(
ω
∣
∣
ω
∣
∣
⋅
x
i
+
b
∣
∣
ω
∣
∣
)
⩾
γ
考虑到几何间隔与函数间隔的关系,可以改写为:
max
ω
,
b
γ
^
∣
∣
ω
∣
∣
s
.
t
.
y
i
(
ω
⋅
x
i
+
b
)
⩾
γ
^
min
ω
,
b
1
2
∣
∣
ω
∣
∣
2
s
.
t
.
y
i
(
ω
⋅
x
i
+
b
)
−
1
⩾
0
下图所示为简单的间隔示意图,加粗的样本为支持向量,支持向量是距离分离超平面最近的样本。
对于上述上述的凸二次规划问题,这里使用拉格朗日乘子法求解其对偶问题来得到原始问题的最优解。首先使用拉格朗日乘子法得到其对偶问题。对上式的约束条件添加拉格朗日乘子
α
i
⩾
0
\alpha_i\geqslant 0
αi⩾0,即:
L
(
ω
,
b
,
α
)
=
1
2
∣
∣
ω
∣
∣
2
+
∑
i
=
1
N
α
i
(
1
−
y
i
(
ω
T
x
i
+
b
)
)
L(\boldsymbol\omega,b,\boldsymbol\alpha)= \frac{1}{2}||\omega||^2+\sum _{i=1}^{N}\alpha_i(1-y_i(\omega^Tx_i+b))
L(ω,b,α)=21∣∣ω∣∣2+i=1∑Nαi(1−yi(ωTxi+b))其中
α
=
(
α
1
,
α
2
,
…
,
α
N
)
\boldsymbol\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_N)
α=(α1,α2,…,αN)。令
L
(
ω
,
b
,
α
)
L(\boldsymbol\omega,b,\boldsymbol\alpha)
L(ω,b,α)对
ω
\boldsymbol\omega
ω和
b
b
b的偏导为零可得:
ω
=
∑
i
=
1
N
α
i
y
i
x
i
0
=
∑
i
=
1
N
α
i
y
i
L
(
ω
,
b
,
α
)
=
1
2
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
y
i
y
j
(
x
i
⋅
x
j
)
+
∑
i
=
1
N
α
i
−
∑
i
=
1
N
α
i
y
i
(
(
∑
j
=
1
N
α
j
y
j
x
j
)
⋅
x
i
+
b
)
=
∑
i
=
1
N
α
i
−
1
2
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
y
i
y
j
(
x
i
⋅
x
j
)
max
α
∑
i
=
1
N
α
i
−
1
2
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
y
i
y
j
(
x
i
⋅
x
j
)
s
.
t
.
∑
i
=
1
N
α
i
y
i
=
0
α
i
⩾
0
,
i
=
1
,
2
,
…
,
N
min
α
1
2
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
y
i
y
j
(
x
i
⋅
x
j
)
−
∑
i
=
1
N
α
i
s
.
t
.
∑
i
=
1
N
α
i
y
i
=
0
α
i
⩾
0
,
i
=
1
,
2
,
…
,
N
ω
∗
=
∑
i
=
1
N
α
i
∗
y
i
x
i
\bm\omega^*=\sum_{i=1}^N\alpha_i^*y_ix_i\\
ω∗=i=1∑Nαi∗yixi对于
b
∗
b^*
b∗的求解,我们首先需要找出某个支持向量,即满足
α
j
∗
>
0
\alpha_j^*>0
αj∗>0对应的样本
(
x
j
,
y
j
)
(x_j,y_j)
(xj,yj),然后求得
b
∗
b^*
b∗为:
b
∗
=
y
j
−
∑
i
=
1
N
α
i
∗
y
i
(
x
i
⋅
x
j
)
b^*=y_j-\sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)
b∗=yj−i=1∑Nαi∗yi(xi⋅xj) 假设我们有
S
S
S个支持向量,则对应我们求出
S
S
S个
b
∗
b^*
b∗,理论上这些
b
∗
b^*
b∗都可以作为最终的结果, 但是我们一般采用一种更健壮的办法,即求出所有支持向量所对应的
b
∗
b^*
b∗,然后将其平均值作为最后的结果。
b
∗
=
1
S
∑
i
=
1
S
b
i
∗
b^*=\frac{1}{S}\sum_{i=1}^Sb_i^*
b∗=S1i=1∑Sbi∗ 这样最终的分离超平面为:
w
∗
⋅
x
+
b
∗
=
0
w^∗\cdot x+b^∗=0
w∗⋅x+b∗=0 最终的分类决策函数为:
f
(
x
)
=
s
i
g
n
(
w
∗
⋅
x
+
b
∗
)
f(x)=sign(w^∗\cdot x+b^∗)
f(x)=sign(w∗⋅x+b∗)其中由于原始问题中含有不等式约束,因此上述的过程需要满足KKT条件。
本文将简单介绍KKT条件,考虑标准约束优化问题:
min
f
(
x
)
s
.
t
.
g
j
(
x
)
=
0
,
j
=
1
,
2
,
…
,
m
h
k
(
x
)
≤
0
,
k
=
1
,
2
,
…
,
p
L
(
x
,
λ
j
,
μ
j
)
=
f
(
x
)
+
∑
j
=
1
m
λ
j
g
j
(
x
)
+
∑
k
=
1
p
μ
k
h
k
(
x
)
L(\bm x,\bm \lambda_j,\bm\mu_j)=f(\bm x)+\sum_{j=1}^m \lambda_jg_j(\bm x)+\sum_{k=1}^p \mu_kh_k(\bm x)
L(x,λj,μj)=f(x)+j=1∑mλjgj(x)+k=1∑pμkhk(x)其中
λ
j
\lambda_j
λj是对应
g
j
(
x
)
=
0
g_j(\bm x)=0
gj(x)=0的Lagrange乘子,
μ
k
\mu_k
μk是对应
h
k
(
x
)
≤
0
h_k(\bm x)\leq0
hk(x)≤0的Lagrange乘子。KKT条件包括
∂
L
∂
x
=
0
g
j
(
x
)
=
0
,
j
=
1
,
2
,
…
,
m
h
k
(
x
)
≤
0
,
k
=
1
,
2
,
…
,
p
μ
k
≥
0
μ
k
h
k
(
x
)
=
0
如有错误,欢迎批评指出,谢谢!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。