Multiple kernel learning, conic duality, and the SMO algorithm

ABSTRACT

While classical kernel-based classifiers are based on a single kernel, in practice it is often desirable to base classifiers on combinations of multiple kernels. Lanckriet et al. (2004) considered conic combinations of kernel matrices for the support vector machine (SVM), and showed that the optimization of the coefficients of such a combination reduces to a convex optimization problem known as a quadratically-constrained quadratic program (QCQP). Unfortunately, current convex optimization toolboxes can solve this problem only for a small number of kernels and a small number of data points; moreover, the sequential minimal optimization (SMO) techniques that are essential in large-scale implementations of the SVM cannot be applied because the cost function is non-differentiable. We propose a novel dual formulation of the QCQP as a second-order cone programming problem, and show how to exploit the technique of Moreau-Yosida regularization to yield a formulation to which SMO techniques can be applied. We present experimental results that show that our SMO-based algorithm is significantly more efficient than the general-purpose interior point methods available in current optimization toolboxes.

REFERENCES

• 1: Andersen, E. D., & Andersen, K. D. (2000). The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm. High Perf. Optimization (pp. 197--232).
• 2: Bertsekas, D. (1995). Nonlinear programming. Nashua, NH: Athena Scientific.
• 3: Paul S. Bradley , O. L. Mangasarian, Feature Selection via Concave Minimization and Support Vector Machines, Proceedings of the Fifteenth International Conference on Machine Learning, p.82-90, July 24-27, 1998
• 4: Brent, R. P. (1973). Algorithms for minimization without derivatives. Englewood Cliffs, NJ: Prentice-Hall.
• 5: Olivier Chapelle , Vladimir Vapnik , Olivier Bousquet , Sayan Mukherjee, Choosing Multiple Parameters for Support Vector Machines, Machine Learning, v.46 n.1-3, p.131-159, 2002 [doi>10.1023/A:1012450327387]
• 6: Grandvalet, Y., & Canu, S. (2003). Adaptive scaling for feature selection in SVMs. Neural Information Processing Systems. Cambridge, MA: MIT Press.
• 7: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 8: S. S. Keerthi , S. K. Shevade , C. Bhattacharyya , K. R. K. Murthy, Improvements to Platt's SMO Algorithm for SVM Classifier Design, Neural Computation, v.13 n.3, p.637-649, March 2001 [doi>10.1162/089976601300014493]
• 9: Gert R. G. Lanckriet , Nello Cristianini , Peter Bartlett , Laurent El Ghaoui , Michael I. Jordan, Learning the Kernel Matrix with Semidefinite Programming, The Journal of Machine Learning Research, 5, p.27-72, 12/1/2004
• 10: Claude Lemaréchal , Claudia Sagastizábal, Practical Aspects of the Moreau--Yosida Regularization: Theoretical Preliminaries, SIAM Journal on Optimization, v.7 n.2, p.367-385, 1997 [doi>10.1137/S1052623494267127]
• 11: Lobo, M. S., Vandenberghe, L., Boyd, S., & Léébret, H. (1998). Applications of second-order cone programming. Lin. Alg. and its Applications, 284, 193--228.
• 12: Ong, S., Smola, A. J., & Williamson, R. C. (2003). Hyperkernels. Neural Information Processing Systems. Cambridge, MA: MIT Press.
• 13: John C. Platt, Fast training of support vector machines using sequential minimal optimization, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999