SVM支持向量机

1SVM支持向量机目录一、简介...........................................................................................................................................1二、线性分类器...............................................................................................................................3三、分类间隔指标...........................................................................................................................4四、线性分类器的求解...................................................................................................................8五、核函数.......................................................................................................................................9六、松弛变量.................................................................................................................................11七、惩罚因子C.............................................................................................................................15八、SVM用于多类分类................................................................................................................17九、SVM的计算复杂度................................................................................................................19一、简介支持向量机在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力（或称泛化能力）。以下逐一分解并解释一下：统计机器学习之所以区别于传统机器学习的本质，就在于统计机器学习能够精确的给出学习效果，能够解答需要的样本数等等一系列问题。与统计机器学习的精密思维相比，传统的机器学习基本上属于摸着石头过河，用传统的机器学习方法构造分类系统是一种技巧，一个人做的结果可能很好，另一个人差不多的方法做出来却很差，缺乏指导和原则。VC维是对函数类的一种度量，可以简单的理解为问题的复杂程度，VC维越高，一个问题就越复杂。SVM关注的是VC维，和样本的维数是无关（甚至样本可以是上万维的，这使得SVM很适合用于解决文本分类的问题，也因此引入了核函数）。结构风险最小：机器学习本质上就是对问题真实模型的逼近（我们选择一个我们认为比较好的近似模型作为假设），而真实模型是未知的。假设与问题真实解之间的误差，叫做风险（更严格的说，误差的累积叫做风险）。我们选择了一个假设（即分类器）之后，我们可以用某些可以掌握的量来逼近误差，最直观的方法就是使用分类器在样本数据上的分类的结果与真实结果（样本是已标注过的数据，即准确的数据）之间的差值来表示。这个差值叫做经验风险Remp(w)。2以前的机器学习方法都把经验风险最小化作为努力的目标，但后来发现很多分类函数能够在样本集上很轻易的达到100%的正确率，在应用于真实分类时却一塌糊涂（即推广能力差，或称泛化能力差）。此时需要选择了一个足够复杂的分类函数（它的VC维很高），精确的记住每一个样本，但对样本之外的数据一律分类错误。基于经验风险最小化原则我们就会发现，该原则适用的大前提是经验风险要能够逼近真实风险才行，但实际上是不能逼近的，因为样本数相对于现实应用要分类的文本数来说太少，经验风险最小化原则只能在占很小比例的样本上做到没有误差，不能保证在更大比例的真实文本上也没有误差。统计学习从而引入泛化误差界的概念，即真实风险应该由经验风险，代表了分类器在给定样本上的误差，以及置信风险，代表了我们能在多大程度上信任分类器在未知文本上分类的结果。置信风险是无法精确计算的，只能给出一个估计的区间，使得整个误差只能计算上界，而无法计算准确值。置信风险与两个量有关，一是样本数量，显然给定的样本数量越大，我们的学习结果越有可能正确，此时置信风险越小；二是分类函数的VC维，显然VC维越大，推广能力越差，置信风险会变大。泛化误差界的公式为：R(w)≤Remp(w)+Ф(n/h)公式中R(w)就是真实风险，Remp(w)就是经验风险，Ф(n/h)就是置信风险。统计学习的目标从经验风险最小化变为了结构风险最小，即经验风险与置信风险的和最小。SVM正是这样一种基于结构风险最小化的算法。SVM的其他特点：小样本，这里的小样本是相对的，对于算法来说，更多的样本几乎总是能带来更好的效果，与问题的复杂度相比，SVM算法要求的样本数是比较少的。非线性，SVM擅长应对样本数据线性不可分的情况，通过松弛变量（惩罚变量）！和核函数！来实现。高维模式识别是指样本维数很高，例如文本的向量表示，如果没有经过降维处理，出现几万维的情况很正常，其他算法基本无法处理。而SVM产生的分类器很简洁，用到的样本信息很少（仅用到那些称之为“支持向量”的样本），在样本维数很高的情况下，也不会给存储和计算造成困扰，可以适用于样本维数很高的情况。（例如：KNN算法在分类时要用到所有样本，样本数巨大，若每个样本维数高的话，基本无法应对）。3二、线性分类器线性分类器(感知机)是简单且有效的分类器形式.在一个线性分类器中,可以了解SVM形成的思路和SVM的核心概念。例1：如图，一个二维空间里仅有两类样本C1和C2是要区分的两个类别，中间的直线就是一个分类函数，它可以将两类样本完全分开。一般，若一个线性函数能够将样本完全分开，称这些数据是线性可分的，否则称为非线性可分。线性函数：在一维空间里就是一个点，在二维空间里就是一条直线，三维空间里就是一个平面，即n维空间中的（n-1）维组件，若不考虑空间维数，这种线性函数也称超平面（HyperPlane）。实际上，线性函数是实值函数（即函数的值是连续的实数），而分类问题（例如这里的二元分类问题—判断样本属于还是不属于一个类别的问题）需要离散的输出值，例如用1表示某个样本属于类别C1，而用-1表示属于C2，这时候只需要简单的在实值函数的基础上附加一个阈值即可，通过分类函数执行时得到的值大于还是小于这个阈值来确定类别归属。例如：有一个线性函数g(x)=wx+b，可以取阈值为0，当有一个样本xi需要判别时，若g(xi)0，就判别为类别C1，若g(xi)0，则判别为类别C2（等于时拒绝判断）。此时等价于给函数g(x)附加一个符号函数sgn()，即f(x)=sgn[g(x)]是真正的判别函数。关于g(x)=wx+b要注意三点：一，式中的x不是二维坐标系中的横轴，而是样本的向量表示，例如一个样本点的坐标是(3,8)，则xT=(3,8)，而不是x=3。二，形式并不局限于二维，在n维空间中仍可以使用这个表达式，只是式中的w为n维向量（在二维的这个例子中，w是二维向量，为表示方便，以下不区别列向量和它的转置）；三，g(x)不是中间那条直线的表达式，中间那条直线的表达式是g(x)=0，即wx+b=0，这个函数叫做分类面。4中间那条分界线并不是唯一的，若稍微旋转一下，只要不把两类数据分错，仍然可以达到上面的效果，稍微平移一下，也可以。此时需考虑，对同一个问题存在多个分类函数的时候，哪一个函数更好，此时需要“分类间隔”指标。三、分类间隔指标分类间隔模型可以判断通过训练建立的分类模型的好坏。在进行文本分类时，可以让计算机将每一个样本看作一个向量（即文本特征组成的向量）和一个标记（标示此样本属于哪个类别）的组合。如Di=(xi,yi)中，xi是文本向量（维数很高），yi是分类标记。在二元线性分类中，这个表示分类的标记只有两个值，1和-1（表示属于或不属于这个类）。有了这种表示法，我们就可以定义一个样本点到某个超平面的间隔：δi=yi(wxi+b)若某个样本属于该类别，wxi+b0，而yi也大于0；若不属于该类别，wxi+b0，yi也小于0，这意味着yi(wxi+b)总是大于0的，而且它的值就等于|wxi+b（即|g(xi)|）。将w和b进行归一化，即用w/||w||和b/||w||分别代替原来的w和b，那么间隔就可以写成解析几何中点xi到直线g(x)=0的距离公式经推广，表示到超平面g(x)=0的距离，g(x)=0就是第二节中提到的分类超平面。||w||叫做向量w的范数，范数是对向量长度的一种度量。常用的向量长度指的是它的2-范数，范数最一般的表示形式为p-范数，即向量w=(w1,w2,w3,……wn)的p-范数为：当p=2的时，就是传统的向量长度。当不指明p时，使用||w||，即不关心p的值；或已指明p的值。当用归一化的w和b代替原值后的间隔叫做几何间隔，表示的是点到超平面的欧氏距离，简称“距离”。以上是单个点到某个超平面的距离，同样可以定义一个点的集合（即一组样本）到某个超平面的距离为此集合中离超平面最近的点的距离。如图所示：5H是分类面，H1和H2平行于H，且是过离H最近的两类样本的直线，H1与H，H2与H之间的距离就是几何间隔。几何间隔与样本的误分次数间存在如下关系：δ是样本集合到分类面的间隔，R=max||xi||i=1,...,n，即R是所有样本中（xi是以向量表示的第i个样本）向量长度最长的值（代表样本的分布广度）。这个误分次数一定程度上代表分类器的误差。由上式可知，样本已知时，误分次数的上界由几何间隔决定。几何间隔越大，误差上界越小。最大化几何间隔是训练阶段的目标。间隔：δ=y(wx+b)=|g(x)|几何间隔：即δ=||w||δ几何。几何间隔与||w||成反比，因此最大化几何间隔与最小化||w||是一回事。一般固定间隔（例如1），寻找最小的||w||。凡是求一个函数的最小值（或最大值）的问题都可以称为寻优问题（规划问题），找最大值的问题可以通过加一个负号变为找最小值的问题，因此我们下面讨论的时针对找最小值的6过程来进行。目标函数为：，为方便后期进行求导等处理，等价于，易看出当||w||=0时目标函数的值最小。反映在图中，就是H1与H2两条直线间的距离无限大，这时，所有样本点（无论正样本还是负样本）都跑到了H1和H2中间，而操作时，H1右侧的点被分为正类，H2左侧的点被分为负类，位于两类中间的样本则拒绝分类。这时，所有样本点都进入了无法分类的灰色地带。造成这种结果的原因是在描述问题时只考虑了目标，而未加入约束条件，约束条件就是在求解过程中必须满足的条件，体现在问题中的某些样本点必须在H1