机器学习之支持向量机SVM Support Vector Machine (一) 线性SVM模型与软硬间隔

        SVM是一种二类分类模型，它的目标是利用训练数据集的间隔最大化找到最优分离超平面。SVM还包括核技巧，使它成为非线性分类器。

        SVM学习方法包含由简至繁的模型：线性可分SVM（硬间隔SVM）、线性SVM（软间隔SVM）、非线性SVM。

        给定训练样本集，分类学习的目标是基于训练集D在样本空间找到一个分离超平面，将不同类别的样本分开。当训练数据集线性可分时，存在无数个分离超平面可将两类数据正确分开，哪个分离超平面最好呢？最优分离超平面可以正确地对训练数据进行分类，也可以对未知数据进行很好的分类。假设分离超平面方程为w∙x+b=0，由法向量w和截距b决定，记为(w, b)。样本空间中任意点x到超平面(w, b)的距离可写为：

        一个点距离分离超平面的远近可以表示分类预测的确信程度。给定一个特定的超平面，可以计算出训练数据集中所有样本点到超平面距离的最小值。间隔（Margin）就是这个距离的二倍。对于线性可分数据集，间隔中间是无点区域，意味着里面不会有任何数据。SVM就是利用间隔最大化求得最优分离超平面，最优超平面有最大的间隔，意味着以充分大的确信度对训练数据进行分类。

        超平面H0划分数据集，满足w∙x+b=0。可以得到两个与H0等距的划分数据集超平面H1和H2，有如下方程：

        由于w和b是可以缩放的，所以让δ=1来简化问题。超平面的约束如下：

        将上述方程写在一起，得到：

 

        距离超平面最近的几个训练样本点使等号成立，它们被称为支持向量。支持向量机由很少的重要的训练样本确定。超平面的间隔为

三、线性可分SVM模型

3.1 原始问题与对偶问题

3.2 KKT条件和支持向量

3.3 线性可分SVM算法过程

四、线性SVM模型与软间隔最大化

4.1 软间隔

        在现实任务中，训练样本并不都是线性可分的，退一步说，即便找到了分离超平面使训练集线性可分，也很难断定不是由于过拟合造成的。缓解该问题的一个办法是允许支持向量机在一些样本上出错，为此引入“软间隔”的概念。前面介绍的支持向量机要求所有样本满足约束
        即所有样本都必须划分正确，这称为“硬间隔”，而软间隔允许某些样本不满足约束，但在最大化间隔的同时，不满足约束的样本应尽可能少。
        对每个样本引入一个松弛变量，使函数间隔加上松弛变量大于等于1。与硬间隔最大化相比，可以看到对样本到超平面的函数距离要求放松了，但每个松弛变量是有代价的，引入惩罚函数C>0。软间隔最大化的SVM学习条件如下：
        惩罚函数C可以理解为回归和分类问题正则化时的参数，C越大，对误分类的惩罚越大，C越小，对误分类的惩罚越小。最小化目标函数包含两层含义，使尽量小即间隔尽量大，同时使误分类点的个数尽量少。
        这是一个凸二次规划问题，关于(w,b,ξ)的解是存在的，可以证明w的解是唯一的，但b的解不唯一，存在于一个区间。假设解为w*和b*，可以得到分离超平面及分类决策函数，这样的模型称为训练样本线性不可分时的线性支持向量机，简称为线性SVM。显然线性SVM包含线性可分SVM，由于现实中训练数据集往往是线性不可分的，线性SVM具有更广的适用性。

4.2 软间隔最大化目标函数的优化

        与线性可分SVM的优化方式类似，首先将软间隔最大化的约束问题用拉格朗日函数转化为无约束问题：
        其中均为拉格朗日系数。要优化的目标函数是
        这个优化目标满足KKT条件，可以通过拉格朗日对偶将优化问题转化为等价的对偶问题求解如下：
        令L(w,b,ξ,α,μ)对w,b,ξ的偏导为零可得
        可以得到
        可以得到对偶问题
        即
        对比硬间隔下的对偶问题可以看出，二者唯一的差别在于对偶变量的约束不同，硬间隔下是，软间隔下是。依然可以通过SMO算法来对上式极小化a，求出w和b。

4.3 软间隔最大化时的支持向量

        硬间隔最大化时，根据KKT条件，如果αi>0，则点在支持向量上。
        软间隔最大化的情况稍微复杂些，KKT条件要求
         

 
 

4.4 软间隔最大化的线性SVM算法过程

        输入：线性样本集
        输出：分离超平面参数w*和b*，分类决策函数。
        算法：
(1) 选择惩罚参数C>0，构造并求解约束最优化问题
(2) 用SMO算法求出上式最小时对应的a*
(3) 计算
(4) 找出所有S个支持向量，即满足，通过，计算出每个支持向量对应的，
(5) 分离超平面
分类决策函数

4.5 损失函数

        最优化问题还有另外一种解释如下：
        其中为损失函数，常用的损失函数有：

        若采用hinge损失，并引入松弛变量，即可得到最优化问题。如果点被正确分类且函数间隔大于1，则损失是0，否则损失是。还可以看出其他损失函数和函数间隔的关系。对于0-1损失函数，如果分类正确，损失是0，误分类损失是1。hinge损失函数是0-1损失函数的上界。