We study a rich family of distributions that capture variable interactions signifi-cantly more expressive than those representable with low-treewidth or pairwisegraphical models, or log-supermodular models. We call thesecooperative graph-ical models. Yet, this family retains structure, which we carefully exploit forefficient inference techniques. Our algorithms combine the polyhedral structure ofsubmodular functions in new ways with variational inference methods to obtainboth lower and upper bounds on the partition function. While ourfully convexupperbound is minimized as an SDP or via tree-reweighted belief propagation, our lowerbound is tightened via belief propagation or mean-field algorithms. The resultingalgorithms are easy to implement and, as our experiments show, effectively obtaingood bounds and marginals for synthetic and real-world examples.

Top