[1]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.
Copy

A survey on training algorithms for support vector machine

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 3 Number of periods: 2008 6 Page number: 467-475 Column: 综述 Public date: 2008-12-25
Title:
A survey on training algorithms for support vector machine
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
CLC:
TP391.9
DOI:
-
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.
Similar References:

Memo

-

Last Update: 2009-04-03

Copyright © CAAI Transactions on Intelligent Systems