机器学习技法-lecture3:Kernel Support Vector Machine

Kernel Support Vector Machine

课程回顾

lecture2中我们主要介绍了对偶SVM的解法及解法需要的条件,本节课我们将主要解决非线性变换导致的过高的计算成本的问题—kernel方法。

Kernel Trick

lecture2中我们通过推导将非线性SVM转化为求解α的QP问题,但是实际上计算层面并没有避免高维空间矩阵的计算问题,这将是我们本节课旨在解决的问题,我们的思路是:将特征转化过程和高维空间的计算过程等两个步骤合并为一个步骤,这样的过程我们称为kernel trick。

我们首先研究最简单的情形即二次多项式的转化过程,我们先对两个点分别做转化然后再相乘,可以得到上面的公式,蒸锅过程我们付出了O(d)而非O(d^2)的计算成本。

我们将特征转化和计算內积两个步骤一起完成的过程函数称为kernel function,相应地我们可以分别计算b和w,并返回相应的指示函数,于是我们得到了kernel SVM ,其相应的计算流程如下。

Polynomial Kernel

接下来我们推导二次多项式变换的一般形式,我们通过对一次系数和二次系数做一定的放缩变换,可以得到一般形式。需要指出的是,这个形式对应的二次变换能做的事情是一致的,但是不同的缩放对应着不同的內积,进而对应着不同的边界,实际应用中K2是常用的形式。

我们可以看到下面是三种不同的参数对应的边界:

更进一步,我们可以通过引入参数(γ,ζ)和Q来将kernel推广到更一般的情形,最后,需要指出的是Q=1的情形即linear kernel的情形,它是最简单的情形甚至不需要通过dual的方式去解决,这往往也是我们需要优先考虑的选择。

Gaussian Kernel

现在我们来思考我们能否使用kernel解决无限多维的转化问题,我们使用一个一维特征的x,使用高斯函数做Taylor展开,我们可以得到下面的结论,可以发现它对应到一个无线维度的特征变换,做一个一般化的推广,我们可以得到Gaussian kernel的形式。

进一步,我们可以总结得到gaussian svm的hypothesis,我们发现他实际上就是以sv为中心的高斯函数的线性组合,我们又把这个函数称为RBF kernel。

学到现在我们发现SVM已经能完成很多事情了,最开始我们只能做hyperplane,随后我们加入了transform,接着为了解决计算效率的问题我们引入了kernel,只做这三步我们没法控制model complexity,而large-margin恰好满足了我们的要求。

于是我们能在较少的hyperplane上做出复杂的边界并且可以使用kernel有效率地完成整个过程,所以我们没必要进行真实的转化在计算,也没必要存储真实的w而只需保存他的表现形式。

最后需要指出的是,SVM也会出现过拟合的,越大的γ对应更尖的高斯函数,当取无穷大的γ时就变成了对每个资料点做辨识,因此应用上不建议使用过大的γ。

Comparison of Kernels

接下来我们分别看看三类kernel的优缺点,首先是linear kernel,毫无疑问这是最简单的kernel也往往是我们首先要考虑使用的kernel,优点是安全和计算速度快,但是他的应用场景往往比较局限,不适用与非线性可分的问题。

polynomial kernel的优点是相对线性核的限制较小,可以认为根据实际情况和经验做Q的限制,缺点是当Q比较大时计算难度大结果不一定可靠,并且它对应着三个参数,选择上的难度较大。

Gaussion kernel无疑是最强大的kernel,同时它的边界在数值复杂度上低于poly,参数也只有一个;但是由于他强大,所以他往往会耗费更多的时间,也需要提防它过于强大而导致的过拟合。

本节课我们主要建立了kernel SVM,其中我们首先介绍了kernel trick,然后介绍了三种常见的kernel并总结了他们的优缺点。

——课堂小结

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180709G01XSB00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券