Discriminant kernel and regularization parameter learning via semidefinite programming

ABSTRACT

Regularized Kernel Discriminant Analysis (RKDA) performs linear discriminant analysis in the feature space via the kernel trick. The performance of RKDA depends on the selection of kernels. In this paper, we consider the problem of learning an optimal kernel over a convex set of kernels. We show that the kernel learning problem can be formulated as a semidefinite program (SDP) in the binary-class case. We further extend the SDP formulation to the multi-class case. It is based on a key result established in this paper, that is, the multi-class kernel learning problem can be decomposed into a set of binary-class kernel learning problems. In addition, we propose an approximation scheme to reduce the computational complexity of the multi-class SDP formulation. The performance of RKDA also depends on the value of the regularization parameter. We show that this value can be learned automatically in the framework. Experimental results on benchmark data sets demonstrate the efficacy of the proposed SDP formulations.

REFERENCES

• 1: Andreas Argyriou , Raphael Hauser , Charles A. Micchelli , Massimiliano Pontil, A DC-programming algorithm for kernel selection, Proceedings of the 23rd international conference on Machine learning, p.41-48, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143850]
• 2: Francis R. Bach , Gert R. G. Lanckriet , Michael I. Jordan, Multiple kernel learning, conic duality, and the SMO algorithm, Proceedings of the twenty-first international conference on Machine learning, p.6, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015424]
• 3: G. Baudat , F. Anouar, Generalized Discriminant Analysis Using a Kernel Approach, Neural Computation, v.12 n.10, p.2385-2404, October 2000 [doi>10.1162/089976600300014980]
• 4: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 5: Crammer, K., Keshet, J., & Singer, Y. (2003). Kernel design using boosting. NIPS (pp. 537--544).
• 6: Nello Cristianini , John Shawe-Taylor, An introduction to support Vector Machines: and other kernel-based learning methods, Cambridge University Press, New York, NY, 1999
• 7: Glenn Fung , Murat Dundar , Jinbo Bi , Bharat Rao, A fast iterative algorithm for fisher discriminant using heterogeneous kernels, Proceedings of the twenty-first international conference on Machine learning, p.40, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015409]
• 8: Golub, G. H., & Van Loan, C. F. (1996). Matrix computations. The Johns Hopkins University Press. Third edition.
• 9: J. J. Hull, A Database for Handwritten Text Recognition Research, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.5, p.550-554, May 1994 [doi>10.1109/34.291440]
• 10: Tony Jebara, Multi-task feature and kernel selection for SVMs, Proceedings of the twenty-first international conference on Machine learning, p.55, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015426]
• 11: Seung-Jean Kim , Alessandro Magnani , Stephen Boyd, Optimal kernel selection in Kernel Fisher discriminant analysis, Proceedings of the 23rd international conference on Machine learning, p.465-472, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143903]
• 12: Gert R. G. Lanckriet , Tijl De Bie , Nello Cristianini , Michael I. Jordan , William Stafford Noble, A statistical framework for genomic data fusion, Bioinformatics, v.20 n.16, p.2626-2635, November 2004 [doi>10.1093/bioinformatics/bth294]
• 13: 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
• 14: Darrin P. Lewis , Tony Jebara , William Stafford Noble, Nonstationary kernel combination, Proceedings of the 23rd international conference on Machine learning, p.553-560, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143914]
• 15: Charles A. Micchelli , Massimiliano Pontil, Learning the Kernel Function via Regularization, The Journal of Machine Learning Research, 6, p.1099-1125, 12/1/2005
• 16: Mika, S., Rätsch, G., & Müüller, K.-R. (2001). A mathematical programming approach to the kernel fisher algorithm. NIPS (pp. 591--597). MIT Press.
• 17: Sebastian Mika , Gunnar Rätsch , Jason Weston , Bernhard Schölkopf , Alex Smola , Klaus-Robert Müller, Constructing Descriptive and Discriminative Nonlinear Features: Rayleigh Coefficients in Kernel Feature Spaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.5, p.623-633, May 2003 [doi>10.1109/TPAMI.2003.1195996]
• 18: Newman, D., Hettich, S., Blake, C., & Merz, C. (1998). UCI repository of machine learning databases.
• 19: Cheng Soon Ong , Alexander J. Smola , Robert C. Williamson, Learning the Kernel with Hyperkernels, The Journal of Machine Learning Research, 6, p.1043-1071, 12/1/2005
• 20: 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
• 21: Schölkopf, S., & Smola, A. (2002). Learning with kernels: Support vector machines, regularization, optimization and beyond. MIT Press.
• 22: Sören Sonnenburg , Gunnar Rätsch , Christin Schäfer , Bernhard Schölkopf, Large Scale Multiple Kernel Learning, The Journal of Machine Learning Research, 7, p.1531-1565, 12/1/2006
• 23: Sturm, J. F. (1999). Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software, 11--12, 625--653.
• 24: Tsang, I. W., & Kwok, J. T. (2006). Efficient hyperkernel learning using second-order cone programming. IEEE Trans. on Neural Networks, 17, 48--58.
• 25: Lieven Vandenberghe , Stephen Boyd, Semidefinite programming, SIAM Review, v.38 n.1, p.49-95, Mar. 1996 [doi>10.1137/1038003]
• 26: Vapnik, V. (1998). Statistical learning theory. Wiley, New York.
• 27: Ye, J., Chen, J., Li, Q., & Kumar, S. (2006). Classification of drosophila embryonic developmental stage range based on gene expression pattern images. Computational Systems Bioinformatics Conference (pp. 293--298).