光滑支持向量机的插值光滑技术
|
摘要
作为数据挖掘的一种新方法,支持向量机从统计学习理论发展而来,是基于结构风险最小化原则设计的机器学习算法,很好地解决了传统机器学习算法所遇到的非线性、高维数、局部极小等问题。目前支持向量机已经得到了广泛的研究和应用,其最新的分支是光滑支持向量机,与支持向量机的传统算法和各种变形相比在学习速度上有较大的优势,同时有着更好的推广能力。
该文从支持向量机的理论基础开始,简单阐述了统计学习理论的VC维理论和结构风险最小化原则,介绍了光滑支持向量机的最优化模型;分析了光滑支持向量机的光滑技术,包括Sigmoid函数的积分函数,基于圆弧曲线的分段函数和基于两插值点的插值多项式函数。本文重点研究了基于三个插值点的插值光滑技术,根据插值区间的不同分一般区间和基于原点的对称区间分别作了详细的探讨;给出了在对称区间插值求解最优插值多项式函数的详细求解过程,包括如何建立最优化模型和求解目标光滑函数;获得了最优三次二阶光滑多项式函数和最优四次二阶光滑多项式函数用于拟合光滑支持向量机的正号函数。另外还特别研究了基于三个插值点的一种间接插值情况,获得了一个一阶光滑的多项式函数。对文中重点研究的光滑函数有详细的求解过程;函数性能的理论证明;以及直观的函数曲线图。
本文所研究的光滑函数都有严密的数学推导,以及对正号函数逼近性能的详尽理论证明。数据实验在模拟数据集上训练基于不同的光滑函数构建的各种光滑支持向量分类机;得出的结论是:总体上对正号函数逼近性能越好的光滑函数建立的光滑支持向量分类机的推广能力越好;计算越复杂的光滑函数构建的光滑支持向量分类机就会消耗越多的训练时间;因此必须衡量光滑函数对于正号函数的逼近效果和计算量才能获得最高训练效率和推广能力的光滑支持向量分类机。
Support Vector Machines evolved from the Statistical Learning Theory is a new method for Data Mining. It’s a kind of machine learning algorithms based on Structural Risk Minimization. Comparing to the traditional machine learning algorithms, SVM is a good solution while encountered in non-linear, high dimension, local minimum and so on. SVM has been widely studied and applied recently, Smooth Support Vector Machine, a latest important branch of support vector machines, has better speed in learning comparing with traditional algorithms and deformations of SVM while it achieves better learning generalization ability.
In this paper, theoretical foundation of SVM, mainly include the VC-dimensional theory and the principle of structural risk minimization in Statistical Learning Theory, will be introduced at beginning, as well as the model of SSVM. smooth techniques for SSVM, including the integral function of Sigmoid function initially proposed by SSVM, piecewise function based on sub-arc curve function and piecewise polynomial function will be anlysised. The main content of this paper is interpolation polynomial technology base on three interplation points, two situations including general region and symmertric region on both sides of the origin will be discussed. The courses of how to establish the optimization model and how to sovle the optimize problem for gaining the best polynomial functions in symmetric region will be given. Two 2-order smooth functions with three and four times, applying in SSVM, were got by the optimization model. A particular circumstance of indirectly interpolation base on three interpolation points is considered. For each smooth function in this paper, the theoretical basis, the detailed derivation process and performance are described.
Base on simulated data, numerical experiment training smooth support vector classifier machine with all different kinds of smooth functions will be given. The better approximation for the plus function for the smooth function, the SSVM has better generalization ability, the more complex calculation for the smooth function, more training time will be consumed. So we should find a smooth function can achieve best generalization ability and least training time by balancing the approximation to the plus function and the calculation for the smooth function while in practical application.
该文从支持向量机的理论基础开始,简单阐述了统计学习理论的VC维理论和结构风险最小化原则,介绍了光滑支持向量机的最优化模型;分析了光滑支持向量机的光滑技术,包括Sigmoid函数的积分函数,基于圆弧曲线的分段函数和基于两插值点的插值多项式函数。本文重点研究了基于三个插值点的插值光滑技术,根据插值区间的不同分一般区间和基于原点的对称区间分别作了详细的探讨;给出了在对称区间插值求解最优插值多项式函数的详细求解过程,包括如何建立最优化模型和求解目标光滑函数;获得了最优三次二阶光滑多项式函数和最优四次二阶光滑多项式函数用于拟合光滑支持向量机的正号函数。另外还特别研究了基于三个插值点的一种间接插值情况,获得了一个一阶光滑的多项式函数。对文中重点研究的光滑函数有详细的求解过程;函数性能的理论证明;以及直观的函数曲线图。
本文所研究的光滑函数都有严密的数学推导,以及对正号函数逼近性能的详尽理论证明。数据实验在模拟数据集上训练基于不同的光滑函数构建的各种光滑支持向量分类机;得出的结论是:总体上对正号函数逼近性能越好的光滑函数建立的光滑支持向量分类机的推广能力越好;计算越复杂的光滑函数构建的光滑支持向量分类机就会消耗越多的训练时间;因此必须衡量光滑函数对于正号函数的逼近效果和计算量才能获得最高训练效率和推广能力的光滑支持向量分类机。
Support Vector Machines evolved from the Statistical Learning Theory is a new method for Data Mining. It’s a kind of machine learning algorithms based on Structural Risk Minimization. Comparing to the traditional machine learning algorithms, SVM is a good solution while encountered in non-linear, high dimension, local minimum and so on. SVM has been widely studied and applied recently, Smooth Support Vector Machine, a latest important branch of support vector machines, has better speed in learning comparing with traditional algorithms and deformations of SVM while it achieves better learning generalization ability.
In this paper, theoretical foundation of SVM, mainly include the VC-dimensional theory and the principle of structural risk minimization in Statistical Learning Theory, will be introduced at beginning, as well as the model of SSVM. smooth techniques for SSVM, including the integral function of Sigmoid function initially proposed by SSVM, piecewise function based on sub-arc curve function and piecewise polynomial function will be anlysised. The main content of this paper is interpolation polynomial technology base on three interplation points, two situations including general region and symmertric region on both sides of the origin will be discussed. The courses of how to establish the optimization model and how to sovle the optimize problem for gaining the best polynomial functions in symmetric region will be given. Two 2-order smooth functions with three and four times, applying in SSVM, were got by the optimization model. A particular circumstance of indirectly interpolation base on three interpolation points is considered. For each smooth function in this paper, the theoretical basis, the detailed derivation process and performance are described.
Base on simulated data, numerical experiment training smooth support vector classifier machine with all different kinds of smooth functions will be given. The better approximation for the plus function for the smooth function, the SSVM has better generalization ability, the more complex calculation for the smooth function, more training time will be consumed. So we should find a smooth function can achieve best generalization ability and least training time by balancing the approximation to the plus function and the calculation for the smooth function while in practical application.
引文
[1] Vapnik V.N. An Overview of Statistical Learning Theroy[J]. IEEE Transactions on Neural Networks, 1999, 10(5): 988-999
[2] Vapnik V.N. Chervonenkis A.Y. The Necessary and Sufficient Conditions for the Uniform Convergence of Averages to their Expected Values[J]. Teoriya Veroyatnostei I ee Primeneniya, 1981, 26(3): 543-564
[3] Vidyasagar M. A Theory of Learning and Generalization: With Applications to Neural Networks and Control Systems[M]. New York: Springer-verlag Telos, 1997
[4] Vapnik V.N, Chervoknenkis A.Y. The Necessary and Sufficient Conditions for Consistency of the Method of Empirical Risk Minimization[J]. Pattern Recognition and Image Analysis, 1991, 1(3): 284-305
[5] Vapnik V.N. The Nature of Statistical Learning Theory[M]. New York: Springer-Verlag, 1999
[6] Vapnik V.N. Statistical Learning Theory[M]. New York: John Wiley & Sons, 1998
[7]张学工译.统计学习理论的本质[M].北京:清华大学出版社, 2000
[8]边肇棋,张学工等.模式识别[M].第2版.北京:清华大学出版社, 2000
[9] Vapnik V.N, Levin E. Measuring the VC-dimension of a learning machine[J]. Neural computation, 1994, 6(1): 851-876
[10] Cristianini N, John Shawe-Taylor. An Introduction to Support Vector Machines and other kernel-based learning methods[M]. Canbridge UK: Cambridge University Press, 2000
[11]邓乃扬,田英杰.数据挖掘中的新方法-支持向量机[M].北京:科学出版社, 2004
[12] Vapnik V.N, Chervonenkis A.Y. A Note on one Class of Perceptrons[A]. http://www.kernel-machines.org/publications/VapChe64, last modified at Jan 31 2007
[13] Vapnik V.N, Levin E. Measuring the VC-dimension of a learning machine[J]. Neural computation, 1994, 6: 851-876
[14] Boser B, Guyon I, Vapnik V. A Training Algorithm for Optimal Margin Classsifiers[A]. Proceeding of the 5th Annul ACM Workshop on Computational Learning theory[C], 1992,144-152
[15] Vapnik V.N, Steven E.G, Smola A.J. Support Vector Method for FunctionApproximation[A], Regression Estimation and Signal Processing[C]. In Proceedings of NIPS'1996, 281-287
[16]王国胜,钟义信.支持向量机的若干新进展[J].电子学报, 2001, 29(10): 1397-1400
[17] Lee Yuh-Jye, Mangasasian O.L. SSVM: A Smooth Support Vector Machine for Classification Computer[J]. Optimization and Applications, 2001, 22(1): 5-21
[18] Lee Yuh-Jye, Hsieh W, Huang C.ε- SSVR: A Smooth Support Vector Machine forε-Insensitive Regression[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 5(17): 678-685
[19] Meng Z, Zhou G, Zhu Y, et al. A Smoothing Support Vector Machine Based on Exact Penalty Function[M]. Springer Berlin, 2005
[20] Jiang M, Meng Z, Zhou Z. A Smoothing Support Vector Machine Based on Quarter Penalty Function[C]. 2007 International Conference on Computational Intelligence and Security, 2007,57-59
[21]林继鹏,刘君华,凌振宝.并行支持向量机算法及其应用[J].吉林大学学报,信息科学版, 2004, 22(5): 453-457
[22]赵泽茂,何坤金,胡友进.基于距离的异常数据挖掘算法及其应用[J].计算机应用与软件, 2005, 22(9): 105-107
[23]李昆仑,黄厚宽等.模糊多类支持向量机及其在入侵检测中的应用[J].计算机学报, 2005, 28(2): 274-280
[24]张翔,肖小玲,徐光佑.基于样本之间紧密度的模糊支持向量机方法[J].软件学报, 2006, 17(5): 951-958
[25]张浩然,汪晓东.回归最小二乘支持向量机的增量和在线式学习算法.计算机学报, 2006, 29(3): 400-406
[26]余艳芳,高大启,一种改进的最小二乘支持向量机及其应用[J].计算机工程与科学, 2006, 28(2): 69-71,85
[27]江田汉,束炯.基于LSSVM的混沌时间序列的多步预测[J].控制与决策, 2006, 21(l): 77-80
[28] Cortes C, Vapnik V. Support Vector Networks[J]. Machine Leaming, 1995, 20(1): 273-297
[29] Osuna E, Freund R, Girosi F. Training Support Vector Machines: An Application to FaceDetection[A]. Proc. Computer Vsion and Pattem Reeognition’97[C], 1997, 130-136
[30]袁玉波,严杰,徐成贤.多项式光滑的支撑向量机[J].算机学报, 2005, 28(1): 9-17
[31] Luo L, LIN C, Peng H et al. A Study on Piecewise Polynomial Smooth Approximation to the Plus Function[A]. Proceeding of ICARCV[C] 2006, 2177-2182
[32]熊金志,胡金莲,袁华强等.一类光滑支持向量机新函数的研究[J],电子学报. 2007, 35(2): 366-370
[33]王亚讯,熊金志.支持向量机的5阶光滑函数及其性能分析[J],计算机工程与应用, 2008, 44(20): 73-74
[34]熊金志,袁华强,彭宏.多项式光滑的支持向量机一般模型研究[J].计算机研究与发展, 2008, 45(8): 1346-1353
[35] Joachims T. Making larger-scale support vector machine learning practical [A]. Scholkopf B, Bruges J.C, Smola A.J. Advances in Kernel Methods-Support Vector Learning [C]. Cambridge, Massachusetts: MIT Press, 1999: 169-184
[36] Mangasarian O.L, Musicant D.R. Successive overrelaxation for support vector machines[J]. IEEE Transactions on Neural Networks, 1999, 10(1): 1032-1037
[37] Platt J. Sequential minimal optimization: A fast algorithm for training support vector machines[A]. Scholkopf B,Bruges J.C, Smola A.J. Advances in Kernel Methods-Support Vector Learning[C]. Cambridge, Massachusetts: MIT Press, 1999: 185-208
[38]张学工.关于统计学习理论与支持向量机[J].自动化学报, 2000, 26(1): 32-42
[39]李国正,曾华军.支持向量机导论[M].北京:电子工业出版社, 2005
[40] Mangasarian O.L. Generalized support vector machines[A]. Smola A, Bartlett P,Scholkopf B, et al. Advances in Large Margin Classifiers[C]. Cambridge, MA, 2000: 135-146
[41] Ahlberg J.H, Nilson E.N, Walsh J.L. The Theory of Splines and Their Applications[M]. New York: Academic press, 1967
[42] Carl D.B. A Practical Guide to Splines[M]. New York: Springer Verlag, 1978
[43] Mangasarian O.L. Mathematical programming in neural networks[J]. ORSA Journal on Computing, 1993, 5(4): 349-360
[44] Chen Chunhui, Mangasarian O.L. Smoothing methods for convex inequalities and linear compementarity problems[J]. Mathematical Programming, 1995, 71(1): 51-69
[45] Chen Chunhui, Mangasarian O.L. A class of smoothing functions for nonlinear and mixed complementarity problems. Computational Optimization and Applications[J]. 1996, 5(2): 97-138
[46] FAN YAN-FENG, ZHANG DE-XIAN. Research on Tangent Circular Arc Smooth Support Vector Machine(TCA-SSVM) Algorithm[A]. Proceedings of the 2008 IEEE International Corference on Information and Automation[C], Zhangjiajie China, June 20-23, 2008,1322-1327
[47] Santi Wulan Purnami, Abdullah Embong, Jasni Modh Zain, et al. A New Smooth Support Vector Machine and Its Applications in Diabetes Disease Diagnosis. Journal of Computer Science, 2009, 5(12): 1006-1011
[48]熊金志,李广明,高晓雷等.一阶多项式光滑的支持向量分类机的一般模型[J].计算机工程与应用, 2007, 43(10): 76-78
[49]黄仁泰,熊金志.一个支持向量机的新光滑函数及其性能分析[J].计算机工程与应用, 2008, 44(18): 64-65
[50] Yuan Y. A modified BFGS algorithm for unconstrained optimization[J]. IMA Journal of Numerical Analysis, 1991, 11(4): 325-332
[51] Yuan Y, Byrd R. Non-quasi-Newton updates for unconstrained optimization[J]. Journal of Computing Mathematics, 1995, 13(2): 95-107
[52] Osuna E, Freund R, Girosi F. An Improved Training Algorithm for Support Vector Maehines[A]. Prineipe J, Gile L, Morgan N, et al. Neural Networks for Signal Processing VII-Proceedings of the 1997 IEEE Workshop[C], NewYork, 1997, 276-285
[53]李建民,张拔,林福宗.支持向量机的训练算法[J].清华大学学报(自然科学版), 2003, 43(l): 120~124
[54] Deng Naiyang, Zhang Jianzhong and Zhong Ping. A theoretical analysis on efficiency of some Newton-PCG methods[J]. Science in China Series A Mathematics, 2005, 48(8): 1046-1064
[2] Vapnik V.N. Chervonenkis A.Y. The Necessary and Sufficient Conditions for the Uniform Convergence of Averages to their Expected Values[J]. Teoriya Veroyatnostei I ee Primeneniya, 1981, 26(3): 543-564
[3] Vidyasagar M. A Theory of Learning and Generalization: With Applications to Neural Networks and Control Systems[M]. New York: Springer-verlag Telos, 1997
[4] Vapnik V.N, Chervoknenkis A.Y. The Necessary and Sufficient Conditions for Consistency of the Method of Empirical Risk Minimization[J]. Pattern Recognition and Image Analysis, 1991, 1(3): 284-305
[5] Vapnik V.N. The Nature of Statistical Learning Theory[M]. New York: Springer-Verlag, 1999
[6] Vapnik V.N. Statistical Learning Theory[M]. New York: John Wiley & Sons, 1998
[7]张学工译.统计学习理论的本质[M].北京:清华大学出版社, 2000
[8]边肇棋,张学工等.模式识别[M].第2版.北京:清华大学出版社, 2000
[9] Vapnik V.N, Levin E. Measuring the VC-dimension of a learning machine[J]. Neural computation, 1994, 6(1): 851-876
[10] Cristianini N, John Shawe-Taylor. An Introduction to Support Vector Machines and other kernel-based learning methods[M]. Canbridge UK: Cambridge University Press, 2000
[11]邓乃扬,田英杰.数据挖掘中的新方法-支持向量机[M].北京:科学出版社, 2004
[12] Vapnik V.N, Chervonenkis A.Y. A Note on one Class of Perceptrons[A]. http://www.kernel-machines.org/publications/VapChe64, last modified at Jan 31 2007
[13] Vapnik V.N, Levin E. Measuring the VC-dimension of a learning machine[J]. Neural computation, 1994, 6: 851-876
[14] Boser B, Guyon I, Vapnik V. A Training Algorithm for Optimal Margin Classsifiers[A]. Proceeding of the 5th Annul ACM Workshop on Computational Learning theory[C], 1992,144-152
[15] Vapnik V.N, Steven E.G, Smola A.J. Support Vector Method for FunctionApproximation[A], Regression Estimation and Signal Processing[C]. In Proceedings of NIPS'1996, 281-287
[16]王国胜,钟义信.支持向量机的若干新进展[J].电子学报, 2001, 29(10): 1397-1400
[17] Lee Yuh-Jye, Mangasasian O.L. SSVM: A Smooth Support Vector Machine for Classification Computer[J]. Optimization and Applications, 2001, 22(1): 5-21
[18] Lee Yuh-Jye, Hsieh W, Huang C.ε- SSVR: A Smooth Support Vector Machine forε-Insensitive Regression[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 5(17): 678-685
[19] Meng Z, Zhou G, Zhu Y, et al. A Smoothing Support Vector Machine Based on Exact Penalty Function[M]. Springer Berlin, 2005
[20] Jiang M, Meng Z, Zhou Z. A Smoothing Support Vector Machine Based on Quarter Penalty Function[C]. 2007 International Conference on Computational Intelligence and Security, 2007,57-59
[21]林继鹏,刘君华,凌振宝.并行支持向量机算法及其应用[J].吉林大学学报,信息科学版, 2004, 22(5): 453-457
[22]赵泽茂,何坤金,胡友进.基于距离的异常数据挖掘算法及其应用[J].计算机应用与软件, 2005, 22(9): 105-107
[23]李昆仑,黄厚宽等.模糊多类支持向量机及其在入侵检测中的应用[J].计算机学报, 2005, 28(2): 274-280
[24]张翔,肖小玲,徐光佑.基于样本之间紧密度的模糊支持向量机方法[J].软件学报, 2006, 17(5): 951-958
[25]张浩然,汪晓东.回归最小二乘支持向量机的增量和在线式学习算法.计算机学报, 2006, 29(3): 400-406
[26]余艳芳,高大启,一种改进的最小二乘支持向量机及其应用[J].计算机工程与科学, 2006, 28(2): 69-71,85
[27]江田汉,束炯.基于LSSVM的混沌时间序列的多步预测[J].控制与决策, 2006, 21(l): 77-80
[28] Cortes C, Vapnik V. Support Vector Networks[J]. Machine Leaming, 1995, 20(1): 273-297
[29] Osuna E, Freund R, Girosi F. Training Support Vector Machines: An Application to FaceDetection[A]. Proc. Computer Vsion and Pattem Reeognition’97[C], 1997, 130-136
[30]袁玉波,严杰,徐成贤.多项式光滑的支撑向量机[J].算机学报, 2005, 28(1): 9-17
[31] Luo L, LIN C, Peng H et al. A Study on Piecewise Polynomial Smooth Approximation to the Plus Function[A]. Proceeding of ICARCV[C] 2006, 2177-2182
[32]熊金志,胡金莲,袁华强等.一类光滑支持向量机新函数的研究[J],电子学报. 2007, 35(2): 366-370
[33]王亚讯,熊金志.支持向量机的5阶光滑函数及其性能分析[J],计算机工程与应用, 2008, 44(20): 73-74
[34]熊金志,袁华强,彭宏.多项式光滑的支持向量机一般模型研究[J].计算机研究与发展, 2008, 45(8): 1346-1353
[35] Joachims T. Making larger-scale support vector machine learning practical [A]. Scholkopf B, Bruges J.C, Smola A.J. Advances in Kernel Methods-Support Vector Learning [C]. Cambridge, Massachusetts: MIT Press, 1999: 169-184
[36] Mangasarian O.L, Musicant D.R. Successive overrelaxation for support vector machines[J]. IEEE Transactions on Neural Networks, 1999, 10(1): 1032-1037
[37] Platt J. Sequential minimal optimization: A fast algorithm for training support vector machines[A]. Scholkopf B,Bruges J.C, Smola A.J. Advances in Kernel Methods-Support Vector Learning[C]. Cambridge, Massachusetts: MIT Press, 1999: 185-208
[38]张学工.关于统计学习理论与支持向量机[J].自动化学报, 2000, 26(1): 32-42
[39]李国正,曾华军.支持向量机导论[M].北京:电子工业出版社, 2005
[40] Mangasarian O.L. Generalized support vector machines[A]. Smola A, Bartlett P,Scholkopf B, et al. Advances in Large Margin Classifiers[C]. Cambridge, MA, 2000: 135-146
[41] Ahlberg J.H, Nilson E.N, Walsh J.L. The Theory of Splines and Their Applications[M]. New York: Academic press, 1967
[42] Carl D.B. A Practical Guide to Splines[M]. New York: Springer Verlag, 1978
[43] Mangasarian O.L. Mathematical programming in neural networks[J]. ORSA Journal on Computing, 1993, 5(4): 349-360
[44] Chen Chunhui, Mangasarian O.L. Smoothing methods for convex inequalities and linear compementarity problems[J]. Mathematical Programming, 1995, 71(1): 51-69
[45] Chen Chunhui, Mangasarian O.L. A class of smoothing functions for nonlinear and mixed complementarity problems. Computational Optimization and Applications[J]. 1996, 5(2): 97-138
[46] FAN YAN-FENG, ZHANG DE-XIAN. Research on Tangent Circular Arc Smooth Support Vector Machine(TCA-SSVM) Algorithm[A]. Proceedings of the 2008 IEEE International Corference on Information and Automation[C], Zhangjiajie China, June 20-23, 2008,1322-1327
[47] Santi Wulan Purnami, Abdullah Embong, Jasni Modh Zain, et al. A New Smooth Support Vector Machine and Its Applications in Diabetes Disease Diagnosis. Journal of Computer Science, 2009, 5(12): 1006-1011
[48]熊金志,李广明,高晓雷等.一阶多项式光滑的支持向量分类机的一般模型[J].计算机工程与应用, 2007, 43(10): 76-78
[49]黄仁泰,熊金志.一个支持向量机的新光滑函数及其性能分析[J].计算机工程与应用, 2008, 44(18): 64-65
[50] Yuan Y. A modified BFGS algorithm for unconstrained optimization[J]. IMA Journal of Numerical Analysis, 1991, 11(4): 325-332
[51] Yuan Y, Byrd R. Non-quasi-Newton updates for unconstrained optimization[J]. Journal of Computing Mathematics, 1995, 13(2): 95-107
[52] Osuna E, Freund R, Girosi F. An Improved Training Algorithm for Support Vector Maehines[A]. Prineipe J, Gile L, Morgan N, et al. Neural Networks for Signal Processing VII-Proceedings of the 1997 IEEE Workshop[C], NewYork, 1997, 276-285
[53]李建民,张拔,林福宗.支持向量机的训练算法[J].清华大学学报(自然科学版), 2003, 43(l): 120~124
[54] Deng Naiyang, Zhang Jianzhong and Zhong Ping. A theoretical analysis on efficiency of some Newton-PCG methods[J]. Science in China Series A Mathematics, 2005, 48(8): 1046-1064