高维支持向量机的一些新发展.pdf

319Journal of BeijNormal University(Natural Science)59(2)2023-04北京师范大学自然科学版）高维支持向量机的一些新发展史宏炜饶昊宸郭旭（北京师范大学统计学院，10 0 8 7 5，北京）摘要又对高维支持向量机（SVM）的一些新发展如非凸惩罚SVM,L范数SVM的误差界以及SVM在充分性降维中的应用进行了介绍；通过数值模拟和实例分析，展示了这些新方法在有限样本时的表现；讨论了一些可能的方向和问题。关键词二元响应变量；支持向量机；惩罚估计；误差界；变量选择；充分性降维中图分类号0212D0I:10.12202/j.0476-0301.20223140引言分类是机器学习领域的一个核心问题.支持向量机（supportvectormachine，SVM)是一种功能强大、精度高并且灵活性强的分类算法，自被提出以后就受到了众多学者的关注和研究.早期研究及应用中，SVM通常利用样本数量的所有特征来建立分类规则.随着数据收集能力的提升，研究所获取的数据往往包含大量的复杂特征；特征数量甚至远大于样本量，只有小部分特征有助于分类研究，其他特征都是余的.研究时利用全部特征可能会产生大量的误差积累，从而对分类结果产生不利的影响.例如：垃圾邮件分类问题，尽管存在大量单词，但真正有助于分类的很少；在实际中，有效的单词是未知的，因此需要构建合适的特征选择方法，这样不仅可减少计算量，提高分类器的预测精度，同时还可简化模型并提供合理解释。SVM特征选择问题已得到了广泛研究.Weston等2 提出了一种尺度法来选择重要特征；Guyon等3提出了SVM递归特征消除法.Wahba4论证了标准SVM可以纳入正则化框架中：合页损失加L惩罚，称作L范数SVM；由于L范数SVM无法获得稀疏解，不能自动选择变量，因此其泛化性能会因包含过多穴余特征而受到不利影响5。一些学者提出了使用稀疏惩罚来代替L惩罚，从而同时实现变量选择和参数估计，例如：Bradley等6、Zhu等17,以及Wegkamp等8 考虑了L范数SVM;Wang等9-10 提出了结合L,与L惩罚的SVM,即elasticnet惩罚SVM;ZouI提出了使用adaptiveLASSO的惩罚SVM.为消除L,惩罚可能造成的偏差，Zhang等12、Becker等13,以及Park等14考虑了基于非凸惩罚SCAD的SVM.对于特征选择方法，一个关键的理论问题是能否将真正重要的特征以很大的概率选择出来。鉴于此，在固定维数下，Park等14提出了SCAD惩罚SVM的Oracle性质，即估计分类器与真实分类器表现渐近一致；Zhang等15在超高维下建立了一般的非凸惩罚SVM的Oracle性质，如SCAD或MCP.然而这种模型选择一致性的结果，在很大程度上依赖于能否正确选择和调整参数.Zhang等16 进行了深人的理论分析，提出了高维情形的SVM信息准则，同时证明了即使特征数量以样本量的指数阶发散时，该准则也具有模型选择一致性。近些年，SVM系数向量估计值的统计性质受到了众多学者的关注及研究.SVM系数向量不仅能够用以预测新观测的类别，还可对特征的相对重要性提供关键信息.在固定维数下，Koo等17 发现了L,范数SVM系数向量的新型Bahadur表示，并提出了估计系数的渐近正态性.Peng等18 在高维情形下，证明了L范数SVM系数的估计值所对应的L误差界为O,Vqln(p/n),式中q为真正重要的特征的个数，p为总的特征个数，n表示样本量.另一方面在当今大数据时代，所收集数据的规模变得非常巨大。为此，Lian等19提出了纠偏L范数SVM的分布式估计量，并证明了所提分布式估计量的L,和L误差界分别为O,(p in(p/n)和O,(Vpln(p/n).*国家自然科学基金资助项目（12 0 7 10 38）+通信作者：郭旭（198 8），男，博士，教授.研究方向：复杂统计推断.E-mail：x u s t a t 12 b n u.e d u.c n收稿日期：2 0 2 2-0 4-30320第59 卷北京师范大自然科学版）在开展SVM理论性质研究的同时，SVM还被广泛应用于统计学实践中，特别是在充分性降维中发挥了重要作用。充分性降维是处理高维数据的有力统计方法之一，此类方法旨在寻求自变量的一些低维组合，并用以刻画自变量与响应变量的结构关系，从而达到降维的目的.自Li20提出切片逆回归方法后，充分性降维得到了长足发展；Li等2 1将SVM引人充分性降维领域，提出了主SVM方法；Shin等2 2 进一步提出了主加权SVM,以便对二分类问题进行降维，有效解决了传统充分性降维算法只能得到一个降维方向的问题.1L,范数文SVM现考虑二分类问题,设随机样本(Y,X,i=1,2,n的总体样本为(Y,X),响应变量Y,E(1,-1)，自变量X,=(Xio,Xi1,.,Xip)T=(Xio,(X,),式中Xio=1对应截距项.对于任意k维向量，a=(ai,ak)eRk,定义如下记号以代表向量范数：1/m1)l l/m=am=12)l ll=max(lai,.,lall;3 ll=k1(a;0).考虑分类超平面为线性的情形，定义h(X;)=XT,式中=(o,(.)以及_=(1,2,)T.SVM的基本思想是求解能够正确分类并且间隔最大的分类超平面.对于线性可分的数据集来说，可将其转化为求解约束优化问题2maxS.t.:Yh(X;)1,i=1,.,n.注意到最大化2/IB-Il,与最小化IB-I呢/2 是等价的，因此可进一步改为优化问题1minB.I,2S.t.:Y,h(X;)1,i=1,.,n.这是一个凸二次规划问题.实践中，数据往往是线性不可分的。解决方案是对每个样本点(X,Y)引人一个松弛变量$0,将硬间隔最大化SVM变为软间隔最大化SVM,即nmin C5:+B-12i=1S.t.:s,1-Y,h(X;),s0,i=1,.,n.式中C是一个调整参数，且C0.软间隔最大化SVM又可等价为最小化目标nmin n(1)i=1式中：形如(1-u)+=max(1-u,0)称为合页损失函数；入是调整参数，用以平衡损失和惩罚。故此，传统SVM可表示为合页损失结合L惩罚的形式.式（1)中，基于参数平方和的惩罚被称作ridge惩罚，该惩罚可将拟合系数收缩，使之趋近于0,但不会恰好为0，因而无法进行变量选择。当数据中存在大量穴余特征时，会导致较大的误差累积，从而对分类结果产生不利的影响，因此需要考虑更稀疏的估计算法。2L,范数SVM为得到稀疏估计，即自动将某些系数估计为0，可将式（1)的L惩罚替换为L惩罚，从而得到L范数SVM，即最小化目标(a)=argmin I.,(,)=argmin n(2)i=1同样通过引人松弛变量，可将式（2)转化为如下线性规划问题7;之小min55Bi=1j=1s.t.:$,0,i=1,2,.,n,s,1-YX,i=1,2,.,n,5j,5,-j,j=1,2,.,p.相比标准L范数SVM,L范数SVM可以将某些系数估计为0，从而达到变量选择的目的。因而L范数SVM更具优势，并且在诸多领域得到了广泛应用，特别是高维情形.而L惩罚可能存在偏差，因此也有学者建议使用非凸惩罚.3高维情形下的SVM3.1丰非凸惩罚的SVM对于第1章的二分类数据，Zhang等15考虑了一种具有非凸惩罚的线性加权SVM,其目标为nQ()=nW.(1-YX(B),+Z p.(IB,),(3)=1j=1式中：W为权重参数，当Y,=1时W,=w,Y,=-1时W,=1-w且0 w1,使得lim P,(t)=n,当t-0+0ta时,pi,(t)入,-t/a,当ta时,p,(t)=0.满足以上2 个条件的常见非凸惩罚是SCAD和MCP.SCAD定义为a/l-(2+2)/2P,(IBI)=AIB|I(OBIa/),a2;2MCP定义为MCP定义为a2BP,(IBI)=BI(0II 1.2Zhang等15建立了非凸惩罚SVM的局部Oracle性质.令Oracle估计量是式(3)中Q()在已知重要特征下的最小值，B,()是由Q()在调整参数入下的局部最小值构成的集合.在一定条件下，当n8时，Oracle估计量的概率满足P(eB,()1.同时也证明当变量个数以样本量的指数阶增长时，非凸惩罚SVM依旧具有局部Oracle性质.由于Q()是分段的，从而导致在有限样本的情形下经验合页损失可能有多个最小值.为了解决这个问题，Zhang等15使用了Zou等2 3 所提出的局部线性逼近算法，并证明了仅需2 次迭代即可趋于1的概率所获得的具有Oracle性质的估计量.这种收敛结果在超高维设定下也成立。3.2L范数SVM估计系数的误差界3.2.1超高维情形下L范数SVM估计系数的L误差界学者们比较关注SVM估计系数（也称权重向量）的统计特性.不同于现有大多数关于SVM的理论研究,Peng等18 对L,范数SVM在超高维情形下的系数估计误差理论进行了深入研究，并对超高维情形下，L范数SVM估计系数的L,误差界为O,(Vqln(p/n)进行了证明。Peng等18 考虑了基于线性SVM的二分类问题（具体参见第2 章）.其主要目标是在pn 时获得IB()-Il的误差界，其中是总体形式下所对应的最小值，且有=argmin L()=argmin E(1-YX).(4)假设=(,i,)是稀疏的，即大部分变量系数为0.在超高维设定下这是一个合理的假设.定义重要特征的指标集为T=(1jp：)0)，T的大小记为|T|=q.根据Koo等17 的研究，可以给出总体合页损失L()的梯度向量和黑塞矩阵.定义S(B)=-E(I(1-YX0)YX)为p+1维的梯度向量，以及H()=E(S(1-YX)XXT)(5)为(p+1)(p+1)的黑塞矩阵，式中：I()为示性函数；;S()为 Dirac delta 函数.为了得到()的良好性质，需要选择合适的调整参数入，有P(clS()l)1-,(6)式中:S()=-n-1I(1-Y,XT0)Y,X;c1为给定的=1常数；指小概率。Peng 等18 证明了一些正则条件下入=CV2A()In(p/n)可满足式(6),其中A()0,是一个常量.合页损失是不连续的，这使得推导IB()-l的误差界具有更大的挑战性.Peng等利用经验过程的理论方法，建立了合页损失函数的理论结果，即1B(h)ni=1i=1(Z(1-X(+YXh)-Z(1-X().)n1=1式中h=-()ER+I.则在一定条件下,对于所有充分大的n，有B(h)2qlnpPsup(1+2CiVM)1,因此该结果证明了n1i=1以很高的概率接近它的期望值，从而消除了合页损失的非连续性问题.基于前文关于调整参数的选取以及建立合页损失近似结果的讨论，Peng等给出了L范数SVM系数向量()的误差界为I/B(a)-llz=O,(Vqln(p/n).Peng等所获得的关于L范数SVM的理论结果，为Zhang等15所提出的基于非凸惩罚SVM进行变量选择的算法提供了合理的初值，可以保证系数估计量满足超高维情形下的Oracle性质，从而识别出重要变量.3.2.2基于SVM纠偏LASSO估计量的误差界基K)且322第59 卷北京师范大自然科学版）于Peng等18 的工作，Lian等19进一步研究了L范数SVM系数的分布式估计.Lian等提出分治算法的基本思想是：将数据分割为多个部分，对每一部分数据采用一个标准估计方法，获得相应的局部估计量；通过简单平均的方法将这些局部估计量组合成一个聚合估计量，聚合估计量与基于所有观测数据所获得的中心估计量具有相似统计特性，并且聚合操作能够有效地减少估计量的方差，但无法降低偏差。对此Lian等在聚合之前进行了纠偏操作，建立了SVM的纠偏LASSO估计量，进一步推广了Peng等的有偏L,范数SVM的估计结果.Lian等对纠偏LASSO的分布式估计研究与其他学者有很大不同.Lee等2 4基于VanDe Geer等2 5所提出的纠偏LASSO估计量，建立了分