research-article

Eigenvalues perturbation of integral operator for kernel selection

Authors:

Shizhong LiaoAuthors Info & Claims

CIKM '13: Proceedings of the 22nd ACM international conference on Information & Knowledge Management

Pages 2189 - 2198

https://doi.org/10.1145/2505515.2505584

Published: 27 October 2013 Publication History

Abstract

Kernel selection is one of the key issues both in recent research and application of kernel methods. This is usually done by minimizing either an estimate of generalization error or some other related performance measure. It is well known that a kernel matrix can be interpreted as an empirical version of a continuous integral operator, and its eigenvalues converge to the eigenvalues of integral operator. In this paper, we introduce new kernel selection criteria based on the eigenvalues perturbation of the integral operator. This perturbation quantifies the difference between the eigenvalues of the kernel matrix and those of the integral operator. We establish the connection between eigenvalues perturbation and generalization error. By minimizing the derived generalization error bounds, we propose the kernel selection criteria. Therefore the kernel chosen by our proposed criteria can guarantee good generalization performance. To compute the values of our criteria, we present a method to obtain the eigenvalues of integral operator via the Fourier transform. Experiments on benchmark datasets demonstrate that our kernel selection criteria are sound and effective.

References

[1]

F. Bach, G. Lanckriet, and M. Jordan. Multiple kernel learning, conic duality, and the SMO algorithm. In Proceedings of the 21th International Conference on Machine Learning (ICML), pages 41--48, 2004.

Digital Library

[2]

P. L. Bartlett, S. Boucheron, and G. Lugosi. Model selection and error estimation. Machine Learning, 48:85--113, 2002.

Digital Library

[3]

P. L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. The Journal of Machine Learning Research, 3:463--482, 2002.

Digital Library

[4]

O. Bousquet and A. Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499--526, 2002.

Digital Library

[5]

M. Braun. Accurate error bounds for the eigenvalues of the kernel matrix. The Journal of Machine Learning Research, 7:2303--2328, 2006.

Digital Library

[6]

G. C. Cawley and N. L. C. Talbot. Preventing over-fitting during model selection via bayesian regularisation of the hyper-parameters. Journal of Machine Learning Research, 8:841--861, 2007.

Digital Library

[7]

G. C. Cawley and N. L. C. Talbot. On over-fitting in model selection and subsequent selection bias in performance evaluation. Journal of Machine Learning Research, 11:2079--2107, 2010.

Digital Library

[8]

O. Chapelle and V. Vapnik. Model selection for Support Vector Machines. In Advances in Neural Information Processing Systems 12 (NIPS), pages 230--236, 1999.

[9]

O. Chapelle, V. Vapnik, O. Bousquet, and S. Mukherjee. Choosing multiple parameters for support vector machines. Machine Learning, 46(1-3):131--159, 2002.

Digital Library

[10]

C. Corte and V. Vapnik. Support-vector networks. Machine Learning, 20(3):273--297, 1995.

Digital Library

[11]

C. Cortes, M. Mohri, and A. Rostamizadeh. L2 regularization for learning kernels. In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence (UAI), pages 109--116, 2009.

Digital Library

[12]

C. Cortes, M. Mohri, and A. Rostamizadeh. Two-stage learning kernel algorithms. In Proceedings of the 27th Conference on Machine Learning (ICML), pages 239--246, 2010.

Digital Library

[13]

C. Cortes, M. Mohri, and A. Talwalkar. On the impact of kernel approximation on learning accuracy. In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 113--120, 2000.

[14]

N. Cristianini, J. Shawe-Taylor, A. Elisseeff, and J. S. Kandola. On kernel-target alignment. In Advances in Neural Information Processing Systems 14 (NIPS), pages 367--373, 2001.

[15]

M. Debruyne, M. Hubert, and J. A. Suykens. Model selection in kernel based regression using the influence function. Journal of Machine Learning Research, 9:2377--2400, 2008.

[16]

