A Topological View of Unsupervised Learning from Noisy Data
- 1 January 2011
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 40 (3), 646-663
- https://doi.org/10.1137/090762932
Abstract
In this paper, we take a topological view of unsupervised learning. From this point of view, clustering may be interpreted as trying to find the number of connected components of any underlying geometrically structured probability distribution in a certain sense that we will make precise. We construct a geometrically structured probability distribution that seems appropriate for modeling data in very high dimensions. A special case of our construction is the mixture of Gaussians where there is Gaussian noise concentrated around a finite set of points (the means). More generally we consider Gaussian noise concentrated around a low dimensional manifold and discuss how to recover the homology of this underlying geometric core from data that do not lie on it. We show that if the variance of the Gaussian noise is small in a certain sense, then the homology can be learned with high confidence by an algorithm that has a weak (linear) dependence on the ambient dimension. Our algorithm has a natural interpretation as a spectral learning algorithm using a combinatorial Laplacian of a suitable data-derived simplicial complex.Keywords
This publication has 11 references indexed in Scilit:
- Manifold Reconstruction in Arbitrary Dimensions Using Witness ComplexesDiscrete & Computational Geometry, 2009
- Towards a theoretical foundation for Laplacian-based manifold methodsJournal of Computer and System Sciences, 2008
- Smooth manifold reconstruction from noisy and non-uniform approximation with guaranteesComputational Geometry, 2008
- Finding the Homology of Submanifolds with High Confidence from Random SamplesDiscrete & Computational Geometry, 2008
- Stability of Persistence DiagramsDiscrete & Computational Geometry, 2006
- From graph to manifold Laplacian: The convergence rateApplied and Computational Harmonic Analysis, 2006
- Laplacian Eigenmaps for Dimensionality Reduction and Data RepresentationNeural Computation, 2003
- Surface Reconstruction by Voronoi FilteringDiscrete & Computational Geometry, 1999
- Computing Betti Numbers via Combinatorial LaplaciansAlgorithmica, 1998
- Three-dimensional alpha shapesACM Transactions on Graphics, 1994