[1]王书舟,伞 冶.支持向量机的训练算法综述[J].智能系统学报,2008,3(6):467-475.
　WANG Shu-zhou,SAN Ye.A survey on training algorithms for support vector machine[J].CAAI Transactions on Intelligent Systems,2008,3(6):467-475.
点击复制

支持向量机的训练算法综述

《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷: 3 期数: 2008年第6期 页码: 467-475 栏目: 综述 出版日期: 2008-12-25
Title:
A survey on training algorithms for support vector machine
文章编号:
1673-4785(2008)06-0467-09
作者:
王书舟, 伞 冶
哈尔滨工业大学 控制与仿真中心，黑龙江 哈尔滨 150001
Author(s):
WANG Shu-zhou，SAN Ye
Control & Simulation Centre, Harbin Institute of Technology, Harbin 150001, China
关键词:
统计学习理论; 支持向量机; 训练算法
Keywords:
statistical learning theory; support vector machine; training algorithms
分类号:
TP391.9
文献标志码:
A
摘要:
支持向量机（SVM）是在统计学习理论基础上发展起来的新方法，其训练算法本质上是一个二次规划的求解问题.首先简要概述了SVM的基本原理，然后对SVM训练算法的国内外研究现状进行综述，重点分析SVM的缩减算法和具有线性收敛性质的算法，对这些算法的性能进行比较，并且对SVM的扩展算法也进行简单介绍.最后对该领域存在的问题和发展趋势进行了展望.
Abstract:
Support vector machines (SVMs) use new methods that originated in statistical learning theory. Training of an SVM can be formulated as a quadratic programming problem. The principles of SVM have been summarized briefly in this paper. The latest developments in SVM training algorithms in domestic and overseas research were reviewed, especially reduction algorithms and algorithms with linear convergence properties. The performance of these algorithms was then compared, and a brief introduction to a proposed extension of them was given. Finally some problems and potential directions for future research are discussed.
参考文献/References:
［1］VAPNIK V. The nature of statistical learning theory［M］. New York：Springer Verlag,2000.
［2］CRISTIANINI N, SHAWE T J. An introduction to support vector machine［M］.New York:Cambridge University Press, 2000.
［3］DOUMPOS M, ZOPOUNIDIS C. Additive support vector machines for pattern classification［J］. IEEE Trans on Systems, Man, and Cybernetics：Part B, 2007, 37(3): 540-550.
［4］JAYADEVA, KHEMCHANDANI R, CHANDRA S. Twin support vector machines for pattern classification［J］. IEEE Trans on Pattern Analysis and Machine Intelligence, 2007, 29(5): 905-910.
［5］WU Zhili, LI Chunhung, JOSEPH K, et al. Location estimation via support vector regression［J］. IEEE Trans on Mobile Computing, 2007, 6(3): 311-321.
［6］HAO Peiyi, CHIANG J H. Fuzzy regression analysis by support vector learning approach［J］. IEEE Trans on Fuzzy Systems, 2008, 16(2): 428-441.
［7］CHANG C C, HSU C W, LIN C J. The analysis of decomposition methods for support vector machines［J］. IEEE Trans on Neural Networks, 2000, 11 (4): 1003-1008.
［8］LIN C J. On the convergence of the decomposition method for support vector machines［J］. IEEE Trans on Neural Networks, 2001, 12(6): 1288-1298. ［9］NORIKAZU T, TETSUO N. Global convergence of decomposition learning methods for support vector machines［J］. IEEE Trans on Neural Networks, 2006, 17 (6): 1362-1369.
［10］LIN C J. A Formal analysis of stopping criteria of decomposition methods for support vector machines［J］. IEEE Trans on Neural Networks, 2002, 13(5): 1045-1052.
［11］HU W J, SONG Q. An accelerated decomposition algorithm for robust support vector machines［J］. IEEE Trans on Circuits and Systems, 2004, 51(5): 234-240.
［12］DONG Jianxiong, ADAM K, CHING Y S. Fast SVM training algorithm with decomposition on very large data sets［J］. IEEE Trans on Pattern Analysis and Machine Intelligence, 2005, 27(4): 603-618.
［13］QIAO Hong, WANG Yanguo, ZHANG Bo. A simple decomposition algorithm for support vector machines with polynomial time convergence［J］. Pattern Recognition, 2007, 40(9): 2543-2549.
［14］周水生, 詹海生, 周利华. 训练支持向量机的Huber近似算法［J］. 计算机学报, 2005, 28(10): 1664-1670.?
ZHOU Shuisheng, ZHAN Haisheng, ZHOU Lihua. A Huber approximation method for training the support vector machines［J］. Chinese Journal of Computers, 2005, 28(10): 1664-1670.
［15］业 宁, 孙瑞祥,董逸生. 多拉格朗日乘子协同优化的SVM快速学习算法研究［J］. 计算机研究与发展, 2006, 43(3): 442-448.
YE Ning, SUN Ruixiang, DONG Yisheng. SVM fast training algorithm research based on multilagrange multiplier［J］. Journal of Computer Research and Development, 2006, 43(3): 442-448.
［16］杨晓伟, 路 节, 张广全. 一种高效的最小二乘支持向量机分类器剪枝算法［J］. 计算机研究与发展, 2007, 44(7): 1128-1136.
YANG Xiaowei , LU Jie , ZHANG Guangquan. An effective pruning algorithm for least squares support vector machine classifier［J］. Journal of Computer Research and Development, 2007, 44(7): 1128-1136.
［17］PLATT J C. Fast training of support vector machines using sequential minimal optimization［C］//Advances in Kernel Methods－Support Vector Learning.Cambridge, MA:MIT Press, 1999: 185-208.
［18］KEERTHI S, SHEVADE S, BHATTCHARYYA C, et al. Improvements to Platt’s SMO algorithm for SVM classifier design［J］. Neural Computation, 2001, 13(3): 637-649.
［19］KEERTHI S, GILBERT E. Convergence of a generalized SMO algorithm for SVM classifier design［J］. Machine Learning, 2002, 46(1/2/3): 351-360.
［20］LIN C J. Asymptotic convergence of an SMO algorithm without any assumptions［J］. IEEE Trans on Neural Networks, 2002, 13(1): 248-250.
［21］SMOLA A, SCH〖AKO¨〗LKOPF B. A tutorial on support vector regressions［J］. Statistics and Computing, 2004, 14(8): 199-222.
［22］SHEVADE S K, KEERTHI S S, BHATTACHARYYA C. Improvements to SMO algorithm for SVM regression［J］. IEEE Trans on Neural Networks, 2000,11(5): 1188-1193. 
［23］FLAKE G W, LAWRENCE S. Efficient SVM regression training with SMO［J］. Machine Learning, 2002, 46(1/2/3): 271-290.
［24］VOGT M. SMO algorithms for support vector machines without bias term［R］. Darmstadt,Germany:Institute of Automatic Control Laboratory for Control Systems and Process Automation, Technische Univ.Darmstadt,2002.
［25］KEERTHI S S, SHEVADE S K. SMO algorithm for least squares SVM formulations［J］. Neural Computation, 2003, 15(2): 487-507.
［26］ZENG Xiangyan, CHEN Xuewen. SMObased pruning methods for sparse least squares support vector machines［J］. IEEE Trans on Neural Networks, 2005, 16 (6): 1541-1546.
［27］NORIKAZU T, TETSUO N. Rigorous proof of termination of SMO algorithm for support vector machines［J］. IEEE Trans on Neural Networks, 2005, 16(3): 774-776.
［28］GUO J, TAKAHASHI N, NISHI T. A novel sequential minimal optimization algorithm for support vector regression［C］//Proceedings of the 13th International Conference on Neural Information Processing. Hong Kong, China, 2006, 4234: 827-836.
［29］TAKAHASHI N, GUO J, NISHI T. Global convergence of SMO algorithm for support vector regression［J］. IEEE Trans on Neural Networks, 2008, 19(6): 971-982.
［30］CAO L J, KEERTHI S S, ONG C J. Developing parallel sequential minimal optimization for fast training support vector machine［J］. Neurocomputing, 2006, 70(3): 93-104. 
［31］CAO L J, KEERTHI S S, ONG C J, et al. Parallel sequential minimal optimization for the training of support vector machines［J］. IEEE Trans on Neural Networks, 2006, 17(4): 1039-1049.
［32］CHEN P H, FAN R E, LIN C J. A study on SMOtype decomposition methods for support vector machines［J］. IEEE Trans on Neural Networks, 2006, 17(4): 893-908.
［33］BO Liefeng, JIAO Licheng, WANG Ling. Working set selection using functional gain for LS-SVM［J］. IEEE Trans on Neural Networks, 2007, 18(5): 1541-1544.
［34］孙 剑, 郑南宁, 张志华. 一种训练支撑向量机的改进贯序最小优化算法［J］. 软件学报, 2002, 13(10): 2007-2012.
SUN Jian, ZHENG Nanning, ZHANG Zhihua. An improved sequential minimization optimization algorithm for support vector machine training［J］. Journal of Software, 2002, 13(10): 2007-2012.
［35］李建民,张 钹,林福宗. 序贯最小优化的改进算法［J］. 软件学报, 2003,14(5): 918-924.
LI Jianmin, ZHANG Bo, LIN Fuzong. An improvement algorithm to sequential minimal optimization［J］. Journal of Software, 2003, 14(5): 918-924.
［36］张浩然, 韩正之. 回归支持向量机的改进序列最小优化学习算法［J］. 软件学报, 2003, 14(12): 2006-2013.
?ZHANG Haoran, HAN Zhengzhi. An improved sequential minimal optimization learning algorithm for regression support vector machine［J］. Journal of Software, 2003, 14(12): 2006-2013.
?［37］朱齐丹，张 智，邢卓异.支持向量机改进序列最小优化学习算法［J］.哈尔滨工程大学学报，2007，28（2）：183-188.
ZHU Qidan,ZHANG Zhi,XING Zhuoyi.Improved SMO learning method of support vector machine ［J］.Journal of Harbin Engineering University,2007,28(2):183-188.
［38］张浩然, 汪晓东. 回归最小二乘支持向量机的增量和在线式学习算法［J］. 计算机学报, 2006, 29(3):400-406.
ZHANG Haoran, WANG Xiaodong. Incremental and online learning algorithm for regression least squares support vector machine［J］. Chinese Journal of Computers, 2006, 29(3): 400-406.
［39］杨 静，张健沛，刘大昕.基于多支持向量机分类器的增量学习算法研究［J］.哈尔滨工程大学学报，2006,27(1):103-106.
YANG Jing,ZHANG Jianpei,LIU Daxin.Research on incremental learning algorithm with multiple support vector machine classifiers ［J］.Journal of Harbin Engineering University,2006,27(1):103-106.
［40］汪 辉. 增量型支持向量机回归训练算法及在控制中的应用［D］. 杭州: 浙江大学, 2006.
?WANG Hui.Incremental support vector machine regression training algorithm and its application in control ［D］.Hangzhu:zhejiang University,2006.
［41］MA J H, THEILER J, PERKINS S. Accurate online support vector regression［J］. Neural Computation, 2003, 15(11): 2683-2703.
［42］VOJISLAV K, MICHAEL V, HUANG Teming. On the equality of kernel AdaTron and sequential minimal optimization in classification and regression tasks and alike algorithms for kernel machines［C］//European Symposium on Artificial Neural Networks.Bruges，Belgium：Dside Publications,2003: 215-222.
［43］YAAKOV E, SHIE M, RON M. Sparse online greedy support vector regression ［C］//Machine learning:ECMI 2002.Berlin:Springer-Verlag,2002：84-96.
［44］KIVINEN J, SMOLA A J, WILLIAMSON R C. Online learning with kernels［J］. IEEE Trans on Signal Processing, 2004, 52(8): 2165-2176.
［45］SMALE S, YAO Y. Online learning algorithms［J］. Foundations of Computational Mathematics, 2006, 6(3): 145-170.
［46］YING Yiming, ZHOU Dingxuan, Online regularized classification algorithms［J］. IEEE Trans on Information Theory, 2006, 52(11): 4775-4788.
［47］BIANCHI N C, CONCONI A, GENTILE C. On the generalization ability of online learning algorithms［J］. IEEE Trans on Information Theory, 2004, 50(9): 2050-2057.
［48］BIANCHI N C, GENTILE C. Improved risk tail bounds for online algorithms［J］. IEEE Trans on Information Theory, 2008, 54(1): 386-390.
［49］STEINWART I. Sparseness of support vector machines［J］. Journal of Machine Learn Research, 2003, 4(3): 1071-1105.
［50］刘向东, 陈兆乾. 一种快速支持向量机分类算法的研究 ［J］. 计算机研究与发展, 2004, 41(8): 1327-1332. 
?LIU Xiangdong, CHEN Zhaoqian. A fast classification algorithm of support vector machines［J］. Journal of Computer Research and Development, 2004, 41(8): 1327-1332.
［51］WU M, SCH〖AKO¨〗LKOPF B, BAKIR G. A direct method for building sparse kernel learning algorithms［J］. Journal of Machine Learning Research, 2006, 7(4): 603-624.
［52］NGUYEN D, HO T. An efficient method for simplifying support vector machines［C］//International Conference on Machine Learning. Bonn, Germany, 2005: 617-624.
［53］NGUYEN D. HO T. A bottomup method for simplifying support vector solutions［J］. IEEE Trans on Neural Networks, 2006, 17(3): 792-796.
［54］KEERTHI S S, CHAPELLE O, DECOSTE D. Building support vector machines with reduced classifier complexity［J］. Journal of Machine Learning Research, 2006, 7 (7): 1493-1515.
［55］LI Qing, JIAO Licheng, HAO Yingjuan. Adaptive simplification of solution for support vector machine［J］. Pattern Recognition，2007, 40(3): 972-980.
［56］SUMEET A, SARADHI V V, HARISH K. Kernelbased online machine learning and support vector reduction［J］. Neurocomputing, 2008, 71 (9): 1230-1237.
［57］CRAMMER K, KANDOLA J, SINGER Y. Online classification on a budget［C］//Advances in Neural Information Processing Systems.Whistler,Canada，2003: 225-232.
［58］WESTON J, BORDES A, BOTTOU L. Online (and offline) on an even tighter budget［C］//Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics.Barbados, 2005:413-420.
［59］DEKEL O, SHWARTZ S S, SINGER Y. The forgetron: A kernel based perceptron on a fixed budget［C］//Advances in Neural Information Processing Systems.Vancouver,Canada,2005: 259-266.
［60］OFER D, YORAM S.Support vector machines on a budget［C］//Advances in Neural Information Processing Systems.Whistler,Canada,2006: 345-352.
［61］JOACHIMS T. Training linear SVMs in linear time［C］//International Conference on Knowledge Discovery and Data Mining(KDD).New York, USA, 2006: 217- 226.
［62］SHWARTZ S S, SINGER Y, SREBRO N. Pegasos: Primal estimated sub gradient solver for SVM［C］//Proceedings of the Twenty Fourth International Conference on Machine Learning (ICML2007):Corvalis,USA, 2007: 807-814.
［63］SMOLA A J, VISHWANATHAN S V N, QUOC V L. Bundle methods for machine learning［C］//Advances in Neural Information Processing Systems.Vancour,Canada,2008.
［64］CHEN P H, LIN C J, SCHLKOPF B. A tutorial on v-support vector machines［J］. Applied Stochastic Models in Business and Industry, 2005, 21(2): 111-136.
［65］KAZUSHI I. Effects of kernel function on v-support vector machines in extreme cases［J］. IEEE Trans on Neural Networks, 2006, 17(1): 1-9.
［66］MANGASARIAN O L, WILD E W. Multisurface proximal support vector machine classification via generalized eigenvalues［J］. IEEE Trans on Pattern Analysis and Machine Intelligence, 2006, 28(1): 69-74.
［67］LEE Y J, HUANG S Y. Reduced support vector machines: a statistical theory［J］. IEEE Trans on Neural Networks, 2007, 18(1): 1-13.
［68］ANTHONY K, PHILIPPE D W. Comments on “pruning error minimization in least squares support vector machines”［J］. IEEE Trans on Neural Network, 2007, 18(2): 606-609.
［69］JIAO Licheng, BO Liefeng, WANG Ling. Fast sparse approximation for least squares support vector machine［J］. IEEE Trans on Neural Network, 2007, 18(3): 685-697. 
［70］WANG Defeng, DANIEL S Y, ERIC C C T, Weighted mahalanobis distance kernels for support vector machines［J］. IEEE Trans on Neural Networks, 2007, 18(5): 1453-1462.
［71］DU Shuxin, CHEN Shengtan. Weighted support vector machine for classifications［C］//IEEE International Conference on Systems, Man and Cybernetics. Hawaii, USA,2005, 4: 3866-3871.
［72］CAWLEY G C. An empirical evaluation of the fuzzy kernel perceptron［J］. IEEE Trans on Neural Networks, 2007, 18(3): 935-937.
［73］HAO P Y, CHIANG J H. Fuzzy regression analysis by support vector learning approach［J］. IEEE Trans on Fuzzy Systems, 2008, 16(2): 428-441.
［74］CHUANG C C, SU S F, JENG J T, et al. Robust support vector regression networks for function approximation with outliers［J］. IEEE Trans on Neural Networks, 2002, 13(6): 1322-1330.
［75］TRAFALIS T B, GILBERT R C. Robust classification and regression using support vector machines［J］. European Journal of Operational Research, 2006, 173 (3): 893-909.
［76］MITRA P, MURTHY C A, PAL S K. A probabilistic active support vector learning algorithm［J］. IEEE Trans on Pattern Analysis and Machine Intelligence, 2004, 26 (3): 413- 418.
［77］TSANG I W, KWOK J T, ZURADA J M. Generalized core vector machines［J］. IEEE Trans on Neural Networks, 2006, 17(5): 1126-1140.
［78］ZANNI L, SERAFINI T, ZANGHIRATI G. Parallel software for training large scale support vector machines on multiprocessor systems［J］. Journal of Machine Learning Research，2006, 7(7): 1467-1492.
［79］赵春晖, 陈万海, 郭春燕. 多类支持向量机方法的研究现状与分析［J］. 智能系统学报, 2007, 2(4): 11-17.
ZHAO Chunhui, CHEN Wanhai, GUO Chunyan. Research and analysis of methods for multiclass support vector machines［J］. CAAI Transactions on Intelligent Systems, 2007, 2(4): 11-17.
［80］THEODORIDIS S, MAVROFORAKIS M. Reduced convex hulls: a geometric approach to support vector machines［J］. IEEE Signal Processing Magazine, 2007, 24(3): 119-122.
［81］BRUZZONE L, CHI M, MARCONCINI M. A novel transductive SVMs for semi-supervised classification of remote sensing images［J］. IEEE Trans on Geoscience and Remote Sensing, 2006, 44(11): 3363-3373.
［82］ASTORINO A, FUDULI A. Nonsmooth optimization techniques for semisupervised classification［J］. IEEE Trans on Pattern Analysis and Machine Intelligence, 2007, 29(12): 2135-2142.
相似文献/References:
[1]陈小娥,陈昭炯.多类SVM在图像艺术属性分类中的应用研究[J].智能系统学报,2009,4(2):157.
　CHEN Xiao-e,CHEN Zhao-jiong.An application of multiclass SVM in the classification of artistic attributes of images[J].CAAI Transactions on Intelligent Systems,2009,4():157.
[2]黄剑华,唐降龙,刘家锋,等.一种基于Homogeneity的文本检测新方法[J].智能系统学报,2007,2(1):69.
　HUANG Jian-hua,TANG Xiang-long,LIU Jia-feng,et al.A new method for text detection based on Homogeneity[J].CAAI Transactions on Intelligent Systems,2007,2():69.
[3]张 亮,朱振峰,赵 耀,等.基于镜头的鲁棒视频广告检测[J].智能系统学报,2007,2(2):83.
　ZHANG Liang,ZHU Zhen-feng,ZHAO Yao,et al.Video commercial detection based on the robustness of sho t[J].CAAI Transactions on Intelligent Systems,2007,2():83.
[4]赵春晖,陈万海,万? 建.一种改进的多类支持向量机超光谱图像分类方法[J].智能系统学报,2008,3(1):77.
　ZHAO Chun-hui,CHEN Wan-hai,WAN jian.An improved hyperspectral image classification method for? a multiclass support vector machine[J].CAAI Transactions on Intelligent Systems,2008,3():77.
[5]杨志豪,洪　莉,林鸿飞,等.基于支持向量机的生物医学文献蛋白质关系抽取[J].智能系统学报,2008,3(4):361.
　YANG Zhi-hao,HONG L i,L IN Hong-fei,et al.Extraction of information on prote in2prote in interaction from biomedical literatures using an SVM[J].CAAI Transactions on Intelligent Systems,2008,3():361.
[6]刘? 琚,乔建苹.基于学习的超分辨率重建技术[J].智能系统学报,2009,4(3):199.
　LIU Ju,QIAO Jian-ping.Learningbased superresolution reconstruction[J].CAAI Transactions on Intelligent Systems,2009,4():199.
[7]刘 胜,李高云,江 娜.SVM性能的免疫鱼群多目标优化研究[J].智能系统学报,2010,5(2):144.
　LIU Sheng,LI Gao-yun,JIANG Na.Multiobjective optimization of an immune fish swarm algorithm to improve support vector machine performance[J].CAAI Transactions on Intelligent Systems,2010,5():144.
[8]杨振兴,刘久富,孙 琳.不变量的程序潜在错误预测[J].智能系统学报,2010,5(4):327.
　YANG Zhen-xing,LIU Jiu-fu,SUN Lin.Using invariants to predict the potential for errors in programs[J].CAAI Transactions on Intelligent Systems,2010,5():327.
[9]古丽娜孜,孙铁利,伊力亚尔,等.一种基于主动学习支持向量机哈萨克文文本分类方法[J].智能系统学报,2011,6(3):261.
　GU Linazi,SUN Tieli,YI Liyaer,et al.An approach to the text categorization of the Kazakh language based on an active learning support vector machine[J].CAAI Transactions on Intelligent Systems,2011,6():261.
[10]何世钊,杨宣访,陈晓娟.支持向量机与BP网络在火灾图像探测上的比较[J].智能系统学报,2011,6(4):339.
　HE Shizhao,YANG Xuanfang,CHEN Xiaojuan.Comparisons between a support vector machine and BP neural network for video image fire detection[J].CAAI Transactions on Intelligent Systems,2011,6():339.
[11]陈晓华,刘大莲,田英杰,等.可拓支持向量分类机[J].智能系统学报,2018,13(1):147.[doi:10.11992/tis.201610019]
　CHEN Xiaohua,LIU Dalian,TIAN Yingjie,et al.Extension support vector classification machine[J].CAAI Transactions on Intelligent Systems,2018,13():147.[doi:10.11992/tis.201610019]

备注/Memo

收稿日期：2008-06-30.
基金项目：国家自然科学基金资助项目(60474069).
作者简介：
王书舟，男，1972年生，博士研究生，主要研究方向为支持向量机建模、直升机控制与仿真.发表学术论文多篇,6篇被EI检索;伞冶，男，1951年生，教授，博士生导师，中国系统仿真学会理事，主要研究方向为复杂大系统的系统控制与仿真.获国家科技进步二等奖2项，三等奖1项，省部级科技进步奖多项.发表学术论文多篇，40余篇被EI收录.

更新日期/Last Update: 2009-04-03
Copyright © 《 智能系统学报》 编辑部
地址：（150001）黑龙江省哈尔滨市南岗区南通大街145-1号楼 电话：0451- 82534001、82518134　邮箱：tis@vip.sina.com