稀疏核机（中）—核方法

作者：stephenDC

导 读

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

SVM的基函数扩展

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

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

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

基扩展SVM的最优化问题

基扩展SVM的解

基扩展的不足

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

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

SVM的核扩展

引入核函数

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

核方法

核函数定义

Mercer定理

Reproducing Kernel Hilbert Space

核SVM

小结

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

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