结构风险最小化_软间隔svm分类是如何实现结构风险最小化的?

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/Yaroo/article/details/53979115

理论背景
    基于数据的机器学习是现代智能技术中的重要方面，研究从观测数据（样本）出发寻找规律，利用这些规律对未来数据或无法观测的数据进行预测。迄今为止，关于机器学习还没有一种被共同接受的理论框架，关于其实现方法大致可以分为三种：
    （1）第一种是经典的（参数）统计估计方法。包括模式识别、神经网络等在内，现有机器学习方法共同的重要理论基础之一是统计学。参数方法正是基于传统统计学的，在这种方法中，参数的相关形式是已知的，训练样本用来估计参数的值。这种方法有很大的局限性，首先，它需要已知样本分布形式，这需要花费很大代价，还有，传统统计学研究的是样本数目趋于无穷大时的渐近理论，现有学习方法也多是基于此假设。但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法实际中表现却可能不尽人意。
    （2）第二种方法是经验非线性方法，如人工神经网络（ANN）。这种方法利用已知样本建立非线性模型，克服了传统参数估计方法的困难。但是，这种方法缺乏一种统一的数学理论。
    与传统统计学相比，统计学习理论（Statistical Learning Theory或SLT）是一种专门研究小样本情况下机器学习规律的理论。该理论针对小样本统计问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在现有有限信息的条件下得到最优结果。V. Vapnik等人从六、七十年代开始致力于此方面研究[1]，到九十年代中期，随着其理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的重视。
VC维

    统计学习理论的一个核心概念就是VC维(VC Dimension)概念，它是描述函数集或学习机器的复杂性或者说是学习能力(Capacity of the machine)的一个重要指标，在此概念基础上发展出了一系列关于统计学习的一致性(Consistency)、收敛速度、推广性能(Generalization Performance)等的重要结论。

    支持向量机

    统计学习理论是建立在一套较坚实的理论基础之上的，为解决有限样本学习问题提供了一个统一的框架。它能将很多现有方法纳入其中，有望帮助解决许多原来难以解决的问题（比如神经网络结构选择问题、局部极小点问题等）；同时，这一理论基础上发展了一种新的通用学习方法──支持向量机（Support Vector Machine或SVM），已初步表现出很多优于已有方法的性能。一些学者认为，SLT和SVM正在成为继神经网络研究之后新的研究热点，并将推动机器学习理论和技术有重大的发展。
    支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度，Accuracy)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷，以期获得最好的推广能力(Generalizatin Ability)。支持向量机方法的几个主要优点有：
    1>它是专门针对有限样本情况的，其目标是得到现有信息下的最优解而不仅仅是样本数趋于无穷大时的最优值；
    2>算法最终将转化成为一个二次型寻优问题，从理论上说，得到的将是全局最优点，解决了在神经网络方法中无法避免的局部极值问题；
    3>算法将实际问题通过非线性变换转换到高维的特征空间(Feature Space)，在高维空间中构造线性判别函数来实现原空间中的非线性判别函数，特殊性质能保证机器有较好的推广能力，同时它巧妙地解决了维数问题，其算法复杂度与样本维数无关；
