An investigation of computational and informational limits in Gaussian mixture clustering

ABSTRACT

We investigate under what conditions clustering 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 recover the clustering using EM, and the number of samples needed without computational restrictions; and characterize the regime in which such a gap exists.

REFERENCES

• 1: Achlioptas, D., & McSherry, F. (2005). On spectral learning of mixtures of distributions. 18th Annual Conference on Learning Theory (COLT).
• 2: Arora Sanjeev , Ravi Kannan, Learning mixtures of arbitrary gaussians, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.247-257, July 2001, Hersonissos, Greece [doi>10.1145/380752.380808]
• 3: Barkai, N., & Sompolinksy, H. (1994). Statistical mechanics of maximum-likelihood desnsity estimation. Physical Review E, 50, 1766--1769.
• 4: Sanjoy Dasgupta, Learning Mixtures of Gaussians, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.634, October 17-18, 1999
• 5: Sanjoy Dasgupta , Leonard J. Schulman, A Two-Round Variant of EM for Gaussian Mixtures, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.152-159, June 30-July 03, 2000
• 6: Kannan, R., Salmasian, H., & Vempala, S. (2005). The spectral method for general mixture models. 18th Annual Conference on Learning Theory (COLT).
• 7: Amit Kumar , Yogish Sabharwal , Sandeep Sen, A Simple Linear Time (1+ ") -Approximation Algorithm for k-Means Clustering in Any Dimensions, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.454-462, October 17-19, 2004 [doi>10.1109/FOCS.2004.7]
• 8: Redner, R. A., & Walker, H. F. (1984). Mixture densities, maximum likelihood and the EM algorithm. SIAM Review, 26, 195--239.
• 9: Santosh Vempala , Grant Wang, A spectral algorithm for learning mixture models, Journal of Computer and System Sciences, v.68 n.4, p.841-860, June 2004 [doi>10.1016/j.jcss.2003.11.008]
• 10: Watkins, T., & Nadal, J. (1994). Optimal unsupervised learning. J. Phys. A, 27, 1899--1915.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Algorithms