T. Evgeniou, M. Pontil, and T. Poggio. Regularization networks and Support Vector Machines. Advances in Computational Mathematics, 13:1--50, 2000.

[17]

C. S. A. Gammerman and V. Vovk. Ridge regression learning algorithm in dual variables. In Proceedings of the 15th International Conference on Machine Learning (ICML), pages 515--521, 1998.

Digital Library

[18]

L. L. Gerfo, L. Rosasco, F. Odone, E. D. Vito, and A. Verri. Spectral algorithms for supervised learning. Neural Computation, 20(3):331--368, 2008.

Digital Library

[19]

G. H. Golub, M. Heath, and G. Wahba. Generalized cross-validation as a method for choosing a good ridge parameter. Technometrics, 21(2):215--223, 1979.

[20]

L. Jia and S. Liao. Accurate probabilistic error bound for eigenvalues of kernel matrix. In Proceedings of the 1st Asian Conference on Machine Learning,2009.

Digital Library

[21]

M. Kloft, U. Brefeld, S. Sonnenburg, and A. Zien. Lp-norm multiple kernel learning. Journal of Machine Learning Research, 12:953--997, 2011.

Digital Library

[22]

G. R. G. Lanckriet, N. Cristianini, P. L. Bartlett, L. E. Ghaoui, and M. I. Jordan. Learning the kernel matrix with semidefinite programming. The Journal of Machine Learning Research, 5:27--72, 2004.

Digital Library

[23]

Y. Liu, S. Liao, and Y. Hou. Learning kernels with upper bounds of leave-one-out error. In Proceedings of the 20th ACM International Conference on Information and Knowledge Management (CIKM), pages 2205--2208, 2011.

Digital Library

[24]

U. V. Luxburg, O. Bousquet, and B. Schölkopf. A compression approach to Support Vector model selection. Journal of Machine Learning Research, 5:293--323, 2004.

Digital Library

[25]

C. H. Nguyen and T. B. Ho. Kernel matrix evaluation. In Proceedings of the 20th International Joint Conference on Artifficial Intelligence (IJCAI), pages 987--992, 2007.

Digital Library

[26]

C. H. Nguyen and T. B. Ho. An efficient kernel matrix evaluation measure. Pattern Recognition, 41(11):3366--3372, 2008.

Digital Library

[27]

A. Rakotomamonjy, F. Bach, S. Canu, and Y. Grandvalet. SimpleMKL. Journal of Machine Learning Research, 9:2491--2521, 2008.

[28]

L. Rosasco, M. Belkin, and E. Vito. On learning with integral operators. The Journal of Machine Learning Research, 11:905--934, 2010.

Digital Library

[29]

B. Schölkopf and A. J. Smola. Learning with kernels. MIT Press, Cambridge, MA, 2002.

[30]

J. Shawe-Taylor and N. Cristianini. Support Vector Machines. Cambridge University Press, MA, 2000.

[31]

I. Steinwart and A. Christmann. Support Vector Machines. Springer Verlag, 2008.

Digital Library

[32]

J. A. K. Suykens and J. Vandewalle. Least squares Support Vector Machine classifiers. Neural Processing Letters, 9(3):293--300, 1999.

Digital Library

[33]

V. Vapnik. The Nature of Statistical Learning Theory. Springer Verlag, 2000.

Digital Library

[34]

G. Wahba. Support Vector Machine, reproducing kernel Hilbert spaces and the randomized GACV. In Advances in Kernel Methods-Support Vector Learning, volume 6, pages 69--88, Cambridge, 1999. MIT Press.

Digital Library

[35]

G. Wahba, Y. Lin, and H. Zhang. GACV for support vector machines. In Advances in Large Margin Classifiers. MIT Press, Cambridge, 1999.

Cited By

