最优化理论与支持向量机

最优化理论与支持向量机摘要近几年来,机器学习方法得到了广泛的应用,在其理论研究和算法实现方面都取得了重大进展成为机器学习领域的前沿热点课题.支持向量机也受到广泛的关注,它以统计学习为基础,建立在计算学习理论的结构风险最小化原则之上,具有简洁的数学形式,已成为机器学习和数据挖掘领域的主要工具.本文主要是对最优化理论的概述以及对支持向量机的简单介绍.通过对最优化理论与支持向量机的学习,进一步深入研究相关理论与实验知识.关键词:样本集类标识支持向量机回归1．最优化理论本学期主要学习了最优化的一些基本理论,一类分类问题,二类分类问题,多类分类问题,回归问题.分类问题的主要思想是通过给定的样本集1,{()}nmixyRRiiT寻找一个定值函数:mfRR.以便利用f来判断任一输入mixR的类标识.另外,分类问题根据数据样本的个数可分为一类分类问题,二类分类问题,多类分类问题.根据定值函数的线性和非线性性,可分为线性分类问题和非线性分类问题.对于分类问题研究最多的是二类分类问题和多类分类问题.近几年来,机器学习方法得到了广泛的应用,在其理论研究和算法实现方面都取得了重大进展成为机器学习领域的前沿热点课题.不少学者将机器学习的方法应用与机械产品寿命的预测,而其中人工神经网络和支持向量机等方法在寿命预测中应用较多.由于人工神经网络存在对样本数量与质量具有高依赖性,且对于小样本情况易陷入局部最优等问题,而以统计学理论为基础的支持向量机,具有严格的理论和数学基础,可以不像神经网络的结构设计需要依赖于设计者的经验知识和先验知识,因此,利用支持向量机理论实现趋势预测分析已成为研究新热点.基于数据的机器学习是一种重要的知识发现方法,是人工智能最具智能特征、最前言的研究领域之一.机器学习主要研究计算机如何模拟或实现人类的学习能力,以获取新的知识技能,重新组织已有的知识结构,使之不断改善自身的性能.机器学习是人类智能的核心问题,是使计算机具有人工智能的根本途径,基于数据的机器学习问题作为人工智能研究领域的一个重要方面.其研究的主要问题是从一组观测数据集出发,得到一些不能通过原理分析而得到的规律,进而利用这些规律对未来数据或无法观测到的数据进行预测和分析.迄今为止,关于机器学习还没有一种被共同接受的理论框架,关于其实现方法大致可以分为以下三种[1].第一种是经典的统计预测方法[2].现有机器学习方法共同的重要理论基础之一是统计学.在这类方法中,模型中参数的相关形式是已知的,用训练样本来估计参数需要已知样本的分布形式,因此具有很大的局限性.另外传统的统计学研究的是样本数目趋于无穷大时的渐进理论,但在实际问题中,样本数量却是有限的,因此一些理论上很优秀的学习方法在实际应用中可能表现的不尽人意.第二种方法是经验非线性方法,如人工神经网络(ANN)方法[3][4],神经网络学习方法对于逼近实数值、离散值或向量值的目标函数提供了一种健壮性很强的方法.对于某些类型的问题,如学习解释复杂的现实世界中的传感器数据,人工神经网络是目前知道的最有效的学习方法,这种方法利用已知样本建立非线性模型,克服了传统参数估计方法的困难,人工神经网络已在很多的实际问题中取得了惊人的成功,如手写识别,图像识别,语音识别.但是这种方法缺少统一的教学理论,过度拟合训练也是人工神经网络学习中的重要问题.尽管人工神经网络对训练数据表现非常好,过度拟合也会导致数据泛化到新的数据时性能很差.第三种方法是统计学习理论(StatisticalLearningTheory,SLT)[5],与传统的统计学习相比,SLT是一种专门研究小样本情况下机器学习规律的理论.该理论针对小样本统计问题建立了一套新的理论体系,在这种体系下的统计推理规则不仅考虑了对渐进性能的要求,而且追求在现有有限信息条件下得到的最优结果.Vapnik等人从20世纪60年代开始致力于此方面的研究,到90年代中期随着其理论的不断发展成熟,也由于神经网络等学习方法在理论上缺乏实质性的进展,SLT开始受到越来越广泛的重视.支持向量机(SVM)[6]是Cortes和Vapnik于1995年在VC维理论和结构风险最这种小原理基础上提出的一种机器学习方法,它是借助优化方法解决机器学习问题的新工具,能够尽量提高学习机的推广能力,即使由有限数据集得到的判别函数对独立的测试集仍能够得到较小的误差.此外SVM是一个凸二次规划,能够保证找到的解释全局最优解.这些特点使SVM成为一种优秀的基于数据的机器学习方法,SVM是机器理论中最新的内容,也是最实用的部分,其主要内容在1992年到1995年间基本完成,目前仍处于基本发展阶段.可以说SLT之所以从20世纪90年代以来受到越来越多的重视,很大程度上是因为它发展出来了SVM这一通用的基于数据的机器学习方法.SVM在解决小样本、非线性及高维模式识别问题中表现出特别的优势,并能够推广到函数拟合等其他机器学习问题中.与传统机器学习方法不同,SVM首先通过非线性变换将原始的样本空间映射到高维的特征空间,然后在这个行空间中求取最优线性分类面,而这种非线性变换是通过定义适当的内积函数实现的.SVM成功的解决了高维问题和局部极小值问题.在SVM中只要定义不同的内积函数,就可以实现多项式逼近、贝叶斯分类器、径向基函数(RBF)方法、多层感知器网络等很多现有的学习算法.在解决高维问题中,神经网络等方法容易陷入一个又一个局部极小值.SVM使用了大因子来控制学习机器的训练过程，使其只选择具有最大分类间隔的分类超平面.最优超平面对线性不可分的情况引入松弛项来控制经验风险从而使其在满足分类要求的情况下具有好的推广能力,寻找最优超平面的过程最终转化为凸二次型优化问题而得到全局最优解.SVM方法具有较好的理论基础,在一些领域的应用中表现出来与众不同的优秀的泛化性能,因此,SVM在解决分类、回归和密度函数估计等机器学习方面获得了非常好的效果,并成功应用在模式识别、回归估计和概率密度函数估计等方面.例如在模式识别方面,SVM在手写数字识别、语音识别、文本分类、信号处理、图像分类和识别等多个领域都有不俗的表现.SVM在精度上已经超过传统的学习算法或与之不相上下.SVM在解决有限样本、高维模式识别、非线性等复杂问题中表现出许多特有的优势,目前SVM已被成功应用于识别、回归、分类问题中.2．线性支持向量机所谓最优化技术就是找出使得目标函数值达到最小或最大的自变量值的方法.最优化问题从其分类看有经典无约束最优化问题和有约束最优化问题.无约束极值问题的数学模型为min()xfx其中12[,,]TnxxxxL称为优化变量,()f函数称为目标函数,该数学表示的含义亦即求取一组x向量,使得最优化目标函数()fx为最小,故这样的问题又称为最小化问题,那么只需给目标函数()fx乘以一个负号就能立即将最大化问题转换成最小化问题.所以最优化问题研究的一般全是最小化问题.有约束最优化问题的数学模型为min()..()0,xfxstGx其中12[,,]TnxxxxL.该数学表达式的含义为求取一组x向量,使得在满足约束条件()0Gx的前提下能够使目标函数()fx最小化.在实际遇到的最优化问题中,有时约束条件可能是很复杂的,它既可以是等式约束,也可以是不等式约束;既可以是线性的,也可以是非线性的,有时甚至不能用纯数学函数来描述.一般的约束问题可以既包含等式约束又包含不等式约束,其一般形式为min()..()0,1,,()0,1,,xijfxstcxipcxjppqLL这类问题称为一般约束问题其中12[,,]TnxxxxL,称()fx称为目标函数,称()0,1,,,()0,1,,ijcxipcxjppqLL为约束条件,并称()icx为约束函数.此外称满足条件的点为可行点,并称全体可行点组成的集合为可行域.该数学表达式的含义为求取一组x向量,使得在满足约束条件()0,1,,,()0,1,,ijcxipcxjppqLL的前提下能够使目标函数()fx最小化.在学习过程中,我们着重研究的是二类分类问题的支持向量机(SupportVectorMachine,简称SVM),以及在SVM基础上得到的其他类型的支持向量机,比如:双生支持向量机(TSVM-Twinsupportvectormachine)[7],最小二乘支持向量机(LSTSVM-leastsquaresupportvectormachine)[8],有界支持向量机(TBSVM-twinboundsupportvectormachine)[9],支持向量回归机(SVR-supportvectorregression)[10]等.在二类分类问题模型基础上进行改进可得到多类分类问题的分类器.SVM涉及到两个凸规划问题——原始问题和对偶问题,由这两个问题的解之间的关系建立算法.因此优化理论也是SVM的重要理论基础.下面介绍一下经典支持向量机(SVM),双生支持向量机(TSVM)以及支持向量回归机(SVR).2.1.线性软间隔支持向量机设1{(,)}{1}nmiiixyR是二类数据集,其中ix是行向量.线性软间隔SVM的基本思想是通过求解一个二次规划问题,得到两个平行边界超平面,进而得到分类超平面.线性软间隔SVM对应的原始问题为21,,1min2..(,)1,0,1,,,niiwbiiiwCstywxbinL其Wolfe对偶形式为111112..0,0,1,,,min,nnnijijijiijiniiiistCinyyxxyL(2.1)其中1(,,)TnnRL是Lagrange乘子向量.通过求解问题(2.1),可得分类超平面,0wxb.具体算法如下.算法1.(线性软间隔二类SVM)步1.给出训练集1{(,)}{1}nmiiixyR.步2.选择适当的参数0C,求解问题(2.1),得最优解1(,,)Tn.步3.计算1niiiiyx.选择的一个正分量0jC,计算1,njiiijibyyxx.步4.构造分离超平面,0xb和决策函数()sgn(,)fxxb.2.2.线性双生支持向量机TSVM的基本思想是通过求解两个二次规划问题得到两个非平行边界超平面,进而得到两个非平行的分类超平面.TSVM对应的原始问题为1111111112121211min,,2..,0,TTTSVMAwebAwebcewbstBwebe2222222221212112min,,2..,0,TTTSVMBwebBwebcewbstAwebe其中,AB分别是数据样本中两类样本组成的列向量,12,ee分别是与,AB列数相同,元素全为1的列向量;12,cc是大于0的参数;是松弛变量.其Wolfe对偶形式为(简记为DTSVM1、DTSVM2)分别为12111min2..0,TTTTDTSVMGHHGestc(2.2)11212min2..0,TTTTDTSVMGHHGestc(2.3)其中,是Lagrange乘子向量,12[],[].HAeGBe通过求解问题(2.2)和(2.3),可得分类超平面110Txwb和220.Txwb算法2.(线性TSVM)步1.给出训练集1{(,)}{1}nmiiixyR.步2.选择适当的参数0C,求解问题(1.2)和(1.3),得最优解1(,,)Tn.步3.计算1niiiiyx.选择的一个正分量0jC,计算1,njiiijibyyxx.步4.构造分离超平面,0xb和决策函数()sgn(,)fxxb.2.3.线性支持向量回归机SVM最初是为分类问题设计的,已