support-vecttor networks课件

1、支持向量网络Corinna Cortes and Vladimir VapnikAT&T Labs-Research, USA摘要. 支持向量网络是一种针对两类问题的新学习机器.它的实现基于以下思想:将输入向量非线性地映射到一个很高维的特征空间.并在该特征空间中构造一个线性决策平面.该决策平面的特殊性质保证了学习机器具有很好的推广能力.支持向量网络的思想已在完全可分的训练数据集上得以实现,这里我们将它扩展到不完全可分的训练数据集.利用多项式输入变换的支持向量网络被证明具有很好的推广能力.我们以光学字体识别为实验将支持向量网络和其他不同的经典学习算法进行了性能比较.关键词：模式识别, 有

2、效的学习算法, 神经网路, 径向基函数分类器, 多项式分类器1 介绍60多年前,R.A.Fisher7提出了模式识别领域的第一个算法.该模型考虑n维向量x正态分布N(m1,1)和N(m2,2), m1 和m2为各个分布的均值向量, 1和2为各个分布的协方差矩阵,并给出最优解为如下二次决策函数: . (1)当1 = 2 = 时该二次决策函数(1)退化为一个线性函数: . (2)评估二次决策函数需要确定n(n+3)/2个自由参数,而评估线性函数只需要n个自由参数.在观测数目较小(小于10n2)的情况下评估O(n2)个参数是不可靠的.Fisher因此提出以下建议,在1 2 时也采用线性判别函数(2)

3、,其中的采用如下形式: , (3)这里是某个常数.Fisher也对两个非正态分布的线性决策函数给出了建议.因此模式识别的算法最开始是和构建线性决策平面相关联的.1962年,Rosenblatt11提出了一种不同的学习机器:感知器(或神经网络).感知器由相关联的神经元构成,每个神经元实现一个分类超平面,因此整个感知器完成了一个分段线性分类平面.如图1.Fig 1: A simple feed-forward perceptron with 8 input units, 2 layers of hidden units, and 1 output unit. The gray-shading of

4、 the Vector entries reflects their numeric value.Rosenblatt没有提出通过调整网络的所有权值来最小化向量集上误差的算法,而提出了一种自适应仅仅改变输出节点上的权值的方法.由于其他权值都是固定的,输入向量被非线性地映射到最后一层节点的特征空间Z.在该空间的线性决策函数如下: (4)通过调整第i个节点到输出节点的权值来最小化定义在训练集上的某种误差.Rosenblatt的方法,再次将构建决策规则归结为构造某个空间的线性超平面.1986年,针对模式识别问题出现了通过调整神经网络所有权值来局部最小化向量集上误差的算法12,13,10,8,即后向传

5、播算法.算法对神经网络的数学模型有微小的改动.至此,神经网络实现了分段线性决策函数.本文提出了一种全新的学习机器,支持向量网络.它基于以下思想:通过事先选择的非线性映射将输入向量映射到一个高维特征空间Z.在空间Z里构建一个线性决策面,该决策面的一些性质保证支持向量网络具有好的推广能力.例如:要构造一个与二阶多项式对应的决策面,我们可以构造一个特征空间Z,它有如下的N=n(n+3)/2个坐标: , n coordinates, , n coordinates, , n(n-1)/2 coordinates ,其中,x = .分类超平面便是在该空间中构造的.以上方法存在两个问题:一个是概念上的,另

6、一个是技术上的.(1)概念上的问题:怎样找到一个推广性很好的分类超平面?特征空间的维数将会很高,能将数据分开的超平面不一定都具有很好的推广性.(2)技术上的问题:怎样在计算上处理如此高维的空间?要在一个200维的空间中构建一个4或5阶的多项式,需要构造一个上十亿的特征空间.概念上的问题在1965年14通过完全可分情况下的最优超平面得以解决.最优超平面是指使两类向量具有最大间隔的线性决策函数,如图2所示.可以发现,构造最优超平面只需考虑训练集中决定分类隔间的少量数据,即所谓的支持向量.如果训练集被最优超平面完全无错地分开,则一个测试样例被错判的期望概率以支持向量的期望数目与训练集向量数目比值为上

