线性可分支持向量机
一.理论基础
一.支持向量机分类
SVM 是一种二分类模型， 包含三种类型：线性可分支持向量机，线性支持向量机以及非线性支持向量机；
线性可分支持向量机
：当训练数据可分时， 通过硬间隔最大化， 学习一个线性的分类器
线性支持向量机
：当训练数据近似线性可分时，通过软间隔最大化，学习一个线性的分类器，即线性支持向量机，有又称为软间隔支持向量机
非线性支持向量机
：当训练数据线性不可分时， 通过使用核技巧以及软件个最大化
二.函数间隔与几何间隔
函数间隔
： 对于给定的训练数据集T和超平面（w,b），定义超平面（w,b）关于样本点
(
x
i
,
y
i
)
(x_i,y_i)
(
x
i
,
y
i
)
的函数间隔为
γ
^
i
=
y
i
(
w
⋅
x
i
+
b
)
\hat{\gamma}_i = y_i(w\cdot{x_i} + b)
γ
^
i
=
y
i
(
w
⋅
x
i
+
b
)
定义超平面（w,b）关于训练集T的函数间隔所有样本点的函数间隔最小值，即：
γ
^
=
max
i
=
1
,
.
.
.
.
.
,
N
γ
^
i
\hat{\gamma}= \max \limits_{i=1,…..,N} \hat{\gamma}_i
γ
^
=
i
=
1
,
.
.
.
.
.
,
N
max
γ
^
i
几何间隔
：对于给定的训练数据集T和超平面（w,b），定义超平面（w,b）关于样本点
(
x
i
,
y
i
)
(x_i,y_i)
(
x
i
,
y
i
)
的几何间隔为
γ
i
=
y
i
(
w
∣
∣
w
∣
∣
2
⋅
x
i
+
b
∣
∣
w
∣
∣
2
)
\gamma_i = y_i(\frac{w}{||w||_2}\cdot{x_i} + \frac{b}{||w||_2})
γ
i
=
y
i
(
∣
∣
w
∣
∣
2
w
⋅
x
i
+
∣
∣
w
∣
∣
2
b
)
定义超平面（w,b）关于训练集T的几何间隔所有样本点的几何间隔最小值，即：
γ
=
max
i
=
1
,
.
.
.
.
.
,
N
γ
i
\gamma= \max \limits_{i=1,…..,N} \gamma_i
γ
=
i
=
1
,
.
.
.
.
.
,
N
max
γ
i
三.支持向量
如下图所示，分离超平面为wTx+b=0。和超平面平行的保持一定的函数距离的这两个超平面对应的向量，我们定义为支持向量，如下图虚线所示。支持向量到超平面的距离为
1
∣
∣
w
∣
∣
2
\frac{1}{||w||_2}
∣
∣
w
∣
∣
2
1
,两个支持向量之间的距离为
2
∣
∣
w
∣
∣
2
\frac{2}{||w||_2}
∣
∣
w
∣
∣
2
2
四.线性可分支持向量机
4.1 线性可分支持向量机的优化函数
SVM 的模型 是让所有点到超平面的距离大于一定的距离，也就是所有的分类点要在各自类别的支持向量两边。这个可以表示为约束最优化问题：
max
w
,
b
γ
\max \limits_{w,b} \gamma
w
,
b
max
γ
s
.
t
.
γ
i
=
y
i
(
w
∣
∣
w
∣
∣
2
⋅
x
i
+
b
∣
∣
w
∣
∣
2
)
≥
γ
i
=
1
,
2……
,
N
s.t.\ \ \ \gamma_i = y_i(\frac{w}{||w||_2}\cdot{x_i} + \frac{b}{||w||_2}) \geq \gamma \ \ i={1,2……,N}
s
.
t
.
γ
i
=
y
i
(
∣
∣
w
∣
∣
2
w
⋅
x
i
+
∣
∣
w
∣
∣
2
b
)
≥
γ
i
=
1
,
2
.
.
.
.
.
.
,
N
考虑到几何间隔和函数间隔的关系，上面约束最优化问题可以表示成：
max
w
,
b
γ
^
∣
∣
w
∣
∣
2
\max \limits_{w,b} \frac{\hat\gamma}{||w||_2}
w
,
b
max
∣
∣
w
∣
∣
2
γ
^
s
.
t
.
γ
^
i
=
y
i
(
w
⋅
x
i
+
b
)
≥
γ
^
i
=
1
,
2……
,
N
s.t.\ \ \ \hat{\gamma}_i= y_i(w\cdot{x_i} + b) \geq \hat\gamma \ \ i={1,2……,N}
s
.
t
.
γ
^
i
=
y
i
(
w
⋅
x
i
+
b
)
≥
γ
^
i
=
1
,
2
.
.
.
.
.
.
,
N
通常这里取
γ
^
=
1
\hat\gamma=1
γ
^
=
1
， 最大化
1
∣
∣
w
∣
∣
2
\frac{1}{||w||_2}
∣
∣
w
∣
∣
2
1
和最小化
1
2
∣
∣
w
∣
∣
2
2
\frac{1}{2}||w||^{2}_2
2
1
∣
∣
w
∣
∣
2
2
等价。
SVM的优化函数等价于
min
w
,
b
1
2
∣
∣
w
∣
∣
2
2
\min\limits_{w,b} \frac{1}{2}||w||^{2}_2
w
,
b
min
2
1
∣
∣
w
∣
∣
2
2
s
.
t
.
γ
^
i
=
y
i
(
w
⋅
x
i
+
b
)
−
1
≥
0
i
=
1
,
2……
,
N
s.t.\ \ \ \hat{\gamma}_i= y_i(w\cdot{x_i} + b) – 1\geq 0 \ \ i={1,2……,N}
s
.
t
.
γ
^
i
=
y
i
(
w
⋅
x
i
+
b
)
−
1
≥
0
i
=
1
,
2
.
.
.
.
.
.
,
N
4.2 线性可分支持向量机的最优化问题求解
4.2 .1 线性可分支持向量机的最优化问题转化成对偶最优化问题
目标函数
1
2
∣
∣
w
∣
∣
2
2
\frac{1}{2}||w||^{2}_2
2
1
∣
∣
w
∣
∣
2
2
为凸函数， 同时约束条件不等式是仿函数； 可以通过拉格朗日函数将目标函数转化成无约束的优化函数：
引入拉格朗日乘子后，我们的优化目标变成：
min
w
,
b
max
a
i
≥
0
L
(
w
,
b
,
α
)
\min\limits_{w,b}\max\limits_{a_i \geq 0} L(w,b,\alpha)
w
,
b
min
a
i
≥
0
max
L
(
w
,
b
,
α
)
其对偶问题为极大值极小值问题：
max
a
i
≥
0
min
w
,
b
L
(
w
,
b
,
α
)
\max\limits_{a_i \geq 0} \min\limits_{w,b}L(w,b,\alpha)
a
i
≥
0
max
w
,
b
min
L
(
w
,
b
,
α
)
最终转换成了求解对偶最优化问题， 求解
α
\alpha
α
4.2 .2 对偶最优化问题的解与原问题的解的关系
4.3 线性可分支持向量机学习总结
参考
1.李航 统计学方法
2.支持向量机原理(一) 线性支持向量机
3.约束优化方法之拉格朗日乘子法与KKT条件