Augment and Reduce: Stochastic Inference for Large Categorical Distributions

Francisco Ruiz, Michalis Titsias, Adji Bousso Dieng, David Blei
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:4403-4412, 2018.

Abstract

Categorical distributions are ubiquitous in machine learning, e.g., in classification, language models, and recommendation systems. However, when the number of possible outcomes is very large, using categorical distributions becomes computationally expensive, as the complexity scales linearly with the number of outcomes. To address this problem, we propose augment and reduce (A&R), a method to alleviate the computational complexity. A&R uses two ideas: latent variable augmentation and stochastic variational inference. It maximizes a lower bound on the marginal likelihood of the data. Unlike existing methods which are specific to softmax, A&R is more general and is amenable to other categorical models, such as multinomial probit. On several large-scale classification problems, we show that A&R provides a tighter bound on the marginal likelihood and has better predictive performance than existing approaches.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-ruiz18a, title = {Augment and Reduce: Stochastic Inference for Large Categorical Distributions}, author = {Ruiz, Francisco and Titsias, Michalis and Dieng, Adji Bousso and Blei, David}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {4403--4412}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/ruiz18a/ruiz18a.pdf}, url = {https://proceedings.mlr.press/v80/ruiz18a.html}, abstract = {Categorical distributions are ubiquitous in machine learning, e.g., in classification, language models, and recommendation systems. However, when the number of possible outcomes is very large, using categorical distributions becomes computationally expensive, as the complexity scales linearly with the number of outcomes. To address this problem, we propose augment and reduce (A&R), a method to alleviate the computational complexity. A&R uses two ideas: latent variable augmentation and stochastic variational inference. It maximizes a lower bound on the marginal likelihood of the data. Unlike existing methods which are specific to softmax, A&R is more general and is amenable to other categorical models, such as multinomial probit. On several large-scale classification problems, we show that A&R provides a tighter bound on the marginal likelihood and has better predictive performance than existing approaches.} }
Endnote
%0 Conference Paper %T Augment and Reduce: Stochastic Inference for Large Categorical Distributions %A Francisco Ruiz %A Michalis Titsias %A Adji Bousso Dieng %A David Blei %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-ruiz18a %I PMLR %P 4403--4412 %U https://proceedings.mlr.press/v80/ruiz18a.html %V 80 %X Categorical distributions are ubiquitous in machine learning, e.g., in classification, language models, and recommendation systems. However, when the number of possible outcomes is very large, using categorical distributions becomes computationally expensive, as the complexity scales linearly with the number of outcomes. To address this problem, we propose augment and reduce (A&R), a method to alleviate the computational complexity. A&R uses two ideas: latent variable augmentation and stochastic variational inference. It maximizes a lower bound on the marginal likelihood of the data. Unlike existing methods which are specific to softmax, A&R is more general and is amenable to other categorical models, such as multinomial probit. On several large-scale classification problems, we show that A&R provides a tighter bound on the marginal likelihood and has better predictive performance than existing approaches.
APA
Ruiz, F., Titsias, M., Dieng, A.B. & Blei, D.. (2018). Augment and Reduce: Stochastic Inference for Large Categorical Distributions. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:4403-4412 Available from https://proceedings.mlr.press/v80/ruiz18a.html.

Related Material