Machine Learning Techniques Lecture 4: Soft-Margin Support Vector Machine | Cheney Shen

Technology blog

Machine Learning Techniques Lecture 4: Soft-Margin Support Vector Machine


 
 

内容:soft-margin SVM

首先列出soft-margin SVM的形式表达,出发点是不坚持所有的已知数据点不一定全部要分对,所以增加了一个参数用来控制设定违反分类结果的程度。推倒的时候也是一个QP问题,所以同样通过对偶问题来化简求解。soft-margin SVM可以告诉我们的是可以把数据通过alpha的值分为三类,边界上的,边界内的,边界外的,对于我们做资料分析很有用。另外我们还提到可以使用cross validation来选择模型参数。

 
 


 
 

上一讲:Kernel SVM

目的是通过把Dual SVM的转换和算内积步骤合起来成为Kernel消除空间维度对计算量的影响,这样以后对于任意维度的SVM都能做到。

 
 

Soft-margin support vector machine:

原来讲的都是不能违反任意一个数据的结果叫做Hard-Margin,这里放宽这个限制。从上一讲出发,gaussian svm太复杂了,我们有没有办法来减少overfitting。

 
 


 
 

上一讲我们得到的信息是:SVM可能会overfitting。

 
 

一个原因是转换太powerful了;另外一个原因是我们坚持要把资料完美的分开,不能出错。

如图所示,如果一定要分开的话就会像右边的图一样边界非常复杂,但不见得这样是合理的。

 
 

也就是看作资料里面存在noise,怎么去处理。

 
 


 
 

我们首先来看看我们以前是怎么处理资料里面存在noise的问题的。

 
 

Pocket 模型

没有办法找一条线分开,那么就找一条线犯最少的错误。

 
 

Hard-margin 模型

所有的圈圈叉叉都要分对,而且还要选择w最小的。

条件太多,所以我们应该像pocket一样容忍一些错误。

 
 

其中一个方式是(可以看作是 pocket 和 hard-margin 的合体):

和原来的SVM一样,我们希望的是w长度最短的,对于做对的点要符合原来的条件来求解,做错的点就不管了。

如果只是这样的话不行,机器会默认偏向统统做错,因此我们需要的是做错的越少越好。

 
 

我们又要W最小,又要做错的最少,因此加上一个参数C来做平衡。C越大表示越不要犯错越好,C比较小的时候表示W越短越好。

 
 


 
 

所以这是我们的新问题 soft-margin SVM,上面黄底表示的公式。

 
 

公式的问题:

存在boolean运算,不是线性的运算,也就是说不是QP问题,也就不能再使用Dual,Kernel机制。

不能区分错误的大小。

 
 

因此提出了下面黄底表示的新的问题公式。

我们把错误记录在 kesi_n 的变数里面, kesi_n >= 0,表示的是离我想要的那个值到底有多远。

这样我们minimize的式子里面也就可以来衡量你犯了多大的错误用kesi的和来表示。

这样就符合了线性变化的条件,同时也可以衡量错误大小的要求了。

 
 


 
 

Margin voilation:意思就是错误可以衡量,图示就是违规的数量的图解。

C:描述的是违反margin的程度,C越大表示允许违反的越小,反之边界会比较平滑和胖。

变数数量:d+1+N,N表示的是每个点到底违反了多少margin,因为只记录违反的N个点,所以多了N个条件。

 
 


 
 

练习

 
 


 
 

黄色底公式就是我们上面推导得到的soft-margin SVM公式。下面就是根据这个问题推导他的对偶问题,然后就可以和hard-margin时候一样,享用容易做feature transform的特性。

 
 

所以先写出 lagrange multipliers,步骤和原来一样,把条件合并到目标函数里面去。然后就得到了 lagrange dual,之后和之前一样用KKT condition来化简。

 
 


 
 

问题写下来如上面的黄底框所示。

化简的第一步是对整个式子求kesi的偏导等于0,就得到一个alpha,beta相关的等式,所以可以把beta换掉用alpha表示,同时alpha的限制条件加强了,得到的结果和原来的hard-margin问题化简结果相似。

 
 


 
 

式子就变得如上面黄底那样简单了。到这里首先是minimize,然后是maxmize,这个式子在hard-margin SVM几乎一样,同样里面的部分去微分求解,和第二讲讲过的dual一致,具体见那边的推导。

 
 


 
 

然后你就会得到一个几乎和hard-margin SVM一样的式子,唯一的差别就是对alpha_n有了一个最大值C的限制。

 
 

因此现在这个问题有N个变数,2N+1个条件。

 
 


 
 

练习

 
 


 
 

