SVM问题再理解与分析——我的角度

欢迎关注我的博客：http://www.cnblogs.com/xujianqing/

支持向量机问题

问题先按照几何间隔最大化的原则引出他的问题为

上面的约束条件就是一个不等式约束，

可以写成

这个是SVM的基本型

对它引入拉格朗日乘子，即对上式添加拉格朗日乘子该问题的拉格朗日函数可以写成：

对偶问题

先定义一个概念：Wolfe对偶：定义问题是凸优化问题的对偶

再定义一个概念：约束规格：

考虑一般约束问题

在式(6)的可行域,在这个约束函数都是可微函数，引进下列两种对约束的限制性条件(约束规格)

1、线性条件：个约束函数都是线性函数

2、梯度无关条件：梯度向量集线性无关，其中为处的有效集

在这里引入一个定理： Wolfe对偶定理：

考虑连续可微的凸优化问题,其中和每一个都是连续可微的凸函数，且定义约束规格中的任意一个约束规格成立，则有以下的：

（1）若原始问题有解，则它的Wolfe对偶问题有解

（2）若原始问题和它的Wolfe对偶问题分别有可行解,则这两个解分别为原始问题和对偶问题最优解的充要条件是它们相应的原始问题和对偶问题的目标函数值相等

对其原始问题引入式中的对偶问题

就是令拉格朗日函数对求偏导数，并令他们等于0

把式（7）中的两个代入原始的拉格朗日函数可得到式：

故得到了SVM基本型的对偶问题为：

求解出后在求出和

由对偶问题解出的是拉格朗日乘子，对应着训练样本，而且需要满足KKT条件，于是就有下式

这里解释了支持向量贡献了超平面的计算和非支持向量对超平面没有影响之间的关系

线性支持向量机与软间隔

在支持向量机中，解决线性不可分问题主要有两种方法：硬间隔核函数空间映射，线性软间隔，一般作用的时候是两者结合起来。

在线性可分的的情况下，支持向量机要求所有的点都要满足约束条件，但是事情往往没有那么完美的满足，在线性不可分的情况下，并不是所有的点都会满足，为了解决这个问题，就引入了一个惩罚项，这个惩罚项对不满足约束条件进行惩罚处理。这里引入一个松弛变量，直观的可以看一下，我们对在分类问题中进行一些调整了，就是把约束条件放宽，原本的约束条件转化为：.当然引入了松弛条件，这时候付出的代价当然要进行相应的调整了，于是我们对分类错误或者分类的效果不满意的点进行了惩罚处理。

这个惩罚处理就体现在了最终需要优化的目标函数当中：软间隔的svm需要优化的目标函数就是：

这里的C就是权衡一下坏点所占有的比重，当时，那时候就强制要求所有的样例点都要满足约束条件，于是上面的问题就转化为一个硬间隔的svm。对式(12)进行优化，代表着两层含义：使得间隔尽量大，同时使得分类点的个数尽量少。

于是软间隔的SVM的原始问题可以描述成下式

式（13）是一个凸二次规划问题，在这里面可以证明得到的解是唯一的，而的解是不唯一的，的解存在于一个区间中，具体证明见书《数据挖掘中的新方法——支持向量机》，当然为了求解式（13）的问题，我们同样要通过求解其对偶问题，从而得到该问题的解。

同样引入拉格朗日函数

对偶问题是拉格朗日的极大极小问题，同样先要求关于 的极小

可得到

上面三个式子代入（14）可得到

再对求的极大，即可得到对偶问题

对约束条件进行转换，消去从而只留下,即后面三个约束条件变为



对偶问题就转为：

这里继续讨论软间隔的SVM的kkt条件，该优化问题具体的kkt条件和原始的KKT条件进行比对理解

损失函数

在软间隔的SVM中引入惩罚项对间隔进行软化，其实惩罚项的系数C含义是权衡惩罚项的比重，但是后面具体的惩罚项只是用一个来表示，却要经过选取，具体的定义就是损失函数

损失函数是评价预测准确度的一种度量，预测:某个假设推断出的结果，损失函数是与假设密切相关的。

常见的损失函数：

0-1损失函数：

此时软间隔的优化函数为：

不敏感损失函数

hinge损失函数 ：,此时的优化函数为：

指数损失函数：

对率损失函数：

在这里证明一下如果在软间隔的SVM中，该原始问题采用的是式(23)的话，

那么其实他的损失函数就是用hinge函数，该函数的作用后面会提，先来证明一下：参考《统计学习方法》李航P114

