Machine Learning Techniques Lecture 3: Kernel Support Vector Machine | Cheney Shen

Technology blog

Machine Learning Techniques Lecture 3: Kernel Support Vector Machine


 
 

内容: kernel SVM

首先讲了把原来的dual SVM的转换和内积的两步合并为Kernel,通过这样回避了原来SVM计算涉及到的对空间维度的依赖,然后讲了多项式kernel和Gaussian kernel,最后对这些kernel做了简单的比较,如果想要的是效率的话往linear走,想要复杂边界的话往高纬度走。

 
 


 
 

上一次我们看的是SVM的对偶形式,其新的形式好像跟空间维度D没有关系,可以使用二次规划来求解。

 
 

今天来看一下 Kernel support vector machine,把好像拿掉,使SVm的形式真的和空间维度没有关系。

 
 


 
 

这是我们上一次推到出来的对偶问题:

从条件的数量和变数的数量来看,这个问题好像都和空间维度D没有关系。但是如果计算Q_d这个矩阵,就需要用到D空间的维度,维度越大越难求解,这里就是瓶颈。

 
 

怎么做?

 
 

求解 Q_d 对于Z空间来说是做内积,但是如果从x空间的角度,其实是两个步骤。步骤是先把x做转换,再做内积,每一步都和维度相关。我们能不能把这两个步骤合起来算得快一些?

 
 


 
 

先考虑一个简单的例子:二次的多项式转换

 
 

使得有 0次项,1次项,2次项,x1x2,x2x1同时存在;

这样转换了再做内积,如上面的推导,就会得到只和 x * x’ 内积的结果。

可以将运算复杂度降低到了O(d)!

 
 


 
 

Kernel function: 转换操作 + 内积操作

 
 

上面的例子所对应的 kernel function 表示为黄底所示部分。

 
 

接下来我们来看SVM里面怎么使用kernel function:

  1. SVM用到内积的地方首先是 二次项系数q,是Z空间里面的内积,可以换成x的kernel function求解。
  2. svm里面算出了alpha以后需要再求得b,w,算出alpha之后通过挑一个support vector来求得b,这里有 w * Z 的内积求解问题,可以转换成Z空间的内积,同样就可以转换成x的kernel function来求解。
  3. 最后得到SVM的结果的这一步,也存在 w * phine 的内积,phine函数就是z,w可以转化成z相关,这样同样可以转换成x的kernel function来求解。

 
 

也就是说没有任何一个时刻真的在z空间做,所有的运算都是在x空间完成,就不会受到空间维度d的影响了,就会很有效率。

 
 


 
 

Kernel SVM 的表示(就是原来的z的内积全部替换为kernel function):

  1. 算Q的时候全部换成Kernel function来求解
  2. 同样的求解alpha
  3. 再算b的时候也是使用kernel function来求解,这里只需要一个support vector就能得到b。
  4. 最后预测函数的表达式求解的时候也是使用kernel function来求解

 
 

时间复杂度:

1的是 算kernel的力气 * N平方

2的是 QP 只有N个变数,N+1个条件

3、4的是 O(SV)

 
 

Kernel SVM 就和空间维度d没有关系了,而且和原来一样,只需要support vector就可以对未来做预测。

 
 


 
 

练习

 
 


 
 

对于二次多项式来说,有些很容易写出 kernel function,有些就比较难,下面介绍一些常用的二次多项式转换。

 
 

蓝色的是原来的,在这基础上做一些些放缩,比如*根号2,对应的kernel函数的一次项前面就会有一个2,如上面红色的公式,再复杂如绿色phine标识的那样。

 
 

整理起来,这里讲的是二次项转换中一次项系数的扩展的方法。这里的变化都是相同的空间内的(power),不同的形式(内积,geometry特性,不同的边界)

 
 


 
 

不同的转换对应到不同的几何定义,不同的距离。

 
 

上面三幅图就是不同的一次项系数对应到的边界变化。相对来说你比较难比较哪个比较好,这里想给大家建立的概念是,换掉kernel,就可能会得到不一样的解。

所以我们要对kernel做选择,才能有比较好的分类结果的表现。

 
 



从二次出发,还能一路推导下去,这里对常数部分做手脚加上theta,然后你能考虑q次方。

 
 

