回顾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算法流程如上图,其中:
一般的Q阶多项式核函数形式如下:
其中,\(\zeta,\gamma\)是参数
加入多项式核函数的SVM被称为多项式核SVM
线性核是多项式核的特殊情形,即Q=1,\(\zeta=0,\gamma=1\),此时就相当于是原始特征\(x,x‘\)的内积:
在实践中,我们应该尽量先尝试比较简单的假设函数,所以要优先尝试用线性核函数
我们来看这个特殊的核函数:
\[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\)太大会引起过拟合
本节课最后比较了各种核函数的优缺点
优点:
缺点:
优点:
缺点:
优点:
缺点:
另外补充一点,核函数可以视为对两个向量的相似度的度量
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