2022年支持向量机及支持向量回归简介 .pdf

《2022年支持向量机及支持向量回归简介 .pdf》由会员分享，可在线阅读，更多相关《2022年支持向量机及支持向量回归简介 .pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、3支持向量机（回归）3.1.1 支持向量机支持向量机（ SVM ）是美国 Vapnik 教授于 1990 年代提出的， 2000年代后成为了很受欢迎的机器学习方法。它将输入样本集合变换到高维空间使得其分离性状况得到改善。它的结构酷似三层感知器，是构造分类规则的通用方法。SVM 方法的贡献在于，它使得人们可以在非常高维的空间中构造出好的分类规则，为分类算法提供了统一的理论框架。作为副产品，SVM 从理论上解释了多层感知器的隐蔽层数目和隐节点数目的作用，因此，将神经网络的学习算法纳入了核技巧范畴。所谓核技巧，就是找一个核函数使其满足，代( , )K x y( , )( ( ),( )K x yxy

2、替在特征空间中内积的计算。因为对于非线性分类，一般是先找一( ),( )xy（个非线性映射将输入数据映射到高维特征空间，使之分离性状况得到很大改观，此时在该特征空间中进行分类，然后再返会原空间，就得到了原输入空间的非线性分类。由于内积运算量相当大，核技巧就是为了降低计算量而生的。特别，对特征空间为 Hilbert空间的情形，设是定义在输入空H( , )K x y间上的二元函数，设中的规范正交基为。如果nRH12( ),( ),.,( ), .nxxx，221( , )( ),( ),kkkkkK x yaxyal那么取即为所求的非线性嵌入映射。由于核函数的定义1( )( )kkkxax( ,

3、)K x y域是原来的输入空间，而不是高维的特征空间。因此，巧妙地避开了计算高维内积所需付出的计算代价。实际计算中，我们只要选定一个，( ), ( )xy（( , )K x y名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - - - 并不去重构嵌入映射。所以寻找核函数（对称且非负）1( )( )kkkxax( , )K x y就是主要任务了。满足以上条件的核函数很多，例如可以取为 d- 阶多项式：，其中为固定元素。( , )(1)dK

4、x yx ygy可以取为径向函数：，其中为固定元素。22( , )exp | /K x yxyy可以取为神经网络惯用的核函数：，其中为固12( , )tanh()K x yc x ycgy定元素。一般地，核函数的存在性只依赖于如何寻找一个平方收敛的非负序列。这ka样的序列在空间的正锥中的序列都满足。但哪一个2l22|0,kklalak最佳还有待于进一步讨论。经验表明，分类问题对于核函数不太敏感。当然，重新构造一个核函数也不是一个简单的事。因此，实际操作中往往就在上述三类中挑出一个来使用就可以了。支持向量机的结构示意图可以表示如下：图 1 支持向量机结构示意图名师资料总结 - - -精品资料欢迎

5、下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 12 页 - - - - - - - - - 其中输入层是为了存贮输入数据，并不作任何加工运算；中间层是通过对样本集的学习，选择；最后一层就是构造分类函数( ,),1,2,3,.,iK x xiL1sgn( ,)Liiiiyy a K x xb整个过程等价于在特征空间中构造一个最优超平面。支持向量机的作用之一就是分类。根据分类的任务，可以划分为一分类，二分类以及多分类。对于多类分类问题，可以用若干种手法将其分解为若干个二分类问题叠加。因此，为了实现支持向量机分

6、类的算法，我们只要针对二分类，从头来给出它的数学原理。3.1.2 支持向量机分类的数学原理设样本集为，我们的目的是寻找一个最(,)|;1,1 ,1,.,niiiixyxRyiI优超平面使得标签为 1 和1 的两类点不仅分开且分得间隔最大。H当在维欧几里德空间中就可以实现线性分离时，也即存在超平面将样本集n按照标签 1 与1 分在两边。由于超平面在维欧几里德空间中的数学表n达式是一个线性方程，其中，为系数向量，为维变量，,0w xbwxn内积，为常数。空间中点到超平面的距离,w xbixL。欲使得最大，等价于最小。于是，|,|(,)|iiw xbd xLw( ,)id x H21|2w得到一个在

7、约束条件下的极值问题21min|2(,)1,1,2,.,iiwyw xbiI引入 Lagrange 乘子，可以解得关于该参变量的方程12(,.,)I名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 12 页 - - - - - - - - - 121,1(),IIiijijijii jQy yx x称之为 Lagrange 对偶函数。其约束条件为,10,0,1,2,.,Iiiii jyiI在此约束条件之下，使得达到最大值的的许多分量为 0，不为 0 的( )Q所对应的样本就

8、称为支持向量。这就是支持向量的来历。iix当在输入空间不能实现线性分离，假设我们找到了非线性映射将样本集映射到高维特征空间中，此时我们(,) |;1,1 ,1,.,niiiix yxRyiIH考虑在中的集合的线性分类，H( (),)|;1,1 ,1,.,niiiixyxRyiI即在中构造超平面，其权系数满足类似的极值问题。由于允许部分点Hw可以例外，那么可以引入松弛项，即改写为：211min|2(,)1,0,1,2,.,LiiiiiiwCyw xbiI最终转化为一个二次型在约束条件下的二次规划问题：11min20, 0(,.,)( ,.,)TTIDcyACC其中，为矩阵。1(,.,)TIyyy

9、( 1,.,1)Tc1,(,)ijiji jIDK x xy y是核函数。( , )K x s名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 12 页 - - - - - - - - - 一分类问题是一个极端情形但却又是非常有用的，它可以表示为如下数学模型：设为空间的有限观测点，找一个以为心，以为半径|,1,.,niixxRiInRaR的包含这些点的最小球体。因此，一分类是对于求一个化合物成分的最小包络曲面的最佳方法。与前面完全相同的手法，设是由某个核函数导出的( , )

10、K x s从输入空间到特征空间中的嵌入映射，最后可以得到二次规划问题11min20, 0(,.,)( ,.,)TTIDcyACC其中，为矩阵。1(,.,)TIyyy( 1,., 1)Tc1,(,)ijiji jIDK x xy y是核函数。此时( , )K x s111( )( , )2( ,)(,)LLLiiijijijif xK x xK x xK x x此时几乎所有的点满足。参数起着控制落在球外点的数目, 变化区2( )f xRC间为：.1/1LC3.1.3 基于线性规划的SVM 分类由于分类问题的自然推理过程都会归结到二次规划求解，计算复杂度相对较高。如果能将其简化为线性规划而且没有较

11、大的误差，那么计算量将急速减少。于是提出了基于线性规划的SVM 分类。此方法经过数学严格推理，是合理的（因为涉及泛函的知识较多，推理过程放在附录中）。因此产生了基于线性规划一分类、二分类、多分类。此处，我们仅给出基于线性规划的SVM 分类的最终形式：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 12 页 - - - - - - - - - 111min.(,),1,., ;1;,0LiiLLiijjiiiiiCstK x xjL解出与则得出决策函数以及阈值。参数控制着满

12、足1( )(,)Liijif xK x xC条件的样本数量。特别核函数取为径向函数时，参数越小，精度越( )f x2高。 另外，要提醒注意的是，在求解大规模分类问题得SVM 算法实现时，需要以下辅助手段：停机准则： 由于分类问题等价于求对偶问题在约束条件下的极值1111max(,).0, 0,1,2,.,LLLiijijijiijLiiijy y K x xstyCiL而 KKT 条件(, ()10()0,1,2,.,iiiiiiywxbCiL是收敛的充分必要条件。因此通过监控 KKT 条件来得到停机条件110, 0,1,2,.,1,0,(,)1, 0,1,LiiijiLiiiijijiyCi

13、Liyy K xxbCiCi这个条件中的不等式不必严格成立，只要在一定误差条件下成立就可以用了。选块算法分解法1.给定参数，。 选取初始工作集，记其对应的样0M00k0WT本点的下标集为。令第次更新的工作集，其对应的样本点的下0JkWTk标集为。kJ2.基于工作集， 由优化问题kWT名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 12 页 - - - - - - - - - 1111max(,).0, 0,LLLiijijijiijLiiikjy y K x xstyCi

14、J求出最优解，构造按照如下方式：?,jkajJ1(,.,)kkkL? ,0,kjkkjkjJjJ3.如果已经在精度内满足停机准则，那么以此权系数构造决策函数即可。k否则继续下一步。4.在中找出个最严重破坏条件kT WM11,0,(,)1, 0,1,iLiiiijijiiyy K xxbCiCi加入得出新的工作集，相应的下标集记为。kW1kW1kJ5 重复 2）3） ，直到样本集耗完为止。序列最小优化算法（ SMO）Input: the observed dataset , 输入精度要求11(,),., (,) |,nllijSxyxyxRyR及指定核函数，初始化，。0( ,)K x y000k

15、Output: the classification of these samplesStep1. 由更新公式12122211221211111222()(,)(,)2(,)()kkkkkkyEEK x xK xxK x xy yStep2. 如果第步时达到停机要求，取近似解，否则继续迭代，直到满k?k足停机为止，取为近似解。3.2 支持向量回归（ SVR）模型对于分类，支持向量机相当于导师样本为有限集的情形。考虑导师集合为不可数的情形，例如训练集可以为形如名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -

16、 - - - - 第 7 页，共 12 页 - - - - - - - - - 11(,),., (,)|,nllijSx yxyxRyR的情形，则演化出支持向量回归概念。支持向量回归也分为线性回归和非线性回归两种，但不是统计学中的线性或者非线性回归了，而是根据是否需要嵌入到高维空间来划分的，我们简述如下：对于给定的样本集, 以及任意给定的，如果在原始空间存在超平S0nR面使得，则( ),nf xw xbwRbR|() |,(,)iiiiyf xxyS称是样本集合的线性回归。( ),f xw xbS与初等代数类似，等价于中任何点到|()|,(,)iiiiyf xxySS(,)iix y超平面的

17、距离不超过。由于我们是分类，所以希( ),f xw xb21 |w望调整超平面的斜率使得与中任点距离都尽可能大。也即使得wS(,)iixy最大化，这等价于要求。于是，线性回归问题转21 |w2min |w化为优化问题：212min|.|,|,1,2,.,iiwstw xbyil于是，引入松弛变量，并使用Lagrange 乘子法，得到优化问题的对偶形式：*,111*11min()(),()()2. .()0,0,1,2,.,llliijjijiiiiiijiiliiiiixxystCil对于不可能在原始空间就可以线性分离的样本集，先用一个非线性映nRS射将数据映射到一个高维特征空间中，使得在特征

18、空间中具有S( )SH很好的线性回归特征，先在该特征空间中进行线性回归，然后返回到原始空间中。这就是支持向量非线性回归。nR于是，支持向量非线性回归的对偶优化问题如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 12 页 - - - - - - - - - *,111*11min()()(,()()2. .()0,0,1,2,.,)llliijjijiiiiii jiiliiiiixxystCil于是，非线性回归问题的实施步骤为：1寻找一个核函数使得，( , )K s

19、 t(,)(),()ijijK x xxx2求优化问题*,111*11min()()(,)()()2. .()0,0,1,2,.,llliijjijiiiiii jiiliiiiiK xxystCil的解。*,ii 3 计算*,1*,1*()(,),()(,),0)0)liijiii jliijii jjjiK xxK xxyCbyC当当（，（，4构造非线性函数。*1( )()(, ),lniijiif xK xxbxRbR3.2.2 支持向量机分类与支持向量回归的关系支持向量机用以分类和回归，两者到底是什么关系？为了建立回归与分类的关系，我们在特征空间中考虑如下的上下移动集合：，( (),1

20、)|(,)iiiiDxyx yS( (),1)|(,)iiiiDxyx yS对于充分大的，与是线性可分离的。于是得出关于与分类。引DDDD入松弛变量，由 SVM 分类方法得到211?min|2?.,)1,)1,0,1,2,.,LiiiiiiiiiwCstw zbzDw zbzDil将目标函数中的改写为特别令, 那么上式变成? w12?(,),ww w2?1w名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - 21121111?mi

