SVM算法推导及其分类的算法实现

SVM算法推导及其分类的算法实现摘要：本文从线性分类问题开始逐步的叙述支持向量机思想的形成，并提供相应的推导过程。简述核函数的概念，以及kernel在SVM算法中的核心地位。介绍松弛变量引入的SVM算法原因，提出软间隔线性分类法。概括SVM分别在一对一和一对多分类问题中应用。基于SVM在一对多问题中的不足，提出SVM的改进版本DAGSVM。Abstract：Thisarticlebeginswithalinearclassificationproblem,GraduallydiscussformationofSVM,andtheirderivation.Descriptiontheconceptofkernelfunction,andthecorepositioninSVMalgorithm.Describesthereasonsfortheintroductionofslackvariables,andproposesoft-marginlinearclassification.SummarytheapplicationofSVMinone-to-oneandone-to-manylinearclassification.BasedonSVMshortageinone-to-manyproblems,animprovedversionwhichcalledDAGSVMwasputforward.关键字：SVM、线性分类、核函数、松弛变量、DAGSVM1.SVM的简介支持向量机(SupportVectorMachine)是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力。对于SVM的基本特点，小样本，并不是样本的绝对数量少，而是与问题的复杂度比起来，SVM算法要求的样本数是相对比较少的。非线性，是指SVM擅长处理样本数据线性不可分的情况，主要通过松弛变量和核函数实现，是SVM的精髓。高维模式识别是指样本维数很高，通过SVM建立的分类器却很简洁，只包含落在边界上的支持向量。2.线性分类器及其求解线性分类器，是最简单也很有效的分类器形式。在一个线性分类器中，可以看到SVM形成的思路,并接触很多SVM的核心概念。用一个二维空间里仅有两类样本的分类问题来举例。如图1所示图1两类样本分类C1和C2是要区分的两个类别，在二维平面中它们的样本如图1所示。中间的直线就是一个分类函数，它可以将两类样本完全分开。一般的，如果一个线性函数能够将样本完全正确的分开，就称这些数据是线性可分的，否则称为非线性可分的。很容易看出来，图1中间那条分界线并不是唯一的，旋转一下，只要不把两类数据分错，仍然可以达到分类的效果，稍微平移一下，也可以。对同一个问题存在多个分类函数的时候，哪一个函数更好呢？必须要先找一个指标来量化“好”的程度，通常使用分类间隔来衡量。设平面中的直线方程为：(x)wxbg（1）设ix是一个有某一对象抽取出的n维向量，iy为分类标记，则可以定义点到某一超平面的间隔：(wb)iiyx（2）用||||ww和||||bw替代（2）式中的w和b得：1|(x)|||||iigw（3）将（3）式得到的间隔称为几何间隔，几何间隔所表示的正是点到超平面的欧氏距离，以上是单个点到某个超平面的距离定义，同样可以定义一个点的集合（就是一组样本）到某个超平面的距离为此集合中离超平面最近的点的距离。图2更加直观的展示出了几何间隔的含义。图2分割超平面图2中，H是分类面，H1和H2是平行于H，且过离H最近的两类样本的直线，H1与H，H2与H之间的距离就是几何间隔。几何间隔与样本的误分次数间存在关系：22()R误差分数其中的δ是样本集合到分类面的间隔，max||x||,i1,...,niR，即R是所有样本中向量长度最长的值。从上式可以看出，误分次数的上界由几何间隔决定。因此选择几何间隔来作为评价一个解优劣的指标，几何间隔越大的解，它的误差上界越小。因此最大化几何间隔成了我们训练阶段的目标。从（3）式可知，几何间隔与||w||是成反比的，因此最大化几何间隔与最小化||w||等价。通常不是固定||w||的大小而寻求最大几何间隔，而是固定间隔（例如固定为1），寻找最小的||w||。此时变成一个最优化问题，若想寻找一个小||w||，就可以用下面的式子表示：min||||w但实际上对于这个目标，常常使用另一个完全等价的目标函数来代替，如下：21min||||2w如果直接来解这个求最小值问题，很容易看出当||w||=0的时候就得到了目标函数的最小值。反映在图2中，就是1H与2H两条直线间的距离无限大，这个时候，所有的样本点都位于1H和2H中间，而我们原本的意图是，1H右侧的被分为正类，2H左侧的被分为负类，位于两类中间的样本则拒绝分类。这样，所有样本点都进入了无法分类的灰色地带。造成这种结果的原因是在描述问题的时候只考虑了目标，而没有加入约束条件，于是可以添加约束条件：[()b]1(i1,2,...,n)iiywx（n是总的样本数）于是可以将两类分类转化成数学形式，如下：21min||||2[()b]-10(i1,2,...,n)iiwywx（4）在这个问题中，自变量就是w，而目标函数是w的二次函数，所有的约束条件都是w的线性函数，这种规划问题就是二次规划（QuadraticProgramming，QP），由于它的可行域是一个凸集，因此它是一个凸二次规划。样本确定了w，用数学的语言描述，就是w可以表示为样本的某种组合：1122nnwxxx（5）式子中的i是拉格朗日乘子，而ix是样本点，也是向量，n就是总样本点的个数。为了方便描述，以下开始严格区别数字与向量的乘积和向量间的乘积，我会用iix表示数字和向量的乘积，而用,ijxx表示向量,ijxx的内积。因此（1）式严格的形式应该是：(x),bgwx（6）w不仅跟样本点的位置有关，还跟样本的类别有关。因此用下面这个式子表示w：121122nnnwxxyxyy（7）其中的iy就是第i个样本的标签，它等于1或者-1。其实以上式子的拉格朗日乘子12,,,n中，只有很少的一部分不等于0，这部分不等于0的拉格朗日乘子后面所乘的样本点，其实都落在1H和2H上，也正是这部分样本唯一的确定了分类函数。这部分可以确定分类的样本点，就叫做支持向量。因此原来的g(x)表达式可以写为：1(x),b(),niiiigwxyxxb，（8）其中，1()niiiiwyx上式可以变形为：1(x),niiiigyxxb（9）此时消去了上式中的w，问题从求w变成了求。这样就简化了原问题的求解，以这样的形式描述问题以后，优化问题少了很大一部分不等式约束。接下来看看SVM在线性分类器上所做的重大改进——核函数。3.SVM中的核函数根据模式识别理论，低维空间线性不可分的模式通过非线性映射到高维特征空间则可能实现线性可分，但是如果直接采用这种技术在高维空间进行分类或回归，则存在确定非线性映射函数的形式和参数、特征空间维数等问题，而最大的障碍则是在高维特征空间运算时存在的“维数灾难”。采用核函数技术可以有效地解决这样问题。如图3所示，当分类问题在低纬空间无法用线性分类方法解决时，可以通过将低纬空间的数据映射到高纬特征空间中，从而达到线性可分的目的。图3低纬度向高纬度空间映射从低纬度向高纬度转化关键在于寻在一个函数，但对目前没有一个系统的方法。对映射过程推导如下：1212123123222211221122222211121222211222(,),(,)(,,),(,,)(,2,),(,2,)2()(,)(,)TTTTTTTTTTTTTTTTTxxxxzzzzzzxxxxxxxxxxxxxxxxxxxxxxKxx（10）从上式可以得出，我们只关心高维空间里内积的值，而核函数就是接受低空间的输入，并计算出在高纬空间的内积值。(,)TKxx，就是我们要找的核函数。如图4图4在映射过程中的核函数于是上式，可以表示为1(x)(,)niiiigyKxxb。尽管给的问题是线性不可分的，但凡是要求内积的时候我们就选定的核函数来算。这样求出来的α再和你选定的核函数一组合，就可以得到线性分类器。但是任然存在以下两个问题：1．既然有很多的核函数，针对具体问题该怎么选择？2．如果使用核函数向高维空间映射后，问题仍然是线性不可分的，那怎么办？第一个问题：对核函数的选择，现在还缺乏指导原则！各种实验的观察结果的确表明，某些问题用某些核函数效果很好，用另一些就很差，但是一般来讲，径向基核函数是不会出太大偏差的一种，首选。对第二个问题的解决则引出了SVM中的另一个概念：松弛变量。4.SVM中的松弛变量假设有另一个训练集，只比原先这个训练集多了一个样本，映射到高维空间以后，也就多了一个样本点，但是这个样本的位置是这样的，如图5：图5新增加了一个样本后分类的结果就是图中黄色那个点，它是方形的，因而它是负类的一个样本，这单独的一个样本，使得原本线性可分的问题变成了线性不可分的。这样类似的问题（仅有少数点线性不可分）叫做“近似线性可分”的问题。对于人类思维，在大量的样本基础上，可能会认为图5中的黄点是错误的，是噪声，会自动的剔除掉。人的思维对于噪声数据具有容错性，可程序没有。由于我们原本的优化问题的表达式中，确实要考虑所有的样本点，在此基础上寻找正负类之间的最大几何间隔，而几何间隔本身代表的是距离，是非负的，像上面这种有噪声的情况会使得整个问题无解。这种解法其实也叫做“硬间隔”分类法，因为他硬性的要求所有样本点都满足和分类平面间的距离必须大于某个值。说明硬间隔的分类法其结果容易受少数点的控制。针对硬间隔的问题，解决方法也很明显，就是仿照人的思路，允许一些点到分类平面的距离不满足原先的要求。由于不同的训练集各点的间距尺度不太一样，因此用间隔（而不是几何间隔）来衡量有利于我们表达形式的简洁。原先对样本点的要求是：[()]1(1,2,...,)()iiywxbinn是样本数（11）该式说明，离分类面最近的样本点函数间隔也要比1大。如果要引入容错性，就给1这个硬性的阈值加一个松弛变量，即允许：[()]1(1,2,...,)()0iiiiywxbinn是样本数（12）因为松弛变量是非负的，因此最终的结果是要求间隔可以比1小。但是当某些点出现这种间隔比1小的情况时（这些点也叫离群点），意味着放弃了对这些点的精确分类，而这对分类器来说是种损失。但是放弃这些点也带来了好处，那就是使分类面不必向这些点的方向移动，因而可以得到更大的几何间隔。显然必须权衡这种损失和好处。得到的分类间隔越大，好处就越多。原始的硬间隔分类对应的优化问题：21min||||2..[()b]-10(i1,2,...,n)iiwSTywx（13）2||||w就是目标函数，希望它越小越好，因而损失就必然是一个能使之变大的量。那如何来衡量损失，有两种常用的方式，或者两种方法没有大的区别。如果选择了第一种，得到的方法的就叫做二阶软间隔分类器，第二种就叫做一阶软间隔分类器。把损失加入到目标函数里的时候，就需要一个惩罚因子，原来的优化问题就变成了下面这样：21min||||2..[()b]1(i1,2,...,n)0iiiiwSTywx（14）这个式子有这么几点要注意：一是并非所有的样本点都有一个松弛变量与其对应。实际上只有“离群点”才有，没离群的点松弛变量