Abstract
The Nearest Neighbor (NN) classification/regression techniques, besides their simplicity, are amongst the most widely applied and well studied techniques for pattern recognition in machine learning. A drawback, however, is the assumption of the availability of a suitable metric to measure distances to the k nearest neighbors. It has been shown that k-NN classifiers with a suitable distance metric can perform better than other, more sophisticated, alternatives such as Support Vector Machines and Gaussian Process classifiers. For this reason, much recent research in k-NN methods has focused on metric learning, i.e. finding an optimized metric. In this paper we propose a simple gradient-based algorithm for metric learning. We discuss in detail the motivations behind metric learning, i.e. error minimization and margin maximization. Our formulation differs from the prevalent techniques in metric learning, where the goal is to maximize the classifier’s margin. Instead our proposed technique (MEGM) finds an optimal metric by directly minimizing the mean square error. Our technique not only results in greatly improved k-NN performance, but also performs better than competing metric learning techniques. Promising results are reported on major UCIML databases.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cover, T.: Rates of convergence for nearest neighbor procedures. In: Proceedings of the International Conference on Systems Sciences (1968)
Fix, E., Hodges, J.: Discriminatory analysis - nonparameteric discrimination: consistency properties. Tech. Report, Randolph Field Texas, US Airforce School of Aviation Medicine, Tech. Rep. (1951)
Snapp, R., Venkatesh, S.: Asymptotic expansions of the k-nearest neighbor risk. The Annals of Statistics (1998)
Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning. Springer Series in Statistics (2001)
Goldberger, J., Roweis, S., Hinton, G., Salakhutdinov, R.: Neighborhood component analysis. In: Proceedings of Neural Inforamtion and Processing Systems (2005)
Davis, J., Dhillon, I.: Structured metric learning for high dimensional problems. In: ACM SIGKDD Conference on Knowledge Discovery and Data Mining (2008)
Weinberger, K., Blitzer, J., Saul, L.: Distance metric learning for large margin nearest neighbor classification. In: Proceedings of Neural Inforamtion and Processing Systems (2005)
Sriperumbudar, B., Lang, O., Lanckriet, G.: Metric embedding for kernel classification rules. In: Proceedings of the International Conference on Machine Learning (2008)
Globerson, A., Roweis, S.: Metric learning by collapsing classes. In: Proceedings of Neural Inforamtion and Processing Systems (2005)
Xing, E., Ng, A., Jordan, M., Russell, S.: Distance metric learning with application to clustering with side-information. In: Proceedings of Neural Inforamtion and Processing Systems (2002)
Friedman, J.: Flexible metric nearest neighbor classification. Tech. Report, Dept. of Statistics, Stanford University, Tech. Rep. (1994)
Lowe, D.: Similarity metric learning for a variable-kernel classifier. In: Proceedings of Neural Inforamtion and Processing Systems (1996)
Weinberger, K., Blitzer, J., Saul, L.: Distance metric learning for large margin nearest neighbor classification. In: Proceedings of Neural Inforamtion and Processing Systems (2006)
Bar-Hillel, A., Hertz, T., Shental, N., Weinshall, D.: Learning distance functions using equivalence relation. In: Proceedings of the International Conference on Machine Learning (2003)
Mertz, C., Murphy, P.: Machine learning repository (2005), http://archive.ics.uci.edu/ml/
Hastie, T., Tibshirani, R.: Discriminative adaptive nearest neighbor classification. IEEE Transactions on Pattern Analysis and Machine Intelligence (1996)
Zaidi, N., Squire, D.M., Suter, D.: BoostML: An adaptive metric learning for nearest neighbor classification. In: Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zaidi, N.A., Squire, D.M., Suter, D. (2010). A Gradient-Based Metric Learning Algorithm for k-NN Classifiers. In: Li, J. (eds) AI 2010: Advances in Artificial Intelligence. AI 2010. Lecture Notes in Computer Science(), vol 6464. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17432-2_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-17432-2_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17431-5
Online ISBN: 978-3-642-17432-2
eBook Packages: Computer ScienceComputer Science (R0)