神经网络的规划学习方法

1、u传统统计学是一种渐进理论渐进理论，研究的是 样本数目趋于无穷大时的极限特性。 u现有的学习方法多基于传统统计学理论传统统计学理论， 但在实际应用中，样本往往是有限的， 因此一些理论上很优秀的学习方法在实 际中的表现却不尽人意，存在着一些难 以克服的问题，比如说如何确定网络结 构的问题、过学习问题、局部极小值问 题等，从本质本质上来说就是因为理论上需 要无穷样本与实际中样本有限的矛盾造 成的。 u与传统统计学的方向不同，VapnikVapnik等人 提出了一个较完善的基于有限样本的理 论体系统计学习理论统计学习理论。 u统计学习理论是又一种通用的前馈神经 网络，同样可用于解决模式分类和非线 性

2、映射问题。 u支持向量机方法是在统计学习理论基础 上发展起来的通用学习方法，它具有全 局优化、适应性强、理论完备、泛化性 能好等优点 。 支持向量机支持向量机 （Support Vector Machine，SVM） u90年代中期，在统计学习理论的基础上发 展出了一种通用的学习方法支持向量 机。它根据有限的样本信息在模型的复杂它根据有限的样本信息在模型的复杂 性和学习能力之间寻求最佳折衷，以获得性和学习能力之间寻求最佳折衷，以获得 最好的泛化能力最好的泛化能力。 u支持向量机在很多机器学习问题的应用中 已初步表现出很多优于已有方法的性能。 u支持向量机的理论最初来自于对数据分 类问题的处理。

3、对于线性可分数据的二 值分类，如果采用多层前向网络来实现， 其机理可以简单描述为：系统随机的产 生一个超平面并移动它，直到训练集合 中属于不同类别的点正好位于该超平面 的不同侧面，就完成了对网络的设计要 求。但是这种机理决定了不能保证最终 所获得的分割平面位于两个类别的中心， 这对于分类问题的容错性容错性是不利的。 u保证最终所获得的分割平面位于两个类 别的中心对于分类问题的实际应用是很重 要的。支持向量机方法很巧妙地解决了这 一问题。 u该方法的机理可以简单描述为：寻找一 个满足分类要求的最优分类超平面，使得 该超平面在保证分类精度保证分类精度的同时，能够 使超平面两侧的空白区域最大化使超平

4、面两侧的空白区域最大化；从理 论上来说，支持向量机能够实现对线性可 分数据的最优分类。为了进一步解决非线 性问题，Vapnik等人通过引入核映射核映射方 法转化为高维空间的线性可分问题来解决。 最优分类超平面最优分类超平面 （Optimal Hyperplane ） u对于两类线性可分两类线性可分的情形，可以直接构造最优 超平面，使得样本集中的所有样本满足如下条 件： （1）能被某一超平面正确划分； （2）距该超平面最近的异类异类向量与超平面之间 的距离最大，即分类间隔（margin ）最大。 u设训练样本输入为 ， ， 对应的期望输出为 u如果训练集中的所有向量均能被某超平 面正确划分，并且

5、距离平面最近的异类异类 向量之间的距离最大（即边缘margin最 大化），则该超平面为最优超平面 （Optimal Hyperplane ） 。 i x1, ,il d i Rx 1, 1 i y 最优分类面示意图最优分类面示意图 支持向量 Support Vector u其中距离超平面最近的异类向量被称为 支持向量（Support Vector），一组支持 向量可以唯一确定一个超平面。SVM是 从线性可分情况下的最优分类面发展而 来，其超平面记为： u为使分类面对所有样本正确分类并且具 备分类间隔，就要求它满足如下约束： 0bxw 1 1 1 0 1 1 ii ii ii bfory yb

