机器学习笔记之支持向量机(四)软间隔SVM

引言

前面几节介绍了硬间隔SVM的模型求解过程，本节将介绍软间隔SVM的模型思想。

回顾：硬间隔SVM总结

硬间隔SVM的核心思想即 最大间隔分类器思想。基于该思想构建的数学问题表示如下：
$$\{\begin{array}{l}\underset{\mathcal{W},b}{\min }\frac{1}{2}{\mathcal{W}}^T\mathcal{W}\\ s.t.y^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)\ge 1(i=1,2,\cdots ,N)\end{array}$$
它的求解思路是拉格朗日乘数法，将原问题转化为无约束原问题：
$$\{\begin{array}{l}\underset{\mathcal{W},b}{\min }\underset{\lambda }{\max }\mathcal{L}(\mathcal{W},b,\lambda )\\ s.t.{\lambda }^{(i)}\ge 0(i=1,2,\cdots ,N)\end{array}$$
随后将无约束原问题转化为对偶问题。并分别对$\mathcal{W},b$进行求导，求解最优模型参数${\mathcal{W}}^{\ast }$：
$${\mathcal{W}}^{\ast }=\sum _{i=1}^N{\lambda }^i{y}^{(i)}{x}^{(i)}$$
最终基于$KKT$条件，找出对应的支持向量$(x^{(k)},y^{(k)})$，使得：
$$1-y^{(k)}\left({\mathcal{W}}^T{x}^{(k)}+b\right)=0$$
将${\mathcal{W}}^{\ast }$带入，得到对应$b^{\ast }$结果：
$$\begin{array}{rl}{b}^{\ast }& =y^{(k)}-({\mathcal{W}}^{\ast }{)}^T{x}^{(k)}\\ & =y^{(k)}-\sum _{i=1}^N\left[{\lambda }^{(i)}{y}^{(i)}{\left(x^{(i)}\right)}^T\right]x^{(k)}\end{array}$$
最终得到硬间隔$SVM$的模型：
$$f(\mathcal{W},b)=sign(({\mathcal{W}}^{\ast }{)}^T\mathcal{X}+b^{\ast })$$

软间隔SVM

硬间隔SVM的限制

由于硬间隔的最大间隔分类器思想是基于**数据集合样本均被正确分类的条件下**产生的，对应的约束条件即：
$$y^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)\ge 1(i=1,2,\cdots ,N)$$

但实际情况中，由于噪声的原因，可能导致两类样本之间的界限模糊，从而导致无法使用直线(超平面)将两类样本完整分开。
基于这种情况，如何对硬间隔SVM进行改进。最朴素的思想是：既然无法完整将样本划分，那么允许其出现少量的错误。从而将优化目标确定为：使错误越小越好。
注意这里的’错误‘是可以量化的：错误有大有小。

如何表示分类错误的样本点？基于分类正确的样本点，分类错误样本点$(x^{(j)},y^{(j)})$满足如下要求：
$$y^{(j)}\left({\mathcal{W}}^T{x}^{(j)}+b\right)<1(x^{(j)},y^{(j)})\in Data$$

令损失函数$loss$表示样本点被错误分类的程度。即：样本点在被错误分类的条件下，距离支持向量所在直线(超平面越远)，被错误分类的程度越大。
对$loss$定义结束后，如何对$loss$进行描述：
由于分类错误的样本点，其$y^{(i)}$与对应的${\mathcal{W}}^T{x}^{(i)}+b$之间异号，那么$1-y^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)>0$恒成立，且该值越大，该样本点被分类错误的程度越大。

至此，任意一个样本点$(x^{(i)},y^{(i)})$只存在如下两种情况：

• 如果样本点被分类正确，则$loss=0$；
• 如果是样本点被分类错误，则$loss=1-y^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)$

$$los{s}^{(i)}=\{\begin{array}{l}0if{y}^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)\ge 1\\ 1-y^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)otherwise\end{array}$$

