《神经网络》课件第10章

10.1统计学习理论的一般概念10.2最优化理论基础10.3支持向量机10.4支持向量机的实现

10.5

SVM在故障诊断中的应用

10.6小结

习题

在第3章，我们研究了由反向传播算法训练的多层感知器。在第8章，我们研究了另一类分层前馈网络，即径向基函数神经网络。这两种神经网络按它们自己的方式都可以称为通用函数逼近器。本章我们将讨论基于统计学习理论而发展的一种新的通用学习方法——支持向量机(SupportVectorMachine，SVM)。像多层感知器网络和径向基函数网络一样，支持向量机也能用于模式分类和非线性回归。10.1统计学习理论的一般概念

基于数据的机器学习是现代智能技术中的重要方面，它研究从观测数据(样本)出发寻找规律，并利用这些规律对未来数据或无法观测的数据进行预测。机器学习的过程就是构建学习机的过程。机器学习含有多种方法，如决策树、遗传算法、人工神经网络、隐Markov链(HMM)等。迄今为止，关于机器学习还没有一种被共同接受的理论框架，关于其实现方法大致可以分为下述三种。第一种是经典的(参数)统计估计方法，包括模式识别、神经网络等在内。现有机器学习方法共同的重要理论基础之一是统计学，参数方法正是基于传统统计学的。在这种方法中，参数的相关形式是已知的，练样本用来估计参数的值。这种方法存在很大的局限性：首先，它需要已知样本分布形式，这需要花费很大代价；其次，传统统计学研究的是样本数目趋于无穷大时的渐近理论，现有学习方法也多是基于此假设，但在实际问题中，样本数往往是有限的，因此一些理论上很优秀的学习方法在实际中的表现却可能不尽人意。第二种方法是经验非线性方法，如人工神经网络(ANN)。这种方法利用已知样本建立非线性模型，克服了传统参数估计方法的困难。但是，这种方法缺乏一种统一的数学理论。

第三种方法是20世纪60年代后期发展起来的统计学习理论(StatisticalLearningTheory，SLT)，它是一种专门研究有限样本情况下非参数估计问题的机器学习理论。与传统统计学相比，该理论针对有限样本统计问题建立了一套新的理论体系，在这种体系下的统计推理规则不仅考虑了对渐近性能的要求，而且追求在现有有限信息的条件下得到最优结果。统计学习理论是建立在一套较坚实的理论基础之上的，为解决有限样本学习问题提供了一个统一的框架。它能将很多现有方法纳入其中，有望帮助解决许多原来难以解决的问题(比如神经网络结构选择问题、局部极小点问题等)；同时，在这一理论基础上发展了一种新的通用学习方法——支持向量机，它已初步表现出很多优于已有方法的性能。一些学者认为，SLT和SVM正在成为继神经网络研究之后新的研究热点，并将推动机器学习理论和技术的重大发展。10.1.1机器学习问题的表示

机器学习的目的是根据给定的训练样本求取系统输入、输出之间依赖关系的估计，使它能够对系统行为做出尽可能准确的预测。机器学习问题的基本模型可以用图10-1表示。其中，系统S是我们研究的对象，它在给定输入x下得到一定的输出y，LM是我们所求的学习机，其输出为。图10-1机器学习的基本模型定义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,ω)就是一个学习机(LearningMachine，LM)。如果对于给定的输入x和ω的一个选择，其输出f(x,ω)总是相同的，则这个学习机f(x,ω)是确定性的(Deterministic)，否则称为不确定性的(Uncertainty)对于确定性学习机中的ω的一个特定选择，就称其为训练过的学习机(TrainedMachine)。

定义10.2

对于一个学习机，损失函数(LossFunction)

L(y,f(x,ω))表示用f(x,ω)对y进行预测而造成的损失。有三类基本的机器学习问题，即模式识别、函数逼近和概率密度估计，不同类型的学习问题有不同形式的损失函数。

(1)模式识别问题(这里仅讨论监督模式识别问题)：输出变量y是类别标号。在两类情况下，

y={0,1}或{-1,1}是二值函数，这时f(x,ω)称为指示函数(IndicatorFunction)，也称为判别函数。模式识别问题中损失函数的一般定义为(10-2)

(2)函数逼近问题(回归问题)：输出变量y是连续变量(这里假设为单值函数)，损失函数一般定义为

L(y,f(x,ω))=(y-f(x,ω))2(10-3)

即采用最小平方误差准则。

(3)概率密度估计问题：学习的目的是根据训练样本确定x的概率密度，设估计的密度函数为p(x,ω)，则损失函数一般定义为

L(p(x,ω))=－logp(x,ω)(10-4)10.1.2经验风险最小化

定义10.3

对于一个学习机，损失函数的期望：

R(ω)=∫L(y,f(x,ω))dP(x,y)(10-5)

称为期望风险(ExpectedRisk)或真实风险(ActualRisk)。而经验风险(EmpiricalRisk)

则是训练集上的平均误差，即：

(10-6)学习的目标在于使期望风险最小化，但是，期望风险R(ω)要依赖联合概率P(x,y)的信息，实际问题中无法计算。因此传统的学习方法中采用了所谓经验风险最小化(ERM)准则，即用样本定义经验风险如式(10-6)所示。作为对式(10-5)的估计，设计学习算法使它最小化。对于损失函数式(10-2)，经验风险就是训练样本错误率；对于式(10-3)的损失函数，经验风险就是平方训练误差；而采用式(10-4)，损失函数的ERM准则就等价于最大似然方法。事实上，神经网络与其他经典学习算法将ERM准则视为当然的出发点，并未研究其合理性、适用范围、可达到的近似质量等理论问题，只是直观上想当然的做法。如此做法存在以下几个问题：

(1)经验风险最小不等于期望风险最小，不能保证学习机的推广能力。算法或方法对未来输出进行正确预测的能力称为推广能力或泛化能力。

