Lifted Tree-Reweighted Variational Inference∗ Hung Hai Bui Natural Language Understanding Lab Nuance Communications

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.