×

Subgradient-based neural network for nonconvex optimization problems in support vector machines with indefinite kernels. (English) Zbl 1371.37145

Summary: Support vector machines (SVMs) with positive semidefinite kernels yield convex quadratic programming problems. SVMs with indefinite kernels yield nonconvex quadratic programming problems. Most optimization methods for SVMs rely on the convexity of objective functions and are not efficient for solving such nonconvex problems. In this paper, we propose a subgradient-based neural network (SGNN) for the problems cast by SVMs with indefinite kernels. It is shown that the state of the proposed neural network has finite length, and as a consequence it converges toward a singleton. The coincidence between the solution and the slow solution of SGNN is also proved starting from the initial value of SGNN. Moreover, we employ the Łojasiewicz inequality to exploit the convergence rate of trajectory of SGNN. The obtained results show that each trajectory is either exponentially convergent, or convergent in finite time, toward a singleton belonging to the set of constrained critical points through a quantitative evaluation of the Łojasiewicz exponent at the equilibrium points. This method is easy to implement without adding any new parameters. Three benchmark data sets from the University of California, Irvine machine learning repository are used in the numerical tests. Experimental results show the efficiency of the proposed neural network.

MSC:

37N35 Dynamical systems in control
68T10 Pattern recognition, speech recognition
90C26 Nonconvex programming, global optimization

Software:

Pegasos
Full Text: DOI

References:

[1] J. P. Aubin, <em>Differential Inclusions</em>,, Springer-Verlag (1984) · Zbl 0538.34007 · doi:10.1007/978-3-642-69512-4
[2] J. P. Aubin, <em>Set-Valued Analysis</em>,, MA: Birkauser (1990)
[3] E. K. P. Chong, An analysis of a class of neural networks for solving linear programming problems,, Automatic Control, 44, 1995 (1999) · Zbl 0957.90087 · doi:10.1109/9.802909
[4] J. Chen, Training SVM with indefinite kernels,, In Proceedings of the 25th International Conference on Machine Learning, 136 (2008) · doi:10.1145/1390156.1390174
[5] F. H. Clarke, <em>Optimization and Non-smooth Analysis</em>,, Wiley (1969)
[6] L. Fengqiu, Design of natural classification kernels using prior knowledge,, Fuzzy Systems, 20, 135 (2012)
[7] A. F. Filippove, <em>Differential Equations with Discontinuous Right-Hand Side, Mathematics and Its Applications (Soviet Series)</em>,, Boston (1988) · Zbl 0664.34001
[8] M. Forti, Convergence of neural networks for programming problems via a nonsmooth Łojasiewicz inequality,, Neural Networks, 17, 1471 (2006)
[9] M. Forti, Absolute stability of analytic neural networks: An approach based on finite trajectory length,, Circuits System I, 51, 2460 (2004) · Zbl 1371.93151 · doi:10.1109/TCSI.2004.838143
[10] B. Haasdonk, Feature space interpretation of svms with indefinite kernels,, Pattern Analysis and Machine Intelligence, 27, 482 (2005) · doi:10.1109/TPAMI.2005.78
[11] M. Hein, Hilbertian metrics and positive definite kernels on probability measures,, In Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics, 136 (2005)
[12] J. J. Hopfield, “Neural” computation of decisions in optimization problems,, Biological cybernetics, 52, 141 (1985) · Zbl 0572.68041
[13] R. Luss, Support vector machine classification with indefinite kernels,, Mathematical Programming Computation, 1, 97 (2009) · Zbl 1191.68511 · doi:10.1007/s12532-009-0005-5
[14] I. Mierswa, <em>Making Indefinite Kernel Learning Practical</em>,, Technical report (2006)
[15] J. C. Platt, Fast training of support vector machines using sequential minimal optimization,, In Advances in Kernel Methods, 185 (1999)
[16] T. Rockafellar, <em>Variational Analysis</em>,, Springer-Verlag (1998) · Zbl 0888.49001 · doi:10.1007/978-3-642-02431-3
[17] S. Shalev-Shwartz, Pegasos: Primal estimated sub-gradient solver for SVM,, Math. Program., 127, 3 (2011) · Zbl 1211.90239 · doi:10.1007/s10107-010-0420-4
[18] H. Saigo, Protein homology detection using string alignment kernels,, Bioinformatics, 20, 1682 (2004) · doi:10.1093/bioinformatics/bth141
[19] B. Schölkopf, <em>Learning with Kernels</em>,, MIT (2002)
[20] B. Schölkopf, <em>Prior Knowledge in Support Vector Kernels</em>,, MIT (1998)
[21] V. N. Vapnik, <em>Statistical Learning Theory</em>,, Wiley (1998) · Zbl 0935.62007
[22] B. Wei, Subgradient-based neural networks for nonsmooth nonconvex optimization problems,, Circuits and Systems I: Regular Papers, 55, 2378 (2008) · doi:10.1109/TCSI.2008.920131
[23] Y. Xia, A one-layer recurrent neural network for support vector machine learning,, Systems, 34, 1621 (2004) · doi:10.1109/TSMCB.2003.822955
[24] S. Ziye, Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems,, Journal of Industrial and Management Optimization, 10, 871 (2014) · Zbl 1283.49021 · doi:10.3934/jimo.2014.10.871
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.