Machine Learning Techniques Lecture 2: Dual Support Vector Machine | Cheney Shen

Technology blog

Machine Learning Techniques Lecture 2: Dual Support Vector Machine

 
 


 
 

内容:dual(对偶) support vector machine

 
 

告诉大家一个新的SVM问题:SVM的对偶问题。对偶问题的出发点是希望移除维度d对于non-linear SVM运算的影响,然后推导出透过 KKT 条件就可以得到对偶的SVM,KKT条件可以转化为QP形式来求解对偶SVM,但最好需要根据SVM来优化QP的运算过程。解的结果你会发现那些活下来的alpha>0的点有重要意义,就是support vector,就这些直接决定了最胖的分隔线。

 
 

 
 


 
 

回顾:linear SVM

可以通过QP求解得到比较robust的分隔线

 
 

今天把linear SVM转成另外一种形式以便更加容易的应用到不同的领域。

 
 


 
 

复习一下上一次上的内容:

 
 

求解:

可以通过二次规划来解SVM,应用于多维的话就是把x转换成Z空间即可,就是对z的线性二次规划求解,这对于x来说就是非线性的SVM。

 
 

作用:

控制模型的复杂度的同时,透过特征转换降低Ein。

 
 

我们Z空间的维度d越大,相对来说求解的难度就越高。

那么如果d无限大的话,还能不能求解。

 
 

因此我们的目标是移除 d 对于SVM求解的影响。

 
 


 
 

原来的VSM:d+1 个变量,N个限制条件

目标(看作是dual)的SVM:只会有N个变数,N+1个限制条件

 
 

这样变数的数量就不会和特征转换的维度增加而增加。

 
 

这里的数学很复杂!涉及到很多深入的最佳化理论,因此这里只讲有助于了解SVM特性的重点,其他就略过了

 
 


 
 

regularization时候的思路:

原来做 regularization 要解决的是有条件的最佳化问题,这个不好解,我们则把这个条件塞到最小化的公式里面,把问题转化为没有条件的公式的最佳化问题。

 
 

工具:

lagrange multipliers – 把条件乘上一定的系数加到目标函数里面去的东西

regularization里面原来每个条件都带一个参数C表示的是我们的w最长可以是多长,他会对应到一个lamda,这个lamda通过最佳解(梯度要往一个方向走但是已经无路可走了,这时候就是最佳解)要满足的条件来得到。

这时候呢,使用者只需要提供lamda而不是原来的C就可以求解问题了。

 
 

这里同样要使用 lagrange multipliers 来求解这里的 有条件的最佳化问题。但是这里的使用方式会比较不一样,这里会直接把 lagrange multipliers 当作是变数,而不是使用者直接给我们的已知量,然后去求解。

 
 

总结:

SVM 里面的每一个条件对应到一个 lagrange multiplier,然后把它当作是变数,去求解和这个变数有关的最佳化问题,这个问题其实最后就是对偶问题。

SVM 里面有 N 个条件,所以就有N个lagrange multiplier,就是有这么多变数。

 
 


 
 

做法:

Lagrange multipliers 在regularization里面叫lamda,但是这里通常用alpha表示。

原来的有条件问题可以写成一个看似没有条件的问题,上面绿框所示,包含红色部分表示原来想要的最佳化的目标,再加上蓝色部分所有的条件乘上其对应的alpha。整个定义为 lagrange function (L(b,w,alpha)表示)。

 
 

SVM 就可以转化成一个看起来没有条件的最小化问题了,黄框所示。

SVM 等式的含义是:每一个b,w的时候我都能算出一个值,这个值是把所有的alpha作为变量得到的最大的lagrange function的值,SVM要获得的就是所有b,w的对应的值的最小值。

证明:

任意的b,w:算分数的过程可能是好的(符合原来的那些限制条件),可能是坏的(不符合原来的那些限制条件至少一条),

  1. 坏的的情况下这个分数会是无限大(原来的有一条蓝色部分大于1,所以lapha越大的结果就是无限大)。
  2. 好的情况下条件这部分这个分数会是0,因此结果就只有原来式子中红色部分的结果(蓝色部分小于1,所以alpha越小越好趋近于0)

所以通过最小化b,w的值就可以淘汰掉那些原来的不符合条件的b,w。

 
 

至此,原来的SVM就转化成了一个看似没有条件的式子来求解。

 
 


 
 

练习

 
 


 
 

灰色公式:

 
 

现在有了一个新的问题:

有了一个lagrange函数,先对alpha做最佳化的动作,然后再对b,w做最小化的动作。

 
 

特性:

如果今天只考虑一个固定的alpha’,这个alpha’的最大值会比任意的最大值小,所以有了式子中的大于等于符号,有了右边部分去掉了max的式子。

任意的alpha’都有此等式,所以先做minb,w以后再考虑取最大的alpha’也是满足的,因此就有了蓝色底的公式。

 
 

像上面一样对掉了最佳化的过程的问题叫做 lagrange dual problem

 
 

对调关系还存在一个大于等于关系,也就是说如果我们解决了这个对偶问题,这个解就是没有对调前的式子的下限解。

 
 


 
 

>= : 叫做 weak duality(弱对偶关系)

= :叫做strong duality(强对偶关系)

  1. 问题是凸的
  2. 问题是有解的,原来的条件没有限制到说找不到任何的解
  3. 条件是线性的

    满足这三点叫做constraint qualification,强对偶关系,可以直接解右边的问题来当作左边的问题的解。也就是说存在一组b,w,alpha的组合对于左边来说是最好的,最右边来说也是最好的。

 
 


 
 

