Welcome Workshop descritpion Call for papers Talks and posters Organizers


Description

There is a growing interest in Machine Learning, in applying geometrical and topological tools to high-dimensional data analysis and processing [14, 3, 20]. Considering a finite set of points in a high-dimensional space, the approaches developed in the field of Topology Learning intend to learn, explore and exploit the topology of the shapes (topological invariants such as the intrinsic dimension or the Betti numbers), manifolds or not, from which these points are supposed to be drawn. Applications likely to benefit from these topological characteristics have been identified in the field of Exploratory Data Analysis [13], Pattern Recognition [11], Process Control [26], Semi-Supervised Learning [5, 8], Manifold Learning [24, 8] and Clustering [22].

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.  

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.