21、n|2?., ()11,? , ()11,0,1,2,.,LiiiiiiiiiwCstwxybwxybil而基于观测集，在特征空间中寻找单参数11(,),., (,) |,nllijSxyxyxRyR约束下的回归函数的问题等价于( ), ( )f xwxb211min|2., (), (),0,1,2,.,LiiiiiiiiiwCstywxbwxybil也就是说，回归问题可以通过分类的算法来实现。附录：基于线性规划的分类的合理性设输入向量的空间为，记为上一切绝对值可积函nR(),1,pnLRpnRp数（即一切可测且满足） ，按照通常的加法和数乘，构g|( )|( )npRg xdx成的线性空间

22、。一般地，我们偏好选则一个非线性映射将嵌入到空nR2()nLR间。因为在该 Hilbert 空间中，任意闭子空间的正交补子空间存在问题是一个已解决了的问题，而在还是一个没有被完全解决的问题。如前所述，(),2,pnLRp在此空间中得到的结果，特别是诱导出的核函数是一个非常好的亮点。在有限维空间中，任何距离都是等价的。这一特征也是有限维空间独有的。类似于上面所述，我们可以在有限维空间上赋予范数：nRpL11|npppiixx取遍区间，特别，范数就是通常的最大值范数：p1,L，范数就是通常的绝对值求和范数，范数就是通常的欧1|max|inixx1L2L式范数。如果用表示内积，那么由Holder 不