推倒完了以后就可以得到 Kernel soft-margin SVM的算法了:

  1. 求解这个问题的时候加上了额外的upper-bound条件。
  2. 一样去求解QP问题
  3. 一样去算b
  4. 得到最后的hypothesis SVM长什么样子

 
 

C的值就是来控制你想要得到边界是更细致变化还是更粗变化。

 
 

这里还需要探讨的问题是,这里面我们算b的方式与原来一样么?

 
 


 
 

Hard-margin里面就是列出KKT条件,图中所示一条的乘积的前后两部分必须有一个为0,那么因为alpha>0,所以后半部分就必须=0,就可以直接告诉我们b是多少。

Soft-margin一样依葫芦画瓢,列出不能同时存在的条件,这里不一样的就是多了一个kesi用来记录到底违反多少点。还存在另外一个条件。通过这两个条件,和原来的方式一样,先找一个support vector,也就是alpha>0,这样就会有 b = 一个和kesi相关的式子,如果kesi = 0,b就可以直接求出来。

 
 

所以求解b的方法总结来说就是:找一个可以使得kesi=0的support vector(命名为free support vector,不再是任意的support vector),这样b就可以很容易得到解。

 
 

实际中也有极少数的情况不存在free support vector,就只能用一堆不等式来限制,就可能存在一堆b,都是可以的答案。

 
 


 
 

然后我们来看看 soft-wargin SVM 的表现怎么样。

当C取不同的值的时候的结果如上面图示,C越大表示越不想犯错误,边界越复杂。C值越大越容易overfit,所以需要好好的去选择参数。

 
 


 
 

我们刚才就是使用 complementary slackness 这个条件来求解b,我们再通过这个来看看 soft-margin SVM 到底告诉我们一些什么信息。

 
 

Soft-margin SVM 的两个 complementary slackness 条件如黄底所示,根据这两个条件我们可以把手上的资料点分成三种。

第一种是free support vector,特点是0<alpha<C,kesi=0,可以用种点来唯一的算出b,这些点就是刚刚好在胖胖的边界上的点。

第二种是non-support vector,特点是alpha=0,kesi=0的点,也就是没有违反边界的点,分得非常好的点,在胖胖的边界外面。

第三种是bounded support vector,特点是alpha=C,kesi != 0的一个值,记录了违反多少,就是图中处于胖胖的边界内的点。

 
 

通过alpha的值就可以把手上的数据点分成三种,这三种对于你做资料分析很有用。

 
 


 
 

练习

 
 


 
 

讲完了model,我们来看看怎么选参数。

 
 

上面的九张图统统都是用的Gaussian kernel的SVM,但是采用了不同的C,garma的组合。横轴是表示的C,纵轴表示的是garma。

 
 

怎么选?

最好用的工具就是Validation。

 
 


 
 

通过采用 Cross Validation,算一下每一种情况下的Error,选一个最好的。

 
 


 
 

如果把 cross validation 递推到极限的话,就是每一份资料只包含一个的话,这时候就有一个特殊的名字叫做 leave-one-out CV Error,这个在SVM上面会有一个有趣的结果。

 
 

E_loocv 的结果和 support vector 的数量是有关系的,可以证明 E_loocv <= SV数量/资料量。

假设今天你有一万个点,如果你解完这个问题以后,对于第一万个点刚好他的alpha=0。意味着只踢掉第10000个点,前面的9999笔资料都丢进SVM,这组alp[ha还会是最佳解,也就意味着最后一个没有用,alpha=0。也就是说把non-support vector 拿掉对于解SVM一点影响也没有。

同样的对于 non-support vector 对于 cross validation 的贡献也是0。

所以就有上面的结论。

 
 


 
 

也可以通过上面的结论来做模型的选择。

 
 

把所有的情况的support vector的数量列出来如上面的图示,但要注意的是这个公式说的只是个上限,不是实际的错误率。

把上限做到最好不代表把真正的错误率做到最好,因此这个结论通常是拿来排除比较危险的结果,就比如上面的三张图所示的结果,先予以排除。

 
 


 
 

练习

 
 


 
 

总结:soft-margin SVM

首先列出soft-margin SVM的形式表达,出发点是不坚持所有的已知数据点不一定全部要分对,所以增加了一个参数用来控制设定违反分类结果的程度。推倒的时候也是一个QP问题,所以同样通过对偶问题来化简求解。soft-margin SVM可以告诉我们的是可以把数据通过alpha的值分为三类,边界上的,边界内的,边界外的,对于我们做资料分析很有用。另外我们还提到可以使用cross validation来选择模型参数。

 
 

下一讲:

至此对SVM进行了一个完整的介绍,但这些都是在binary classification的情况下,下面开始讲如何将SVM延伸到更复杂问题的求解。


Post a Comment

Your email address will not be published. Required fields are marked *

  • Categories

  • Tags