在SVM方法中，只要定义不同的内积函数，就可以实现多项式逼近、贝叶斯分类器、径向基函数(Radial Basic Function或RBF)方法、多层感知器网络等许多现有学习算法。
    统计学习理论从七十年代末诞生，到九十年代之前都处在初级研究和理论准备阶段，近几年才逐渐得到重视，其本身也趋向完善，并产生了支持向量机这一将这种理论付诸实现的有效的机器学习方法。目前，SVM算法在模式识别、回归估计、概率密度函数估计等方面都有应用。例如，在模式识别方面，对于手写数字识别、语音识别、人脸图像识别、文章分类等问题，SVM算法在精度上已经超过传统的学习算法或与之不相上下。
     VC 维在有限的训练样本情况下，当样本数 n 固定时，此时学习机器的 VC 维越高学习机器的复杂性越高。VC 维反映了函数集的学习能力，VC 维越大则学习机器越复杂(容量越大)。   
    所谓的结构风险最小化就是在保证分类精度（经验风险）的同时，降低学习机器的 VC 维，可以使学习机器在整个样本集上的期望风险得到控制。  
    推广的界（经验风险和实际风险之间的关系，注意引入这个原因是什么？因为训练误差再小也就是在这个训练集合上，实际的推广能力不行就会引起过拟合问题还。所以说要引入置信范围也就是经验误差和实际期望误差之间的关系）：
    期望误差R(ω) ≤ Remp (ω)+ Φ（h/n）注意Remp (ω)是经验误差也就是训练误差（线性中使得所有的都训练正确），Φ（h/n）是置信范围，它是和样本数和VC维有关的。上式中置信范围Φ 随n/h增加，单调下降。即当n/h较小时，置信范围Φ 较大，用经验风险近似实际风险就存在较大的误差，因此，用采用经验风险最小化准则，取得的最优解可能具有较差的推广性；如果样本数较多，n/h较大，则置信范围就会很小，采用经验风险最小化准则，求得的最优解就接近实际的最优解。可知：影响期望风险上界的因子有两个方面：首先是训练集的规模 n，其次是 VC 维 h。可见，在保证分类精度（经验风险）的同时，降低学习机器的 VC 维，可以使学习机器在整个样本集上的期望风险得到控制，这就是结构风险最小化（Structure Risk Minimization，简称 SRM）的由来。
     在有限的训练样本情况下，当样本数 n 固定时，此时学习机器的 VC 维越高(学习机器的复杂性越高)，则置信范围就越大，此时，真实风险与经验风险之间的差别就越大，这就是为什么会出现过学习现象的原因。机器学习过程不但要使经验风险最小，还要使其 VC 维尽量小，以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性，它与学习机器的 VC 维及训练样本数有关。  
    线性可分的问题就是满足最优分类面的面要求分类面不但能将两类样本正确分开（训练错误率为 0），而且要使两类的分类间隔最大。

    VC维在有限的训练样本情况下，当样本数 n 固定时，此时学习机器的 VC 维越高学习机器的复杂性越高。VC 维反映了函数集的学习能力，VC 维越大则学习机器越复杂(容量越大)。

    所谓的结构风险最小化就是在保证分类精度（经验风险）的同时，降低学习机器的 VC 维，可以使学习机器在整个样本集上的期望风险得到控制。

    推广的界（经验风险和实际风险之间的关系，注意引入这个原因是什么？因为训练误差再小也就是在这个训练集合上，实际的推广能力不行就会引起过拟合问题还。所以说要引入置信范围也就是经验误差和实际期望误差之间的关系）：期望误差R(ω) ≤ Remp (ω)+ Φ（n/h）注意Remp (ω)是经验误差也就是训练误差（线性中使得所有的都训练正确），Φ（n/h）是置信范围，它是和样本数和VC维有关的。上式中置信范围Φ 随n/h增加，单调下降。即当n/h较小时，置信范围Φ 较大，用经验风险近似实际风险就存在较大的误差，因此，用采用经验风险最小化准则，取得的最优解可能具有较差的推广性；如果样本数较多，n/h较大，则置信范围就会很小，采用经验风险最小化准则，求得的最优解就接近实际的最优解。可知：影响期望风险上界的因子有两个方面：首先是训练集的规模 n，其次是 VC 维 h。可见，在保证分类精度（经验风险）的同时，降低学习机器的 VC 维，可以使学习机器在整个样本集上的期望风险得到控制，这就是结构风险最小化（Structure Risk Minimization，简称 SRM）的由来。在有限的训练样本情况下，当样本数 n 固定时，此时学习机器的 VC 维越高(学习机器的复杂性越高)，则置信范围就越大，此时，真实风险与经验风险之间的差别就越大，这就是为什么会出现过学习现象的原因。机器学习过程不但要使经验风险最小，还要使其 VC 维尽量小，以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性，它与学习机器的 VC 维及训练样本数有关。

    线性可分的问题就是满足最优分类面的面要求分类面不但能将两类样本正确分开（训练错误率为 0），而且要使两类的分类间隔最大（这个是怎么回事呢？原来是有根据的，这个让俺郁闷了好久呢。在 @ 间隔下，超平面集合的 VC 维 h 满足下面关系：

         h = f （1/@*@）

    其中， f().是单调增函数，即 h 与@的平方成反比关系。因此，当训练样本给定时，分类间隔越大，则对应的分类超平面集合的 VC 维就越小。）。根据结构风险最小化原则，前者是保证经验风险（经验风险和期望风险依赖于学习机器函数族的选择）最小，而后者使分类间隔最大，导致 VC 维最小，实际上就是使推广性的界中的置信范围最小，从而达到使真实风险最小。注意：置信范围大说明真实风险和经验风险的差别较大。

    解释到这里了，终于有点眉目了，哦原来就是这么回事啊，真是的。总结一下就是训练样本在线性可分的情况下，全部样本能被正确地分类（咦这个不就是传说中的yi*(w*xi+b)）>=1的条件吗），即经验风险Remp 为 0 的前提下，通过对分类间隔最大化（咦，这个就是Φ（w）＝(1/2)*w*w嘛），使分类器获得最好的推广性能。

    那么解释完线性可分了，我们知道其实很多时候是线性不可分的啊，那么有什么区别没有啊？废话区别当然会有啦，嘿嘿那么什么是本质的区别啊？本质的区别就是不知道是否线性可分但是允许有错分的样本存在（这个咋回事还是没明白hoho）但是正是由于允许存在错分样本，此时的软间隔分类超平面表示在剔除那些错分样本后最大分类间隔的超平面。这里就出现了新词松驰因子，干吗用滴？就是用来控制错分样本的啊。这样的话经验风险就要跟松驰因子联系在一起了。而C就是松驰因子前面的系数，C>0 是一个自定义的惩罚因子，它控制对错分样本惩罚的程度，用来控制样本偏差与机器推广能力之间的折衷。c越小，惩罚越小，那么训练误差就越大，使得结构风险也变大，而C 越大呢，惩罚就越大，对错分样本的约束程度就越大，但是这样会使得第二项置信范围的权重变大那么分类间隔的权重就相对变小了，系统的泛化能力就变差了。所以选择合适的C还是很有必要的。

选择核函数。

    核函数有很多种，如线性核、多项式核、Sigmoid 核和 RBF（Radial Basis function）核。本文选定 RBF 核为 SVM 的核函数（RBF 核K(x, y) = exp(－γ || x －y ||的平方),γ > 0）。因为RBF 核可以将样本映射到一个更高维的空间，可以处理当类标签（Class Labels）和特征之间的关系是非线性时的样例。Keerthi 等[25]证明了一个有惩罚参数C 的线性核同有参数(C,γ )（其中C 为惩罚因子，γ 为核参数）的 RBF 核具有相同的性能。对某些参数，Sigmoid核同 RBF 核具有相似的性能。另外，RBF 核与多项式核相比具有参数少的优点。因为参数的个数直接影响到模型选择的复杂性。非常重要的一点是0< Kij ≤1与多项式核相反，核值可能趋向无限(γxi xj + r >1)或者0 < γxi xj + r <1，跨度非常大。而且，必须注意的是Sigmoid 核在某些参数下是不正确的（例如，没有两个向量的内积）。

    用交叉验证找到最好的参数 C 和γ 。使用 RBF 核时，要考虑两个参数 C 和γ 。因为参数的选择并没有一定的先验知识，必须做某种类型的模型选择（参数搜索）。目的是确定好的(C,γ)使得分类器能正确的预测未知数据（即测试集数据），有较高的分类精确率。值得注意的是得到高的训练正确率即是分类器预测类标签已知的训练数据的正确率）不能保证在测试集上具有高的预测精度。因此，通常采用交叉验证方法提高预测精度。k 折交叉验证（k-fold cross validation）

是将训练集合分成 k 个大小相同的子集。其中一个子集用于测试，其它 k-1 个子集用于对分类器进行训练。这样，整个训练集中的每一个子集被预测一次，交叉验证的正确率是 k次正确分类数据百分比的平均值。它可以防止过拟合的问题。

