Canonical duality solution for alternating support vector machine

Yubo Yuan

doi:10.3934/jimo.2012.8.611

Previous Article
A common set of weight approach using an ideal decision making unit in data envelopment analysis
JIMO Home
This Issue
Next Article
A neighboring extremal solution for an optimal switched impulsive control problem

July 2012, 8(3): 611-621. doi: 10.3934/jimo.2012.8.611

Canonical duality solution for alternating support vector machine

Yubo Yuan ^1,

1.	Department of Computer Science and Technology, School of Information Science and Engineering, East China University of Science and Technology, Shanghai 200237, China

Received June 2011 Revised December 2011 Published June 2012

Abstract
Related Papers

Support vector machine (SVM) is one of the most popular machine learning methods and is educed from a binary data classification problem. In this paper, the canonical duality theory is used to solve the normal model of SVM. Several examples are illustrated to show that the exact solution can be obtained after the canonical duality problem being solved. Moreover, the support vectors can be located by non-zero elements of the canonical dual solution.

Keywords: support vector machine, Global optimization, classification, data mining., duality theory.

Mathematics Subject Classification: Primary: 68T10; Secondary:90C2.

Citation: Yubo Yuan. Canonical duality solution for alternating support vector machine. Journal of Industrial & Management Optimization, 2012, 8 (3) : 611-621. doi: 10.3934/jimo.2012.8.611

References:

