带松弛变量的SVM
线性支持向量机的软间隔最大化模型
不完全线性可分
实际问题中，数据不一定完全线性可分。
数据线性可分，但间隔小
左图：少量样本被错分但间隔大
右图：样本被完全分对，但间隔小
样本完全线性可分时： y i ( w T x i + b ) ≥ 1 y_i ( \mathbf{w}^T \mathbf{x}_i + b) \ge 1 yi(wTxi+b)≥1
实际问题中，数据未必完全线性可分，因此有了软间隔(soft margin)的概念，它允许样本分错，即允许样本不满足约束，落实到约束条件，引入松弛变量(slack variables)
ξ
i
≥
0
\xi_i \ge 0
ξi≥0，使得
y
i
(
w
T
x
i
+
b
)
≥
1
−
ξ
i
y_i ( \mathbf{w}^T \mathbf{x}_i + b ) \ge 1 - \xi_i
yi(wTxi+b)≥1−ξi
当然我们不希望约束放得太松，因此会要求
ξ
i
\xi_i
ξi尽可能低，反映到优化问题本身，就变成下面的数学形式：
min
w
,
b
,
C
1
2
∣
∣
w
∣
∣
2
2
+
C
∑
i
=
1
N
ξ
i
s
.
t
.
y
i
(
w
T
x
i
+
b
)
≥
1
−
ξ
i
,
i
=
1
,
2
,
⋯
,
N
ξ
i
≥
0
,
i
=
1
,
2
,
⋯
,
N
\begin{aligned} &\min_{\mathbf{w}, b, C} \frac{1}{2}||\mathbf{w}||_2^2 + C\sum_{i=1}^N \xi_i \\ s.t. \quad y_i( \mathbf{w}^T& \mathbf{x}_i + b ) \ge 1-\xi_i, \quad i = 1,2,\cdots,N \\ &\xi_i \ge 0, \quad i = 1,2,\cdots,N \end{aligned}
s.t.yi(wTw,b,Cmin21∣∣w∣∣22+Ci=1∑Nξixi+b)≥1−ξi,i=1,2,⋯,Nξi≥0,i=1,2,⋯,N
参数
C
>
0
C \gt 0
C>0是惩罚项系数，它控制间隔和松弛变量惩罚项之间的平衡，
C
C
C越大，对误分类的惩罚越大，反之，则误分类的惩罚越小。实际应用中，参数
C
C
C需要调参确定。
现在的优化目标变为：间隔尽可能大的同时样本被误分类的程度尽可能小。
软间隔最大化目标函数的优化
和硬间隔线性可分SVM的优化方式类似，先用拉格朗日乘子法，将目标函数变成：
L
(
w
,
b
,
ξ
,
α
,
μ
)
=
1
2
∣
∣
w
∣
∣
2
2
+
C
∑
i
=
1
N
ξ
i
−
∑
i
=
1
N
α
i
[
y
i
(
w
T
x
i
+
b
)
−
1
+
ξ
i
]
−
∑
i
=
1
N
μ
i
ξ
i
L(\mathbf{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu}) = \frac{1}{2}||\mathbf{w}||_2^2 + C\sum_{i=1}^N \xi_i - \sum_{i=1}^N \alpha_i[ y_i(\mathbf{w}^T\mathbf{x}_i+b) - 1+ \xi_i ] - \sum_{i=1}^N \mu_i \xi_i
L(w,b,ξ,α,μ)=21∣∣w∣∣22+Ci=1∑Nξi−i=1∑Nαi[yi(wTxi+b)−1+ξi]−i=1∑Nμiξi
使优化问题变为
min
w
,
b
,
ξ
max
α
,
μ
L
(
w
,
b
,
ξ
,
α
,
μ
)
s
.
t
.
ξ
i
≥
0
,
i
=
1
,
2
,
⋯
,
N
α
i
≥
0
,
i
=
1
,
2
,
⋯
,
N
μ
i
≥
0
,
i
=
1
,
2
,
⋯
,
N
\begin{aligned} &\min_{\mathbf{w}, b, \boldsymbol{\xi}} \max_{\boldsymbol{\alpha}, \boldsymbol{\mu}} L(\mathbf{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu}) \\ s.t. \quad &\xi_i \ge 0, \quad i=1,2,\cdots,N \\ &\alpha_i \ge 0, \quad i=1,2,\cdots,N \\ &\mu_i \ge 0, \quad i=1,2,\cdots,N \end{aligned}
s.t.w,b,ξminα,μmaxL(w,b,ξ,α,μ)ξi≥0,i=1,2,⋯,Nαi≥0,i=1,2,⋯,Nμi≥0,i=1,2,⋯,N
优化问题满足KKT条件，可以等价为对偶问题
max
α
,
μ
min
w
,
b
,
ξ
L
(
w
,
b
,
ξ
,
α
,
μ
)
s
.
t
.
ξ
i
≥
0
,
i
=
1
,
2
,
⋯
,
N
α
i
≥
0
,
i
=
1
,
2
,
⋯
,
N
μ
i
≥
0
,
i
=
1
,
2
,
⋯
,
N
\begin{aligned} &\max_{\boldsymbol{\alpha}, \boldsymbol{\mu}} \min_{\mathbf{w}, b, \boldsymbol{\xi}} L(\mathbf{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu}) \\ s.t. \quad& \xi_i \ge 0, \quad i=1,2,\cdots,N \\ &\alpha_i \ge 0, \quad i=1,2,\cdots,N \\ &\mu_i \ge 0, \quad i=1,2,\cdots,N \end{aligned}
s.t.α,μmaxw,b,ξminL(w,b,ξ,α,μ)ξi≥0,i=1,2,⋯,Nαi≥0,i=1,2,⋯,Nμi≥0,i=1,2,⋯,N
先求目标函数的极小化问题，
L
(
w
,
b
,
ξ
,
α
,
μ
)
L(\mathbf{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu})
L(w,b,ξ,α,μ)对参数求偏导得：
{
∂
L
∂
w
=
0
⇒
w
=
∑
i
=
1
N
α
i
y
i
x
i
∂
L
∂
b
=
0
⇒
∑
i
=
1
N
α
i
y
i
=
0
∂
L
∂
ξ
i
=
0
⇒
C
−
α
i
−
μ
i
=
0
\left\{ \begin{aligned} &\frac{\partial L}{\partial \mathbf{w}} = 0 \Rightarrow \mathbf{w} = \sum_{i=1}^N\alpha_i y_i \mathbf{x}_i \\ &\frac{\partial L}{\partial b} = 0 \Rightarrow \sum_{i=1}^N \alpha_i y_i = 0 \\ &\frac{\partial L}{\partial \xi_i} = 0 \Rightarrow C - \alpha_i - \mu_i = 0 \end{aligned} \right.
⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧∂w∂L=0⇒w=i=1∑Nαiyixi∂b∂L=0⇒i=1∑Nαiyi=0∂ξi∂L=0⇒C−αi−μi=0
令
ψ
(
α
,
μ
)
=
min
w
,
b
,
ξ
L
(
w
,
b
,
ξ
,
α
,
μ
)
\psi(\boldsymbol{\alpha}, \boldsymbol{\mu}) = \min_{\mathbf{w}, b, \boldsymbol{\xi}} L(\mathbf{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu})
ψ(α,μ)=w,b,ξminL(w,b,ξ,α,μ)
把以上偏导结果代回
L
(
w
,
b
,
ξ
,
α
,
μ
)
L(\mathbf{w}, b, \boldsymbol{\xi}, \boldsymbol{\alpha}, \boldsymbol{\mu})
L(w,b,ξ,α,μ)，有
ψ
(
α
,
μ
)
=
1
2
∣
∣
w
∣
∣
2
2
+
C
∑
i
=
1
N
ξ
i
−
∑
i
=
1
N
α
i
[
y
i
(
w
T
x
i
+
b
)
−
1
+
ξ
i
]
−
∑
i
=
1
N
μ
i
ξ
i
=
1
2
∣
∣
w
∣
∣
2
2
+
∑
i
=
1
N
C
ξ
i
−
∑
i
=
1
N
α
i
[
y
i
(
w
T
x
i
+
b
)
−
1
+
ξ
i
]
−
∑
i
=
1
N
μ
i
ξ
i
=
1
2
∣
∣
w
∣
∣
2
2
+
∑
i
=
1
N
(
α
i
+
μ
i
)
ξ
i
−
∑
i
=
1
N
α
i
[
y
i
(
w
T
x
i
+
b
)
−
1
+
ξ
i
]
−
∑
i
=
1
N
μ
i
ξ
i
=
1
2
∣
∣
w
∣
∣
2
2
−
∑
i
=
1
N
α
i
[
y
i
(
w
T
x
i
+
b
)
−
1
+
ξ
i
]
+
∑
i
=
1
N
α
i
ξ
i
=
1
2
∣
∣
w
∣
∣
2
2
−
∑
i
=
1
N
α
i
[
y
i
(
w
T
x
i
+
b
)
−
1
]
=
1
2
w
T
w
−
∑
i
=
1
N
α
i
y
i
w
T
x
i
−
∑
i
=
1
N
α
i
y
i
b
+
∑
i
=
1
N
α
i
=
1
2
w
T
∑
i
=
1
N
α
i
y
i
x
i
−
w
T
∑
i
=
1
N
α
i
y
i
x
i
−
b
∑
i
=
1
N
α
i
y
i
+
∑
i
=
1
N
α
i
=
−
1
2
w
T
∑
i
=
1
N
α
i
y
i
x
i
+
∑
i
=
1
N
α
i
=
−
1
2
(
∑
j
=
1
N
α
j
y
j
x
j
)
T
∑
i
=
1
N
α
i
y
i
x
i
+
∑
i
=
1
N
α
i
=
∑
i
=
1
N
α
i
−
1
2
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
y
i
y
j
x
j
T
x
i
=
∑
i
=
1
N
α
i
−
1
2
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
y
i
y
j
x
i
T
x
j
\begin{aligned} \psi(\boldsymbol{\alpha}, \boldsymbol{\mu}) = & \frac{1}{2} ||\mathbf{w}||_2^2 + C \sum_{i=1}^N \xi_i - \sum_{i=1}^N \alpha_i [ y_i (\mathbf{w}^T\mathbf{x}_i+b) - 1+ \xi_i ] - \sum_{i=1}^N \mu_i \xi_i \\ =& \frac{1}{2} ||\mathbf{w}||_2^2 + \sum_{i=1}^N C \xi_i - \sum_{i=1}^N \alpha_i[ y_i (\mathbf{w}^T \mathbf{x}_i+b) - 1 + \xi_i ] - \sum_{i=1}^N \mu_i \xi_i \\ =& \frac{1}{2} ||\mathbf{w} ||_2^2 + \sum_{i=1}^N (\alpha_i + \mu_i) \xi_i - \sum_{i=1}^N \alpha_i [ y_i(\mathbf{w}^T\mathbf{x}_i+b) - 1+ \xi_i ] - \sum_{i=1}^N \mu_i \xi_i \\ =& \frac{1}{2} ||\mathbf{w} ||_2^2 - \sum_{i=1}^N \alpha_i[ y_i (\mathbf{w}^T \mathbf{x}_i+b) - 1+ \xi_i ] + \sum_{i=1}^N \alpha_i \xi_i \\ =& \frac{1}{2} ||\mathbf{w} ||_2^2 - \sum_{i=1}^N \alpha_i[ y_i (\mathbf{w}^T \mathbf{x}_i+b) - 1] \\ =& \frac{1}{2} \mathbf{w}^T \mathbf{w} - \sum_{i=1}^N \alpha_i y_i \mathbf{w}^T \mathbf{x}_i - \sum_{i=1}^N \alpha_i y_i b + \sum_{i=1}^N \alpha_i \\ =& \frac{1}{2} \mathbf{w}^T \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i - \mathbf{w}^T \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i - b \sum_{i=1}^N \alpha_i y_i + \sum_{i=1}^N \alpha_i \\ =& -\frac{1}{2} \mathbf{w}^T \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i + \sum_{i=1}^N \alpha_i \\ =& -\frac{1}{2} (\sum_{j=1}^N \alpha_j y_j \mathbf{x}_j)^T \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i + \sum_{i=1}^N \alpha_i \\ =& \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j \mathbf{x}_j^T \mathbf{x}_i \\ =& \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j \mathbf{x}_i^T \mathbf{x}_j \\ \end{aligned}
ψ(α,μ)===========21∣∣w∣∣22+Ci=1∑Nξi−i=1∑Nαi[yi(wTxi+b)−1+ξi]−i=1∑Nμiξi21∣∣w∣∣22+i=1∑NCξi−i=1∑Nαi[yi(wTxi+b)−1+ξi]−i=1∑Nμiξi21∣∣w∣∣22+i=1∑N(αi+μi)ξi−i=1∑Nαi[yi(wTxi+b)−1+ξi]−i=1∑Nμiξi21∣∣w∣∣22−i=1∑Nαi[yi(wTxi+b)−1+ξi]+i=1∑Nαiξi21∣∣w∣∣22−i=1∑Nαi[yi(wTxi+b)−1]21wTw−i=1∑NαiyiwTxi−i=1∑Nαiyib+i=1∑Nαi21wTi=1∑Nαiyixi−wTi=1∑Nαiyixi−bi=1∑Nαiyi+i=1∑Nαi−21wTi=1∑Nαiyixi+i=1∑Nαi−21(j=1∑Nαjyjxj)Ti=1∑Nαiyixi+i=1∑Nαii=1∑Nαi−21i=1∑Nj=1∑NαiαjyiyjxjTxii=1∑Nαi−21i=1∑Nj=1∑NαiαjyiyjxiTxj
目标函数和硬间隔线性可分SVM的完全一样，参数也只剩下
α
\boldsymbol{\alpha}
α。
目标函数已经消去参数 ξ \boldsymbol{\xi} ξ，所以对应的约束条件 ξ i ≥ 0 \xi_i \ge 0 ξi≥0可以去掉。
现在优化问题的数学形式变成
max
α
,
μ
∑
i
=
1
N
α
i
−
1
2
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
y
i
y
j
x
i
T
x
j
s
.
t
.
∑
i
=
1
N
α
i
y
i
=
0
C
−
α
i
−
μ
i
=
0
,
i
=
1
,
2
,
⋯
,
N
α
i
≥
0
,
i
=
1
,
2
,
⋯
,
N
μ
i
≥
0
,
i
=
1
,
2
,
⋯
,
N
\begin{aligned} \max_{\boldsymbol{\alpha}, \boldsymbol{\mu}} \sum_{i=1}^N \alpha_i - \frac{1}{2} &\sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j \mathbf{x}_i^T \mathbf{x}_j \\ s.t. \quad\quad\quad\quad\quad \sum_{i=1}^N \alpha_i &y_i = 0 \\ C - \alpha_i - \mu_i = 0&, \quad i=1, 2,\cdots,N \\ \alpha_i \ge 0&, \quad i=1, 2,\cdots,N \\ \mu_i \ge 0&, \quad i=1, 2,\cdots,N \end{aligned}
α,μmaxi=1∑Nαi−21s.t.i=1∑NαiC−αi−μi=0αi≥0μi≥0i=1∑Nj=1∑NαiαjyiyjxiTxjyi=0,i=1,2,⋯,N,i=1,2,⋯,N,i=1,2,⋯,N
对于约束条件
C
−
α
i
−
μ
i
=
0
,
i
=
1
,
2
,
⋯
,
N
α
i
≥
0
,
i
=
1
,
2
,
⋯
,
N
μ
i
≥
0
,
i
=
1
,
2
,
⋯
,
N
\begin{aligned} C - \alpha_i - \mu_i = 0, \quad i=1, 2,\cdots,N \\ \alpha_i \ge 0, \quad i=1, 2,\cdots,N \\ \mu_i \ge 0, \quad i=1, 2,\cdots,N \end{aligned}
C−αi−μi=0,i=1,2,⋯,Nαi≥0,i=1,2,⋯,Nμi≥0,i=1,2,⋯,N
为了简化，去掉
μ
i
\mu_i
μi，只剩下
0
≤
α
i
≤
C
0 \le \alpha_i \le C
0≤αi≤C。
目标函数已经不含参数 μ \boldsymbol{\mu} μ，与其有关的约束条件也可以消除的话，整个优化问题就只剩下参数 α \boldsymbol{\alpha} α，这样优化问题的求解就简便多了。
目标函数变号，变成求最小值，最终优化问题的数学形式如下：
min
α
1
2
∑
i
=
1
N
∑
j
=
1
N
α
i
α
j
y
i
y
j
x
i
T
x
j
−
∑
i
=
1
N
α
i
s
.
t
.
∑
i
=
1
N
α
i
y
i
=
0
0
≤
α
i
≤
C
,
i
=
1
,
2
,
⋯
,
N
\begin{aligned} \min_{\boldsymbol{\alpha}} \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j& y_i y_j \mathbf{x}_i^T \mathbf{x}_j - \sum_{i=1}^N \alpha_i \\ s.t. \quad\quad\quad\quad\quad \sum_{i=1}^N \alpha_i &y_i = 0 \\ 0 \le \alpha_i \le C, \quad& i=1, 2,\cdots,N \end{aligned}
αmin21i=1∑Nj=1∑Nαiαjs.t.i=1∑Nαi0≤αi≤C,yiyjxiTxj−i=1∑Nαiyi=0i=1,2,⋯,N
与硬间隔线性可分SVM相比，软间隔线性可分SVM的优化问题数学形式仅仅多了一个约束条件
0
≤
α
i
≤
C
0 \le \alpha_i \le C
0≤αi≤C，依然可以通过SMO算法来求解最优解
α
∗
\boldsymbol{\alpha}^*
α∗，从而求得
w
∗
=
∑
i
=
1
N
α
i
∗
y
i
x
i
\mathbf{w}^* = \sum_{i=1}^N\alpha_i^* y_i \mathbf{x}_i
w∗=i=1∑Nαi∗yixi
对于参数
b
b
b，能像硬间隔SVM模型那样取任一支持向量
(
x
k
,
y
k
)
(\mathbf{x}_k,y_k)
(xk,yk)，代入
y
k
(
w
T
x
k
+
b
)
=
1
y_k (\mathbf{w}^T \mathbf{x}_k + b) = 1
yk(wTxk+b)=1来求解吗？
不行，因为软间隔SVM模型的支持向量并不都在最大间隔边界 y k ( w T x k + b ) = 1 y_k (\mathbf{w}^T \mathbf{x}_k + b) = 1 yk(wTxk+b)=1上（原因会在下一节讲），所以需要找到最大间隔边界上的任一支持向量 ( x k , y k ) (\mathbf{x}_k, y_k) (xk,yk)，代入 w ∗ \mathbf{w}^* w∗得到
b ∗ = y k − w ∗ T x k b^* = y_k - {\mathbf{w}^*}^T \mathbf{x}_k b∗=yk−w∗Txk
软间隔最大化模型的支持向量
由于引入了松弛变量 ξ i \xi_i ξi，软间隔最大化时的支持向量要较为复杂。
根据软间隔SVM模型的部分KKT条件：
α
i
[
1
−
ξ
i
−
y
i
(
w
T
x
i
+
b
)
]
=
0
,
i
=
1
,
2
,
⋯
,
N
μ
i
ξ
i
=
0
,
i
=
1
,
2
,
⋯
,
N
y
i
(
w
T
x
i
+
b
)
≥
1
−
ξ
i
,
i
=
1
,
2
,
⋯
,
N
ξ
i
≥
0
,
i
=
1
,
2
,
⋯
,
N
α
i
≥
0
,
i
=
1
,
2
,
⋯
,
N
μ
i
≥
0
,
i
=
1
,
2
,
⋯
,
N
\begin{aligned} \alpha_i [ 1 - \xi_i - y_i(\mathbf{w}^T \mathbf{x}_i + b) ] = 0,&\quad i=1,2,\cdots,N \\ \mu_i \xi_i = 0,&\quad i=1,2,\cdots,N \\ y_i(\mathbf{w}^T \mathbf{x}_i + b) \ge 1 - \xi_i,&\quad i=1,2,\cdots,N \\ \xi_i \ge 0,&\quad i=1,2,\cdots,N \\ \alpha_i \ge 0,&\quad i=1,2,\cdots,N \\ \mu_i \ge 0,&\quad i=1,2,\cdots,N \end{aligned}
αi[1−ξi−yi(wTxi+b)]=0,μiξi=0,yi(wTxi+b)≥1−ξi,ξi≥0,αi≥0,μi≥0,i=1,2,⋯,Ni=1,2,⋯,Ni=1,2,⋯,Ni=1,2,⋯,Ni=1,2,⋯,Ni=1,2,⋯,N
以及约束条件
C
−
α
i
−
μ
i
=
0
0
≤
α
i
≤
C
C - \alpha_i - \mu_i = 0 \\ 0 \le \alpha_i \le C
C−αi−μi=00≤αi≤C
-
如果 α i = 0 \alpha_i=0 αi=0，有 μ i = C ⇒ ξ i = 0 ⇒ y i ( w T x i + b ) ≥ 1 \mu_i = C \Rightarrow \xi_i = 0 \Rightarrow y_i(\mathbf{w}^T \mathbf{x}_i + b) \ge 1 μi=C⇒ξi=0⇒yi(wTxi+b)≥1，样本点 ( x i , y i ) (\mathbf{x}_i,y_i) (xi,yi)在间隔边界上，或者在最大间隔外且被正确分类，它不是支持向量。
-
如果 α i ≠ 0 \alpha_i \ne 0 αi=0，那么 y i ( w T x i + b ) = 1 − ξ i y_i (\mathbf{w}^T \mathbf{x}_i + b) = 1 - \xi_i yi(wTxi+b)=1−ξi，样本点 ( x i , y i ) (\mathbf{x}_i,y_i) (xi,yi)是支持向量。
可以进一步这些支持向量分类讨论：
- 如果 0 < α i < C 0 \lt \alpha_i \lt C 0<αi<C，根据 C − α i − μ i = 0 C - \alpha_i - \mu_i = 0 C−αi−μi=0可知 μ i > 0 \mu_i \gt 0 μi>0，由 μ i ξ i = 0 \mu_i \xi_i = 0 μiξi=0得出 ξ i = 0 \xi_i = 0 ξi=0，因此 y i ( w T x i + b ) = 1 y_i (\mathbf{w}^T \mathbf{x}_i + b) = 1 yi(wTxi+b)=1，说明样本点 ( x i , y i ) (\mathbf{x}_i,y_i) (xi,yi)恰好在最大间隔边界上；
- 如果
α
i
=
C
\alpha_i = C
αi=C，根据
C
−
α
i
−
μ
i
=
0
C - \alpha_i - \mu_i = 0
C−αi−μi=0可知
μ
i
=
0
\mu_i = 0
μi=0，由
μ
i
ξ
i
=
0
\mu_i \xi_i = 0
μiξi=0得出
ξ
i
\xi_i
ξi未必为0，即
ξ
i
≥
0
\xi_i \ge 0
ξi≥0：
- 若 0 ≤ ξ i < 1 0 \le \xi_i \lt 1 0≤ξi<1，那么 0 < y i ( w T x i + b ) = 1 − ξ i ≤ 1 0 \lt y_i (\mathbf{w}^T \mathbf{x}_i + b) = 1 - \xi_i \le 1 0<yi(wTxi+b)=1−ξi≤1，说明样本点 ( x i , y i ) (\mathbf{x}_i,y_i) (xi,yi)落在最大间隔边界内部且仍被正确分类；
- 若 ξ i = 1 \xi_i = 1 ξi=1，那么 y i ( w T x i + b ) = 0 y_i (\mathbf{w}^T \mathbf{x}_i + b) = 0 yi(wTxi+b)=0，说明样本点 ( x i , y i ) (\mathbf{x}_i,y_i) (xi,yi)恰好落在分离超平面上，无法被正确分类；
- 若 ξ i > 1 \xi_i \gt 1 ξi>1，那么 y i ( w T x i + b ) = 1 − ξ i < 0 y_i (\mathbf{w}^T \mathbf{x}_i + b) = 1 - \xi_i \lt 0 yi(wTxi+b)=1−ξi<0，说明样本点 ( x i , y i ) (\mathbf{x}_i,y_i) (xi,yi)落在超平面误分类的一侧；
软间隔最大化的线性SVM的算法过程
输入：训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯ , ( x N , y N ) } T=\{(\mathbf{x}_1,y_1), (\mathbf{x}_2,y_2), \cdots, (\mathbf{x}_N,y_N)\} T={(x1,y1),(x2,y2),⋯,(xN,yN)}。
输出：分离超平面和分类决策函数。
算法步骤：
-
选择一个惩罚系数 C > 0 C \gt 0 C>0，构造约束优化问题
min α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j x i T x j − ∑ i = 1 N α i s . t . ∑ i = 1 N α i y i = 0 , i = 1 , 2 , ⋯ , N 0 ≤ α i ≤ C , i = 1 , 2 , ⋯ , N \begin{aligned} \min_{\boldsymbol{\alpha}} \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j& y_i y_j \mathbf{x}_i^T \mathbf{x}_j - \sum_{i=1}^N \alpha_i \\ s.t. \quad \sum_{i=1}^N \alpha_i y_i = 0,& \quad i=1, 2,\cdots,N \\ 0 \le \alpha_i \le C,& \quad i=1, 2,\cdots,N \\ \end{aligned} αmin21i=1∑Nj=1∑Nαiαjs.t.i=1∑Nαiyi=0,0≤αi≤C,yiyjxiTxj−i=1∑Nαii=1,2,⋯,Ni=1,2,⋯,N -
用SMO算法求出优化函数最小时的参数 α ∗ \boldsymbol{\alpha}^* α∗。
-
计算 w ∗ = ∑ i = 1 N α i ∗ y i x i \mathbf{w}^* = \sum_{i=1}^N\alpha_i^* y_i \mathbf{x}_i w∗=∑i=1Nαi∗yixi。
-
寻找一个满足 0 < α k ∗ < C 0 \lt \alpha_k^* \lt C 0<αk∗<C的样本点 ( x k , y k ) (\mathbf{x}_k,y_k) (xk,yk)，计算 b ∗ = y k − w ∗ T x k b^* = y_k - {\mathbf{w}^*}^T \mathbf{x}_k b∗=yk−w∗Txk。
-
求得分离超平面 w ∗ T x + b ∗ = 0 {\mathbf{w}^*}^T \mathbf{x} + b^*=0 w∗Tx+b∗=0和分类决策函数 f ( x ) = sgn ( w ∗ T x + b ∗ ) f(x) = \text{sgn}({\mathbf{w}^*}^T \mathbf{x} + b^*) f(x)=sgn(w∗Tx+b∗)
软间隔最大化模型的一种解释：合页损失+L2正则
合页损失(hinge loss)
合页损失函数表达式
L
h
i
n
g
e
(
x
)
=
{
1
−
x
,
x
<
1
0
,
x
≥
1
L_{hinge}(x)= \left\{ \begin{aligned} 1 - x, \quad x \lt 1 \\ 0, \quad x \ge 1 \end{aligned} \right.
Lhinge(x)={1−x,x<10,x≥1
软间隔最大化模型的一种解释
软间隔最大化模型的优化函数： L ( w , b ) = 1 2 ∣ ∣ w ∣ ∣ 2 2 + C ∑ i = 1 N ξ i L(\mathbf{w}, b) = \frac{1}{2}||\mathbf{w}||_2^2 + C\sum_{i=1}^N \xi_i L(w,b)=21∣∣w∣∣22+C∑i=1Nξi。
根据之前对支持向量的讨论，有
-
对于非支持向量
ξ i = 0 \xi_i = 0 ξi=0， y i ( w T x i + b ) ≥ 1 y_i(\mathbf{w}^T\mathbf{x}_i + b) \ge 1 yi(wTxi+b)≥1。
-
对于支持向量
ξ i ≥ 0 \xi_i \ge 0 ξi≥0， y i ( w T x i + b ) = 1 − ξ i ≤ 1 y_i(\mathbf{w}^T\mathbf{x}_i + b) = 1-\xi_i \le 1 yi(wTxi+b)=1−ξi≤1，有 ξ i = 1 − y i ( w T x i + b ) \xi_i = 1 - y_i(\mathbf{w}^T\mathbf{x}_i + b) ξi=1−yi(wTxi+b)。
ξ
i
\xi_i
ξi能用合页损失表示：
ξ
i
=
L
h
i
n
g
e
(
y
i
(
w
T
x
i
+
b
)
)
=
{
1
−
y
i
(
w
T
x
i
+
b
)
,
y
i
(
w
T
x
i
+
b
)
<
1
0
,
y
i
(
w
T
x
i
+
b
)
≥
1
\xi_i = L_{hinge}(y_i (\mathbf{w}^T \mathbf{x}_i + b))= \left\{ \begin{aligned} 1 - y_i(\mathbf{w}^T\mathbf{x}_i + b), \quad y_i(\mathbf{w}^T\mathbf{x}_i + b) \lt 1 \\ 0, \quad y_i(\mathbf{w}^T\mathbf{x}_i + b) \ge 1 \end{aligned} \right.
ξi=Lhinge(yi(wTxi+b))={1−yi(wTxi+b),yi(wTxi+b)<10,yi(wTxi+b)≥1
这个合页损失要传达的意思是：如果样本点被正确分类，且在间隔区域之外，损失为0；否则损失是 1 − y i ( w T x i + b ) 1 - y_i(\mathbf{w}^T\mathbf{x}_i + b) 1−yi(wTxi+b)。
软间隔最大化模型的优化函数可以写成
L
(
w
,
b
)
=
C
∑
i
=
1
N
L
h
i
n
g
e
(
y
i
(
w
T
x
i
+
b
)
)
+
1
2
∣
∣
w
∣
∣
2
2
\begin{aligned} L(\mathbf{w}, b) &= C \sum_{i=1}^N L_{hinge}(y_i (\mathbf{w}^T\mathbf{x}_i + b)) + \frac{1}{2}||\mathbf{w}||_2^2 \end{aligned}
L(w,b)=Ci=1∑NLhinge(yi(wTxi+b))+21∣∣w∣∣22
对比一般的机器学习模型的目标函数形式：
J
(
θ
)
=
∑
i
=
1
N
L
(
y
i
,
f
(
x
i
;
θ
)
)
+
λ
R
(
θ
)
J(\boldsymbol{\theta})=\sum_{i=1}^N L(y_i,f(\mathbf{x}_i;\boldsymbol{\theta})) + \lambda R(\boldsymbol{\theta})
J(θ)=i=1∑NL(yi,f(xi;θ))+λR(θ)
容易发现他们的形式非常相似。
所以，软间隔最大化模型的SVM可以解释为合页损失+L2正则的机器学习模型。