Learning and Inference via Maximum Inner Product Search

Stephen Mussmann, Stefano Ermon
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2587-2596, 2016.

Abstract

A large class of commonly used probabilistic models known as log-linear models are defined up to a normalization constant.Typical learning algorithms for such models require solving a sequence of probabilistic inference queries. These inferences are typically intractable, and are a major bottleneck for learning models with large output spaces. In this paper, we provide a new approach for amortizing the cost of a sequence of related inference queries, such as the ones arising during learning. Our technique relies on a surprising connection with algorithms developed in the past two decades for similarity search in large data bases. Our approach achieves improved running times with provable approximation guarantees. We show that it performs well both on synthetic data and neural language models with large output spaces.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-mussmann16, title = {Learning and Inference via Maximum Inner Product Search}, author = {Mussmann, Stephen and Ermon, Stefano}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2587--2596}, 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/mussmann16.pdf}, url = {https://proceedings.mlr.press/v48/mussmann16.html}, abstract = {A large class of commonly used probabilistic models known as log-linear models are defined up to a normalization constant.Typical learning algorithms for such models require solving a sequence of probabilistic inference queries. These inferences are typically intractable, and are a major bottleneck for learning models with large output spaces. In this paper, we provide a new approach for amortizing the cost of a sequence of related inference queries, such as the ones arising during learning. Our technique relies on a surprising connection with algorithms developed in the past two decades for similarity search in large data bases. Our approach achieves improved running times with provable approximation guarantees. We show that it performs well both on synthetic data and neural language models with large output spaces.} }
Endnote
%0 Conference Paper %T Learning and Inference via Maximum Inner Product Search %A Stephen Mussmann %A Stefano Ermon %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-mussmann16 %I PMLR %P 2587--2596 %U https://proceedings.mlr.press/v48/mussmann16.html %V 48 %X A large class of commonly used probabilistic models known as log-linear models are defined up to a normalization constant.Typical learning algorithms for such models require solving a sequence of probabilistic inference queries. These inferences are typically intractable, and are a major bottleneck for learning models with large output spaces. In this paper, we provide a new approach for amortizing the cost of a sequence of related inference queries, such as the ones arising during learning. Our technique relies on a surprising connection with algorithms developed in the past two decades for similarity search in large data bases. Our approach achieves improved running times with provable approximation guarantees. We show that it performs well both on synthetic data and neural language models with large output spaces.
RIS
TY - CPAPER TI - Learning and Inference via Maximum Inner Product Search AU - Stephen Mussmann AU - Stefano Ermon 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-mussmann16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 2587 EP - 2596 L1 - http://proceedings.mlr.press/v48/mussmann16.pdf UR - https://proceedings.mlr.press/v48/mussmann16.html AB - A large class of commonly used probabilistic models known as log-linear models are defined up to a normalization constant.Typical learning algorithms for such models require solving a sequence of probabilistic inference queries. These inferences are typically intractable, and are a major bottleneck for learning models with large output spaces. In this paper, we provide a new approach for amortizing the cost of a sequence of related inference queries, such as the ones arising during learning. Our technique relies on a surprising connection with algorithms developed in the past two decades for similarity search in large data bases. Our approach achieves improved running times with provable approximation guarantees. We show that it performs well both on synthetic data and neural language models with large output spaces. ER -
APA
Mussmann, S. & Ermon, S.. (2016). Learning and Inference via Maximum Inner Product Search. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:2587-2596 Available from https://proceedings.mlr.press/v48/mussmann16.html.

Related Material