Monte Carlo Anti-Differentiation for Approximate Weighted Model Integration

Pedro Zuidberg Dos Martires, Samuel KolbarXiv 2020 · arXiv

Introduction

Probabilistic inference in hybrid domains—where discrete Boolean variables coexist with continuous real-valued measurements—is a cornerstone of modern AI. Weighted Model Integration (WMI) provides the formal framework for such tasks. However, exact WMI is #P-hard, and current symbolic solvers struggle with the "curse of dimensionality." This paper introduces Monte Carlo Anti-Differentiation (MCAD), a technique that replaces expensive symbolic integration with efficient numerical approximations, allowing solvers to handle high-dimensional problems while maintaining structural exploitation.

The WMI Challenge and Symbolic Bottlenecks

In WMI, the goal is to compute the integral of a weight function over a region defined by logical constraints. These constraints typically manifest as a set of convex polytopes.

Weighted Model Integration (WMI) involves integrating weight functions over complex geometric regions defined by logical constraints.

State-of-the-art solvers often use symbolic integration to find exact anti-derivatives. While precise, this approach scales poorly; the complexity of the symbolic formulas grows exponentially with the number of continuous variables. Conversely, standard numerical Monte Carlo methods provide point estimates (definite integrals) but lack the functional form required for the recursive, factorized algorithms that make WMI solvers efficient.

The MCAD Approach

MCAD bridges the gap between symbolic and numerical methods by computing a numerical approximation of the anti-derivative that can serve as a "drop-in" replacement in existing solvers. The process involves four key stages:

  1. Sampling: Using the VolEsti hit-and-run sampler, the algorithm draws uniform samples from the convex polytopes defined by the problem's constraints.
  2. Weighting: Each sample is assigned a weight based on the problem's specific weight function.
  3. Density Estimation: To reconstruct a functional form from discrete samples, MCAD employs histograms. By binning weighted samples, it creates a piecewise constant function that approximates the true indefinite integral.
  4. Integration into F-XSDD: The authors integrated this backend into the F-XSDD solver. This allows the system to exploit problem structure (factorization) while using fast approximations for the underlying calculus.
The MCAD pipeline: (left) sampling from the constrained region, (top right) weighting samples, and (bottom right) constructing a piecewise constant histogram approximation of the anti-derivative.

By performing integration within factorized, low-dimensional subspaces, MCAD avoids the sample rejection issues that typically plague naive Monte Carlo methods in high dimensions.

Experimental Evaluation

The authors evaluated F-XSDD(MCAD) against several synthetic benchmarks:

  • XOR(N) and Mutex(N): Highly structured problems where symbolic solvers typically exhibit exponential runtime growth.
  • M-ual ($x^2, N, M$): A high-dimensional benchmark where configurations like $M$-ual($10, 10$) reach 100 dimensions.

The results demonstrate that F-XSDD(MCAD) successfully avoids exponential runtime scaling. In the 100-dimensional test cases, where exact symbolic solvers and naive rejection samplers timed out, MCAD provided reliable approximations with low and stable Root Mean Squared Error (RMSE).

Discussion and Future Directions

MCAD proves that a piecewise constant approximation is often "good enough" for reliable inference, combining the structural benefits of symbolic solvers with the scalability of Monte Carlo methods.

However, the use of histograms introduces its own dimensionality constraints within the integration subspaces. Future work aims to replace simple histograms with more sophisticated density estimators, such as Kernel Density Estimation (KDE) or Sum-Product Networks (SPNs), and to implement importance sampling to further reduce approximation variance.

Summary updated

Abstract

Probabilistic inference in the hybrid domain, i.e. inference over discrete-continuous domains, requires tackling two well known #P-hard problems 1)~weighted model counting (WMC) over discrete variables and 2)~integration over continuous variables. For both of these problems inference techniques have been developed separately in order to manage their #P-hardness, such as knowledge compilation for WMC and Monte Carlo (MC) methods for (approximate) integration in the continuous domain. Weighted model integration (WMI), the extension of WMC to the hybrid domain, has been proposed as a formalism to study probabilistic inference over discrete and continuous variables alike. Recently developed WMI solvers have focused on exploiting structure in WMI problems, for which they rely on symbolic integration to find the primitive of an integrand, i.e. to perform anti-differentiation. To combine these advances with state-of-the-art Monte Carlo integration techniques, we introduce \textit{Monte Carlo anti-differentiation} (MCAD), which computes MC approximations of anti-derivatives. In our empirical evaluation we substitute the exact symbolic integration backend in an existing WMI solver with an MCAD backend. Our experiments show that that equipping existing WMI solvers with MCAD yields a fast yet reliable approximate inference scheme.
BibTeX
@misc{martires2020monte,
  author = {Pedro Zuidberg Dos Martires and Samuel Kolb},
  title = {{Monte Carlo Anti-Differentiation for Approximate Weighted Model Integration}},
  year = {2020},
  eprint = {2001.04566},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2001.04566},
}
Figure