SVM简介

支持向量机简介（supportvectormachine）苏志铭2015.5.20Outline•SVM简介•线性分类器•线性分类器求解•核函数•松弛变量•SVM的多分类•总结SVM简介支持向量机，因其英文名为supportvectormachine，故一般简称SVM，支持向量机是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力。VC维：对函数类的一种度量，可以简单的理解为问题的复杂程度，VC维越高，一个问题就越复杂。结构风险：结构风险为经验风险与置信风险之和。经验风险，代表了分类器在给定样本上的误差；置信风险，代表了我们在多大程度上可以信任分类器在未知文本上分类的结果。线性分类器通俗来讲，SVM是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。以右图为例，在一个二维平面内，有两个类别的离散样本点，一条直线将两类样本分开。一个线性函数，如果能将样本完全正确分开，这些数据即为线性可分。线性函数在一维空间为一个点，二维空间是一条直线，三维空间里是一个平面。如果不关注维数，线性函数被统称为——超平面。线性分类器假设有一个线性函数：我们可以取阈值为0，如果有一个样本需要判别，如果，判断该样本属于类别C1，如果，判断该样本属于类别C2，等于的时候就拒绝判断。于是，图中中间那条直线就可以表达为，即，这个函数也被叫分类面。但是，很容易看出，中间那条分界线并不是唯一的，只要稍微旋转一下，仍然可以正确分类两类数据，或者，稍微平移一下。通常使用叫做“分类间隔”的指标来找到最优分类面。()bTgxwx()0igx()0igx𝑥𝑖()=0gxb=0Twx线性分类器通过一个分类面，可以将上图中两类样本分开，平面两边数据的类别y可以分别用1和-1表示。定义一个样本点到超平面的函数间隔为：，超平面关于数据集的函数间隔为其中的最小值。那么，当，yi同时大于0，当,yi同时小于0。所以，现在把w和b进行一下归一化，即用w/||w||和b/||w||分别代替原来的w和b，那么间隔就可以写成这个式子正好是解析几何中，点xi到直线的距离公式，推广一下，那么就是样本点xi到分类超平面的距离。线性分类器iiiybTwx𝑤𝑇𝑥i+b0𝑤𝑇𝑥i+b0iiib=gTwxxii1gxw()=0gx()=0gx线性分类器当用归一化的w和b代替原值之后的间隔有一个专门的名称，叫做几何间隔，几何间隔所表示的正是点到超平面的欧氏距离。以上是单个点到某个超平面的距离定义，同样可以定义一个点的集合（就是一组样本）到某个超平面的距离为此集合中离超平面最近的点的距离。下面的图更加直观的展示出了几何间隔的现实含义：对一个数据点进行分类，当超平面离数据点的“间隔”越大，分类的确信度也越大。所以，为了使得分类的确信度尽量高，需要让所选择的超平面能够最大化这个“间隔”值。线性分类器的解选择一个最优分类超平面的问题，即最大化几何间隔的问题：固定间隔（即超平面的函数间隔），那么要使几何间隔最大化，即最大，也就是，。实际上，对于这个目标函数，经常利用另一个完全等价的函数代替：。1g几何xw()=1gx1wminw21min2w线性分类器的解很容易看出当||w||=0的时候就得到了目标函数的最小值。反映在图中，就是H1与H2两条直线间的距离无限大，这个时候，所有的样本点（无论正样本还是负样本）都跑到了H1和H2中间。所有的样本都不可分了。造成这种结果的原因是在描述问题的时候只考虑了目标，而没有加入约束条件，约束条件就是在求解过程中必须满足的条件，体现在我们的问题中就是样本点必须在H1或H2的某一侧（或者至少在H1和H2上），而不能跑到两者中间。我们前文提到过把间隔固定为1，这是指把所有样本点中间隔最小的那一点的间隔定为1。线性分类器的解按照间隔的定义，满足这些条件就相当于让下面的式子总是成立：因此我们的两类分类问题也被我们转化成了它的数学形式，一个带约束的最小值的问题：subjectto因此，满足上面公式的分类面就是最优分类面，过在平行于分类面的的超平面H1和H2上的训练样本，即使得上式等号成立的训练样本，称为支持向量。iiyb1i=12,3...nnTwx，，，为样本总数21min2wiiyb-10i=12,3...nn，，，为样本总数Twx线性分类器的解求解上述的约束优化问题是一个二次凸规划问题，由于目标函数和约束条件都是凸的，根据最优化理论，这一问题存在全局最小解。应用Lagrange乘子法并满足KKT条件（Karush-Kuhn-Tucher），求得因此，分类函数为：对于新点x的预测，只需要计算它与训练数据点的内积即可（表示向量内积），此外，所谓SupportingVector也在这里显示出来——事实上，所有非SupportingVector所对应的系数α都是等于零的，因此对于新点的内积计算实际上只要针对少量的“支持向量”而不是所有的训练数据即可。1niiiiwyx1()，niiiigxyxxb线性分类器的解为什么非支持向量对应的等于零呢？直观上来理解的话，就是这些“后方”的点——正如我们之前分析过的一样，对超平面是没有影响的，由于分类完全有超平面决定，所以这些无关的点并不会参与分类问题的计算，因而也就不会产生任何影响了。计算过程中，通过Lagrangemultiplier得到的目标函数：注意到如果xi是支持向量的话，上式中红颜色的部分是等于0的（因为支持向量的函数间隔等于1，而对于非支持向量来说，函数间隔会大于1，因此红颜色部分是大于零的，而又αi是非负的，为了满足最大化，αi必须等于0。这也就是这些非支持向量的点的局限性。核函数之前一直在讨论的线性分类器,只能对线性可分的样本做处理。如果提供的样本线性不可分，结果很简单，线性分类器的求解程序会无限循环，永远也解不出来。这必然使得它的适用范围大大缩小，而它的很多优点我们实在不原意放弃，怎么办呢？是否有某种方法，让线性不可分的数据变得线性可分呢？举个例子，我们把横轴上a点到b点间的红色部分里的所有点定为正类，两边黑色部分定为负类，那么显然找不到一个线性函数，即一条直线（二维空间的线性函数）将其分开。但是，我们可以找到一条曲线，如右图，它的函数表达式为：2012()gxccxcx核函数问题是，这个函数并不是一个线性函数，但是，如果新建向量，y=[y1；y2；y3]=[1；x；x2]α=[α1；α2；α3]=[c0；c1；c2]这样g(x)就可以转化为f(y)=a,y=ay，在任意维度的空间中，这种形式的函数都是一个线性函数（只不过其中的a和y都是向量罢了）。原来在二维空间中一个线性不可分的问题，映射到四维空间后，变成了线性可分的！因此这也形成了我们最初想解决线性不可分问题的基本思路——向高维空间转化，使其变得线性可分。那么，是否可以找到一种映射，将输入空间映射到高维特征空间，最终在高维特征空间中构造出最优分离超平面，从而把平面上本身不好分的非线性数据分开呢？对于非线性的情况，SVM的处理方法是选择一个核函数，通过将数据映射到高维空间，来解决在原始空间中线性不可分的问题。核函数在线性不可分的情况下，支持向量机首先在低维空间中完成计算，然后通过核函数将输入空间映射到高维特征空间，最终在高维特征空间中构造出最优分离超平面，从而把平面上本身不好分的非线性数据分开。如图所示，一堆数据在二维空间无法划分，从而映射到三维空间里划分：核函数如果原始数据是不可线性划分的，按照公式：是无法进行正确分类的，那么就按照某种映射，将x映射为φ（x），以同样的映射，将w映射为φ（w），那么得到线性函数：它可将原问题可分。但是，如果先将数据映射到高纬空间，再进行内积计算，可能导致维数灾难，所以引进核函数来简化映射空间中的内积运算（先内积，再用核函数计算使得结果与上式结果相同，高维空间的内积运算转化为低维输入空间的核函数计算）即分类函数为：因此，尽管给出线性不可分的问题，通过选定核函数，就可以当做线性分类器使用。()gxwxb，()gxwxb，1()niiiigxyKxxb，核函数用不同核函数可以导致不同的支持向量机，常用的几种核函数有：•线性核函数•多项式核函数•高斯核函数（径向基核函数）•Sigmoid核函数松弛变量如果使用核函数向高维空间映射后，问题仍然是线性不可分，如图：用黑圈圈起来的蓝点就将本来线性可分的问题变得不可分，这个点偏离正常点很远，可能是噪点，但是在SVM模型中，本来就只用到了支持向量，噪点的存在影响会很大。为了处理这种情况，SVM允许数据点在一定程度上偏离超平面。那么，在有松弛的情况下，其实噪点也属于支持向量，不同的支持向量拉格朗日参数的值不同。松弛变量原来，我们的约束条件为：现在考虑到一些特殊点，约束条件变为：其中称为松弛变量，对应数据点xi允许偏离的函数间隔。当然，如果松弛变量任意大的话，那任意的超平面都是符合条件的了。所以，我们在原来的目标函数后面加上一项，使得这些松弛变量的总和也要最小：其中C为惩罚因子。松弛变量完整的式子为：这个式子有这么几点要注意：一是并非所有的样本点都有一个松弛变量与其对应。实际上只有“离群点”才有，或者也可以这么看，所有没离群的点松弛变量都等于0。二是松弛变量的值实际上标示出了对应的点到底离群有多远，值越大，点就越远。三是惩罚因子C决定了你有多重视离群点带来的损失，显然当所有离群点的松弛变量的和一定时，你定的C越大，对目标函数的损失也越大，此时就暗示着你非常不愿意放弃这些离群点，最极端的情况是你把C定为无限大，这样只要稍有一个点离群，目标函数的值马上变成无限大，马上让问题变成无解。四是惩罚因子C不是一个变量，整个优化问题在解的时候，C是一个你必须事先指定的值。松弛变量并不是每一个松弛变量都必须使用相同的惩罚因子C，可以对不同利群点采用不同的C值，来表明样本的重视程度。重要的样本C就取大点，反之取小点。对付数据集偏斜问题的方法之一就是在惩罚因子上作文章，那就是给样本数量少的负类更大的惩罚因子，表示我们重视这部分样本（因此我们的目标函数中因松弛变量而损失的部分就变成了：其中i=1…p都是正样本，j=p+1…p+q都是负样本。libSVM这个算法包在解决偏斜问题的时候用的就是这种方法。那C+和C-怎么确定呢？它们的大小是试出来的（参数调优），但是它们的比例可以有些方法来确定。咱们先假定说C+是5这么大，那确定C-的一个很直观的方法就是使用两类样本数的比来算。-11ppqijijpCC0iSVM的多分类SVM是一种典型的两类分类器，但现实中要解决的往往是多分类问题。几种方法：•一对多方法（One-Against-The-Rest）：如果有k类，在某一类和其他k-1类间建立超平面，建立k个SVM分类器，每个SVM分类器将某一类的数据从其他类的数据中鉴别出来，但是，有“数据集偏斜”问题，而且每次训练都用到了所有样本。•一对一方法（One-Against-One）：为任意两个类构建超平面，即k类需要训练k*（k-1）/2个SVM分类器，测试时采用投票，投票类别最多的为测试类别，但是如果k太大，训练和决策时就会很耗时；•SVM决策树（SVMDecisionTree）：将SVM与二叉树结合，构成多类分类器，形似有向无环图，也叫DAGSVM。缺点是，如果某个节点出错，那么错误就会在后续节点延续。SVM的多分类DAGSVM举例：在分类时,