支持向量机（SVM）--3

上次说到支持向量机处理线性可分的情况，这次让我们一起学习一下支持向量机处理非线性的情况，通过引进核函数将输入空间映射到高维的希尔伯特空间，进而将线性不可分转化为线性可分的情况。好的，让我们详细的了解一下核函数的前世与今生~~~~~~~~

特征空间的隐式映射：核函数

已经了解到了支持向量机处理线性可分的情况，而对于非线性的情况，支持向量机的处理方法是选择一个核函数κ(·, ·)，通过将数据映射到高维空间，来解决在原始空间中线性不可分的问题。由于核函数的优良品质，这样的非线性扩展在计算量上并没有比原来复杂多少，这一点是非常难得的。当然，这要归功于核方法——除了支持向量机之外，任何将计算表示为数据点的内积的方法，都可以使用核方法进行非线性扩展。Minsky 和Papert 早就在20 世纪60 年代就已经明确指出线性学习器计算能力有限。为什么呢？因为总体上来讲，现实世界复杂的应用需要有比线性函数更富有表达能力的假设空间，也就是说，目标概念通常不能由给定属性的简单线性函数组合产生，而是应该一般地寻找待研究数据的更为一般化的抽象特征。而下文我们将具体介绍的核函数则提供了此种问题的解决途径，从下文你将看到，核函数通过把数据映射到高维空间来增加第一节所述的线性学习器的能力，使得线性学习器对偶空间的表达方式让分类操作更具灵活性和可操作性。因为训练样例一般是不会独立出现的，它们总是以成对样例的内积形式出现，而用对偶形式表示学习器的优势在为在该表示中可调参数的个数不依赖输入属性的个数，通过使用恰当的核函数来替代内积，可以隐式得将非线性的训练数据映射到高维空间，而不增加可调参数的个数（当然，前提是核函数能够计算对应着两个输入特征向量的内积）。

简而言之：在线性不可分的情况下，支持向量机通过某种事先选择的非线性映射（核函数）将输入变量映射到一个高维特征空间，在这个空间中构造最优分类超平面。我们使用支持向量机进行数据集分类工作的过程首先是同预先选定的一些非线性映射将输入空间映射到高维特征空间。

在高维特征空间中对训练数据通过超平面进行分类，避免了直接在原输入空间中寻找非线性函数来进行分类。支持向量机的分类函数具有这样的性质：它是一组以支持向量为参数的非线性函数的线性组合，因此分类函数的表达式仅和支持向量的数量有关，而独立于空间的维度，在处理高维输入空间的分类时，这种方法尤其有效，其工作原理如图所示：

        在我们遇到核函数之前，如果用原始的方法，那么在用线性学习器学习一个非线性关系，需要选择一个非线性特征集，并且将数据写成新的表达形式，这等价于应用一个固定的非线性映射，将数据映射到特征空间，在特征空间中使用线性学习器，因此，考虑的假设集是这种类型的函数：

在上文提到过对偶形式，而这个对偶形式就是线性学习器的一个重要性质，这意味着假设可以表达为训练点的线性组合，因此决策规则可以用测试点和训练点的内积来表示：

这里我直接给出一个定义：核是一个函数κ，对所有x, z ∈ X，满足κ(x, z) = ⟨ϕ(xi), ϕ(x)⟩，这里ϕ(·) 是从原始输入空间X 到内积特征空间F 的映射。

如何处理非线性数据

了线性情况下的支持向量机，它通过寻找一个线性的超平面来达到对数据进行分类的目的。不过，由于是线性方法，所以对非线性的数据就没有办法处理。举个例子来说，如图2.3所示的两类数据，分别分布为两个圆圈的形状，这样的数据本身就是线性不可分的，此时咱们该如何把这两类数据分开呢？

事实上，上图所述的这个数据集，是用两个半径不同的圆圈加上了少量的噪音生成得到的，所以，一个理想的分界应该是一个“圆圈”而不是一条线（超平面）。如果用X1 和X2 来表示这个二维平面的两个坐标的话，我们知道一条二次曲线（圆圈是二次曲线的一种特殊情况）的方程可以写作这样的形式：

现在让我们再回到支持向量机中的情形，假设原始的数据是非线性可分的，我们通过一个映射ϕ(·) 将其映射到一个高维空间中，数据变得线性可分了，这个时候，我们就可以使用原来的推导来进行计算，只是所有的推导现在是在新的空间，而不是原始空间中进行。当然，推导过程也并不是可以简单地直接类比的，例如，原本我们要求超平面的法向量w，但是如果映射之后得到的新空间的维度是无穷维的，要表示一个无穷维的向量描述起来就比较麻烦。于是我们不妨先忽略过这些细节，直接从最终的结论来分析，回忆一下，我们上一次中得到的最终的分类函数是这样的：

现在则是在映射过后的空间，即：

而其中的 也是通过求解如下的对偶问题而得到的

似乎是的：拿到非线性可分的数据，就找一个映射ϕ(·)，然后一股脑把原来的数据映射到新空间中，再按照线性可分情况下支持向量机的求解方法来做即可。不过事实上没有这么简单！其实刚才的方法稍想一下就会发现有问题：在最初的例子里，我们对一个二维空间做映射，选择的新空间是原始空间的

所有一阶和二阶的组合，得到了五个维度；如果原始空间是三维，那么我们会得到19 维的新空间，这个数目是呈爆炸性增长的，这给ϕ(·) 的计算带来了非常大的困难，而且如果遇到无穷维的情况，就根本无从计算了。所以就需要核函数出马了.

我们把这里的计算两个向量在隐式映射过后的空间中的内积的函数叫做核函数 Kernel Function，例如，我们的核函数为：

核函数能简化映射空间中的内积运算——刚好“碰巧”的是，在我们的支持向量机里需要计算的地方数据向量总是以内积的形式出现的。对比刚才我们上面写出来的式子，现在我们的分类函数为：

其中 由如下的对偶问题求解而得。

常用的核函数

核函数的本质

        上面说了这么一大堆，读者可能还是没明白核函数到底是个什么东西？我再简要概括下，即以下三点：

1. 实际中，我们会经常遇到线性不可分的样例，此时，我们的常用做法是把样例特征映射到高维空间中去；

2. 但进一步，如果凡是遇到线性不可分的样例，一律映射到高维空间，那么这个维度大小是会高到可怕的，那咋办呢？

3. 此时，核函数就隆重登场了，核函数的价值在于它虽然也是讲特征进行从低维到高维的转换，但核函数绝就绝在它事先在低维上进行计算，而将实质上的分类效果表现在了高维上，也就如上文所说的避免了直接在高维空间中的复杂计算。

        核方法是机器学学习中的重要的概念，弄懂这部分的内容对于后续的深入理解十分重要，在这儿特别推荐一本关于机器学习入门的一本书籍----统计学习方法---李航----清华大学出版社出版。