搜索
研究报告题目支持向量机学习报告学号学生支持向量机学习报告支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力。支持向量机SVM(SupportVectorMachine)是AT&TBell实验室的V．Vapnik提出的针对分类和回归问题的统计学习理论。由于SVM方法具有许多优点和有前途的实验性能，该技术已成为机器学习研究领域中的热点，并取得很理想的效果，如人脸识别、手写体数字识别和网页分类等。1原理及方法SVM根据问题的复杂性可以分为线性可分SVM和非线性可分SVM，其基本原理如下：在进行文本分类的时候，每一个样本由一个向量（就是那些文本特征所组成的向量）和一个标记（标示出这个样本属于哪个类别）组成。如下：Di=(xi,yi)xi就是文本向量（维数很高），yi就是分类标记。在二元的线性分类中，这个表示分类的标记只有两个值，1和-1（用来表示属于还是不属于这个类）。有了这种表示法，可以定义一个样本点到某个超平面的间隔：yi(wxi+b)如果某个样本属于该类别的话，那么wxi+b0（因为我们所选的g(x)=wx+b就通过大于0还是小于0来判断分类），而yi也大于0；若不属于该类别的话，那么wxi+b0，而yi也小于0，这意味着yi(wxi+b)总是大于0的，而且它的值就等于|wxi+b|（也就是|g(xi)|）现在把w和b进行一下归一化，用w/||w||和b/||w||分别代替原来的w和b，间隔就可以写成当用归一化的w和b代替原值之后的间隔叫做几何间隔，几何间隔所表示的正是点到超平面的欧氏距离，简称几何间隔为“距离”。同样一个点的集合（就是一组样本）到某个超平面的距离为此集合中离超平面最近的点的距离。下面这张图展示出了几何间隔的现实含义：H是分类面，而H1和H2是平行于H，且过离H最近的两类样本的直线，H1与H，H2与H之间的距离就是几何间隔。间隔：δ=y(wx+b)=|g(x)|几何间隔：可以看出δ=||w||几何。几何间隔与||w||是成反比的，因此最大化几何间隔与最小化||w||完全是一回事。而我们常用的方法并不是固定||w||的大小而寻求最大几何间隔，而是固定间隔（例如固定为1），寻找最小的||w||。而凡是求一个函数的最小值（或最大值）的问题都可以称为寻优问题（也叫作一个规划问题），又由于找最大值的问题总可以通过加一个负号变为找最小值的问题，因此我们下面讨论的时候都针对找最小值的过程来进行。一个寻优问题最重要的部分是目标函数，顾名思义，就是指寻优的目标。例如我们想寻找最小的||w||这件事，就可以用下面的式子表示：但实际上对于这个目标，常常使用另一个完全等价的目标函数来代替，那就是：当2w到最小时，||w||也达到最小，反之亦然（前提当然是||w||描述的是向量的长度，因而是非负的）。将约束条件改写为：从KKT条件得知只有函数间隔是1（离超平面最近的点）的线性约束式前面的系数，也就是说这些约束式，对于其他的不在线上的点()，极值不会在他们所在的范围内取得，因此前面的系数.实线是最大间隔超平面，假设×号的是正例，圆圈的是负例。在虚线上的点就是函数间隔是1的点，那么他们前面的系数，其他点都是。这三个点称作支持向量。构造拉格朗日函数如下：按照对偶问题的求解步骤来进行，首先求解的最小值，对于固定的，的最小值只与w和b有关。对w和b分别求偏导数。并得到将上式带回到拉格朗日函数中得到，此时得到的是该函数的最小值（目标函数是凸函数）代入后，化简过程如下：最后得到由于最后一项是0，因此简化为将向量内积表示为此时的拉格朗日函数只包含了变量。然而我们求出了才能得到w和b。接着是极大化，首先由于目标函数和线性约束都是凸函数，而且这里不存在等式约束h。存在w使得对于所有的i，。因此，一定存在使得是原问题的解，是对偶问题的解。如果求出了，根据即可求出w（也是，原问题的解）。然后即可求出b。即离超平面最近的正的函数间隔要等于离超平面最近的负的函数间隔。由于前面求解中得到考虑，根据求解得到的，代入前式得到也就是说，以前新来的要分类的样本首先根据w和b做一次线性运算，然后看求的结果是大于0还是小于0,来判断正例还是负例。现在有了，我们不需要求出w，只需将新来的样本和训练数据中的所有样本做内积和即可。我们从KKT条件中得到，只有支持向量的，其他情况。因此，只需求新来的样本和支持向量的内积，然后运算即可。希望将得到的特征映射后的特征应用于SVM分类，而不是最初的特征。这样，我们需要将前面公式中的内积从，映射到。将特征映射到高维空间后，往往就可分了。将核函数形式化定义，如果原始特征内积是，映射后为，那么定义核函数（Kernel）为只需先计算，然后计算即可，然而这种计算方式是非常低效的。比如最初的特征是n维的，我们将其映射到维，然后再计算，这样需要的时间。先看一个例子，假设x和z都是n维的，展开后，得可以只计算原始特征x和z内积的平方（时间复杂度是O(n)），就等价与计算映射后特征的内积。也就是说我们不需要花时间了。如果映射函数（n=3时），根据上面的公式，得到也就是说核函数只能在选择这样的作为映射函数时才能够等价于映射后特征的内积。再看一个核函数对应的映射函数（n=3时）是更一般地，核函数对应的映射后特征维度为。由于计算的是内积，我们可以想到IR中的余弦相似度，如果x和z向量夹角越小，那么核函数值越大，反之，越小。因此，核函数值是和的相似度。再看另外一个核函数这时，如果x和z很相近（），那么核函数值为1，如果x和z相差很大（），那么核函数值约等于0。由于这个函数类似于高斯分布，因此称为高斯核函数，也叫做径向基函数(RadialBasisFunction简称RBF)。它能够把原始特征映射到无穷维。既然高斯核函数能够比较x和z的相似度，并映射到0到1，下面的图说明在低维线性不可分时，映射到高维后就可分了，使用高斯核函数。注意，使用核函数后，怎么分类新来的样本呢？线性的时候我们使用SVM学习出w和b，新来样本x的话，我们使用来判断，如果值大于等于1，那么是正类，小于等于是负类。在两者之间，认为无法确定。如果使用了核函数后，就变成了只需将替换成。给定m个训练样本，每一个对应一个特征向量。那么，将任意两个和带入K中，计算得到。i可以从1到m，j可以从1到m，这样可以计算出m*m的核函数矩阵（KernelMatrix）。如果假设K是有效地核函数，那么根据核函数定义可见，矩阵K应该是个对称阵。首先使用符号来表示映射函数的第k维属性值。那么对于任意向量z，得最后一步和前面计算时类似。如果K是个有效的核函数（即和等价），那么，在训练集上得到的核函数矩阵K应该是半正定的（）这样得到一个核函数的必要条件：K是有效的核函数==核函数矩阵K是对称半正定的。这个条件也是充分的，由Mercer定理来表达。Mercer定理：如果函数K是上的映射（也就是从两个n维向量映射到实数域）。那么如果K是一个有效核函数（也称为Mercer核函数），那么当且仅当对于训练样例，其相应的核函数矩阵是对称半正定的。Mercer定理表明为了证明K是有效的核函数，那么不用去寻找，而只需要在训练集上求出各个，然后判断矩阵K是否是半正定（使用左上角主子式大于等于零等方法）即可。把一个本来线性不可分的文本分类问题，通过映射到高维空间而变成了线性可分的。就像下图这样：圆形和方形的点各有成千上万个。现在想象我们有另一个训练集，只比原先这个训练集多了一篇文章，映射到高维空间以后（当然，也使用了相同的核函数），也就多了一个样本点，但是这个样本的位置是这样的：就是图中黄色那个点，它是方形的，因而它是负类的一个样本，这单独的一个样本，使得原本线性可分的问题变成了线性不可分的。这样类似的问题（仅有少数点线性不可分）叫做“近似线性可分”的问题。但这种对噪声的容错性是人的思维带来的。由于原本的优化问题的表达式中，确实要考虑所有的样本点，在此基础上寻找正负类之间的最大几何间隔，而几何间隔本身代表的是距离，是非负的，像上面这种有噪声的情况会使得整个问题无解。这种解法其实也叫做“硬间隔”分类法，因为他硬性的要求所有样本点都满足和分类平面间的距离必须大于某个值。仿照人的思路，允许一些点到分类平面的距离不满足原先的要求。由于不同的训练集各点的间距尺度不太一样，因此用间隔（而不是几何间隔）来衡量有利于我们表达形式的简洁。我们原先对样本点的要求是：意思是说离分类面最近的样本点函数间隔也要比1大。如果要引入容错性，就给1这个硬性的阈值加一个松弛变量，即允许因为松弛变量是非负的，因此最终的结果是要求间隔可以比1小。但是当某些点出现这种间隔比1小的情况时（这些点也叫离群点），意味着我们放弃了对这些点的精确分类，而这对我们的分类器来说是种损失。但是放弃这些点也带来了好处，那就是使分类面不必向这些点的方向移动，因而可以得到更大的几何间隔（在低维空间看来，分类边界也更平滑）。显然我们必须权衡这种损失和好处。好处很明显，我们得到的分类间隔越大，好处就越多。回顾我们原始的硬间隔分类对应的优化问题：||w||2就是目标函数（当然系数可有可无），希望它越小越好，因而损失就必然是一个能使之变大的量（能使它变小就不叫损失了，我们本来就希望目标函数值越小越好）。那如何来衡量损失，1lii其中l都是样本的数目。把损失加入到目标函数里的时候，就需要一个惩罚因子（cost，也就是libSVM的诸多参数中的C），原来的优化问题就变成了下面这样：一是并非所有的样本点都有一个松弛变量与其对应。实际上只有“离群点”才有，所有没离群的点松弛变量都等于0（对负类来说，离群点就是在前面图中，跑到H2右侧的那些负样本点，对正类来说，就是跑到H1左侧的那些正样本点）。二是松弛变量的值实际上标示出了对应的点到底离群有多远，值越大，点就越远。三是惩罚因子C决定了重视离群点带来的损失的程度，显然当所有离群点的松弛变量的和一定时，定的C越大，对目标函数的损失也越大，此时就暗示着不愿意放弃这些离群点，最极端的情况是把C定为无限大，这样只要稍有一个点离群，目标函数的值马上变成无限大，问题变成无解，这就退化成了硬间隔问题。四是惩罚因子C不是一个变量，整个优化问题在解的时候，C是一个必须事先指定的值，指定这个值以后，解一下，得到一个分类器，然后用测试数据看看结果怎么样，如果不够好，换一个C的值，再解一次优化问题，得到另一个分类器，再看看效果，如此就是一个参数寻优的过程，但这和优化问题本身决不是一回事，优化问题在解的过程中，C一直是定值。从大的方面说优化问题解的过程，就是先试着确定一下w，也就是确定了前面图中的三条直线，这时看看间隔有多大，又有多少点离群，把目标函数的值算一算，再换一组三条直线（你可以看到，分类的直线位置如果移动了，有些原来离群的点会变得不再离群，而有的本来不离群的点会变成离群点），再把目标函数的值算一算，如此往复（迭代），直到最终找到目标函数最小时的w。松弛变量也就是解决线性不可分问题的方法，核函数的引入也是为了解决线性不可分的问题。其实两者还有些不同。以文本分类为例。在原始的低维空间中，样本相当的不可分，无论怎么找分类平面，总会有大量的离群点，此时用核函数向高维空间映射一下，虽然结果仍然是不可分的，但比原始空间里的要更加接近线性可分的状态（就是达到了近似线性可分的状态），此时再用松弛变量处理那些少数“冥顽不化”的离群点，更加简单有效。对比复杂的推导过程，SVM的思想确实简单。是在样本中去找分隔线，为了评判哪条分界线更好，引入了几何间隔最大化的目标。之后解决目标函数的最优化问题。在解决最优化的过程中，发现了w可以由特征向量内积来表示，进而发现了核函数，仅需要调整核函数就可以将特征进行低维到高维的变换，在低维上进行计算，实质结果表现在高维上。由于并不是所有的样本都可分，为了保证SVM的通用性，进行了软间隔的