6、bfory x w x w x w u可以计算出分类间隔为 ，因此构造最优 超平面的问题就转化为在约束式下求： u为了解决这个约束最优化问题，引入下式所示 的Lagrange函数： 其中 为Lagrange乘数。约束最优化问题的解由 Lagrange函数的鞍点决定。 2 w 211 min 22 www w 2 11 1 2 ll iiii ii Lyb wxw 0 i u利用Lagrange优化方法可以将上述二次 规划问题转化为其对偶问题对偶问题，即在约束 条件： 下对 求解下列函数的最大值： 如果 为最优解，那么： l i ii y 1 0li i , 1,0 i 1,1 1 2 ll i

7、ijijij ii j Wy y xx i 1 l iii i y wx u以上是在不等式约束下求二次函数极值 问题，是一个二次规划问题（Quadratic Programming，QP），），存在唯一解。根据 最优性条件Karush-Khn-Tucker条件 （KKT条件），这个优化问题的解必须满 足： u对多数样本对多数样本 将为零，取值不为零的将为零，取值不为零的 所对应的样本即为支持向量，它们通常只所对应的样本即为支持向量，它们通常只 是全体样本中很少的一部分。是全体样本中很少的一部分。 10,1, iii b yil x w i i u求解上述问题后得到的最优分类函数是： u在通过训

8、练得到最优超平面后,对于给定 的未知样本x，只需计算f (x)即可判断x所 属的分类。 1 sgn l iii i fyb xxx u若训练样本集是线性不可分的，或事先 不知道它是否线性可分，将允许存在一些 误分类的点，此时引入一个非负松弛变非负松弛变 量量 ，约束条件变为: u目标函数改为在以上约束条件下求： u 即折衷考虑最小错分样本和最大分类间 隔。其中，C0 为惩罚因子 ，控制对错 分样本的惩罚程度 。 0 i 1 0 1, iiii ybil w x， 1 1 min , 2 l i i C ww w u线性不可分情况和线性可分情况的 差别差别就在于可分模式中的约束条件中 的 在不可

9、分模式中换为了更严 格的条件 。除了这一修正， 线性不可分情况的约束最优化问题中 权值和阈值的最优值的计算都和线性 可分情况中的过程是相同的。 0 i 0 i C 支持向量机支持向量机 （Support Vector Machine, SVM） u在现实世界中，很多分类问题都是线性不可分 的，即在原来的样本空间中无法找到一个最优 的线性分类函数，这就使得支持向量机的应用 具有很大的局限性。但是可以设法通过非线性通过非线性 变换将原样本空间的非线性问题转化为另一个变换将原样本空间的非线性问题转化为另一个 空间中的线性问题空间中的线性问题。SVM就是基于这一思想的。 首先将输入向量通过非线性映射变

10、换到一个高 维的特征向量空间，在该特征空间中构造最优 分类超平面。 u由于在上面的二次规划（QP）问题中， 无论是目标函数还是分类函数都只涉及 内积运算，如果采用核函数(Kernel Function)就可以避免在高维空间进行复杂 运算，而通过原空间的函数来实现内积 运算。因此，选择合适的内积核函数核函数 就可以实现某 一非线性变换后的线性分类，而计算复 杂度却没有增加多少 ，从而巧妙地解决 了高维空间中计算带来的“维数灾难” 问题。 , ijij K xxxx u此时，相应的决策函数化为： u支持向量机求得的决策函数形式上类似 于一个神经网络，其输出是若干中间层 节点的线性组合，而每一个中间

11、层节点 对应于输入样本与一个支持向量的内积， 因此也被称作是支持向量网络。 1 sgn, l iii i fyKb xx x 支持向量机示意图支持向量机示意图 选择不同的核函数 可以生成不同的支持向量机，常有以下 几种： （1）线性核函数： （2）多项式核函数： （3）Gauss核函数： （4）Sigmoid核函数： , ijij K x xxx , ii Kx xx x ,1 q ii K x xx x 2 ( ,)exp 2 i i K xx x x ,tanh ii Kcx xx x 一个具体核函数的例子一个具体核函数的例子 假设数据是位于 中的向量，选择： 然后寻找满足下述条件的空间H

