Description |

Some works concerning manifolds have been done by researchers from Machine Learning. In the framework of Manifold Learning [8, chapter 5], [19, 27], non linear dimension reduction techniques are used to represent or visualize high-dimensional data or as pre-processing step for supervised or unsupervised learning tasks [12, 18, 25]. However, the final dimension of the output data and the topology of the space they live in, are constrained a priori. In Semi-Supervised Learning, it is intended to perform manifold regularization by taking into account the topology of the shapes using the Laplacian of some proximity graph of the data [2, 5]. A similar approach is also used in Spectral Clustering [4]. But in both cases, the choice of the proximity graph greatly impacts the results, making these methods sensitive to noise [21] or outliers, and there is no objective way to choose a good graph.

In the field of Computational Geometry, lots of efforts have been realized in processing geometric data in dimension 2 or 3. Using concepts such as epsilon- samples [1] and restricted Delaunay triangulations [17], efficient tools [1, 15] for estimating topological and geometrical properties of shapes have been developed. However, it is necessary to assume that the unknown shape is a smooth manifold and that the sample is not too noisy to ensure the correctness of the reconstruction algorithms.

Topology Learning aims at going beyond all these limits by providing methods able to extract geodesic paths or topological invariants from noisy high-dimensional out-of-control sampled shapes with theoretical guarantees and algorithmic tractability, and with the least a priori constraints or knowledge. It lies at the crossing of Machine Learning, Computational Geometry and Topology.

In the last few years, new ideas have emerged to face the Topology Learning problems from the algorithmic and theoretical points of view. They lead to new methods that are based upon geometric and algebraic topology tools. For example, the distance function point of view [9] allows to unify and generalize what was previously known about geometric inference [23]. The concept of topological persistence [16] proved very helpful for filtering out noise in geometric signals [10] or visualizing sub-structures in 3D images [22]. Recent attempts have also been made to deal with manifold reconstruction in high-dimension [6], and to mix statistical and topological tools, extending Voronoï concepts to Bregman divergence [7], or defining generative models based on simplicial complexes [3] combining the ideas of generative Principal Manifolds [24] and Witness Complexes [13]. The development of these newideas still face several theoretical and algorithmic difficulties that need to be addressed.

References |

[1] N. Amenta and M. Bern. Surface reconstruction by voronoi filtering. Discrete and Computational Geometry, 22(4), pp 481-504, 1999.

[2] A. Argyriou, M. Herbster, and M. Pontil. Combining graph laplacians for semi-supervised learning. Proc. of NIPS 2005.

[3] M. Aupetit. Learning topology with the generative gaussian graph and the EM algorithm. Proc. of NIPS 2005

[4] M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. Proc. of NIPS 2002

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

[6] J.-D. Boissonnat, L. Guibas, and S. Oudot. Manifold reconstruction in arbitrary dimensions using witness complexes. In Proc. of Symp. on Computational Geometry (SoCG), pages 194-203, 2007.

[7] J.-D. Boissonnat, F. Nielsen, and R. Nock. On bregman voronoi diagrams. In Proc. 18th ACM-SIAM Symp. on Discrete Algorithms (SODA), 2007.

[8] O. Chapelle, B. Schölkopf, and A. Zien, editors. Semi-Supervised Learning. MIT Press, Cambridge, MA, 2006.

[9] F. Chazal, D. Cohen-Steiner, and A. Lieutier. A sampling theory for compact sets in euclidean spaces. To appear in Discrete & Computational Geometry, Springer, 2007.

[10] F. Chazal and A. Lieutier. Topology guaranteeing manifold reconstruction using distance function to noisy data. in proc. Symp. on Computational Geometry (SoCG'06), 2006.

[11] A. Collins, A. Zomorodian, G. Carlsson, and L. Guibas. A barcode shape descriptor for curve point cloud data. Eurographics Symposium on Point-Based Graphics M. Alexa, S. Rusinkiewicz, (Editors), 2004.

[12] D. de Ridder, O. Kouropteva, O. Okun, M. Pietikäinen, and R. P. W. Duin. Supervised locally linear embedding. In ICANN, pages 333-341, 2003.

[13] V. de Silva and G. Carlsson. Topological estimation using witness complexes. In M. Alexa and S. Rusinkiewicz (Eds) Eurographics Symposium on Point- Based Graphics, ETH, Zürich,Switzerland, June 2-4, 2004.

[14] V. de Silva and J. B. Tenenbaum. Global versus local methods for nonlinear dimensionality reduction. Proc. of NIPS 2002

[15] H. Edelsbrunner, J. Harer, V. Natarajan, and V. Pascucci. Morse-smale complexes for piecewise linear 3-manifolds. Proc. 19th Ann. Symp. Comp. Geom. (SOCG), 2003.

[16] H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. In IEEE Symp. on Found. of Comp. Sci., pages 454-463, 2000.

[17] H. Edelsbrunner and N. R. Shah. Triangulating topological spaces. International Journal on Computational Geometry and Applications, 7:365-378, 1997.

[18] A. Errity and J. McKenna. An investigation of manifold learning for speech analysis. In Proc. of the Int. Conf. on Spoken Language Processing (Interspeech 2006 - ICSLP), pages 2506-2509, 2006.

[19] A. M. Farahmand, C. Szepesvari, and J-Y Audibert. Manifold adaptive dimension estimation. In Proceedings of the 24th ICML, 2007.

[20] G. Haro, G. Randall, and G. Sapiro. Stratification learning: Detecting mixed density and dimensionality in high dimensional point clouds. Proc. of NIPS 2007.

[21] M. Hein and M. Maier. Manifold denoising. Advances in Neural Information Processing Systems 19, 2007.

[22] D. Laney, P.-T. Bremer, A. Mascarenhas, P. Miller, and V. Pascucci. Understanding the structure of the turbulent mixing layer in hydrodynamic instabilities. IEEE Trans. on Vis. and Comp. Graph. Vol. 12, No. 5, pages 1053-1060, 2006.

[23] P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete and Computational . Geometry, 2006.

[24] R. Tibshirani. Principal curves revisited. Statistics and Computing, (2):183-190, 1992.

[25] M. Vlachos, C. Domeniconi, D. Gunopulos, G. Kollios, and N. Koudas. Nonlinear dimensionality reduction techniques for classification and visualization. Proc of KDD '02

[26] M. Zeller, R. Sharma, and K. Schulten. Topology representing network for sensor-based robot motion planning. WCNN, INNS Press, pages 100-103, 1996.

[27] Z. Zhang and H. Zha. Principal manifolds and nonlinear dimensionality reduction via tangent space alignment. SIAM J. Sci. Comp., 26:313-338, 2005.