Improving Optimization-Based Approximate Inference by Clamping Variables

Junyao Zhao, Josip Djolonga, Sebastian Tschiatschek, Andreas Krause
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:441-450, 2017.

Abstract

While central to the application of probabilis- tic models to discrete data, the problem of marginal inference is in general intractable and efficient approximation schemes need to exploit the problem structure. Recently, there have been efforts to develop inference techniques that do not necessarily make factorization as- sumptions about the distribution, but rather ex- ploit the fact that sometimes there exist effi- cient algorithms for finding the MAP config- uration. In this paper, we theoretically prove that for discrete multi-label models the bounds on the partition function obtained by two of these approaches, Perturb-and-MAP and the bound from the infinite R{é}nyi divergence, can be only improved by clamping any subset of the variables. For the case of log-supermodular models we provide a more detailed analysis and develop a set of efficient strategies for choos- ing the order in which the variables should be clamped. Finally, we present a number of nu- merical experiments showcasing the improve- ments obtained by the proposed methods on several models.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-zhao17a, title = {Improving Optimization-Based Approximate Inference by Clamping Variables}, author = {Zhao, Junyao and Djolonga, Josip and Tschiatschek, Sebastian and Krause, Andreas}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {441--450}, 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/zhao17a/zhao17a.pdf}, url = {https://proceedings.mlr.press/r15/zhao17a.html}, abstract = {While central to the application of probabilis- tic models to discrete data, the problem of marginal inference is in general intractable and efficient approximation schemes need to exploit the problem structure. Recently, there have been efforts to develop inference techniques that do not necessarily make factorization as- sumptions about the distribution, but rather ex- ploit the fact that sometimes there exist effi- cient algorithms for finding the MAP config- uration. In this paper, we theoretically prove that for discrete multi-label models the bounds on the partition function obtained by two of these approaches, Perturb-and-MAP and the bound from the infinite R{é}nyi divergence, can be only improved by clamping any subset of the variables. For the case of log-supermodular models we provide a more detailed analysis and develop a set of efficient strategies for choos- ing the order in which the variables should be clamped. Finally, we present a number of nu- merical experiments showcasing the improve- ments obtained by the proposed methods on several models.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Improving Optimization-Based Approximate Inference by Clamping Variables %A Junyao Zhao %A Josip Djolonga %A Sebastian Tschiatschek %A Andreas Krause %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-zhao17a %I PMLR %P 441--450 %U https://proceedings.mlr.press/r15/zhao17a.html %V R15 %X While central to the application of probabilis- tic models to discrete data, the problem of marginal inference is in general intractable and efficient approximation schemes need to exploit the problem structure. Recently, there have been efforts to develop inference techniques that do not necessarily make factorization as- sumptions about the distribution, but rather ex- ploit the fact that sometimes there exist effi- cient algorithms for finding the MAP config- uration. In this paper, we theoretically prove that for discrete multi-label models the bounds on the partition function obtained by two of these approaches, Perturb-and-MAP and the bound from the infinite R{é}nyi divergence, can be only improved by clamping any subset of the variables. For the case of log-supermodular models we provide a more detailed analysis and develop a set of efficient strategies for choos- ing the order in which the variables should be clamped. Finally, we present a number of nu- merical experiments showcasing the improve- ments obtained by the proposed methods on several models. %Z Reissued by PMLR on 04 October 2026.
APA
Zhao, J., Djolonga, J., Tschiatschek, S. & Krause, A.. (2017). Improving Optimization-Based Approximate Inference by Clamping Variables. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:441-450 Available from https://proceedings.mlr.press/r15/zhao17a.html. Reissued by PMLR on 04 October 2026.

Related Material