Abstract
Weighted Model Integration (WMI) is a powerful framework for probabilistic inference in hybrid domains, yet it faces a significant "expressivity gap" when dealing with non-linear constraints and complex weight functions. We introduce WMI-LP, a novel algorithm that reduces non-linear integration into a series of linear programming (LP) instances using real algebraic geometry. By leveraging Handelman’s Theorem for set containment checks, WMI-LP provides deterministic, $\epsilon$-tight error guarantees for rational and radical weight functions. Our evaluation on 120 challenging benchmarks demonstrates that WMI-LP is more robust and provides tighter bounds than existing symbolic and approximate solvers.
Introduction
Probabilistic inference in hybrid domains—mixing discrete and continuous variables—often requires calculating the "weight" of a model. This involves integrating a weight function over a region defined by logical constraints. While WMI is a robust framework, most existing tools are optimized for linear or polynomial functions. However, real-world applications in physics, finance, and robotics frequently involve rational functions (fractions of polynomials) or radical functions (roots of polynomials).
Exact WMI is #P-hard, and current approximate methods either lack formal error guarantees (like Monte Carlo sampling) or cannot handle the non-linear arithmetic required for these complex functions. WMI-LP addresses this by providing a scalable approach with formal, user-defined precision.
Methodology: From Integration to Linear Programming
WMI-LP transforms the integration of a weight function $w(x)$ over a set $S$ into a volume calculation of a higher-dimensional set $S'$ in $\mathbb{R}^{n+1}$. The algorithm follows a three-step pipeline:
- Reduction to Volume: The problem is reframed as finding the volume of a region bounded by the original constraints and the weight function.
- Bounding: Binary search and LP solvers determine the interval bounds for the newly introduced dimension.
- Recursive Subdivision (Gridding): The algorithm covers the target region with hyper-rectangles. For each rectangle, it must decide if it is entirely "Inside," "Outside," or "Intersecting" the target set.
To handle non-linear constraints without expensive symbolic math, WMI-LP uses Farkas’ Lemma and Handelman’s Theorem. These tools from real algebraic geometry translate the non-linear containment check into a standard Linear Programming (LP) problem. This innovation allows the algorithm to use high-performance solvers like Gurobi to process thousands of checks in milliseconds. Furthermore, the process is perfectly parallelizable, allowing it to scale with modern multi-core processors.
Experimental Evaluation
The authors evaluated WMI-LP using two benchmark families designed to push the limits of current solvers:
- Family (A) - Random Rational Functions: 60 instances featuring fractions of polynomials of degree two or three.
- Family (B) - Random Radical Functions: 60 instances involving square roots of polynomials.
Key Results and Discussion
WMI-LP demonstrated a clear leap in applicability and precision:
- Robustness: WMI-LP successfully solved all 120 benchmarks. In contrast, the symbolic tool LattE solved none, and the sampling-based VolEsti failed on all radical function benchmarks (Family B).
- Tightness: Unlike statistical methods, WMI-LP is $\epsilon$-tight, providing a hard interval $[Lower, Upper]$ where the true value is guaranteed to reside. As shown in the comparative data, WMI-LP consistently provided much tighter error bounds than GuBPI, whose errors were often orders of magnitude larger than the requested precision.
- Reliability: While Mathematica is powerful, it often returned symbolic expressions too complex for use or encountered execution errors on radical functions. WMI-LP provided reliable numerical approximations where symbolic integrators struggled.
Conclusion and Future Work
WMI-LP bridges the expressivity gap in hybrid probabilistic inference by providing a scalable, deterministic approximation for non-linear real arithmetic. While the recursive subdivision approach currently faces the "curse of dimensionality" in very high-dimensional spaces, the use of LP as a proxy for integration offers a significant advancement. Future work will focus on optimizing subdivision strategies, such as using non-rectangular shapes or heuristic-driven splitting, to further enhance scalability.
Summary updated