【机器学习基础】软间隔支持向量机

问题导读：
1、什么是软间隔支持向量机？
2、核软间隔支持向量机的算法步骤？
3、SVM留一交叉验证误差与支持向量的关系？



引言在上一小节中，我们介绍了核支持向量机。于是，不管是简单的问题还是复杂的问题，我们都可以做得到。
然而，像高斯核的方法太复杂了，可能造成过拟合的问题。导致过拟合的现象的原因有可能是你选择特征转换太强大了，导致无法用最大间隔的方法控制模型的复杂度，还有一个原因是，如果坚持将所有的数据都做到正确分类，这样有可能将噪声也考虑到模型的构建之中，这样就会将噪声拟合进你的结果中去了。
软间隔支持向量机第一步：容忍错误的发生这是硬间隔支持向量机(hard-margin SVM)的基本定义，其中要求所有的数据都要分类正确，并且还要选择w最小的情况：

为了缓解这样的问题，不如我们容忍一些错误的发生，将发生错误的情况加入到目标式子之中，希望能得到一个错分类情况越少越好的结果。其中参数C代表了间隔和犯错情况的相对重要性（即C是对最大间隔[large margin]和噪声容忍度[noise tolerance]的权衡和折中），C比较大的时候代表犯错越少越好，C比较小的时候代表找到的w越短越好，也就是在对的数据上的间隔越宽越好。

这个式子有一个缺点，因为存在判断是非问题(booling problem)的运算，所以这不是一个线性的式子，于是就不能用二次规划的方法来解决。并且这种方法也没法衡量错误的大小。
为了解决这些问题，我们需要提出一个新的式子，这个式子能够区分小错和大错，而且它可以继续使用二次规划的方法来求解。
第二步：对于错误的衡量下面的式子中的ξn是用来衡量数据犯了多大的错误，而不是数据犯了几个错误。并且这样的改变，将ξ作为一个变量加入到式子中去，得到ξ的一次式，这样可以用二次规划的方法来求解。

我们用ξ来记录违规数据距离边界的距离，并将这个距离纳入到最佳化的标准里面。

参数C控制我们到底要多大的边界还是更加在意违反边界的情形越少越好。
越大的C代表，我们宁可边界窄一点，也要违反的数据少一点。
小的C代表，我们希望得到更宽的边界。

第三步：推导对偶问题我们接下来要做的是，推导上面问题的对偶问题，得到了对偶问题就可以很轻易的引入核技巧来轻易地做特征转换(feature transform)。
原始问题是这样的：

由于现在是两个条件，所以我们使用αn和βn来构造拉格朗日函数：

得到了拉格朗日函数后，我们就可以将其转化为对偶问题，并用KKT条件来简化。
我们想对ξn做简化，通过对ξn求偏微分:

这样我们就可以用αn来表示βn了，但是由于βn>0，所以αn还要有一个限制条件：


这样我们就可以去掉ξn和βn两个变量，得到如下的式子：

上面得到的式子就和硬间隔支持向量机的对偶形式很相似了，我们就可以对b和w求偏微分，得到和标准的支持向量机对偶问题几乎一样的答案：

这就是标准的软间隔支持向量机的对偶形式：

与硬间隔支持向量机不同的是，这里的αn有C这个上限的限制。
核软间隔支持向量机接下来，我们得到了核软间隔支持向量机的算法步骤：

这里与之前硬间隔支持向量机不同的是在求b的过程是不一样的。现在因为是一个新的二次规划问题，其KKT条件已经变化了。
求b我们对比一下硬间隔SVM和软间隔SVM的不同：

从上图看到，在求硬间隔SVM的b参数的时候，使用KKT条件中的互补松弛特性(complementary slackness)，根据两个式子相乘为0，当αn>0的时候(即对应支持向量)，求得b的表达式。
现在，我们在观察软间隔SVM的互补松弛特性。
根据上面两个式子，我们令αs不等于C，这样就使得ξs=0。这样我们就可以得到b的式子。
经过上面的一番解释，我们知道，这里要求b，不是像硬间隔SVM中那样要找一个任意的支持向量来计算b，而是找一个自由的支持向量(free SV)，来计算b。

不同的C对应的效果
上面的图像是使用高斯核软间隔SVM，但是不同C的值的不同的分类效果。
当C=1的时候，蓝色区域表示圆圈的区域，红色区域表示红叉的区域，灰色的区域表示边界部分。这里我们看到存在错误的情况。
当C=10的时候，我们通过使用比较大的C来控制，我们希望分类要尽量减少错误，这里我们发现灰色的边界区域变窄了，但是犯错的数据减少了。
当C=100的时候，犯错的数据变少了，但是会出现过拟合的问题。
这告诉我们，要通过选择参数来避免过拟合问题。
αn的物理意义我们可以根据之前的互补松弛特性的两个式子，将数据分成三种情况：

  对于0 < αn < C的情况，ξn=0，这里对应的是在边界上的支持向量的数据
  对于αn=0，ξn=0，这是没有违反边界，被正确分类的数据，这些点在边界的外面
  对于αn=C，这种情形是违反边界的数据，图中用三角标注的数据，我们使用ξn记录下来数据到边界中线的距离（这里违反的数据有比较小的违反，即虽然在边界内，但是没有被错误分类；另一种是被错误分类的数据，是比较大的违反）

这里的αn的不同情况对于我们进行数据的分析是很有帮助的，它的不同的值能够说明其所代表的数据与边界是什么位置关系。

模型选择通过交叉检验来选择模型参数
上面这个图表示的是使用高斯核SVM在不同的C和不同的γ的不同的边界表现，其中横轴对应不同C，而纵轴代表不同的γ。

上面这个图表示了使用交叉验证的方法我们选择误差最小的那个模型参数，我们这里只能选择几个不同的C和γ，比较一下哪个参数组合形式比较好。
SVM留一交叉验证误差与支持向量的关系SVM中有个很有意思是关系，留一交叉验证的误差会小于等于支持向量在所有数据中的比例。
如果将非支持向量的那个数据去除，这对找到构造边界的最佳解没有影响，所以非支持向量在留一交叉验证的误差上的贡献一定是0，而支持向量在留一交叉验证的误差上的贡献可能是0也可能是1。所以得到了这个限制关系。

于是我们也可以根据支持向量的数量来进行模型参数的选择，但值得注意的是，支持向量的数量只能用于估计一个上限，但不一定是最好的，所以通常利用这种关系来排除一些明显不好的模型参数。


资料来源：
GitCafe博客主页([url]http://jasonding1354.gitcafe.io/)[/url]
Github博客主页([url]http://jasonding1354.github.io/)[/url]
CSDN博客([url]http://blog.csdn.net/jasonding1354)[/url]
简书主页([url]http://www.jianshu.com/users/2bd9b48f6ea8/latest_articles)[/url]

赞~