(2)从概率论中的大数定律可知，经验风险只有在样本数无穷大时才趋近于期望风险，需要非常多的样本才能保证学习机的性能。

(3)某些情况下，当经验风险过小时，推广能力反而下降，这就是神经网络中令人头疼的所谓过学习(Overfitting)问题。

(4)使经验风险最小的点与期望风险最小的点并非同一个点(如图10-2所示)。图10-2期望风险与经验风险之间的关系图在早期神经网络研究中，人们总是把注意力集中在如何使Remp更小，但很快发现，一味追求小的训练误差并不是总能达到好的预测效果。在某些情况下，训练误差过小反而会导致推广能力的下降，即出现过学习现象。之所以出现过学习现象，一是因为学习样本不充分，二是学习机设计不合理，这两个问题是相互关联的。假设我们有一组训练样本(x,y)，x分布在实数范围内，而y取值在[0,1]之间，那么不论这些样本是依据什么函数模型产生的，只要我们用一个函数f(x,α)来拟合这些样本，其中α是待定参数，总能够找到一个α使训练误差为零，如图10-3所示，但显然这个“最优函数”不能正确代表原来的函数模型。原因就是试图用一个复杂的模型来拟合有限的样本，结果导致丧失了推广能力。在神经网络中，如果对于有限的训练样本来说网络的学习能力过强，足以记住每一个训练样本，此时经验风险很快可以收敛到很小甚至零，但却根本无法保证它对新的样本能够得到好的预测。这就是有限样本下学习机的复杂性与推广性之间的矛盾。图10-3用三角函数拟合任意点的例子由此可看出，有限样本情况下：①经验风险最小并不一定意味着期望风险最小；②学习机的复杂性不但应与所研究的系统有关，而且要和有限数目的样本相适应。我们需要一种能够指导我们在小样本情况下建立有效的学习和推广方法的理论。10.1.3学习机的VC维与风险界

统计学习理论就是研究小样本统计估计和预测的理论。它从理论上较系统地研究了经验风险最小化原则成立的条件、有限样本下经验风险与期望风险的关系及如何利用这些理论找到新的学习原则和方法等问题。其主要涉及的内容包括：

(1)经验风险最小化准则下统计学习一致性的条件；

(2)在这些条件下关于统计学习方法推广性的界的结论；

(3)在这些界的基础上建立的小样本归纳推理准则；

(4)实现新的准则的实际方法(算法)。

其中，最有指导性的理论结果是推广性的界，与此相关的一个核心概念是VC维(VapnikChervonenkisDimension)。

经验风险Remp(ω)到期望风险R(ω)的一致收敛性理论包括收敛速度的解，它们基于称为VC维的重要参数。VC维是由学习机实现的分类函数族的容量或表示能力的测度。

在给出VC维定义之前，首先讨论线性分类问题。两类问题的分类通常用一个实值函数按照这样的方式操作：当f(x)≥0时，输入x∈X被标记为正类，否则被标记为负类。

考虑f(x)，x∈X是线性函数的情况，函数可以写

(10-7)其中w是一个n维权值向量，b是偏置，学习算法意味着一定要从数据中学习到这些参数。决策规则由sgn(f(x))给出，sgn(·)是一符号函数，即：这类假设的几何解释是，wTx+b=0定义的判别边界将输入空间X分为两半(见图10-4)。当n=2时，二维情况的判别边界为一直线；当n=3时，判别边界为一平面;n>3时，则判别边界为一超平面。超平面是维数为n-1的仿射子空间，它将输入空间分为两部分，这两部分对应输入中的两类。在图10-4中，当b的值变化时，超平面平行于自身移动。因此，如果想表达Rn中的所有可能超平面，包括n+1个可调参数的表达式是必要的。图10-4二维情况下的分类超平面定义10.4考虑两类分类问题，其中函数f(x,w)∈{0,1}，。对于给定的一组l个点，可以按所有2l个可能的方式进行标识；对于每一个可能的标识，如果在{f(w)}中总能取得一个函数，这个函数能够用来正确地区分这些标识，则称这l个点构成的点集能够被{f(w)}分隔(Shattered)。函数族{f(w)}的VC维定义为能够被{f(w)}分隔的训练点l的最大数目。若对任意数目的样本都有函数能够将它们分隔，则函数集的VC维是无限大的。用更熟悉的话说，分类函数集{f(w)}的VC维是能被机器学习的训练样本的最大数量，这种学习对于分类函数所有可能的二分标记是无错误的。VC维反映了函数集的学习能力，VC维越大则学习机越复杂(容量越大)。遗憾的是，目前尚没有通用的关于任意函数集VC维计算的理论，只对一些特殊的函数集知道其VC维。比如在n维实数空间中线性分类器和线性实函数的VC维是n+1。为了说明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。图10-5二维空间的VC维(a)三个点被有向直线分隔;(b)四个点不能被有向直线分隔注：在Rn中至少可以找到一组n+1个点能够被超平面分隔，但不是任意一组n+1个点都能够被超平面分隔。例如将所有点集中在一条直线上的情况就不能被分隔。我们不加证明地给出下述有用的定理。定理10.1

Rn中两个点集能够被一个超平面分隔的充分与必要条件是其凸包(包含该点集的最小凸集)的交集为空集。

定理10.2考虑Rn中l个点的集合，选择其中任意一点作为原点，那么l个点能够被超平面分隔的充分与必要条件是除了原点外其余点的位置向量是线性独立的。

统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的关系，即推广性的界。关于两类分类问题，结论是：对指示函数集中的所有函数(包括使经验风险最小的函数)，经验风险Remp(ω)和实际风险R(ω)之间满足如下关系。

