Press "Enter" to skip to content

稀疏核机(中):核方法

 

作者丨stephenDC

 

这是作者的第 7 篇文章

 

导   读

 

在上一篇文章中,我们简单回顾了   SVM的导出 (点击加粗字体可回顾)。本篇文章将在此基础上,讨论SVM的基函数扩展,引出并重点讨论核方法。

 

SVM的基函数扩展

 

在上一篇文章里介绍过,如果样本是线性不可分的,但在误差允许的范围内仍然适用线性模型,可以引入松弛变量来解决此类问题。

 

但如果样本不仅是线性不可分,而且线性分割的最优误差也完全无法接受,这时候就需要考虑扩充模型容量了。

 

不过,线性不可分的样本集,也许用抛物线(二阶多项式模型)就可分了,更不用说其他更加复杂的模型。而基函数扩展,是最常用的对线性模型进行容量扩展的方法之一,因此有理由期待,扩展后的SVM可以对数据集有更好的分类能力。

 

 

 

 

基扩展SVM的最优化问题

 

 

 

 

基扩展SVM的解

 

 

 

 

基扩展的不足

 

 

对线性模型进行基扩展,既可以提升模型容量,又可以直接类推线性模型的方法和结论,那幺根据“没有免费午餐定理”,要付出的代价是什幺呢?

 

先说答案:代价是计算量的增加。

 

 

 

SVM的核扩展

 

 

引入核函数

 

显然,这种定义基于内积运算,且只是将基函数的内积,用一个二元函数代替而已。这当然是一种非常形式化的定义,后文会给出更加规范化的定义。

 

 

 

 

核方法

 

 

核函数定义

 

 

Mercer定理

 

 

Reproducing Kernel Hilbert Space

 

 

 

 

 

小结

 

核方法的引入,是为了在扩展模型容量的同时,不显着地增加计算量。原则上,在计算中只用到样本内积的模型,均可用核方法进行扩展。下一篇文章,我们会将核方法用到线性回归和感知器,并结合支持向量回归,来讨论稀疏性。

 

P.S.

 

很多文献里讲到,核方法是将输入空间的原问题,映射到高维(甚至无穷维)的特征空间中解决的。这种说法没有任何问题,但给人的感觉好像是,解决问题的关键是高维空间,到了高维空间很多问题都迎刃而解了。

 

事实上,解决问题的关键并不是将问题映射到了高维空间,而是非线性的映射本身。 假设我们在原来p维的输入向量后面加上N个全是0的分量,那幺显然即便N为无穷大,线性不可分的问题依然线性不可分。

 

但反过来,假设我们在映射前后并不增大(甚至减小)空间的维度,只要映射本身够复杂,依然可以解决问题(当然,这会过拟合)。

 

比如,三维空间中用平面不可分的数据集,我们总有办法人为的移动到二维空间中使之成为线性可分的数据集,而数据在移动前后的对应关系,即为所求的映射。

 

当然,这个映射必定会很复杂,如果用常规的基函数(比如多项式基函数)进行展开,基函数张成的空间也会是高维的。因此,相对于不同的基函数,可以视为将问题映射到了不同维度的空间,这只是看问题的一个角度,而非解决问题的实质所在。

 

以上部分是个人理解,欢迎交流意见,更欢迎批评指正。

 

参考文献

 

A Story of Basis and Kernel – Part I: Function Basis

 

A Story of Basis and Kernel – Part II: Reproducing Kernel Hilbert Space

 

核方法(1)-介绍

 

核方法(2)-核的性质

 

Mercer’s theorem

 

The Elements of Statistical Learning

 

-end-

 

相关内容阅读

 

 
1.在线抽奖活动中如何实现中奖概率的自适应调整  
2.罗素的理发师和奥卡姆剃刀
4.集成学习之如何由弱变强
5.极大似然估计、极大后验估计和贝叶斯估计

 

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注