线性口袋算法改进了线性感知器算法.doc

线性口袋算法改进了线性感知器算法，能够直接处理线性不可分问题。1、支持向量机理论1、SVM从线性可分情况下的最优分类面发展而来。H为分类线,H1, H2分别为过各类中离分类线最近的样本且平行于分类线的直线, 它们之间的距离叫做分类间隔(margin)。推广到高维空间，最优分类线就变为最优分类面。 2、最优分类面就是要求分类线不但能将两类正确分开(训练错误率为0),且使分类间隔最大。3、SVM考虑寻找一个满足分类要求的超平面,并且使训练集中的点距离分类面尽可能的远,也就是寻找一个分类面使它两侧的空白区域(margin)最大。4、过两类样本中离分类面最近的点且平行于最优分类面的超平面上H1,H2的训练样本就叫做支持向量。2、广义最优分类面假定训练数据可以被一个超平面分开我们进行正归化此时分类间隔等于使最大间隔最大等价于使最小我们可以对它进行归一化，使得所有样本都满足，即离分类面最近的样本满足，这样分类间隔就等于。因此要求分类间隔最大，就是要求最小。而要求分类面对所有样本正确分类，就是要求满足。因此，满足上面公式且使最小的分类面就是最优分类面。最优分类面问题可以表示成约束优化问题MinimizeSubject to定义Lagrange函数求偏导：得将上式代入拉格朗日函数，消去w和b得到原问题的Wolf对偶（Dual）问题：x1=(0,0),y1=+1x2=(1,0),y2=+1x3=(2,0),y3=-1x4=(0,2),y4=-1可调用Matlab中的二次规划程序，求得a1,a2,a3,a4的值，进而求得w和b的值。而分划超平面仅仅依赖于为零的训练点，而与对应于为零的那些训练点无关。很多情况下，训练数据集是线性不可分的，Vapnik等人提出了用广义分类面（松弛子）来解决这一问题。非线性问题通过非线性变换将它转化为某个高维空间中的线性问题，在这个高维空间中寻找最优分类面。近似线性可分：当最优分类面不能把两类点完全分开时（线性不可分），如果希望在经验风险和推广性能之间求得某种均衡，则可以通过引入超松弛因子，允许错分样本的存在，此时的分类面满足：两个目标：1.间隔尽可能大2.错划程度尽可能小当时，样本点正确分类；当时，样本点被错分。因此，引入一个惩罚参数，新的目标函数变为:体现了经验风险，而则体现了表达能力。所以惩罚参数实质上是对经验风险和表达能力匹配一个裁决。当时，近似线性可分SVC的原始问题退化为线性可分SVC的原始问题。1、 用间隔定量地定义了置信风险：间隔越大，置信风险越小，间隔越小，置信风险越大2、 用参数C实现了经验风险与置信风险的折中3、 最优分类超平面只由少数支持向量决定，问题具有稀疏性4、 模型为凸二次规划模型，没有陷入局部最优解的问题，任何局部最优解都是全局最优解5、 通过使用核方法，具备了强大的非线性处理能力 注：问题具有稀疏性是指决策时可以不管非支持向量的样本，而仅用到少数支持向量样本。注意训练时还是用到了所有的样本。核函数SVM中不同的内积核函数将形成不同的算法,主要的核函数有三类：多项式核函数得到q阶多项式分类器。径向基函数S形函数对非线性分类问题，若在原始空间中的简单最优分类面不能得到满意的分类结果，则可以通过非线性变换转化为某个高维空间的线性问题，在变换空间求最优分类面，SVM通过核函数变换，巧妙地解决了这个问题。如何针对不同的问题选择不同的核函数仍然是一个悬而未决的问题。由于寻找最优分类面函数只涉及到训练样本之间的点积运算，所以将样本映射到高维空间H时，算法仅使用H空间中的点积，而没有单独出现。能够找到一个函数K使得，这种点积运算是可以在原空间中的函数实现的，甚至没有必要知道变换的形式。根据泛函的有关理论，只要一种核函数满足Mercer条件，它就对应某一种变换空间中的点积。引入内积函数之后，目标函数式变为：相应的分类函数式变为：Mercer条件对于任意的对称函数，它是某个特征空间中的内积运算的充要条件是，对于任意的。在最优分类面中采用适当的内积函数就可以实现某一非线性变换后的线性分类,而计算复杂度却没有增加。其中，是模型的解。这就是支持向量机。概况地说，支持向量机就是首先通过用内积函数定义的非线性变换将输入空间变换到一个高维空间，在这个空间中求最优分类面。支持向量机(support vector machines)是由贝尔实验室研究者Vapnik于20世纪90年代最先提出的一种新的机器学习理论，是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷，以期获得最好的推广能力。 统计方法是从事物外在的表现去推断该事物可能的规律性。统计学习理论是针对小样本情况下的机器学习理论，它依据算法的经验风险以及算法本身的构造来推测它的实际风险，并获得较好的泛化能力。统计学习理论将算法的训练过程看作算法向训练样本学习的过程。统计学习理论是一种专门研究小样本情况下机器学习规律的理论,其核心概念是VC维。VC维反映了函数集的学习能力,VC维越大则学习机器越复杂。一般地,对于N维线性空间中的VC维是N+1。但是在非线性情况下,VC维通常是无法计算的。在应用统计学习理论时，可以通过变通的办法避开直接求VC维的问题。统计学习理论从VC维的概念出发,推导出了关于经验风险和实际风险之间关系,并得出结论是:学习机器的实际风险是由两部分组成的,一是经验风险(训练误差),另一个是置信范围,它和学习机器的VC维及训练样本数有关,可以简单表示为。置信范围随的增大而减小。对于一个特定的学习问题,当样本数固定时,如果学习机器的VC维h越高,则置信范围越大,从而导致实际风险与经验风险之间的差就越大。因此,在学习时,不但要使经验风险尽可能小,也要控制VC维,从而减小置信范围,使期望风险最小,这就是结构风险最小化原则(SRM)。结构风险最小化原则的思想是:把函数集构造为一个函数子集序列,使各子集按照VC维的大小排列,在每个子集中寻找最小经验风险,在子集中折衷考虑经验风险和置信范围,取得实际风险的最小,如图1所示。结构风险最小化原则统计学习理论的4个部分：1. 学习过程一致性的理论。一个基于经验风险最小化原则的学习过程满足什么条件，它的经验风险与实际风险趋向一致。2. 学习过程收敛速度的理论。如果学习过程的经验风险与实际风险趋向一致，那么它们间的接近速度随着训练样本数的增加是如何变化的。哪些因素控制着它们接近的速度。3. 控制学习过程泛化能力的理论。采用前两部分的结论改进学习过程。4. 构造学习算法的理论。采用前三部分的结论，在分类和拟合问题中构造现实的学习算法。机器学习的基本问题机器学习的主要问题是从一组观测数据集的数据出发，得到一些不能通过原理分析而得到的规律，进而利用这些规律对未来的数据或者无法观测到的数据进行预测和分析学习问题就是从给定的函数集 ，选择出能够最好地逼近训练器响应的函数。机器学习的目标可以形式化的表示为：根据n个独立同分布的观测样本，在一组函数集中求出一个最优函数，使其对未知样本进行估计时，最小化期望风险泛函。其中联合概率分布是未知的，是用对y进行预测时造成的损失，称为损失函数。简单地说，学习的目标就是求一映射函数，使之与实际系统映射的差异最小。经验风险最小化问题学习机器产生的映射函数与实际系统的映射之间的差异可以用单个样本点上的损失函数来描述。损失函数在总体样本集上的数学期望，即为期望风险的泛函： 损失函数描述了映射函数与实际系统在总体集上的差异，将学习的目标变成了最小化期望风险。在实际的问题中，无法直接的计算得到。在传统的机器学习方法中，通常将经验风险作为期望风险的估计值，学习的目标就是使经验风险最小，强调利用经验风险最小化（ERM）原则进行学习。但实际上，用ERM原则代替最小化期望风险泛函，只是直观上合理的想当然做法而已，理论依据并不充分，容易“过学习”(overfitting)。期望风险=经验风险（训练误差）+置信范围。VC维与学习一致性理论对于二值分类问题，其目标函数f只有0和1两种取值，称这类函数为指示函数。对于一个指示函数集，如果存在h个数据样本能够被函数集中的函数按所有可能得种形式分开，则称函数集能够把h个数据样本打散。函数集的VC维就是能打散的最大数据样本数目。一般而言，VC维代表了机器的学习能力，其值越大表明其学习机器的学习能力越强，但学习机器就越复杂。然而，目前还没有通用的关于计算任意函数集的VC维的理论，只有对一些特殊函数集的VC维可以准确知道。对于指示函数集和概率分布函数，如果下列两序列概率地收敛到同一极限，则称为经验风险最小一致性。，。经验风险最小一致性经验风险最小化学习过程一致性的充分必要条件是函数集的VC维有限，且快速收敛。这个充要条件在理论上有重要的意义，但是实践中一般无法直接应用。给定的对应着一个或一组超平面，其VC维与h满足下面的函数关系：，其中f（）是单调增函数，即h与分类间隔成反比关系。因此，当训练样本给定时，分类间隔越大，则所对应的VC维越小。置信范围和学习机器的VC维及训练样本数有关，随的变化趋势如图所示。n：训练样本数，h：VC维，：置信范围结构化风险最小化通常，在小样本的情况下，对于复杂的学习机器，其训练误差过小，但反而造成了置信范围的增大，从而导致泛化性能下降。这往往是由于学习机器的结构不合理造成的。因此，ERM原则在样本有限时是不合理的。为此，统计学习理论提出了一种新的策略，在保证ERM原则的基础上，降低学习机器的VC维，能够使得期望风险在整个总体集上得到控制，即在训练误差和置信范围二者之间寻求一个折衷。这种思想就是结构风险最小化(Structural Risk Minimization，SRM)原则。最小化算法的经验风险与置信范围之和(而不仅仅是最小化经验风险)被称作结构风险最小化原则。 实现SRM原则可以有两种思路：1、 对函数集S的每个子集Si求最小经验风险,然后选择使最小经验风险和置信范围之和最小的子集；2、 设计函数集的某种结构使每个子集中都能取得最小的经验风险，如使训练误差为0,然后只需选择适当的子集使置信范围最小,则这个子集中使经验风险最小的函数就是最优函数。 所谓最优分类线，就是要求分类线不但能将两类正确分开，使训练错误率为0，而且还要使分类间隔最大。前者保证经验风险最小；后者保证推广性界中的置信范围最小，从而使真实的风险最小。推广到高维空间，最优分类线就成了最优分类面。标准的SVM对噪声是不具有鲁棒性的,如何选择合适的目标函数以实现鲁棒性是至关重要的。支持向量机的本质是解一个二次规划问题,虽然有一些经典（如对偶方法、 内点算法等）,但当训练集规模很大时,这些算法面临着维数灾难问题。为此,人们提出了许多针对大规模数据集的SVM训练算法。训练SVM的绝大多数算法都是针对分类问题,只有一小部分算法考虑了回归函数的估计问题。SVM存在两个主要问题：二次规划的训练速度核函数的选择SVM方法的特点（1）SVM的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”。（2）少数支持向量决定了最终结果,这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定了该方法不但算法简单,而且具有较好的“鲁棒”性。这种“鲁棒”性主要体现在:增、删非支持向量样本对模型没有影响;支持向量样本集具有一定的鲁棒性;有些成功的应用中,SVM 方法对核的选取不敏感。由于SVM的求解最后转化成二次规划问题的求解，因此SVM的解是全局唯一的最优解。SVM在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。超平面方程g(x)=0定义了一个判定面，它把归类于C1的点与归类于C2的点分开来。当g(x)是线性函数时，这个平面被称为“超平面”(hyperplane)。当x1和x2都在判定面上时， 这表明w和超平面上任意向量正交，并称w为超平面的法向量。 注意到：x1-x2表示超平面上的一个向量（1）线性判别函数利用一个超平面把特征空间分隔成两个区域。（2）超平面的方向由法向量w确定，它的位置由阈值w0确定。（3）判别函数g(x)正比于x点到超平面的代数距离（带正负号）。当x点在超平面的正侧时，g(x)0；当x点在超平面的负侧时，g(x)0，则判定x属于C1，如果g(x)0，则判定x属于C2，如果g(x)=0，则可以将x任意分到某一类或者拒绝判定。 线性不可分情形（1）线性不可分情形（2）模型（3）的求解，必须知道非线性映射的具体形式，但实际工作上，给出的具体形式是非常困难的！线性不可分情形（3）对偶模型当C=,K(xi,xj)=(xi，xj)时对应线性可分情形；当0C,K(xi,xj)=(xi，xj)时对应近似线性可分情形。原问题的解与对偶问题的解之间的关系：分类决策