grama:控制一次项系数;

theta:控制常数项;

Q:控制次方。

 
 

这样以后,你做高次转换的复杂度和维度无关,计算也就很简单,只要能把kernel计算出来。

右边的图就是10次方做出来的图,虽然特别高次方,但是边界还算简单,large-margin相对来说可以帮你控制overfitting。

 
 

Polynomail SVM 就是 Polynomial Kernel 配合 SVM 来使用。

 
 


 
 

如果我们回到一次转换,也可以做,通常叫做linear kernel。

 
 

Linear 是值得你最先尝试的一种方式!

 
 


 
 

练习

 
 


 
 

如果我们可以用kernel有效率的解决高纬度空间的运算的话,那么对于无限多维的转换是不是也能解决?

 
 

特例:

原始资料只有一个维度,考虑一个特别的函数如上面所示的高斯函数

经过一翻推导你会发现最终也是一个x函数phine(x)的内积,而且是无限多维的高斯函数。

 
 


 
 

这是后来考虑G_SVM,是一堆中心在support vector上面的高斯函数的线性组合。

所以也被叫做 Radial Basis Function(RBF) kernel

 
 

Gaussian SVM:使用高斯函数来做kernel的SVM,意思是把x映射到无限多维的空间里面,在这里面找出一个最胖的分割情况。

 
 


 
 

通过 kernel SVM 可以有效率的做到 large-margin + hyperplanes + transform。

 
 

不再去算Z,直接用kernel替代;

不再存储W,只存w的表现方式support vector和alpha;

 
 

现在还可以做无限多维度的SVM,比如通过Gaussian kernel实现的 Gaussian SVM,large-margin在这些过程中提供不overfitting的保障。

 
 


 
 

真的那么美好么?

 
 

举一个gaussian kernel的例子,不同的gaussian kernel得到的结果如上面三幅图。

参数不合理还是会overfit,还是要慎重选择kernel!Gaussian SVM里面不建议使用太大的garma,garma越大fit越强烈。

 
 


 
 

练习

 
 


 
 

我们接下来分析一下各种kernel的好坏处:

 
 

  1. Linear Kernel

其实就是把原始的内积丢进去就好,各种求解方式的效率差很小。

好处是最简单最安全最优先尝试的方法;不牵扯到特别转换,所以可以设计特别的QP solver,计算得更快;对于人来说可以很容易的看出来到底怎么去做分类。

坏处是有限制的,如果data不具有线性则没有办法做

 
 


 
 

  1. Polynomial kernel

有限情况下的kernel。

好处是比linear更加宽松,高次解决了非线性data不能处理的限制;可以通过对Q的设定来表达你对这个模型的想象。

坏处是你要算kernel的值的时候比较困难,Q越大越难求解;参数多而且需要你去选择,比较困难。

 
 


 
 

  1. Gaussian Kernel

无限情况下的kernel。

好处是表达能力是无限的,因为是无限多维的转换;比起polynormial来说数值求解的难度比较低;只有一个参数garma所以比较容易选择。

缺点是无限多维度的转换,不直观;比起linear来说计算相对比较慢;能力太强可能会overfitting。

 
 


 
 

  1. 其他的kernel

kernel代表的是x和x’转换以后在z空间的相似性(内积表示的就是一种相似性)。

那么从相似性来考虑采用什么样的kernel?

不见得可以,因为kernel是一种相似性,一种向量的内积在Z空间的相似性。

如果你要用自己的kernel的话,要注意的是你要想办法证明它到底为什么是个kernel。

 
 

kernel的充分必要条件:

对称,从矩阵角度看kernel矩阵是两个z矩阵相乘,也就是说kernel矩阵是半正定的。

 
 


 
 

练习

 
 


 
 

总结: kernel SVM

首先讲了把原来的dual SVM的转换和内积的两步合并为Kernel,通过这样回避了原来SVM计算涉及到的对空间维度的依赖,然后讲了多项式kernel和Gaussian kernel,最后对这些kernel做了简单的比较,如果想要的是效率的话往linear走,想要复杂边界的话往高纬度走。

 
 

下一讲:如何避免高纬度SVM(Gaussian SVM)的overfitting


Post a Comment

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

  • Categories

  • Tags