定义10.5对于一个学习机，假定损失函数以概率1-η取值，其中0≤η≤1，那么下面的误差界成立：其中h是学习机的VC维，l是样本数目。不等式(10-8)的右边称为风险界(RiskBound)，它由两部分组成:第一项是经验风险(训练误差);另一部分称为置信范围，它和学习机的VC维及训练样本数有关，是随l/h增大而减小的函数。实际风险可以简单地表示为(10-9)它表明，在有限训练样本下，学习机器的VC维越高(复杂性越高),则置信范围越大，导致实际风险与经验风险之间可能的差别越大。这就是为什么会出现过学习现象的原因。机器学习过程不但要使经验风险最小，还要使VC维尽量小以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性。关于风险界，需要指出，推广性的界是对于最坏情况的结论，在很多情况下是较松的，尤其当VC维较高时更是如此。而且，这种界只在对同一类学习函数进行比较时有效，可以指导我们从函数集中选择最优的函数，在不同函数集之间比较却不一定成立。10.1.4结构风险最小化

下面将讨论结构风险最小化(StructuralRiskMinimiza

tion，SRM)问题。由学习机的风险界的构成看到，要控制学习机的实际风险，必须同时控制经验风险和置信范围。

因为VC维是整数，难以使其平滑变化，于是，结构风险最小化的思想是，将函数集构造为一个函数子集序列，使各个子集按照VC维的大小(亦即的大小)排列；在每个子集中寻

找最小经验风险，在子集间折中考虑经验风险和置信界限，取得实际风险最小。具体方法如下：

令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中的函数有界。此时机器学习的任务是在每个子集中寻找经验风险最小的同时，在子集间折中考虑经验风险和置信范围，使得实际风险最小，如图10-6所示。图10-6按VC维排序使函数嵌套的结构风险最小

SRM原理实际上提供了一种对于给定的样本数据在近似精度和模型近似函数复杂性之间折中的定量方法，即在近似函数集的结构中找出一个最佳子集，使实际风险确保上界达到极小。实现SRM原则可以有两种思路：一是在每个子集中求最小经验风险，然后选择使最小经验风险和置信范围之和最小的子集；二是设计函数集的某种结构使每个子集中都能取得最小的经验风险(如使训练误差为0)，然后只需选择适当的子集使置信范围最小，则这个子集中使经验风险最小的函数就是最优函数，支持向量机方法实际上就是这种思想的具体实现。例如神经网络的构造过程，函数集为(10-12)其中y是估计对象的实际输出，是神经网络的输出。若隐节点数可变，则函数集(10-12)式具有嵌套结构：(10-13)其中Sk={Q(z,w):满足第k种约束}中的神经网络都具有相同的结构，隐节点数为k，其近似函数为(10-14)已经证明，上述神经网络的VC维数取决于S函数的类型和权重的数目，并且在一般条件下是有界的(尽管它可能很大)。因此在选定的嵌套结构式(10-13)中，子集是按VC维数(即近似函数的复杂性)递增的顺序排列的，符合SRM归纳原理的要求。通常神经网络的设计，首先利用已有的先验知识或经验确定隐节点数目，从SRM原理的观点来看，这就是选定了一个子集Sk，该子集中所有的函数有一个确定不变的VC维数，即f(l/h)确定；随后通过训练确定最优权值，相当于最小化经验风险Remp(ω)。目前存在的问题是神经网络结构的确定大多是凭经验选取的，有一定的盲目性，无法确定泛化的置信界限，所以无法保证网络的泛化能力。即使经验误差很小，但可能推广或泛化能力很差。这就是神经网络中的过学习难题。10.2最优化理论基础

最优化理论是数学上的一个分支，它研究某些数学上定义的问题的最优解。根据特定的代价函数和约束的本质，可以得出许多类最优化问题，这些问题已经过深入研究并找到了很有效的解决方法。为了训练支持向量机，其中涉及到线性约束、二次目标函数等问题。10.2.1二次规划

凸性在最优化理论和方法的研究中起着重要作用。本节简要地介绍凸集和凸函数的基本概念和基本结果。

定义10.6(凸集)设集合，如果对任意x1,x2∈X，有：(10-15)则称X是凸集。这个定义表明，如果x1、x2属于凸集X，则连接x1和x2的线段仍属于X。

定义10.7(凸组合)设x1,…,xl∈Rn，若：其中，，αi≥0，i=1,…,l；则称x是x1,…,xl的一个凸组合。定理10.3(凸集的充要条件)集合是凸集的充分必要条件是X中任意若干点的任一凸组合仍属于X。现举例说明：

【例10-1】超平面是凸集，其中w∈Rn是非零向量，b∈R。

事实上，对任意的x1，x2∈H和α∈[0,1]，有：

wT(αx1+(1-α)x2)+b=0

故(αx1+(1-α)x2)∈H

【例10-2】闭半空间H-={x|wTx≤β}和H+={x|wTx≥β}为凸集。

注意到对任意x1，x2∈H-和α∈[0,1]，有：

wT(αx1+(1-α)x2)=αwTx1+(1-α)wTx2≤β

故(αx1+(1-α)x2)∈H-,其余类似。

定理10.4

若X1和X2是凸集，则交集X1∩X2也是凸集。

【例10-3】由有限个半闭空间的交组成的集合

叫多面集，即

其中wi是非零向量；βi是数。则该多面集是闭凸集。定义10.8(凸函数)设集合是非空凸集，f是定义在X上的函数。称函数f是X上的凸函数，如果对任意的x1，x2∈X，α∈(0,1),都有：

f(αx1+(1-α)x2)≤αf(x1)+(1-α)f(x2)

(10-17)

称f为X上的严格凸函数。如果对任意x1≠x2时,则式(10-17)中

的严格不等号成立。

凸函数的定义表示两点的线性插值大于函数值，其几何解释为，一个凸函数的图形总是位于相应弦的下方。如果凸函数是可微的，可以用下面的特征描述凸函数。定理10.5(凸函数的充要条件)设X是非空凸集，f(x)是X上的可微函数，则f(x)是凸函数的充要条件是，对任意的X中的点，都有

