机器学习笔记之支持向量机(四)软间隔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,bmin​21​WTWs.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​λmax​L(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,bmin​21​WTW+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)}