  We examine the effect of clamping variables for approximate inference in
undirected graphical models with pairwise relationships and discrete variables.
For any number of variable labels, we demonstrate that clamping and summing
approximate sub-partition functions can lead only to a decrease in the
partition function estimate for TRW, and an increase for the naive mean field
method, in each case guaranteeing an improvement in the approximation and
bound. We next focus on binary variables, add the Bethe approximation to
consideration and examine ways to choose good variables to clamp, introducing
new methods. We show the importance of identifying highly frustrated cycles,
and of checking the singleton entropy of a variable. We explore the value of
our methods by empirical analysis and draw lessons to guide practitioners.
