svm一种具有可学习性的学习模型

svm一种具有可学习性的学习模型

1支持向量机理论svm统计理论始于1960年末。在接下来的20年里，参与这一领域的人数很少。这期间，前苏联人Vapnik&Chervonenkis做了大量开创性、奠基性的工作。这些工作主要是纯理论性的，故当时未引起人们的重视。进入90年代，该理论被用来分析神经网络，90年代中期，基于该理论设计的支持向量机（SupportVectorMachine，简称SVM）在解决一系列实际问题中获得成功，表现出优良的学习能力尤其是泛化能力，从而引起人们对这一领域的极大关注。目前，有关这一理论及其应用的研究正在快速发展。不夸张地说，就象信息论为信息技术的崛起开辟道路一样，统计学习理论将带来机器学习领域一场深刻变革。2统计学习理论2.1及时掌握最优设计条件设X是系统的输入空间，Y是输出空间，统计学习模型包括三要素，p(x）：输入空间X上的概率测度。p(y|x）：输出空间Y上的条件概率测度。学习机：，∧是非空指标集，f:X→Y。这样乘积空间X×Y上有概率测度p(x,y)=p(x)p(y|x）。今试图用函数f(x，α）来拟合输入x和输出y之间的关系，这种拟合是有风险（或损失）的，设风险为L(y,f(x，α）），则平均风险为。学习的目标：寻找α0∈∧，使得R（α0)=min，前提条件是p(x,y）未知，仅仅知道样本（xi,yi),i=1,2，…，l。这个模型具有一般性，包括了一些常见的学习问题，例如模式识别：密度估计：L=-lnp(x,y，α），p(x,y，α）是密度。2.2．p到pz实质上，也为了今后讨论方便，学习问题可简练地写成寻找α0∈∧，使得R（α0)=min，前提条件是概率分布p(z）未知，仅仅知道样本zi,i=1,2，…，l。2.3估计：正确理解概率收敛经验风险最小化原理：为了求（2）中的α0，定义经验风险，把它的最小点αl作为α0的估计，即。实际上，经验风险最小化原理并不陌生，最小均方误差和极大似然估计方法都是它的具体运用。现在的问题是：如此得到的确αl符合要求吗？即下式成立吗？表示依概率收敛。定义1若（）式成立，称机器关于p具有可学习性。2.4重要的定义以下是模式识别的例子定理1（）成立的充要条件是这个定理不但是机器可学习的充分条件而且是必要条件，故称关键定理。2.5．p或p无关记。称为VC-熵（E表示求数学期望），为生长函数。结论(1)与p有关，因此它给出了对某个特定问题（或环境）机器可学习的充要条件；(2)与p无关，它给出了对任意问题（或环境）机器可学习的充要条件。这两个结果是统计学习理论中有里程碑意义的重要成果。2.6．机器的vc-维数先介绍统计学习理论中一个极其重要的概念：VC-维数。定义2设S是X上取邀0,1妖值的函数集合，A奂X。如果任给E奂X，总存在fE∈S满足fE(x)=1,x∈E;fE(x)=0,x∈A\E则称SVC-分开（VC-shatter)A。所有被SVC-分开的集合A所含元素个数的最大值，称为S的VC-维数（如果S能VC-分开元素个数任意大的集合A奂X，则S的VC-维数为∞）。VC-维数是机器复杂度的一个度量。由定理2和3可得结论：对任意p，机器可学习的充要条件是VC-维数有限。90年代初，人们证明了神经网络的VC-维数与它的联结个数和神经元内部的传递函数有关，一般条件下是有限的，但可能是一个很大的数。以上结论都是在样本数l→∞时成立，而实际问题中样本数总是有限的，甚至样本数很小（即小样本情况），为了分析这种情况下的学习质量，需要考虑2.7（觹觹）的收敛速度定理4设VC-维数h有限，则下式以概率1-η成立关于定理4作如下说明：(1）特别地，（）对αl成立。(2）（）右端第一项反映训练样本的拟合程度；第二项与l/h有关，当l给定时随h增大而增大。(3）要使实际风险尽量小，仅仅最小化经验风险是不够的，还必须同时降低机器的VC-维数。(4）利用该结论可以分析神经网络的行为：要使网络对训练集拟合得好，比如说误差为0，就要扩大网络规模，规模扩大导致VC-维数h增大，从而（l给定时）第二项增大。因此即使第一项为0，总的平均风险R（αl）也可能很大，也就是网络的泛化能力差。这就是人们常说的过度拟合（Overfitting）。2.8求取l的二元样结构风险最小化原理：设学习机，给它赋予一个结构使得且Sk的VC-维数有限。对大小为l的样本，先寻找Sk（或∧k）其中k=k(l），然后寻找使得（）右端两项之和最小。这样求出的确实比用经验风险最小化原理得到的αl有更好的性质。定理5。如何设计具体算法实现结构风险最小化原理呢？2.9x+b的确定设训练样本x1，…，xl∈Rd且分别是球心和半径，w·x+b=0是标准超平面（即满足）。今考虑学习机，在S上定义结构如下：定理6Sk的VC-维数min([r2ck2],d)+1([x]表示不超过x的最大整数）。2.9.1结构风险最小原理训练样本线性可分时，可以做到经验风险等于0，但为了保证在测试集上有小的错误率，按照结构风险最小化原理应该选择这样的Sk：它含有把训练样本正确无误分开的标准超平面，同时它的VC-维数要最小。根据定理6，后者可通过令（w·w）最小来保证，于是问题化为这样就解得最优分离超平面。2.9.2常用的正数惩罚系数要使（觹觹觹）式右端两项之和最小，可通过下面的优化问题来实现其中C是自定义的正数（惩罚系数），θ（ξ）=0，如果ξ=0；θ（ξ）=1，如果ξ>0。由于该优化问题NP-完全的，故常用θ（ξ）=ξσ（σ0）来近似，为了计算方便又常取σ=1（或2）。这样就得到广义最优超平面。2.9.3训练样本被最优超平面或广义最优超平面分离的期望SVM的主要思想是：用非线性函数把输入变量映射到某个高维特征空间F，然后在F中构造（广义）最优超平面。有关支持向量机的详细描述见。定理7若训练样本被最优超平面（或广义最优超平面）分离，则一个测试样本发生错误的概率的期望E[P(error）]E[支持向量个数]/（训练样本总数-1）。为什么SVM的泛化能力很好？定理7提供了部分答案（也是迄今这方面最好的结果），因为上述不等式与输入空间的维数无关，所以在高维（甚至是无穷维）特征空间中，只要能找到这样的超平面，其支持向量个数相对于训练样本总数很少，那么它的泛化能力就很强。3p有附加信息且p型统计学习理论的重要结论，都是建立在考虑固定问题（环境）或任意问题（环境）基础上的。这是两个极端情形。许多情况下人们对所处理的问题并非一无所知，即有附加信息，可这样来描述：，说对p有附加信息，如果已知P0P且p∈P0。通俗地讲，就是虽然还不能完全确定p但知道了包含p的一个较小的范围P0。在这个基础上，可以类似地讨论可学习性、学习质量的控制等一系列相关问题。这就要求不但要刻画学习机S，还要刻画环境P0（比如