7、界,即: . (5)注意,这个界与分类空间的维数无关.并且由此可知,如果支持向量的个数相对与整个训练集很小,则构建出来的分类超平面将具有很好的推广性,即便是在一个无限维空间.第5节中,通过实际问题我们验证了比值(5)能够小到0.03而相应的最优超平面在一个十亿的特征空间依然具有很好的推广能力.Fig 2. An example of a separable problem in a 2 dimensional space. The support vectors, marked with grey squares, define the margin of largest separation

8、 between the two classes.令为特征空间里的最优超平面.我们将看到,特征空间中最优超平面的权值可以写成支持向量的某个线性组合 . (6)从而特征空间里的线性决策函数I(z)为如下形式: , (7)其中表示支持向量和向量在特征空间里的内积.因此,该决策函数可以通过一个两层的网络来描述.如图3.尽管最优超平面保证了好的推广性,但如何处理高维特征空间这个技术上的问题依然存在.1992年,在文献3中证明构造决策函数的步骤可以交换顺序:不必先将输入向量通过某种非线性变换映射到特征空间再与特征空间中的支持向量做内积；而可以先在输入空间通过内积或者某种别的距离进行比较,再对比较的值进行

9、非线性变化.如图4.这就允许我们构造足够好的分类决策面,比如任意精度的多项式决策面.称这种类型的学习机器为支持向量网络.支持向量网络的技术首先针对能够完全无错地分开的数据集.本文我们将支持向量网络推广到不能完全无错分类的数据集.通过该扩展,作为一种全新的学习机器的支持向量网络将和神经网络一样的强大和通用.第5节将展示它在256维的高维空间中针对高达7阶的多项式决策面的推广性.并将它和其他经典的算法比如线性分类器、k近邻分类器和神经网络做了性能上的比较.第2、3、4节着重引出算法并讨论了算法的一些性质.算法的一些重要细节参见附录.Fig 3. Classification by a suppor

10、t-vector network of an unknown pattern is conceptually done by first transforming the pattern into some high-dimensional feature space. An optimal hyperplane constructed in this feature space determines the output. The similarity to a two-layer perceptron can be seen by comparison to Fig 1.Fig 4. Cl

11、assification of an unknown pattern by a support-vector network. The pattern is in input space compared to support vectors. The resulting values are non-linearly transformed. A linear function of these transformed values determines the output of the classifier.2 最优超平面本节回顾文献14中针对能被完全无错分开的训练数据的最优超平面方法.

12、下一节介绍软间隔的概念,用来处理训练集不完全可分情况下的学习问题.2.1 最优超平面算法训练样本集 , (8)是线性可分的如果存在向量w和标量b使得以下不等式 (9)对(8)中所有元素都成立.我们将不等式(9)写成如下形式: (10)最优超平面 (11)是指将训练数据以最大间隔分开的那个平面:它决定了向量w/|w|的方向,该方向上两不同类别训练向量间的距离最大.可回顾图2.记这个距离为,它由下式给定: . (12)最优超平面(w0,b0)便是使得距离(12)取最大值的那组参数.根据(12)和(10)可得 . (13)这表明,最优超平面就是满足条件(10)并且使得最小化的超平面.因此,构建一个最

13、有超平面其实就是一个二次规划问题.满足的向量即为支持向量.附录中将证明决定最优超平面的向量可以写成所有训练向量的一个线性组合: , (14)其中0.由于只有支持向量处的系数>0(参考附录),表达式(14)只是的一种简写形式.要求出参数向量:,需要求解以下二次规划问题: (15)其中=(),且满足限制: 0, (16) Y = 0, (17) = (1,.,1)是维的单位向量, 是维的类标签向量,是×的对称矩阵其元素 . (18)不等式(16)表示非负象限.因此,问题变为在非负象限中最大化二次式(15),并服从约束条件(17).当训练数据可完全无错地分开时,在附录A中我们证明了在

14、最大泛函(15)、和式(13)的最大间隔之间有以下关系: . (19)如果存在某个和某个较大的常数使得不等式 (20)成立,则所有把训练集(8)分开的超平面其间隔都满足.如果训练集(8)不能被超平面完全分开,则两个类的样本间的间隔变的任意小,使得泛函的值变得任意大.因此,要在约束条件(16)和(17)下最大化泛函(15),要么能求得最大值(这种情况需要构造最大间隔为的最优超平面),要么求出超过某个给定的常数的最大值(这种情况下不可能以大于的间隔分开训练数据).在约束条件(16)和(17)下最大化泛函(15)的问题如下方法可有效地解决.将训练数据集划分为几部分,使每部分占有合理的少量数据.先求解

15、由第一部分训练数据决定的二次规划问题.对于该问题,会有两个结果:其一,这部分数据不能被任何超平面分开(这种情况下整个数据集都不能被任何超平面分开);其二,找到了能分开这部分数据的最优超平面.假设对第一部分数据泛函(15)的最大化时对应的向量为.该向量某些维上取值为零,它们是和该部分数据中非支持向量相关的.将第一部分数据中的支持向量和第二部分中不满足约束条件(10)的向量组成一个新的训练集,其中w将由决定.对于这个新的训练集,构建泛函并假设其在最大化.持续递增地构造出覆盖全部训练数据的解向量,此时,或者会发现无法找到将整个训练集无错分开的超平面,或者构建出了整个训练集的最优超平面,且=.值得注意

16、的是,在这个过程中泛函的值是单调递增的,因为越来越多的训练向量被考虑到优化过程中来,使得两类样本之间的间隔越来越小.3 软间隔超平面考虑训练数据不能完全无错地分开的情况,此时,我们希望能以最小的错误将训练集分开.为形式化进行表示,引入非负变量.现在,最小化泛函 (21)参数>0,约束条件为, (22). (23)对于足够小的>0,泛函(21)描述了训练错误数.最小化泛函(21)可获得被错分样本的某个最小子集:.如果不考虑这些样本,其他的样本组成的训练集可以被无错地分开.可以构造一个将其他样本组成的训练集完全分开的最优超平面.该思想形式化表述如下:最小化泛函 (24)约束条件为(22

17、)和(23),其中F(u)是一个单调凸函数,C是常数.对于足够大的C和足够小的,在约束条件(22)和(23)下最大化泛函(24)的向量w0和常数b0决定了最优超平面,而该超平面使得训练集上错误数最小并将未分错部分以最大间隔分开.然而,在训练集上构建一个超平面使得错误数最小一般说来是NP完全的.为避免出现NP完全性,我们考虑=1的情况(使得最优问题(15)具有唯一解的最小).此时,泛函(24)描述了如何构建一个分类超平面使得训练错误的偏差之和最小且被正确分类的样本的间隔最大的问题(对于足够大的C).如果整个训练集都能被正确地分开,则此时构建出来的超平面就是最优间隔超平面.相比于<1的情况,

18、=1的情况存在有效的方法寻找(24)的解.称这个解为软间隔超平面.在附录A我们考虑在约束条件(22)和(23)下最小化泛函 (25)其中F(u)是个单调凸函数且满足F(0)=0.为了表述的简洁,本节只考虑F(u)=u2的情况.此时,最优化问题依然是个二次规划问题.附录A中,我们证明了最优超平面算法里的向量w可以写成支持向量的一个线性组合:.为求向量,需要求解以下双重二次规划问题,最大化泛函 (26)约束条件为 , (27) , (28) , (29)其中、和与构建最优超平面的最优化问题中的相同,是一个标量,(29)描述了坐标取值范围.根据(29),可以发现,泛函(26)中所允许的最小的应该为.

19、因此,为求解软间隔分类器我们求解出在约束条件0和(27)下使泛函 (30)最大化的向量.这个问题不同于在泛函(30)中增加这一项来构造最优间隔分类器的问题.由于多了这一项,构造软件间隔分类器的问题对于任何数据集都是唯一的且有解的. 因为这一项的存在,泛函(30)不再是二次的.在约束条件0和(27)下最大化泛函(30)属于凸规划问题的范畴.因此,要构建软间隔分类器,我们可以在维的参数空间解凸规划问题,也可以在+1维的(,)参数空间解二次规划问题.在我们的实验里,采用的是后者.4 特征空间中内积的回旋方法前文描述了在输入空间构建分类超平面的算法.为建立特征空间里的超平面,首先要通过选择一个N维向量

