支持向量机支持向量机模型选择研究摘要:统计学习理论为系统地研究有限样本情况下的机器学习问题提供了一套比较完整的理论体系。
支持向量机(suPportvectorMachine,SVM)是在该理论体系下产生的一种新的机器学习方法,它能较好地解决小样本、非线性、维数灾难和局部极小等问题,具有很强的泛化能力。
支持向量机目前已经广泛地应用于模式识别、回归估计、概率密度估计等各个领域。
不仅如此,支持向量机的出现推动了基于核的学习方法(Kernel-based Learning Methods)的迅速发展,该方法使得研究人员能够高效地分析非线性关系,而这种高效率原先只有线性算法才能得到。
目前,以支持向量机为主要代表的核方法是机器学习领域研究的焦点课题之一。
众所周知,支持向量机的性能主要取决于两个因素:(1)核函数的选择;(2)惩罚系数(正则化参数)C的选择。
对于具体的问题,如何确定SVM中的核函数与惩罚系数就是所谓的模型选择问题。
模型选择,尤其是核函数的选择是支持向量机研究的中心内容之一。
本文针对模型选择问题,特别是核函数的选择问题进行了较为深入的研究。
其中主要的内容如下:1.系统地归纳总结了统计学习理论、核函数特征空间和支持向量机的有关理论与算法。
2.研究了SVM参数的基本语义,指出数据集中的不同特征和不同样本对分类结果的影响可以分别由核参数和惩罚系数来刻画,从而样木重要性和特征重要性的考察可以归结到SVM的模型选择问题来研究。
在对样本加权SVM模型(例如模糊SVM)分析的基础上,运用了特征加权SVM模型,即FWSVM,本质上就是SVM与特征加权的结合。
3,在系统归纳总结SVM模型选择。
尤其是核函数参数选择的常用方法(例如交叉验证技术、最小化LOO误差及其上界、优化核评估标准)。
关键词:机器学习;模式分类;支持向量机;模型选择;核函数;核函数评估支持向量机基础引言机器学习的科学基础之一是统计学。
传统统计学所研究的是渐近理论,即当样本数目趋于无穷大时的极限特性。
基于传统统计学的机器学习,也称为统计模式识别,由Duda等人提出。
Duda的贡献主要是以经典统计理论为工具刻画了模式识别与机器学习的各类任务,同时暗示了对所建模型的评价方法。
然而,在实际应用中,学习样本的数目往往是有限的,特别当问题处于高维空问时尤其如此。
统计学习理论研究的是有限样本情况下的机器学习问题,它基于PAC(Probably Approximately Correct)框架给出关于学习算法泛化性能的界,从而可以得出误差精度和样木数目之间的关系。
这样,样木集合成为泛化指标的随机变量,由此建立了结构风险理论。
Minsky和PaPert在20世纪60年代明确指出线性学习机计算能力有限。
总体上,现实世界复杂的应用需要比线性函数更富有表达能力的假设空间"多层感知器可以作为这个问题的一个解,由此导向了多层神经网络的反向传播算法。
核函数表示方式提供了另一条解决途径,即将数据映射到高维空间来增强线性学习机的计算能力。
核函数的引入最终使得在适当的特征空间中使用人们熟知的线性算法高效地检测非线性关系成为一可能。
SVM是建立在统计学习理论(包括核函数的表示理论)基础上的第一个学习算法,目前主要应用于求解监督学习问题,即分类和回归问题。
SVM以泛化能力为目标,其目的不是对己知样本的描述(或称为记忆),而是对未知样本的预测(或称为泛化)"对于算法的性能问题,SVM标志着人们已经从单纯的实验验证向理论分析过渡"与多层神经网络的反向传播算法相比较,SVM的优点是什么呢?首先,以严格的数学理论(统计学习理论)为基础,克服了神经网络学习中的经验和启发式成分;用结构风险最小化原则代替经验风险最小化,克服了过学习问题,提高了学习机的泛化能力。
其次,利用核函数与核技巧巧妙地克服了特征空间的维数灾难问题;最后,通过解决一个凸二次规划问题,得到全局最优解,而不是神经网络学习中的局部最优解。
问题的数学形式为:l1 UwNwwCN,，,,1,，，，，,2,1iywxbNil((,1,))1,1,,，,,,？iii stNil,,0,1,,.？i通过求其对偶问题，归结为一个二次函数极值问题:ll1WAAyyAAKxx()(,),,,,iijijij 2,,1,1iijstACil:0,1,,,,,？ilAy,0,ii,1i分类判别函数为:l，，,, fxsignAyKxxb,，,，，，，,iii,,,,i,1,,，，模型选择与核函数的研究面对一个实际的问题,我们应如何应用支持向量机来解决呢?从通用的层面看,显然首先应把问题转化为能用支持向量机求解的数学模型。
这一过程称为模型选择,其中应包括:(i)数据集的获取与预处理;(ii)SvM类型的选择,如选择标准的SVM或v一SVM;(111)SVM中核函数和其已参数(如惩罚系数C)的选择。
其中第三个问题是模型选择研究的重点。
核函数隐式地定义了高维特征空间的结构,使得线性不可分的问题转化为线性可分的问题,而且不增加计算量,是影响SVM性能的关键因素"另一方面,SVM的分类性能除了取决于核函数的选择外,还取决于惩罚系数C,该系数的目的是在误分样本与学习机模型复杂性之间进行折衷,即在确定的特征空间中调节经验风险和学习机置信范围的比例,以使得学习机器的泛化能力最好。
简要地说,核函数的选择主要影响数据在特征空间中的分布,而惩罚系数C，在特征空间中确定经验风险水平而影响SVM的性能。
本文主要讨论核函数的选择问题。
由于核函数和核技巧在SVM中的成功应用,学术界对核函数的研究正如火如茶地展开,其中核函数的理论研究，核函数的构造和核函数中参数的选择是三个主要的研究方向。
常用的几种核函数常用的核函数主要包括以下几种:1. 多项式核。
多项式核的一般形式为:d， kxzxzcdZc(,)(,),,0,,,，,,2指数型径向基核。
指数型径向基核的形式为:2||||xz, ,kxz(,)exp(),0,,,22,当所讨论的问题是不连续(即离散)时,这个核函数可应用于产生一个线性的分段解。
3.傅立叶核"常用的傅立叶核有两种,它们都是由一维傅立叶核生成的。
第一种傅立叶核所对应的一维傅立叶核为21,q kxzxzR(,),,,,,122(12cos()),,，qxzq其中q是满足0<q<1的常数。
第二种傅立叶核所对应的一维傅立叶核为,,,||xzch(),, kxzxzRxz(,),,,0||2,,,,,,,1,2,sh(),,其中是常数4.多层感知器核(Sigmoid核)。
多层感知器核的形式为:kxzxz(,)tanh(,),0,0,,,,,,,,,,,,0,对于这个核必需强调的是,它仅对某些才是半正定的。
特征加权SVM基于特征加权核函数构造的SVM称为特征加权svM(Feature WeightedSVM,SWFVM)。
形式地表述如下:lll1,,,,yykxxmax(,),,,iijijpij2,,,111iijlsty,.0,,,ii,1i？,,,Cil0,1,,i则决策函数为t,* fxykxxb()sgn((,)),，,,iipi,1i*其中，任选,中的一个分量对应的点， xjl** byykxx,,,(,),jjiij,1i显然,特征加权SVM和传统的C一SVM的形式几乎完全相同,只是将核函数换k(x,z)成了特征加权核函数称(x,z)。
数据集及实验设置从UCI机器学习数据库中选择的数据集有7个,总共有699个样本,除去其中16个包含未知特征值的样本,剩下683个样本。
表3—1简单地描述了所选数据集的基本属性。
SVM的实现采用了LIBSVM软件包。
实验结果由表3—4图3—2与图3—3，可以看出:数据集Letter中的不同特征对分类结果影响程度的差别比Breast大,而FWSVM正是利用特征加权核函数反映这种差别的学习算法，它通过特征加权减少弱相关特征(权重小)对分类结果的影响，从而提高了学习算法的分类性能。
局部化的核函数评估目前，核函数的评估方法主要分为三类:其一，依据算法的评价标准进行评估。
算法的评价标准,如10一折交叉验证误差、LOO误差、LOO误差的上界等,提供了评价两种方案(当然包括核函数的选择)的准则。
比较两种不同方案对应的数量指标(误差或误差界),以较小者为优。
其二,综合应用多种统计方法进行评估。
这里的统计方法包括k一折交叉验证、配对t测试、纠正重复取样t测试等。
三,独立于算法的核函数评估。
这种方法的基础是一系列独立于算法的核评估标准的提出,如核排列、核极化、基于特征空间的核矩阵评估标准独立于具体的学习算法是这种方法与前面两种方法的重要区别,它不直接考虑分类器的泛化性能,而是着力捕捉训练数据集在特征空间中的可分离特性。
基于特征空间的核矩阵评估标准Nguyen和Ho两人分析了核排列标准的一些严重缺陷,指出拥有较大的核排列值是一个好的核函数的充分而非必要条件(即使核排列值很小的核函数完全有可能获得很好的性能),并提出了一个替代标准)基于特征空间的核矩阵评估标准: ,var ,FSMkk(,),,,||||，,设训练集T中正类和负类的样本分别有和个: ll，,l，1(),,,x,i，li,1，l1,()x,,,i,lil,，1,，,，,,,e,||||,，,,,l， 2,,,(),xe1i,，,,i,12var(),，l,1，l2(),,,,xei,,1,,il,1，2var(),,l,1,varvarvar,，，,,显然，FSMkk(,)0,，其中分母的含义是特征空间中正负类中心的距离，分子的含义是特征空间中同类内的样本在正负类中心所确定的方向上的总偏差。
局部结构信息与降维数据集中的局部结构信息,或者称为多模态，在实际应用中是经常可见的，例如在手写阿拉伯数字识别中将数字分成奇数和偶数两类、通过构造多个一对多的二分类问题来解决多类分类等问题中就存在这种情形。
这种分离的聚类块就是存在于同类数据中的局部结构信息。
许多学者对具有局部结构信息的数据集上的机器学习作了较为深入的研究,其木质是为了在学习的过程中保持数据的局部结构不受到破坏。
降维是高维数据分析的重要预处理步骤之一,目的是在保留数据的大部分内在信息的同时将高维空间的数据样本嵌入到一个相对低维的空间。
Fisher判别分析是一种应用非常广泛的线性降维算法。
FDA利用了数据点的类别信息,是一种有监督的降维算法,其目的是最大化数据集类间的离散度,同时最小化类内的离散度。
然而,FDA没有考虑到数据中的局部结构信息对算法性能的影响,会将同类内的多个聚类块投影成唯一的聚类块,从而破坏数据的分布特性。
局部保持投影算法则克服了FnA算法的这个缺陷,它保持输入空间相近邻的数据点在低维嵌入空间中也是近邻的;换句话说,它保持了数据的局部结构信息。