第五篇 统计学习方法是如何实现分类与聚类的（十二）
清华大学计算机系 马少平
第十二节：
核函数与核方法
艾博士：简单地说，如果函数K(xi,xj)= φ(xi) ·φ(xj) ，则称 K(xi,xj)为核函数。
注意核函数是在原空间计算的函数，而φ(xi) ·φ(xj) 是在变换后新空间的向量点积。我们看式(5.76)非线性支持向量机对应的最优化问题：
这里主要是计算 φ(xi) ·φ(xj) ，如果能直接计算出 φ(xi) ·φ(xj) 的值，我们并不关心具体的变换函数 φ(xi) 是什么。
小明：对啊，我们关心的是 φ(xi) ·φ(xj) 而不是φ(xi) ，如果知道了核函数K(xi,xj) ，利用核函数直接计算出 φ(xi) ·φ(xj) 就可以了。但是，存在这样的核函数吗？即便存在，感觉核函数更复杂了，会比变换更容易定义吗？如果还是难于定义，那还是不解决问题啊。
艾博士：小明的担心是有道理的，如果不能更容易地获得核函数，那么这种通过核函数计算变换后的点积 φ(xi) ·φ(xj)的方法也就没有实际意义。
首先，核函数是存在的。比如对于刚才举例的式(5.81)这个变换：
小明经过简单的验证后说：二者果然相等啊，但是怎么找到合适的核函数呢？
其次，科学家们已经为我们找好了一些常用的核函数，对于应用研究来说，拿过来用就可以了。
在定义了核函数之后，依照前面讲过的式(5.76)～(5.80)非线性支持向量机的结果,非线性支持向量机对应的最优化问题为：
用核函数表示就是:
设该最小值问题的解：
在变换后的新空间得到最优分界超平面方程：
用核函数表示就是：
其中 xj、yj 为0<αj*<C 对应的样本及其类别标记。
由于我们并不知道变换函数 ，所以并不能显式地得到 ，将 带入到最优超平面方程式(5.84)中，有：
这就是在原空间中用核函数表示的非线性支持向量机对应的最优分界超曲面方程。
由此得到非线性支持向量机的分类决策函数：
小明：在变换后的新空间中，最优分界面是个超平面，式(5.88)给出的是在原空间用核函数表示的分界超曲面，不再是一个超平面。
艾博士：下面我们就介绍几个常用的核函数以及相应的最优分界超曲面方程：
（1）线性核函数
线性核函数其实就是不做任何变换，直接在原空间求解线性支持向量机问题。线性核函数的引入是为了将支持向量机问题统一在核函数框架之下。
（4）sigmoid核函数
其中tanh为双曲正切函数，γ 、r 为常量。
带入到式(5.88)中，有最优分界超曲面方程为：
值得注意的是，这里的两个超参数 γ、r 并不是在任意取值下都能使得sigmoid核函数满足核函数的条件，也就是说，当γ 、r 取值不当时，式(5.96)并不构成一个核函数，不满足非线性支持向量机的优化条件，这样构成的支持向量机也就不会有一个好的分类结果。
小明：艾博士您介绍了几个常用的核函数，那么在实际使用时，如何选择合适的核函数呢？
艾博士：如何选择核函数是一个经验性的技能，一般来说，如果样本分布是线性可分或者接近线性可分的，则采用线性核函数。多项式核函数也是在样本分布比较接近线性可分时效果比较好，不太适用于样本分布非线性比较严重的场合。高斯核函数是一个比较万能的核函数，多数情况下具有比较好的表现，当对样本分布缺乏了解时，可以首先考虑使用高斯核函数，如果效果不理想再考虑其他的核函数。对于高斯核函数来说，超参数 σ 如何取值也是值得考虑的因素， σ 取值过大容易造成欠拟合，而取值过小又容易造成过拟合，选择一个好的 σ 值，才会有最好的性能。图5.40给出了 σ 不同大小情况下最优分界超曲面示意图。图5.40(a)是 σ 值过大的情况，分界超曲面比较平缓，属于欠拟合。图5.40(b) σ 值比较合适，分界超曲面比较好地将两类分开，是我们希望得到的恰拟合。图5.40(c)σ 值过小，将一个类别圈成了若干小的圈圈，圈圈内为一个类别，圈圈外为另一个类别，造成了过拟合。欠拟合、过拟合都不是我们希望的结果。另外，样本x是由多个特征的取值构成的向量，有的特征取值范围可能比较大，有的特征取值可能比较小，这种情况下无论对哪种核函数都是不利的，会造成支持向量机分类性能下降。解决办法是对训练集中的样本做归一化处理，尽可能消除因特征取值范围不同造成的影响。这种情况下一定要记住，当使用支持向量机做分类时，对待分类样本也要做同样的归一化处理。总的来说，如何选择核函数并没有什么一定之规，在实际使用时，可以采用不同的核函数，多做些实验验证，哪种方法效果好就采用哪种方法，因为我们毕竟是为了获得一个性能更好的分类器。
图5.40 不同 值下的分界超曲面示意图
小明：我了解了，性能为王，能提高分类性能的就是好方法，而不拘泥于使用哪种方法。
艾博士：下面我们给一个非线性支持向量机的求解例子。
设 x1=(0,0) 为负类，y1=-1 ，x2=(1,1) 、x3=(-1,-1) 为正类，y2=1 、y3=1 。用如下核函数求解非线性支持向量机问题，并判定x=(0,1)的分类结果。
先计算出几个样本点间的核函数值：
从而得到待分类样本x=(0,1)的类别为负类。
图5.41给出了该问题的示意图，在原空间中，最优分界超曲面实际上是两条红色的直线，处于两条直线之间的样本点为负类，两条直线之外的样本点为正类。
图5.41 例题的最优分界超曲面示意图
小明：从前面给的两个支持向量机的例子可以看出，虽然通过对偶问题的求解已经大大简化了支持向量机的求解，但无论是线性支持向量机还是非线性支持向量机求解起来还是比较麻烦的，尤其是当训练样本比较多的时候更是如此。在实际问题中，支持向量机是如何求解的呢？
艾博士：小明你提到了一个很重要的问题，如果没有一个高效的求解算法，则支持向量机很难在实际中得到应用。
支持向量机问题，无论是线性的还是非线性的，最终都转化为了一个满足一定约束条件下关于的二次函数求最小值问题。由于是一个二次的凸函数，具有唯一的最小极值点，有很多算法可以求解该问题。但是当训练样本比较多时，求解效率是一个问题。事实上在支持向量机提出来的一段时间内，由于缺乏高效的求解算法，支持向量机方法应用的并不多，直到有了快速有效的方法提出来之后，才得到了广泛的应用。
序列最小最优化算法(SMO)是一个典型的求解支持向量机问题的算法。SMO算法采用启发式方法，每次选择两个变量进行优化，迭代地一步步逐步逼近问题的最优解。我们将在附录中详细给出SMO算法，这里就不多叙述了。
未完待续