20、函数:将n维输入向量x映射成N维特征向量.于是,一个N维的线性分类器(w,b)的构造将针对这些被转换的向量:, .对一个未知向量x进行分类,需要先将它转换到分类空间(),再考虑以下函数的符号 . (31)根据软间隔分类方法的性质,向量w可写成特征空间中支持向量的线性组合.即 . (32)由于内积的线性特点,分类函数(31)对于一个未知向量x的判别仅依赖于内积运算: . (33)构造支持向量网络的思想来自于对Hilbert空间2中内积一般形式的考虑: . (34)根据Hilbert-Schmidt理论6,任意的对称函数都能展开成以下形式 , (35)其中为特征值,为特征函数,由核的如下积分式定义

21、:.保证(34)描述了在某个特征空间中的一个内积的一个充分条件是展开式(35)中的所有特征值都为正数.要保证所有的这些系数都为正,充分必要条件是,对使得成立的所有g,条件成立(Mersers定理).因此,满足Mersers定理的函数就可以用作内积.Aizerman, Braverman和Rozonoer1提出了一种特征空间里内积的回旋形式 , (36)称之为势函数.事实上,特征空间中内积的回旋可以用满足Mersers条件的任何函数,特别地,要在n维输入空间构造d次多项式分类器,我们可以利用以下函数 . (37)使用不同的内积我们以任意类型的决策平面来构造不同的学习机器3.这些学习机器的决策平面

22、具有如下形式,其中是支持向量在输入空间的像,是支持向量在特征空间的权值.求解支持向量和它们的权值可采用和原来的最优间隔分类器或者软间隔分类器类似的方法.唯一的不同点是矩阵D(在(18)中定义)的元素变为, .5 支持向量网络的一般特征5.1 支持向量网络建立的决策规则是有效的要构建支持向量网络的决策规则,需要求解如下二次优化问题:,约束条件为:,其中矩阵,.由训练数据集决定, 是决定内积回旋的函数.这个最优化问题可通过训练数据决定的一个中间优化问题来求解,这个解是由支持向量组成的.相关技术在第3节已经论述过.求得的最优决策函数是唯一的.每一个最优化问题都有其相应的标准解法.5.2 支持向量网络

23、是一种通用的学习机器通过选择不同的核函数来内积回旋,可以实现不同的支持向量网络.下一节我们将考虑多项式决策面的支持向量网络.为实现多项式的不同阶数,选用如下核函数用于内积回旋.具有如下决策函数形式的径向基函数的学习机器可通过以下核函数实现.此时,支持向量机将会构建出近似函数的中心以及相应的权值. 也可以结合已有问题的先验知识来构建一个特殊的回旋函数.因此,支持向量网络是非常通用的一种学习机器,利用不同的核函数就能实现不同的决策函数集合.5.3 支持向量网络与推广能力的控制控制一个学习机器的推广能力需要控制两个因素:训练集上的错误率和学习机器的容量VC维14.测试集上的误差概率存在这样一个界:不