12、：使映射 从 映射到H且满足： 可以选择H=R3以及： 2 R 2 , ijij Kx xxx 2 R 2 x yxy 2 1 1 2 2 2 ( )2 x x x x x x2 x1 z3 z2 z1 用图来表示该变换：用图来表示该变换： SVM用于二维样本分类用于二维样本分类 支持向量机与多层前向网络支持向量机与多层前向网络 的比较的比较 u与径向基函数网络和多层感知器相比， 支持向量机避免了在前者的设计中经常使 用的启发式结构，它不依赖于设计者的经 验知识；而且支持向量机的理论基础决定 了它最终求得的是全局最优值而不是局部 极小值，也保证了它对于未知样本的良好 泛化能力而不会出现过学习现

13、象。 支持向量机的分类学习支持向量机的分类学习 算法算法 对于分类问题，用支持向量机方法进 行求解的学习算法过程为： 第一步第一步 给定一组输入样本 ， 及其对应 的期望输出 ； 第二步第二步 选择合适的核函数 及 相关参数； 第三步第三步 在约束条件 和 下求解 得到最优权值 ； i xli, 1 1, 1 i y , ijij K x xxx l i ii y 1 00 i C 1,1 1 max ( )(, ) 2 ll iijiji ii j Wy y K x x i 第四步 计算： ； 第五步 对于待分类向量x ，计算： 为1或1，决定x属于哪一类。 1 () l iii i y w

14、x 1 sgn, l iii i fyKb xx x 用于函数拟合的支持向量机用于函数拟合的支持向量机 u假定数据集 。首先考 虑用线性回归函数线性回归函数 拟合数据 集X的问题。 u所有训练数据在精度 下无误差地用线性 函数拟合，即： u考虑到允许拟合误差存在的情况： (,)1, ii Xyilx ( )fbxw x 1, ii ii yb il by w x w x 1, iii iii yb il by w x w x u优化目标函数为： u对偶问题为：在约束条件 下求下式的最大值。 u回归函数为： 1 1 min ( ,)()() 2 l iiii i C ww w 1111 1 (,

15、)()()()()() 2 llll iiiiiiiiijjij iiij Wy xx 0, 1, ii Cil 1 ( )()() l iii i fbb xw xx x 用不同的支持向量机对人工数据进用不同的支持向量机对人工数据进 行分类行分类 （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; （b ）线性不可分 对下面二维待分类人工数据P进行分类： X = 2 7; 3

16、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; （1）、实验环境）、实验环境 Matlab 7.0 （2）、界面设计）、界面设计 （3 3）、具体实现）、具体实现 a) a) 对于线性可分的人工样本数据对于线性可分的人工样本数据P P。其中共有。其中共有1111个待分类样本。个待分类样本。使用 最简单的支持向量机，即以线性核函数K(x,xi i)=(x. . xi i)作为内积函数的 支持向量机来训练该数据集合。惩罚因子C取10。 黑色

17、线为数据集合的两类分类线，可以看出它能将两类准确无误的分开，错 误率为0。蓝线和绿线为两类样本的最大间隔边界。5,11,6三点为支持向量。 样本点样本点分类结果分类结果 b)b) 对于线性不可分的人工样本数据对于线性不可分的人工样本数据P P。其中共有。其中共有1212个待分类样本。个待分类样本。 1 1）用线性核函数）用线性核函数SVMSVM进行训练。进行训练。仍采用最简单的支持向量机，即以线性核 函数K(x,xi i)=(x. . xi i)作为内积函数的支持向量机来训练该数据集合。惩 罚因子C取10。 显然黑色线为数据集合的两类分类线，不能将两类准确无误的分开，点12是 错分的样本点，而

18、5和点11落在了分类间隔内。此时正确率为91.67%。 样本点样本点分类结果分类结果 2 2）利用较为复杂的）利用较为复杂的RBFRBF核函数支持向量机进行分类。核函数支持向量机进行分类。 RBF核函数中的核宽度这个参数是由用户决定的。因此下面采用三个不同的 RBF核宽度来对该函数集合进行分类。惩罚因子C取100。 选择RBF核宽度为8,其结果如图所示。 从图中可以看出，此时SVM以点12作为类别1的一个聚类中心，在其周围 形成了一个类似“小岛”的区域。并且，点2，3，4，5，6,11和12是支持向 量，错分样本数为0。 使用一个较小的值1作为RBF核宽度,其结果如图所示。 黑线为分类边界，蓝