(10-18)

类似地，f(x)是严格凸函数的充要条件是，对于任意的X中的点，都有：

(10-19)

定理10.5表明了根据局部导数的线性近似是函数的低估。

定理10.6

考虑Rn上的二次函数：

(10-20)

其中G是n×n矩阵，r是n维向量，δ是实数。若G是半正定矩阵，则f(x)是Rn上的凸函数；若G是正定矩阵，则f(x)是Rn上的严格凸函数。定义10.9

一般的最优化问题描述如下：

这里f(x)称为目标函数，剩下的关系分别称为不等式约束和等式约束。目标函数的最优值称为最优化问题的值。

对目标函数和约束的本质的不同假设会产生不同的优化问题。

定义10.10对于目标函数，等式或不等式约束都是凸函数的最优化问题称为凸约束问题。对于目标函数是二次的，而约束都是线性函数下的最优化问题，称为二次规划问题。(10-21)定义10.11

可行区域是指目标函数的约束满足的区域，可以表示为

最优化问题的解是指存在一个点，使得不存在其他的点x∈Ω满足

。这个点也称为f(x)全局最小。如果满足，并且，满足，那么点称为f(x)局部最小。(10-22)

定理10.7考虑凸约束问题。设Ω是问题的可行域，

则：

(1)若问题有局部解，则是问题的全局解；

(2)问题的全局解组成的集合是凸集；

(3)若问题有局部解，f(x)是Ω上的严格凸函数，则

是问题的唯一全局解。

为了训练支持向量机(SVM)，只考虑线性约束、凸二次目标函数的问题，并且

Ω∈Rn，即考虑处理凸二次规划问题。下一小节将介绍拉格朗日(Lagrange)乘子技术及其扩展，并将其限制在二次规划问题之内。

10.2.2拉格朗日理论

