最优化理论与支持向量机

1、最优化理论与支持向量机摘要 近几年来，机器学习方法得到了广泛的应用，在其理论研究和算法实现方面都取 得了重大进展成为机器学习领域的前沿热点课题.支持向量机也受到广泛的关注，它以统计学习为基础，建立在计算学习理论的结构风险最小化原则之上，具有简洁的数学形式，已成为机器学习和数据挖掘领域的主要工具.本文主要是对最优化理论的概述以及对支持 向量机的简单介绍.通过对最优化理论与支持向量机的学习，进一步深入研究相关理论与 实验知识关键词：样本集 类标识 支持向量机 回归1 最优化理论本学期主要学习了最优化的一些基本理论，一类分类问题，二类分类问题，多类分类 问题,回归问题分类问题的主要思想是通过给定的样

2、本集 T =（,生）：4 Rm R寻找一 个定值函数f ：Rm R.以便利用f来判断任一输入Rm的类标识.另外,分类问题根 据数据样本的个数可分为一类分类问题，二类分类问题，多类分类问题根据定值函数的 线性和非线性性，可分为线性分类问题和非线性分类问题对于分类问题研究最多的是二 类分类问题和多类分类问题近几年来，机器学习方法得到了广泛的应用，在其理论研究和算法实现方面都取得了 重大进展成为机器学习领域的前沿热点课题.不少学者将机器学习的方法应用与机械产品 寿命的预测，而其中人工神经网络和支持向量机等方法在寿命预测中应用较多由于人工神经网络存在对样本数量与质量具有高依赖性，且对于小样本情况易陷入

3、局部最优等问题而以统计学理论为基础的支持向量机，具有严格的理论和数学基础，可以不像神经网络的 结构设计需要依赖于设计者的经验知识和先验知识，因此，利用支持向量机理论实现趋势 预测分析已成为研究新热点基于数据的机器学习是一种重要的知识发现方法，是人工智能最具智能特征、最前言 的研究领域之一 机器学习主要研究计算机如何模拟或实现人类的学习能力，以获取新的知识技能，重新组织已有的知识结构，使之不断改善自身的性能机器学习是人类智能的 核心问题，是使计算机具有人工智能的根本途径，基于数据的机器学习问题作为人工智能 研究领域的一个重要方面.其研究的主要问题是从一组观测数据集出发，得到一些不能通 过原理分析

4、而得到的规律，进而利用这些规律对未来数据或无法观测到的数据进行预测和 分析迄今为止，关于机器学习还没有一种被共同接受的理论框架，关于其实现方法大致可 以分为以下三种1.第一种是经典的统计预测方法2.现有机器学习方法共同的重要理论基础之一是统计 学.在这类方法中，模型中参数的相关形式是已知的，用训练样本来估计参数需要已知样 本的分布形式，因此具有很大的局限性.另外传统的统计学研究的是样本数目趋于无穷大 时的渐进理论，但在实际问题中，样本数量却是有限的，因此一些理论上很优秀的学习方 法在实际应用中可能表现的不尽人意.第二种方法是经验非线性方法 , 如人工神经网络 (ANN) 方法 34, 神经网络

5、学习方法 对于逼近实数值、离散值或向量值的目标函数提供了一种健壮性很强的方法 . 对于某些类 型的问题 , 如学习解释复杂的现实世界中的传感器数据 , 人工神经网络是目前知道的最有 效的学习方法 , 这种方法利用已知样本建立非线性模型 , 克服了传统参数估计方法的困难 , 人工神经网络已在很多的实际问题中取得了惊人的成功 , 如手写识别 , 图像识别 , 语音识 别 . 但是这种方法缺少统一的教学理论 , 过度拟合训练也是人工神经网络学习中的重要问 题 . 尽管人工神经网络对训练数据表现非常好 , 过度拟合也会导致数据泛化到新的数据时 性能很差.第三种方法是统计学习理论 ( Statistic

6、al Learning Theory, SLT) 5, 与传统的统计学习相 比, SLT 是一种专门研究小样本情况下机器学习规律的理论 . 该理论针对小样本统计问题 建立了一套新的理论体系 , 在这种体系下的统计推理规则不仅考虑了对渐进性能的要求 , 而且追求在现有有限信息条件下得到的最优结果.Vapnik等人从20世纪60年代开始致力于此方面的研究 , 到 90年代中期随着其理论的不断发展成熟 , 也由于神经网络等学习方法 在理论上缺乏实质性的进展 , SLT 开始受到越来越广泛的重视 .支持向量机(SVM)6是Cortes和Vapnik于1995年在VC维理论和结构风险最这种小 原理基础上

