您好,欢迎访问三七文档
当前位置:首页 > 临时分类 > 支持向量机及支持向量回归简介
3.支持向量机(回归)3.1.1支持向量机支持向量机(SVM)是美国Vapnik教授于1990年代提出的,2000年代后成为了很受欢迎的机器学习方法。它将输入样本集合变换到高维空间使得其分离性状况得到改善。它的结构酷似三层感知器,是构造分类规则的通用方法。SVM方法的贡献在于,它使得人们可以在非常高维的空间中构造出好的分类规则,为分类算法提供了统一的理论框架。作为副产品,SVM从理论上解释了多层感知器的隐蔽层数目和隐节点数目的作用,因此,将神经网络的学习算法纳入了核技巧范畴。所谓核技巧,就是找一个核函数(,)Kxy使其满足(,)((),())Kxyxy,代替在特征空间中内积(),())xy(的计算。因为对于非线性分类,一般是先找一个非线性映射将输入数据映射到高维特征空间,使之分离性状况得到很大改观,此时在该特征空间中进行分类,然后再返会原空间,就得到了原输入空间的非线性分类。由于内积运算量相当大,核技巧就是为了降低计算量而生的。特别,对特征空间H为Hilbert空间的情形,设(,)Kxy是定义在输入空间nR上的二元函数,设H中的规范正交基为12(),(),...,(),...nxxx。如果221(,)((),()),{}kkkkkKxyaxyal,那么取1()()kkkxax即为所求的非线性嵌入映射。由于核函数(,)Kxy的定义域是原来的输入空间,而不是高维的特征空间。因此,巧妙地避开了计算高维内积(),())xy(所需付出的计算代价。实际计算中,我们只要选定一个(,)Kxy,并不去重构嵌入映射1()()kkkxax。所以寻找核函数(,)Kxy(对称且非负)就是主要任务了。满足以上条件的核函数很多,例如可以取为d-阶多项式:(,)(1)dKxyxy,其中y为固定元素。可以取为径向函数:22(,)exp||||/Kxyxy,其中y为固定元素。可以取为神经网络惯用的核函数:12(,)tanh()Kxycxyc,其中y为固定元素。一般地,核函数的存在性只依赖于如何寻找一个平方收敛的非负序列ka。这样的序列在2l空间的正锥22|0,kklalak中的序列都满足。但哪一个最佳还有待于进一步讨论。经验表明,分类问题对于核函数不太敏感。当然,重新构造一个核函数也不是一个简单的事。因此,实际操作中往往就在上述三类中挑出一个来使用就可以了。支持向量机的结构示意图可以表示如下:图1支持向量机结构示意图其中输入层是为了存贮输入数据,并不作任何加工运算;中间层是通过对样本集的学习,选择(,),1,2,3,...,iKxxiL;最后一层就是构造分类函数1sgn((,))LiiiiyyaKxxb整个过程等价于在特征空间中构造一个最优超平面。支持向量机的作用之一就是分类。根据分类的任务,可以划分为一分类,二分类以及多分类。对于多类分类问题,可以用若干种手法将其分解为若干个二分类问题叠加。因此,为了实现支持向量机分类的算法,我们只要针对二分类,从头来给出它的数学原理。3.1.2支持向量机分类的数学原理设样本集为(,)|;1,1,1,...,niiiixyxRyiI,我们的目的是寻找一个最优超平面H使得标签为+1和-1的两类点不仅分开且分得间隔最大。当在n维欧几里德空间中就可以实现线性分离时,也即存在超平面将样本集按照标签-1与+1分在两边。由于超平面在n维欧几里德空间中的数学表达式是一个线性方程,0wxb,其中,w为系数向量,x为n维变量,,wx内积,b为常数。空间中点ix到超平面L的距离|,|(,)||||iiwxbdxLw。欲使得(,)idxH最大,等价于21||||2w最小。于是,得到一个在约束条件下的极值问题21min||||2(,)1,1,2,...,iiwywxbiI引入Lagrange乘子12(,,...,)I,可以解得关于该参变量的方程121,1(),IIiijijijiijQyyxx称之为Lagrange对偶函数。其约束条件为,10,0,1,2,...,IiiiijyiI在此约束条件之下,使得()Q达到最大值的的许多分量为0,不为0的i所对应的样本ix就称为支持向量。这就是支持向量的来历。当在输入空间不能实现线性分离,假设我们找到了非线性映射将样本集(,)|;1,1,1,...,niiiixyxRyiI映射到高维特征空间H中,此时我们考虑在H中的集合((),)|;1,1,1,...,niiiixyxRyiI的线性分类,即在H中构造超平面,其权系数w满足类似的极值问题。由于允许部分点可以例外,那么可以引入松弛项,即改写为:211min||||2(,)1,0,1,2,...,LiiiiiiwCywxbiI最终转化为一个二次型在约束条件下的二次规划问题:'''11min20,0(,...,)(,...,)TTIDcyACC其中,1(,...,)TIyyy,(1,...,1)Tc,1,(,)ijijijIDKxxyy为矩阵。(,)Kxs是核函数。一分类问题是一个极端情形但却又是非常有用的,它可以表示为如下数学模型:设|,1,...,niixxRiI为空间nR的有限观测点,找一个以a为心,以R为半径的包含这些点的最小球体。因此,一分类是对于求一个化合物成分的最小包络曲面的最佳方法。与前面完全相同的手法,设是由某个核函数(,)Kxs导出的从输入空间到特征空间中的嵌入映射,最后可以得到二次规划问题'''11min20,0(,...,)(,...,)TTIDcyACC其中,1(,...,)TIyyy,(1,...,1)Tc,1,(,)ijijijIDKxxyy为矩阵。(,)Kxs是核函数。此时111()(,)2(,)(,)LLLiiijijijifxKxxKxxKxx此时几乎所有的点满足2()fxR。参数C起着控制落在球外点的数目,变化区间为:1/1LC.3.1.3基于线性规划的SVM分类由于分类问题的自然推理过程都会归结到二次规划求解,计算复杂度相对较高。如果能将其简化为线性规划而且没有较大的误差,那么计算量将急速减少。于是提出了基于线性规划的SVM分类。此方法经过数学严格推理,是合理的(因为涉及泛函的知识较多,推理过程放在附录中)。因此产生了基于线性规划一分类、二分类、多分类。此处,我们仅给出基于线性规划的SVM分类的最终形式:111min.(,),1,...,;1;,0LiiLLiijjiiiiiCstKxxjL解出与则得出决策函数1()(,)LiijifxKxx以及阈值。参数C控制着满足条件()fx的样本数量。特别核函数取为径向函数时,参数2越小,精度越高。另外,要提醒注意的是,在求解大规模分类问题得SVM算法实现时,需要以下辅助手段:停机准则:由于分类问题等价于求对偶问题在约束条件下的极值1111max(,)..0,0,1,2,...,LLLiijijijiijLiiijyyKxxstyCiL而KKT条件[(,())1]0()0,1,2,...,iiiiiiywxbCiL是收敛的充分必要条件。因此通过监控KKT条件来得到停机条件110,0,1,2,...,1,0,((,))1,0,1,,LiiijiLiiiijijiyCiLiyyKxxbCiCi这个条件中的不等式不必严格成立,只要在一定误差条件下成立就可以用了。选块算法+分解法1.给定参数0M,0,0k。选取初始工作集0WT,记其对应的样本点的下标集为0J。令kWT第k次更新的工作集,其对应的样本点的下标集为kJ。2.基于工作集kWT,由优化问题1111max(,)..0,0,LLLiijijijiijLiiikjyyKxxstyCiJ求出最优解ˆ{,}jkajJ,构造1(,...,)kkkL按照如下方式:ˆ,0,kjkkjkjJjJ3.如果k已经在精度内满足停机准则,那么以此权系数构造决策函数即可。否则继续下一步。4.在\kTW中找出M个最严重破坏条件11,0,((,))1,0,1,,iLiiiijijiiyyKxxbCiCi加入kW得出新的工作集1kW,相应的下标集记为1kJ。5.重复2)-3),直到样本集耗完为止。序列最小优化算法(SMO)Input:theobserveddataset11(,),...,(,)|,nllijSxyxyxRyR,输入精度要求0及指定核函数(,)Kxy,初始化00,0k。Output:theclassificationofthesesamplesStep1.由更新公式12122211221211111222()(,)(,)2(,)()kkkkkkyEEKxxKxxKxxyyStep2.如果第k步时达到停机要求,取近似解ˆk,否则继续迭代,直到满足停机为止,取为近似解。3.2支持向量回归(SVR)模型对于分类,支持向量机相当于导师样本为有限集的情形。考虑导师集合为不可数的情形,例如训练集可以为形如11(,),...,(,)|,nllijSxyxyxRyR的情形,则演化出支持向量回归概念。支持向量回归也分为线性回归和非线性回归两种,但不是统计学中的线性或者非线性回归了,而是根据是否需要嵌入到高维空间来划分的,我们简述如下:对于给定的样本集S,以及任意给定的0,如果在原始空间nR存在超平面(),,,nfxwxbwRbR使得|()|,(,)iiiiyfxxyS,则称(),fxwxb是样本集合S的-线性回归。与初等代数类似,|()|,(,)iiiiyfxxyS等价于S中任何点(,)iixy到超平面(),fxwxb的距离不超过21||||w。由于我们是分类,所以希望调整超平面的斜率w使得与S中任点(,)iixy距离都尽可能大。也即使得21||||w最大化,这等价于要求2min||||w。于是,-线性回归问题转化为优化问题:212min||||..|,|,1,2,...,iiwstwxbyil于是,引入松弛变量,并使用Lagrange乘子法,得到优化问题的对偶形式:****,111**11min()(),()()2..()0,0,,1,2,...,llliijjijiiiiiijiiliiiiixxystCil对于不可能在原始空间nR就可以线性分离的样本集S,先用一个非线性映射将数据S映射到一个高维特征空间中,使得()S在特征空间H中具有很好的线性回归特征,先在该特征空间中进行线性回归,然后返回到原始空间nR中。这就是支持向量非线性回归。于是,支持向量非线性回归的对偶优化问题如下:****,111**11min()()(,(()()2..()0,0,,1,2,...,))llliijjijiiiiiijiiliiiiixxystCil于是,非线性回归
本文标题:支持向量机及支持向量回归简介
链接地址:https://www.777doc.com/doc-7315263 .html