Tangent space learning and generalization

Abstract

Manifold learning has attracted considerable attention over the last decade, in which exploring the geometry and topology of the manifold is the central problem. Tangent space is a fundamental tool in discovering the geometry of the manifold. In this paper, we will first review canonical manifold learning techniques and then discuss two fundamental problems in tangent space learning. One is how to estimate the tangent space from random samples, and the other is how to generalize tangent space to ambient space. Previous studies in tangent space learning have mainly focused on how to fit tangent space, and one has to solve a global equation for obtaining the tangent spaces. Unlike these approaches, we introduce a novel method, called persistent tangent space learning (PTSL), which estimates the tangent space at each local neighborhood while ensuring that the tangent spaces vary smoothly on the manifold. Tangent space can be viewed as a point on Grassmann manifold. Inspired from the statistics on Grassmann manifold, we use intrinsic sample total variance to measure the variation of estimated tangent spaces at a single point, and thus, the generalization problem can be solved by estimating the intrinsic sample mean on Grassmann manifold. We validate our methods by various experimental results both on synthetic and real data.

Keywords

tangent space learning / machine learning / manifold learning

References

[1] Pearson K. On lines and planes of closest fit to systems of points in space. Philosophical Magazine, 1901, 2(6): 559-572

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

[3] Ham J, Lee D D, Mika S, Schölkopf B. A kernel view of the dimensionality reduction of manifolds. In: Proceedings of the 21st International Conference on Machine Learning. 2004, 369-276

[4] Tenenbaum J, de Silva V, Langford J. A global geometric framework for nonlinear dimensionality reduction. Science, 2000, 290(5500): 2319-2323

[5] Roweis S, Saul L. Nonlinear dimensionality reduction by locally linear embedding. Science, 2000, 290(5500): 2323-2326

[6] Belkin M, Niyogi P. Laplacian eigenmaps and spectral techniques for embedding and clustering. In: Proceedings of Advances in Neural Information Processing Systems. 2001, 14: 585-591

[7] de Silva V, Tenenbaum J B. Global versus local methods in nonlinear dimensionality reduction. In: Becker S, Thrun S, Obermayer K, eds. Proceedings of Advances in Neural Information Processing Systems. 2002, 15: 721-728

[8] Zhang Z, Wang J. MLLE: Modified locally linear embedding using multiple weights. In: Schölkopf B, Platt J, Hoffman T, eds. Proceedings of Advances in Neural Information Processing Systems. 2007, 19: 1593-1600

[9] Weinberger K Q, Sha F, Saul L K. Learning a kernel matrix for nonlinear dimensionality reduction. In: Proceedings of the 21th International Conference on Machine Learning. 2004, 106-113

[10] Coifman R R, Lafon S, Lee A B, Maggioni M, Warner F, Zucker S. Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps. In: Proceedings of the National Academy of Sciences. 2005, 7426-7431

[11] Chung F R K. Spectral Graph Theory. Regional Conference Series in Mathematics Vol 92. Providence: American Mathematical Society, 1997

[12] Bengio Y, Paiement J, Vincent P, Delalleau O, Roux N L, Ouimet M. Out-of-sample extensions for LLE, Isomap, MDS, eigenmaps, and spectral clustering. In: Thrun S, Saul L, Schölkopf B, eds. Proceedings of Advances in Neural Information Processing Systems. 2004, 16: 177-184

[13] Belkin M, Niyogi P. Convergence of Laplacian eigenmaps. In: Schöllkopf B, Platt J, Hoffman T, eds. Proceedings of Advances in Neural Information Processing Systems. Cambridge: MIT Press, 2007, 19: 129-136

[14] Belkin M, Niyogi P, Sindhwani V. Manifold regularization: a geometric framework for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 2006, 7: 2399-2434

[15] He X, Ji M, Bao H. A unified active and semi-supervised learning framework for image compression. In: Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition. 2009, 65-72

[16] He X. Laplacian regularized d-optimal design for active learning and its application to image retrieval. IEEE Transactions on Image Processing, 2010, 19(1): 254-263

[17] He X, Niyogi P. Locality preserving projections. In: Proceedings of Advances in Neural Information Processing Systems. 2003, 153-160

