Scaling-up Importance Sampling for Markov Logic Networks

Deepak Venugopal, Vibhav GogateNeurIPS 2014 · OpenReview

Overview

Markov Logic Networks (MLNs) are a powerful framework combining first-order logic with probability. However, they suffer from a massive scalability hurdle known as the grounding problem. To perform inference, most algorithms "ground" the logic, expanding compact rules into a massive Markov network graph. For large domains, this graph quickly becomes too large to fit in memory.

While "lifted inference" techniques attempt to solve this by exploiting symmetries in the logic to avoid grounding, they hit a second wall: the evidence problem. In the real world, specific data (evidence) breaks these symmetries. For example, if a rule states "friends tend to have similar habits," but we introduce specific facts about thousands of individual people, the mathematical shortcuts of lifted inference vanish, forcing the algorithm to ground almost everything.

This paper introduces a scalable importance sampling algorithm for MLNs that avoids this "grounding explosion." By combining domain compression for proposal distributions with a secondary "inner sampler" for weight computation, the authors enable accurate inference on models with millions of groundings where traditional tools fail.

Methods

The authors propose a two-stage importance sampling approach that never requires grounding the full MLN.

1. Informed Proposal Distribution via Compression

Instead of sampling from a simple distribution, the algorithm uses a "compressed" version of the MLN. The authors cluster similar objects in the domain (e.g., grouping people with similar evidence profiles) to create a much smaller, manageable model.

Example of domain compression for MLNs.

They then sample "lifted symbols"—which represent the total count of true groundings for a predicate—using Gibbs sampling on this compressed representation. Approximate symmetries are enough here: you don't need perfect symmetry to get a good proposal distribution. Clustering "roughly similar" objects provides a proposal that is "informed" enough to guide the sampler effectively.

2. Fast Weight Computation via Inner Sampling

Normally, calculating the "importance weight" of a sample requires iterating over every single possible grounding of every formula—a task that is #P-complete. The authors solve this by using a second, "inner" sampler. Instead of counting every grounding, they sample a small, representative subset of groundings to estimate the weight. By treating the weight calculation as a sub-sampling problem, they bypass the prohibitive polynomial complexity of grounding.

3. Rao-Blackwellization

To keep the variance of these estimates low, they use Rao-Blackwellization. They partition variables in a formula into "shared" and "non-shared" variables. They sample the shared ones and analytically compute the exact count for the non-shared ones, significantly improving accuracy without adding much computational cost.

Key Results

The researchers evaluated their approach on several standard MLN benchmarks, including small/exact benchmarks (Smokers, HMM, Relation, and LogReq) and large-scale benchmarks like Hypertext Classification (~1 million groundings) and Entity Resolution (~8 million groundings).

  • Massive Scalability: The algorithm successfully handled the Entity Resolution task with 8 million groundings. The state-of-the-art system at the time, Alchemy, was unable to produce results for these large datasets due to memory exhaustion during grounding.
  • Speed: For the 1-million-grounding Hypertext dataset, the system could generate hundreds of weighted samples per minute, whereas traditional methods couldn't even start the process.
  • Efficiency vs. Accuracy Trade-off: The experiments demonstrated a clear "knob" for researchers: by adjusting the compression ratio ($N_s$), one can trade off a bit of accuracy for massive gains in speed.
Error vs. Time across different datasets for varying compression ratios ($N_s$).
  • Asymptotic Unbiasedness: Despite the layers of approximation (compression and inner sampling), the authors prove that their estimator remains asymptotically unbiased, meaning it will eventually converge to the true probability as more samples are taken.

Limitations and Future Work

While highly effective, the approach has a few limitations:

  • Clustering Dependency: The quality of the proposal distribution depends heavily on the initial unsupervised clustering of the domain. If the clustering is poor, the importance sampling might take a very long time to converge.
  • Variance in Complex Formulas: While Rao-Blackwellization helps, formulas with very high numbers of shared variables might still lead to high variance in the weight estimates.

For future work, the authors suggest exploring more sophisticated clustering strategies (like graph-based similarity) and applying these "inner sampling" ideas to other MCMC algorithms.

Summary updated

Abstract

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.
BibTeX
@inproceedings{venugopal2014scaling,
  author = {Deepak Venugopal and Vibhav Gogate},
  title = {{Scaling-up Importance Sampling for Markov Logic Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=BkV42DbubH},
}
Figure