Learning a kernel matrix for nonlinear dimensionality reduction

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: Mikhail Belkin , Partha Niyogi, Laplacian Eigenmaps for dimensionality reduction and data representation, Neural Computation, v.15 n.6, p.1373-1396, June 2003 [doi>10.1162/089976603321780317]
• 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: Christopher J. C. Burges, Geometry and invariance in kernel based methods, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 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: Thore Graepel, Kernel Matrix Completion by Semidefinite Programming, Proceedings of the International Conference on Artificial Neural Networks, p.694-699, August 28-30, 2002
• 8: Jihun Ham , Daniel D. Lee , Sebastian Mika , Bernhard Schölkopf, A kernel view of the dimensionality reduction of manifolds, Proceedings of the twenty-first international conference on Machine learning, p.47, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015417]
• 9: J. J. Hull, A Database for Handwritten Text Recognition Research, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.5, p.550-554, May 1994 [doi>10.1109/34.291440]
• 10: Jolliffe, I. T. (1986). Principal component analysis. New York: Springer-Verlag.
• 11: Gert R. G. Lanckriet , Nello Cristianini , Peter Bartlett , Laurent El Ghaoui , Michael I. Jordan, Learning the Kernel Matrix with Semidefinite Programming, The Journal of Machine Learning Research, 5, p.27-72, 12/1/2004
• 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: Lawrence K. Saul , Sam T. Roweis, Think globally, fit locally: unsupervised learning of low dimensional manifolds, The Journal of Machine Learning Research, 4, p.119-155, 12/1/2003
• 15: Bernhard Scholkopf , Alexander J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, MIT Press, Cambridge, MA, 2001
• 16: Bernhard Schölkopf , Alexander Smola , Klaus-Robert Müller, Nonlinear component analysis as a kernel eigenvalue problem, Neural Computation, v.10 n.5, p.1299-1319, July 1, 1998 [doi>10.1162/089976698300017467]
• 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: Lieven Vandenberghe , Stephen Boyd, Semidefinite programming, SIAM Review, v.38 n.1, p.49-95, Mar. 1996 [doi>10.1137/1038003]
• 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.