解决约束非线性规划问题的方法大致有三类：直接处理约束、用线性规划逼近、转化成无约束问题。拉格朗日(Lagrange)乘子法是一种将约束问题变为无约束优化问题的方法，它揭示了条件极值的基本特性，也是最优准则法的理论基础。现在来寻求目标函数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)由于函数f(x,y)在(x0,y0)处取得极值，从而函数f(x,y(x))在x=x0处取得极值，必有：(10-25)由隐含数求导公式：将其代入(10-25)式有：(10-26)式(10-23)和式(10-26)就是函数z=f(x,y)在点(x0,y0)处取得极值的必要条件。记则上述条件可写成：(10-27)根据以上分析，引进函数：(10-28)此函数称为拉格朗日函数，其中λ叫做拉格朗日乘子。从式(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.12

给定一个在域上的最优化问题：(10-30)定义广义拉格朗日函数为(10-31)其中αi(i=1,…,k)、βi(i=1,…,m)为拉格朗日乘子。在约束问题的最优解中，包含了对应的拉格朗日乘子向量。如果能事先知道这个拉格朗日乘子，常常会减少求解原始约束问题的困难，这产生了求解约束问题的一个新途径——对偶方法。定义10.13

定义10.12中原问题的拉格朗日对偶问题如下：

这里θ(α,β)=infx∈ΩL(x,α,β)，目标函数在最优解的值称为问题的解。(我们使用“下确界inf”而不使用“极小值min”，原因是可能不存在极小值。)

下面根据弱对偶定理及两个推论，给出原问题和对偶问题的基本关系。(10-32)定理10.8令x∈Ω是定义10.12中原问题的一个可行解，而(α,β)是定义10.13中对偶问题的可行解,则f(x)≥θ(α,β)。

推论1

对偶问题的值的上界由原问题的值给出：

sup{θ(α,β)|α≥0}≤inf{f(x)|g(x)≤0,h(x)=0}

推论2

如果f(x′)=θ(α′,β′)，其中α′≥0，并且

g(x′)≤0,h(x′)=0，则x′和(α′,β′)分别是原问题和对偶问题的解。在这种情况下,i=1,…,k。

注：原问题的解和对偶问题的解的值之差称为对偶间隙。检测对偶间隙消失的方法是鞍点的出现。

定理10.9对于原问题，三元组(x′,α′,β′)是拉格朗日方程的鞍点，当且仅当其组成是原问题和对偶问题的最优解并且没有对偶间隙时，原问题和对偶问题的值关系为

f(x′)=θ(α′,β′)

现在提出强对偶定理，该定理保证对于讨论的最优化的原问题和对偶问题有相同的值。

定理10.10给定域Ω∈Rn上的最优化问题：

其中gi和hi是仿射函数，也就是对于某个矩阵A和向量b有：

其对偶间隙为零。

下面介绍Kuhn-Tucker定理，该定理给出了一般的最优化问题有最优解的条件。定理10.11

给定一个定义在凸域上的最优化问题：

其中f是可微且凸函数，gi和hi是仿射函数，一般地，一个点x′是最优点的充分必要条件是存在满足：其中L是广义拉格朗日函数。注：上式中的第三个关系称为KarushKuhnTucker互补条件(简称KKT条件)。它意味着对于积极约束(或有效约束)，有，但是对于非积极约束(或非有效约束)，有。10.2.3二次规划的对偶

使用拉格朗日理论理解凸最优化问题可以使用一个对偶表示替代原问题，该对偶问题通常比原问题更易处理。因为直接处理不等式约束是困难的。对偶问题通过引入又称为对偶变量的拉格朗日乘子来解。对偶方法来源于将对偶变量作为问题的基本未知量的思想。下面把对偶性应用到凸二次目标函数的一个重要而特殊的场合，这是对偶性的一种实际应用。定理10.12

考虑二次规划问题(10-33)其中G是一个n×n正定矩阵，，，。假设可行域非空，则这个问题可重写为：在x上的最小值是无约束的，最小值在x=-G-1(ATα+r)上得到。将该式代入原问题，得到其对偶形式：(10-34)注：二次规划的对偶形式是另一个二次规划问题，但是其约束更为简单。二次规划问题已成为支持向量机理论的标准技术，并且铺平了从最优化理论到算法技术的道路。进一步的问题是，KKT互补条件意味着只有积极约束有非零对偶变量，这就意味着一些最优化问题的实际变量数目要比全部训练集的规模小很多。后面将使用到的“支持向量”这个术语是指那些对偶变量非零的训练样本。10.3支持向量机

前面两节已经介绍了支持向量机的基础理论知识，而要使理论在实际中发挥作用，还要求它能够实现，这就是所谓的支持向量机(SupportVectorMachine，SVM)方法。这也是统计学习理论中最“年轻”的部分，其主要内容在1992~1995年间基本完成，目前仍处于不断发展阶段。因为它从某种意义上可以表示成类似神经网络的形式，所以支持向量机在起初也曾被称为支持向量网络。什么是SVM？这个问题首先应从模式识别开始讲解。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-7超平面的几何解释超平面具有以下性质：

(1)w与H正交(如图10-7所示)。

假设x1和x2是H上的两个向量，因为，则，向量必在H上，所以w与(x1-x2)垂直，即w与H正交。

(2)任意点x∈Rn到超平面的代数距离，即f(x)正比于x到H的代数距离。

证明：任意点x到超平面H的距离为(10-35)点s在超平面H上满足，用Lagrange乘子法解决约束最优问题。令非负变量，建立Lagrange函数：(10-36)J(s,λ)对s和λ求微分并置结果等于零，得：(10-37)令xi-si=ti，代入上式，得：(10-38)解得，于是：(10-39)对于点x，若f(x)>0，则x点为H的正侧；若f(x)<0，则x点为H的负侧。因此，点x到超平面的代数距离为(10-40)

(3)原点到超平面的代数距离

，即原点到H的代数距离与偏置b成正比。

证明：因为f(x)=wTx+b=b(x=0)，所以。

(4)若b>0，则H在原点的正侧；若b<0，则H在原点的负侧；若b=0，则f(x)=wTx，说明超平面H通过原点。10.3.2线性可分支持向量机

设两类问题训练样本集为S=(x1,y1),(x2,y2),…,(xl,yl)，其中xi∈Rn，yi={1,-1},i=1,…,l。问题线性可分是指，存在着超平面wTx+b=0，使得训练样本中的正类输入和负类输入分别位于该超平面的两侧,或者说存在着参数对(w,b),使得：yi=sgn(wTxi+b)i=1,…,l(10-41)

观察图10-8，存在许多决策超平面都可以将两类样本分开。我们应该选择哪一个呢？图10-8用超平面划分两类的情况假定划分直线的法向已经给定，如图10-9所示。直线H1是一条以w为法向量且能正确划分两类样本的直线。显然这样的直线并不唯一，如果平行地向右上方或左下方推移直线H1，直到碰到某类训练点,这样就得到了两条极端直线H2和H3，在直线H2和H3之间的平行直线都能正确划分两类。显然在H2和H3中间的那条直线H为最好。图10-9最优分类超平面以上给出了在已知法向量w1的情况下构造划分直线的方法。这样就把问题归结为寻求法向量w1的问题。

假如此时H表示为，因为其在中间，显然H2、H3可以分别表示为

(10-42)

两边同除以k，令，b1/k=b，则H表示为wTx+b=0，H2、H3分别变换为

wTx+b=-1,wTx+b=1(10-43)上述过程称为划分超平面的规范化过程。那么，此时两条直线H2和H3之间的间隔为(10-44)如前所述，对于适当的法向量，会有两条极端的直线，这两条直线之间有间隔，最优分类直线就应该是间隔最大的那个法向量所表示的超平面。即分类平面应该使两类之间的间隔最大(m最大)，同时满足下面的约束条件：(10-45)因此可以将求取最优平面问题转化为下列优化问题。考虑一个线性可分训练集S，寻找最优参数对(w,b)的过程，可转化为下列的约束优化问题：(10-46)这是一个二次归化问题，上式也可以写成如下形式：(10-47)现在考虑如何采用10.2节的策略将优化问题转化为相应的对偶问题。原始拉格朗日函数为

这里αi≥0是约束的拉格朗日乘子。因为都是不等式约束，所以这些乘子都是非负的。

通过对相应的w和b求偏导，可以找到相应的对偶形式：

(10-48)(10-49)将得到的关系式：(10-50)代入到原始拉格朗日函数，得到：(10-51)由优化理论中的对偶理论知，最小化式(10-48)等于最大化以式(10-48)约束的拉格朗日乘子为变量的式(10-51),即：(10-52)这是一个凸二次规划问题，有全局最优解。求解得到权重向量的最优解为

(10-53)同时因为这个优化问题的最优解必须满足如下KKT条件，条件要求最优解α′，w′,b′必须满足：

(10-54)任取αi≠0，可求得b。由上式可知，结果可得大部分αi为零。将αi不为零所对应的样本称为支持向量(SupportVector，SV)。因此在权重向量的表达式中，只有这些点包括在内，即式(10-53)变为(10-55)这样优化超平面就可以表示为(10-56)线性可分支持向量机说明如下：

(1)分类超平面由支持向量确定。也就是说，只需少量样本就可构成最优分类面，而且定量给出了每个训练点在所得解中的重要性。不是支持向量的点没有影响，在未退化的情况下，这些点轻微的扰动不影响解。

(2)对偶目标函数和最优分类面有一个显著的特性，就是数据仅出现在内积中。这为使用核技术在特征空间中找到并使用超平面成为可能。

(3)Vapnik证明线性分类器VC维满足：

h≤‖w‖2r2+1

(10-57)

式中r为包络训练样本的最小球半径。这说明，SVM在使训练样本被正确划分的同时，又最小化了分类面的VC维；SVM体现了结构风险最小化的思想，所以具有较好的泛化能力。10.3.3近似线性可分支持向量机

最大间隔分类器是一个很重要的概念，是分析和构造更加复杂的支持向量机的起点，但它在许多实际应用中并不完全使用。如果数据有噪声，输入空间(特征空间)一般不能线性可分。最大间隔分类器的主要问题使它总是完美地产生一个没有训练误差的一致假设。当训练集近似线性可分时，任何划分超平面的方法都必有错分，所以不能再要求训练点满足约束条件yi(wTxi+b)≥1,i=1,…,l。为此，对i个训练点(xi,yi)引入松弛变量，把约束条件放松为yi(wTxi+b)≥1-ζi,i=1,…,l。显然向量ζ=(ζ1,ζ2,…,ζl)T体现了训练集被错分的情况。可以采用

作为一种度量，描述训练集被错分的程度。这样，现在就有两个目标：仍希望间隔2/‖w‖尽可能大,同时希望错分程度

尽可能小。引进惩罚参数C把两个目标综合为一个目标，即极小化：上式的目标函数实质上由两部分组成:一部分是控制分类器的VC维(h)，另一部分是经验风险。实践中，惩罚系数C>0是对分类错误的惩罚，用于调整置信范围和经验误差间的均衡。C增大，则被压制，经验风险小。(10-58)

ζi是优化理论中的松弛变量，图10-10显示了两个误分点对应于标准超平面的间隔松弛变量。特别地，若xi没有错分，则ζi=0。图10-10分类问题中的松弛变量近似线性可分支持向量机的原优化问题：(10-59)同样，我们可以得到近似线性可分的对偶表示，即：(10-60)对比线性可分情况与近似线性可分情况的对偶表示，二者最大化的目标函数是相同的；不同之处在于，约束条件αi≥0被替换为条件更强的0≤αi≤C。10.3.4非线性可分支持向量机

超平面的分类能力毕竟有限，为此需要考虑分离曲面。令x为输入空间的向量，则通过事先确定的非线性映射函数：

f:x→f(x),Rn→F

(10-61)

把x映射到一个高维特征空间F，然后在F空间求最优分类超平面，如图10-11所示。

图10-11简化分类任务的特征映射可以注意到，在上面的支持向量机算法的对偶表示中，不论是寻优目标函数式(10-52)还是最优的超平面式(10-56)，都只涉及训练样本之间的内积运算。如果能够找到一个函数k使得k(xi,xj)=(xi)Tf(xj)，这样在特征空间F实际上只需进行内积运算；而这种内积运算是可以用原输入空间中的函数实现的，我们甚至没有必要知道非线性函数的具体形式。这实际上就是支持向量机的另一吸引人的地方，即核的表示方法。通过选择使用恰当的核函数来代替内积，可以隐式地将训练数据非线性映射到高维特征空间，以增强线性分类器的计算能力。

[例10-4]考虑二维输入空间的情况。设一非线性映射函数将输入空间的点映射到三维特征空间，非线性函数为：

任选输入空间两点和，这样该两点在特征空间的内积为：如定义核函数为输入空间两点内积的平方，则：因此，有：满足Mercer条件的常用核函数：

(1)多项式核函数

(2)径向基核函数

(3)Sigmoid核函数或对于非线性分类问题，首先将输入样本经非线性隐函数投影到某个特征空间。变换后在空间的分类平面为：寻找最优参数对的过程，可转化为下列的约束优化问题：(10-62)(10-63)类似线性情况，引入拉格朗日乘子后，优化方程为：所得分类超平面为：(10-64)(10-65)以上在解决非线性可分问题过程中，其特点是在原空间构造一个核函数使之等于变换后空间的内积运算，尽管通过非线性变换将样本数据映射到高维甚至无穷维空间，并在高维空间中构造最优分类超平面，但在求解最优化问题和计算分类平面时并不需要显式计算该非线性函数，甚至不需知道其具体形式，而只需计算函数。

[例10-5]若有5个数据点分别为：且第1、2和5为正类，第3和4为负类，即：定义多项式核函数为优化方程为利用二次规划算法，求得：因此，支持向量是。分类判别函数为其中，b的求解按照、或，并且在，可得：分类判别函数(见图10-12)为：图10-12分类曲线支持向量机算法的基本步骤如下：

(1)训练样本归一化；

(2)选择合适的核函数k(xi,xj)；

(3)确定核函数参数及惩罚系数C；

(4)执行训练算法，并求得拉格朗日系数αi，i=1,…,l；(5)得到分类判别函数。10.3.5支持向量回归机支持向量的方法应用于回归问题，仍保留了最大间隔算法的所有主要特征：非线性函数可以通过高维特征空间中的线性学习算法得到，同时系统的容量由与特征空间维数不相关的参数控制；同分类算法一样，学习算法要最小化一个凸函数，并且它的解是稀疏的。

1.ε不敏感损失函数

若以鲁棒性为设计目标，对于任何鲁棒性的数值度量必须考虑到由于微小噪声的影响而可能产生最大性能退化。这需要定义一个损失函数，它可以忽略真实值某个上下范围内的误差,可以描述为(10-66)其中ε是指定的参数，损失函数Lε(d,y)称为ε不敏感损失函数(ε-insensitiveLossFunction)。如果估计器输出y和期望输出d的偏差的绝对值小于ε，则损失函数等于零，否则它等于偏差绝对值减去ε。图10-13说明了Lε(d,y)和误差d-y的依赖关系。探讨ε不敏感损失函数的另一个动机是如同分类SVM一样，它可以确保对偶变量的稀疏性。使用训练点的一个小的子集表示解可带来很大的计算优势，同时确保全局最小解的存在和可靠泛化界的优化。图10-13ε不敏感损失函数

2.非线性SVR考虑非线性回归模型，标量d对向量x的依赖可描述为

d=f(x)+v(10-67)其中f(·)是自变量的一个确定性函数，加性噪声v统计独立于输入向量x，二者的统计特性是未知的。我们将所有可用的信息描述成一组训练数据，其中xi是输入向量x的一个样本值，di是模型输出d的相应值，l为样本个数。如果在线性函数集合f(x)=(w·f(x))+b中估计回归函数，求解问题的经验风险为其中是高维特征空间的点。可以引入两组非负的松弛变量和描述式(10-66)定义的e不敏感损失函数，有：(10-68)(10-69)

ε-SVR就是在式(10-69)约束下，求下式的最小化代价泛函数：其中，惩罚因子C是事先给定的参数。为了构造相应的对偶问题，定义Lagrange乘子ai、，上面的凸二次规划问题可转化为求解下式的新形式：(10-71)式中是满足Mercer定理的内积核。注意同模式识别问题的解一样，Lagrange乘子中仅有一部分不为零，对应的数据点定义为支持向量(SupportVector，SV)。e和两者都必须由用户选择，和控制的估计函数为：(10-72)

e和C选择的原则方法一直是一个未解决的研究领域。从概念上讲，e和C选择的提出和模式分类中参数C的选择具有同样的复杂性。然而，在实际应用中回归的复杂性控制是一个更困难的问题，这是由于，①参数e和C必须同时调整；②回归本质上比模式分类更困难。10.4支持向量机的实现

支持向量机所涉及到的数学知识是比较难的，自己编程实现该算法难度就更大了。但是现在的网络资源非常发达，而且国际上的科学研究者把他们的研究成果已经放在网络上，免费提供给用于研究目的，这样方便大多数的研究者，不必要花费大量的时间理解SVM算法的深奥数学原理和计算机程序设计。目前有关SVM计算的相关软件有很多，如LIBSVM、mySVM、SVMLight等，这些软件大部分的免费下载地址和简单介绍都可以在/上获得。10.4.1

LIBSVM软件包简介

LIBSVM是台湾大学林智仁博士开发设计的一个简单、易于使用和快速有效地SVM模式识别与回归的软件包。他不仅提供了LIBSVM的C＋＋语言的算法源代码，还提供了Python、Java、MATLAB、LabVIEW等语言的接口，可以方便的在Windows或UNIX平台下使用，也便于人们根据自己的需要进行改进(例如设计使用符合自己特定问题需要并且在进行模型参数选择时可以绘制出交叉验证精度的等高线图)。另外还提供了WINDOWS平台下的可视化操作工具SVM-toy。LIBSVM软件包可以在.tw/~cjlin/免费获得。

LIBSVM可以解决分类问题(包括C-SVC、n-SVC)、回归问题(包括e-SVR、n-SVR)以及分布估计(one-class-SVM)等问题，提供了线性、多项式、径向基和S形函数四种常用的核函数供选择。SVM用于模式识别或回归时，SVM方法及其参数、核函数及其参数的选择，目前国际上还没有形成一个统一的模式，也就是说最优SVM算法、参数选择还只能是凭借经验、实验对比、大范围的搜寻或者利用软件包提供的交互检验功能进行寻优。10.4.2

LIBSVM使用方法

LIBSVM在给出源代码的同时还提供了Windows操作系统下的可执行文件，包括：进行SVM训练的svmtrain.exe；根据已获得的SVM模型对数据集进行预测的svmpredict.exe；以及对训练数据与测试数据进行简单缩放操作的svmscale.exe。它们都可以直接在DOS环境中使用。如果下载的包中只有C++的源代码，则也可以自己在VC等软件上编译生成可执行文件。

LIBSVM使用的一般步骤是：⑴按照LIBSVM软件包所要求的格式准备数据集；⑵对数据进行简单的缩放操作；⑶考虑选用RBF核函数；⑷采用交叉验证选择最佳参数与；⑸采用最佳参数与对整个训练集进行训练获取SVM模型；⑹利用获取的模型进行测试与预测。

1)LIBSVM使用的数据格式该软件使用的训练数据和检验数据文件格式如下：<label><index1>:<value1><index2>:<value2>…其中<label>是训练数据集的目标值，对于分类，它是标识某类的整数(支持多个类)；对于回归，是任意实数。<index>是以1开始的整数，可以是不连续的；<value>为实数，也就是我们常说的特征值或自变量。检验数据文件中的label只用于计算准确度或误差，如果它是未知的，只需用一个数填写这一栏，也可以空着不填。在程序包中，还包括有一个训练数据实例：heart_scale，方便参考数据文件格式以及练习使用软件。

