2014 ReducingtheSamplingComplexityof

• (Li et al., 2014) ⇒ Aaron Q. Li, Amr Ahmed, Sujith Ravi, and Alexander J. Smola. (2014). “Reducing the Sampling Complexity of Topic Models.” In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2014) Journal. ISBN:978-1-4503-2956-9 doi:10.1145/2623330.2623756

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222014%22+Reducing+the+Sampling+Complexity+of+Topic+Models
• http://dl.acm.org/citation.cfm?id=2623330.2623756&preflayout=flat#citedby

Quotes

Author Keywords

• Alias method; complexity measures; graph algorithms; performance measures; sampling; scalability; topic models

Abstract

Inference in topic models typically involves a sampling step to associate latent variables with observations. Unfortunately the generative model loses sparsity as the amount of data increases, requiring O (k) operations per word for k topics. In this paper we propose an algorithm which scales linearly with the number of actually instantiated topics k_d in the document. For large document collections and in structured hierarchical models k_d ll k. This yields an order of magnitude speedup. Our method applies to a wide variety of statistical models such as PDP [16, 4] and HDP [19].

At its core is the idea that dense, slowly changing distributions can be approximated efficiently by the combination of a Metropolis-Hastings step, use of sparsity, and amortized constant time sampling via Walker's alias method.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2014 ReducingtheSamplingComplexityof	Alexander J. Smola Amr Ahmed Aaron Q. Li Sujith Ravi			Reducing the Sampling Complexity of Topic Models				10.1145/2623330.2623756		2014