继续观察，发现$los{s}^{(i)}\ge 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)}
继续化简，虽然$los{s}^{(i)}$被划分为两种情况：$0,y^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)$，但是这两种情况在值域中连续。因此，直接定义一个目标函数${\xi }^{(i)}$表示$los{s}^{(i)}$，并附加约束条件：
$${\xi }^{(i)}=1-y^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)s.t.{\xi }^{(i)}\ge 0$$
基于该式，可以统计数据集合中所有样本点的$\xi$结果：
$$\sum _{i=1}^N{\xi }^{(i)}$$
并希望${\sum }_{i=1}^N{\xi }^{(i)}$结果越小越好，该值越小意味着 构建的直线对所有样本点错误分类的程度越低，选择的模型就越准确：

将该结果与硬间隔SVM的目标函数合并，得到新的目标函数：
$$\underset{\mathcal{W},b}{\min }\frac{1}{2}{\mathcal{W}}^T\mathcal{W}+\mathcal{C}\sum _{i=1}^N{\xi }^{(i)}$$
其中$\mathcal{C}$表示一个常数系数；整个式子中只包含$\mathcal{W},b$两个变量。
目标函数更新后，同样需要更新对应的 约束条件：
重新观察${\xi }^{(i)}$，观察该函数是否包含什么实际意义？

• 当${\xi }^{(i)}=0$时，即：$y^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)=1$，这意味着达到恰好将样本分类正确的边界。
  $y^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)=1$的函数图像并不是一条直线，而是关于分类直线(超平面)${\mathcal{W}}^T{x}^{(i)}+b=0$相对称的两条直线(超平面)，并称落在该超平面上的点为支持向量。
• 但前面提到，样本点被分类错误不是没有找好直线(超平面) 的问题，而是基于数据集合噪声的情况，导致不存在一条直线(超平面)能够对所有样本进行完美划分。
• 这些被直线(超平面)分类错误的点满足的条件是：${\xi }^{(i)}>0$。即：
  $$y^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)<1$$
  换句话说，这些错误分类的样本点位于直线(超平面)$y^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)=1$所围成的区域中。而区域外的点都是分类正确的样本点。
• 因此，${\xi }^{(i)}$表示当前被分类错误的样本点$(x^{(i)},y^{(i)})$到超平面$y^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)=1$的距离；而$1-{\xi }^{(i)}$表示被错误分类样本点$(x^{(i)},y^{(i)})$到分类直线${\mathcal{W}}^T{x}^{(i)}+b=0$的距离。

因为${\xi }^{(i)}>0$，所以$1-{\xi }^{(i)}<1$。这意味着确实存在这样一个样本点比分类正确时的支持向量还要靠近分类直线。基于支持向量的定义，即便是分类错误的点，但它依然更靠近${\mathcal{W}}^T{x}^{(i)}+b=0$。因此，支持向量将被更靠近${\mathcal{W}}^T{x}^{(i)}+b=0$的样本点所替代。这个新样本点到${\mathcal{W}}^T{x}^{(i)}+b=0$的距离是：$1-{\xi }^{(i)}$。
因此，被分类错误的样本点$(x^{(i)},y^{(i)})$的约束条件表示如下：
可以理解为：由于分类错误点的存在，导致’支持向量‘所在超平面围成的区域从间隔为1压缩到了$1-{\xi }^{(i)}$;
$$y^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)\ge 1-{\xi }^{(i)}$$

至此，基于软间隔的SVM问题描述如下：
$$\{\begin{array}{l}\underset{\mathcal{W},b}{\min }\frac{1}{2}{\mathcal{W}}^T\mathcal{W}+\mathcal{C}{\sum }_{i=1}^N{\xi }^{(i)}\\ s.t.y^{(i)}\left({\mathcal{W}}^T{x}^{(i)}+b\right)\ge 1-{\xi }^{(i)}\\ {\xi }^{(i)}\ge 0\end{array}$$

后续求解过程与硬间隔SVM的求解过程相同。
至此，支持向量机介绍结束。

相关参考：
机器学习-支持向量机4-软间隔SVM-模型定义