2)

svmscale.exe的用法对数据集进行缩放，其目的是：⑴避免一些特征值范围过大而另一些特征值范围过小；⑵避免在训练时为了计算核函数而计算内积的时候引起数值计算的困难，通常将数据缩放到[-1,1]或者是[0,1]之间。指令格式：svmscale[-llower][-uupper][-yy_lower

y_upper]

[-ssave_filename][-rrestore_filename]

filename

(缺省值：lower=-1，upper=1，没有对y进行缩放)其中，-l：数据下限标记；lower：缩放后数据下限；-u：数据上限标记；upper：缩放后数据上限；-y：是否对目标值同时进行缩放；y_lower为下限值，y_upper为上限值；-ssave_filename：表示将缩放的规则保存为文件save_filename；-rrestore_filename：表示将缩放规则文件restore_filename载入后按此缩放；filename：待缩放的数据文件(要求满足前面所述的格式)。缩放规则文件可以用文本浏览器打开，看到其格式为：lowerupper；lval1uval1；lval2uval2其中的lower与upper与使用时所设置的lower与upper含义相同；index表示特征序号；lval为该特征对应转换后下限lower的特征值；uval为对应于转换后上限upper的特征值。数据集的缩放结果在此情况下通过DOS窗口输出，当然也可以通过DOS的文件重定向符号“>”将结果另存为指定的文件。使用实例：⑴svmscale–strain3.rangetrain3>train3.scale表示采用缺省值(即对属性值缩放到[-1,1]的范围，对目标值不进行缩放)，对数据集train3进行缩放操作，其结果缩放规则文件保存为train3.range，缩放集的缩放结果保存为train3.scale。⑵svmscale–rtrain3.rangetest3>test3.scale表示载入缩放规则train3.range后按照其上下限对应的特征值和上下限值线性的地对数据集test3进行缩放，结果保存为test3.scale。