[1]	J. O. Berger, "Statistical Decision Theory and Bayesian Analysis,", Second edition, (1985). Google Scholar
[2]	P. J. Bickel and K. A. Doksum, "Mathematical Statistics. Basic Ideas and Selected Topics," Second edition,, Prentice-Hall, (2001). Google Scholar
[3]	C. J. C. Burges, A tutorial on support vector machines for pattern recognition,, Data Mining and Knowledge Discovery, 2 (1998), 121. Google Scholar
[4]	O. Chapelle, V. Vapnik, O. Bousquet and S. Mukherjee, Choosing multiple parameters for support vector machines,, Machine Learning, 46 (2002), 131. Google Scholar
[5]	B. Chen and P. T. Harker, Smooth approximations to nonlinear complementarity problems,, SIAM J. Optimization, 7 (1997), 403. Google Scholar
[6]	C. Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems,, Computational Optimization and Applications, 5 (1996), 97. Google Scholar
[7]	C. Chen and O. L. Mangasarian, Smoothing methods for convex inequalities and linear complementarity problems,, Math. Programming, 71 (1995), 51. doi: 10.1016/0025-5610(95)00005-4. Google Scholar
[8]	X. Chen, L. Qi and D. Sun, Global and superlinear convergence of the smoothing newton method and its application to general box constrained variational inequalities,, Math. of Computation, 67 (1998), 519. Google Scholar
[9]	X. Chen and Y. Ye, On homotopy-smoothing methods for variational inequalities,, SIAM J. Control and Optimization, 37 (1999), 589. doi: 10.1137/S0363012997315907. Google Scholar
[10]	G. P. Crespi, I. Ginchev and M. Rocca, Two approaches toward constrained vector optimization and identity of the solutions,, Journal of Industrial and Management Optimization, 1 (2005), 549. Google Scholar
[11]	G. W. Flake and L. Steve, Efficient SVM regression training with SMO,, Machine Learning, 46 (2002), 271. Google Scholar
[12]	K. Fukunaga, "Introduction to Statistical Pattern Recognition,", Second edition, (1990). Google Scholar
[13]	G. Fung and O. L. Mangasarian, Finite Newton method for Lagrangian support vector machine classification,, Neurocomputing, 55 (2003), 39. Google Scholar
[14]	D. Y. Gao, Canonical dual transformation method and generalized triality theory in nonsmooth global optimization,, J. Global Optimization, 17 (2000), 127. Google Scholar
[15]	D. Y. Gao, Perfect duality theory and complete set of solutions to a class of global optimization,, Optimization, 52 (2003), 467. doi: 10.1080/02331930310001611501. Google Scholar
[16]	D. Y. Gao, Complete solutions to constrained quadratic optimization problems,, Journal of Global Optimisation, 29 (2004), 377. doi: 10.1023/B:JOGO.0000048034.94449.e3. Google Scholar
[17]	D. Y. Gao, Sufficient conditions and perfect duality in nonconvex minimization with inequality constraints,, Journal of Industrial and Management Optimization, 1 (2005), 53. Google Scholar
[18]	D. Y. Gao, Complete solutions and extremality criteria to polynomial optimization problems,, Journal of Global Optimization, 35 (2006), 131. doi: 10.1007/s10898-005-3068-5. Google Scholar
[19]	L. Gonzalez, C. Angulo, F. Velasco and A. Catala, Dual unification of bi-class support vector machine formulations,, Pattern Recognition, 39 (2006), 1325. Google Scholar
[20]	A. G. Hadigheh and T. Terlaky, Generalized support set invariancy sensitivity analysis in linear optimization,, Journal of Industrial and Management Optimization, 2 (2006), 1. Google Scholar
[21]	Q. He, Z.-Z. Shi, L.-A. Ren and E. S. Lee, A novel classification method based on hyper-surface,, Mathematical and Computer Modelling, 38 (2003), 395. doi: 10.1016/S0895-7177(03)90096-3. Google Scholar
[22]	C. W. Hsu and C. J. Lin, A simple decomposition method for support vector machines,, Machine Learning, 46 (2002), 291. Google Scholar
[23]	T. Joachims, Making large-scale support vector machine learning practical,, in, (1999). Google Scholar
[24]	S. S. Keerthi, K. B. Duan, S. K. Shevade and A. N. Poo, A fast dual algorithm for kernel logistic regression,, Machine Learning, 61 (2005), 151. Google Scholar
[25]	P. Laskov, Feasible direction decomposition algorithms for training support vector machines,, Machine Learning, 46 (2002), 315. Google Scholar
[26]	Y.-J. Lee, W. F. Hsieh and C. M. Huang, $\epsilon$-SSVR: A smooth support vector machine for $\epsilon$-insensitive regression,, IEEE Transaction on Knowledge and Data Engineering, 17 (2005), 678. doi: 10.1109/TKDE.2005.77. Google Scholar
[27]	Y.-J. Lee and O. L. Mangarasian, SSVM: A smooth support vector machine for classification,, Computational Optimization and Applications, 22 (2001), 5. Google Scholar
[28]	O. L. Mangasarian and D. R. Musicant, Successive overrelaxation for support vector machines,, IEEE Transactions on Neural Networks, 10 (1999), 1032. doi: 10.1109/72.788643. Google Scholar
[29]	T. M. Mitchell, "Machine Learning,", McGraw-Hill Companies, (1997). Google Scholar
[30]	T. Mitchell, Statistical Approaches to Learning and Discovery,, The course of Machine Learning at CMU, (2003). Google Scholar
[31]	D. Montgomery, "Design and Analysis of Experiments,", Third edition, (1991). Google Scholar
[32]	D. J. Newman, S. Hettich, C. L. Blake and C. J. Merz, "UCI Repository of Machine Learning Databases,", University of California, (1998). Google Scholar
[33]	P.-F. Pai, System reliability forecasting by support vector machines with genetic algorithms,, Mathematical and Computer Modelling, 43 (2006), 262. doi: 10.1016/j.mcm.2005.02.008. Google Scholar
[34]	N. Panda and E. Y. Chang, KDX: An Indexer for support vector machines,, IEEE Transaction on Knowledge and Data Engineering, 18 (2006), 748. doi: 10.1109/TKDE.2006.101. Google Scholar
[35]	J. Platt, Sequential minimal optimization: A fast algorithm for training support vector machines,, Advances in Kernel Methods-Support Vector Learning [R], (1999), 185. Google Scholar
[36]	K. Schittkowski, Optimal parameter selection in support vector machines,, Journal of Industrial and Management Optimization, 1 (2005), 465. Google Scholar
[37]	B. Schölkoft, "Support Vector Learning,", R. Oldenbourg Verlag, (1997). Google Scholar
[38]	V. Vapnik, "The Nature of Statistical Learning Theory,", Springer-Verlag, (1995). Google Scholar
[39]	V. Vapnik, The support vector method of function estimation NATO ASI Series,, in, (1998). Google Scholar
[40]	V. Vapnik, An overview of statistical learning theory,, in, (1999). Google Scholar
[41]	V. Vapnik, Three remarks on support vector function estimation,, IEEE transactions on Neural Networks, 10 (1999), 988. Google Scholar
[42]	Z. Y. Wu, H. W. J. Lee, F. S. Bai and L. S. Zhang, Quadratic smoothing approximation to $l_1$ exact penalty function in global optimization,, Journal of Industrial and Management Optimization, 1 (2005), 533. Google Scholar
[43]	K. F. C. Yiu, K. L. Mak and K. L. Teo, Airfoil design via optimal control theory,, Journal of Industrial and Management Optimization, 1 (2005), 133. Google Scholar
[44]	Y. Yuan, J. Yan and C. Xu, Polynomial smooth support vector machine (PSSVM),, Chinese Journal Of Computers, 28 (2005), 9. Google Scholar
[45]	Y. Yuan and T. Huang, A polynomial smooth support vector machine for classification,, Lecture Note in Artificial Intelligence, 3584 (2005), 157. Google Scholar
[46]	Y. Yuan and R. Byrd, Non-quasi-Newton updates for unconstrained optimization,, J. Comput. Math., 13 (1995), 95. Google Scholar
[47]	Y. Yuan, A modified BFGS algorithm for unconstrained optimization,, IMA J. Numer. Anal., 11 (1991), 325. doi: 10.1093/imanum/11.3.325. Google Scholar