19、线和绿线为两类的最大间隔边界。由于较小的核宽度允 许了分类边界的分割，因此图中的分类边界有很多条。由此造成了每个样本 点都是支持向量，所以错分样本数为0。 使用一个较大的值36作为RBF核宽度,其结果如图所示。 黑线为分类边界，蓝线和绿线为两类的最大间隔边界。使用较大的核宽度时 分类边界比较简化，但是出现了错分样本，即点5和12，此时的分类正确率 为83.33%。 实验小结: 从实验可以看出，针对同一问题，也即 同一组数据来说，用不同核函数的支持 向量机的分类结果是不同的。而且可以 看到针对不同的问题，对同一种核函数 支持向量机来说，选择合适的参数也是 很关键的，不同的参数的选择就对应着 不同

20、的分类结果。 支持向量机算法的研究与应用支持向量机算法的研究与应用 u 支持向量机算法改进支持向量机算法改进 u 核函数的改进核函数的改进 u 错误惩罚参数的选择错误惩罚参数的选择 u 不敏感参数不敏感参数 的选择的选择 u 支持向量机解决多类划分问题支持向量机解决多类划分问题 u 支持向量机的应用支持向量机的应用 支持向量机算法改进支持向量机算法改进 传统的利用标准二次型优化技术解决对偶 问题的方法是训练算法慢的主要原因。 (1) SVM方法需要计算和存储核函数矩阵， 当样本点数目较大时，需要很大的内存， 例如，当样本点数目超过4000时，存储核 函数矩阵需要多达128MB内存； (2) S

21、VM在二次型寻优过程中要进行大量的 矩阵运算，多数情况下，寻优算法是占用 算法时间的主要部分。 u近年来人们针对方法本身的特点提出了 许多算法来解决对偶寻优问题。这些算 法的一个共同的思想就是采用分而治之分而治之 的原则将原始QP问题分解为规模较小的 子问题，通过循环解决一系列子问题来 求得原问题的解。 u现有的训练算法分为三类： “块算法”（chunking algorithm） “Osuna 分解算法” “SMO算法” 核函数的改进核函数的改进 u核函数的形式及其参数决定了分类器的类型和复杂程度。 在不同的问题领域，核函数应当具有不同的形式和参数， 应将领域知识引入进来，从数据依赖的角度选

22、择核函数。 u初步尝试的方法有： Amari利用黎曼几何结构方法来修改核函数 ； Barzilay通过改进邻近核来改进核函数； Brailovsky局部核函数方法； G. F. Smits 多个核函数组合起来使用； 错误惩罚参数的选择错误惩罚参数的选择 错分样本惩罚参数C实现在错分样本的比 例和算法复杂度之间的折衷。C值的确定 一般是用户根据经验给定的，随意性很 大，也很难知道所取C值的好坏性。如何 消除C值选取的随意性，而采用某种方法 自动地选择一个最佳的C值，这个问题目 前尚未解决。 不敏感参数不敏感参数 的选择的选择 uSVM通过参数 控制回归估计的精度， 但 取多少才能达到所期望的估计