3.

svmtrain的用法

svmtrain实现对训练数据集的训练，获得SVM模型。指令格式：svmtrain[options]training_set_file[model_file]其中，options(操作参数)：可用的选项即表示的涵义如下所示。

(1)-ssvm类型：设置SVM类型，默认值为0，可选类型有：

0－C-SVC

1－n-SVC

2－one-class-SVM

3－e-SVR

4－n-SVR

(2)-t核函数类型：设置核函数类型，默认值为2，可选类型有：

0－线性核

1－多项式核

2－RBF核

3－sigmoid核

(3)-ccost：设置C-SVC、e-SVR、n-SVR中的惩罚系数C，默认值为1；

(4)-nn：设置n-SVC、one-class-SVM与n-SVR中参数n，默认值0.5；

(5)-pe：设置n-SVR的损失函数中的e，默认值为0.1；

(6)-mcachesize：设置cache内存大小，以MB为单位，默认值为40；

(7)-ee：设置终止准则中的可容忍偏差，默认值为0.001；

(8)-hshrinking：是否使用启发式，可选值为0或1，默认值为1；

(9)-b概率估计：是否计算SVC或SVR的概率估计，可选值0或1，默认0；

(10)-wiweight：对各类样本的惩罚系数C加权，默认值为1；

(11)-vn：n折交叉验证模式。

