Fast Amortized Inference and Learning in Log-linear Models with Randomly Perturbed Nearest Neighbor Search

Stephen Mussmann, Daniel Levy, Stefano Ermon
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:371-380, 2017.

Abstract

Inference in log-linear models scales linearly in the size of output space in the worst-case. This is often a bottleneck in natural language processing and computer vision tasks when the output space is feasibly enumerable but very large. We propose a method to per- form inference in log-linear models with sub- linear amortized cost. Our idea hinges on using Gumbel random variable perturbations and a pre-computed Maximum Inner Product Search data structure to access the most-likely elements in sublinear amortized time. Our method yields provable runtime and accuracy guarantees. Further, we present empirical ex- periments on ImageNet and Word Embeddings showing significant speedups for sampling, in- ference, and learning in log-linear models.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-mussmann17a, title = {Fast Amortized Inference and Learning in Log-linear Models with Randomly Perturbed Nearest Neighbor Search}, author = {Mussmann, Stephen and Levy, Daniel and Ermon, Stefano}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {371--380}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/mussmann17a/mussmann17a.pdf}, url = {https://proceedings.mlr.press/r15/mussmann17a.html}, abstract = {Inference in log-linear models scales linearly in the size of output space in the worst-case. This is often a bottleneck in natural language processing and computer vision tasks when the output space is feasibly enumerable but very large. We propose a method to per- form inference in log-linear models with sub- linear amortized cost. Our idea hinges on using Gumbel random variable perturbations and a pre-computed Maximum Inner Product Search data structure to access the most-likely elements in sublinear amortized time. Our method yields provable runtime and accuracy guarantees. Further, we present empirical ex- periments on ImageNet and Word Embeddings showing significant speedups for sampling, in- ference, and learning in log-linear models.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Fast Amortized Inference and Learning in Log-linear Models with Randomly Perturbed Nearest Neighbor Search %A Stephen Mussmann %A Daniel Levy %A Stefano Ermon %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-mussmann17a %I PMLR %P 371--380 %U https://proceedings.mlr.press/r15/mussmann17a.html %V R15 %X Inference in log-linear models scales linearly in the size of output space in the worst-case. This is often a bottleneck in natural language processing and computer vision tasks when the output space is feasibly enumerable but very large. We propose a method to per- form inference in log-linear models with sub- linear amortized cost. Our idea hinges on using Gumbel random variable perturbations and a pre-computed Maximum Inner Product Search data structure to access the most-likely elements in sublinear amortized time. Our method yields provable runtime and accuracy guarantees. Further, we present empirical ex- periments on ImageNet and Word Embeddings showing significant speedups for sampling, in- ference, and learning in log-linear models. %Z Reissued by PMLR on 04 October 2026.
APA
Mussmann, S., Levy, D. & Ermon, S.. (2017). Fast Amortized Inference and Learning in Log-linear Models with Randomly Perturbed Nearest Neighbor Search. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:371-380 Available from https://proceedings.mlr.press/r15/mussmann17a.html. Reissued by PMLR on 04 October 2026.

Related Material