Header logo is

On the Complexity of Learning the Kernel Matrix


Conference Paper


We investigate data based procedures for selecting the kernel when learning with Support Vector Machines. We provide generalization error bounds by estimating the Rademacher complexities of the corresponding function classes. In particular we obtain a complexity bound for function classes induced by kernels with given eigenvectors, i.e., we allow to vary the spectrum and keep the eigenvectors fix. This bound is only a logarithmic factor bigger than the complexity of the function class induced by a single kernel. However, optimizing the margin over such classes leads to overfitting. We thus propose a suitable way of constraining the class. We use an efficient algorithm to solve the resulting optimization problem, present preliminary experimental results, and compare them to an alignment-based approach.

Author(s): Bousquet, O. and Herrmann, D.
Book Title: Advances in Neural Information Processing Systems 15
Journal: Advances in Neural Information Processing Systems, 15
Pages: 399-406
Year: 2003
Month: October
Day: 0
Editors: Becker, S. , S. Thrun, K. Obermayer
Publisher: The MIT Press

Department(s): Empirical Inference
Bibtex Type: Conference Paper (inproceedings)

Event Name: Sixteenth Annual Conference on Neural Information Processing Systems (NIPS 2002)
Event Place: Vancouver, Canada

Address: Cambridge, MA, USA
Digital: 0
ISBN: 0-262-02550-7
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF


  title = {On the Complexity of Learning the Kernel Matrix},
  author = {Bousquet, O. and Herrmann, D.},
  journal = {Advances in Neural Information Processing Systems, 15},
  booktitle = {Advances in Neural Information Processing Systems 15},
  pages = {399-406},
  editors = {Becker, S. , S. Thrun, K. Obermayer},
  publisher = {The MIT Press},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {Cambridge, MA, USA},
  month = oct,
  year = {2003},
  month_numeric = {10}