23、精度是 不明确的，为此出现了许多新的SVM方 法。 u Schlkoph和Smola -SVM方法方法 u Lin C-F 加权支持向量机，通过对 每个样本数据点采用不同的 ，来获得 更准确的回归估计。 支持向量机解决支持向量机解决多类多类划分划分 问题问题 “多类支持向量机”（Multi-category Support Vector Machines，M-SVMs）。 它们可以大致分为两大类： （1）通过某种方式构造一系列的两类分 类器并将它们组合在一起来实现多类分 类； （2）直接在目标函数上进行改进，建立K 分类支持向量机。 一对多方法一对多方法 ( l - against - res

24、t ，1-a-r) 此算法是对于K类问题构造K个两类分类器。第i个SVM 用第i类中的训练样本作为正的训练样本，而将其它的 样本作为负的训练样本，即每个SVM分别将某一类的 数据从其他类别中分离出来。测试时将未知样本划分 到具有最大分类函数值的那类。 缺点：泛化能力较差，且训练样本数目大，训练困难。 此外，该方法还有可能存在测试样本同时属于多类或 不属于任何一类的情况。 一对一方法一对一方法 ( l - against - 1，1-a-1) u该算法在K类训练样本中构造所有可能的两类 分类器，每类仅仅在K类中的两类训练样本之 间训练，结果共构造K(K-1)/2个分类器。组合 这些两类分类器很自

25、然地用到了投票法，得票 最多（ Max Wins ）的类为新点所属的类。 u缺点：推广误差无界，分类器的数目K(K-1)/2 随类数K的增加急剧增加，导致在决策时速度 很慢。此外，还可能存在一个样本同时属于多 个类的情况。 决策导向非循环图决策导向非循环图SVM方法方法 （Decision Directed Acyclic Graph，DDAG） u在训练阶段，其与1-a-1方法相同，对于K类问题， DDAG含有K(K-1)/2个两类分类器。然而在决策阶段， 使用从根节点开始的导向非循环图（DAG），具有 K(K-1)/2个内部节点以及K个叶子节点，每个内部节点 都是一个两类分类器，叶子节点为

26、最终的类值。 u缺点：根节点的选择直接影响着分类的结果，不同的 分类器作为根节点，其分类结果可能会不同，从而产 生分类结果的不确定性。 基于二叉树的多类基于二叉树的多类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）。 u优点：所需要训练的两类支持向量机的数量

27、 少 ；消除了决策时存在同时属于多类或不属于 任何一类的情况 ；总共需要训练的样本和前两 种方法相比减少了许多。 u缺点：若在某个节点上发生分类错误，将会把 错误延续下去，该节点后续下一级节点上的分 类就失去意义。 最小最大模块化支持向量机最小最大模块化支持向量机 （Min-Max-Modular -SVM, M3-SVM ） u该方法充分利用分布式并行计算系统，将一个 K类问题分解成K(K-1)/2个二类问题，然后把一 个二类问题分解成一系列指定规模的小的二类 子问题。 u优点：这些二类子问题的特点是在训练过程中 完全相互独立，因此可以容易地在集群计算机 和网格上实现超并行学习。在保证推广能

28、力的 前提下，能够明显提高训练速度，是一种解决 大规模模式分类问题的有效方法。 支持向量机的应用支持向量机的应用 随着对SVM研究的进展和深入，其应用也越来 越广泛，基于SVM思想的一些模型和方法被广 泛应用于各个领域，包括模式识别，如人脸识 别、字符识别、笔迹鉴别、文本分类、语音鉴 别、图像识别、图像分类、图像检索等等；回 归估计，如非线性系统估计、预测预报、建模 与控制等等；以及网络入侵检测、邮件分类、 数据挖掘和知识发现、信号处理、金融预测、 生物信息等新领域。 u可以计算出分类间隔为 ，因此构造最优 超平面的问题就转化为在约束式下求： u为了解决这个约束最优化问题，引入下式所示 的La

29、grange函数： 其中 为Lagrange乘数。约束最优化问题的解由 Lagrange函数的鞍点决定。 2 w 211 min 22 www w 2 11 1 2 ll iiii ii Lyb wxw 0 i u利用Lagrange优化方法可以将上述二次 规划问题转化为其对偶问题对偶问题，即在约束 条件： 下对 求解下列函数的最大值： 如果 为最优解，那么： l i ii y 1 0li i , 1,0 i 1,1 1 2 ll iijijij ii j Wy y xx i 1 l iii i y wx u以上是在不等式约束下求二次函数极值 问题，是一个二次规划问题（Quadratic Programming，QP），），存在唯一解。根据 最优性条件Karush-Khn-Tucker条件