求解右边的问题:

  1. 里面的min部分是没有条件最佳化问题,那么就是求梯度是0的地方,谷底就是最佳解。先来对b微分就得到上面蓝色部分第一点的式子。

    上一步得到的一个等于0的式子代入,原来式子各个+0,则可以把b化简掉,没有b了。

 
 


 
 

  1. 同样的方式来对于w求偏微分得到一个=0的式子,同样的方式加入到原来的式子,可以将原来的式子消掉w,所以得到的式子就只剩下alpha了。所以minimize这一个步骤被化简掉了。

 
 


 
 

剩下一个只有alpha的问题,就是lagrange对偶问题的简化版。

 
 

结论:

如果是强对偶关系的话,需要满足下面的条件(KKT conditions):

  1. 满足原来问题的条件
  2. 满足对偶问题的条件
  3. 满足微分以后产生的条件
  4. Alpha * 里面部分原来的条件要等于0,也就是说这个式子的两部分至少一部分等于0

 
 

下面就是用这些条件来求解最佳的b,w,alpha

 
 


 
 

练习

 
 


 
 

上一步就得到了对偶问题的简化版,这里首先将其转化成我们常看到的SVM的对偶问题,会有一些些小小的变化:

将最大化变成最小化操作,通过取负号保证正的,然后通过导数来做到。

条件部分只是写法不一样,没变化,一共N+1个条件,w的条件用不着了(隐藏了),这里只需要专心求解alpha。

目标函数的二次式做了个展开的动作

 
 

至此得到了SVM的QP问题,而后就继续求解QP(二次规划)问题。

 
 


 
 

求解QP问题,代入模版。

 
 


 
 

SVM对偶问题的Q取名为 Q_d,d代表对偶的意思。

至此我们就可以解出来了,但是这个求解过程真的有那么容易么,我们来看看这个Q_d有多大。

 
 

Q_d:

每一格的内容是: y_n * y_m * z_n * z_m 相乘,一般不会是0。

如果是3000笔资料,其存储量差不多会是3G的大小

需要特殊处理:不存整个Q,而是用到再算,或者是使用特殊的条件来加速求解

也就是说需要用特别为SVM设计的二次规划来求解,不然的话计算会特别慢。

 
 


 
 

上面因此就可以得到中间产物alpha,然后我们怎么来得到b,w呢

 
 

使用KKT条件由最好的alpha来得到最好的b,w。

  1. w和alpha的关系就一个条件而已,直接解得。
  2. 两个条件和b有关,alpha大于0的时候最后一条后面的部分必须等于0,则可以求解得到b。(这里后半部分等于0可以得到那个点就是在胖胖的边界上,也就是support vector)

 
 


 
 

练习

 
 


 
 

Support Vector:就是在胖胖的分界线边界的那些点,这些是我们所需要的,其他的则是不需要的。【SV candidate】

求解SVM得到说:如果alpha>0的话,这个点一定在胖胖的边界上。【SV positive】

所以:我们将alpha_n>0的这些点叫做 support vector(SV positive)。

SV positive 可能会比原来我们所定义的 SV candidate 少一些,也可能一样多。

 
 

SV 重要性:

由原来w的求解公示可以看到W 是 alpha的线性组合,也就是说alpha=0就不需要计算。也就是说求解w只需要用到alpha>0的值。

同样你会发现求解b的时候使用的也是alpha>0的点。

也就是说w,b都是只靠support vector来求解得到的,所以和SV的定义相一致。

 
 

SV 就直接可以区分资料对结果是有用的还是无用的。

 
 


 
 

SVM里面的W表示成alpha相关的公式:alpha是对偶解

PLA里面也有相似的定义:beta表示的是犯错几次

 
 

两者w都是原始资料的线性组合

不完全是偶然,一般来说你做gradient decent这些演算法,和PLA一样从0出发,你也会得到类似的式子,这样的结果叫做:最佳的w可以被我们的资料 represent。

 
 

SVM特别的是:只需要资料里面的support vector就可以表示出来。

PLA特别的是:只需要用资料里面的犯错的点表示出来。

 
 


 
 

总结来说,从上一讲到这一共介绍了SVm的两种表示方式:

 
 

第一种是原始的(Primal SVM):让w越小越好,有一堆的条件限制;变数的数量和哪一个空间有关,空间维度越高越难求解;原来是通过对b,w的特别的放缩来得到最佳解。

第二种是对偶的(Dual SVM):切换到alpha空间去求解;问题的大小和资料的数量有关,资料量越大越难求解;通过最佳化求解得到support vector和对应的alpha,用这些来得到b,w最佳解。

都是得到最佳的b,w来创建SVM的式子来分类。

 
 


 
 

我们做完了没有?

 
 

我们想要求解SVM但是不想要碰d,因为d可能是很大很大。

然后这里讲的新的推导看起来只和N有关,和D无关,但真的是这样么?

D藏到了计算Q矩阵的地方,计算Q_n,m的内积,d越大越难以求解。

 
 

所以我们要想办法避开Q里面的D相关运算,这是下一讲的内容。

 
 


 
 

练习

 
 


 
 

总结:

告诉大家一个新的SVM问题:SVM的对偶问题。对偶问题的出发点是希望移除维度d对于non-linear SVM运算的影响,然后推导出透过 KKT 条件就可以得到对偶的SVM,KKT条件可以转化为QP形式来求解对偶SVM,但最好需要根据SVM来优化QP的运算过程。解的结果你会发现那些活下来的alpha>0的点有重要意义,就是support vector,就这些直接决定了最胖的分隔线。

 
 

下一讲:

移除 Q 对 D 的依赖。


Post a Comment

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

  • Categories

  • Tags