摘录（二）

第6章 支持向量机
6.1 间隔与支持向量
给定训练样本集D={(x1,y1)，(x2,y2)，...，(xm,ym)},yi∈{-1,+1}，分类学习最基本的想法就是基于训练集D在样本空间中找到一个划分超平面，将不同类别的样本分开。但能将训练样本分开的划分超平面可能有很多，如图6.1所示，我们应该努力去找到哪一个呢？
图6.1 存在多个划分超平面将两类训练样本分开
直观上看，应该去找位于两类训练样本“正中间”的划分超平面，即图6.1中红色的那个，因为该划分超平面对训练样本局部扰动的“容忍”性最好。例如，由于训练集的局限性或噪声的因素，训练集外的样本可能比图6.1中的训练样本更接近两个类的分隔界，这将使许多划分超平面出现错误，而红色的超平面受影响最小。换言之，这个划分超平面所产生的分类结果是最鲁棒的，对未见示例的泛化能力最强。
法向量，决定了超平面的方向；位移项，决定了超平面与原点之间的距离。显然，划分超平面可被法向量w和位移b确定
若超平面能将训练样本正确分类，则总存在缩放变换
每个样本点对应一个特征向量。
距离超平面最近的这几个训练样本点使式(6.3)的等号成立，它们被称为“支持向量”(support vector)，两个异类支持向量到超平面的距离之和称为“间隔”(margin)。
图6.2 支持向量与间隔
欲找到具有“最大间隔”(maximum margin)的划分超平面，也就是要找到能满足式(6.3)中约束的参数w和b，使得r最大
图6.5
间隔貌似仅与w有关，但事实上b通过约束隐式地影响着w的取值，进而对间隔产生影响。
显然，为了最大化间隔，仅需最大化‖w‖-1，这等价于最小化‖w‖2。于是，式(6.5)可重写为
图6.6
这就是支持向量机（Support Vector Machine，简称SVM）的基本型。
6.2 对偶问题
“对偶问题”(dual problem)
KKT(Karush-Kuhn-Tucker)条件
支持向量机这个名字强调了此类学习器的关键是如何从支持向量构建出解；同时也暗示着其复杂度主要与支持向量的数目有关。
这显示出支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关。
那么，如何求解式(6.11)呢？不难发现，这是一个二次规划问题，可使用通用的二次规划算法来求解；然而，该问题的规模正比于训练样本数，这会在实际任务中造成很大的开销。为了避开这个障碍，人们通过利用问题本身的特性，提出了很多高效算法，SMO(Sequential Minimal Optimization)是其中一个著名的代表。
SMO的基本思路是先固定ai之外的所有参数，然后求ai上的极值。由于存在约束，若固定ai之外的其他变量，则ai可由其他变量导出.于是，SMO每次选择两个变量ai和aj，并固定其他参数。这样，在参数初始化后，SMO不断执行如下两个步骤直至收敛：
选取一对需更新的变量ai和aj;
固定ai和aj以外的参数，求解式(6.11)获得更新后的ai和aj。
注意到只需选取的ai和aj中有一个不满足KKT条件(6.13)，目标函数就会在迭代后增大[Osuna et al.,1997]。直观来看，KKT条件违背的程度越大，则变量更新后可能导致的目标函数值增幅越大。于是，SMO先选取违背KKT条件程度最大的变量。第二个变量应选择一个使目标函数值增长最快的变量，但由于比较各变量所对应的目标函数值增幅的复杂度过高，因此SMO采用了一个启发式：使选取的两变量所对应样本之间的间隔最大。一种直观的解释是，这样的两个变量有很大的差别，与对两个相似的变量进行更新相比，对它们进行更新会带给目标函数值更大的变化。
SMO算法之所以高效，恰由于在固定其他参数后，仅优化两个参数的过程能做到非常高效。
不难发现，这样的二次规划问题具有闭式解，于是不必调用数值优化算法即可高效地计算出更新后的ai和aj。
其中S={i|ai＞0,i=1,2,...,m}为所有支持向量的下标集。理论上，可选取任意支持向量并通过求解式(6.17)获得b，但现实任务中常采用一种更鲁棒的做法：使用所有支持向量求解的平均值
6.3　核函数