7、提出的一种机器学习方法 , 它是借助优化方法解决机器学习问题的新工具 , 能 够尽量提高学习机的推广能力 , 即使由有限数据集得到的判别函数对独立的测试集仍能够 得到较小的误差 . 此外 SVM 是一个凸二次规划 , 能够保证找到的解释全局最优解 . 这些特 点使SVM成为一种优秀的基于数据的机器学习方法，SVM是机器理论中最新的内容，也是 最实用的部分, 其主要内容在 1992年到1995年间基本完成, 目前仍处于基本发展阶段 . 可 以说SLT之所以从20世纪90年代以来受到越来越多的重视,很大程度上是因为它发展出 来了 SVM 这一通用的基于数据的机器学习方法 .SVM 在解决小样本、

8、非线性及高维模式识别问题中表现出特别的优势 , 并能够推广到 函数拟合等其他机器学习问题中 . 与传统机器学习方法不同 , SVM 首先通过非线性变换将 原始的样本空间映射到高维的特征空间 , 然后在这个行空间中求取最优线性分类面 , 而这 种非线性变换是通过定义适当的内积函数实现的 .SVM 成功的解决了高维问题和局部极小 值问题. 在 SVM 中只要定义不同的内积函数 , 就可以实现多项式逼近、贝叶斯分类器、径 向基函数(RBF)方法、多层感知器网络等很多现有的学习算法.在解决高维问题中，神经网 络等方法容易陷入一个又一个局部极小值 . SVM 使用了大因子来控制学习机器的训练过 程，使其

9、只选择具有最大分类间隔的分类超平面 . 最优超平面对线性不可分的情况引入松 弛项来控制经验风险从而使其在满足分类要求的情况下具有好的推广能力 , 寻找最优超平 面的过程最终转化为凸二次型优化问题而得到全局最优解 .SVM 方法具有较好的理论基础 , 在一些领域的应用中表现出来与众不同的优秀的泛 化性能, 因此, SVM 在解决分类、回归和密度函数估计等机器学习方面获得了非常好的效 果, 并成功应用在模式识别、回归估计和概率密度函数估计等方面 . 例如在模式识别方面 , TOC o 1-5 h z SVM在手写数字识别、语音识别、文本分类、信号处理、图像分类和识别等多个领域都有 不俗的表现.SV

10、M在精度上已经超过传统的学习算法或与之不相上下.SVM在解决有限样本、高维模式识别、非线性等复杂问题中表现出许多特有的优势，目前SVM已被成功应用于识别、回归、分类问题中.线性支持向量机所谓最优化技术就是找出使得目标函数值达到最小或最大的自变量值的方法最优化问题从其分类看有经典无约束最优化问题和有约束最优化问题.无约束极值问题的数学模型为min f (x)x其中x 亠b)空；，i = 1,L ,n,(vw,k b) - yi 乞；,i =1,L ,n,其中；是大于0的参数.其Wolfe对偶形式为Xi,X八迈上+冃)-Z ：訂(3 -冃)(2.4)郭2瓦工1妙一冃炉s.t. : i 一 匚=0,

11、 0i C, 0 岂乞 C, i =1,L ,n.其中,:是 Lagrange乘子向量.通过求解问题(2.4),可得分类超平面：:w,x b = 0.具体算法如下. 算法3.(线性支持向量回归机)步 1.给出训练集( X,yi)：#u Rmx1.步2.选择适当的参数C .0, ; .0,求解问题(1.4),得最优解宀阳，阳，护=w：)t.步3.计算；八；4( - -i*)Xi .选择厂的一个正分量0 ： :- j : C ,计算b =y - : w*,Xj -；,或者选择的一个正分量 0 ： / : C ,计算 b = y - : w*,Xj -；步4.构造决策函数f (x) = ： ，x *