[18] He X, Yan S, Hu Y, Niyogi P, Zhang H J. Face recognition using Laplacianfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(3): 328-340

[19] He X, Cai D, Niyogi P. Tensor subspace analysis. In: Proceedings of Advances in Neural Information Processing Systems. 2005, 18: 499-506

[20] Donoho D L, Grimes C. Hessian eigenmaps: locally linear embedding techniques for high-dimensional data. Proceedings of the National Academy of Sciences, 2003, 100(10): 5591-5596

[21] Steinke F, Hein M. Non-parametric regression between manifolds. In: Koller D, Schuurmans D, Bengio Y, Bottou L, eds. Proceedings of Advances in Neural Information Processing Systems. 2008, 21: 1561-1568

[22] Kim K I, Steinke F, Hein M. Semi-supervised regression using hessian energy with an application to semi-supervised dimensionality reduction. In: Bengio Y, Schuurmans D, Lafferty J, Williams C K I, Culotta A, eds. Advances in Neural Information Processing Systems. 2009, 22: 979-987

[23] Zhang Z, Zha H. Principal manifolds and nonlinear dimension reduction via local tangent space alignment. SIAM Journal of Scientific Computing, 2004, 26(1): 313-338

[24] Brand M. Charting a manifold. In: Proceedings of Advances in Neural Information Processing Systems. 2003, 15: 961-968

[25] Lin T, Zha H. Riemannian manifold learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(5): 796-809

[26] Dollár P, Rabaud V, Belongie S. Non-isometric manifold learning: analysis and an algorithm. In: Proceedings of the 24th International Conference on Machine learning. 2007, 227: 241-248

[27] Dollár P, Belongie S, Rabaud V. Learning to traverse image manifolds. In: Schölkopf B, Platt J, Hoffman T, eds. Proceedings of Advances in Neural Information Processing Systems. 2007, 19: 361-368

[28] Zomorodian A, Carlsson G. Computing persistent homology. Discrete and Computational Geometry, 2005, 33(2): 249-274

[29] Niyogi P, Smale S, Weinberger S. Finding the homology of submanifolds with high confidence from random samples. Discrete and Computational Geometry, 2008, 39(1): 419-441

[30] Eells J, Lemaire L. Selected Topics in Harmonic Maps. CBMS Regional Conference Series in Mathematics, Vol 50. Providence: American Mathematical Society, 1983

[31] Bengio Y, Monperrus M. Non-local manifold tangent learning. In: Proceedings of Advances in Neural Information Processing Systems. 2005, 17: 129-136

[32] Cai D, He X, Han J. Document clustering using locality preserving indexing. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(12): 1624-1637

[33] Lin B, He X, Zhou Y, Liu L, Lu K. Approximately harmonic projection: theoretical analysis and an algorithm. Pattern Recognition, 2010, 43(10): 3307-3313

[34] Turk M, Pentland A. Eigenfaces for recognition. Journal of Cognitive Neuroscience, 1991, 3(1): 71-86

[35] Belhumeur P N, Hepanha J P, Kriegman D J. Eigenfaces vs. Fisherfaces: recognition using class specific linear projection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997, 19(7): 711-720

[36] Atkinson A C, Donev A N. Optimum Experimental Designs. Oxford: Oxford University Press, 2007

[37] Cheng L, Vishwanathan S V N. Learning to compress images and videos. In: Proceedings of the 24th International Conference on Machine Learning. 2007, 161-168

[38] Achlioptas D. Random matrices in data analysis. In: Proceedings of the 15th European Conference on Machine Learning. 2004, 1-8

[39] Ham J, Lee D D. Grassmann discriminant analysis: a unifying view on subspacebased learning. In: Proceedings of the 25th International Conference on Machine Learning. 2008, 376-383

[40] Bhattacharya R, Patrangenaru V. Nonparametic estimation of location and dispersion on riemannian manifolds. Journal of Statistical Planning and Inference, 2002,108: 23-36

[41] Eckart C, Young G. The approximation of one matrix by another of lower rank. Psychometrika, 1936, 1(3): 211-218

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg