A topological view of unsupervised learning from noisy data

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

91 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)646-663
Journal / PublicationSIAM Journal on Computing
Volume40
Issue number3
Publication statusPublished - 2011
Externally publishedYes

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. © 2011 Society for Industrial and Applied Mathematics.

Research Area(s)

  • Data, Manifolds, Topology

Citation Format(s)

A topological view of unsupervised learning from noisy data. / Niyogi, P.; Smale, S.; Weinberger, S.
In: SIAM Journal on Computing, Vol. 40, No. 3, 2011, p. 646-663.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review