12、 b .步5.对任一测试点% Rn,其输出f(%=：w*,%b*.此外还学习了一些多类支持向量机的模型.如多元双生支持向量机(Multi-twin support vector machine,简记为 MTSVM),多生支持向量机(Multiple birth support vector machine, 简记为MBSVM)等.2.4.多元双生支持向量机(MTSVM)多元双生支持向量机是在TSVM基础上采用了一对余的方法处理数据的，为每一类数 据利用最小二乘原理构造一个分类超平面，使得该类数据点尽可能靠近这一超平面，同时 尽可能的排斥其它类数据.本文中用到的数据点中的第i类用A Rci =1

13、丄c表示，剩余 的其它类看作是另一类，用Bj =At,L ,AtA、,L ATT R(c网,i =1丄c表示.MTSVM基本思想是对于c类问题，为每一类找到一个超平面+b =0,i =1丄，c.使得除第i类之外的的数据点尽可能靠近这一超平面，同时尽可 能的排斥第i类数据.MTSVM第i类数据点对应的原始问题为1 2 1mb先2卜側+射|右瓦j$占弋s.t-(BiWi 勺20)丨一勺，i -0, i, j =1丄，c,其中 ei Rct $2 e R(cf T Ci0.此规划的wolfe对偶为min丄、c2心Tt1 Tct|： i Gi Hi HiGi ： iiTe2i(2.5)s.t0g,i

14、=1,L ,c,其中 Hi =A,eJ, G 二田鸟.通过求解问题(2.5),得到第i类数据点对应的分类超平面 vw,x+bi=0. 具体算法如下.算法 4. (MTSVM)步 1.给出训练集(x,yi)i：u Rmx1,L ,c.步 2.对每一个 r 1, L ,c,取 X：一 Xi,X-=X Xi.步3.选择适当的参数Ci 0,求解问题(2.5),得最优解 汀珥叮，,J)T,i可,L ,c. 步 4.令 ui 二Mb,计算 u* (HiTHi)9：步5.构造分离超平面b0和决策函数(x) =： J”,x 巾：步6.对任一测试点% Rm,若fk(%p wjJ夠，则判断属第k类.2.5.多生支

15、持向量机(MBSVM)MBSVM基本思想是对于c类问题，为每一类找到一个超平面Wi, +h =0,i =1丄,c.使得第i类的数据点尽可能靠近这一超平面,同时尽可能的排斥 其它类数据.MBSVM与MTSVM不同之处在于MBSVM是把数据中的一类数据点放到约束条件中 其它类点作为另一类，放在目标函数中.MBSVM第i类数据点对应的原始问题为mjn 三 BiW +胡| +Ge：q1w，bj, Q 2s.t (AWi +乂2匕)+ Gk -0,0.其中 q R(cs 1, eb RCi1, G此规划的wolfe对偶为m istT n i2.0 . + h = 0 .具体算法如下.算法 6. (MBS

16、VM)步1.步2.步3.步4.步5.步6.给出训练集(xi,yi)nd Rm 1,L,c.对每一个 r 1L ,c,取 X：-Xi，X_-X Xi.选择适当的参数Ci 0,求解问题(2.6),得最优解：=(叮，叮)T,i =1, L ,c. 令 Ui =w；bl，计算 u-(HiTHi)JGi*.构造分离超平面七0和决策函数fj(x) *”,x b”.,则判断属第k类.Wi |对任一测试点% Rm ,若fk(% = max非线性支持向量机在日常生活中遇到的分类问题，大部分是线性不可分的问题.对于线性不可分问题， 通过引入核函数k： Rm Rm R,利用核函数的特征映射将数据映射到高维特征空间，

17、使得映射后的数据是(近似)线性可分的.常见的核函数主要有：咼斯径向基核：2 2 2 2k(x, y) =exp - x - y| / - 或 k(x, y) =exp - x - y / 2二，(二.0).多项式核：k(x,y) =(：x,y c)d,(c R,d 0).利用核函数定义，minas.t问题(2.1)可改进为如下1 n nni八iryiyjkXXj) -v yrn i ： i% =0,0 乞：i c,i =1,L , n.(3.1)算法1可改进为算法3.(加核二类SVM)步1.给出训练集( *$)：4匸Rm1.步2.选择适当的参数C 0,求解问题(1.1),得最优解】=：(打，,

18、n)T .步3.计算八；斗i人.选择厂的一个正分量0 ： :- j :：: C ,计算b j -、1 yi: i k:Xj, Xj -.步4.构造分离超平面 -X b=o和决策函数f(x)=sgn(k-,x bj.利用核函数定义，问题(2.2)和(2.3)改进为如下DTSVM 1 mr as.t1_1in： tG H TH- e2：-20 _： _ q,(3.2)DTSVM 2 mins.t-tG HtHGt 1 _eT 120 -c2,(3.3)其中:,-是 Lagrange乘子向量,H 二K(A,X) e1, G=K(B,X) e2.算法与算法 2是 相同的.此外还学习了一些其它支持向量机

19、的模型，此处不再一一列举.4.结论近年来，支持向量机受到广泛的关注，SVM是在统计学习理论 VC维理论和结构风险 最小原理的基础上发展起来的一种新的机器学习方法.它以统计学习为基础，建立在计算学习理论的结构风险最小化原则之上，具有简洁的数学形式，能进行直观的几何解释并具 有良好的泛化能力，避免了局部最优解，且需要人为设定的参数较少，便于使用，为小样 本机器学习提供了一种新方法，以用于模式识别、回归分析和函数逼近等领域.支持向量 机已成为机器学习和数据挖掘领域的主要工具.由于它具有一些传统机器学习方法所不能 匹敌的优势而成为目前国内外研究的一个热点问题，并已成功应用于众多模式识别领域.通过学习本

20、门课程我了解到了许多与分类相关的知识.今后将会在此基础上不断改进 继续学习.随着研究的不断深入,新问题、新思想将会不断涌现，这必将促进SVM方法在实际应用中发挥更大的作用参考文献F.Mulier.Vapnik-Chervonenkis(VC) learning theory and its applications. IEEE Transactions on Neural Network, 1999, 10(5): 985-987.黄风岗 , 宁克欧 . 模式识别 . 哈尔滨工业大学出版社 , 1998.S.Haykin. Neural networks: A comprehensive Foundation. Pearson Education Inc. 1999.高隽. 人工神经网络原理及仿真实例 . 北京 :