统计学习

    什么是统计学习？看起来高深莫测，其实就是在这干这么一件事情：就是给你看一堆东西，你想办法给一个解释，然后拿着这个解释去判断其它的东西。不过，和物理学不一样，在那里，解释是人想出来的，在统计学习里，解释是机器构造出来的。

    在许多问题里面，对象是非常复杂的，要用成百上千，甚至更多的数字去表示一个东西。当统计学家们遇到了这些问题，他们终于从对在一维和二维空间建立起来的基于概率密度的完美的数学体系的沉迷中惊醒了——经典的统计体系在“维数灾难”的洪水猛兽面前竟然不堪一击。统计学的定理告诉我们，当样本足够多的时候，估计可以足够准确，可是对于高维空间，无情的现实用两个理由断然拒绝了统计学家们的渴求——不可能有那么多的样本，也不可能在这么多的样本上面进行计算。

    有限的样本意味着什么呢？很多本来能很好地建模的问题变成不适定的了(ill-posed)。通俗地说，就是给你的这么些样本，你可以用这个模型解释，也可以用那个模型解释，大家都解释得非常完美。那么究竟哪个是真的解释呢？令人沮丧的是，无论是这些样本还是那些美妙的统计学理论都无法给出答案——我们只能被告知，这些模型是不可被识别出谁对谁错的(unidentifiable)——在哲学上，有个深奥的名词，叫做不可证伪性。

    噢，既然都很完美，那么我们都接受好了。可是，别忘了，我们的目标不是守着这些解释度过余生，而是用它们帮我们干后面的事情——要是一个东西干不好事情的，就算再完美，还是呆在一边凉快去吧。想象一个也许很多大学生，乃至中学生都会的例子——曲线拟合。我们看到100个点，在一个抛物线附近震荡。我们首先拿一根直线去拟，怎么都不好；于是我们用二次曲线，嗯，看起来不错，好多了。于是我们开始兴奋起来——看起来，增加曲线的次数是个好主意。次数在一点点的加，到了100的时候，大家欢呼起来——太完美了，没有一点误差！于是大家拿着这个100次曲线模型信心十足地去套别的点，傻眼了，错的一塌糊涂！那个差强人意的二次曲线反而在这里工作的不错。

    这个深刻的教训告诉我们：一个在已有数据中很完美的模型，在新的数据面前不一定最好的。Perfect很可能只是由于over-fitting产生的illusion。后来统计学家研究了这个问题，告诫我们除了有追求perfect的热情，还要锻造一把Occam的剃刀：除了让模型在已知的例子中很好的工作，还要把模型“剃”得简单一点——简单的美才是真的美。

    在这个原理的基础上，统计数学家Vapnik通过严密的数学推理建立了结构风险最小化（Structure Risk Minimization）的理论，把模型复杂性融入到优化目标当中，以取代单纯追求在已知数据上的令人陶醉的完美的经验风险最小化（Empirical Risk Minimization），并且提出了现在风靡全球的支持向量机 （Support Vector Machines）。

    其实，统计学家在这个事情上是落后了，从古希腊的哲学家和数学家，到近代的物理学家，所孜孜以求的不就是对这个世界的一个简单而完美的解释吗？对于许多伟大的科学家来说，支持其科学探索的并不是建立一套复杂得令人望而生畏的体系来描述我们的世界，相反，他们穷毕生精力所探索的正是存在于宇宙中的简单和和谐。回到刚才那个两个模型的抉择问题，简单性的信念支持着我们做这样的决定：选简单的那个。

    反思我们过去的处事方式，确实感到惭愧：在干很多事情的时候，总是试图通过建立复杂的东西来获得成就感，并且向别人炫耀自己的多才多艺的实力——文章越长越好，程序越复杂越好，公式越深奥越好。可是，回想起来，这些当时在班级和同伴里轰动一时的东西——上百页的实验报告，上万行的程序，以及长篇小说一样的文章，最后给自己留下了什么。很多时候我们在创造复杂的东西，往往代表着我们还缺乏足够的能力去找出深藏于complexity和diversity背后的core simplicity——这才是在历史长河中亘古不衰的。

    现代的社会是复杂的和多姿多彩的，但这是“简单”在变化中孕育的，在这个复杂的世界中游刃有余的最好方法就是把握根本的简单性。这就是简单和复杂的矛盾。
--------------------- 
作者：Yaroo 
来源：CSDN 
原文：https://blog.csdn.net/yaroo/article/details/53979115 
版权声明：本文为博主原创文章，转载请附上博文链接！