Kernel Support Vector Machine《机器学习技法》学习笔记(3.1、3.2、3.3、3.4)

这一章是在SVM这个词前面加了一个kernal,什么都好计算了。

预备知识

泰勒展开式

高斯核函数(径向基函数)那一部分,为了证明高斯核函数是把x映射到无穷维的z空间中,需要用到泰勒展开式

核函数

主要使用PRML里面第六章的说法。

再用PRML那本书里面的话说 kernel trick

kernel trick可以翻译为核技巧或者核把戏,也被称为核替换。
如果我们有⼀个算法,它的输⼊向量x只以标量积的形式出现,那么我们可以⽤⼀些其他 的核来替换这个标量积。
上面这句话的意思就是如果x这个始终会以xTx‘的形式出现,那么我们就直接可以定义一个k(x,x')函数,它一方面等于:

另一方面可能合并在一起,消掉ϕ(x)这个函数时k(x,x')函数又会变得很简单,比如下面这个:

就是x和x‘的差的绝对值。
如果ϕ(x) = x,那么k(x,x')= xTx‘,这就是线性核

上一周的另外一个伏笔

为什么第二周突然去讲对偶问题,看完这一章我就明白了。
是这样的,对偶问题往往会产生核函数去解。
我大概总结出来了为什么对偶经常会有核函数:
1.w都是做什么的?都是表示x的系数,要和x相乘的呀
2.凸优化问题的最优解是什么时候?肯定那一点的w的梯度等于0
3.那怎么表示w等于0呢,肯定是原来的x表示呀,就是某一点x‘的时候可以表示它等于0.
这样原来的wx就变成了xT和x‘呀。这样就可以核函数了。
当然不是随便一个x和x‘的函数就是核函数,还需要对称性等一些定义。
反正就知道一些典型的被人证明过的核函数就行了。
比如上面说过的线性核。
还有就是Polynomial Kernel这种多项式的核。
还有就是比较有名的同质核(homogeneous kernel),也被称为径向基函数(radial basis function),它只依赖于参数之间的距离(通常是欧⼏⾥得距离)的⼤⼩,即k(x, x′) = k(|x − x′|)。
比如高斯核函数就是一种径向基函数。

核函数k(x, x‘)是⼀个合法的核函数的充分必要条件 是Gram矩阵(元素由k(xn,xm)给出)在所有的集合{xn}的选择下都是半正定的
构造新的核函数的⼀个强⼤的⽅法是使⽤简单的核函数作为基本的模块来构造。可以使⽤下⾯的性质来完成这件事。
给定合法的核k 1 (x, x′)和k 2 (x, x′),下⾯的新核也是合法的

接上周的对偶问题说

上一周讲的是SVM的对偶问题,因为很多是非线性可分的,所以进行函数转换x->z。
可以发现如果对x进行一些转换,可以证明和原问题的答案是一样,而且和这个原始x的纬度d几乎没有什么关系。这一章就是让问题和这个d完全没有关系。
上一周的最后残留结果是这样的:

问题中已经没有d了,但是Z里面可是对d做的高纬映射变成了d‘,所以实际上如果先x->z,然后对z直接做内积运算,那么这个还是和d'有关的,而且d‘非常大。

kernel trick

现在不能分开看,要合起来看,映射展开放在一起,如果ZnZm乘起来能够用某个函数最后直接表达出Xn和Xm的某种关系,这样的话,其实就是Xn和Xm直接带进去这个函数就求出来了,根本不用管Z。
上面的这个就是kernel的内涵,就是利用核函数一方面达到了低维到高维转换以便解决线性平面不可分的情况,另一方面用一个整体的思想将转换之后的运算和转换本身联系到一起使得计算很简单。

看一些具体的kernel trick

假如现在对于一个d维的x向量,经过x->z这一步转换成下面这样,z会变成d ^ 2维:

可以发现如果z和z’相乘就会变成:

发现可以用基本的线形核函数组合得到,而且还是一个d维的运算。
于是上一周讲的Q,b就可以用核函数表示:

这样就再也不用算上一周说的z的内积,只需要计算d维的x的内积

dual SVM 转换 kernel SVM


这样转换的结果就是:
只用原始的x的维度,避免了z的维度那么大,同时还是只跟SV相关

多项式核函数

上面说的最简单的二项式函数,因为常数和线形核函数的系数都是1。
假如添加了系数呢,像下面这样:

和上面最简单的相比:
两者变成的z的维度是相同;
但是γ会对每一个维度的值进行放缩,而这个内积又代表着点到分隔面的距离,所以还是会有影响的。

多项式核函数使用参数对比


SV也会变,最后的结果也会变,当核函数改变的时候,margin就会改变。

现在我们就不用思考怎么x->z这个过程了,我们直接利用对偶问题选择kernel函数就可以了。

通用的多项式核函数

利用多项式核函数的SVM一般叫做多项式SVM

ζ=0,γ=1,Q=1那就是线形核函数

高斯核函数

上面多项式核函数还是只是转换成d ^ Q维,那什么时候才能变成无限维呢,最后还能用一个简单的核函数表示。
高斯核函数就出来了。如果我们不要求得到z,下面的正面就够了:

但是你想证明为什么z是无限维的,那就需要泰勒展开式:

这个跟i相关,i是无限维的,z就是无限维的

高斯SVM

利用高斯核函数的SVM又叫高斯SVM

前三周一步一步看干了什么

第一周去找超平面,平面是平的
第二周做一个高维转换,可以找到曲面,但是高维不好算
第三周的高维转换利用核把戏 x->z 变成 k(x,x'),曲面好算

高斯核函数使用参数对比


如果γ很大,会过拟合。

各种核函数对SVM的好坏

线形核函数--最简单

直观、快速可解释
但是如果线形不可分,就不能用

多项式核函数--一般Q都是小的

可以解决线形不可分,通过Q可以帮助你理解对结果的认识
坏处:其实Q大的时候难算,而且参数多,一般是Q=2,3,先试试1怎么样

高斯核函数--最流行

无限维,拟合能力没有上限,数学也不难算,参数只有一个
根本无法解释无限维空间的情况,很容易过拟合

其他证明一个函数能不能做核函数,略。

发表评论

电子邮件地址不会被公开。