证明：线性支持向量机原始最优化问题式（23）等价于最优化问题

证明：令

当时



当时







故满足式（23）的约束条件:



最优化问题 可以写成：

取可以得到：



命题得证

所以在用线性支持向量机的时候，我们其实默认的损失函数就是hinge损失函数，它和其他损失函数的图像如下图所示

支持向量

这里又要说到支持向量的概念了，在求解线性支持向量中我们需要满足KKT条件下对问题进行优化，在上述我们给过那个图

对于任意的训练样本总有或者.当时，则该样本不会对结果产生影响；当 时，则，这时候的样本会对结果产生影响，即样本就是支持向量。此时分为两种情况看

,当时，此时由约束条件得到，,此时样本落在间隔的边界上面。这时候损失函数是0

,当时，此时由约束条件得到，,当时，此时样本落在间隔的内部，即两个间隔之间。当时，此时样本错误分类。这时候损失函数起作用，根据样本点的分类情况而定。

所以从上述可以看出对于最终结果的影响是支持向量在起作用，当然这个作用的大小主要看的是该点被分类的效果，因为从合页损失函数的图像来看，只有当分类的效果即的时候，此时的分类效果正好，不被惩罚即损失为0，在分类的效果不好的时候此时的惩罚项起作用，即损失不为0.所以合页函数不仅要分的正确，还要分的具有足够高的置信度，还有因为合页函数在上面为0了，就保证了svm解的稀疏性，就是在分类很正确的情况下，该样本是不会对决策函数产生影响的。大于1的时候损失为0，退化为硬间隔的情况，硬间隔的情况下又因为分类正确，且不是在边界上的点，于是就不起作用了。

当然我们可以把合页损失函数用另外的损失来替换，例如把he页函数替换为对率的时候，这时候由于对率函数连续光滑，这样就算是在后面分类正确的情况下，还是会产生损失，由此这样的点还是会对模型的构建产生影响，于是就是得不到关于支持向量概念的东西。其实这时候的模型会变为一个对率回归的模型。

正如上述，损失函数的性质直接对模型的性质产生影响，由此我们可以用一个更加简洁的方式来表达一下目标函数：

式24的第一项表示这个模型的一些属性，固有属性，是根据先验知识得到的，第二项是这个模型在这个训练集上面的误差项，这里的误差项表示着经验风险，当然我们希望在训练集上面的误差很小，有一种办法就是构造出很完美的第一项出来，它对数据的描述很精确，但是又不希望模型对于这个训练集过度精确的描述，以至于把一些不是通用的特征都学进去。所以我们需要优化的是这两个矛盾的一种同一。所以很多的学习任务，能把优化的目标函数写出来，那才是王道。具体见描述https://www.zhihu.com/question/59461289

VC维概念的理解

VC维

我们在对一个问题进行学习的时候，会得到一些问题的决策函数,但是决策函数是不唯一的，这些决策函数构成的集合就叫做假设集，用来表示。我们通常是从这个假设集里面找一个使得经验风险最小的来作为决策函数。

vc维是度量一个假设集的表达能力的，对于VC维的定义：

先定义几个概念：

(1):这个概念是表示：

设：

1、是一个假设集，理解为决策函数的集合，它们在上取值为-1或者+1

2、就是空间里面的m个点构成的集合

把中的每一个点代入中的一个函数，得到一个m维的向量（f(x_1,\cdots,f(x_m))），其实这个向量就是-1和+1构成的向量,当把里面的所有的都取到后，所得到的不同的m维向量的个数就是

打散：还是上面的和，如果就称为被打散

打散其实可以这样理解：

看上面的图，上面的是二维空间上的线性指示函数

令,上面的图中，被打散，就是如上图所示，当取不同的的时候，那三个点的决策值是不一样的值，可以取编种情况，这样就能说明，被打散

增长函数:

VC维表示的是在空间中能打散的最多的点数。这里的最多是存在性问题。

其实有一个结论：在维空间中中的线性指示函数集合，它的VC维是（反正在求职过程中考过这个问题（某互联网大厂））

支持向量机的总体理解

支持向量机的理论基础是统计学习理论，其实它就是一个结构风险最小化的近似实现，结构风险相当于期望风险的一个上界，它是经验风险和置信区间的和，经验风险依赖于决策函数的选取，但是置信区间是，的VC维的增函数，两者是矛盾的。矛盾体现在：当VC维数变大的时候可以选到更好的使得经验风险比较小，但是此时的置信区间比较大。