第五章神经网络的规划学习方法优秀PPT.ppt

第五章神经网络的规划学第五章神经网络的规划学习方法习方法第一页，本课件共有57页主要内容主要内容u支持向量机支持向量机u支持向量机的分类学习算法支持向量机的分类学习算法 u用于函数拟合的支持向量机用于函数拟合的支持向量机 u支持向量机算法的研究与支持向量机算法的研究与应应用用u仿真仿真实实例例第二页，本课件共有57页u传统统计学是一种渐进理论渐进理论，研究的是样本数目趋于无穷大时的极限特性。u现有的学习方法多基于传统统计学理论传统统计学理论，但在实际应用中，样本往往是有限的，因此一些理论上很优秀的学习方法在实际中的表现却不尽人意，存在着一些难以克服的问题，比如说如何确定网络结构的问题、过学习问题、局部极小值问题等，从本质本质上来说就是因为理论上需要无穷样本与实际中样本有限的矛盾造成的。第三页，本课件共有57页u与传统统计学的方向不同，VapnikVapnik等人提出了一个较完善的基于有限样本的理论体系统计学习理论统计学习理论。u统计学习理论是又一种通用的前馈神经网络，同样可用于解决模式分类和非线性映射问题。u支持向量机方法是在统计学习理论基础上发展起来的通用学习方法，它具有全局优化、适应性强、理论完备、泛化性能好等优点。第四页，本课件共有57页支持向量机支持向量机（Support Vector Machine，SVM）u90年代中期，在统计学习理论的基础上发展出了一种通用的学习方法支持向量机。它根据有限的样本信息在模型的复杂它根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷，以获得性和学习能力之间寻求最佳折衷，以获得最好的泛化能力最好的泛化能力。u支持向量机在很多机器学习问题的应用中已初步表现出很多优于已有方法的性能。第五页，本课件共有57页u支持向量机的理论最初来自于对数据分类问题的处理。对于线性可分数据的二值分类，如果采用多层前向网络来实现，其机理可以简单描述为：系统随机的产生一个超平面并移动它，直到训练集合中属于不同类别的点正好位于该超平面的不同侧面，就完成了对网络的设计要求。但是这种机理决定了不能保证最终所获得的分割平面位于两个类别的中心，这对于分类问题的容错性容错性是不利的。第六页，本课件共有57页u保证最终所获得的分割平面位于两个类别的中心对于分类问题的实际应用是很重要的。支持向量机方法很巧妙地解决了这一问题。u该方法的机理可以简单描述为：寻找一个满足分类要求的最优分类超平面，使得该超平面在保证分类精度保证分类精度的同时，能够使使超平面两侧的空白区域最大化超平面两侧的空白区域最大化；从理论上来说，支持向量机能够实现对线性可分数据的最优分类。为了进一步解决非线性问题，Vapnik等人通过引入核映射核映射方法转化为高维空间的线性可分问题来解决。第七页，本课件共有57页最优分类超平面最优分类超平面（Optimal Hyperplane）u对于两类线性可分两类线性可分的情形，可以直接构造最优超平面，使得样本集中的所有样本满足如下条件：（1）能被某一超平面正确划分；（2）距该超平面最近的异类异类向量与超平面之间的距离最大，即分类间隔（margin）最大。第八页，本课件共有57页u设训练样本输入为 ，对应的期望输出为 u如果训练集中的所有向量均能被某超平面正确划分，并且距离平面最近的异类异类向量之间的距离最大（即边缘margin最大化），则该超平面为最优超平面（Optimal Hyperplane）。第九页，本课件共有57页最优分类面示意图最优分类面示意图 支持向量Support Vector第十页，本课件共有57页u其中距离超平面最近的异类向量被称为支持向量（Support Vector），一组支持向量可以唯一确定一个超平面。SVM是从线性可分情况下的最优分类面发展而来，其超平面记为：u为使分类面对所有样本正确分类并且具备分类间隔，就要求它满足如下约束：第十一页，本课件共有57页u可以计算出分类间隔为 ，因此构造最优超平面的问题就转化为在约束式下求：u为了解决这个约束最优化问题，引入下式所示的Lagrange函数：其中 为Lagrange乘数。约束最优化问题的解由Lagrange函数的鞍点决定。第十二页，本课件共有57页u利用Lagrange优化方法可以将上述二次规划问题转化为其对偶问题对偶问题，即在约束条件：下对 求解下列函数的最大值：如果 为最优解，那么：第十三页，本课件共有57页u以上是在不等式约束下求二次函数极值问题，是一个二次规划问题（Quadratic Programming，QP），），存在唯一解。根据最优性条件Karush-Khn-Tucker条件（KKT条件），这个优化问题的解必须满足：u对多数样本对多数样本 将为零，取值不为零的将为零，取值不为零的 所所对应的样本即为支持向量，它们通常只是对应的样本即为支持向量，它们通常只是全体样本中很少的一部分。全体样本中很少的一部分。第十四页，本课件共有57页u求解上述问题后得到的最优分类函数是：u在通过训练得到最优超平面后,对于给定的未知样本x，只需计算f(x)即可判断x所属的分类。第十五页，本课件共有57页u若训练样本集是线性不可分的，或事先不知道它是否线性可分，将允许存在一些误分类的点，此时引入一个非负松弛变量非负松弛变量 ，约束条件变为:u目标函数改为在以上约束条件下求：u 即折衷考虑最小错分样本和最大分类间隔。其中，C0 为惩罚因子，控制对错分样本的惩罚程度。第十六页，本课件共有57页u线性不可分情况和线性可分情况的差差别别就在于可分模式中的约束条件中的 在不可分模式中换为了更严格的条件 。除了这一修正，线性不可分情况的约束最优化问题中权值和阈值的最优值的计算都和线性可分情况中的过程是相同的。第十七页，本课件共有57页支持向量机支持向量机（Support Vector Machine,SVM）u在现实世界中，很多分类问题都是线性不可分的，即在原来的样本空间中无法找到一个最优的线性分类函数，这就使得支持向量机的应用具有很大的局限性。但是可以设法通过非线性变换将原样本空间通过非线性变换将原样本空间的非线性问题转化为另一个空间中的线性问题的非线性问题转化为另一个空间中的线性问题。SVM就是基于这一思想的。首先将输入向量通过非线性映射变换到一个高维的特征向量空间，在该特征空间中构造最优分类超平面。第十八页，本课件共有57页u由于在上面的二次规划（QP）问题中，无论是目标函数还是分类函数都只涉及内积运算，如果采用核函数(Kernel Function)就可以避免在高维空间进行复杂运算，而通过原空间的函数来实现内积运算。因此，选择合适的内积核函数核函数 就可以实现某一非线性变换后的线性分类，而计算复杂度却没有增加多少，从而巧妙地解决了高维空间中计算带来的“维数灾难”问题。第十九页，本课件共有57页u此时，相应的决策函数化为：u支持向量机求得的决策函数形式上类似于一个神经网络，其输出是若干中间层节点的线性组合，而每一个中间层节点对应于输入样本与一个支持向量的内积，因此也被称作是支持向量网络。第二十页，本课件共有57页支持向量机示意图支持向量机示意图 第二十一页，本课件共有57页 选择不同的核函数 可以生成不同的支持向量机，常有以下几种：（1）线性核函数：（2）多项式核函数：（3）Gauss核函数：（4）Sigmoid核函数：第二十二页，本课件共有57页一个具体核函数的例子一个具体核函数的例子 假设数据是位于 中的向量，选择：然后寻找满足下述条件的空间H：使映射 从 映射到H且满足：可以选择H=R3以及：第二十三页，本课件共有57页用图来表示该变换：用图来表示该变换：SVM用于二维样本分类用于二维样本分类第二十四页，本课件共有57页支持向量机与多层前向网络支持向量机与多层前向网络的比较的比较 u与径向基函数网络和多层感知器相比，支持向量机避免了在前者的设计中经常使用的启发式结构，它不依赖于设计者的经验知识；而且支持向量机的理论基础决定了它最终求得的是全局最优值而不是局部极小值，也保证了它对于未知样本的良好泛化能力而不会出现过学习现象。第二十五页，本课件共有57页支持向量机的分类学习支持向量机的分类学习算法算法 对于分类问题，用支持向量机方法进行求解的学习算法过程为：第一步第一步 给定一组输入样本 ，及其对应的期望输出 ；第二步第二步 选择合适的核函数 及相关参数；第三步第三步 在约束条件 和 下求解 得到最优权值 ；第二十六页，本课件共有57页第四步 计算：；第五步 对于待分类向量x ，计算：为1或1，决定x属于哪一类。第二十七页，本课件共有57页用于函数拟合的支持向量机用于函数拟合的支持向量机 u假定数据集 。首先考虑用线性回归函数线性回归函数 拟合数据集X的问题。u所有训练数据在精度 下无误差地用线性函数拟合，即：u考虑到允许拟合误差存在的情况：第二十八页，本课件共有57页u优化目标函数为：u对偶问题为：在约束条件 下求下式的最大值。u回归函数为：第二十九页，本课件共有57页用不同的支持向量机对人工数据进用不同的支持向量机对人工数据进行分类行分类（a）线性可分对下面二维待分类人工数据P进行分类：X=2 7;3 6;2 2;8 1;6 4;4 8;9 5;9 9;9 4;6 9;7 4;Y=+1;+1;+1;+1;+1;-1;-1;-1;-1;-1;-1;第三十页，本课件共有57页（b）线性不可分对下面二维待分类人工数据P进行分类：X=2 7;3 6;2 2;8 1;6 4;4 8;9 5;9 9;9 4;6 9;7 4;4 4;Y=+1;+1;+1;+1;+1;-1;-1;-1;-1;-1;-1;-1;第三十一页，本课件共有57页（1）、实验环境）、实验环境 Matlab 7.0（2）、界面设计）、界面设计第三十二页，本课件共有57页（3 3）、具体实现）、具体实现a)a)对于线性可分的人工样本数据对于线性可分的人工样本数据P P。其中共有。其中共有1111个待分类样本。个待分类样本。使用最简单的支持向量机，即以线性核函数K(x,xi i)=(x.xi i)作为内积函数的支持向量机来训练该数据集合。惩罚因子C取10。第三十三页，本课件共有57页黑色线为数据集合的两类分类线，可以看出它能将两类准确无误的分开，错误率为0。蓝线和绿线为两类样本的最大间隔边界。5,11,6三点为支持向量。样本点样本点分类结果分类结果第三十四页，本课件共有57页b)b)对于线性不可分的人工样本数据对于线性不可分的人工样本数据P P。其中共有。其中共有1212个待分类样本。个待分类样本。c)c)1 1）用线性核函数）用线性核函数SVMSVM进行训练。进行训练。仍采用最简单的支持向量机，即以线性核函数K(x,xi i)=(x.xi i)作为内积函数的支持向量机来训练该数据集合。惩罚因子C取10。第三十五页，本课件共有57页显然黑色线为数据集合的两类分类线，不能将两类准确无误的分开，点12是错分的样本点，而5和点11落在了分类间隔内。此时正确率为91.67%。样本点样本点分类结果分类结果第三十六页，本课件共有57页2 2）利用较为复杂的）利用较为复杂的RBFRBF核函数支持向量机进行分类。核函数支持向量机进行分类。RBF核函数中的核宽度这个参数是由用户决定的。因此下面采用三个不同的RBF核宽度来对该函数集合进行分类。惩罚因子C取100。选择RBF核宽度为8,其结果如图所示。第三十七页，本课件共有57页从图中可以看出，此时SVM以点12作为类别1的一个聚类中心，在其周围形成了一个类似“小岛”的区域。并且，点2，3，4，5，6,11和12是支持向量，错分样本数为0。第三十八页，本课件共有57页使用一个较小的值1作为RBF核宽度,其结果如图所示。第三十九页，本课件共有57页黑线为分类边界，蓝线和绿线为两类的最大间隔边界。由于较小的核宽度允许了分类边界的分割，因此图中的分类边界有很多条。由此造成了每个样本点都是支持向量，所以错分样本数为0。第四十页，本课件共有57页使用一个较大的值36作为RBF核宽度,其结果如图所示。第四十一页，本课件共有57页黑线为分类边界，蓝线和绿线为两类的最大间隔边界。使用较大的核宽度时分类边界比较简化，但是出现了错分样本，即点5和12，此时的分类正确率为83.33%。第四十二页，本课件共有57页实验小结:从实验可以看出，针对同一问题，也即同一组数据来说，用不同核函数的支持向量机的分类结果是不同的。而且可以看到针对不同的问题，对同一种核函数支持向量机来说，选择合适的参数也是很关键的，不同的参数的选择就对应着不同的分类结果。第四十三页，本课件共有57页支持向量机算法的研究与应用支持向量机算法的研究与应用u 支持向量机算法改进支持向量机算法改进u 核函数的改进核函数的改进u 错误惩罚参数的选择错误惩罚参数的选择u 不敏感参数不敏感参数 的选择的选择u 支持向量机解决多类划分问题支持向量机解决多类划分问题u 支持向量机的应用支持向量机的应用第四十四页，本课件共有57页支持向量机算法改进支持向量机算法改进 传统的利用标准二次型优化技术解决对偶问题的方法是训练算法慢的主要原因。(1)SVM方法需要计算和存储核函数矩阵，当样本点数目较大时，需要很大的内存，例如，当样本点数目超过4000时，存储核函数矩阵需要多达128MB内存；(2)SVM在二次型寻优过程中要进行大量的矩阵运算，多数情况下，寻优算法是占用算法时间的主要部分。第四十五页，本课件共有57页u近年来人们针对方法本身的特点提出了许多算法来解决对偶寻优问题。这些算法的一个共同的思想就是采用分而治之分而治之的原则将原始QP问题分解为规模较小的子问题，通过循环解决一系列子问题来求得原问题的解。u现有的训练算法分为三类：“块算法”（chunking algorithm）“Osuna 分解算法”“SMO算法”第四十六页，本课件共有57页核函数的改进核函数的改进u核函数的形式及其参数决定了分类器的类型和复杂程度。在不同的问题领域，核函数应当具有不同的形式和参数，应将领域知识引入进来，从数据依赖的角度选择核函数。u初步尝试的方法有：Amari利用黎曼几何结构方法来修改核函数；Barzilay通过改进邻近核来改进核函数；Brailovsky局部核函数方法；G.F.Smits 多个核函数组合起来使用；第四十七页，本课件共有57页错误惩罚参数的选择错误惩罚参数的选择 错分样本惩罚参数C实现在错分样本的比例和算法复杂度之间的折衷。C值的确定一般是用户根据经验给定的，随意性很大，也很难知道所取C值的好坏性。如何消除C值选取的随意性，而采用某种方法自动地选择一个最佳的C值，这个问题目前尚未解决。第四十八页，本课件共有57页不敏感参数不敏感参数 的选择的选择uSVM通过参数 控制回归估计的精度，但 取多少才能达到所期望的估计精度是不明确的，为此出现了许多新的SVM方法。u Schlkoph和Smola -SVM方法方法 u Lin C-F 加权支持向量机，通过对每个样本数据点采用不同的 ，来获得更准确的回归估计。第四十九页，本课件共有57页支持向量机解决支持向量机解决多类多类划分问划分问题题“多类支持向量机”（Multi-category Support Vector Machines，M-SVMs）。它们可以大致分为两大类：（1）通过某种方式构造一系列的两类分类器并将它们组合在一起来实现多类分类；（2）直接在目标函数上进行改进，建立K分类支持向量机。第五十页，本课件共有57页一对多方法一对多方法(l-against-rest，1-a-r)此算法是对于K类问题构造K个两类分类器。第i个SVM用第i类中的训练样本作为正的训练样本，而将其它的样本作为负的训练样本，即每个SVM分别将某一类的数据从其他类别中分离出来。测试时将未知样本划分到具有最大分类函数值的那类。缺点：泛化能力较差，且训练样本数目大，训练困难。此外，该方法还有可能存在测试样本同时属于多类或不属于任何一类的情况。第五十一页，本课件共有57页一对一方法一对一方法(l-against-1，1-a-1)u该算法在K类训练样本中构造所有可能的两类分类器，每类仅仅在K类中的两类训练样本之间训练，结果共构造K(K-1)/2个分类器。组合这些两类分类器很自然地用到了投票法，得票最多（Max Wins）的类为新点所属的类。u缺点：推广误差无界，分类器的数目K(K-1)/2随类数K的增加急剧增加，导致在决策时速度很慢。此外，还可能存在一个样本同时属于多个类的情况。第五十二页，本课件共有57页决策导向非循环图决策导向非循环图SVM方法方法 （Decision Directed Acyclic Graph，DDAG）u在训练阶段，其与1-a-1方法相同，对于K类问题，DDAG含有K(K-1)/2个两类分类器。然而在决策阶段，使用从根节点开始的导向非循环图（DAG），具有K(K-1)/2个内部节点以及K个叶子节点，每个内部节点都是一个两类分类器，叶子节点为最终的类值。u缺点：根节点的选择直接影响着分类的结果，不同的分类器作为根节点，其分类结果可能会不同，从而产生分类结果的不确定性。第五十三页，本课件共有57页基于二叉树的多类基于二叉树的多类SVM分类方法分类方法 对于K类的训练样本，训练K-1个支持向量机。第1个支持向量机以第1类样本为正的训练样本，将第2，3，K类训练样本作为负的训练样本训练SVM1，第i个支持向量机以第i类样本为正的训练样本，将第i+l，i+2，K类训练样本作为负的训练样本训练SVMi，直到第K-1个支持向量机将以第K-1类样本作为正样本，以第K类样本为负样本训练SVM（K-1）。第五十四页，本课件共有57页u优点：所需要训练的两类支持向量机的数量少；消除了决策时存在同时属于多类或不属于任何一类的情况；总共需要训练的样本和前两种方法相比减少了许多。u缺点：若在某个节点上发生分类错误，将会把错误延续下去，该节点后续下一级节点上的分类就失去意义。第五十五页，本课件共有57页最小最大模块化支持向量机最小最大模块化支持向量机（Min-Max-Modular-SVM,M3-SVM）u该方法充分利用分布式并行计算系统，将一个K类问题分解成K(K-1)/2个二类问题，然后把一个二类问题分解成一系列指定规模的小的二类子问题。u优点：这些二类子问题的特点是在训练过程中完全相互独立，因此可以容易地在集群计算机和网格上实现超并行学习。在保证推广能力的前提下，能够明显提高训练速度，是一种解决大规模模式分类问题的有效方法。第五十六页，本课件共有57页支持向量机的应用支持向量机的应用 随着对SVM研究的进展和深入，其应用也越来越广泛，基于SVM思想的一些模型和方法被广泛应用于各个领域，包括模式识别，如人脸识别、字符识别、笔迹鉴别、文本分类、语音鉴别、图像识别、图像分类、图像检索等等；回归估计，如非线性系统估计、预测预报、建模与控制等等；以及网络入侵检测、邮件分类、数据挖掘和知识发现、信号处理、金融预测、生物信息等新领域。第五十七页，本课件共有57页