搜索
统计学习方法——SVM01统计学习概述02支持向量机简介Content03支持向量机的实现原理04支持向量机的理解与总结03支持向量机的泛化1统计学习统计学习概述统计学习(StatisticalLearning)是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测与分析的一门学科。统计学习也被称为统计机器学习。统计学习主要用于对未知新数据进行预测与分析，精准的预测不仅能使计算机更加智能化，还可能给人们带来新的知识和发现。统计学习方法主要分为四类：监督学习、无监督学习、半监督学习和强化学习。统计学习方法的过程可以概括如下：从给定的、有限的训练数据集合出发，应用某个评价准则，从假设空间(学习模型的集合)中选取一个最优的模型，使它对已知训练数据及未知测试数据在给定的评价准则下有最优的预测。2支持向量机支持向量机简介支持向量机(SupportVectorMachine)是统计学习理论的一种实现方法，它较好地实现了结构风险最小化思想。支持向量机理论是由Vapnik和Cortes在1995年提出用于解决模式识别问题的方法，当时的SVM属于一种线性的分类模型，而后Boser、Guyon和Vapnik等人又引入核技巧，提出非线性支持向量机。支持向量机是基于VC维理论和结构风险最小化原理而构建的一种监督学习模型，主要用于分类和回归分析。SVM在解决小样本、非线性和高维模式识别中表现出特有的优势，并且比一般的学习机拥有更好的泛化和推广能力。3线性分类器(感知机)支持向量机原理感知机是二类分类的线性模型。其输入为实例的特征向量，输出为实例的类别，取+1和-1两个值。感知机学习旨在求出将训练数据进行线性划分的分离超平面。这里举个简单的二类分类问题的例子：输入数据点用x来表示，这是一个n维向量，而类别用y来表示，可以取1或-1，分别代表两个不同的类。要在n维的数据空间中找到一个超平面，其方程可以表示为：我们希望通过这个超平面可以把两类数据分隔开来。我们令,如果f(x)=0，那么x是位于超平面上的点。我们不妨要求对于所有满足f(x)0的点，其对应的y=-1，而f(x)0则对应y=1的数据点。即分类决策函数：y=sign(wTx+b)3线性分类器(感知机)支持向量机原理如图所示，两种颜色的点分别代表两个类别，红颜色的线表示一个可行的超平面。从几何直观上来说，由于超平面是用于分隔两类数据的，越接近超平面的点越“难”分隔，因为如果超平面稍微转动一下，它们就有可能跑到另一边去。反之，如果是距离超平面很远的点，例如图中的右上角或者左下角的点，则很容易分辩出其类别。理想情况下，我们希望f(x)的值都是很大的正数或者很小的负数，这样我们就能更加确信它是属于其中某一类别的。4函数间隔和几何间隔支持向量机原理在超平面wTx+b=0确定的情况下，|wTx+b|能够相对地表示点x距离超平面的远近。而wTx+b的符号与类标记y的符号是否一致能够表示分类是否正确。所以可用量y(wTx+b)来表示分类的正确性及确信度，这就是函数间隔(FunctionalMargin)。公式定义：而几何间隔(GeometricalMargin)定义为数据点x到超平面的距离。如图所示，对于一个点x，令其垂直投影到超平面上对应的点为x0，由于w是超平面的法向量，我们有又由于x0是超平面上的点，代入超平面的方程即可算出5最大间隔超平面支持向量机原理这里的γ是带符号的，我们需要的是它的绝对值，因此也乘上对应y的类别即可，因此实际上我们定义的几何间隔为：我们需要选取最大间隔作为目标函数来分类，很显然几何间隔是不会被||w||和b影响的，它只随着超平面变动而变动。因此，这是更合适的一个选择。这样一来，最优间隔分类器的目标函数即定义为：。由于我们的目标就是要确定超平面，因此可以把另一个变量固定下来，固定的方式有两种：一是固定||w||，当我们找到最优的时也就可以随之而固定；二是反过来固定，此时||w||也可以根据最优的得到。为了方便推导和优化，我们通常选择的是第二种，令=1，则此时我们的目标函数为：6最优间隔分类器支持向量机原理如图所示，中间的红色线条是最优超平面，另外两条线到红线的距离都是等于的。此时我们的最优间隔分类器为：由于求的最大值等价于求的最小值，因此函数可以改写成：7拉格朗日对偶（Lagrangeduality）支持向量机原理得到这个形式以后，就可以很明显地看出来，它是一个凸优化问题，或者更具体地说，它是一个凸二次优化问题——目标函数是二次的，约束条件是线性的。为了有效地求解凸优化问题，通常会将它作为原始最优化问题，应用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解。这样做的优点有两点：一是对偶问题往往更容易求解，二是为了更自然的引入核函数，进而推广到非线性分类问题。通过给每一个约束条件加上一个Lagrangemultiplier，我们可以将它们融入到目标函数里去：7拉格朗日对偶（Lagrangeduality）支持向量机原理根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：表示的就是对偶问题的最优值，并且有，对偶问题的最优值在这里提供了原始问题的最优值的一个下界。当满足KKT条件时，那么对偶问题的最优值就等于原始问题的最优值。首先让L关于w和b最小化，分别对w，b求偏导并令其等于0：带回原Lagrange函数得：7拉格朗日对偶（Lagrangeduality）支持向量机原理再对该Lagrange函数求极大，则得到关于对偶变量的优化问题：关于上述对偶问题的求解，需要应用SMO算法。在这里就不详细阐述了，我们只需知道，只要满足KKT条件，一定存在w*，α*，使得w*是原问题的解，α*是对偶问题的解。假设我们已经求得对偶问题的最优解α*,那么可以得到w*=∑α*yixi，b*=yj-∑α*yi(xi·xj)8支持向量支持向量机原理由得到的w，超平面方程可以写成所谓SupportingVector也在这里显示出来——事实上，所有非支持向量所对应的系数α都是等于零的，因此对于新点的计算实际上只要针对少量的“支持向量”而不是所有的训练数据。注意到如果xi是支持向量的话，上式中的拉格朗日乘数是等于0的。但对于非支持向量来说，由于αi是非负的，为了满足最大化，必须使得αi=0。9核技巧支持向量机原理之前我们所讲解的都是线性可分情况下的支持向量机，它通过寻找一个线性的超平面来达到对数据进行分类的目的。但是对于线性不可分的数据，线性支持向量机就没有办法处理了，于是乎需要一个更好的办法来处理非线性的情况。对于右边的这幅图来说，一个理想的分类器应该是一个“圆圈”而不是一条线（超平面）。如果用X1和X2来表示这个二维平面的两个坐标的话，一条二次曲线的方程可以写成这样的形式：如果我们构造另外一个五维的空间，其中五个坐标的值分别为Z1=X1，Z2=X12，Z3=X2，Z4=X22，Z5=X1X2，那么显然可以改写成一个新的方程：9核技巧支持向量机原理关于新的坐标Z，这正是一个超平面方程！也就是说，如果我们做一个映射Φ=R2__R5,将X映射成Z，那么在新的空间中原来的数据将变为线性可分的，从而就能用原来的推导公式进行处理了。只是现在所有的推导是在新的空间(特征空间)，而不是原始空间中进行的，因而要进行一次映射变换：我们对一个二维空间做映射，选择的新空间是原始空间的所有一阶和二阶的组合，得到了五个维度；如果原始空间是三维，那么我们会得到19维的新空间，这个数目是呈爆炸性增长的，这给Φ(·)的计算带来了非常大的困难(也就是俗称的维数灾难)。为了解决这个问题，支持向量机引入了核技巧。9核技巧支持向量机原理设两个向量和，Φ(·)就是之前那个到五维空间的映射，则经过特征映射过后：Φ(x1)=(η1，η12，η2，η22，η1η2)，Φ(x2)=(ξ1，ξ12，ξ2，ξ22，ξ1ξ2)内积为：。可以再来看一个方程：如果我们将映射函数Φ(·)改为那么我们会发现的结果等价于，这意味着我们并不需要显式的去计算映射后特征空间中向量的内积，我们只需计算原始空间中向量的内积的平方。在这里,我们就把这种函数称之为核函数(KernelFunction),即：9核技巧支持向量机原理核函数能简化特征空间中的内积运算——刚好“碰巧”的是，在SVM里需要计算的地方向量总是以内积的形式出现的。将核函数带入，现在我们的分类函数为：这样一来，我们避开了直接在高维的特征空间中进行计算，而结果却是等价的！但是找到这样的映射Φ和再计算其对应的核函数K几乎是不可能的事，通常我们直接选择一个核函数——我们知道它对应了某个映射，但是并不知道这个映射具体是什么。由于我们只需计算核函数即可，所以我们并不需要关心也没有必要求出所对应的映射的具体形式。10核函数支持向量机原理当然，我们选择核函数也有一定的标准，并不是任意的二元函数都能作为核函数。那怎么判断一个给定的函数K(x,y)是不是核函数呢？或者说，该函数要满足什么条件才能成为核函数？核函数通常是指的正定核函数，正定核函数的充要条件是：K是有效核函数==K对应的Gram矩阵是半正定的。常见的核函数有以下几种：⑴线性核函数：⑵多项式核函数：⑶径向基函数：⑷神经网络核函数：11结构风险最小化SVM的泛化经验风险最小化准则已经在神经网络等机器学习中得到了广泛的应用。该准则是从假设样本无穷大的条件下出发的，在有限样本(小样本)情况下，它无法解决学习机的复杂性和泛化能力之间的矛盾，采用该准则的学习机容易出现过学习现象。结构风险定义为经验风险与置信风险的和。解决过拟合的典型办法是正则化，正则化就是结构风险最小化策略的实现，即在经验风险上加一个正则化项(惩罚项)。11软间隔最大化SVM的泛化在使用了核函数后，SVM能够处理非线性情况下的数据了，但是在实际问题中，对于某些情况还是难以处理：并不是数据本身是非线性结构的，而是因为数据往往带有有噪音(Outliers)，将这些噪音除去后，剩下大部分的样本点组成的集合是线性可分的。11软间隔最大化SVM的泛化在这种情况下，这些特殊的样本点不能满足函数间隔大于等于1的约束条件。为了解决这个问题，可以对每个样本点引进一个松弛变量,使函数间隔加上松弛变量大于等于1。约束条件变为：同时，对于每个松弛变量，需要支付一个代价，目标函数变为：其中C是一个惩罚参数，用于控制间隔距离和分类误差的权重。(注意，其中ξ是需要优化的变量，而C是一个事先确定好的常量)相比之前的间隔分类函数，由于引入了松弛系数，对分类误差不再是0容忍了。因此也被称为：软间隔最大化11软间隔最大化SVM的泛化再次利用拉格朗日对偶求解目标函数，得到如下形式：分析方法和前面一样，转换成对偶问题后，对w、b和ξ求偏导：12SVM基本思想总结支持向量机在形式上类似一个神经网络，输出的是中间节点的线性组合，每个中间节点对应一个支持向量。其结构如下所示：12SVM基本思想总结支持向量机的实现思想：通过非线性映射把n维向量映射到高维特征空间中，使向量在高维空间中的映像具有线性关系，以便在这个空间中构造线性最优决策函数。在构造最优决策函数时，巧妙地利用原空间的核函数取代了高维特征空间中的内积运算，也被称为内积的回旋。核函数实现了输入输出间的非线性关系，避免了高维的计算灾难。因此，构造支持向量机可以分为两步：最优决策函数和内积的回旋，在此过程中，我们甚至无需知道映射Φ的具体形式。13SVM的特点总结支持向量机方法是集优化、核、优良泛化能力等特点于一身的统计学习理论的一种实现。根据有限的样本信息，在模型的复杂度和学习能力之间寻找最佳折衷，以获得最好的推广能力。主要特点如下：1.针对有限样本情况，采用结构风险最小化准则，使其具有很好的泛化能力；2.将分类问题转换成一个凸优化问题，这样可以获得全局最优解，解决了传统神经网络中无法避免的局部极值问题；3.利用支持向量和核函数巧妙地解决了维数问题，其算法复杂度与样本大小无关，非常适合处理高维计算问题。14SVM的研究意义总结目前，大量关于支持向量机的研究主要集中在设计快速的算法解决大规