文章目录
1. 支持向量机核心思想
支持向量机SVM有三宝：间隔，对偶，核技巧
注：核技巧与SVM没有固定的绑定关系，核技巧作用是让SVM从普通的欧式空间映射到高维空间，可以实现非线性的分类
支持向量机的作用是找到一个超平面将上图中的样本进行分类，SVM模型的作用是找到一个超平面
y
=
w
T
x
+
b
(
绿
色
)
y=w^Tx+b(绿色)
y=wTx+b(绿色)，这个超平面具有很好的鲁棒性，不会随着样本的轻微的波动而进行错误的分类；简而言之：我们要找到一个很好的超平面，这个超平面距离两类样本点的距离足够大，由一定的鲁棒性；
支
持
向
量
机
超
平
面
：
f
(
w
)
=
w
T
x
+
b
(1)
支持向量机超平面：f(w)=w^Tx+b\tag{1}
支持向量机超平面：f(w)=wTx+b(1)
2.SVM的分类
- Hard-margin SVM ----> 硬间隔 SVM
- Soft-margin SVM ----->软间隔 SVM
- Kernel SVM ------>核函数 SVM
3.SVM的模型建立-hard-margin SVM 硬间隔
3.1数据集定义
我们定义数据集中由N个样本 D = { ( x i , y i ) } i = 1 N , 其 中 x i ∈ R p ; y i ∈ { − 1 , + 1 } D=\{(x_i,y_i)\}_{i=1}^N,其中x_i \in \mathbb{R}^p;y_i \in\{-1,+1\} D={(xi,yi)}i=1N,其中xi∈Rp;yi∈{−1,+1},我们就是运用一个符号函数将上述样本分成 y 1 = − 1 , y 2 = + 1 ; y_1=-1,y_2=+1; y1=−1,y2=+1;
3.2 求两类样本最小距离点
我们知道，要做最大间隔分类器分两步：
1.间隔，从N个样本中找到一个样本到超平面最小的距离：
m
a
r
g
i
n
(
w
,
b
)
=
m
i
n
i
=
1
,
2
,
.
.
,
n
1
∣
∣
w
∣
∣
(
w
T
x
i
+
b
)
;
f
o
r
{
x
i
,
y
i
}
margin(w,b)=min_{i=1,2,..,n}\frac{1}{||w||}(w^Tx_i+b) ;for\{x_i,y_i\}
margin(w,b)=mini=1,2,..,n∣∣w∣∣1(wTxi+b);for{xi,yi}
2. 最大：求出间隔后，再求最大间隔
w
,
b
m
a
x
x
i
,
i
=
1
,
2
,
.
.
n
;
m
i
n
1
∣
∣
w
∣
∣
(
w
T
x
i
+
b
)
=
w
,
b
m
a
x
x
i
,
i
=
1
,
2
,
.
.
n
;
m
i
n
1
∣
∣
w
∣
∣
(
w
T
x
i
+
b
)
=
w
,
b
m
a
x
1
∣
∣
w
∣
∣
x
i
,
i
=
1
,
2
,
.
.
n
;
m
i
n
[
y
i
(
w
T
x
i
+
b
)
]
(2)
\ {}_{w,b}^{max}\ {}_{x_i,i=1,2,..n;}^{min}{\frac{1}{||w||}(w^Tx_i+b)}=\ {}_{w,b}^{max}\ {}_{x_i,i=1,2,..n;}^{min}{\frac{1}{||w||}(w^Tx_i+b)}=\ {}_{w,b}^{max}\frac{1}{||w||}\ {}_{x_i,i=1,2,..n;}^{min}[y_i(w^Tx_i+b)] \tag{2}
w,bmax xi,i=1,2,..n;min∣∣w∣∣1(wTxi+b)= w,bmax xi,i=1,2,..n;min∣∣w∣∣1(wTxi+b)= w,bmax∣∣w∣∣1 xi,i=1,2,..n;min[yi(wTxi+b)](2)
满足：s.t.:
y
i
(
w
T
x
i
+
b
)
>
0
y_i(w^Tx_i+b)>0
yi(wTxi+b)>0
注：
∵
y
i
(
w
T
x
i
+
b
)
>
0
\because y_i(w^Tx_i+b)>0
∵yi(wTxi+b)>0
∴
一
定
存
在
一
个
数
r
>
0
,
对
于
所
有
样
本
{
(
x
i
,
y
i
)
}
;
其
最
小
值
是
r
；
令
：
M
I
N
[
y
i
(
w
T
x
i
+
b
)
]
=
r
;
\therefore 一定存在一个数r>0,对于所有样本\{(x_i,y_i)\};其最小值是r；令：MIN[y_i(w^Tx_i+b)]=r ;
∴一定存在一个数r>0,对于所有样本{(xi,yi)};其最小值是r；令：MIN[yi(wTxi+b)]=r;
∵
因
为
超
平
面
是
可
以
自
由
缩
放
的
\because 因为超平面是可以*缩放的
∵因为超平面是可以*缩放的
∴
所
以
对
于
超
平
面
来
说
，
w
T
x
i
+
b
=
2
w
T
x
i
+
2
b
\therefore 所以对于超平面来说，w^Tx_i+b=2w^Tx_i+2b
∴所以对于超平面来说，wTxi+b=2wTxi+2b
∴
既
然
都
相
等
，
那
么
我
们
为
了
后
续
方
便
计
算
和
约
束
∣
∣
w
∣
∣
,
就
可
以
令
r
=
1
\therefore 既然都相等，那么我们为了后续方便计算和约束||w||,就可以令r=1
∴既然都相等，那么我们为了后续方便计算和约束∣∣w∣∣,就可以令r=1
w
,
b
m
a
x
1
∣
∣
w
∣
∣
x
i
,
i
=
1
,
2
,
.
.
n
;
m
i
n
[
y
i
(
w
T
x
i
+
b
)
]
=
w
,
b
m
a
x
1
∣
∣
w
∣
∣
(3)
\ {}_{w,b}^{max}\frac{1}{||w||}\ {}_{x_i,i=1,2,..n;}^{min}[y_i(w^Tx_i+b)]= \ {}_{w,b}^{max}\frac{1}{||w||}\tag{3}
w,bmax∣∣w∣∣1 xi,i=1,2,..n;min[yi(wTxi+b)]= w,bmax∣∣w∣∣1(3)
S
.
T
：
y
i
(
w
T
x
i
+
b
)
≥
1
；
i
=
1
,
2
,
.
.
.
,
N
(4)
S.T ：y_i(w^Tx_i+b)\geq1；i=1,2,...,N\tag{4}
S.T：yi(wTxi+b)≥1；i=1,2,...,N(4)
我们一般习惯用最小值表示,并将||w||表示成向量形式||W||=
1
2
w
T
w
\frac{1}{2}w^Tw
21wTw：
3.3最大间隔分类器数学模型(优化问题=凸优化问题convex_optimization)
w
,
b
m
i
n
1
2
w
T
w
;
(5)
\ {}_{w,b}^{min}\frac{1}{2}w^Tw;\tag{5}
w,bmin21wTw;(5)
S
.
T
：
y
i
(
w
T
x
i
+
b
)
≥
1
；
N
个
约
束
：
i
=
1
,
2
,
.
.
.
,
N
(6)
S.T ：y_i(w^Tx_i+b)\geq1；N个约束：i=1,2,...,N\tag{6}
S.T：yi(wTxi+b)≥1；N个约束：i=1,2,...,N(6)
以上是一个凸优化问题，目标函数是二次函数，一共有N个约束，即一个二次规划问题(Quadratic Programming)-QP问题；
3.4 数学模型转换
对于此类问题，我们的思想是借助拉格朗日法将凸优化问题(原问题)转换成对偶问题；
3.4.1 将凸优化问题转换成拉格朗日乘子
原
问
题
:
w
,
b
m
i
n
1
2
w
T
w
;
(7)
原问题:\ {}_{w,b}^{min}\frac{1}{2}w^Tw;\tag{7}
原问题: w,bmin21wTw;(7)
原
问
题
:
S
.
T
：
y
i
(
w
T
x
i
+
b
)
≥
1
；
N
个
约
束
：
i
=
1
,
2
,
.
.
.
,
N
(7)
原问题:S.T ：y_i(w^Tx_i+b)\geq1；N个约束：i=1,2,...,N\tag{7}
原问题:S.T：yi(wTxi+b)≥1；N个约束：i=1,2,...,N(7)
拉
格
朗
日
函
数
:
L
(
w
,
b
,
λ
)
=
1
2
w
T
w
+
∑
i
=
1
N
λ
i
[
1
−
y
i
(
w
T
x
i
+
b
)
]
;
(8)
拉格朗日函数:L(w,b,\lambda)=\frac{1}{2}w^Tw+\sum_{i=1}^{N}\lambda_i[1-y_i(w^Tx_i+b)];\tag{8}
拉格朗日函数:L(w,b,λ)=21wTw+i=1∑Nλi[1−yi(wTxi+b)];(8)
拉
格
朗
日
函
数
:
S
.
T
：
λ
i
≥
0
；
1
−
y
i
(
w
T
x
i
+
b
)
≤
0
(8)
拉格朗日函数:S.T ：\lambda_i\geq0；1-y_i(w^Tx_i+b)\leq 0\tag{8}
拉格朗日函数:S.T：λi≥0；1−yi(wTxi+b)≤0(8)
我们通过拉格朗日乘子法，将原问题中带约束的问题转换成无约束的问题：那么原问题的等价模型如下：
原
问
题
的
等
价
模
型
：
w
,
b
m
i
n
λ
m
a
x
L
(
w
,
b
,
λ
)
(9)
原问题的等价模型：\ {}_{w,b}^{min}\ {}_{\lambda}^{max}L(w,b,\lambda) \tag{9}
原问题的等价模型： w,bmin λmaxL(w,b,λ)(9)
原
问
题
的
等
价
模
型
：
s
.
t
：
λ
i
≥
0
(9)
原问题的等价模型：s.t：\lambda_i \geq 0 \tag{9}
原问题的等价模型：s.t：λi≥0(9)
3.4.2 原问题与等价问题解释
将w,b组成的数据几何分成两个部分:令 Δ = 1 − y i ( w T x i + b ) \Delta=1-y_i(w^Tx_i+b) Δ=1−yi(wTxi+b)
情况1：
当
Δ
=
1
−
y
i
(
w
T
x
i
+
b
)
>
0
；
且
λ
i
≥
0
;
则
：
当\Delta=1-y_i(w^Tx_i+b)>0；且\lambda_i \geq 0;则：
当Δ=1−yi(wTxi+b)>0；且λi≥0;则：
λ m a x L ( w , b , λ ) = 1 2 w T w + ∑ i = 1 N λ i [ 1 − y i ( w T x i + b ) ] = 1 2 w T w + ∞ \ {}_{\lambda}^{max}L(w,b,\lambda)=\frac{1}{2}w^Tw+\sum_{i=1}^{N}\lambda_i[1-y_i(w^Tx_i+b)]=\frac{1}{2}w^Tw+\infty λmaxL(w,b,λ)=21wTw+∑i=1Nλi[1−yi(wTxi+b)]=21wTw+∞
情况2：
当
Δ
=
1
−
y
i
(
w
T
x
i
+
b
)
≤
0
；
且
λ
i
≥
0
;
则
：
当\Delta=1-y_i(w^Tx_i+b)\leq0；且\lambda_i \geq 0;则：
当Δ=1−yi(wTxi+b)≤0；且λi≥0;则：
λ m a x L ( w , b , λ ) = 1 2 w T w + ∑ i = 1 N λ i [ 1 − y i ( w T x i + b ) ] = 1 2 w T w + 0 = 1 2 w T w \ {}_{\lambda}^{max}L(w,b,\lambda)=\frac{1}{2}w^Tw+\sum_{i=1}^{N}\lambda_i[1-y_i(w^Tx_i+b)]=\frac{1}{2}w^Tw+0=\frac{1}{2}w^Tw λmaxL(w,b,λ)=21wTw+∑i=1Nλi[1−yi(wTxi+b)]=21wTw+0=21wTw
合并上述问题：
w
,
b
m
i
n
λ
m
a
x
L
(
w
,
b
,
λ
)
=
w
,
b
m
i
n
{
∞
,
1
2
w
T
w
}
=
w
,
b
m
i
n
{
1
2
w
T
w
}
\ {}_{w,b}^{min}\ {}_{\lambda}^{max}L(w,b,\lambda)=\ {}_{w,b}^{min}\{\infty,\frac{1}{2}w^Tw\}=\ {}_{w,b}^{min}\{\frac{1}{2}w^Tw\}
w,bmin λmaxL(w,b,λ)= w,bmin{∞,21wTw}= w,bmin{21wTw}
结 论 ： w , b m i n λ m a x L ( w , b , λ ) = w , b m i n 1 2 w T w 结论：\ {}_{w,b}^{min}\ {}_{\lambda}^{max}L(w,b,\lambda)=\ {}_{w,b}^{min}\frac{1}{2}w^Tw 结论： w,bmin λmaxL(w,b,λ)= w,bmin21wTw
3.4.3对偶问题转换[将原问题 -> 对偶问题]
原
问
题
：
w
,
b
m
i
n
λ
m
a
x
L
(
w
,
b
,
λ
)
;
λ
i
≥
0
；
相
当
于
凤
尾
原问题：\ {}_{w,b}^{min}\ {}_{\lambda}^{max}L(w,b,\lambda);\lambda_i \geq0；相当于凤尾
原问题： w,bmin λmaxL(w,b,λ);λi≥0；相当于凤尾
对
偶
问
题
：
λ
m
a
x
w
,
b
m
i
n
L
(
w
,
b
,
λ
)
;
λ
i
≥
0
；
相
当
于
鸡
头
对偶问题：\ {}_{\lambda}^{max}\ {}_{w,b}^{min}L(w,b,\lambda);\lambda_i \geq0；相当于鸡头
对偶问题： λmax w,bminL(w,b,λ);λi≥0；相当于鸡头
我们可以用凤尾永远大于鸡头来形象
凤
尾
≥
鸡
头
[
弱
对
偶
关
系
]
凤尾\geq鸡头[弱对偶关系]
凤尾≥鸡头[弱对偶关系]
凤
尾
=
鸡
头
[
强
对
偶
关
系
]
；
满
足
K
K
T
条
件
情
况
下
的
凸
优
化
问
题
凤尾=鸡头[强对偶关系]；满足KKT条件情况下的凸优化问题
凤尾=鸡头[强对偶关系]；满足KKT条件情况下的凸优化问题
强
对
偶
问
题
下
的
等
价
模
型
：
λ
m
a
x
w
,
b
m
i
n
L
(
w
,
b
,
λ
)
;
λ
i
≥
0
(10)
强对偶问题下的等价模型：\ {}_{\lambda}^{max}\ {}_{w,b}^{min}L(w,b,\lambda);\lambda_i \geq0 \tag{10}
强对偶问题下的等价模型： λmax w,bminL(w,b,λ);λi≥0(10)