Lifted Tree-Reweighted Variational Inference

Hung Bui Nuance, Tuyen Huynh Jon von Neumann Institute Vietnam National University Ho Chi Minh City, David Sontag New York University
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:391-400, 2014.

Abstract

We analyze variational inference for highly sym- metric graphical models such as those arising from first-order probabilistic models. We first show that for these graphical models, the tree- reweighted variational objective lends itself to a compact lifted formulation which can be solved much more efficiently than the standard TRW formulation for the ground graphical model. Compared to earlier work on lifted belief prop- agation, our formulation leads to a convex op- timization problem for lifted marginal inference and provides an upper bound on the partition function. We provide two approaches for im- proving the lifted TRW upper bound. The first is a method for efficiently computing maxi- mum spanning trees in highly symmetric graphs, which can be used to optimize the TRW edge ap- pearance probabilities. The second is a method for tightening the relaxation of the marginal poly- tope using lifted cycle inequalities and novel ex- changeable cluster consistency constraints.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-nuance14a, title = {Lifted Tree-Reweighted Variational Inference}, author = {Nuance, Hung Bui and City, Tuyen Huynh Jon von Neumann Institute Vietnam National University Ho Chi Minh and University, David Sontag New York}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {391--400}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/nuance14a/nuance14a.pdf}, url = {https://proceedings.mlr.press/r12/nuance14a.html}, abstract = {We analyze variational inference for highly sym- metric graphical models such as those arising from first-order probabilistic models. We first show that for these graphical models, the tree- reweighted variational objective lends itself to a compact lifted formulation which can be solved much more efficiently than the standard TRW formulation for the ground graphical model. Compared to earlier work on lifted belief prop- agation, our formulation leads to a convex op- timization problem for lifted marginal inference and provides an upper bound on the partition function. We provide two approaches for im- proving the lifted TRW upper bound. The first is a method for efficiently computing maxi- mum spanning trees in highly symmetric graphs, which can be used to optimize the TRW edge ap- pearance probabilities. The second is a method for tightening the relaxation of the marginal poly- tope using lifted cycle inequalities and novel ex- changeable cluster consistency constraints.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Lifted Tree-Reweighted Variational Inference %A Hung Bui Nuance %A Tuyen Huynh Jon von Neumann Institute Vietnam National University Ho Chi Minh City %A David Sontag New York University %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-nuance14a %I PMLR %P 391--400 %U https://proceedings.mlr.press/r12/nuance14a.html %V R12 %X We analyze variational inference for highly sym- metric graphical models such as those arising from first-order probabilistic models. We first show that for these graphical models, the tree- reweighted variational objective lends itself to a compact lifted formulation which can be solved much more efficiently than the standard TRW formulation for the ground graphical model. Compared to earlier work on lifted belief prop- agation, our formulation leads to a convex op- timization problem for lifted marginal inference and provides an upper bound on the partition function. We provide two approaches for im- proving the lifted TRW upper bound. The first is a method for efficiently computing maxi- mum spanning trees in highly symmetric graphs, which can be used to optimize the TRW edge ap- pearance probabilities. The second is a method for tightening the relaxation of the marginal poly- tope using lifted cycle inequalities and novel ex- changeable cluster consistency constraints. %Z Reissued by PMLR on 04 October 2026.
APA
Nuance, H.B., City, T.H.J.v.N.I.V.N.U.H.C.M. & University, D.S.N.Y.. (2014). Lifted Tree-Reweighted Variational Inference. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:391-400 Available from https://proceedings.mlr.press/r12/nuance14a.html. Reissued by PMLR on 04 October 2026.

Related Material