Clamping Improves TRW and Mean Field Approximations

INTRODUCTION

Undirected graphical models, also called Markov random fields (MRFs), are a powerful and compact way to represent dependencies between variables, and have become a central tool in machine learning. A key challenge is to estimate the normalizing partition function. For example, this may be used to compute the probability of evidence, and is often a critical component of learning a model. An exact solution may be obtained via the junction tree method but unless the treewidth is bounded, this can take exponential time (Lauritzen and Spiegelhalter 1988). Hence, many approximate methods have been developed.

We focus on three popular approaches: the tree-reweighted approximation (TRW, Wainwright et al. 2005); the naïve mean field approximation (MF); and the Bethe approximation, often implemented via belief propagation (BP, Pearl 1988, Yedidia et al. 2000). In each case, we shall examine the effect on the respective partition function estimate of clamping one or more variables to each possible setting then combining the approximate results obtained on the clamped sub-models. See §2 for all definitions. If all variables are clamped, then the exact solution is obtained but with time exponential in the number of variables. Intuitively, as more variables are clamped, one would hope for better results, but this is not always the case and demonstrating guarantees has been challenging.

Weller and Jebara 2014b recently proved that for an attractive binary pairwise model (where it is known that the Bethe partition function yields a lower bound), the optimum Bethe partition function approximation can only increase (hence improve) for each variable clamped. They also provided an example of a non-attractive model (their Figure 5c) where clamping any variable leads to a worse approximation. Nevertheless, they introduced two heuristics for identifying a good variable to clamp, and for both attractive and mixed models, demonstrated empirically that approximation error can sometimes be significantly reduced by clamping even one variable.

We make the following contributions. For both TRW (which yields an upper bound) and MF (which provides a lower bound), we show that for pairwise models with any number of labels, and with any types of potentials, clamping can only improve the partition function estimate by decreasing and increasing the bounds respectively. Our proofs also yield insight into the approximate marginals returned. We next examine how to select a good sequence of variables to clamp. Although the methods of Weller and Jebara 2014b can perform well for choosing one variable, we show that, for some models, their methods perform poorly, particularly for selecting multiple variables. We introduce methods that strip a model to its core, search for strongly frustrated cycles, and make use of approximate singleton entropy. We provide an empirical analysis of all approaches, including a comparison against the ‘greedy’ choice of the best variable to clamp in hindsight after an exhaustive exploration. We conclude with observations to help guide practitioners.

The technique of branching or conditioning on variables, and approximating over the remaining variables has been explored in algorithms such as branch-and-cut (Padberg and Rinaldi 1991, Mitchell 2002), work on resolution versus search (Rish and Dechter 2000) and in (Darwiche 2009, Chapter 8). Cutset conditioning was discussed by Pearl 1988 and refined by Peot and Shachter 1991 as a method to render the remaining topology acyclic before using belief propagation. Eaton and Ghahramani 2009 developed this further, introducing conditioned belief propagation. Liu et al. 2012 explored feedback message passing for inference in Gaussian (not discrete) models, deriving strong results for attractive models. Bouchard and Zoeter 2009 discuss soft-binning to split configurations into subsets then apply the mean field approximation on each but without guarantees. Choi and Darwiche 2008 examined methods to approximate the partition function by deleting edges.

PRELIMINARIES AND NOTATION

We consider probability distribution $p(x)=e^{-E(x)}/Z(\theta)$, where $E(x)$ is the energy of configuration $x$. The partition function $Z(\theta)$ is a quantity of fundamental interest. It requires summing over all states to yield the normalizing constant $Z(\theta)=\sum_{x}\exp\left(-E(x)\right)$ which ensures that $\sum_{x}p(x)=1$. We denote the log-partition function, sometimes called the cumulant function, by $A(\theta)=\log Z(\theta)$.

For binary models, we assume a reparameterization such that $E(x)=-\sum_{i\in{\cal V}}\theta_{i}x_{i}-\sum_{(i,j)\in\mathcal{E}}\frac{W_{ij}}{2}\left[x_{i}x_{j}+(1-x_{i})(1-x_{j})\right]$, with singleton potentials $\theta_{i}$ and edge weights $W_{ij}$. If $W_{ij}\geq 0$ then the edge $(i,j)$ is attractive (in which case, the edge tends to pull $X_{i}$ and $X_{j}$ toward the same value). If $W_{ij}<0$ then the edge is repulsive. If all edges of a model are attractive, then the model is called attractive, else it is mixed.