show all references

References:

[1]	J. O. Berger, "Statistical Decision Theory and Bayesian Analysis,", Second edition, (1985). Google Scholar
[2]	P. J. Bickel and K. A. Doksum, "Mathematical Statistics. Basic Ideas and Selected Topics," Second edition,, Prentice-Hall, (2001). Google Scholar
[3]	C. J. C. Burges, A tutorial on support vector machines for pattern recognition,, Data Mining and Knowledge Discovery, 2 (1998), 121. Google Scholar
[4]	O. Chapelle, V. Vapnik, O. Bousquet and S. Mukherjee, Choosing multiple parameters for support vector machines,, Machine Learning, 46 (2002), 131. Google Scholar
[5]	B. Chen and P. T. Harker, Smooth approximations to nonlinear complementarity problems,, SIAM J. Optimization, 7 (1997), 403. Google Scholar
[6]	C. Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems,, Computational Optimization and Applications, 5 (1996), 97. Google Scholar
[7]	C. Chen and O. L. Mangasarian, Smoothing methods for convex inequalities and linear complementarity problems,, Math. Programming, 71 (1995), 51. doi: 10.1016/0025-5610(95)00005-4. Google Scholar
[8]	X. Chen, L. Qi and D. Sun, Global and superlinear convergence of the smoothing newton method and its application to general box constrained variational inequalities,, Math. of Computation, 67 (1998), 519. Google Scholar
[9]	X. Chen and Y. Ye, On homotopy-smoothing methods for variational inequalities,, SIAM J. Control and Optimization, 37 (1999), 589. doi: 10.1137/S0363012997315907. Google Scholar
[10]	G. P. Crespi, I. Ginchev and M. Rocca, Two approaches toward constrained vector optimization and identity of the solutions,, Journal of Industrial and Management Optimization, 1 (2005), 549. Google Scholar
[11]	G. W. Flake and L. Steve, Efficient SVM regression training with SMO,, Machine Learning, 46 (2002), 271. Google Scholar
[12]	K. Fukunaga, "Introduction to Statistical Pattern Recognition,", Second edition, (1990). Google Scholar
[13]	G. Fung and O. L. Mangasarian, Finite Newton method for Lagrangian support vector machine classification,, Neurocomputing, 55 (2003), 39. Google Scholar
[14]	D. Y. Gao, Canonical dual transformation method and generalized triality theory in nonsmooth global optimization,, J. Global Optimization, 17 (2000), 127. Google Scholar
[15]	D. Y. Gao, Perfect duality theory and complete set of solutions to a class of global optimization,, Optimization, 52 (2003), 467. doi: 10.1080/02331930310001611501. Google Scholar
[16]	D. Y. Gao, Complete solutions to constrained quadratic optimization problems,, Journal of Global Optimisation, 29 (2004), 377. doi: 10.1023/B:JOGO.0000048034.94449.e3. Google Scholar
[17]	D. Y. Gao, Sufficient conditions and perfect duality in nonconvex minimization with inequality constraints,, Journal of Industrial and Management Optimization, 1 (2005), 53. Google Scholar
[18]	D. Y. Gao, Complete solutions and extremality criteria to polynomial optimization problems,, Journal of Global Optimization, 35 (2006), 131. doi: 10.1007/s10898-005-3068-5. Google Scholar
[19]	L. Gonzalez, C. Angulo, F. Velasco and A. Catala, Dual unification of bi-class support vector machine formulations,, Pattern Recognition, 39 (2006), 1325. Google Scholar
[20]	A. G. Hadigheh and T. Terlaky, Generalized support set invariancy sensitivity analysis in linear optimization,, Journal of Industrial and Management Optimization, 2 (2006), 1. Google Scholar
[21]	Q. He, Z.-Z. Shi, L.-A. Ren and E. S. Lee, A novel classification method based on hyper-surface,, Mathematical and Computer Modelling, 38 (2003), 395. doi: 10.1016/S0895-7177(03)90096-3. Google Scholar
[22]	C. W. Hsu and C. J. Lin, A simple decomposition method for support vector machines,, Machine Learning, 46 (2002), 291. Google Scholar
[23]	T. Joachims, Making large-scale support vector machine learning practical,, in, (1999). Google Scholar
[24]	S. S. Keerthi, K. B. Duan, S. K. Shevade and A. N. Poo, A fast dual algorithm for kernel logistic regression,, Machine Learning, 61 (2005), 151. Google Scholar
[25]	P. Laskov, Feasible direction decomposition algorithms for training support vector machines,, Machine Learning, 46 (2002), 315. Google Scholar
[26]	Y.-J. Lee, W. F. Hsieh and C. M. Huang, $\epsilon$-SSVR: A smooth support vector machine for $\epsilon$-insensitive regression,, IEEE Transaction on Knowledge and Data Engineering, 17 (2005), 678. doi: 10.1109/TKDE.2005.77. Google Scholar
[27]	Y.-J. Lee and O. L. Mangarasian, SSVM: A smooth support vector machine for classification,, Computational Optimization and Applications, 22 (2001), 5. Google Scholar
[28]	O. L. Mangasarian and D. R. Musicant, Successive overrelaxation for support vector machines,, IEEE Transactions on Neural Networks, 10 (1999), 1032. doi: 10.1109/72.788643. Google Scholar
[29]	T. M. Mitchell, "Machine Learning,", McGraw-Hill Companies, (1997). Google Scholar
[30]	T. Mitchell, Statistical Approaches to Learning and Discovery,, The course of Machine Learning at CMU, (2003). Google Scholar
[31]	D. Montgomery, "Design and Analysis of Experiments,", Third edition, (1991). Google Scholar
[32]	D. J. Newman, S. Hettich, C. L. Blake and C. J. Merz, "UCI Repository of Machine Learning Databases,", University of California, (1998). Google Scholar
[33]	P.-F. Pai, System reliability forecasting by support vector machines with genetic algorithms,, Mathematical and Computer Modelling, 43 (2006), 262. doi: 10.1016/j.mcm.2005.02.008. Google Scholar
[34]	N. Panda and E. Y. Chang, KDX: An Indexer for support vector machines,, IEEE Transaction on Knowledge and Data Engineering, 18 (2006), 748. doi: 10.1109/TKDE.2006.101. Google Scholar
[35]	J. Platt, Sequential minimal optimization: A fast algorithm for training support vector machines,, Advances in Kernel Methods-Support Vector Learning [R], (1999), 185. Google Scholar
[36]	K. Schittkowski, Optimal parameter selection in support vector machines,, Journal of Industrial and Management Optimization, 1 (2005), 465. Google Scholar
[37]	B. Schölkoft, "Support Vector Learning,", R. Oldenbourg Verlag, (1997). Google Scholar
[38]	V. Vapnik, "The Nature of Statistical Learning Theory,", Springer-Verlag, (1995). Google Scholar
[39]	V. Vapnik, The support vector method of function estimation NATO ASI Series,, in, (1998). Google Scholar
[40]	V. Vapnik, An overview of statistical learning theory,, in, (1999). Google Scholar
[41]	V. Vapnik, Three remarks on support vector function estimation,, IEEE transactions on Neural Networks, 10 (1999), 988. Google Scholar
[42]	Z. Y. Wu, H. W. J. Lee, F. S. Bai and L. S. Zhang, Quadratic smoothing approximation to $l_1$ exact penalty function in global optimization,, Journal of Industrial and Management Optimization, 1 (2005), 533. Google Scholar
[43]	K. F. C. Yiu, K. L. Mak and K. L. Teo, Airfoil design via optimal control theory,, Journal of Industrial and Management Optimization, 1 (2005), 133. Google Scholar
[44]	Y. Yuan, J. Yan and C. Xu, Polynomial smooth support vector machine (PSSVM),, Chinese Journal Of Computers, 28 (2005), 9. Google Scholar
[45]	Y. Yuan and T. Huang, A polynomial smooth support vector machine for classification,, Lecture Note in Artificial Intelligence, 3584 (2005), 157. Google Scholar
[46]	Y. Yuan and R. Byrd, Non-quasi-Newton updates for unconstrained optimization,, J. Comput. Math., 13 (1995), 95. Google Scholar
[47]	Y. Yuan, A modified BFGS algorithm for unconstrained optimization,, IMA J. Numer. Anal., 11 (1991), 325. doi: 10.1093/imanum/11.3.325. Google Scholar

