Approximate Knowledge Compilation by Online Collapsed Importance Sampling

Tal Friedman, Guy Van den Broeck

Introduction

This paper introduces Collapsed Compilation, a hybrid inference algorithm that scales exact knowledge compilation to large graphical models by integrating it with importance sampling. By dynamically choosing which variables to sample and using partially compiled circuits as highly accurate proposal distributions, the method outperforms state-of-the-art approximate inference techniques on complex, structured benchmarks.

The Challenge of Probabilistic Inference

Probabilistic inference—calculating the likelihood of events in a complex system—is notoriously difficult. Knowledge Compilation (KC) is a powerful technique for exact inference: it transforms a model into an Arithmetic Circuit (AC) where queries can be answered in linear time. However, KC faces a "memory wall": for large or highly connected models, the resulting circuits grow exponentially, making exact inference impossible.

A common workaround is collapsed sampling, where a subset of variables is sampled while exact inference is performed on the rest. Traditionally, this approach has two major flaws:

  1. Static Partitioning: It requires deciding which variables to sample before starting, even though the optimal variables to sample often depend on the specific values assigned to previous variables (context-specific independence).
  2. The Proposal Problem: Importance sampling requires a "proposal distribution" to guess variable values. If this guess is poor, the algorithm takes an impractical amount of time to converge.

Methods: Online Collapsed Importance Sampling

To overcome these limitations, the authors propose Online Collapsed Importance Sampling and its practical implementation, Collapsed Compilation.

Algorithm for Online Collapsed Importance Sampling

This approach introduces several key innovations:

  • Online Selection: Instead of relying on a fixed plan, the algorithm decides which variable to sample next during the sampling process. This allows it to adapt dynamically to the specific "context" of the current sample.
  • The Circuit as a Proposal: As the algorithm compiles the model into a Sentential Decision Diagram (SDD), it eventually hits a user-defined size limit (e.g., 100,000 nodes). Instead of failing, it uses this partially compiled circuit to generate the proposal distribution. Because the circuit already incorporates many of the model's constraints and factors, it provides a significantly more accurate "guess" than standard methods.
  • Variable Selection Policies: The authors tested three distinct heuristics to pick the next variable:
  • RBVar: Minimizes the variance of the query.
  • MinEnt: Picks variables with the lowest entropy (the most "certain" ones).
  • FrontierDistance: A graph-based heuristic that picks variables close to the "frontier" of the current compilation.

Key Insights and Results

The algorithm was rigorously evaluated on standard benchmarks from the UAI Inference Competitions, including genetic linkage analysis models (Linkage), computer vision models (Grids & Segmentation), Dynamic Bayesian Networks (DBN), a frustrated Ising model (Frust16), and probabilistic logic programming (ProbLog).

  • Exploiting Local Structure and Determinism: Many real-world models feature "determinism" (logical rules where probabilities are strictly 0 or 1). Standard approximate methods like Loopy Belief Propagation often struggle or fail to converge in these scenarios. Collapsed Compilation thrives here because it leverages symbolic logic techniques under the hood. In the ProbLog benchmark, which is full of hard logical constraints, the method was much more stable and accurate than alternatives like Samplesearch, which exhibited consistent bias.
  • Superior Accuracy: On complex benchmarks like DBN and frust16, Collapsed Compilation significantly outperformed state-of-the-art baselines such as Edge-Deletion Belief Propagation (EDBP) and IJGP-Samplesearch.
  • Efficiency and the "Sweet Spot": Even with a limited "budget" for exact inference (restricting the circuit size to a threshold of 100k nodes), the method's ability to use partial knowledge made its importance sampling highly effective. It captured correlations between variables that simple marginals miss, balancing a high-quality proposal distribution with the speed needed to take many samples within a one-hour time limit.

Limitations and Future Work

While powerful, the method has limitations. It still requires that individual factors in the model can be compiled into SDDs; if a single factor is too complex to represent, the algorithm cannot initialize. Additionally, performance is sensitive to the chosen variable selection policy, and the optimal policy isn't always obvious for a novel dataset.

Future work will explore extending this framework to other types of queries, such as Most Probable Explanation (MPE), and developing more sophisticated online policies to further reduce the variance of the estimates.

Summary updated

Abstract

We introduce collapsed compilation, a novel approximate inference algorithm for discrete probabilistic graphical models. It is a collapsed sampling algorithm that incrementally selects which variable to sample next based on the partial compila- tion obtained so far. This online collapsing, together with knowledge compilation inference on the remaining variables, naturally exploits local structure and context- specific independence in the distribution. These properties are used implicitly in exact inference, but are difficult to harness for approximate inference. More- over, by having a partially compiled circuit available during sampling, collapsed compilation has access to a highly effective proposal distribution for importance sampling. Our experimental evaluation shows that collapsed compilation performs well on standard benchmarks. In particular, when the amount of exact inference is equally limited, collapsed compilation is competitive with the state of the art, and outperforms it on several benchmarks.
BibTeX
@inproceedings{friedman2018approximate,
  author = {Tal Friedman and Guy Van den Broeck},
  title = {{Approximate Knowledge Compilation by Online Collapsed Importance Sampling}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=RQypFWcb130},
}
Figure