Scaling-up Importance Sampling for Markov Logic Networks
Markov Logic Networks (MLNs) are weighted first-order logic templates for generating large (ground) Markov networks. Lifted inference algorithms for them bring the power of logical inference to probabilistic inference. These algorithms operate as much as possible at the compact first-order level, grounding or propositionalizing the MLN only as necessary. As a result, lifted inference algorithms can be much more scalable than propositional algorithms that operate directly on the much larger ground network. Unfortunately, existing lifted inference algorithms suffer from two interrelated problems, which severely affects their scalability in practice. First, for most real-world MLNs having complex structure, they are unable to exploit symmetries and end up grounding most atoms (the grounding problem). Second, they suffer from the evidence problem, which arises because evidence breaks symmetries, severely diminishing the power of lifted inference. In this paper, we address both problems by presenting a scalable, lifted importance sampling-based approach that never grounds the full MLN. Specifically, we show how to scale up the two main steps in importance sampling: sampling from the proposal distribution and weight computation. Scalable sampling is achieved by using an informed, easy-to-sample proposal distribution derived from a compressed MLN-representation. Fast weight computation is achieved by only visiting a small subset of the sampled groundings of each formula instead of all of its possible groundings. We show that our new algorithm yields an asymptotically unbiased estimate. Our experiments on several MLNs clearly demonstrate the promise of our approach.
This paper combines evidence-based clustering with an importance sampling approach. It further optimizes the weight function calculation of importance sampling, by using a second sampler to estimate the number of true groundings.     I recommend to accept this paper because of the importance of the evidence problem, and the fact that the proposed solution is very general and scalable.     The paper is well-written and clear, except for Figure 1 (b) and Equations 5,6, and 7, which are poorly explained.     A disadvantage of the paper is that its clustering algorithm is reused from a recent publication:    "Evidence-based Clustering for Scalable Inference in Markov Logic" at ECML 2014.    Thus, the clustering algorithm is not a contribution of this paper.    Another disadvantage is the complexity of the setup.     The introduction says that the combination of the base importance sampler, and the sampler for the number of groundings yield unbiased estimates. This claim is not supported by the main text. The first sampler is obviously unbiased when using the exact number of groundings. Proposition 2 says that the second sampler is unbiased. I don't think this implies that the combination of the two is unbiased. Even if the second sampler is unbiased, it has a variance because it uses a finite fixed sample size. This variance can induce a bias in the first sampler?     The experimental setup is impressive, because of the scale of the MLN models considered. The results are slightly disappointing though: the errors do not go down significantly. Is this to be expected?     Beta is used in line 300 and 400/Fig3 for different variables? Is the second beta explained?