支持向量机课件

第10章支持向量机 10.1统计学习理论的一般概念10.2最优化理论基础10.3支持向量机10.4支持向量机的实现10.5SVM在故障诊断中的应用10.6小结习题 10.1统计学习理论的一般概念第10章支持向量机 在第3章，我们研究了由反向传播算法训练的多层感知器。在第8章，我们研究了另一类分层前馈网络，即径向基函数神经网络。这两种神经网络按它们自己的方式都可以称为通用函数逼近器。本章我们将讨论基于统计学习理论而发展的一种新的通用学习方法支持向量机(Support Vector Machine，SVM)。像多层感知器网络和径向基函数网络一样，支持向量机也能用于模式分类和非线性回归。在第3章，我们研究了由反向传播算法训练的多层感知器。在第第10章支持向量机 10.1统计学习理论的一般概念统计学习理论的一般概念 基于数据的机器学习是现代智能技术中的重要方面，它研究从观测数据(样本)出发寻找规律，并利用这些规律对未来数据或无法观测的数据进行预测。机器学习的过程就是构建学习机的过程。机器学习含有多种方法，如决策树、遗传算法、人工神经网络、隐Markov 链(HMM)等。迄今为止，关于机器学习还没有一种被共同接受的理论框架，关于其实现方法大致可以分为下述三种。10.1统计学习理论的一般概念 基于数据的机器学习是现第10章支持向量机 第一种是经典的(参数)统计估计方法，包括模式识别、神经网络等在内。现有机器学习方法共同的重要理论基础之一是统计学，参数方法正是基于传统统计学的。在这种方法中，参数的相关形式是已知的，练样本用来估计参数的值。这种方法存在很大的局限性：首先，它需要已知样本分布形式，这需要花费很大代价；其次，传统统计学研究的是样本数目趋于无穷大时的渐近理论，现有学习方法也多是基于此假设，但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法在实际中的表现却可能不尽人意。第一种是经典的(参数)统计估计方法，包括模式识别、神经网第10章支持向量机 第二种方法是经验非线性方法，如人工神经网络(ANN)。这种方法利用已知样本建立非线性模型，克服了传统参数估计方法的困难。但是，这种方法缺乏一种统一的数学理论。第三种方法是20世纪60年代后期发展起来的统计学习理论(Statistical Learning Theory，SLT)，它是一种专门研究有限样本情况下非参数估计问题的机器学习理论。与传统统计学相比，该理论针对有限样本统计问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在现有有限信息的条件下得到最优结果。第二种方法是经验非线性方法，如人工神经网络(ANN)。这第10章支持向量机 统计学习理论是建立在一套较坚实的理论基础之上的，为解决有限样本学习问题提供了一个统一的框架。它能将很多现有方法纳入其中，有望帮助解决许多原来难以解决的问题(比如神经网络结构选择问题、局部极小点问题等)；同时，在这一理论基础上发展了一种新的通用学习方法支持向量机，它已初步表现出很多优于已有方法的性能。一些学者认为，SLT和SVM正在成为继神经网络研究之后新的研究热点，并将推动机器学习理论和技术的重大发展。统计学习理论是建立在一套较坚实的理论基础之上的，为解决有第10章支持向量机 10.1.1机器学习问题的表示机器学习问题的表示机器学习的目的是根据给定的训练样本求取系统输入、输出之间依赖关系的估计，使它能够对系统行为做出尽可能准确的预测。机器学习问题的基本模型可以用图10-1表示。其中，系统S是我们研究的对象，它在给定输入x下得到一定的输出y，LM是我们所求的学习机，其输出为。10.1.1机器学习问题的表示机器学习的目的是根据给第10章支持向量机 图10-1机器学习的基本模型图10-1机器学习的基本模型第10章支持向量机 定义定义10.1设变量y与变量x之间存在一定的未知依赖关系，即遵循某一未知的联合概率分布P(x,y)，机器学习问题就是根据l个独立同分布(i.i.d)的观测样本：(x1,y1),(x2,y2),(xl,yl)(10-1)在一组函数f(x,)中按某个准则选择一个最优的函数f(x,0)对依赖关系进行估计，其中，是参数；而f(x,)就是一个学习机(Learning Machine，LM)。如果对于给定的输入x和的一个选择，其输出f(x,)总是相同的，则这个学习机f(x,)是确定性的(Deterministic)，否则称为不确定性的(Uncertainty)对于确定性学习机中的的一个特定选择，就称其为训练过的学习机(Trained Machine)。定义10.1设变量y与变量x之间存在一定的未知依赖关系第10章支持向量机 定义定义10.2对于一个学习机，损失函数(Loss Function)L(y,f(x,)表示用f(x,)对y进行预测而造成的损失。有三类基本的机器学习问题，即模式识别、函数逼近和概率密度估计，不同类型的学习问题有不同形式的损失函数。定义10.2对于一个学习机，损失函数(Loss Fu第10章支持向量机(1)模式识别问题(这里仅讨论监督模式识别问题)：输出变量y是类别标号。在两类情况下，y=0,1或-1,1是二值函数，这时f(x,)称为指示函数(Indicator Function)，也称为判别函数。模式识别问题中损失函数的一般定义为(10-2)(1)模式识别问题(这里仅讨论监督模式识别问题)：输第10章支持向量机(2)函数逼近问题(回归问题)：输出变量y是连续变量(这里假设为单值函数)，损失函数一般定义为 L(y,f(x,)=(y-f(x,)2 (10-3)即采用最小平方误差准则。(3)概率密度估计问题：学习的目的是根据训练样本确定x的概率密度，设估计的密度函数为p(x,)，则损失函数一般定义为 L(p(x,)=logp(x,)(10-4)(2)函数逼近问题(回归问题)：输出变量y是连续变量第10章支持向量机 10.1.2经验风险最小化经验风险最小化定义定义10.3对于一个学习机，损失函数的期望：R()=L(y,f(x,)dP(x,y)(10-5)称为期望风险(Expected Risk)或真实风险(Actual Risk)。而经验风险(Empirical Risk)则是训练集上的平均误差，即：(10-6)10.1.2经验风险最小化定义10.3对于一个学习第10章支持向量机 学习的目标在于使期望风险最小化，但是，期望风险R()要依赖联合概率P(x,y)的信息，实际问题中无法计算。因此传统的学习方法中采用了所谓经验风险最小化(ERM)准则，即用样本定义经验风险如式(10-6)所示。作为对式(10-5)的估计，设计学习算法使它最小化。对于损失函数式(10-2)，经验风险就是训练样本错误率；对于式(10-3)的损失函数，经验风险就是平方训练误差；而采用式(10-4)，损失函数的ERM准则就等价于最大似然方法。学习的目标在于使期望风险最小化，但是，期望风险R()要第10章支持向量机 事实上，神经网络与其他经典学习算法将ERM准则视为当然的出发点，并未研究其合理性、适用范围、可达到的近似质量等理论问题，只是直观上想当然的做法。如此做法存在以下几个问题：(1)经验风险最小不等于期望风险最小，不能保证学习机的推广能力。算法或方法对未来输出进行正确预测的能力称为推广能力或泛化能力。(2)从概率论中的大数定律可知，经验风险只有在样本数无穷大时才趋近于期望风险，需要非常多的样本才能保证学习机的性能。事实上，神经网络与其他经典学习算法将ERM准则视为当然的第10章支持向量机(3)某些情况下，当经验风险过小时，推广能力反而下降，这就是神经网络中令人头疼的所谓过学习(Overfitting)问题。(4)使经验风险最小的点与期望风险最小的点并非同一个点(如图10-2所示)。(3)某些情况下，当经验风险过小时，推广能力反而下降，第10章支持向量机 图10-2期望风险与经验风险之间的关系图 图10-2期望风险与经验风险之间的关系图 第10章支持向量机 在早期神经网络研究中，人们总是把注意力集中在如何使Remp更小，但很快发现，一味追求小的训练误差并不是总能达到好的预测效果。在某些情况下，训练误差过小反而会导致推广能力的下降，即出现过学习现象。在早期神经网络研究中，人们总是把注意力集中在如何使Rem第10章支持向量机 之所以出现过学习现象，一是因为学习样本不充分，二是学习机设计不合理，这两个问题是相互关联的。假设我们有一组训练样本(x,y)，x分布在实数范围内，而y取值在 0,1之间，那么不论这些样本是依据什么函数模型产生的，只要我们用一个函数f(x,)来拟合这些样本，其中是待定参数，总能够找到一个使训练误差为零，如图10-3所示，但显然这个“最优函数”不能正确代表原来的函数模型。原因就是试图用一个复杂的模型来拟合有限的样本，结果导致丧失了推广能力。之所以出现过学习现象，一是因为学习样本不充分，二是学习机第10章支持向量机 在神经网络中，如果对于有限的训练样本来说网络的学习能力过强，足以记住每一个训练样本，此时经验风险很快可以收敛到很小甚至零，但却根本无法保证它对新的样本能够得到好的预测。这就是有限样本下学习机的复杂性与推广性之间的矛盾。在神经网络中，如果对于有限的训练样本来说网络的学习能力过第10章支持向量机 图10-3用三角函数拟合任意点的例子图10-3用三角函数拟合任意点的例子第10章支持向量机 支持向量机课件第10章支持向量机 支持向量机课件第10章支持向量机 由此可看出，有限样本情况下：经验风险最小并不一定意味着期望风险最小；学习机的复杂性不但应与所研究的系统有关，而且要和有限数目的样本相适应。我们需要一种能够指导我们在小样本情况下建立有效的学习和推广方法的理论。由此可看出，有限样本情况下：经验风险最小并不一定意第10章支持向量机 10.1.3学习机的学习机的VC维与风险界维与风险界统计学习理论就是研究小样本统计估计和预测的理论。它从理论上较系统地研究了经验风险最小化原则成立的条件、有限样本下经验风险与期望风险的关系及如何利用这些理论找到新的学习原则和方法等问题。其主要涉及的内容包括：(1)经验风险最小化准则下统计学习一致性的条件；(2)在这些条件下关于统计学习方法推广性的界的结论；(3)在这些界的基础上建立的小样本归纳推理准则；10.1.3学习机的VC维与风险界统计学习理论就是第10章支持向量机(4)实现新的准则的实际方法(算法)。其中，最有指导性的理论结果是推广性的界，与此相关的一个核心概念是VC维(Vapnik Chervonenkis Dimension)。经验风险Remp()到期望风险R()的一致收敛性理论包括收敛速度的解，它们基于称为VC维的重要参数。VC维是由学习机实现的分类函数族的容量或表示能力的测度。(4)实现新的准则的实际方法(算法)。其中，最有指第10章支持向量机 在给出VC维定义之前，首先讨论线性分类问题。两类问题的分类通常用一个实值函数按照这样的方式操作：当f(x)0时，输入xX被标记为正类，否则被标记为负类。考虑f(x)，xX是线性函数的情况，函数可以写(10-7)其中w是一个n维权值向量，b是偏置，学习算法意味着一定要从数据中学习到这些参数。决策规则由sgn(f(x)给出，sgn()是一符号函数，即：在给出VC维定义之前，首先讨论线性分类问题。两类问题的分第10章支持向量机 这类假设的几何解释是，wTx+b=0定义的判别边界将输入空间X分为两半(见图10-4)。当n=2时，二维情况的判别边界为一直线；当n=3时，判别边界为一平面;n3 时，则判别边界为一超平面。超平面是维数为n-1的仿射子空间，它将输入空间分为两部分，这两部分对应输入中的两类。在图10-4中，当b的值变化时，超平面平行于自身移动。因此，如果想表达Rn中的所有可能超平面，包括n+1个可调参数的表达式是必要的。这类假设的几何解释是，wTx+b=0定义的判别边界将输入第10章支持向量机 图10-4二维情况下的分类超平面图10-4二维情况下的分类超平面第10章支持向量机 定义定义10.4考虑两类分类问题，其中函数f(x,w)0,1，。对于给定的一组l个点，可以按所有2l个可能的方式进行标识；对于每一个可能的标识，如果在f(w)中总能取得一个函数，这个函数能够用来正确地区分这些标识，则称这l个点构成的点集能够被f(w)分隔(Shattered)。函数族f(w)的VC维定义为能够被f(w)分隔的训练点l的最大数目。若对任意数目的样本都有函数能够将它们分隔，则函数集的VC维是无限大的。定义10.4考虑两类分类问题，其中函数f(x,w)第10章支持向量机 用更熟悉的话说，分类函数集f(w)的VC维是能被机器学习的训练样本的最大数量，这种学习对于分类函数所有可能的二分标记是无错误的。VC维反映了函数集的学习能力，VC维越大则学习机越复杂(容量越大)。遗憾的是，目前尚没有通用的关于任意函数集VC维计算的理论，只对一些特殊的函数集知道其VC维。比如在n维实数空间中线性分类器和线性实函数的VC维是n+1。用更熟悉的话说，分类函数集f(w)的VC维是能被机器第10章支持向量机 为了说明Rn中超平面集合的VC维是n+1这一结论，考虑图10-5所描述的二维空间(即n=2)的情况。在图10-5(a)中，对于空间的任意三个点的集合x1,x2,x3，分为“左”、“上”、“下”，而且有8种(23)可能的标记。对于这些标记，总可以找到一组有向直线将不同的标记点进行分隔(注意标识不是赋值)。在图10-5(b)中，对于空间的四个点的集合x1,x2,x3,x4，点x2和x3标记为0，点x1和x4标记为1。可是这一次，我们看到点x1和x4不能用一条直线与点x2和x3分隔开来。式(10-7)中所描述的n=2判定规则的VC维是3。为了说明Rn中超平面集合的VC维是n+1这一结论，考虑图第10章支持向量机 图10-5二维空间的VC维(a)三个点被有向直线分隔;(b)四个点不能被有向直线分隔图10-5二维空间的VC维第10章支持向量机 注：在Rn中至少可以找到一组n+1个点能够被超平面分隔，但不是任意一组n+1个点都能够被超平面分隔。例如将所有点集中在一条直线上的情况就不能被分隔。我们不加证明地给出下述有用的定理。注：在Rn中至少可以找到一组n+1个点能够被超平面分隔第10章支持向量机 定理定理10.1Rn中两个点集能够被一个超平面分隔的充分与必要条件是其凸包(包含该点集的最小凸集)的交集为空集。定理定理10.2考虑Rn中l个点的集合，选择其中任意一点作为原点，那么l个点能够被超平面分隔的充分与必要条件是除了原点外其余点的位置向量是线性独立的。统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的关系，即推广性的界。关于两类分类问题，结论是：对指示函数集中的所有函数(包括使经验风险最小的函数)，经验风险Remp()和实际风险R()之间满足如下关系。定理10.1Rn中两个点集能够被一个超平面分隔的充分与第10章支持向量机 定义定义10.5对于一个学习机，假定损失函数以概率1-取值，其中01，那么下面的误差界成立：其中h是学习机的VC维，l是样本数目。定义10.5对于一个学习机，假定损失函数以概率1-取第10章支持向量机 不等式(10-8)的右边称为风险界(Risk Bound)，它由两部分组成:第一项是经验风险(训练误差);另一部分称为置信范围，它和学习机的VC维及训练样本数有关，是随l/h增大而减小的函数。实际风险可以简单地表示为(10-9)不等式(10-8)的右边称为风险界(Risk Bound第10章支持向量机 它表明，在有限训练样本下，学习机器的VC维越高(复杂性越高),则置信范围越大，导致实际风险与经验风险之间可能的差别越大。这就是为什么会出现过学习现象的原因。机器学习过程不但要使经验风险最小，还要使VC维尽量小以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性。它表明，在有限训练样本下，学习机器的VC维越高(复杂性越第10章支持向量机 关于风险界，需要指出，推广性的界是对于最坏情况的结论，在很多情况下是较松的，尤其当VC维较高时更是如此。而且，这种界只在对同一类学习函数进行比较时有效，可以指导我们从函数集中选择最优的函数，在不同函数集之间比较却不一定成立。关于风险界，需要指出，推广性的界是对于最坏情况的结论，在第10章支持向量机 10.1.4结构风险最小化结构风险最小化下面将讨论结构风险最小化(Structural RiskMinimization，SRM)问题。由学习机的风险界的构成看到，要控制学习机的实际风险，必须同时控制经验风险和置信范围。因为VC维是整数，难以使其平滑变化，于是，结构风险最小化的思想是，将函数集构造为一个函数子集序列，使各个子集按照VC维的大小(亦即的大小)排列；在每个子集中寻找最小经验风险，在子集间折中考虑经验风险和置信界限，取得实际风险最小。具体方法如下：10.1.4结构风险最小化下面将讨论结构风险最小化(第10章支持向量机 令z=(x,y)代表输入、输出样本数据对，将函数L(y,f(x,w)简记为Q(z,w)。选择函数Q(z,w)，使其具有一种嵌套结构：其中Sk=Q(z,w):满足第k种约束为函数集的子集，其VC维hk为有限的。在此结构中，嵌套子集按其复杂度(即VC维大小)的顺序排列：(10-10)此外，还要求子集Sk中的函数有界。令z=(x,y)代表输入、输出样本数据对，将函数L(y第10章支持向量机 此时机器学习的任务是在每个子集中寻找经验风险最小的同时，在子集间折中考虑经验风险和置信范围，使得实际风险最小，如图10-6所示。此时机器学习的任务是在每个子集中寻找经验风险最小的同时，第10章支持向量机 图10-6按VC维排序使函数嵌套的结构风险最小图10-6按VC维排序使函数嵌套的结构风险最小第10章支持向量机 SRM原理实际上提供了一种对于给定的样本数据在近似精度和模型近似函数复杂性之间折中的定量方法，即在近似函数集的结构中找出一个最佳子集，使实际风险确保上界达到极小。实现SRM原则可以有两种思路：一是在每个子集中求最小经验风险，然后选择使最小经验风险和置信范围之和最小的子集；二是设计函数集的某种结构使每个子集中都能取得最小的经验风险(如使训练误差为0)，然后只需选择适当的子集使置信范围最小，则这个子集中使经验风险最小的函数就是最优函数，支持向量机方法实际上就是这种思想的具体实现。SRM原理实际上提供了一种对于给定的样本数据在近似精度和第10章支持向量机 例如神经网络的构造过程，函数集为(10-12)其中y是估计对象的实际输出，是神经网络的输出。若隐节点数可变，则函数集(10-12)式具有嵌套结构：(10-13)其中Sk=Q(z,w):满足第k种约束中的神经网络都具有相同的结构，隐节点数为k，其近似函数为例如神经网络的构造过程，函数集为(10-12)其中y第10章支持向量机(10-14)已经证明，上述神经网络的VC维数取决于S函数的类型和权重的数目，并且在一般条件下是有界的(尽管它可能很大)。因此在选定的嵌套结构式(10-13)中，子集是按VC维数(即近似函数的复杂性)递增的顺序排列的，符合SRM归纳原理的要求。(10-14)已经证明，上述神经网络的VC维数取决于S第10章支持向量机 通常神经网络的设计，首先利用已有的先验知识或经验确定隐节点数目，从SRM原理的观点来看，这就是选定了一个子集Sk，该子集中所有的函数有一个确定不变的VC维数，即f(l/h)确定；随后通过训练确定最优权值，相当于最小化经验风险Remp()。目前存在的问题是神经网络结构的确定大多是凭经验选取的，有一定的盲目性，无法确定泛化的置信界限，所以无法保证网络的泛化能力。即使经验误差很小，但可能推广或泛化能力很差。这就是神经网络中的过学习难题。通常神经网络的设计，首先利用已有的先验知识或经验确定隐节第10章支持向量机 10.2最优化理论基础最优化理论基础 最优化理论是数学上的一个分支，它研究某些数学上定义的问题的最优解。根据特定的代价函数和约束的本质，可以得出许多类最优化问题，这些问题已经过深入研究并找到了很有效的解决方法。为了训练支持向量机，其中涉及到线性约束、二次目标函数等问题。10.2最优化理论基础 最优化理论是数学上的一个分支第10章支持向量机 10.2.1二次规划二次规划凸性在最优化理论和方法的研究中起着重要作用。本节简要地介绍凸集和凸函数的基本概念和基本结果。定义定义10.6(凸集)设集合，如果对任意x1,x2X，有：(10-15)则称X是凸集。这个定义表明，如果x1、x2属于凸集X，则连接x1和x2的线段仍属于X。10.2.1二次规划凸性在最优化理论和方法的研究中第10章支持向量机 定义定义10.7(凸组合)设x1,xlRn，若：其中，i0，i=1,l；则称x是x1,xl的一个凸组合。定理定理10.3(凸集的充要条件)集合是凸集的充分必要条件是X中任意若干点的任一凸组合仍属于X。现举例说明：定义10.7(凸组合)设x1,xlRn，若第10章支持向量机【例10-1】超平面 是凸集，其中wRn是非零向量，bR。事实上，对任意的x1，x2H和 0,1，有：wT(x1+(1-)x2)+b=0故 (x1+(1-)x2)H【例10-1】超平面 第10章支持向量机【例10-2】闭半空间H-=x|wTx和H+=x|wTx为凸集。注意到对任意x1，x2H-和 0,1，有：wT(x1+(1-)x2)=wTx1+(1-)wTx2故(x1+(1-)x2)H-,其余类似。【例10-2】闭半空间H-=x|wTx 和H+=第10章支持向量机 定理定理10.4若X1和X2是凸集，则交集X1X2也是凸集。【例例10-3】由有限个半闭空间的交组成的集合叫多面集，即其中wi是非零向量；i是数。则该多面集是闭凸集。定理10.4若X1和X2是凸集，则交集X1X2也是凸第10章支持向量机 定义定义10.8(凸函数)设集合是非空凸集，f是定义在X上的函数。称函数f是X上的凸函数，如果对任意的x1，x2X，(0,1),都有：f(x1+(1-)x2)f(x1)+(1-)f(x2)(10-17)称f为X上的严格凸函数。如果对任意x1x2时,则式(10-17)中的严格不等号成立。凸函数的定义表示两点的线性插值大于函数值，其几何解释为，一个凸函数的图形总是位于相应弦的下方。如果凸函数是可微的，可以用下面的特征描述凸函数。定义10.8(凸函数)设集合是非空凸集，f是定第10章支持向量机 定理定理10.5(凸函数的充要条件)设X是非空凸集，f(x)是X上的可微函数，则f(x)是凸函数的充要条件是，对任意的X中的点 ，都有 (10-18)类似地，f(x)是严格凸函数的充要条件是，对于任意的X中的点，都有：(10-19)定理10.5表明了根据局部导数的线性近似是函数的低估。定理10.5(凸函数的充要条件)设X是非空凸集，f(x第10章支持向量机 定理定理10.6考虑Rn上的二次函数：(10-20)其中G是nn矩阵，r是n维向量，是实数。若G是半正定矩阵，则f(x)是Rn上的凸函数；若G是正定矩阵，则f(x)是Rn上的严格凸函数。定理10.6考虑Rn上的二次函数：第10章支持向量机 定义定义10.9一般的最优化问题描述如下：这里f(x)称为目标函数，剩下的关系分别称为不等式约束和等式约束。目标函数的最优值称为最优化问题的值。对目标函数和约束的本质的不同假设会产生不同的优化问题。定义定义10.10对于目标函数，等式或不等式约束都是凸函数的最优化问题称为凸约束问题。对于目标函数是二次的，而约束都是线性函数下的最优化问题，称为二次规划问题。(10-21)定义10.9一般的最优化问题描述如下：这第10章支持向量机 定义定义10.11可行区域是指目标函数的约束满足的区域，可以表示为最优化问题的解是指存在一个点，使得不存在其他的点x满足 。这个点 也称为f(x)全局最小。如果满足 ，并且 ，满足 ，那么点 称为f(x)局部最小。(10-22)定义10.11可行区域是指目标函数的约束满足的区域，可第10章支持向量机 定理定理10.7考虑凸约束问题。设是问题的可行域，则：(1)若问题有局部解，则是问题的全局解；(2)问题的全局解组成的集合是凸集；(3)若问题有局部解，f(x)是上的严格凸函数，则是问题的唯一全局解。为了训练支持向量机(SVM)，只考虑线性约束、凸二次目标函数的问题，并且 Rn，即考虑处理凸二次规划问题。下一小节将介绍拉格朗日(Lagrange)乘子技术及其扩展，并将其限制在二次规划问题之内。定理10.7考虑凸约束问题。设是问题的可行域，则：第10章支持向量机 10.2.2拉格朗日理论拉格朗日理论解决约束非线性规划问题的方法大致有三类：直接处理约束、用线性规划逼近、转化成无约束问题。拉格朗日(Lagrange)乘子法是一种将约束问题变为无约束优化问题的方法，它揭示了条件极值的基本特性，也是最优准则法的理论基础。10.2.2拉格朗日理论解决约束非线性规划问题的方第10章支持向量机 现在来寻求目标函数z=f(x,y)在约束条件为(x,y)=0下,在点(x0,y0)取得极值的必要条件。因(x0,y0)是条件极值点，故有：j(x0,y0)=0 (10-23)设函数f(x,y)与j(x,y)在点(x0,y0)的某个邻域内有连续的偏导数，并且y(x,y)0。由隐函数存在定理可知，方程j(x,y)=0确定一个具有连续导数的函数y=y(x)，将其代入到目标函数,有：z=f(x,y)=f(x,y(x)(10-24)现在来寻求目标函数z=f(x,y)在约束条件为(x,第10章支持向量机 由于函数f(x,y)在(x0,y0)处取得极值，从而函数f(x,y(x)在x=x0处取得极值，必有：(10-25)由隐含数求导公式：由于函数f(x,y)在(x0,y0)处取得极值，从而第10章支持向量机 将其代入(10-25)式有：(10-26)式(10-23)和式(10-26)就是函数z=f(x,y)在点(x0,y0)处取得极值的必要条件。记 将其代入(10-25)式有：(10-26)式(10-第10章支持向量机 则上述条件可写成：(10-27)根据以上分析，引进函数：(10-28)此函数称为拉格朗日函数，其中叫做拉格朗日乘子。则上述条件可写成：(10-27)根据以上分析，引进函数：第10章支持向量机 从式(10-27)不难看出，(x0,y0)适合方程组：Lx=0,Ly=0,L=0 (10-29)即(x0，y0)是拉格朗日函数的驻点。设函数f(x,y)与j(x,y)有连续的偏导数，作拉格朗日函数L(x,y,)=f(x,y)+j(x,y)，如果(x0,y0)是方程组(10-27)的解，则点(x0,y0)是目标函数z=f(x,y)在约束条件j(x,y)=0下的可疑极值点。现在考虑最一般的情况，最优化问题既包含等式约束又包含不等式约束。首先，给出广义拉格朗日的定义。从式(10-27)不难看出，(x0,y0)适合方程组：第10章支持向量机 定义定义10.12 给定一个在域上的最优化问题：(10-30)定义广义拉格朗日函数为 (10-31)其中i(i=1,k)、i(i=1,m)为拉格朗日乘子。定义10.12 给定一个在域上的最优化问题：第10章支持向量机 在约束问题的最优解中，包含了对应的拉格朗日乘子向量。如果能事先知道这个拉格朗日乘子，常常会减少求解原始约束问题的困难，这产生了求解约束问题的一个新途径对偶方法。在约束问题的最优解中，包含了对应的拉格朗日乘子向量。如果第10章支持向量机 定义定义10.13定义10.12中原问题的拉格朗日对偶问题如下：这里(,)=infxL(x,)，目标函数在最优解的值称为问题的解。(我们使用“下确界inf”而不使用“极小值min”，原因是可能不存在极小值。)下面根据弱对偶定理及两个推论，给出原问题和对偶问题的基本关系。(10-32)定义10.13定义10.12中原问题的拉格朗日对偶问题第10章支持向量机 定理定理10.8令令x是定义10.12中原问题的一个可行解，而(,)是定义10.13中对偶问题的可行解,则f(x)(,)。推论推论1对偶问题的值的上界由原问题的值给出：sup(,)|0inf f(x)|g(x)0,h(x)=0推论推论2如果f(x)=(,)，其中0，并且g(x)0,h(x)=0，则x和(,)分别是原问题和对偶问题的解。在这种情况下,i=1,k。注：原问题的解和对偶问题的解的值之差称为对偶间隙。检测对偶间隙消失的方法是鞍点的出现。定理10.8令x是定义10.12中原问题的一个可行第10章支持向量机 定理定理10.9对于原问题，三元组(x,)是拉格朗日方程的鞍点，当且仅当其组成是原问题和对偶问题的最优解并且没有对偶间隙时，原问题和对偶问题的值关系为f(x)=(,)现在提出强对偶定理，该定理保证对于讨论的最优化的原问题和对偶问题有相同的值。定理10.9对于原问题，三元组(x,)第10章支持向量机 定理定理10.10给定域Rn上的最优化问题：其中gi和hi是仿射函数，也就是对于某个矩阵A和向量b有：其对偶间隙为零。下面介绍Kuhn-Tucker定理，该定理给出了一般的最优化问题有最优解的条件。定理10.10给定域Rn上的最优化问题：第10章支持向量机 定理定理10.11 给定一个定义在凸域上的最优化问题：其中f是可微且凸函数，gi和hi是仿射函数，一般地，一个点x是最优点的充分必要条件是存在满足：定理10.11 给定一个定义在凸域上的最优化问第10章支持向量机 其中L是广义拉格朗日函数。注：上式中的第三个关系称为KarushKuhnTucker互补条件(简称KKT条件)。它意味着对于积极约束(或有效约束)，有，但是对于非积极约束(或非有效约束)，有。其中L是广义拉格朗日函数。第10章支持向量机 10.2.3二次规划的对偶二次规划的对偶使用拉格朗日理论理解凸最优化问题可以使用一个对偶表示替代原问题，该对偶问题通常比原问题更易处理。因为直接处理不等式约束是困难的。对偶问题通过引入又称为对偶变量的拉格朗日乘子来解。对偶方法来源于将对偶变量作为问题的基本未知量的思想。下面把对偶性应用到凸二次目标函数的一个重要而特殊的场合，这是对偶性的一种实际应用。10.2.3二次规划的对偶使用拉格朗日理论理解凸最第10章支持向量机 定理定理10.12考虑二次规划问题(10-33)其中G是一个n n正定矩阵，。假设可行域非空，则这个问题可重写为：定理10.12考虑二次规划问题(10-33)其中G第10章支持向量机 在x上的最小值是无约束的，最小值在x=-G-1(AT+r)上得到。将该式代入原问题，得到其对偶形式：(10-34)在x上的最小值是无约束的，最小值在x=-G-1(AT第10章支持向量机 注：二次规划的对偶形式是另一个二次规划问题，但是其约束更为简单。二次规划问题已成为支持向量机理论的标准技术，并且铺平了从最优化理论到算法技术的道路。进一步的问题是，KKT互补条件意味着只有积极约束有非零对偶变量，这就意味着一些最优化问题的实际变量数目要比全部训练集的规模小很多。后面将使用到的“支持向量”这个术语是指那些对偶变量非零的训练样本。注：二次规划的对偶形式是另一个二次规划问题，但是其约束第10章支持向量机 10.3支支 持持 向向 量量 机机前面两节已经介绍了支持向量机的基础理论知识，而要使理论在实际中发挥作用，还要求它能够实现，这就是所谓的支持向量机(Support Vector Machine，SVM)方法。这也是统计学习理论中最“年轻”的部分，其主要内容在19921995年间基本完成，目前仍处于不断发展阶段。因为它从某种意义上可以表示成类似神经网络的形式，所以支持向量机在起初也曾被称为支持向量网络。什么是SVM？这个问题首先应从模式识别开始讲解。10.3支 持 向 量 机前面两节已经介绍了支持向量第10章支持向量机 10.3.1分类超平面的几何性质分类超平面的几何性质假定f(x)=wTx+b=0决定一个决策界面，当f(x)为线性时，这个决策界面便是一个超平面H。其中w是超平面H的法向量，决定超平面的方向；b决定超平面的位置。一般来说，超平面H把输入空间分成两个半空间,即R1、R2空间。当x在R1空间时，f(x)0,指向R1，为H的正侧；反之为H的负侧,如图10-7所示。10.3.1分类超平面的几何性质假定f(x)=wT第10章支持向量机 图10-7超平面的几何解释图10-7超平面的几何解释第10章支持向量机 超平面具有以下性质：(1)w与H正交(如图10-7所示)。假设x1和x2是H上的两个向量，因为 ，则 ，向量必在H上，所以w与(x1-x2)垂直，即w与H正交。超平面具有以下性质：(1)w与H正交(如图1第10章支持向量机(2)任意点xRn到超平面的代数距离 ，即f(x)正比于x到H的代数距离。证明：任意点x到超平面H的距离为(10-35)点s在超平面H上满足 ，用Lagrange乘子法解决约束最优问题。令非负变量，建立Lagrange函数：(2)任意点xRn到超平面的代数距离 第10章支持向量机(10-36)J(s,)对s和求微分并置结果等于零，得：(10-37)(10-36)J(s,)对s和求微分并置结果等于零，第10章支持向量机 令xi-si=ti，代入上式，得：(10-38)解得 ，于是：(10-39)令xi-si=ti，代入上式，得：(10-38)解得第10章支持向量机 对于点x，若f(x)0，则x点为H的正侧；若f(x)0，则x点为H的正侧；若f(x)0，则H在原点的正侧；若b0是对分类错误的惩罚，用于调整置信范围和经验误差间的均衡。C增大，则 被压制，经验风险小。(10-58)上式的目标函数实质上由两部分组成:一部分是控制分类器的VC第10章支持向量机 i是优化理论中的松弛变量，图10-10显示了两个误分点对应于标准超平面的间隔松弛变量。特别地，若xi没有错分，则i=0。图10-10分类问题中的松弛变量i是优化理论中的松弛变量，图10-10显示了两个误分点第10章支持向量机 近似线性可分支持向量机的原优化问题：(10-59)同样，我们可以得到近似线性可分的对偶表示，即：(10-60)近似线性可分支持向量机的原优化问题：(10-59)第10章支持向量机 对比线性可分情况与近似线性可分情况的对偶表示，二者最大化的目标函数是相同的；不同之处在于，约束条件i0被替换为条件更强的0iC。对比线性可分情况与近似线性可分情况的对偶表示，二者最大化第10章支持向量机 10.3.4非线性可分支持向量机非线性可分支持向量机超平面的分类能力毕竟有限，为此需要考虑分离曲面。令x为输入空间的向量，则通过事先确定的非线性映射函数：f:x f(x),RnF (10-61)把x映射到一个高维特征空间F，然后在F空间求最优分类超平面，如图10-11所示。10.3.4非线性可分支持向量机超平面的分类能力毕第10章支持向量机 图10-11简化分类任务的特征映射 图10-11简化分类任务的特征映射第10章支持向量机 可以注意到，在上面的支持向量机算法的对偶表示中，不论是寻优目标函数式(10-52)还是最优的超平面式(10-56)，都只涉及训练样本之间的内积运算。如果能够找到一个函数k使得k(xi,xj)=(xi)Tf(xj)，这样在特征空间F实际上只需进行内积运算；而这种内积运算是可以用原输入空间中的函数实现的，我们甚至没有必要知道非线性函数的具体形式。可以注意到，在上面的支持向量机算法的对偶表示中，不论是寻第10章支持向量机 这实际上就是支持向量机的另一吸引人的地方，即核的表示方法。通过选择使用恰当的核函数来代替内积，可以隐式地将训练数据非线性映射到高维特征空间，以增强线性分类器的计算能力。这实际上就是支持向量机的另一吸引人的地方，即核的表示方法第10章支持向量机 例例10-4 考虑二维输入空间的情况。设一非线性映射函数将输入空间的点映射到三维特征空间，非线性函数为：任选输入空间两点和，这样该两点在特征空间的内积为：例10-4 考虑二维输入空间的情况。设一非线性映射函第10章支持向量机 如定义核函数为输入空间两点内积的平方，则：因此，有：如定义核函数为输入空间两点内积的平方，则：因此，有：第10章支持向量机 满足Mercer条件的常用核函数：(1)多项式核函数(2)径向基核函数(3)Sigmoid核函数 或 满足Mercer 条件的常用核函数：或 第10章支持向量机 对于非线性分类问题，首先将输入样本经非线性隐函数投影到某个特征空间。变换后在空间的分类平面为：寻找最优参数对的过程，可转化为下列的约束优化问题：(10-62)(10-63)对于非线性分类问题，首先将输入样本经非线性隐函数投影到某第10章支持向量机 类似线性情况，引入拉格朗日乘子后，优化方程为：所得分类超平面为：(10-64)(10-65)类似线性情况，引入拉格朗日乘子后，优化方程为：所得分类超第10章支持向量机 以上在解决非线性可分问题过程中，其特点是在原空间构造一个核函数使之等于变换后空间的内积运算，尽管通过非线性变换将样本数据映射到高维甚至无穷维空间，并在高维空间中构造最优分类超平面，但在求解最优化问题和计算分类平面时并不需要显式计算该非线性函数，甚至不需知道其具体形式，而只需计算函数。以上在解决非线性可分问题过程中，其特点是在原空间构造一个第10章支持向量机 例例10-5 若有5个数据点分别为：且第1、2和5为正类，第3和4为负类，即：定义多项式核函数为例10-5 若有5个数据点分别为：第10章支持向量机 优化方程为利用二次规划算法，求得：优化方程为利用二次规划算法，求得：第10章支持向量机 因此，支持向量是。分类判别函数为其中，b的求解按照 、或 ，并且在 ，可得：分类判别函数(见图10-12)为：因此，支持向量是。分类判别函数为第10章支持向量机 图10-12 分类曲线图10-12 分类曲线第10章支持向量机 支持向量机算法的基本步骤如下：(1)训练样本归一化；(2)选择合适的核函数k(xi,xj)；(3)确定核函数参数及惩罚系数C；(4)执行训练算法，并求得拉格朗日系数i，i=1,l；(5)得到分类判别函数。支持向量机算法的基本步骤如下：第10章支持向量机 10.3.5支持向量回归机支持向量回归机支持向量的方法应用于回归问题，仍保留了最大间隔算法的所有主要特征：非线性函数可以通过高维特征空间中的线性学习算法得到，同时系统的容量由与特征空间维数不相关的参数控制；同分类算法一样，学习算法要最小化一个凸函数，并且它的解是稀疏的。10.3.5支持向量回归机第10章支持向量机 1.不敏感损失函数不敏感损失函数若以鲁棒性为设计目标，对于任何鲁棒性的数值度量必须考虑到由于微小噪声的影响而可能产生最大性能退化。这需要定义一个损失函数，它可以忽略真实值某个上下范围内的误差,可以描述为 (10-66)1.不敏感损失函数(10-66)第10章支持向量机 其中是指定的参数，损失函数L(d,y)称为不敏感损失函数(-insensitive Loss Function)。如果估计器输出y和期望输出d的偏差的绝对值小于，则损失函数等于零，否则它等于偏差绝对值减去。图10-13说明了L(d,y)和误差d-y的依赖关系。探讨不敏感损失函数的另一个动机是如同分类SVM一样，它可以确保对偶变量的稀疏性。使用训练点的一个小的子集表示解可带来很大的计算优势，同时确保全局最小解的存在和可靠泛化界的优化。其中是指定的参数，损失函数L(d,y)称为不敏感第10章支持向量机 图10-13不敏感损失函数图10-13不敏感损失函数第10章支持向量机 2.非线性非线性SVR考虑非线性回归模型，标量d对向量x的依赖可描述为d=f(x)+v (10-67)其中f()是自变量的一个确定性函数，加性噪声v统计独立于输入向量x，二者的统计特性是未知的。我们将所有可用的信息描述成一组训练数据 ，其中xi是输入向量x的一个样本值，di是模型输出d的相应值，l为样本个数。2.非线性SVR第10章支持向量机 如果在线性函数集合f(x)=(w f(x)+b中估计回归函数，求解问题的经验风险为其中 是高维特征空间的点。可以引入两组非负的松弛变量 和 描述式(10-66)定义的e不敏感损失函数，有：(10-68)(10-69)如果在线性函数集合f(x)=(w f(x)+b中估计第10章支持向量机-SVR就是在式(10-69)约束下，求下式的最小化代价泛函数：其中，惩罚因子C是事先给定的参数。为了构造相应的对偶问题，定义Lagrange乘子ai、，上面的凸二次规划问题可转化为求解下式的新形式：-SVR就是在式(10-69)约束下，求下式的最小化代第10章支持向量机 (10-71)(10-71)第10章支持向量机 式中 是满足Mercer定理的内积核。注意同模式识别问题的解一样，Lagrange乘子中仅有一部分不为零，对应的数据点定义为支持向量(Support Vector，SV)。e和两者都必须由用户选择，和控制的估计函数为：(10-72)式中 是满足Mercer 定理的内积核第10章支持向量机 e和C选择的原则方法一直是一个未解决的研究领域。从概念上讲，e和C选择的提出和模式分类中参数C的选择具有同样的复杂性。然而，在实际应用中回归的复杂性控制是一个更困难的问题，这是由于，参数e和C必须同时调整；回归本质上比模式分类更困难。e和C选择的原则方法一直是一个未解决的研究领域。从概念上第10章支持向量机 10.4支持向量机的实现支持向量机的实现支持向量机所涉及到的数学知识是比较难的，自己编程实现该算法难度就更大了。但是现在的网络资源非常发达，而且国际上的科学研究者把他们的研究成果已经放在网络上，免费提供给用于研究目的，这样方便大多数的研究者，不必要花费大量的时间理解SVM算法的深奥数学原理和计算机程序设计。目前有关SVM计算的相关软件有很多，如LIBSVM、mySVM、SVMLight等，这些软件大部分的免费下载地址和简单介绍都可以在http:/www.kernel-machines.org/上获得。10.4支持向量机的实现支持向量机所涉及到的数学知识第10章支持向量机 10.4.1 LIBSVM 软件包简介软件包简介LIBSVM是台湾大学林智仁博士开发设计的一个简单、易于使用和快速有效地SVM模式识别与回归的软件包。他不仅提供了LIBSVM的C语言的算法源代码，还提供了Python、Java、MATLAB、LabVIEW等语言的接口，可以方便的在Windows或UNIX平台下使用，也便于人们根据自己的需要进行改进(例如设计使用符合自己特定问题需要并且在进行模型参数选择时可以绘制出交叉验证精度的等高线图)。另外还提供了WINDOWS平台下的可视化操作工具SVM-toy。LIBSVM软件包可以在http:/www.csie.ntu.edu.tw/cjlin/免费获得。10.4.1 LIBSVM 软件包简介第10章支持向量机 LIBSVM可以解决分类问题(包括C-SVC、n-SVC)、回归问题(包括e-SVR、n-SVR)以及分布估计(one-class-SVM)等问题，提供了线性、多项式、径向基和S形函数四种常用的核函数供选择。SVM用于模式识别或回归时，SVM方法及其参数、核函数及其参数的选择，目前国际上还没有形成一个统一的模式，也就是说最优SVM算法、参数选择还只能是凭借经验、实验对比、大范围的搜寻或者利用软件包提供的交互检验功能进行寻优。LIBSVM可以解决分类问题(包括C-SVC、n-SVC第10章支持向量机 10.4.2 LIBSVM使用方法使用方法LIBSVM 在给出源代码的同时还提供了 Windows 操作系统下的可执行文件，包括：进行SVM训练的svmtrain.exe；根据已获得的SVM模型对数据集进行预测的 svmpredict.exe；以及对训练数据与测试数据进行简单缩放操作的svmscale.exe。它们都可以直接在 DOS 环境中使用。如果下载的包中只有 C+的源代码，则也可以自己在 VC 等软件上编译生成可执行文件。10.4.2 LIBSVM使用方法第10章支持向量机 LIBSVM使用的一般步骤是：按照LIBSVM软件包所要求的格式准备数据集；对数据进行简单的缩放操作；考虑选用RBF 核函数；采用交叉验证选择最佳参数与；采用最佳参数与对整个训练集进行训练获取SVM模型；利用获取的模型进行测试与预测。LIBSVM使用的一般步骤是：第10章支持向量机 1)LIBSVM使用的数据格式该软件使用的训练数据和检验数据文件格式如下：:其中是训练数据集的目标值，对于分类，它是标识某类的整数(支持多个类)；对于回归，是任意实数。是以1开始的整数，可以是不连续的；为实数，也就是我们常说的特征值或自变量。检验数据文件中的label只用于计算准确度或误差，如果它是未知的，只需用一个数填写这一栏，也可以空着不填。在程序包中，还包括有一个训练数据实例：heart_scale，方便参考数据文件格式以及练习使用软件。1)LIBSVM使用的数据格式第10章支持向量机 2)svmscale.exe的用法的用法对数据集进行缩放，其目的是：避免一些特征值范围过大而另一些特征值范围过小；避免在训练时为了计算核函数而计算内积的时候引起数值计算的困难，通常将数据缩放到-1,1或者是 0,1 之间。指令格式：svmscale-l lower-u upper-y y_lower y_upper -s save_filename-r restore_filename filename(缺省值：lower=-1，upper=1，没有对y进行缩放)2)svmscale.exe的用法第10章支持向量机 其中，-l：数据下限标记；lower：缩放后数据下限；-u：数据上限标记；upper：缩放后数据上限；-y：是否对目标值同时进行缩放；y_lower为下限值，y_upper为上限值；-s save_filename：表示将缩放的规则保存为文件save_filename；-r restore_filename：表示将缩放规则文件restore_filename载入后按此缩放；filename：待缩放的数据文件(要求满足前面所述的格式)。其中，-l：数据下限标记；lower：缩放后数据下限；-第10章支持向量机 缩放规则文件可以用文本浏览器打开，看到其格式为：lower upper；lval1 uval1；lval2 uval2其中的lower与upper与使用时所设置的lower与upper含义相同；index表示特征序号；lval为该特征对应转换后下限lower的特征值；uval为对应于转换后上限upper的特征值。数据集的缩放结果在此情况下通过DOS窗口输出，当然也可以通过DOS的文件重定向符号“”将结果另存为指定的文件。缩放规则文件可以用文本浏览器打开，看到其格式为：第10章支持向量机 使用实例：svmscale s train3.range train3train3.scale 表示采用缺省值(即对属性值缩放到-1,1的范围，对目标值不进行缩放)，对数据集 train3进行缩放操作，其结果缩放规则文件保存为train3.range，缩放集的缩放结果保存为 train3.scale。svmscale r train3.range test3test3.scale 表示载入缩放规则train3.range后按照其上下限对应的特征值和上下限值线性的地对数据集test3进行缩放，结果保存为test3.scale。使用实例：第10章支持向量机 3.svmtrain的用法的用法svmtrain实现对训练数据集的训练，获得SVM模型。指令格式：svmtrain options training_set_file model_file 其中，options(操作参数)