23、等式，我们得,w x名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 12 页 - - - - - - - - - ，其中是中的一对共轭数。假设一对平|,| | |qpw xwx111pq1,行的超平面为：与，那么，两个平面之间的11( ),f xw xb22( ),fxw xb距离为1212|(,)|qbbd ffw特别，如果上赋予的是范数，则nR1L1212|(,)|bbd ffw于是，导出相应的优化问题,minmax |.(,)1,1,2,.,jjw biiwsty

24、w xbil于是得到线性规划：min.(,)1,1,2,.,1,2,., ,iinjjastyw xbilawawjla bRwR简化了计算。同理，对于不可分离的情况，引入松弛变量后可得1min.(,)1,1,2,.,0,1,2,., ,liiiiinjjjaCstyw xbilawawjla bR wR同理，对于非线性分类的情况，换成核函数11min.(,)1,1,2,.,0,1,2,., ,liilijjjiijnjjjaCstyy K xxbilaajla bRwR同样也采用范数，此时相应的优化问题为L名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

25、- - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 12 页 - - - - - - - - - 1min.(,)1,1,2,.,0,1,2,., ,niiiinjjjjjastyw xbilawawjn a bR wR而非线性问题的松弛条件下的优化问题为：111min.(,)1,1,2,.,0,1,2,., ,nliiiilijjjiijnjjjjjaCstyy K xxbilaajla bRwR无论是那种，都简化了运算。但是由此会付出多大的代价呢？如果记，1SVM，分别为基于上述相应范数得出的支持向量机，我们留作习题，请2SVMSVM大家自己选择一个样本

26、数据库，然后基于该库中数据，对三种在时间复杂度，精度，鲁棒性进行比较，也即填写如下表格：耗费时间Jackknife平均精度鲁棒性（训练集更换）1SVM2SVMSVM小节SVM 的程序会很多，基于不同范数得到不同计算复杂度的程序。选择不同的核函数计算复杂度也会有区别；核函数的选取有研究价值，但难度大。目前见到的核函数对于精度的影响从某种意义上讲是“不大” 。但我们已经从个案中发现，有时差异很大，于是，最优核函数的存在性问题值得深入讨论。SVM 的用途很多，可以取代神经网络的角色（支持向量回归SVR） ；可以求有界集的 “最小体积 ” （一分类问题）；多分类问题。其它的应用还在探索中，与随机图，与粗糙集的结合也已经有人在做，我已经审阅过的期刊论文就是这样。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 12 页 - - - - - - - - -