research-article

Metric embedding for kernel classification rules

Authors:

Bharath K. Sriperumbudur,

Gert R. G. LanckrietAuthors Info & Claims

ICML '08: Proceedings of the 25th international conference on Machine learning

Pages 1008 - 1015

https://doi.org/10.1145/1390156.1390283

Published: 05 July 2008 Publication History

Abstract

In this paper, we consider a smoothing kernel based classification rule and propose an algorithm for optimizing the performance of the rule by learning the bandwidth of the smoothing kernel along with a data-dependent distance metric. The data-dependent distance metric is obtained by learning a function that embeds an arbitrary metric space into a Euclidean space while minimizing an upper bound on the resubstitution estimate of the error probability of the kernel classification rule. By restricting this embedding function to a reproducing kernel Hilbert space, we reduce the problem to solving a semidefinite program and show the resulting kernel classification rule to be a variation of the k-nearest neighbor rule. We compare the performance of the kernel rule (using the learned data-dependent distance metric) to state-of-the-art distance metric learning algorithms (designed for k-nearest neighbor classification) on some benchmark datasets. The results show that the proposed rule has either better or as good classification accuracy as the other metric learning algorithms.

References

[1]

Devroye, L., Gyorfi, L., & Lugosi, G. (1996). A Probabilistic Theory of Pattern Recognition. New York: Springer-Verlag.

[2]

Devroye, L., & Krzy&zdot;żak, A. (1989). An equivalence theorem for L<sub>1</sub> convergence of the kernel regression estimate. Journal of Statistical Planning and Inference, 23, 71--82.

[3]

Evgeniou, T., Pontil, M., & Poggio, T. (2000). Regularization networks and support vector machines. Advances in Computational Mathematics, 13, 1--50.

[4]

Globerson, A., & Roweis, S. (2006). Metric learning by collapsing classes. Advances in Neural Information Processing Systems 18 (pp. 451--458). Cambridge, MA: MIT Press.

[5]

Goldberger, J., Roweis, S., Hinton, G., & Salakhutdinov, R. (2005). Neighbourhood components analysis. Advances in Neural Information Processing Systems 17 (pp. 513--520). Cambridge, MA: MIT Press.

[6]

Horst, R., & Thoai, N. V. (1999). D.c. programming: Overview. Journal of Optimization Theory and Applications, 103, 1--43.

Digital Library

[7]

Schölkopf, B., Herbrich, R., & Smola, A. J. (2001). A generalized representer theorem. Proc. of the Annual Conference on Computational Learning Theory (pp. 416--426).

Digital Library

[8]

Schölkopf, B., & Smola, A. J. (2002). Learning with kernels. Cambridge, MA: MIT Press.

[9]

Shalev-Shwartz, S., Singer, Y., & Ng, A. Y. (2004). Online and batch learning of pseudo-metrics. Proc. of 21<sup>st</sup> International Conference on Machine Learning. Banff, Canada.

Digital Library

[10]

Snapp, R. R., & Venkatesh, S. S. (1998). Asymptotic expansions of the k nearest neighbor risk. The Annals of Statistics, 26, 850--878.

[11]

Torresani, L., & Lee, K. (2007). Large margin component analysis. Advances in Neural Information Processing Systems 19 (pp. 1385--1392). Cambridge, MA: MIT Press.

[12]

von Luxburg, U., & Bousquet, O. (2004). Distance-based classification with Lipschitz functions. Journal for Machine Learning Research, 5, 669--695.

Digital Library

[13]

Weinberger, K. Q., Blitzer, J., & Saul, L. K. (2006). Distance metric learning for large margin nearest neighbor classification. Advances in Neural Information Processing Systems 18 (pp. 1473--1480). Cambridge, MA: MIT Press.

[14]

Weinberger, K. Q., & Tesauro, G. (2007). Metric learning for kernel regression. Proc. of the 11<sup>th</sup> International Conference on Artificial Intelligence and Statistics.

[15]

Xing, E. P., Ng, A. Y., Jordan, M. I., & Russell, S. (2003). Distance metric learning with application to clustering with side-information. Advances in Neural Information Processing Systems 15 (pp. 505--512). Cambridge, MA: MIT Press.

Cited By

Geng BTao DXu C(2011)DAMLIEEE Transactions on Image Processing10.1109/TIP.2011.213410720:10(2980-2989)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1109/TIP.2011.2134107
Yu YJiang JZhang L(2011)Distance metric learning by minimal distance maximizationPattern Recognition10.1016/j.patcog.2010.09.01944:3(639-649)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1016/j.patcog.2010.09.019
Zaidi NSquire D(2010)SVMs and data dependent distance metric2010 25th International Conference of Image and Vision Computing New Zealand10.1109/IVCNZ.2010.6148826(1-7)Online publication date: Nov-2010
https://doi.org/10.1109/IVCNZ.2010.6148826
Show More Cited By

Index Terms

Metric embedding for kernel classification rules
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning
        Supervised learning by classification
      2. Unsupervised learning
        Cluster analysis
    2. Machine learning approaches
      1. Classification and regression trees
  2. Modeling and simulation
    1. Model development and analysis
      1. Model verification and validation
      2. Modeling methodologies

Recommendations

Extracting Decision Rules from Sigmoid Kernel
ADMA '08: Proceedings of the 4th international conference on Advanced Data Mining and Applications

Sigmoid kernel is widely applied in neural networks for classification tasks. SVM classifier, which is applied with sigmoid kernel, has excellent classification accuracy. However, as sigmoid kernel has complicated structure, it is generally difficult ...
Extracting Positive and Negative Association Classification Rules from RBF Kernel
ICCIT '07: Proceedings of the 2007 International Conference on Convergence Information Technology

Recently, building associative classifiers by miming association rules is a hot research problem. As negative association rules also help to understand the data, in this paper, we present our InterRBF algorithm, which expands RBF kernel into its ...
A Mahalanobis metric learning-based polynomial kernel for classification of hyperspectral images

In this paper, to combine the advantage of both polynomial kernel and the Mahalanobis distance metric learning (DML) methods, we propose a Mahalanobis DML based polynomial kernel for the classification of hyperspectral images. To ensure the method is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICML '08: Proceedings of the 25th international conference on Machine learning

July 2008

1310 pages

ISBN:9781605582054

DOI:10.1145/1390156

General Chair:
William Cohen
Carnegie Mellon University
,
Program Chairs:
Andrew McCallum
University of Massachusetts Amherst
,
Sam Roweis
University of Toronto and Google

Copyright © 2008 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

Pascal
University of Helsinki
Xerox
Federation of Finnish Learned Societies
Google Inc.
NSF
Machine Learning Journal/Springer
Microsoft Research: Microsoft Research
Intel: Intel
Yahoo!
Helsinki Institute for Information Technology
IBM: IBM

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Division of Mathematical Sciences

Conference

ICML '08

Sponsor:

Microsoft Research
Intel
IBM

ICML '08: The 25th Annual International Conference on Machine Learning held in conjunction with the 2007 International Conference on Inductive Logic Programming

July 5 - 9, 2008

Helsinki, Finland

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
197
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Geng BTao DXu C(2011)DAMLIEEE Transactions on Image Processing10.1109/TIP.2011.213410720:10(2980-2989)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1109/TIP.2011.2134107
Yu YJiang JZhang L(2011)Distance metric learning by minimal distance maximizationPattern Recognition10.1016/j.patcog.2010.09.01944:3(639-649)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1016/j.patcog.2010.09.019
Zaidi NSquire D(2010)SVMs and data dependent distance metric2010 25th International Conference of Image and Vision Computing New Zealand10.1109/IVCNZ.2010.6148826(1-7)Online publication date: Nov-2010
https://doi.org/10.1109/IVCNZ.2010.6148826
Zaidi NSquire DSuter D(2010)A Gradient-Based Metric Learning Algorithm for k-NN ClassifiersAI 2010: Advances in Artificial Intelligence10.1007/978-3-642-17432-2_20(194-203)Online publication date: 2010
https://doi.org/10.1007/978-3-642-17432-2_20

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