Article

Learning a kernel matrix for nonlinear dimensionality reduction

Authors:

Kilian Q. Weinberger,

Lawrence K. SaulAuthors Info & Claims

ICML '04: Proceedings of the twenty-first international conference on Machine learning

Page 106

https://doi.org/10.1145/1015330.1015345

Published: 04 July 2004 Publication History

Abstract

We investigate how to learn a kernel matrix for high dimensional data that lies on or near a low dimensional manifold. Noting that the kernel matrix implicitly maps the data into a nonlinear feature space, we show how to discover a mapping that "unfolds" the underlying manifold from which the data was sampled. The kernel matrix is constructed by maximizing the variance in feature space subject to local constraints that preserve the angles and distances between nearest neighbors. The main optimization involves an instance of semidefinite programming---a fundamentally different computation than previous algorithms for manifold learning, such as Isomap and locally linear embedding. The optimized kernels perform better than polynomial and Gaussian kernels for problems in manifold learning, but worse for problems in large margin classification. We explain these results in terms of the geometric properties of different kernels and comment on various interpretations of other manifold learning algorithms as kernel methods.

References

[1]

Belkin, M., & Niyogi, P. (2003). Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6), 1373--1396.

Digital Library

[2]

Bengio, Y., Paiement, J.-F., & Vincent, P. (2004). Out-of-sample extensions for LLE, Isomap, MDS, eigenmaps, and spectral clustering. Advances in Neural Information Processing Systems 16. Cambridge, MA: MIT Press.

[3]

Biswas, P., & Ye, Y. (2003). A distributed method for solving semideinite programs arising from ad hoc wireless sensor network localization. Stanford University, Department of Electrical Engineering, working paper.

[4]

Burges, C. J. C. (1999). Geometry and invariance in kernel based methods. Advances in Kernel Methods---Support Vector Learning. Cambridge, MA: MIT Press.

Digital Library

[5]

Cortes, C., Haffner, P., & Mohri, M. (2003). Rational kernels. Advances in Neural Information Processing Systems 15 (pp. 617--624). Cambridge, MA: MIT Press.

[6]

Donoho, D. L., & Grimes, C. E. (2003). Hessian eigenmaps: locally linear embedding techniques for high-dimensional data. Proceedings of the National Academy of Arts and Sciences, 100, 5591--5596.

[7]

Graepel, T. (2002). Kernel matrix completion by semidefinite programming. Proceedings of the International Conference on Artificial Neural Networks (pp. 694--699). Springer-Verlag.

Digital Library

[8]

Ham, J., Lee, D. D., Mika, S., & Schöölkopf, B. (2004). A kernel view of the dimensionality reduction of manifolds. Proceedings of the Twenty First International Conference on Machine Learning (ICML-04). Banff, Canada.

Digital Library

[9]

Hull, J. J. (1994). A database for handwritten text recognition research. IEEE Transaction on Pattern Analysis and Machine Intelligence, 16(5), 550--554.

Digital Library

[10]

Jolliffe, I. T. (1986). Principal component analysis. New York: Springer-Verlag.

[11]

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

Digital Library

[12]

Lodhi, H., Saunders, C., Cristianini, N., & Watkins, C. (2004). String matching kernels for text classification. Journal of Machine Learning Research. in press.

[13]

Roweis, S. T., & Saul, L. K. (2000). Nonlinear dimensionality reduction by locally linear embedding. Science, 290, 2323--2326.

[14]

Saul, L. K., & Roweis, S. T. (2003). Think globally, fit locally: unsupervised learning of low dimensional manifolds. Journal of Machine Learning Research, 4, 119--155.

Digital Library

[15]

Schölkopf, B., & Smola, A. J. (2002). Learning with kernel: Support vector machines, regularization optimization, and beyond. Cambridge, MA: MIT Press.

Digital Library

[16]

Schölkopf, B., Smola, A. J., & Müüller, K.-R. (1998). Nonlinear component analysis as a kernel eigenvalue problem. Neural Computation, 10, 1299--1319.

Digital Library

[17]

Sturm, J. F. (1999). Using SeDuMi 1.02, a MATLAB toolbox for optimization overy symmetric cones. Optimization Methods and Software, 11--12, 625--653.

[18]

Tenenbaum, J. B., de Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290, 2319--2323.

[19]

Vandenberghe, L., & Boyd, S. P. (1996). Semidefinite programming. SIAM Review, 38(1), 49--95.

Digital Library

[20]

Weinberger, K. Q., & Saul, L. K. (2004). Unsupervised learning of image manifolds by semidefinite programming. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR-04). Washington D.C.

Digital Library

Cited By

Er BFidan U(2024)Koroner Arter Hastalığı Sınıflandırılmasında Destek Vektör Makinelerinin Gri Kurt Optimizasyonuna Dayalı Özellik Seçim Yöntemi ile GeliştirilmesiEskişehir Türk Dünyası Uygulama ve Araştırma Merkezi Bilişim Dergisi10.53608/estudambilisim.14097345:1(37-44)Online publication date: 30-Jun-2024
https://doi.org/10.53608/estudambilisim.1409734
El Moutaouakil KRoudani MOuhmid AZhilenkov AMobayen S(2024)Decomposition and Symmetric Kernel Deep Neural Network Fuzzy Support Vector MachineSymmetry10.3390/sym1612158516:12(1585)Online publication date: 27-Nov-2024
https://doi.org/10.3390/sym16121585
Chung DKwon SAhn S(2024)Enhanced trajectory data visualization: a dynamic time warping integrated t-SNE approach with real-data applicationsCommunications in Statistics - Simulation and Computation10.1080/03610918.2024.2430732(1-14)Online publication date: 26-Nov-2024
https://doi.org/10.1080/03610918.2024.2430732
Show More Cited By

