Hierarchical mixture models: a probabilistic analysis

ABSTRACT

Mixture models form one of the most widely used classes of generative models for describing structured and clustered data. In this paper we develop a new approach for the analysis of hierarchical mixture models. More specifically, using a text clustering problem as a motivation, we describe a natural generative process that creates a hierarchical mixture model for the data. In this process, an adversary starts with an arbitrary base distribution and then builds a topic hierarchy via some evolutionary process, where he controls the parameters of the process. We prove that under our assumptions, given a subset of topics that represent generalizations of one another (such as baseball → sports → base), for any document which was produced via some topic in this hierarchy, we can efficiently determine the most specialized topic in this subset, it still belongs to. The quality of the classification is independent of the total number of topics in the hierarchy and our algorithm does not need to know the total number of topics in advance. Our approach also yields an algorithm for clustering and unsupervised topical tree reconstruction. We validate our model by showing that properties predicted by our theoretical results carry over to real data. We then apply our clustering algorithm to two different datasets: (i) "20 newsgroups"[19] and (ii) a snapshot of abstracts of arXiv {2} (15 categories, ~240,000 abstracts). In both cases our algorithm performs extremely well.

REFERENCES

• 1: A. Ambainis , R. Desper , M. Farach , S. Kannan, Nearly tight bounds on the learnability of evolution, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.524, October 19-22, 1997
• 2: Arxiv. http://www.arxiv.org.
• 3: D. Blei, T. Gri, M. Jordan, and J. Tenenbaum. Hierarchical topic models and the nested chinese restaurant process. In NIPS, 2004.
• 4: David M. Blei , Andrew Y. Ng , Michael I. Jordan, Latent dirichlet allocation, The Journal of Machine Learning Research, 3, p.993-1022, 3/1/2003 [doi>10.1162/jmlr.2003.3.4-5.993]
• 5: Anirban Dasgupta , John Hopcroft , Jon Kleinberg , Mark Sandler, On Learning Mixtures of Heavy-Tailed Distributions, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.491-500, October 23-25, 2005 [doi>10.1109/SFCS.2005.56]
• 6: 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
• 7: Martin Farach , Sampath Kannan, Efficient algorithms for inverting evolution, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.230-236, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237868]
• 8: Katherine A. Heller , Zoubin Ghahramani, Bayesian hierarchical clustering, Proceedings of the 22nd international conference on Machine learning, p.297-304, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102389]
• 9: W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58:301:13--30, March 1963.
• 10: Thomas Hofmann, The Cluster-Abstraction Model: Unsupervised Learning of Topic Hierarchies from Text Data, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.682-687, July 31-August 06, 1999
• 11: Thomas Hofmann, Unsupervised learning by probabilistic latent semantic analysis, Machine Learning, v.42 n.1/2, p.177-196, Jan. 2001 [doi>10.1023/A:1007617005950]
• 12: Thomas Hofmann , Jan Puzicha, Latent Class Models for Collaborative Filtering, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.688-693, July 31-August 06, 1999
• 13: A. Jepson and M. Black. Mixture models for optical flow computation. Partitioning Data Sets I, 1993.
• 14: L. B.-T. Jones, R. Bean, G. McLachlan, and J. Zhu. Intelligent Data Engineering and Automated Learning -- I, volume 3578, chapter Application of Mixture Models to Detect Differentially Expressed Genes, pages 422----431. Springer, 2005.
• 15: Jon Kleinberg , Mark Sandler, Using mixture models for collaborative filtering, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007439]
• 16: A. McCallum and K. Nigam. A comparison of event models for naive bayes text classification. In AAAI-98 Workshop on Learning for Text Categorization, 1998.
• 17: A. K. McCallum. Multi-label text classification with a mixture model trained by em. In Proc. of AAAI'99 workshop on text learning, 1999.
• 18: G. McLachlan and K. Basford. Mixture Models, inference and applications to clustering. Marcel Dekker, 1987.
• 19: T. Mitchell. 20 newsgroups.
• 20: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 21: L. A. Salter. Algorithms for phylogenetic tree reconstruction, 2000.
• 22: Mark Sandler, On the use of linear programming for unsupervised text classification, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081901]
• 23: Nir Ailon , Moses Charikar, Fitting tree metrics: Hierarchical clustering and Phylogeny, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.73-82, October 23-25, 2005 [doi>10.1109/SFCS.2005.36]
• 24: C. Stauffer and W. Grimson. Adaptive background mixture models for real-time tracking. In CVPR, volume II, pages 246--252, 1999.
• 25: Y. Teh, M. Jordan, M. Beal, and D. Blei. Hierarchical dirichlet processes. J. of the American Statistical Association, 2006.
• 26: Kristina Toutanova , Francine Chen , Kris Popat , Thomas Hofmann, Text classification in a hierarchical mixture model for small training sets, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502604]
• 27: Yair Weiss , Edward H. Adelson, A Unified Mixture Framework for Motion Segmentation: Incorporating Spatial Coherence and Estimating the Number of Models, Proceedings of the 1996 Conference on Computer Vision and Pattern Recognition (CVPR '96), p.321, June 18-20, 1996

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.0 General

General Terms:
Algorithms, Experimentation, Theory

Keywords:
hierarchical clustering, mixture models, topical models