资源描述:
《序贯最小优化的改进算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、1000-9825/2003/14(05)0918©2003JournalofSoftware软件学报Vol.14,No.5∗序贯最小优化的改进算法+李建民,张钹,林福宗(清华大学计算机科学与技术系,北京100084)(清华大学智能技术与系统国家重点实验室,北京100084)AnImprovementAlgorithmtoSequentialMinimalOptimization+LIJian-Min,ZHANGBo,LINFu-Zong(DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing1000
2、84,China)(StateKeyLaboratoryofIntelligentTechnologyandSystems,TsinghuaUniversity,Beijing100084,China)+Correspondingauthor:Phn:86-10-62782266ext8426,E-mail:ljm@s1000e.cs.tsinghua.edu.cnhttp://www.cs.tsinghua.edu.cnReceived2002-01-07;Accepted2002-08-13LiJM,ZhangB,LinFZ.Animprovementalgorithmtos
3、equentialminimaloptimization.JournalofSoftware,2003,14(5):918~924.http://www.jos.org.cn/1000-9825/14/918.htmAbstract:Atpresentsequentialminimaloptimization(SMO)algorithmisaquiteefficientmethodfortraininglarge-scalesupportvectormachines(SVM).However,thefeasibledirectionstrategyforselectingwork
4、ingsetsmaydegradetheperformanceofthekernelcachemaintainedinSMO.AfteraninterpretationofSMOasthefeasibledirectionmethodinthetraditionaloptimizationtheory,anovelstrategyforselectingworkingsetsappliedinSMOispresented.Basedontheoriginalfeasibledirectionselectionstrategy,thenewmethodtakesbothreduct
5、ionoftheobjectfunctionandcomputationalcostrelatedtotheselectedworkingsetintoconsiderationinordertoimprovetheefficiencyofthekernelcache.Itisshownintheexperimentsonthewell-knowndatasetsthatcomputationofthekernelfunctionandtrainingtimeisreducedgreatly,especiallyfortheproblemswithmanysamples,supp
6、ortvectorsandnon-boundsupportvectors.Keywords:machinelearning;supportvectormachine;sequentialminimaloptimization;cache摘要:序贯最小优化(sequentialminimaloptimization,简称SMO)算法是目前解决大量数据下支持向量机(supportvectormachine,简称SVM)训练问题的一种十分有效的方法,但是确定工作集的可行方向策略会降低缓存的效率.给出了SMO的一种可行方向法的解释,进而提出了一种收益代价平衡的工作集选择方法,综合考虑与工
7、作集相关的目标函数的下降量和计算代价,以提高缓存的效率.实验结果表明,该方法可以提高SMO算法的性能,缩短SVM分类器的训练时间,特别适用于样本较多、支持向量较多、非有界支持向量较多的情况.关键词:机器学习;支持向量机;序贯最小优化;缓存∗SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.60135010(国家自然科学基金);theNationalGrandFundamentalResearch97