Liu YLiao S(2022)Preventing Over-Fitting of Cross-Validation with Kernel StabilityMachine Learning and Knowledge Discovery in Databases10.1007/978-3-662-44851-9_19(290-305)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-662-44851-9_19
Liu YLiao SZhang HRen WWang W(2021)Kernel Stability for Model Selection in Kernel-Based AlgorithmsIEEE Transactions on Cybernetics10.1109/TCYB.2019.292382451:12(5647-5658)Online publication date: Dec-2021
https://doi.org/10.1109/TCYB.2019.2923824
Li JLiu YYin RZhang HDing LWang W(2018)Multi-class learningProceedings of the 32nd International Conference on Neural Information Processing Systems10.5555/3326943.3327089(1593-1602)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.5555/3326943.3327089
Show More Cited By

Index Terms

Eigenvalues perturbation of integral operator for kernel selection
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
    2. Machine learning approaches
      1. Markov decision processes
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Markov decision processes

Recommendations

A pre-selecting base kernel method in multiple kernel learning

The pre-defined base kernel greatly affects the performance of multiple kernel learning (MKL), but selecting the pre-defined base kernel still has no theoretical guidance. In practice, it is very difficult to select a set of appropriate base kernels ...
Eigenvalues ratio for kernel selection of kernel methods
AAAI'15: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence

The selection of kernel function which determines the mapping between the input space and the feature space is of crucial importance to kernel methods. Existing kernel selection approaches commonly use some measures of generalization error, which are ...
Nonpositive Eigenvalues of Hollow, Symmetric, Nonnegative Matrices

Among hollow, symmetric $n$-by-$n$ nonnegative matrices, it is shown that any number $k$, $2\leq k\leq n-1$ of nonpositive eigenvalues is possible. However, as $n$ grows, small numbers of nonpositive eigenvalues become increasingly rare. In particular, if ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '13: Proceedings of the 22nd ACM international conference on Information & Knowledge Management

October 2013

2612 pages

ISBN:9781450322638

DOI:10.1145/2505515

General Chairs:
Qi He
LinkedIn, USA
,
Arun Iyengar
IBM T.J. Watson Research Center, USA
,
Program Chairs:
Wolfgang Nejdl
L3S Research Center, Germany
,
Jian Pei
Simon Fraser University, Canada
,
Rajeev Rastogi
Amazon, India

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 October 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CIKM'13

Sponsor:

CIKM'13: 22nd ACM International Conference on Information and Knowledge Management

October 27 - November 1, 2013

California, San Francisco, USA

Acceptance Rates

CIKM '13 Paper Acceptance Rate 143 of 848 submissions, 17%;

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
215
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)3

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu YLiao S(2022)Preventing Over-Fitting of Cross-Validation with Kernel StabilityMachine Learning and Knowledge Discovery in Databases10.1007/978-3-662-44851-9_19(290-305)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-662-44851-9_19
Liu YLiao SZhang HRen WWang W(2021)Kernel Stability for Model Selection in Kernel-Based AlgorithmsIEEE Transactions on Cybernetics10.1109/TCYB.2019.292382451:12(5647-5658)Online publication date: Dec-2021
https://doi.org/10.1109/TCYB.2019.2923824
Li JLiu YYin RZhang HDing LWang W(2018)Multi-class learningProceedings of the 32nd International Conference on Neural Information Processing Systems10.5555/3326943.3327089(1593-1602)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.5555/3326943.3327089
Liu YLin HDing LWang WLiao S(2018)Fast cross-validationProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304889.3305007(2497-2503)Online publication date: 13-Jul-2018
https://dl.acm.org/doi/10.5555/3304889.3305007
Li JLiu YLin HYue YWang W(2017)Efficient kernel selection via spectral analysisProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3172077.3172183(2124-2130)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3172077.3172183
(2017)Granularity selection for cross-validation of SVMInformation Sciences: an International Journal10.1016/j.ins.2016.06.051378:C(475-483)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1016/j.ins.2016.06.051
Ding LLiao SLi JWang XGarofalakis MSoboroff ISuel TWang M(2014)Model Selection with the Covering Number of the Ball of RKHSProceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management10.1145/2661829.2662034(1159-1168)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.1145/2661829.2662034

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents