A General Framework for Anytime Approximation in Probabilistic Databases

Maarten Van den Heuvel, Floris Geerts, Wolfgang Gatterbauer, Martin TheobaldarXiv 2018 · OpenReview

TL;DR

This paper introduces a more general branch-and-bound framework for approximating query probabilities in probabilistic databases. By employing "dissociation" to derive tighter bounds than existing model-based methods, their approach significantly improves accuracy and efficiency, offering a better trade-off between computation time and approximation quality.

What Problem Does This Paper Address?

Calculating the exact probability of a query over probabilistic databases (PDBs) is computationally expensive, often falling into the #P-hard complexity class. This makes it a bottleneck for applications like statistical relational learning. While existing "anytime approximation" methods offer faster, albeit approximate, answers, they rely on either sampling or a branch-and-bound approach with "model-based bounds." This paper aims to improve upon the latter by developing a more general and effective branch-and-bound framework that can achieve better approximations with the same computational resources.

Methods

The core innovation is the introduction of "dissociation-based bounds" to replace or augment the traditional "model-based bounds" within a branch-and-bound framework. Dissociation works by replacing multiple occurrences of a variable in a query's lineage (a propositional formula representing the query) with independent copies, each assigned a carefully chosen probability. This technique is shown to generalize and improve upon model-based bounds, leading to tighter upper and lower bounds for the query's probability.

The authors also propose a novel heuristic for the "branch" part of the algorithm, which involves selecting variables for Shannon expansion (a technique to break down complex formulas). Instead of simply picking the most frequent variable (as in prior work), they select the variable with the highest sum of "influences" of its occurrences. This influence-based selection, combined with gradient-descent methods for finding optimal dissociation bounds, allows for a more informed and efficient approximation process. They also introduce an "optimization trade-off" knob, allowing users to control how much time is spent on finding better lower bounds before proceeding.

Datasets

The experiments were conducted on the Yago3 dataset. The authors generated lineages from this dataset by considering four different queries, varying input probabilities, join orders, and injecting constants.

Key Insights and Ideas

  • Dissociation is a powerful generalization: The paper demonstrates that dissociation-based bounds are not just an alternative but a superior method for approximating probabilities, generalizing and improving upon existing model-based bounds.
  • Tighter bounds mean fewer approximations: By achieving tighter bounds, the framework can potentially reduce the number of computationally expensive Shannon expansions needed to reach a desired accuracy, leading to overall efficiency gains.
  • Influence-based variable selection is key: Moving beyond simple frequency heuristics for variable selection in Shannon expansion, using "influence" leads to better decisions and more efficient approximation.
  • Controllable trade-off: The introduction of an "optimization trade-off" knob allows for flexible resource allocation, balancing the effort spent on finding better bounds against the time available.

Key Results

The paper presents experimental results showing that their new methods, PGD (Projected Gradient Descent) and HB (Hybrid method), significantly outperform existing model-based (MB) and symmetric dissociation (SD) approaches on the Yago3 dataset. These new methods achieve better accuracy-time trade-offs, meaning they can achieve lower approximation errors for a given amount of time, or reach a target accuracy faster. Specifically, they highlight that their methods work best with the influence heuristic for variable selection, though they still outperform others even with the frequency heuristic.

Limitations and Future Work

  • Gradient Descent Computation: While gradient-descent methods find better lower bounds, they can take longer than randomly assigning model-based bounds. The paper acknowledges this trade-off and introduces the "optimization trade-off" knob to manage it.
  • Future Work: The authors suggest that their framework has potential applications beyond probabilistic databases, particularly in the broader field of statistical-relational learning (SRL).

Summary updated

Abstract

Anytime approximation algorithms that compute the probabilities of queries over probabilistic databases can be of great use to statistical learning tasks. Those approaches have been based so far on either (i) sampling or (ii) branch-and-bound with model-based bounds. We present here a more general branch-and-bound framework that extends the possible bounds by using 'dissociation', which yields tighter bounds.
BibTeX
@misc{heuvel2018general,
  author = {Maarten Van den Heuvel and Floris Geerts and Wolfgang Gatterbauer and Martin Theobald},
  title = {{A General Framework for Anytime Approximation in Probabilistic Databases}},
  year = {2018},
  eprint = {1806.10078},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1806.10078},
}
Figure