[1]	Yves Dumont, Frederic Chiroleu. Vector control for the Chikungunya disease. Mathematical Biosciences & Engineering, 2010, 7 (2) : 313-345. doi: 10.3934/mbe.2010.7.313
[2]	Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311
[3]	F.J. Herranz, J. de Lucas, C. Sardón. Jacobi--Lie systems: Fundamentals and low-dimensional classification. Conference Publications, 2015, 2015 (special) : 605-614. doi: 10.3934/proc.2015.0605
[4]	A. K. Misra, Anupama Sharma, Jia Li. A mathematical model for control of vector borne diseases through media campaigns. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1909-1927. doi: 10.3934/dcdsb.2013.18.1909
[5]	W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349
[6]	Habib Ammari, Josselin Garnier, Vincent Jugnon. Detection, reconstruction, and characterization algorithms from noisy data in multistatic wave imaging. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 389-417. doi: 10.3934/dcdss.2015.8.389
[7]	Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094
[8]	Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212
[9]	Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[10]	Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[11]	Mats Gyllenberg, Jifa Jiang, Lei Niu, Ping Yan. On the classification of generalized competitive Atkinson-Allen models via the dynamics on the boundary of the carrying simplex. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 615-650. doi: 10.3934/dcds.2018027
[12]	Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[13]	Carlos Gutierrez, Nguyen Van Chau. A remark on an eigenvalue condition for the global injectivity of differentiable maps of $R^2$. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 397-402. doi: 10.3934/dcds.2007.17.397
[14]	Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617
[15]	Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[16]	Irena PawŃow, Wojciech M. Zajączkowski. Global regular solutions to three-dimensional thermo-visco-elasticity with nonlinear temperature-dependent specific heat. Communications on Pure & Applied Analysis, 2017, 16 (4) : 1331-1372. doi: 10.3934/cpaa.2017065

2019 Impact Factor: 1.366

American Institute of Mathematical Sciences

Canonical duality solution for alternating support vector machine

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

Canonical duality solution for alternating support vector machine

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors