目录
1.SVM的问题提出
终于讲到大名鼎鼎的支撑向量机（support vector machine）SVM。初见此名，相信大家跟我一样都是满脸的黑人问号，什么是支撑向量，什么又是向量机？切莫着急，听我一一道来。
之前我们在讲线性回归和PLA的时候，着眼点都在能不能正确分类样本，对一个线性可分的样本，我们能找到一个分类面，使所有的样本都正确分类。但是，由于对于线性可分的样本，正确率肯定是100%，我们无法对分类面进行评价，无法知道到底哪一个分类面是最好的。所谓的好，指的就是当一个未知样本放进来的时候，哪一个分类面更有可能将它区分正确。线性SVM为了解决哪一个分类面最好的问题，引入了支持向量的概念。首先，我们看看下面这张图：
黑色的线是分界面。从直观的感觉出发，很显然，第三个分类面应该是最好的。在这个分类面下，两类样本到分类面的最短距离是最大的，也就是说灰色的这条间隙是最大的。对于这个间隙，我的理解是容噪能力。试设想，如果真实的点就是样本点加上噪声，比如高斯噪声，那么我们就在该点边上画一个圆，显然，图三能容纳的圆的半径是要远远大于图一和图二的，因此我们说图三找到的这个分界面优于其他，因为它的容噪能力更强。我们就把处在间隙边缘，也就是到分类面距离为最小距离的点（特征向量），称为支撑向量，可以想象为它们从两边夹住了中间这个间隙。而SVM就是寻找支撑向量、从而获得这个分类面的算法（我不太清楚为什么是向量机，可能是用支撑向量做了一个分类机？）
2.SVM推导与证明
在上一节，我们明确了什么是支撑向量机。那么接下来，问题就变成了怎么样找到这一个分类面了。首先，给出特征向量到分界面
h
(
x
)
h(x)
h(x)的距离公式：
d
(
x
)
=
∥
h
(
x
)
∥
∥
w
∥
=
1
∥
w
∥
∗
∥
w
T
x
+
b
∥
=
1
∥
w
∥
∗
y
∗
(
w
T
x
+
b
)
d(x) = \frac{\|h(x)\|}{\|w\|} = \frac{1}{\|w\|} * \|w^Tx+b\| = \frac{1}{\|w\|} *y*(w^Tx+b)
d(x)=∥w∥∥h(x)∥=∥w∥1∗∥wTx+b∥=∥w∥1∗y∗(wTx+b)
这个公式怎么来的在第一篇PLA有推导，那么SVM的优化目标就可以写作：
max
α
s.t.
y
i
(
w
T
⋅
x
i
+
b
)
≥
0
,
i
=
1
,
2
,
…
,
N
a
=
min
d
(
x
i
)
,
i
=
1
,
2
,
…
,
N
\begin{aligned} &\quad\quad\max \alpha \\ \text { s.t. }\quad &y_{i}\left(w^T \cdot x_{i}+b\right) \geq 0, i=1,2, \ldots, N \\ & a = \min d(x_i) , i = 1,2,\ldots, N \end{aligned}
s.t. maxαyi(wT⋅xi+b)≥0,i=1,2,…,Na=mind(xi),i=1,2,…,N
这个问题还是不好解啊，有一个maxmin在里头。那怎么办？我们假设
min
y
∗
(
w
T
x
+
b
)
=
c
\min y*(w^Tx+b) = c
miny∗(wTx+b)=c,此时的分界面
h
(
x
)
=
w
T
x
+
b
=
0
h(x)=w^Tx+b=0
h(x)=wTx+b=0,我们令将分类面进行缩放，变成
1
c
∗
(
w
T
x
+
b
)
=
0
\frac{1}{c}*(w^Tx+b)=0
c1∗(wTx+b)=0,这两个分类面其实是一样的，将这个式子带入，结果
min
y
∗
(
w
T
x
+
b
)
\min y*(w^Tx+b)
miny∗(wTx+b)就变成了1，但是分类面并没有改变。那么我们就可以人为的使
min
y
∗
(
w
T
x
+
b
)
=
1
\min y*(w^Tx+b)=1
miny∗(wTx+b)=1，因为这并不会改变分类面，上述问题就可以转化为如下问题：
max
w
,
b
1
∥
w
∥
s.t.
y
i
(
w
T
⋅
x
i
+
b
)
≥
1
,
i
=
1
,
2
,
…
,
N
\begin{aligned} &\quad\quad\max _{w, b} \frac{1}{\|w\|} \\\\ \text { s.t. }\quad &y_{i}\left(w^T \cdot x_{i}+b\right) \geq 1, i=1,2, \ldots, N \\ \end{aligned}
s.t. w,bmax∥w∥1yi(wT⋅xi+b)≥1,i=1,2,…,N
max问题并不好解，可以转化为min问题，加上一个系数并不影响结果：
min
w
,
b
1
2
∥
w
∥
2
s.t.
y
i
(
w
T
⋅
x
i
+
b
)
≥
1
,
i
=
1
,
2
,
…
,
N
\begin{aligned} &\quad\quad\min _{w, b} \frac{1}{2}\|w\|^2\\\\ \text { s.t. }\quad &y_{i}\left(w^T \cdot x_{i}+b\right) \geq 1, i=1,2, \ldots, N \\ \end{aligned}
s.t. w,bmin21∥w∥2yi(wT⋅xi+b)≥1,i=1,2,…,N
3.线性SVM求解优化方法
看到我们化简出来的这个式子，其实就是一个典型的二次规划问题，二次规划的标准形式为：
min
q
(
x
)
=
1
2
x
T
G
x
+
x
T
c
s.t.
a
i
T
x
≥
b
i
,
i
∈
τ
\begin{aligned} &\min q(x)=\frac{1}{2} x^{T} G x+x^{T} c\\ \text{s.t.}\quad&\quad a_{i}^{T} x \geq b_{i}, \quad i \in \tau \end{aligned}
s.t.minq(x)=21xTGx+xTcaiTx≥bi,i∈τ
跟上面的式子是一样的，我们只需要令：
x
=
[
b
w
]
;
G
=
[
0
0
d
T
0
d
I
d
]
;
c
=
0
d
+
1
;
a
n
T
=
y
n
[
1
x
n
T
]
;
b
n
=
1
x=\left[\begin{array}{cc} b \\ w \end{array}\right]; G=\left[\begin{array}{cc} 0 & \mathbf{0}_{d}^{T} \\ \mathbf{0}_{d} & \mathrm{I}_{d} \end{array}\right] ; c=\mathbf{0}_{d+1} ; \mathbf{a}_{n}^{T}=y_{n}\left[\begin{array}{ll} 1 & \mathbf{x}_{n}^{T} \end{array}\right] ; b_{n}=1
x=[bw];G=[00d0dTId];c=0d+1;anT=yn[1xnT];bn=1
就把SVM的问题化为了标准的二次规划问题，如果G是一个半正定矩阵，那么就是一个凸优化问题，数学上有很多解法，matlab和python都有相应的包，就不再解释了。