1 Clamping a Variable and Related Definitions

These do not hold in general for approximate values but motivate the following definitions, that are achieved by clamping variable $X_{i}$ and summing approximate sub-partition functions:

We next show that for TRW and MF, clamping and summing always reduces error and improves bounds for any model type.

NEW RESULTS FOR THE TREE-REWEIGHTED APPROXIMATION TRW

Using definitions from §2, for any model and any variable $X_{i}\in\{0,\dots,L_{i}-1\}$,

NEW RESULTS FOR THE NAIVE MEAN FIELD APPROXIMATION MF

In this Section, we consider the mean field negative free energy approximation,

In practice, there may be locally optimum solutions for the clamped problems that show worse performance than the parent. However, the analysis above shows that this concern is guaranteed to be avoided if the clamped optimizations are initialized at the solution of the parent problem.

METHODS TO SELECT WHICH VARIABLES TO CLAMP

Henceforth, we focus on binary pairwise models. As shown above, clamping a variable and summing over approximate sub-partition functions will always reduce error and improve bounds for both MF and TRW. Further, Weller and Jebara 2014b proved that for the Bethe approximation, this is also true for attractive models, and empirically it is often helpful for mixed models.

This leads to the question of how to choose which variable, or sequence of variables, to clamp. Weller and Jebara 2014b introduced two selection heuristics, motivated by trying to break strong cycles (we say a subgraph is strong if all its edges have weights with high absolute value; since Bethe and TRW are exact on trees, this goal is reasonable), and demonstrated that these heuristics were effective in several contexts. We first describe these earlier approaches.

maxW is a simple $O(|\mathcal{E}|)$ method which picks a variable $X_{i}$ with $\max_{i\in{\cal V}}\sum_{j\in{\cal N}(i)}|W_{ij}|$. One way in which maxW can make a poor selection is to choose a variable at the centre of a large star configuration but far from any cycle. Mpower was introduced as a more complex approach to attempt to avoid this problem (we introduce a simpler method in §5.1) by considering the convergent series of powers of a modified $|W|$ matrix, which approximates a weighted count around all cycles. It was shown that Mpower outperforms maxW in some cases, though for many examples, their performance was similar.

Note that both maxW and Mpower rely exclusively on the absolute value of edge weights $|W_{ij}|$, while ignoring their signs, and also ignoring singleton potentials. In the remainder of this Section, we demonstrate how these earlier methods can perform poorly in certain circumstances, and introduce new approaches. Details of all selection methods are provided in the Appendix.

Following Sudderth et al. 2007, we define the core of a graph (model), to be what remains after iteratively pruning nodes (variables) with degree 1. Equivalently, it is the subgraph (submodel) induced on the nodes (variables) which either belong to some cycle, or lie on a path between cycles. An example is shown in Figure 1. For pairwise entropy approximations, we should expect it will be better to strip a model to its core before applying any method to select a variable (then clamping it in the original model). In many cases that were previously challenging for maxW, this quick pre-processing step enables maxW to perform as well as the more expensive Mpower method.

2 Balanced Models, Frustrated Cycles and Strong Cycles

A frustrated cycle is a cycle with an odd number of repulsive edges (see §2 for definitions). These cause difficulties for many methods of inference. A balanced model (or sub-model) is one that does not contain any frustrated cycles. It is easily shown (Harary 1953, Weller 2015) that a model may be mapped into an equivalent attractive model by flipping an appropriately chosen subset of variables iff it is balanced (in which case such a set can be identified in linear time). Hence, results for attractive models readily extend to the broader class of balanced models.

This motivates trying to identify strong frustrated cycles. Both the maxW and Mpower earlier methods of Weller and Jebara 2014b consider only $|W_{ij}|$, hence are unable to differentiate between balanced and frustrated cycles. To find strong frustrated cycles is NP-hard but we introduce heuristics that build on a recent algorithm by Sontag et al. 2012, which was used in a cutting plane approach to tighten the local polytope for MAP inference. We combine ideas from their algorithm with cycle scores based on the loop series method (Chertkov and Chernyak 2006, Sudderth et al. 2007, Weller et al. 2014) and present two new heuristics for identifying a good variable to clamp: frustCycles, which seeks to identify a variable lying on strong frustrated cycles, which if clamped, would remove those cycles; and strongCycles, which attempts also to take into due consideration the (lower) value of removing strong balanced cycles. Details are provided in the Appendix.

3 Using Singleton Entropies

All previous clamping selection methods examine only edge weights. However, if a variable already has very low singleton entropy (typically this would be due to a strong singleton potential: this might be present in the original model, or could have arisen as a result of earlier clamping rounds), then it has effectively already been held fixed to one value, and there is little to be gained from clamping it. On the other hand, if a variable has high entropy and is strongly connected to many others, without a frustrated cycle, then clamping it can effectively lead to a cascade where many other variables will also be ‘effectively clamped’, yielding a significant improvement in approximation error. Afterward, there is little residual value in actually clamping those other variables.

This effect is illustrated by comparing the rows of Figure 2. Observe that even in the $K_{5}$ fully connected model, when no frustrated cycle is present (i.e. when edge weights are positive), just one clamping is sufficient to obtain almost zero error.

A further illustration is provided by considering the model in Figure 3. Recognizing this effect, ideally we would compute singleton entropies by exact inference, but that would clearly be too costly, hence, we use approximate inference. Specifically, we introduce TRE versions of each earlier method: for each variable, multiply its respective earlier heuristic clamp score by its TRw Entropy (we want both high) and choose the best. We use the TRW approximate entropy for two reasons (Weller et al. 2014): (i) TRW singleton marginals typically have similarly good accuracy to Bethe, while often being easier to estimate (since the TRW free energy is convex); and (ii) we are particularly interested in cases where edge potentials are high around a variable, and in this setting, Bethe marginals can be poor, being pulled toward 0 or 1 even if the true marginal is close to 1/2. TRE versions of all heuristics perform well for multiple clampings on models such as the one in Figure 3.

EXPERIMENTS

We tested all approaches on 100 runs each of various randomly generated binary pairwise models, exploring up to 5 clampings. We used all topologies shown in Figure 4, with the following parameters: all used random singleton potentials $\theta_{i}\sim U$; attractive models had $W_{ij}\sim U$ (typically a difficult lower intermediate value for Bethe) or $W_{ij}\sim U$; mixed models had $W_{ij}\sim U$ or $W_{ij}\sim U$. Exact values were computed using the junction tree algorithm. All inference methods were implemented using the standard open source libDAI library (Mooij 2010). In addition, we performed experiments on complete graphs with fewer variables but a similar number of edges, see Figure 5, and on random 4-regular graphs. Figure 5(d) shows typical timings vs. performance. Full details and results are provided in the Appendix.

We implemented all variable selection methods, specifically: maxW, Mpower, frustCycles and strongCycles, always first stripping to the core. We also tried the original maxW without stripping (as a comparison, which was previously shown to perform well). In addition, we used TRE versions of all these, for a total of 10 heuristics. We also implemented a greedy search over all possible clampings up to 3, to see how this would perform compared to our heuristics, and we implemented pseudo-greedy, which tried only the 10 heurstics in our basket and picked the best performer. This best performer was determined for MF (TRW) by the highest (lowest) solution. Similarly for Bethe for attractive models, best performer meant the variable which led to the greatest increase. For pseudo-greedy for Bethe on mixed models, where there is no way to be sure which is best, we tried various options, settling on picking the variable that gave the best improvement (i.e. the biggest fall) in TRW.

Looking across all results (Figures 4 and 5, with more details in the Appendix), we make the following observations.

Bethe typically dominates for accuracy as an inference method, as has been previously observed. However, as mixed models become more densely interconnected with strong edges, MF becomes competitive, and can even be far superior to Bethe, e.g. see Figure 5(c). We believe this is because Bethe (and TRW) can return arbitrarily high error for strong frustrated cycles, see §5.2. Figure 18 in the Appendix shows a histogram of Bethe errors on mixed models.

Clamping improves accuracy significantly, particularly when models have many strong edge weights. The improvement is greater for random models than for those with fixed degree; this is likely because some high degree variables will be present which will be good to clamp. Our heuristics perform well. Pseudo-greedy (which takes the best of our set of heuristics at each stage) performs almost identically to true greedy (which tries all possible clampings), except for MF. There, we believe that part of the effect is due to the highly non-convex optimization, so that true greedy effectively gets the benefit of many random initializations. There is clear value to probing with our portfolio of heuristics and picking the best, since no one method dominated. The best single performer was maxW after being augmented with our core and TRE updates (these augmentations were particularly helpful after the first clamping), which was best only about half the time (Figure 19 in the Appendix). See the Appendix for more details, including error plots zoomed in around the Bethe results.

Runtime varies significantly, see Figure 5(d) for a typical example. Considering clamping approaches, greedy takes the longest time though yields little benefit over pseudo-greedy. maxW, augmented with our core and TRE updates, is fast and yields the best time-adjusted results. See Appendix for all timings, and note that sometimes, clamping makes the subsequent optimization problems easier to solve, hence the total time with clamping is occasionally lower than without, while also being significantly more accurate. All branches over multiple clampings can be parallelized, as clearly can (pseudo-)greedy approaches. As an inference method, MF runs the fastest but this could be influenced by our implementation, with all timings sensitive to parameters. In order to get TRW to converge, we used damping which significantly slows it down, though there may be faster convergent methods. Further, edge weights could be optimized which is not implemented in libDAI. For Bethe, we used the HAK double-loop algorithm (Heskes et al. 2003), which was needed to ensure convergence.

Additional discussion on greedily selecting which next variable to clamp is provided in §10 of the Appendix.

CONCLUSION

Earlier approaches to selecting a variable to clamp can perform poorly in some settings. We examined when this is likely to occur, and introduced new methods based on first stripping to the core, looking for heavy (frustrated) cycles, and using singleton entropies. These new methods empirically yielded significant benefits.

Based on an experimental comparison across the different inference approaches and clamping selection methods, including examining the accuracy improvement vs. time tradeoff, we are able to suggest the following practical recommendations:

As has been previously observed, typically Bethe is the best approach, provided convergence difficulties do not arise. However, perhaps surprisingly, for densely connected mixed models with strong edges, MF can be much more accurate (e.g. Figure 5(c)).

Clamping can be very helpful, more so for denser models with stronger edge weights, a setting where inference on the original model is hard.

For variable selection, if speed is critical, use just the updated maxW heuristic (augmented with core and TRE). Otherwise, use our basket of approaches and pick the pseudo-greedy best option. For Bethe on mixed models, use TRW to guide pseudo-greedy selection.

In many cases, it will be helpful to run MF and TRW in order to obtain guaranteed bounds on the true partition function. If a Bethe method is used, bounds can also be useful to check if a poor local optimum was returned (below the MF value).

References

APPENDIX: SUPPLEMENTARY MATERIAL Clamping Improves TRW and Mean Field Approximations

Details of all methods used for selecting a variable to clamp.

Additional experimental details and results.

Additional discussion on greedily selecting a variable to clamp.

Details of all methods for selecting a variable to clamp

The maxW and Mpower heuristics introduced by Weller and Jebara 2014b were defined as follows.

This is the simplest method yet it can be very effective. Assign a clamp score $s(i)$ to each variable $i$ by setting $s(i)=\sum_{j\in{\cal N}(i)}|W_{ij}|$. Pick the variable with highest score.

1.2 Mpower

Form matrix $M$ defined by $M_{ij}=\frac{1}{n-1}\tanh\big|\frac{W_{ij}}{4}\big|$. The $\tanh$ term is inspired by the effect of cycles in Lemma 5 from Weller et al. 2014, which was derived using loop series methods (Sudderth et al. 2007, Chertkov and Chernyak 2006), and dividing by $n-1$ is in order to ensure that row sums are $<1$ and hence $\sum_{k=1}^{\infty}M^{k}$ is convergent. Note that $[M^{k}]_{ii}$ is the sum over all paths of length $k$ from $i$ to $i$ of the product of the modified edge weights along the cycle.

To compute the sum over all $k$, evaluate $(I-M)^{-1}-I$ and examine diagonal terms. However, this overcounts all cycles, and in particular it includes relatively high value terms coming from paths simply from $i$ to any neighbor $j$ and back again, along with all powers of these. In order to discard these, compute clamp score $s(i)$ as the $i$th diagonal term of $(I-M)^{-1}-I$ minus $s_{i}/(1-s_{i})$, where $s_{i}$ is the $i$th diagonal term of $M^{2}$. Pick the variable with highest score.

See (Weller and Jebara 2014b, Supplement) for more details.

2 New methods

For frustCycle, the goal is to try to identify at least one frustrated cycle composed of edges $(i,j)$ with high absolute weight $|W_{ij}|$. The method builds on an algorithm introduced by Sontag et al. 2012. strongCycles works in the same way but also takes into consideration balanced cycles. These approaches are the first to examine the sign of edge weights $W_{ij}$ (in order to identify strong frustrated cycles) rather than just their absolute value $|W_{ij}|$.

2.2 Strip to the core

To strip a model to its core, simply iteratively remove variables with degree 1 until no more remain, see Figure 1. This is typically run as a pre-processing step before applying other clamp selection heuristics. When removing variables, care must be taken to keep track of the original variable indices for those that remain. For all methods above, we first strip to the core.

We have described 4 heuristics so far: maxW, Mpower, frustCycles and strongCycles, all of which first strip to the core. In addition, recognizing that MF makes the assumption that all variables are independent, which may be poor when edge strengths are strong irrespective of cycles being present, we also use a maxW0 heuristic which does not first strip to the core, for a total of five.

2.3 TRE methods

All methods so far use only edge weights. We add TRE versions of all the above (see §5.3), hence this gives 10 heuristics.

2.4 Meta-heuristics for clamping

For Bethe on mixed models, we can’t know in advance if we have an over- or under-estimate, so we cannot do exactly the same thing. Instead, we explored performance achieved by picking the variable that gave best improvement in: (i) TRW; (ii) TRW-MF, that is the gap between the two; and (iii) MF. Of these, the greedy-TRW heuristic was the most successful, and it is this version of greedy (and correspondingly, pseudo-greedy) that we report for Bethe on mixed models.

Additional experimental details and results

For all inference methods, we used the open source libDAI library (Mooij 2010), with the following parameters:

For MF, MF[tol=1e-7,maxiter=10000,damping=0.0,init=RANDOM,updates=NAIVE]

For Bethe, HAK[doubleloop=1,clusters=BETHE,init=UNIFORM,tol=1e-7,maxiter=10000] This is guaranteed to converge to a stationary point of the Bethe free energy (whereas BP may not converge).

For TRW, TRWBP[updates=SEQFIX,tol=1e-7,maxiter=10000,logdomain=0,nrtrees=1000,... damping=0.25,init=UNIFORM]

Note that, particularly for MF and Bethe methods, we may obtain local (rather than global) optima. Because of this, we might occasionally observe results that get worse with clamping, even where theory shows that the global optimum can only improve. For MF, initializing the optimization of each clamped problem to the solution of the parent problem removes this concern, though we did not find this necessary in practice: empirically it appeared sufficient to initialize using the same random seed each time. For Bethe, we see no easy way to avoid this issue without using expensive methods such as those of Weller and Jebara 2014a.

All grids are toroidal, so all variables have degree 4. Random 4-regular graphs are randomly generated s.t. all variables still have exactly degree 4, though the structure is random. All random Erdös-Renyi models have edge probability s.t. the average degree is 4. Note that the complete graphs have far fewer variables (just 10 or 15) but are much more densely connected (with roughly the same number of edges as the corresponding models with degree 4) and have higher treewidth.

1 Additional results

We first provide plots of number of clamps vs. error for all runs, then the same plots but zoomed in so that the Bethe results are easier to see; then plots of runtime ($\log$ scale) vs. error for all runs. Note that sometimes clamping makes the subsequent optimization problems easier to solve, hence the total time with clamping is occasionally lower than without, while also being significantly more accurate (for example, see TRW performance with mixed $$ for the complete graph on 10 variables in Figure 14).

Finally, in Figure 19, we provide plots showing performance of each heuristic - this indicates how often each one picks the same variable to clamp as pseudo-greedy at each specific clamp step.

Additional discussion on greedily selecting a variable to clamp

An interesting question is whether greedily picking the one variable that gives best error improvement and repeating say $k$ times is optimal, i.e. will it result in error as low as if instead, we try all possible sequences of clampings up to $k$ long. It becomes computationally expensive to try this but we ran experiments out to 3 clampings. We observed that iterating a greedy search is not optimal, in that the full optimization does perform better, but only by a very slight margin on the models we tried.