TL;DR
This paper introduces the first lifted inference algorithm for hybrid probabilistic relational models, which combine discrete and continuous variables. Their method, Lifted Hybrid EPBP (LEPBP), significantly speeds up inference compared to standard particle-based methods while maintaining accuracy, and a novel "coarse-to-fine" extension further improves efficiency by adaptively refining evidence groupings.
What Problem Does This Paper Address?
Statistical Relational Learning (SRL) models are powerful for representing complex relational data with uncertainty. However, performing probabilistic inference (e.g., calculating the probability of certain events) on these models is computationally challenging, especially when they involve both discrete and continuous variables. Existing "lifted inference" techniques exploit model symmetries to speed up inference, but they have largely been limited to purely discrete or purely continuous (specifically Gaussian) models. This paper tackles the problem of efficient and accurate lifted inference for hybrid models, which are more general and realistic but pose significant challenges for existing lifted methods, particularly when dealing with continuous evidence that can break model symmetries.
Methods
The core of the paper is the Lifted Hybrid EPBP (LEPBP) algorithm. It builds upon Expectation Particle Belief Propagation (EPBP), a particle-based approximate inference method. The key innovations are:
- Hybridization: LEPBP adapts EPBP to handle models with both discrete and continuous variables. It uses particle sampling for continuous variables and exact computations for discrete ones.
- Lifted Inference: It first constructs a "compressed factor graph" by grouping similar variables and factors (using a "color passing" mechanism). Inference is then performed on this compressed graph, leveraging symmetries to reduce computation.
- Coarse-to-Fine Lifting: To address the issue of continuous evidence breaking symmetries, they introduce a coarse-to-fine lifting approach. This method starts with a coarse clustering of evidence values and iteratively refines these clusters while interleaving lifted EPBP. This adaptive refinement allows the algorithm to exploit approximate symmetries even when evidence is continuous.
Datasets
The paper evaluates their methods on several synthetic and real-world datasets:
- Relational Gaussian Models: A synthetic model with multivariate Gaussian potentials, inspired by the "Recession model," used to evaluate performance with varying levels of continuous evidence.
- Relational Kalman Filtering: Groundwater level data from the Republican River Compact Association model, used to test inference on dynamical systems with parameter tying.
- Hybrid Markov Logic Networks (MLNs): A simulated "advisedBy" domain to test performance on hybrid models with both discrete and continuous clauses.
- Image Denoising: A standard 50x50 grayscale image denoising task, where the noisy image is treated as evidence, to demonstrate performance on problems where evidence can break symmetries.
Key Insights and Ideas
- Hybridization is Crucial: The ability to handle both discrete and continuous variables within a lifted inference framework is essential for real-world SRL applications.
- Continuous Evidence is a Symmetry Breaker: Unlike discrete evidence, continuous evidence can significantly reduce the symmetries in a model, making standard lifted inference less effective.
- Approximate Symmetries are Powerful: The coarse-to-fine approach demonstrates that even approximate symmetries, derived from clustered evidence, can lead to substantial computational gains.
- Particle Methods Adapt Well: Particle-based methods, like EPBP, are flexible enough to be adapted for lifted inference in hybrid models, especially when combined with clever proposal distribution strategies.
Key Results
- Significant Speedup: LEPBP consistently outperforms standard EPBP in terms of running time, often by a factor of 2-10x, especially on models with a moderate amount of continuous evidence.
- Accuracy Maintained: Despite the speedup, LEPBP and its coarse-to-fine variant achieve accuracy comparable to or only slightly worse than baseline methods (including exact methods where applicable). For instance, in relational Kalman filtering, their methods achieved less than 1% error in the tree case and around 3% error in the loopy case compared to exact LRKF.
- Coarse-to-Fine Advantage: The coarse-to-fine lifting approach (C2FEPBP) further improves upon LEPBP, achieving roughly twice the speed in some cases (e.g., image denoising) while maintaining similar accuracy.
- Versatility: The proposed methods are not limited to specific potential functions (like Gaussians) and can handle arbitrary integrable potentials, making them more broadly applicable than prior lifted inference techniques.
Limitations and Future Work
- Sampling-Based Nature: While faster than non-lifted particle methods, LEPBP is still a sampling-based approach and can be slower than exact methods like GaBP on a single core for specific model classes (e.g., Gaussian MLNs).
- Parallelization: The authors note that their sampling-based methods are inherently parallelizable, suggesting this as a key future direction for further scaling.
- Variational Methods: They are exploring variational methods for even larger hybrid domains and POMDPs.
- Local Lipschitz Assumption: The theoretical guarantees for the coarse-to-fine approach rely on potentials being locally Lipschitz, which is a reasonable assumption but worth noting.
Summary updated