Addendum for paper "H. Bui, T. Huynh, D. Sontag. Lifted Tree-Reweighted Variational Inference. Proceedings of Uncertainty in Artificial Intelligence (UAI), July 2014."

9/15/2014:

After publication of our paper, we found an error in the code used to produce Figure 6 (page 9), where the parameter \theta_{111} was not being varied in the computations of the log-partition functions (it was varied in the data likelihood term). The currently linked to paper has the revised figure. The original paper can be found here:

   http://cs.nyu.edu/~dsontag/papers/BuiHuySon_uai14_orig.pdf

The main difference is that we now observe a phase transition at \theta_{111} > 0.02 where the likelihood drops very quickly. This phase transition does not appear in Jaimovich et al. UAI '07's Figure 7. In an effort to better understand which of the two approximations (Lifted TRW versus Lifted BP) is more accurate, we did a series of additional investigations. Note that the difficulty here is that we cannot run exact inference on the full protein-protein interaction problem (which has over 330,000 random variables), so assessing "better" without knowing the ground truth is non-trivial.

First, we ran both exact inference (using the JT/junction tree algorithm), BP, and TRW on a smaller instance containing just 6 proteins (this is about the limit of what exact non-lifted inference can perform quickly). We observed a phase transition in the JT results, and TRW appears to give a close-to-exact approximation of the log-partition function, in particular having the phase transition at a similar setting of the parameters as JT. In contrast, BP's phase transition is remarkably more peaked and occurs at a larger value of \theta_{111}.

This led us to conjecture that the phase transition is in fact occuring at a larger value of \theta_{111} than was considered in Jaimovich et al's work. We next ran lifted BP on the original protein-protein interaction instance for much larger values of \theta_{111}. Although Alchemy's Lifted BP code does not output an estimate of the log-partition function, from observing the estimates of the single-node marginals we can see that Lifted BP has a phase transition at \theta_{111} between 0.66 and 0.72.

From our experiments with smaller models, we have reason to believe that the Lifted TRW approximation of the log-likelihood landscape is the more accurate one. However, this then leads to the surprising conclusion that the maximum likelihood parameters occur at or near \theta_{011}=0 and \theta_{111}=0! That is, at least for this simplified model (where \theta_1* is fixed to -5.29; see the paper), machine learning results in the tertiary potentials being very small.

Finally, we also changed the text at the end of Section 8 from "Moreover, the high-likelihood parameter settings extends to larger values of θ111. For all algorithms there is a sudden decrease in the likelihood at θ011 > 0 (not shown in the figure)." to "For the lifted TRW algorithms there is a sudden decrease in the likelihood at θ_011 > 0 and θ_111 > 0.02 (so as to not affect the scale, we show this as white)." to better reflect the new figure.