Proceedings

Kernel Matrix Evaluation

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 987-991.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

We study the problem of evaluating the goodness of a kernel matrix for a classification task. As kernel matrix evaluation is usually used in other expensive procedures like feature and model selections, the goodness measure must be calculated efficiently. Most previous approaches are not efficient, except for Kernel Target Alignment that can be calculated in O(n2) time complexity. Although KTA is widely used, we show that it has some serious drawbacks. We propose an efficient surrogate measure to evaluate the goodness of a kernel matrix based on the data distributions of classes in the feature space. The measure not only overcomes the limitations of KTA, but also possesses other properties like invariance, efficiency and error bound guarantee. Comparative experiments show that the measure is a good indication of the goodness of a kernel matrix.

  1. [Crammer et al., 2002] Koby Crammer, Joseph Keshet, and Yoram Singer. Kernel design using boosting. In NIPS, pages 537-544, 2002.
  2. [Cristianini et al., 2002] Nello Cristianini, John Shawe- Taylor, Andre Elisseeff, and Jaz Kandola. On kernel-target alignment. In T. G. Dietterich, S. Becker, and Z. Ghahra- mani, editors, Advances in Neural Information Processing Systems 14, Cambridge, MA, 2002. MIT Press.
  3. [Feller, 1971] William Feller. An Introduction to Probabil- ity Theory and Its Applications, volume 2. John Wiley & Sons, 1971.
  4. [Fine and Scheinberg, 2002] Shai Fine and Katya Schein- berg. Efficient svm training using low-rank kernel repre- sentations. Journal of Machine Learning Research, 2:243- 264, 2002.
  5. [Gartner et al., 2004] Thomas Gartner, John W. Lloyd, and Peter A. Flach. Kernels and distances for structured data. Machine Learning Journal, 57(3):205-232, 2004.
  6. [Globerson and Roweis, 2006] Amir Globerson and Sam Roweis. Metric learning by collapsing classes. In Y. Weiss, B. Schölkopf, and J. Platt, editors, Advances in Neural In- formation Processing Systems 18, pages 451-458, 2006.
  7. [Gradshteyn and Ryzhik, 2000] I. S. Gradshteyn and I. M. Ryzhik. Table of Integrals, Series, and Products. Aca- demic Press, San Diego, CA, 2000.
  8. [Jebara et al., 2004] Tony Jebara, Risi Kondor, and Andrew Howard. Probability product kernels. Journal of Machine Learning Research, 5:819-844, 2004.
  9. [Kwok and Tsang, 2003] James T. Kwok and Ivor W. Tsang. Learning with idealized kernels. In ICML, pages 400-407, 2003.
  10. [Lanckriet et al., 2002] Gert R. G. Lanckriet, Laurent El Ghaoui, Chiranjib Bhattacharyya, and Michael I. Jordan. A robust minimax approach to classification. Journal of Machine Learning Research, 3:555-582, 2002.
  11. [Lanckriet et al., 2004] Gert R. G. Lanckriet, Nello Cristian- ini, Peter Bartlett, Laurent El Ghaoui, and Michael I. Jor- dan. Learning the kernel matrix with semidefinite pro- gramming. J. Mach. Learn. Res., 5:27-72, 2004.
  12. [Meila, 2003] Marina Meila. Data centering in feature space. In Christopher M. Bishop and Brendan J. Frey, editors, Ninth International Workshop on Artificial Intelligence and Statistics, 2003.
  13. [Neumann et al., 2005] Julia Neumann, Christoph Schnorr, and Gabriele Steidl. Combined svm-based feature selec- tion and classification. Machine Learning, 61(1-3):129- 150, 2005.
  14. [Ong et al., 2005] Cheng Soon Ong, Alexander J. Smola, and Robert C. Williamson. Learning the kernel with hyper- kernels. Journal of Machine Learning Research, 6:1043- 1071, 2005.
  15. [Schölkopf and Smola, 2002] Bernhard Schölkopf and Alexander J. Smola. Learning with Kernels. MIT Press, Cambridge, MA, 2002.
  16. [Shawe-Taylor and Cristianini, 2004] John Shawe-Taylor and Nello Cristianini. Kernel Methods for Pattern Anal- ysis. Cambridge University Press, New York, NY, USA, 2004.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards