Lifted Tree-Reweighted Variational Inference

We analyze variational inference for highly symmetric 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 propagation, our formulation leads to a convex optimization problem for lifted marginal inference and provides an upper bound on the partition function. We provide two approaches for improving the lifted TRW upper bound. The first is a method for efficiently computing maximum spanning trees in highly symmetric graphs, which can be used to optimize the TRW edge appearance probabilities. The second is a method for tightening the relaxation of the marginal polytope using lifted cycle inequalities and novel exchangeable cluster consistency constraints.

• Publication year

  2014

• Venue

  Conference on Uncertainty in Artificial Intelligence

• Publication date

  2014-06-16

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1406.4200
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the Complexity and Approximation of Binary Evidence in Lifted Inference

  2013cited by this paper
• Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization

  2013cited by this paper
• Markov Chains on Orbits of Permutation Groups

  2012cited by this paper
• Exact Lifted Inference with Distinct Soft Evidence on Every Object

  2012influential reference
• Automorphism Groups of Graphical Models and Lifted Variational Inference

  2012cited by this paper
• Probabilistic theorem proving

  2011cited by this paper
• Convergent Decomposition Solvers for Tree-reweighted Free Energies

  2011cited by this paper
• Informed Lifting for Message-Passing

  2010cited by this paper
• Approximate Lifted Belief Propagation

  2010cited by this paper
• Counting Belief Propagation

  2009cited by this paper
• Lifted First-Order Belief Propagation

  2008influential reference
• Lifted Probabilistic Inference with Counting Formulas

  2008cited by this paper
• Tightening LP Relaxations for MAP using Message Passing

  2008cited by this paper
• Graphical Models, Exponential Families, and Variational Inference

  2008cited by this paper
• New Outer Bounds on the Marginal Polytope

  2007cited by this paper
• Convergent Propagation Algorithms via Oriented Trees

  2007cited by this paper
• Template Based Inference in Symmetric Relational Markov Random Fields

  2007influential reference
• Minimizing and Learning Energy Functions for Side-Chain Prediction

  2007cited by this paper
• An introduction to exponential random graph (p*) models for social networks

  2007cited by this paper
• Towards an Integrated Protein–Protein Interaction Network: A Relational Markov Network Approach

  2005cited by this paper
• Lifted First-Order Probabilistic Inference

  2005cited by this paper
• Tree-based reparameterization framework for analysis of sum-product and related algorithms

  2003cited by this paper
• A new class of upper bounds on the log partition function

  2002cited by this paper
• Algebraic Graph Theory

  2001cited by this paper
• A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems

  1990cited by this paper
• A hierarchy of relaxation between the continuous and convex hull representations

  1990cited by this paper
• On the cut polytope

  1986cited by this paper
• An algorithm for quadratic programming

  1956cited by this paper

• Lifted Hybrid Variational Inference

  2020influential citation
• State-Space Abstractions for Probabilistic Inference: A Systematic Review

  2018cites this paper
• Lifted Generalized Dual Decomposition

  2018influential citation
• Lifted Weighted Mini-Bucket

  2018cites this paper
• Learning Representations of Text through Language and Discourse Modeling: From Characters to Sentences

  2018cites this paper
• Lifted Region-Based Belief Propagation

  2016cites this paper
• Equitable Partitions of Concave Free Energies

  2015influential citation
• A Fast Variational Approach for Learning Markov Random Field Language Models

  2015cites this paper
• Towards High-Level Probabilistic Reasoning with Lifted Inference

  2015cites this paper
• Unifying Logical and Statistical AI

  2006cites this paper