Bethe Projections for Non-Local Inference

Luke Vilnis UMass Amherst, David Belanger UMass Amherst, Daniel Sheldon UMass Amherst, Andrew McCallum UMass Amherst
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:249-258, 2015.

Abstract

Many inference problems in structured prediction are naturally solved by augmenting a tractable dependency structure with complex, non-local auxiliary objectives. This includes the mean field family of variational inference algorithms, soft- or hard-constrained inference using Lagrangian relaxation or linear programming, collective graphical models, and forms of semi-supervised learning such as posterior regularization. We present a method to discriminatively learn broad families of inference objectives, capturing powerful non-local statistics of the latent variables, while maintaining tractable and provably fast inference using non-Euclidean projected gradient descent with a distance-generating function given by the Bethe entropy. We demonstrate the performance and flexibility of our method by (1) extracting structured citations from research papers by learning soft global constraints, (2) achieving state-of-the-art results on a widely-used handwriting recognition task using a novel learned non-convex inference procedure, and (3) providing a fast and highly scalable algorithm for the challenging problem of inference in a collective graphical model applied to bird migration.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-amherst15b, title = {{B}ethe Projections for Non-Local Inference}, author = {Amherst, Luke Vilnis UMass and Amherst, David Belanger UMass and Amherst, Daniel Sheldon UMass and Amherst, Andrew McCallum UMass}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {249--258}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/amherst15b/amherst15b.pdf}, url = {https://proceedings.mlr.press/r13/amherst15b.html}, abstract = {Many inference problems in structured prediction are naturally solved by augmenting a tractable dependency structure with complex, non-local auxiliary objectives. This includes the mean field family of variational inference algorithms, soft- or hard-constrained inference using Lagrangian relaxation or linear programming, collective graphical models, and forms of semi-supervised learning such as posterior regularization. We present a method to discriminatively learn broad families of inference objectives, capturing powerful non-local statistics of the latent variables, while maintaining tractable and provably fast inference using non-Euclidean projected gradient descent with a distance-generating function given by the Bethe entropy. We demonstrate the performance and flexibility of our method by (1) extracting structured citations from research papers by learning soft global constraints, (2) achieving state-of-the-art results on a widely-used handwriting recognition task using a novel learned non-convex inference procedure, and (3) providing a fast and highly scalable algorithm for the challenging problem of inference in a collective graphical model applied to bird migration.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Bethe Projections for Non-Local Inference %A Luke Vilnis UMass Amherst %A David Belanger UMass Amherst %A Daniel Sheldon UMass Amherst %A Andrew McCallum UMass Amherst %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-amherst15b %I PMLR %P 249--258 %U https://proceedings.mlr.press/r13/amherst15b.html %V R13 %X Many inference problems in structured prediction are naturally solved by augmenting a tractable dependency structure with complex, non-local auxiliary objectives. This includes the mean field family of variational inference algorithms, soft- or hard-constrained inference using Lagrangian relaxation or linear programming, collective graphical models, and forms of semi-supervised learning such as posterior regularization. We present a method to discriminatively learn broad families of inference objectives, capturing powerful non-local statistics of the latent variables, while maintaining tractable and provably fast inference using non-Euclidean projected gradient descent with a distance-generating function given by the Bethe entropy. We demonstrate the performance and flexibility of our method by (1) extracting structured citations from research papers by learning soft global constraints, (2) achieving state-of-the-art results on a widely-used handwriting recognition task using a novel learned non-convex inference procedure, and (3) providing a fast and highly scalable algorithm for the challenging problem of inference in a collective graphical model applied to bird migration. %Z Reissued by PMLR on 04 October 2026.
APA
Amherst, L.V.U., Amherst, D.B.U., Amherst, D.S.U. & Amherst, A.M.U.. (2015). Bethe Projections for Non-Local Inference. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:249-258 Available from https://proceedings.mlr.press/r13/amherst15b.html. Reissued by PMLR on 04 October 2026.

Related Material