24、等式 (38)以概率1-成立.界(38)中的置信区间决定于学习机器的VC维,训练集数据个数和的值.(38)中的两个因素形成了一对矛盾:学习机器的VC维越小,置信区间越小,但是错误的频率越大.结构风险最小化原则用来解决这个问题:对于给定的数据集,找到一个使置信区间与错误频率之和最小的解.结构风险最小化原则的一个特例是奥科玛-剃刀原则:保持第一项为零最小化第二项.我们知道,对于阈值b固定的线性指示函数其VC维等于输入空间的维数.然而,对于函数集(权值有界)其VC维可小于输入空间的维数且依赖于.可以看到,最优间隔分类器方法运用了奥科玛-剃刀原则.将(38)的第一项保持为零(通过满足不等式(9),再最

25、小化第二项(通过最小化函数).这样的最小化避免了过拟合问题.然而,即使是在训练数据完全可分的情况下,也可以通过以训练集上的错误为代价来最小化(38)中的置信区间那一项进一步获得更好的推广性.在软间隔分类方法中,这可以通过选择恰当的参数C来实现.在支持向量网络算法中,可以通过调节参数C来控制决策规则的复杂度和错误频率这一对矛盾,即使是对于训练集无法完全分开这种一般情况.因此,支持向量网络能够控制影像学习机器推广能力的两个因素.6 实验分析为验证支持向量网络方法,我们进行了两组实验.(1)构建了平面上的人工数据集并用2阶多项式决策面进行了实验;(2)针对数字识别这个实际问题进行了实验.6.1 平面

26、上的实验利用核函数 (39)其中d=2,构建平面上不同样本集的决策规则.实验结果证实了该算法的强大.图5给出了一些例子.黑白两种子弹代表两类.在图中,双圆圈表示支持向量,十字表示错分的向量.可以发现,支持向量的个数相对于训练样本的个数是很少的.Fig 5. Examples of the dot-product (39) with d=2. Support patterns are indicated with double circles, errors with a cross.Fig 6. Examples of patterns with labels from the US Post

27、al Service digit database.6.2 数字识别实验针对位图数字识别构建支持向量网络的实验用到了一大一小两个数据库.小的是美国邮政服务器上的数据库,包含7300个训练样本和2000个测试样本.数据的分辨率是16×16像素,图6给出了一些例子.在这个数据库上,我们研究不同阶数的多项式的实验结果.大的数据库包含60,000训练样本和10,000测试样本,是NIST上训练集和测试集50-50的混合.28×28像素的分辨率导致输入维数是784.在这个数据上我们只构建了一个四阶的多项式分类器.该分类器的性能和其他不同学习机器在基准学习4上进行了比较.实验中共构建了

28、十个分类器,每个类别一个.每个超平面使用相同的内积和数据预处理过程.对未知样本的判别结果为十个分类器中输出结果最大的一个.Table 1. Performance of various classifiers collected from publications and own experiments. For reference see text.Table 2. Results obtained for dot products of polynomials of various degree. The number “support vectors”is a mean value pe

29、r classifier.Fig 7. Labeled examples of errors on the training set for the 2nd degree polynomial support-vector classifier.6.2.1 美国邮政服务数据库上的实验美国邮政服务数据库的数据是从现实生活中的邮政编码采集的,很多研究者在此之上做过实验.表1列出了公共实验和我们的实验中不同分类器的性能.人工表现的结果由J.Bromley和E.Sackinger给出5.CART的结果是贝尔实验室的Daryl Pregibon和Michael D.Riley以及NJ的Murray Hi

30、ll完成的.C4.5的结果是C.Cortes得到的,最优两层神经网络的结果是B.Scholkopf得到的.专门为此用途的五层神经网络结构(LeNet1)结果是由Y.LeCun等人取得的9.本实验我们利用预处理技术(居中,倾斜,平滑)来合并实验中相关变量的知识.数据平滑作为支持向量网络的一项预处理技术在文献3中进行了研究.本实验与文献3一致,选择=0.75的平滑高斯核函数.实验基于数据库构建了以(39)的内积的多项式指示函数.输入空间的维数是256,多项式阶数范围从1到7.表2描述了实验结果.实验的训练数据不是线性可分的.可以发现,支持向量的个数增加非常缓慢.7阶多项式只比3阶多项式多了30%的

31、支持向量,甚至比一阶多项式还少.但是特征空间的维数7阶多项式却比3阶多项式的1010倍还多.除此以外还能看到,随着空间维数的增加性能并没有多大的改变,可见没有过拟合的问题.线性分割器的支持向量数目较多是由于数据集的不可分导致的:200个向量包括了支持向量和值非零的训练向量.如果>1则训练向量被错分;每个线性分类器在训练集上平均有34个样本被错分.2阶分类器训练集上被错分的总数下降到了4.这4个样本如图7所示.值得注意的是,当我们考虑所获得的支持向量个数并不是期望的数目时,实验中推广能力的界保持不变.各种不同情况错误概率的上界不超过3%(事实上在测试集上对单个分类器错误概率不超过1.5%)

32、.构建多项式分类器的时间不依赖于多项式的阶数,而仅依赖于支持向量的个数.即使是最坏情况,也快于专门为此用途设计的最优性能神经网络(LeNet19).神经网络的性能是5.1%的粗错误率.2阶或更高阶的多项式性能好于LeNet1.6.2.2 NIST数据库上的实验NIST数据库作为基准学习引入刚刚两周.时间的限制只允许构建一种类型的分类器,我们选择4阶多项式,且未进行预处理.该选择是基于美国邮政服务数据库上的实验.表3列出了10个分类器的支持向量数目和训练集与测试集上的性能.可以看到,即使是4阶的多项式(多于108的自由参数)也会在训练集上出错.平均训练误差是0.02%,即平均每类12个.分类器1

33、错分的14个样本如图8所示.再次注意对于所得的不同支持向量数目上界(5)是如何保持的.Table 3. Result obtained for a 4th degree polynomial classifier on the NIST database. The size of the training set is 60,000, and the size of the test size is 10,000 patterns.Fig 8. The 14 misclassified test patterns with labels for classifier 1. Patterns w

34、ith label “1” are false negative. Patterns with other labels are false positive.Fig 9. Results from the benchmark study.十个分类器在测试集上的联合误差是1.1%.这个结果应该在学习基准上和其他的分类器进行比较.包括一个线性分类器,一个具有60,000个原型的k (=3)最近邻分类器,两个专门为数字识别而设计的神经网络(LeNet1和LeNet4).作者只给出了支持向量网络的实验结果.学习基准的比较结果如图9所示.我们引用文献4对学习基准的描述来作为本节的总结:“很长一段时间L

35、eNet1被认为是发展水平通过一系列在结构和错误特征分析的实验,LeNet4被认为是支持向量网络具有很高的精度,很令人瞩目,因为和其他高性能的分类器不一样,它不包括问题的几何学知识.事实上,即使是对图像像素进行加密,比如通过一个固定随机的置换,它依然可以工作得很好.”最后要说的是,支持向量网络性能的进一步提高可以通过构建一个反应已有问题先验信息的内积函数.7 总结本文介绍了一种针对两类分类问题的新型学习机器支持向量网络.支持向量网络包含3个思想:求解最优超平面的技术(允许将解向量在支持向量上展开),内积回旋的思想(将决策面求解从线性扩展到非线性),和软间隔的概念(允许训练集上出现错误).该算法

36、已经过测试并和其他分类算法进行过性能比较.尽管它的决策面设计简单但是在比较学习上它展现了很好的性能.其他特征例如容量控制能力和决策面变换的简易性证实了支持向量网络是一种及其强大和通用的学习机器.References1 M. Aizerman, E.Braverman, and L. Rozonoer. Theoretical foundations of the potential function method in pattern recognition learning. Automation and Remote Control, 25:821-837, 1964.2 T. W. An

37、derson and R. R. Bahadur. Classification into two multivariate normal distributions with different covariance matrices. Ann. Math. Stat.,33:420-431,1966.3 B. E. Boser, I. Guyon, and V. N. Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the Fifth Annual Workshop of Comp

38、utational Learning Theory, volume 5, pages 144-152, Pittsburg, 1992. ACM.4 L.Bottou, C.Cortes, J. S. Denker, H.Drucker, I.Guyon, L.D.Jackel, Y.LeCun, E.Sackinger P. Simard, V. Vapnik, and U. A. Miller. Comparison of classifier methods: A case study in handwritten digit recognition. Proceedings of 12

39、th International Conference on Pattern Recognition and Neural Network, 1994.5 J. Bromley and E. Sackinger. Neural-network and k-nearest-neighbor classifiers. Technical Report 11359-910819-16TM, AT&T, 1991.6 R.Courant and D.Hilbert. Methods of Mathematical Physics. Interscience, New York, 1953.7 R. A. Fisher. The use of mu