An investigation of computational and informa-tional limits in gaussian mixture clustering.pdf

An Investigation of Computational and Informational Limits in Gaussian Mixture Clustering Nathan Srebro? nati@cs.toronto.edu Gregory Shakhnarovich? gregory@cs.brown.edu Sam Roweis? roweis@cs.toronto.edu ? Dept. of Computer Science, University of Toronto, Toronto, Ontario, CANADA ? Dept. of Computer Science, Brown University, Providence, Rhode Island, USA Abstract We investigate under what conditions clus- tering by learning a mixture of spherical Gaussians is (a) computationally tractable; and (b) statistically possible. We show that using principal component projection greatly aids in recovering the clustering using EM; present empirical evidence that even using such a projection, there is still a large gap between the number of samples needed to re- cover the clustering using EM, and the num- ber of samples needed without computational restrictions; and characterize the regime in which such a gap exists. 1. Introduction Consider clustering a collection of points by fitting a mixture-of-Gaussians model to the data. Viewed as a problem of optimizing an objective function, such as the likelihood, this problem seems to be hard in the traditional worst-case sense. On the other hand, when the data is inherently clustered, and enough data is available, local search methods typically succeed in optimizing the objective and recovering the clustering. This leads to the conventional wisdom that “clustering is not hard—it is either easy, or not interesting”. How true is this statement? Is there a regime in which clustering is hard even though it is interesting? When is clustering hard? Lately, a series of theoretical results established that if data is generated from an adequately separated mixture of Gaussians, and enough samples are avail- able, then clustering is in fact easy—polynomial time Appearing in Proceedings of the 23 rd International Con- ference on Machine Learning, Pittsburgh, PA, 2006. Copy- right 2006 by the author(s)/owner(s). algorithms exist that can recove