操作参数-v随机地将数据剖分为n部分并计算交叉检验准确度和均方根误差。以上这些参数设置可以按照SVM的类型和核函数所支持的参数进行任意组合，如果设置的参数在函数或SVM类型中没有也不会产生影响，程序不会接受该参数；如果应有的参数设置不正确，参数将采用默认值。training-set-file是要进行训练的数据集；model-file是训练结束后产生的模型文件，该参数如果不设置将采用默认的文件名，也可以设置成自己惯用的文件名。使用实例：svmtraintrain3.scaletrain3.model表示训练train3.scale，将模型保存为文件train3.model，并在dos窗口中输出如下结果：

optimizationfinished,＃iter=1756

nu=0.464223

obj=-551.002342,rho=-0.337784

nSV=604,nBSV=557

TotalnSV=604其中，＃iter为迭代次数；nu与前面的操作参数－nn相同；obj为SVM文件转换的二次规划求解得到的最小值；rho为判决函数的常数项b；nSV为支持向量个数；nBSV为边界上的支持向量个数；TotalnSV为支持向量总个数。训练后的模型保存为文件train3.model，用记事本等文本浏览器打开可以看到其内容。

4.svmpredict的用法

svmpredict根据训练获得的模型，对数据集合进行预测。指令格式：svmpredict[options]test-filemodel-fileoutput-file

options(操作参数)bprobability-estimates：是否需要进行概率估计预测，可选值为0或者1，默认值为0。

model-file是由svmtrain产生的模型文件；test-file是要进行预测的数据文件；output-file是svmpredict的输出文件，表示预测的结果值。svmpredict没有其它的选项。

应用LIBSVM，需要依次运行svmscale.exe，svmtrain.exe，svmpredict.exe等命令，其实更简单的方法是使用easy.py，可以很方便地从MATLAB中用dos或system命令调用。10.4.3SVM在MATLAB中的实现

SVM的研究方兴未艾，有关SVM计算的软件有很多，其中STPRtool是另外一种应用广泛的软件包。现举例说明其用法。

Riply数据集是一个用来检验分类算法性能的标准数据集，该数据集分为两类，训练样本数为250，测试样本数为1000。由于测试样本数远大于训练样本数，因而测试结果可以反映算法的泛化性能。具体程序如下(本例M文件见光盘中的FLch10eg1)，其中核函数选用径向基核函数(RBF)，核参数s=1，惩罚因子C=10。图10-14表示训练结果，“×”为正类，“○”为负类，大圆圈的样本为支持向量。图10-14SVM对训练集分类结果trn=load(’riply_trn’);

%loadtrainingdataoptions.ker=’rbf’;

%useRBFkerneloptions.arg=1;

%kernelargumentoptions.C=10;

%regularizationconstantmodel=smo(trn,options);

%trainSVMclassifierppatterns(trn);%visualizationpsvm(model);tst=load(’riply_tst’);%loadtestingdataypred=svmclass(tst.X,model);%classifydata10.5

SVM在故障诊断中的应用

系统的故障诊断某种程度上可以理解为模式识别过程。设被测对象全部可能发生的状态(正常和故障状态)组成状态空间S，它的可测量特征的取值范围的全体构成特征空间Y。当系统处于某一状态s时，系统具有确定的特征y，即存在映射g:S→Y；反之，一定的特征也对应确定的状态，即存在映射f:Y→S。状态空间与特征空间的关系可用图10-15表示。

图10-15状态空间与特征空间的关系故障诊断的目的在于根据可测量的特征向量来判断系统处于何种状态，也就是找出映射f。若系统可能发生的状态是有限的，例如可能发生n故障，这里假设系统正常状态为s0,各个故障状态为s1,s2,…,sn。当系统处于状态si时，对应的可测量特征向量为yi=(yi1,yi2,…,yim)T。故障诊断过程就是由特