Learning a kernel matrix for nonlinear dimensionality reduction
1. Computing methodologies

Recommendations

Semi-supervised nonlinear dimensionality reduction
ICML '06: Proceedings of the 23rd international conference on Machine learning

The problem of nonlinear dimensionality reduction is considered. We focus on problems where prior information is available, namely, semi-supervised dimensionality reduction. It is shown that basic nonlinear dimensionality reduction algorithms, such as ...
Analysis and extension of spectral methods for nonlinear dimensionality reduction
ICML '05: Proceedings of the 22nd international conference on Machine learning

Many unsupervised algorithms for nonlinear dimensionality reduction, such as locally linear embedding (LLE) and Laplacian eigenmaps, are derived from the spectral decompositions of sparse matrices. While these algorithms aim to preserve certain ...
Incremental Nonlinear Dimensionality Reduction by Manifold Learning

Understanding the structure of multidimensional patterns, especially in unsupervised cases, is of fundamental importance in data mining, pattern recognition, and machine learning. Several algorithms have been proposed to analyze the structure of high-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICML '04: Proceedings of the twenty-first international conference on Machine learning

July 2004

934 pages

ISBN:1581138385

DOI:10.1145/1015330

Conference Chair:
Carla Brodley
Purdue University/Tufts University

Copyright © 2004 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 July 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

271
Total Citations
View Citations
2,694
Total Downloads

Downloads (Last 12 months)98
Downloads (Last 6 weeks)20

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Er BFidan U(2024)Koroner Arter Hastalığı Sınıflandırılmasında Destek Vektör Makinelerinin Gri Kurt Optimizasyonuna Dayalı Özellik Seçim Yöntemi ile GeliştirilmesiEskişehir Türk Dünyası Uygulama ve Araştırma Merkezi Bilişim Dergisi10.53608/estudambilisim.14097345:1(37-44)Online publication date: 30-Jun-2024
https://doi.org/10.53608/estudambilisim.1409734
El Moutaouakil KRoudani MOuhmid AZhilenkov AMobayen S(2024)Decomposition and Symmetric Kernel Deep Neural Network Fuzzy Support Vector MachineSymmetry10.3390/sym1612158516:12(1585)Online publication date: 27-Nov-2024
https://doi.org/10.3390/sym16121585
Chung DKwon SAhn S(2024)Enhanced trajectory data visualization: a dynamic time warping integrated t-SNE approach with real-data applicationsCommunications in Statistics - Simulation and Computation10.1080/03610918.2024.2430732(1-14)Online publication date: 26-Nov-2024
https://doi.org/10.1080/03610918.2024.2430732
Hassan QAl-Jiboory AAl-Razgan MViktor PGhazaly NAwwad EAlgburi SAli BSapaev IDawood IJaszczur MSameen ABarakat M(2024)Sustainable Energy Planning and Integration for District Heating Systems: A Case Study in Nineveh Province, IraqJournal of Building Engineering10.1016/j.jobe.2024.109411(109411)Online publication date: Apr-2024
https://doi.org/10.1016/j.jobe.2024.109411
Jiang QZhou GZhao Q(2024)Semi-supervised multi-view concept decompositionExpert Systems with Applications10.1016/j.eswa.2023.122572241(122572)Online publication date: May-2024
https://doi.org/10.1016/j.eswa.2023.122572
Bonetti PMetelli ARestelli M(2024)Interpretable linear dimensionality reduction based on bias-variance analysisData Mining and Knowledge Discovery10.1007/s10618-024-01015-038:4(1713-1781)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s10618-024-01015-0
Horikawa SNemoto CTajima KMatsubara MMorishima A(2024)An Adaptive Feature Selection Method for Learning-to-Enumerate ProblemAdvances in Information Retrieval10.1007/978-3-031-56063-7_8(122-136)Online publication date: 23-Mar-2024
https://doi.org/10.1007/978-3-031-56063-7_8
Zhang QYing ZZhou JSun JZhang B(2023)Broad Learning Model with a Dual Feature Extraction Strategy for ClassificationMathematics10.3390/math1119408711:19(4087)Online publication date: 26-Sep-2023
https://doi.org/10.3390/math11194087
Asgari MMagerand LManfredi L(2023)A review on model-based and model-free approaches to control soft actuators and their potentials in colonoscopyFrontiers in Robotics and AI10.3389/frobt.2023.123670610Online publication date: 9-Nov-2023
https://doi.org/10.3389/frobt.2023.1236706
Wenskovitch JDowling MNorth C(2023)Toward Addressing Ambiguous Interactions and Inferring User Intent with Dimension Reduction and Clustering Combinations in Visual AnalyticsACM Transactions on Interactive Intelligent Systems10.1145/358856514:1(1-35)Online publication date: 17-Apr-2023
https://dl.acm.org/doi/10.1145/3588565
Show More Cited By

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