首页 > 其他 > 详细

机器学习技法(林轩田)学习笔记:Lecture 3 & Lecture 4

时间:2018-07-27 14:06:14      阅读:222      评论:0      收藏:0      [点我收藏+]

Lecture 3:Kernel Support Vector Machine

Kernel Trick

回顾Lecture 2中SVM的拉格朗日对偶问题:

技术分享图片

对偶问题中,有n个变量需要求解,n个不等式约束条件和1个等式约束条件

整个问题只有在计算\(q_{n,m}\)时与\(\tilde d\)有联系:计算\(z_n,z_m\)的内积的时间复杂度是\(O(\tilde d)\)的,另外,在求解该对偶问题前,\(z_i\)都需要通过特征变换\(z_i=\Phi(x_i)\)来得到

为了彻底摆脱对\(\tilde d\)的联系,就要用到核技巧(kernel trick)了

首先看一个例子:特征变换\(\Phi(x)\)把原始特征\(x\)映射到二阶的\(z\)

技术分享图片

(为了方便表示,把诸如x1x2和x2x1这样的两项都拆开写了)

\(x\)是d维的,\(z=\Phi_2(x)\)\(d^2+1\)维的,直接计算两个\(z_1,z_2\)的内积,时间复杂度是\(O(d^2)\)

我们把\(\Phi_2(x)^T\Phi_2(x‘)\)展开:

技术分享图片

如果我们跳过计算\(\Phi_2(x),\Phi_2(x‘)\),以及\(\Phi_2(x)^T\Phi_2(x‘)\),而是直接计算最后的\(x^Tx‘\),时间复杂度就降到了\(O(d)\)

我们定义特征变换\(\Phi_2\)对应的核函数
\[K_{\Phi_2}(x,x‘)=1+x^Tx‘+(x^Tx‘)(x^Tx‘)=\Phi_2(x)^T\Phi_2(x‘)\]

使用简单的核函数代替内积,就可以让这一过程的时间复杂度与\(\tilde d\)无关了

技术分享图片

类似地,我们把b和\(g(x)\)中的w表示成\(\sum_{n=1}^N\alpha_ny_nz_n\),然后用核函数代替其中\(z_n,z_s\)的内积,如上图。这样就能让计算内积的过程与\(\Phi,z,\tilde d\)无关了

技术分享图片

使用核技巧后,之前的SVM算法流程如上图,其中:

  • (1)中获得每个\(q_{n,m},p\)的时间复杂度就变成了$O(n^2)\cdot $(计算核函数K的时间复杂度)
  • (2)是一个n个变量、n+1个约束条件的特殊二次规划问题
  • (3)和(4)的时间复杂度都是O(支持向量个数)·(计算核函数K的时间复杂度)

Polynomial Kernel

一般的Q阶多项式核函数形式如下:

技术分享图片

其中,\(\zeta,\gamma\)是参数

加入多项式核函数的SVM被称为多项式核SVM

线性核是多项式核的特殊情形,即Q=1,\(\zeta=0,\gamma=1\),此时就相当于是原始特征\(x,x‘\)的内积:

技术分享图片

在实践中,我们应该尽量先尝试比较简单的假设函数,所以要优先尝试用线性核函数

Gaussian Kernel

我们来看这个特殊的核函数:

\[K(x,x‘)=\exp(-\gamma \|x-x‘\|^2),\gamma>0\]

首先看x为标量时的情况:

技术分享图片

我们可以把这个核函数看作是对两个\(\Phi(x),\Phi(x‘)\)的内积,特征变换\(\Phi(x)\)将标量x映射为无限维的向量

高斯核SVM的假设函数为:

技术分享图片

其中,\(\sum_{SV}\alpha_n\gamma_n\exp(\cdots)\)可以视为是若干个以\(x_n\)(\(\alpha_n>0\)的支持向量)为中心、方差相同的高斯分布的线性组合

总结:带核函数的SVM的大间隔保证了泛化能力(\(E_{in}\approx E_{out}\));而核函数则让原始特征映射到高维(甚至无限维)空间中,使得决策边界变得复杂,\(E_{in}\)很小

技术分享图片

选取合适的高斯核参数\(\gamma\)十分重要,\(\gamma\)越大,每个高斯分布就越"尖",如上图所示,\(\gamma\)太大会引起过拟合

Comparison of Kernels

本节课最后比较了各种核函数的优缺点

线性核

优点:

  • 简单,在实践中应该首先尝试简单的线性核函数
  • 运算速度快
  • 最后可以很容易得到有实际意义的\(w\)

缺点:

  • 过于简单

多项式核

优点:

  • 可以表示出比线性核更复杂的边界
  • 通过阶数Q的大小,可以控制决策边界的复杂程度

缺点:

  • Q太大时,\(|\zeta+\gamma x^Tx‘|<1\)时K趋于0,\(|\zeta+\gamma x^Tx‘|>1\)时K趋于正无穷
  • 参数更多,有三个参数\(\zeta,\gamma,Q\),不方便选取

高斯核

优点:

  • 把原始特征映射到无限维向量,可以表示出比线性核、多项式核更复杂的边界
  • K始终在\([0,1]\)内,这一点比多项式核好很多
  • 只有一个参数\(\gamma\)

缺点:

  • 无法得到\(w\)
  • 比线性核更慢
  • \(\gamma\)太大时容易过拟合

另外补充一点,核函数可以视为对两个向量的相似度的度量

K是有效的核函数的充要条件是,对于任意n个向量\(x_1,\cdots,x_n\),矩阵\(K\)(其中\(k_{ij}=K(x_i,x_j)\))是半正定的

机器学习技法(林轩田)学习笔记:Lecture 3 & Lecture 4

原文:https://www.cnblogs.com/qpswwww/p/9377102.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!