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:
- 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).
- 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.
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
ProbLogbenchmark, 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
DBNandfrust16, 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