机器学习笔记之支持向量机——软间隔SVM
- 引言
- 回顾：硬间隔SVM总结
- 软间隔SVM
- 硬间隔SVM的限制
引言
前面几节介绍了硬间隔SVM的模型求解过程，本节将介绍软间隔SVM的模型思想。
回顾：硬间隔SVM总结
硬间隔SVM的核心思想即 最大间隔分类器思想。基于该思想构建的数学问题表示如下：
{
min
W
,
b
1
2
W
T
W
s
.
t
.
y
(
i
)
(
W
T
x
(
i
)
+
b
)
≥
1
(
i
=
1
,
2
,
⋯
,
N
)
\begin{cases}\mathop{\min}\limits_{\mathcal W,b} \frac{1}{2} \mathcal W^{T}\mathcal W \\ s.t. \quad y^{(i)}\left(\mathcal W^{T}x^{(i)} + b\right) \geq 1 \quad (i=1,2,\cdots,N)\end{cases}
⎩
⎨
⎧W,bmin21WTWs.t.y(i)(WTx(i)+b)≥1(i=1,2,⋯,N)
它的求解思路是拉格朗日乘数法，将原问题转化为无约束原问题：
{
min
W
,
b
max
λ
L
(
W
,
b
,
λ
)
s
.
t
.
λ
(
i
)
≥
0
(
i
=
1
,
2
,
⋯
,
N
)
\begin{cases}\mathop{\min}\limits_{\mathcal W,b} \mathop{\max}\limits_{\lambda} \mathcal L(\mathcal W,b,\lambda) \\ s.t. \quad \lambda^{(i)} \geq 0 \quad (i=1,2,\cdots,N)\end{cases}
⎩
⎨
⎧W,bminλmaxL(W,b,λ)s.t.λ(i)≥0(i=1,2,⋯,N)
随后将无约束原问题转化为对偶问题。并分别对
W
,
b
\mathcal W,b
W,b进行求导，求解最优模型参数
W
∗
\mathcal W^{*}
W∗：
W
∗
=
∑
i
=
1
N
λ
i
y
(
i
)
x
(
i
)
\mathcal W^{*} = \sum_{i=1}^N\lambda^{i}y^{(i)}x^{(i)}
W∗=i=1∑Nλiy(i)x(i)
最终基于
K
K
T
KKT
KKT条件，找出对应的支持向量
(
x
(
k
)
,
y
(
k
)
)
(x^{(k)},y^{(k)})
(x(k),y(k))，使得：
1
−
y
(
k
)
(
W
T
x
(
k
)
+
b
)
=
0
1 - y^{(k)}\left(\mathcal W^{T}x^{(k)} + b \right) = 0
1−y(k)(WTx(k)+b)=0
将
W
∗
\mathcal W^*
W∗带入，得到对应
b
∗
b^*
b∗结果：
b
∗
=
y
(
k
)
−
(
W
∗
)
T
x
(
k
)
=
y
(
k
)
−
∑
i
=
1
N
[
λ
(
i
)
y
(
i
)
(
x
(
i
)
)
T
]
x
(
k
)
\begin{aligned} b^* & = y^{(k)} - (\mathcal W^*)^{T}x^{(k)} \\ & =y^{(k)} - \sum_{i=1}^N\left[\lambda^{(i)}y^{(i)}\left(x^{(i)}\right)^{T}\right]x^{(k)} \end{aligned}
b∗=y(k)−(W∗)Tx(k)=y(k)−i=1∑N[λ(i)y(i)(x(i))T]x(k)
最终得到硬间隔
S
V
M
SVM
SVM的模型：
f
(
W
,
b
)
=
s
i
g
n
(
(
W
∗
)
T
X
+
b
∗
)
f(\mathcal W,b) = sign((\mathcal W^*)^{T} \mathcal X + b^*)
f(W,b)=sign((W∗)TX+b∗)
软间隔SVM
硬间隔SVM的限制
由于硬间隔的最大间隔分类器思想是基于**数据集合样本均被正确分类的条件下**产生的，对应的约束条件即：
y
(
i
)
(
W
T
x
(
i
)
+
b
)
≥
1
(
i
=
1
,
2
,
⋯
,
N
)
y^{(i)}\left(\mathcal W^{T}x^{(i)} + b\right) \geq 1 \quad (i=1,2,\cdots,N)
y(i)(WTx(i)+b)≥1(i=1,2,⋯,N)
但实际情况中，由于噪声的原因，可能导致两类样本之间的界限模糊，从而导致无法使用直线(超平面)将两类样本完整分开。
基于这种情况，如何对硬间隔SVM进行改进。最朴素的思想是：既然无法完整将样本划分，那么允许其出现少量的错误。从而将优化目标确定为：使错误越小越好。
注意这里的’错误‘是可以量化的：错误有大有小。
如何表示分类错误的样本点？基于分类正确的样本点，分类错误样本点
(
x
(
j
)
,
y
(
j
)
)
(x^{(j)},y^{(j)})
(x(j),y(j))满足如下要求：
y
(
j
)
(
W
T
x
(
j
)
+
b
)
<
1
(
x
(
j
)
,
y
(
j
)
)
∈
D
a
t
a
y^{(j)}\left(\mathcal W^{T}x^{(j)} + b\right) < 1 \quad (x^{(j)},y^{(j)}) \in Data
y(j)(WTx(j)+b)
0
1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) > 0
1−y(i)(WTx(i)+b)>0恒成立，且该值越大，该样本点被分类错误的程度越大。
至此，任意一个样本点 ( x ( i ) , y ( i ) ) (x^{(i)},y^{(i)}) (x(i),y(i))只存在如下两种情况：
- 如果样本点被分类正确，则 l o s s = 0 loss=0 loss=0；
- 如果是样本点被分类错误，则 l o s s = 1 − y ( i ) ( W T x ( i ) + b ) loss= 1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) loss=1−y(i)(WTx(i)+b)
l o s s ( i ) = { 0 i f y ( i ) ( W T x ( i ) + b ) ≥ 1 1 − y ( i ) ( W T x ( i ) + b ) o t h e r w i s e loss^{(i)} = \begin{cases}0 \quad if \quad y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) \geq 1 \\ 1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) \quad otherwise \end{cases} loss(i)={0ify(i)(WTx(i)+b)≥11−y(i)(WTx(i)+b)otherwise
继续观察，发现
l
o
s
s
(
i
)
≥
0
loss^{(i)} \geq 0
loss(i)≥0恒成立。将上述两种情况进行合并：
l
o
s
s
(
i
)
=
max
{
0
,
1
−
y
(
i
)
(
W
T
x
(
i
)
+
b
)
}
loss^{(i)} = \max \{0,1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right)\}
loss(i)=max{0,1−y(i)(WTx(i)+b)}
继续化简，虽然
l
o
s
s
(
i
)
loss^{(i)}
loss(i)被划分为两种情况：
0
,
y
(
i
)
(
W
T
x
(
i
)
+
b
)
0,y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right)
0,y(i)(WTx(i)+b)，但是这两种情况在值域中连续。因此，直接定义一个目标函数
ξ
(
i
)
\xi^{(i)}
ξ(i)表示
l
o
s
s
(
i
)
loss^{(i)}
loss(i)，并附加约束条件：
ξ
(
i
)
=
1
−
y
(
i
)
(
W
T
x
(
i
)
+
b
)
s
.
t
.
ξ
(
i
)
≥
0
\xi^{(i)} = 1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) \quad s.t. \quad \xi^{(i)} \geq0
ξ(i)=1−y(i)(WTx(i)+b)s.t.ξ(i)≥0
基于该式，可以统计数据集合中所有样本点的
ξ
\xi
ξ结果：
∑
i
=
1
N
ξ
(
i
)
\sum_{i=1}^N\xi^{(i)}
i=1∑Nξ(i)
并希望
∑
i
=
1
N
ξ
(
i
)
\sum_{i=1}^N \xi^{(i)}
∑i=1Nξ(i)结果越小越好，该值越小意味着 构建的直线对所有样本点错误分类的程度越低，选择的模型就越准确：
将该结果与硬间隔SVM的目标函数合并，得到新的目标函数：
min
W
,
b
1
2
W
T
W
+
C
∑
i
=
1
N
ξ
(
i
)
\mathop{\min}\limits_{\mathcal W,b} \frac{1}{2}\mathcal W^{T}\mathcal W + \mathcal C\sum_{i=1}^N \xi^{(i)}
W,bmin21WTW+Ci=1∑Nξ(i)
其中
C
\mathcal C
C表示一个常数系数；整个式子中只包含
W
,
b
\mathcal W,b
W,b两个变量。
目标函数更新后，同样需要更新对应的 约束条件：
重新观察
ξ
(
i
)
\xi^{(i)}
ξ(i)，观察该函数是否包含什么实际意义？
- 当
ξ
(
i
)
=
0
\xi^{(i)} = 0
ξ(i)=0时，即：
y
(
i
)
(
W
T
x
(
i
)
+
b
)
=
1
y^{(i)}\left(\mathcal W^{T}x^{(i)} + b\right) = 1
y(i)(WTx(i)+b)=1，这意味着达到恰好将样本分类正确的边界。
y ( i ) ( W T x ( i ) + b ) = 1 y^{(i)}\left(\mathcal W^{T}x^{(i)} + b\right) = 1 y(i)(WTx(i)+b)=1的函数图像并不是一条直线，而是关于分类直线(超平面) W T x ( i ) + b = 0 \mathcal W^{T}x^{(i)} + b =0 WTx(i)+b=0相对称的两条直线(超平面)，并称落在该超平面上的点为支持向量。 - 但前面提到，样本点被分类错误不是没有找好直线(超平面) 的问题，而是基于数据集合噪声的情况，导致不存在一条直线(超平面)能够对所有样本进行完美划分。
- 这些被直线(超平面)分类错误的点满足的条件是：
ξ
(
i
)
>
0
\xi^{(i)} > 0
ξ(i)>0。即：
y ( i ) ( W T x ( i ) + b ) < 1 y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) < 1 y(i)(WTx(i)+b) 0 \xi^{(i)} > 0 ξ(i)>0，所以 1 − ξ ( i ) < 1 1 - \xi^{(i)}关注打赏查看更多评论
