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.
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:
- Sampling: Using the VolEsti hit-and-run sampler, the algorithm draws uniform samples from the convex polytopes defined by the problem's constraints.
- Weighting: Each sample is assigned a weight based on the problem's specific weight function.
- 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.
- 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.
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