相关文章：拉格朗日乘子法
SVM 是支持向量机(Support Vector Machine)的简称。简单来说，支持向量机所做的就是去寻找两类数据之间的分隔线，或者通常称为超平面(hyperplane)。
假设我们有训练样本集
D
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
…
,
(
x
m
,
y
m
)
}
,
y
i
∈
{
−
1
,
+
1
}
D=\left\{\left(\boldsymbol{x}_{1}, y_{1}\right),\left(\boldsymbol{x}_{2}, y_{2}\right), \ldots,\left(\boldsymbol{x}_{m}, y_{m}\right)\right\}, y_{i} \in\{-1,+1\}
D={(x1,y1),(x2,y2),…,(xm,ym)},yi∈{−1,+1}，其中有两类数据。支持向量机是一种算法，把这些点作为输入数据。如果可能的话，输出一条线，来将这些数据分类。
显然，图片中的三条线都能够把不同类别的数据点分隔开，一侧是叉，另一侧是圆圈。但选中的这条线是最好的分割线，为什么呢？
该划分超平面对训练样本局部扰动的"容忍”性最好，它最大化了到最近点的距离，并且对于左右两个类别都是如此。例如，由于训练集的局限性或噪声的因素，训练集外的样本可能比上图中的训练样本更接近两个类的分隔界，这将使许多划分超平面出现错误，而选中的超平面受影响最小。换言之，这个划分超平面所产生的分类结果是最鲁棒的，对未见示例的泛化能力最强。
在样本空间中，划分超平面可通过如下线性方程来描述：
w
T
x
+
b
=
0
\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b=0
wTx+b=0
其中
w
=
(
w
1
;
w
2
;
…
;
w
d
)
\boldsymbol{w}=\left(w_{1} ; w_{2} ; \ldots ; w_{d}\right)
w=(w1;w2;…;wd) 为法向量，决定了超平面的方向；
b
b
b 为位移项，决定了超平面与原点之间的距离。显然，划分超平面可以被法向量
w
\boldsymbol{w}
w 和位移
b
b
b 确定，记为
(
w
,
b
)
(\boldsymbol{w},b)
(w,b)。样本空间中任意点
x
\boldsymbol{x}
x 到超平面
(
w
,
b
)
(\boldsymbol{w},b)
(w,b) 的距离可写为：
r
=
∣
w
T
x
+
b
∣
∥
w
∥
r=\frac{\left|\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b\right|}{\|\boldsymbol{w}\|}
r=∥w∥∣
∣wTx+b∣
∣
假设超平面 ( w , b ) (\boldsymbol{w},b) (w,b) 能将训练样本正确分类，即对于 ( x i , y i ) ∈ D (\boldsymbol{x_i},y_i)\in D (xi,yi)∈D，
则：
{
w
T
x
i
+
b
⩾
+
1
,
y
i
=
+
1
w
T
x
i
+
b
⩽
−
1
,
y
i
=
−
1
\left\{\begin{array}{ll} \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b \geqslant+1, & y_{i}=+1 \\ \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b \leqslant-1, & y_{i}=-1 \end{array}\right.
{wTxi+b⩾+1,wTxi+b⩽−1,yi=+1yi=−1
如下图所示，距离超平面最近的几个圈起来的训练样本点使上面公式的等号成立，它们被称为"支持向量" (support vector)，两个异类支持向量到超平面的距离之和为：
γ
=
2
∥
w
∥
\gamma=\frac{2}{\|\boldsymbol{w}\|}
γ=∥w∥2
而这个距离通常被称之为间隔(margin)，就是线与两个分类中最近点之间的距离。支持向量机首先保证分类正确，在此前提下，再最大化间隔。
欲找到具有最大间隔(maximum margin)的划分超平面，也就是要找到能满足约束的参数
w
\boldsymbol{w}
w 和
b
b
b，使得
γ
\gamma
γ 最大，即：
max
w
,
b
2
∥
w
∥
s.t.
y
i
(
w
T
x
i
+
b
)
⩾
1
,
i
=
1
,
2
,
…
,
m
.
\begin{aligned} \max _{\boldsymbol{w}, b} & \frac{2}{\|\boldsymbol{w}\|} \\ \text { s.t. } & y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1, \quad i=1,2, \ldots, m . \end{aligned}
w,bmax s.t. ∥w∥2yi(wTxi+b)⩾1,i=1,2,…,m.
显然，为了最大化问隔，仅需最大化
∥
w
∥
−
1
\|\boldsymbol{w}\|^{-1}
∥w∥−1，这等价于最小化
∥
w
∥
2
\|\boldsymbol{w}\|^{2}
∥w∥2 . 于是，上式可重写为：
Eq.1：
min
w
,
b
1
2
∥
w
∥
2
s.t.
y
i
(
w
T
x
i
+
b
)
⩾
1
,
i
=
1
,
2
,
…
,
m
.
\begin{aligned} \min _{\boldsymbol{w}, b} & \frac{1}{2}\|\boldsymbol{w}\|^{2} \\ \text { s.t. } & y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1, \quad i=1,2, \ldots, m . \end{aligned}
w,bmin s.t. 21∥w∥2yi(wTxi+b)⩾1,i=1,2,…,m.
这就是支持向量机 (Support Vector Machine，SVM)的基本型。
现在问题来到了如何获得最大化的间隔。我们希望求解式 Eq.1 来得到大间隔划分超平面所对应的模型：
f
(
x
)
=
w
T
x
+
b
f(\boldsymbol{x})=\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b
f(x)=wTx+b
其中
w
\boldsymbol{w}
w 和
b
b
b 是模型参数。Eq.1 本身是一个凸二次规划(convex quadratic programming)问题，能直接用现成的优化计算包求解，但可以用更高效的办法。
可以看到，Eq.1 是有约束项的，对其使用拉格朗日乘子法可得到其对偶问题。具体来说，对 Eq.1 的每条约束添加拉格朗日乘子
α
i
⩾
0
\alpha_i \geqslant 0
αi⩾0，则该问题的拉格朗日函数可写为：
Eq.2：
L
(
w
,
b
,
α
)
=
1
2
∥
w
∥
2
+
∑
i
=
1
m
α
i
(
1
−
y
i
(
w
T
x
i
+
b
)
)
L(\boldsymbol{w}, b, \boldsymbol{\alpha})=\frac{1}{2}\|\boldsymbol{w}\|^{2}+\sum_{i=1}^{m} \alpha_{i}\left(1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)\right)
L(w,b,α)=21∥w∥2+i=1∑mαi(1−yi(wTxi+b))
其中
α
=
(
α
1
;
α
2
;
…
;
α
m
)
\boldsymbol{\alpha}=\left(\alpha_{1} ; \alpha_{2} ; \ldots ; \alpha_{m}\right)
α=(α1;α2;…;αm)。令
L
(
w
,
b
,
α
)
L(\boldsymbol{w}, b, \boldsymbol{\alpha})
L(w,b,α) 对
w
\boldsymbol{w}
w 和
b
b
b 的偏导为零可得
w
=
∑
i
=
1
m
α
i
y
i
x
i
0
=
∑
i
=
1
m
α
i
y
i
\begin{aligned} \boldsymbol{w} &=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i} \\ 0 &=\sum_{i=1}^{m} \alpha_{i} y_{i} \end{aligned}
w0=i=1∑mαiyixi=i=1∑mαiyi
扩展 Eq.2，我们有： 1 2 w ⊤ w ⏞ α ⊤ A α − ∑ i = 1 m α i y i w ⊤ x i ⏞ α ⊤ A α − b ∑ i = 1 m α i y i ⏞ 0 + ∑ i = 1 m α i \frac{1}{2} \overbrace{\boldsymbol{w}^{\top} \boldsymbol{w}}^{\alpha^{\top} A \alpha}-\overbrace{\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{w}^{\top} \boldsymbol{x}_{i}}^{\alpha^{\top} A \alpha}-\overbrace{b \sum_{i=1}^{m} \alpha_{i} y_{i}}^{0}+\sum_{i=1}^{m} \alpha_{i} 21w⊤w α⊤Aα−i=1∑mαiyiw⊤xi α⊤Aα−bi=1∑mαiyi 0+i=1∑mαi
将式子带入 Eq.2，即可将
L
(
w
,
b
,
α
)
L(\boldsymbol{w}, b, \boldsymbol{\alpha})
L(w,b,α) 中的
w
\boldsymbol{w}
w 和
b
b
b 消去，并考虑
0
=
∑
i
=
1
m
α
i
y
i
0 =\sum_{i=1}^{m} \alpha_{i} y_{i}
0=∑i=1mαiyi 的约束，可以得到 Eq.1 的对偶问题：
Eq.3：
max
α
∑
i
=
1
m
α
i
−
1
2
∑
i
=
1
m
∑
j
=
1
m
α
i
α
j
y
i
y
j
x
i
T
x
j
s.t.
∑
i
=
1
m
α
i
y
i
=
0
α
i
⩾
0
,
i
=
1
,
2
,
…
,
m
.
\max _{\boldsymbol{\alpha}} \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j} \\ \text { s.t. } \sum_{i=1}^{m} \alpha_{i} y_{i}=0 \\ \alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m .
αmaxi=1∑mαi−21i=1∑mj=1∑mαiαjyiyjxiTxj s.t. i=1∑mαiyi=0αi⩾0,i=1,2,…,m.
解出
α
\boldsymbol{\alpha}
α 后，求出
w
\boldsymbol{w}
w 和
b
b
b 即可得到模型：
Eq.4：
f
(
x
)
=
w
T
x
+
b
=
∑
i
=
1
m
α
i
y
i
x
i
T
x
+
b
.
\begin{aligned} f(\boldsymbol{x}) &=\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b \\ &=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}+b . \end{aligned}
f(x)=wTx+b=i=1∑mαiyixiTx+b.
从对偶问题 Eq.3 解出的问是式 Eq.2 中的拉格朗日乘子，它正好对应着训练样本
(
x
i
,
y
i
)
(\boldsymbol{x}_{i},y_i)
(xi,yi)。注意到式 Eq.1 中有不等式约束，因此上述过程需满足 KKT(Karush-Kuhn-Tucker)条件，即要求：
{
α
i
⩾
0
y
i
f
(
x
i
)
−
1
⩾
0
α
i
(
y
i
f
(
x
i
)
−
1
)
=
0.
\left\{\begin{array}{l} \alpha_{i} \geqslant 0 \\ y_{i} f\left(\boldsymbol{x}_{i}\right)-1 \geqslant 0 \\ \alpha_{i}\left(y_{i} f\left(\boldsymbol{x}_{i}\right)-1\right)=0 . \end{array}\right.
⎩
⎨
⎧αi⩾0yif(xi)−1⩾0αi(yif(xi)−1)=0.
于是, 对任意训练样本 ( x i , y i ) \left(\boldsymbol{x}_{i}, y_{i}\right) (xi,yi)，总有 α i = 0 \alpha_{i}=0 αi=0 或 y i f ( x i ) = 1 y_{i} f\left(\boldsymbol{x}_{i}\right)=1 yif(xi)=1。若 α i = 0 \alpha_{i}=0 αi=0, 则该样本将不会在式 Eq.4 的求和中出现，也就不会对 f ( x ) f(\boldsymbol{x}) f(x) 有任何影响；若 α i > 0 \alpha_{i}>0 αi>0，则必有 y i f ( x i ) = 1 y_{i} f\left(\boldsymbol{x}_{i}\right)=1 yif(xi)=1，所对应的样本点位于最大间隔边界上，是一个支持向量。这显示出支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关。
现在给出一个比较复杂的数据集，它有很多聚集在 x x x 和 y y y 坐标系原点周围的红叉和大部分位于红叉外围的蓝色圆圈组成。根据前面所说支持向量机内容，无法对这组数据给出一个理想的分类结果------这两个类之间不存在明显的线性超平面(不存在线性分隔器来区分这两个类，即很难在两个类之间画一条线)。但实际上，支持向量机可以对这样的数据进行分类。
我们认为我们把数据特征 x x x 和 y y y 输入到一个神奇的大盒子，也就是支持向量机里，输出是一个标签，标签是蓝圈或红叉。现在挑选一个对这组数据有帮助的特征，就是 x 2 + y 2 x^2+y^2 x2+y2。这时现在有一个三维的输入空间。
我们将这个新的
x
2
+
y
2
x^2+y^2
x2+y2 特征称为
z
z
z。这里
x
,
y
x, y
x,y 的超平面与原点之间的距离
z
z
z 始终为非负数。神奇的是，所有红叉离原点的距离都很小；所有蓝圆圈离原点的距离都很大。
这时图中
x
−
z
x-z
x−z 坐标系内的数据是可以线性分割的。更有趣的是，图中线性可分的线对应着原始数据中的圆，它由坐标系中与原点距离相等的一系列点组成。因此，选择一个较为合适的新特征，就能让支持向量机学习圆形的非线性决策面，这是非常神奇的。简单来说，这里用到的方法，就是将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。
上面这种方法看起来确实很有用，但也确实很难，需要写一些新的特征，而支持向量机最棒的一点在于并不需要这么做。
有一种函数，它们接收低纬度的输入空间或特征空间，并将其映射到高维度空间。所以，过去不可线性分隔的内容变为可分隔--------这些函数被称为核函数。该方法被称为核技巧(kernel trick)。
这些不仅是具有特征空间的函数，而且是超过两个输入的函数。应用核函数技巧将输入空间从 x , y x,y x,y 变换到更大的输入空间后，再使用支持向量机对数据点进行分类，得到解以后返回原始空间，这样就能得到一个非线性分隔，这是支持向量机的一个重要优点。
可以便捷地找到最佳的线性分类器或不同类之间的线性分隔线，在更高维度空间应用所谓的核技巧就能够实现一个极其强大的功能-----它是机器学习最主要的技巧之一。
特征映射指的是函数
ϕ
:
R
n
→
R
N
\phi: \mathbb{R}^{n} \rightarrow \mathbb{R}^{N}
ϕ:Rn→RN
ϕ
(
x
)
=
(
ϕ
1
(
x
)
,
…
,
ϕ
N
(
x
)
)
⊤
,
x
∈
R
n
\phi(\mathbf{x})=\left(\phi_{1}(\mathbf{x}), \ldots, \phi_{N}(\mathbf{x})\right)^{\top}, \quad \mathbf{x} \in \mathbb{R}^{n}
ϕ(x)=(ϕ1(x),…,ϕN(x))⊤,x∈Rn
基函数(basis functions)；特征向量而空间
ϕ
(
x
)
:
x
∈
R
n
{\phi(\mathbf{x}):\mathbf{x}\in\mathbb{R}^{n}}
ϕ(x):x∈Rn 被称为特征空间。令
ϕ
(
x
)
\phi(\boldsymbol{x})
ϕ(x) 表示将
x
\boldsymbol{x}
x 映射后的特征向量，于是在特征空间中划分超平面所对应的模型可表示为：
f
(
x
)
=
w
T
ϕ
(
x
)
+
b
f(\boldsymbol{x})=\boldsymbol{w}^{\mathrm{T}} \phi(\boldsymbol{x})+b
f(x)=wTϕ(x)+b
其中
w
\boldsymbol{w}
w 和
b
b
b 是模型参数。
类似式 Eq.1，有
min
w
,
b
1
2
∥
w
∥
2
s.t.
y
i
(
w
T
ϕ
(
x
i
)
+
b
)
⩾
1
,
i
=
1
,
2
,
…
,
m
\begin{aligned} \min _{\boldsymbol{w}, b} & \frac{1}{2}\|\boldsymbol{w}\|^{2} \\ \text { s.t. } & y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \phi\left(\boldsymbol{x}_{i}\right)+b\right) \geqslant 1, \quad i=1,2, \ldots, m \end{aligned}
w,bmin s.t. 21∥w∥2yi(wTϕ(xi)+b)⩾1,i=1,2,…,m
其对偶问题是:
Eq.5：
max
α
∑
i
=
1
m
α
i
−
1
2
∑
i
=
1
m
∑
j
=
1
m
α
i
α
j
y
i
y
j
ϕ
(
x
i
)
T
ϕ
(
x
j
)
s.t.
∑
i
=
1
m
α
i
y
i
=
0
,
α
i
⩾
0
,
i
=
1
,
2
,
…
,
m
.
\max _{\alpha} \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \phi\left(\boldsymbol{x}_{i}\right)^{\mathrm{T}} \phi\left(\boldsymbol{x}_{j}\right) \\ \begin{array}{ll} \text { s.t. } & \sum_{i=1}^{m} \alpha_{i} y_{i}=0, \\ & \alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m . \end{array}
αmaxi=1∑mαi−21i=1∑mj=1∑mαiαjyiyjϕ(xi)Tϕ(xj) s.t. ∑i=1mαiyi=0,αi⩾0,i=1,2,…,m.
求解式 Eq.5 涉及到计算
ϕ
(
x
i
)
T
ϕ
(
x
j
)
\phi\left(\boldsymbol{x}_{i}\right)^{\mathrm{T}} \phi\left(\boldsymbol{x}_{j}\right)
ϕ(xi)Tϕ(xj)，这是样本
x
i
\boldsymbol{x}_{i}
xi 与
x
j
\boldsymbol{x}_{j}
xj 映射到特征空间之后的内积。由于特征空间维数可能很高，甚至可能是无穷维，因此直接计算
ϕ
(
x
i
)
T
ϕ
(
x
j
)
\phi\left(\boldsymbol{x}_{i}\right)^{\mathrm{T}} \phi\left(\boldsymbol{x}_{j}\right)
ϕ(xi)Tϕ(xj) 通常是困难的。为了避开这个障碍，可以设想这样一个函数:
κ
(
x
i
,
x
j
)
=
⟨
ϕ
(
x
i
)
,
ϕ
(
x
j
)
⟩
=
ϕ
(
x
i
)
T
ϕ
(
x
j
)
\kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\left\langle\phi\left(\boldsymbol{x}_{i}\right), \phi\left(\boldsymbol{x}_{j}\right)\right\rangle=\phi\left(\boldsymbol{x}_{i}\right)^{\mathrm{T}} \phi\left(\boldsymbol{x}_{j}\right)
κ(xi,xj)=⟨ϕ(xi),ϕ(xj)⟩=ϕ(xi)Tϕ(xj)
即
x
i
\boldsymbol{x}_{i}
xi 与
x
j
\boldsymbol{x}_{j}
xj 在特征空间的内积等于它们在原始样本空间中通过函数
κ
(
⋅
,
⋅
)
\kappa(\cdot, \cdot)
κ(⋅,⋅) 计算的结果。有了这样的函数, 我们就不必直接去计算高维甚至无穷维特征空间中的内积，于是式 Eq.5 可重写为：
max
α
∑
i
=
1
m
α
i
−
1
2
∑
i
=
1
m
∑
j
=
1
m
α
i
α
j
y
i
y
j
κ
(
x
i
,
x
j
)
s.t.
∑
i
=
1
m
α
i
y
i
=
0
,
α
i
⩾
0
,
i
=
1
,
2
,
…
,
m
.
\begin{aligned} \max _{\alpha} & \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \\ \text { s.t. } & \sum_{i=1}^{m} \alpha_{i} y_{i}=0, \\ & \alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m . \end{aligned}
αmax s.t. i=1∑mαi−21i=1∑mj=1∑mαiαjyiyjκ(xi,xj)i=1∑mαiyi=0,αi⩾0,i=1,2,…,m.
求解后即可得到：
f
(
x
)
=
w
T
ϕ
(
x
)
+
b
=
∑
i
=
1
m
α
i
y
i
ϕ
(
x
i
)
T
ϕ
(
x
)
+
b
=
∑
i
=
1
m
α
i
y
i
κ
(
x
,
x
i
)
+
b
\begin{aligned} f(\boldsymbol{x}) &=\boldsymbol{w}^{\mathrm{T}} \phi(\boldsymbol{x})+b \\ &=\sum_{i=1}^{m} \alpha_{i} y_{i} \phi\left(\boldsymbol{x}_{i}\right)^{\mathrm{T}} \phi(\boldsymbol{x})+b \\ &=\sum_{i=1}^{m} \alpha_{i} y_{i} \kappa\left(\boldsymbol{x}, \boldsymbol{x}_{i}\right)+b \end{aligned}
f(x)=wTϕ(x)+b=i=1∑mαiyiϕ(xi)Tϕ(x)+b=i=1∑mαiyiκ(x,xi)+b
这里的函数
κ
(
⋅
,
⋅
)
\kappa(\cdot, \cdot)
κ(⋅,⋅) 就是 核函数(kernel function)。上式显示出模型最优解可通过训练样本的核函数展开，这一展式也被称为支持向量展式(support vector expansion)。显然，若已知合适映射
ϕ
(
⋅
)
\phi(\cdot)
ϕ(⋅) 的具体形式, 则可写出核函数
κ
(
⋅
,
⋅
)
\kappa(\cdot, \cdot)
κ(⋅,⋅)，但在现实任务中我们通常不知道
ϕ
(
⋅
)
\phi(\cdot)
ϕ(⋅) 是什么形式。我们希望样本在特征空间内线性可分，因此特征空间的好坏对支持向量机的性能至关重要。需注意的是，在不知道特征映射的形式时，我们并不知道什么样的核函数是合适的，而核函数也仅是隐式地定义了这个特征空间。于是，"核函数选择"成为支持向量机的最大变数。若核函数选择不合适，则意味着将样本映射到了一个不合适的特征空间，很可能导致性能不佳。
名称 表达式 参数 线性核 κ ( x i , x j ) = x i T x j 多项式核 κ ( x i , x j ) = ( x i T x j ) d d ⩾ 1 为多项式的次数 高斯核 κ ( x i , x j ) = exp ( − ∥ x i − x j ∥ 2 2 σ 2 ) σ > 0 为高斯核的带宽(width) 拉普拉斯核 κ ( x i , x j ) = exp ( − ∥ x i − x j ∥ σ ) σ > 0 Sigmoid 核 κ ( x i , x j ) = tanh ( β x i T x j + θ ) tanh 为双曲正切函数, β > 0 , θ < 0 \begin{array}{lll} \hline \text { 名称 } & \text { 表达式 } & \text { 参数 } \\ \hline \text { 线性核 } & \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j} & \\ \text { 多项式核 } & \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\left(\boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}\right)^{d} & d \geqslant 1 \text { 为多项式的次数 } \\ \text { 高斯核 } & \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\exp \left(-\frac{\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|^{2}}{2 \sigma^{2}}\right) & \sigma>0 \text { 为高斯核的带宽(width) } \\ \text { 拉普拉斯核 } & \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\exp \left(-\frac{\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|}{\sigma}\right) & \sigma>0 \\ \text { Sigmoid 核 } & \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\tanh \left(\beta \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}+\theta\right) & \tanh \text { 为双曲正切函数, } \beta>0, \theta<0 \\ \hline \end{array} 名称 线性核 多项式核 高斯核 拉普拉斯核 Sigmoid 核 表达式 κ(xi,xj)=xiTxjκ(xi,xj)=(xiTxj)dκ(xi,xj)=exp(−2σ2∥xi−xj∥2)κ(xi,xj)=exp(−σ∥xi−xj∥)κ(xi,xj)=tanh(βxiTxj+θ) 参数 d⩾1 为多项式的次数 σ>0 为高斯核的带宽(width) σ>0tanh 为双曲正切函数, β>0,θ<0
此外, 还可通过函数组合得到, 例如:
若
κ
1
\kappa_{1}
κ1 和
κ
2
\kappa_{2}
κ2 为核函数, 则对于任意正数
γ
1
\gamma_{1}
γ1、
γ
2
\gamma_{2}
γ2，其线性组合也是核函数：
γ
1
κ
1
+
γ
2
κ
2
\gamma_{1} \kappa_{1}+\gamma_{2} \kappa_{2}
γ1κ1+γ2κ2
若
κ
1
\kappa_{1}
κ1 和
κ
2
\kappa_{2}
κ2 为核函数，则核函数的直积也是核函数：
κ
1
⊗
κ
2
(
x
,
z
)
=
κ
1
(
x
,
z
)
κ
2
(
x
,
z
)
\kappa_{1} \otimes \kappa_{2}(\boldsymbol{x}, \boldsymbol{z})=\kappa_{1}(\boldsymbol{x}, \boldsymbol{z}) \kappa_{2}(\boldsymbol{x}, \boldsymbol{z})
κ1⊗κ2(x,z)=κ1(x,z)κ2(x,z)
若
κ
1
\kappa_{1}
κ1 为核函数，则对于任意函数
g
(
x
)
g(\boldsymbol{x})
g(x) 也是核函数：
κ
(
x
,
z
)
=
g
(
x
)
κ
1
(
x
,
z
)
g
(
z
)
\kappa(\boldsymbol{x}, \boldsymbol{z})=g(\boldsymbol{x}) \kappa_{1}(\boldsymbol{x}, \boldsymbol{z}) g(\boldsymbol{z})
κ(x,z)=g(x)κ1(x,z)g(z)
有时候，似乎支持向量机无法对某些问题进行正确分类。例如，可能有这样的一个数据集，很显然，将两个类分割的决策面是不存在的，可以将下面的这个点当作 outlier。所以问题是，这时候希望支持向量机怎么做？
最好的情况，就是作出一个决策边界，直接把错误分类的那一点放在另一边-----支持向量机完全可以做到这一点，他们经常能找到一条决策边界，使两个数据集的间隔最大化同时容忍个别异常值，就像这里所展示的。
在前面的讨论中，一直假定训练样本在样本空间或特征空间中是线性可分的，即存在一个超平面能将不同类的样本完全划分开。然而，在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分；退一步说，即使恰好找到了某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合所造成的。
缓解该问题的一个办法是允许支持向量机在一些样本上出错。为此，要引入软间隔(soft margin)的概念。如图所示，红色圈出了一些不满足约束的样本：
前面介绍的支持向量机形式是要求所有样本均满足约束，使所有样本都必须划分正确，这称为硬间隔(hard margin)，而软间 隔则是允许某些样本不满足约束条件：
y
i
(
w
T
x
i
+
b
)
⩾
1
y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1
yi(wTxi+b)⩾1。
在最大化间隔的同时，不满足约束的样本应尽可能少。于是，优化目标可写为：
Eq.6：
min
w
,
b
1
2
∥
w
∥
2
+
C
∑
i
=
1
m
ℓ
0
/
1
(
y
i
(
w
T
x
i
+
b
)
−
1
)
\min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \ell_{0 / 1}\left(y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)-1\right)
w,bmin21∥w∥2+Ci=1∑mℓ0/1(yi(wTxi+b)−1)
其中
C
>
0
C>0
C>0 是一个常数,
ℓ
0
/
1
\ell_{0 / 1}
ℓ0/1 是 “
0
/
1
0 / 1
0/1 损失函数”
ℓ
0
/
1
(
z
)
=
{
1
,
if
z
<
0
0
,
otherwise
\ell_{0 / 1}(z)=\left\{\begin{array}{ll} 1, & \text { if } z<0 \\ 0, & \text { otherwise } \end{array}\right.
ℓ0/1(z)={1,0, if z<0 otherwise
当 C C C 取无限大时，式 Eq.6 迫使所有样本均满足约束；而当 C C C 取有限值时，Eq.6 允许一些样本不满足约束。
然而，
ℓ
0
/
1
\ell_{0 / 1}
ℓ0/1 非凸、非连续，数学性质不太好，使得式 Eq.6 不易直接求解。于是，人们通常用其他一些函数来代替
ℓ
0
/
1
\ell_{0 / 1}
ℓ0/1，称为替代损失(surrogate loss)。替代损失函数一般具有较好的数学性质，如它们通常是凸的连续函数且是
ℓ
0
/
1
\ell_{0 / 1}
ℓ0/1 的上界。下图给出了三种常用的替代损失函数：
即：
若采用 hinge 损失，则式 Eq.6 变成：
min
w
,
b
1
2
∥
w
∥
2
+
C
∑
i
=
1
m
m
a
x
(
0
,
1
−
y
i
(
w
T
x
i
+
b
)
)
\min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} max\left(0,1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)\right)
w,bmin21∥w∥2+Ci=1∑mmax(0,1−yi(wTxi+b))
引入松弛变量(slack variables)
ξ
i
⩾
0
\xi_i \geqslant 0
ξi⩾0，可将上面公式重写为：
min
w
,
b
,
ξ
i
1
2
∥
w
∥
2
+
C
∑
i
=
1
m
ξ
i
s.t.
y
i
(
w
T
x
i
+
b
)
⩾
1
−
ξ
i
ξ
i
⩾
0
,
i
=
1
,
2
,
…
,
m
.
\begin{aligned} \min _{\boldsymbol{w}, b, \xi_{i}} & \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \xi_{i} \\ \text { s.t. } & y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1-\xi_{i} \\ & \xi_{i} \geqslant 0, i=1,2, \ldots, m . \end{aligned}
w,b,ξimin s.t. 21∥w∥2+Ci=1∑mξiyi(wTxi+b)⩾1−ξiξi⩾0,i=1,2,…,m.
这就是常用的 软间隔支持向量机。
创建分类器时要传递到形参的自变量称为实参。在 SVM 中，参数就是 核 和即将要讨论的另外连个参数：
C
C
C(软间隔) 和
γ
\gamma
γ(正则化)。下图中的两个 SVM 有不同的核函数，其中左侧的那个是线性函数(linear)，右侧的那个是径向基函数(rbf)：
SVM 的一个重要参数是
C
C
C 参数，它会在光滑的决策边界以及尽可能正确分类所有训练点两者之间进行平衡。假设我们的数据如下图：
可以画出可能是非常直的线，其代价是有少数的点分类错误；也可以画出相当曲折的线，基本上所有的训练点都被分类正确。然而，选择一个复杂模型是有代价的-------像这样复杂的模型，可能有一定的概率对于测试集的泛化能力不够。有些会稍微直一些、稍微更直接些，在开始观察测试集的准确度时可能实际上是更好的选择。
C C C 值越大，就意味着对更多训练点进行正确分类。实际上其含义就是 C C C 值越大，就可以得到更复杂的决策边界。它可以弯曲绕过单独的数据点尽可能让所有训练的分类都正确。但代价是，可能比想要的结果复杂一些。希望决策边界的形状接近于直线的程度有多少、希望如何平衡光滑决策边界和训练点正确分类这两者，这些是机器学习的很关键的灵活部分。
γ \gamma γ 定义单个训练样本对结果作用范围的远近，较小的 γ \gamma γ 值意味着每个点都可能对最终结果产生作用；反之，较大的 γ \gamma γ 值意味着训练样本只对距离较近的决策边界有影响。
如下图中，如果 γ \gamma γ 值较大，决策边界的具体细节将取决于距离边界非常近的点。这些影响结果的数据点非常接近边界，在一定程度上忽略了距离决策边界较远的点。如果 γ \gamma γ 值较小，那么即使距离决策边界较远的点，也会对决策边界具体形状产生影响。这样造成的影响在于，尤其对于 γ \gamma γ 较大的情况下 会给出一条相当曲折的决策边界。
也就是说，
γ
\gamma
γ 值较大时，近距离的点极大改变了决策边界的方向，从而最终使该点位于边界正确的一侧；如果
γ
\gamma
γ 值较小，靠近决策边界的这些点的重要程度会相对降低。这时下图例子中，最终得到的决策边界线性度和平滑度更高、曲折的程度则更低。
注意，线性核只能使用参数 C C C 来调优；而对于非线性核，可以调整 C C C 和 γ \gamma γ！
下图这个例子中，决策边界非常复杂，像这样的情形，被称为过拟合。这是机器学习中常见的。
举个例子，在下面这一组数据，看起来可以被图中绿色的直线分隔。而图中有一个在红色与蓝色之间的黑色决策面，红蓝数据被正确分类，但决策面的其他很多位置看上去非常奇怪。如果仅仅是照搬原始数据对其进行分类，机器学习算法就会产生类似的复杂结果，而不是产生像直线这样的简单结果，这就意味着出现了过拟合。
在机器学习中，要避免过拟合。控制过拟合的方法之一就是，通过调整算法中的参数
c
c
c，
γ
\gamma
γ 以及 核函数。
对于具有明显的分隔边界的复杂数据支持向量机的表现十分出色；对于海量数据，它们的表现不太好-----------因为在这种规模的数据集中，训练时间与数据量的三次方成正比。对于数据集噪声过大情况，支持向量机的效果也不好。
所以，如果类之间的重叠较多，且需要将不同类分隔开，此时朴素贝叶斯分类器会更有效。
所以，拥有的数据集和可用特征上，如果有一个海量数据集且有很多特征，现成的支持向量机程序运行速度可能会很慢，数据中的某些噪声也可能会导致过拟合现象。所以，需要在测试数据集上进行测试看看它的表现如何，接下来这个训练后的模型就可以用了。
支持向量机(SVMs) 是一套用于分类、回归和异常值检测的监督学习方法。
支持向量机的优点有：
支持向量机的缺点有：
SVC、NuSVC 和 LinearSVC 是能够对数据集进行二分类和多分类的类。
SVC 和 NuSVC 是类似的方法，但接受的参数集略有不同，且有不同的数学公式(见数学公式部分)。而 LinearSVC 是支持向量分类在线性核的情况下的另一个(更快的)实现。请注意，LinearSVC 不接受参数 kernel，因为它被认为是线性的。它也缺少 SVC 和 NuSVC 的一些属性，比如 support_。
与其他分类器一样，SVC、NuSVC 和 LinearSVC 使用两个数组作为输入:一个数组 X(n_samples，n_features) 包含训练样本，一个数组 y (n_samples) 包含类标签(字符串或整数)：
>>> from sklearn import svm
>>> X = [[0, 0], [1, 1]]
>>> y = [0, 1]
>>> clf = svm.SVC()
>>> clf.fit(X, y)
SVC()
在经过拟合后，该模型可以用来预测新的值：
>>> clf.predict([[2., 2.]])
array([1])
支持向量机的决策函数依赖于训练数据的某个子集，称为支持向量。这些支持向量的一些性质可以在属性 support_vectors_、support_ 和 n_support_ 中找到。
>>> # get support vectors
>>> clf.support_vectors_
array([[0., 0.],
[1., 1.]])
>>> # get indices of support vectors
>>> clf.support_
array([0, 1]...)
>>> # get number of support vectors for each class
>>> clf.n_support_
array([1, 1]...)
SVC 和 NuSVC 实现了“一对一”的多类分类方法。总共构造了 n_classes * (n_classes - 1) / 2 个分类器，每个分类器从两个类中训练数据。为了提供与其他分类器一致的接口，decision_function_shape 选项允许将“一对一”分类器的结果单调地转换为“一对其余”的形状(n_samples, n_classes) 决策函数。
>>> X = [[0], [1], [2], [3]]
>>> Y = [0, 1, 2, 3]
>>> clf = svm.SVC(decision_function_shape='ovo')
>>> clf.fit(X, Y)
SVC(decision_function_shape='ovo')
>>> dec = clf.decision_function([[1]])
>>> dec.shape[1] # 4 classes: 4*3/2 = 6
6
>>> clf.decision_function_shape = "ovr"
>>> dec = clf.decision_function([[1]])
>>> dec.shape[1] # 4 classes
4
LinearSVC 实现的“一对其余”的多类策略，也训练了 n_classes 模型。
>>> lin_clf = svm.LinearSVC()
>>> lin_clf.fit(X, Y)
LinearSVC()
>>> dec = lin_clf.decision_function([[1]])
>>> dec.shape[1]
4