nips nips2011 nips2011-58 nips2011-58-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: David Sontag, Dan Roy
Abstract: We consider the computational complexity of probabilistic inference in Latent Dirichlet Allocation (LDA). First, we study the problem of finding the maximum a posteriori (MAP) assignment of topics to words, where the document’s topic distribution is integrated out. We show that, when the e↵ective number of topics per document is small, exact inference takes polynomial time. In contrast, we show that, when a document has a large number of topics, finding the MAP assignment of topics to words in LDA is NP-hard. Next, we consider the problem of finding the MAP topic distribution for a document, where the topic-word assignments are integrated out. We show that this problem is also NP-hard. Finally, we briefly discuss the problem of sampling from the posterior, showing that this is NP-hard in one restricted setting, but leaving open the general question. 1
C. Biernacki and S. Chr´tien. Degeneracy in the maximum likelihood estimation of univariate e Gaussian mixtures with EM. Statist. Probab. Lett., 61(4):373–382, 2003. ISSN 0167-7152. D. Blei and J. McAuli↵e. Supervised topic models. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Adv. in Neural Inform. Processing Syst. 20, pages 121–128. MIT Press, Cambridge, MA, 2008. D. M. Blei, A. Y. Ng, and M. I. Jordan. Latent Dirichlet allocation. J. Mach. Learn. Res., 3: 993–1022, 2003. ISSN 1532-4435. T. L. Gri ths and M. Steyvers. Finding scientific topics. Proc. Natl. Acad. Sci. USA, 101(Suppl 1):5228–5235, 2004. doi: 10.1073/pnas.0307752101. E. Halperin and R. M. Karp. The minimum-entropy set cover problem. Theor. Comput. Sci., 348 (2):240–250, 2005. ISSN 0304-3975. doi: http://dx.doi.org/10.1016/j.tcs.2005.09.015. J. Kiefer and J. Wolfowitz. Consistency of the maximum likelihood estimator in the presence of infinitely many incidental parameters. Ann. Math. Statist., 27:887–906, 1956. ISSN 0003-4851. J. Kivinen and M. K. Warmuth. Exponentiated gradient versus gradient descent for linear predictors. Inform. and Comput., 132, 1995. A. Krause and V. Cevher. Submodular dictionary selection for sparse representation. In Proc. Int. Conf. on Machine Learning (ICML), 2010. S. Lacoste-Julien, F. Sha, and M. Jordan. DiscLDA: Discriminative learning for dimensionality reduction and classification. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Adv. in Neural Inform. Processing Syst. 21, pages 897–904. 2009. W. Li and A. McCallum. Semi-supervised sequence modeling with syntactic topic models. In Proc. of the 20th Nat. Conf. on Artificial Intelligence, volume 2, pages 813–818. AAAI Press, 2005. L. Lovasz and S. Vempala. Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization. In Proc. of the 47th Ann. IEEE Symp. on Foundations of Comput. Sci., pages 57–68. IEEE Computer Society, 2006. ISBN 0-7695-2720-5. P. Miettinen, T. Mielik¨inen, A. Gionis, G. Das, and H. Mannila. The discrete basis problem. IEEE a Trans. Knowl. Data Eng., 20(10):1348–1362, 2008. I. Mukherjee and D. M. Blei. Relative performance guarantees for approximate inference in latent Dirichlet allocation. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Adv. in Neural Inform. Processing Syst. 21, pages 1129–1136. 2009. I. Porteous, D. Newman, A. Ihler, A. Asuncion, P. Smyth, and M. Welling. Fast collapsed gibbs sampling for latent dirichlet allocation. In Proc. of the 14th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pages 569–577, New York, NY, USA, 2008. ACM. A. Schrijver. Combinatorial optimization. Polyhedra and e ciency. Vol. A, volume 24 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 2003. ISBN 3-540-44389-4. Paths, flows, matchings, Chapters 1–38. J. K. Sepp¨nen, E. Bingham, and H. Mannila. A simple algorithm for topic identification in 0-1 a data. In Proc. of the 7th European Conf. on Principles and Practice of Knowledge Discovery in Databases, pages 423–434. Springer-Verlag, 2003. Y. W. Teh, D. Newman, and M. Welling. A collapsed variational Bayesian inference algorithm for latent Dirichlet allocation. In Adv. in Neural Inform. Processing Syst. 19, volume 19, 2007. A. L. Yuille and A. Rangarajan. The concave-convex procedure. Neural Comput., 15:915–936, April 2003. ISSN 0899-7667. 9