Provable Algorithms for Inference in Topic Models

Sanjeev Arora, Rong Ge, Frederic Koehler, Tengyu Ma, Ankur Moitra
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2859-2867, 2016.

Abstract

Recently, there has been considerable progress on designing algorithms with provable guarantees —typically using linear algebraic methods—for parameter learning in latent variable models. Designing provable algorithms for inference has proved more difficult. Here we take a first step towards provable inference in topic models. We leverage a property of topic models that enables us to construct simple linear estimators for the unknown topic proportions that have small variance, and consequently can work with short documents. Our estimators also correspond to finding an estimate around which the posterior is well-concentrated. We show lower bounds that for shorter documents it can be information theoretically impossible to find the hidden topics. Finally, we give empirical results that demonstrate that our algorithm works on realistic topic models. It yields good solutions on synthetic data and runs in time comparable to a single iteration of Gibbs sampling.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-arorab16, title = {Provable Algorithms for Inference in Topic Models}, author = {Arora, Sanjeev and Ge, Rong and Koehler, Frederic and Ma, Tengyu and Moitra, Ankur}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2859--2867}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/arorab16.pdf}, url = {https://proceedings.mlr.press/v48/arorab16.html}, abstract = {Recently, there has been considerable progress on designing algorithms with provable guarantees —typically using linear algebraic methods—for parameter learning in latent variable models. Designing provable algorithms for inference has proved more difficult. Here we take a first step towards provable inference in topic models. We leverage a property of topic models that enables us to construct simple linear estimators for the unknown topic proportions that have small variance, and consequently can work with short documents. Our estimators also correspond to finding an estimate around which the posterior is well-concentrated. We show lower bounds that for shorter documents it can be information theoretically impossible to find the hidden topics. Finally, we give empirical results that demonstrate that our algorithm works on realistic topic models. It yields good solutions on synthetic data and runs in time comparable to a single iteration of Gibbs sampling.} }
Endnote
%0 Conference Paper %T Provable Algorithms for Inference in Topic Models %A Sanjeev Arora %A Rong Ge %A Frederic Koehler %A Tengyu Ma %A Ankur Moitra %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-arorab16 %I PMLR %P 2859--2867 %U https://proceedings.mlr.press/v48/arorab16.html %V 48 %X Recently, there has been considerable progress on designing algorithms with provable guarantees —typically using linear algebraic methods—for parameter learning in latent variable models. Designing provable algorithms for inference has proved more difficult. Here we take a first step towards provable inference in topic models. We leverage a property of topic models that enables us to construct simple linear estimators for the unknown topic proportions that have small variance, and consequently can work with short documents. Our estimators also correspond to finding an estimate around which the posterior is well-concentrated. We show lower bounds that for shorter documents it can be information theoretically impossible to find the hidden topics. Finally, we give empirical results that demonstrate that our algorithm works on realistic topic models. It yields good solutions on synthetic data and runs in time comparable to a single iteration of Gibbs sampling.
RIS
TY - CPAPER TI - Provable Algorithms for Inference in Topic Models AU - Sanjeev Arora AU - Rong Ge AU - Frederic Koehler AU - Tengyu Ma AU - Ankur Moitra BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-arorab16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 2859 EP - 2867 L1 - http://proceedings.mlr.press/v48/arorab16.pdf UR - https://proceedings.mlr.press/v48/arorab16.html AB - Recently, there has been considerable progress on designing algorithms with provable guarantees —typically using linear algebraic methods—for parameter learning in latent variable models. Designing provable algorithms for inference has proved more difficult. Here we take a first step towards provable inference in topic models. We leverage a property of topic models that enables us to construct simple linear estimators for the unknown topic proportions that have small variance, and consequently can work with short documents. Our estimators also correspond to finding an estimate around which the posterior is well-concentrated. We show lower bounds that for shorter documents it can be information theoretically impossible to find the hidden topics. Finally, we give empirical results that demonstrate that our algorithm works on realistic topic models. It yields good solutions on synthetic data and runs in time comparable to a single iteration of Gibbs sampling. ER -
APA
Arora, S., Ge, R., Koehler, F., Ma, T. & Moitra, A.. (2016). Provable Algorithms for Inference in Topic Models. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:2859-2867 Available from https://proceedings.mlr.press/v48/arorab16.html.

Related Material