Abstract
Weighted Model Integration (WMI) is a fundamental task in probabilistic inference, often hampered by the geometric complexity of logical constraints. This paper proposes an acceleration technique using orthogonal transformations to align slanted regions with coordinate axes. By employing Pythagorean triples to maintain rational coefficients for SMT solvers and focusing on Gaussian weight functions, the method achieves significant speedups, particularly in high-dimensional spaces.
Introduction
In probabilistic programming and artificial intelligence, calculating the probability that a set of continuous variables satisfies a specific logical formula is known as the Weighted Model Integration (WMI) problem. A common approach to solving WMI involves decomposing the complex geometric region defined by the formula into a collection of simple axis-aligned hyperrectangles, or "boxes." While calculating the volume or weight of these boxes is computationally trivial, the efficiency of the decomposition depends heavily on the orientation of the region's boundaries.
The Curse of Slantedness
Most real-world constraints are "slanted" relative to the coordinate axes (e.g., $x + y \leq 10$). Attempting to fill a slanted region with axis-aligned boxes creates a "staircase" effect, where an exponentially large number of tiny boxes are required to fill the gaps near the edges. This leads to slow convergence and high computational costs, a phenomenon that worsens significantly as dimensionality increases.
Methodology: Rational Orthogonal Transformations
The authors propose "rotating" the entire problem space so that the slanted faces of the formula become axis-aligned. This transformation allows the algorithm to capture the majority of the probability mass using a few large boxes rather than many small ones.
To implement this effectively, the authors addressed three primary technical challenges:
- Preserving Independence: According to the Skitovitch-Darmois theorem, linear transformations only preserve the independence of variables if they follow a Gaussian (Normal) distribution. Consequently, this method specifically targets WMI problems with Gaussian weight functions.
- Rational Rotations: Modern Satisfiability Modulo Theories (SMT) solvers require rational coefficients. Standard rotation matrices involving sines and cosines often result in irrational numbers. The authors circumvent this by using Givens rotations constructed from Pythagorean triples (e.g., 3, 4, 5), enabling "rational rotations" that can approximate any angle with arbitrary precision.
- Heuristic Optimization: To choose the best rotation, the authors use a heuristic based on QR-factorization. They prioritize aligning the "heaviest" faces—those where the probability density is highest—with the axes first to maximize immediate volume coverage.
Experimental Results
The method was evaluated on synthetic benchmarks and complex "Random-Walk" benchmarks simulating robotic movement. The results demonstrate that the difficulty of hyperrectangular decomposition is driven more by constraint orientation than by the number of constraints.
- Dimensionality Scaling: While improvements in 3D were modest (~17%), the transformed approach in 7D covered 1500% more weighted volume than the standard approach within the same 100-second window.
- Convergence Speed: Orthogonal transformations allow the algorithm to identify high-weight boxes almost immediately, whereas baseline methods struggle with a multitude of low-weight boxes at the boundaries.
- Robustness: On complex benchmarks with up to 90 atomic predicates, the transformation consistently yielded superior lower bounds on probability, justifying the overhead of calculating the rotation.
Conclusion and Future Work
By bridging the gap between number theory and formal methods, this research provides a powerful tool for high-dimensional probabilistic inference. While currently restricted to Gaussian distributions, future work may explore extending these techniques to other distribution types or integrating them with different integration backends, such as those based on algebraic decision diagrams.
Summary updated