Clamping Variables and Approximate Inference
It was recently proved using graph covers (Ruozzi, 2012) that the Bethe partition function is upper bounded by the true partition function for a binary pairwise model that is attractive. Here we provide a new, arguably simpler proof from first principles. We make use of the idea of clamping a variable to a particular value. For an attractive model, we show that summing over the Bethe partition functions for each sub-model obtained after clamping any variable can only raise (and hence improve) the approximation. In fact, we derive a stronger result that may have other useful implications. Repeatedly clamping until we obtain a model with no cycles, where the Bethe approximation is exact, yields the result. We also provide a related lower bound on a broad class of approximate partition functions of general pairwise multi-label models that depends only on the topology. We demonstrate that clamping a few wisely chosen variables can be of practical value by dramatically reducing approximation error.
Review for On the Power of ClampingSummary: This paper presents some deep technical results on inferencein a particular class of undirected graphical models.  By clampingwell-chosen variables, a complex graph can be split into smallergraphs, which can each be processed independently, and the resultscombined.  The authors present approximation bounds for the partitionfunction in such an approach, and demonstrate that clamping improvesapproximation error.This paper is a well-written deep dive into a specific inferenceapproach on a specific model class (binary pairwise model withattractive potentials).  Proofs of the main technical results are thecenterpiece of the paper, although some simple experiments demonstratethat the approach can have practical value by reducing approximationerror.Overall I found this paper well-done, although a bit dense at times.While it's unclear to me how generally interesting these results are(given the fairly limited class of applicable problems), the materialpushes the state-of-the-art in a long line of similar work that thecommunity considers valuable.One weakness of this paper is the general lack of connection to otherapproximation methods.  As the authors note, the idea of conditioningon a variable (or set of variables) and approximating over the resthas a long and fruitful history.  Given that rich and variedliterature, it would have been interesting to see how other methodscompare to clamping+Bethe, either theoretically or practically. Theauthors do compare to TRW in the experiments, but I'm left wonderingif there are other serious approximation methods for the same class ofmodels, and if so, what their performance/guarantees might look like.Along those lines, I strongly encourage the authors to pursue the ideaoutlined in the last paragraph: "It is tempting to speculate thatsimilar results may be found for other approximations. For example,for some methods that upper bound the partition function, such as TRW,it may be possible to show that a lower (hence better) approximationis always achieved when a variable is clamped."  That would beinteresting indeed.Minor comments:You prove that Z_B <= Z, and that Z_B^i >= Z_B.  Perhaps I missed it,but can you say anything about the relationship between Z_B^i and Z?Is clamping upper-bounded by Z?