Approximate Decomposition: A Method for Bounding and Estimating Probabilistic and Deterministic Queries

David LarkinUAI 2003

TL;DR

This paper introduces "Approximate Decomposition" (AD), a novel algorithm for efficiently bounding and estimating answers to complex probabilistic and deterministic queries in large graphical models. AD tackles the intractability of exact inference by strategically simplifying the problem structure, offering tighter bounds than existing methods like mini-buckets, especially for challenging networks.

What Problem Does This Paper Address?

Reasoning with uncertainty in Artificial Intelligence, particularly using belief networks, often involves computationally intractable problems. Exact algorithms like clique tree propagation or variable elimination require time and space that grow exponentially with the "treewidth" of the network's interaction graph. This makes them infeasible for large, complex networks. While approximation methods exist, they either lack guaranteed bounds (like iterative belief propagation), can be expensive (stochastic simulation), or require tailoring to specific network types (variational methods). Mini-buckets offer guaranteed bounds but often produce bounds that are too loose to be practically useful. This paper aims to bridge this gap by providing a method that guarantees tight bounds and accurate estimates for both probabilistic and deterministic queries on general networks.

Methods

The core of the paper is the Approximate Decomposition (AD) algorithm. AD works by iteratively eliminating variables from the graphical model, similar to variable elimination. However, AD introduces a crucial constraint: it limits the "width" of the graph (a measure of its density, related to the number of neighbors a node has) to a predefined bound i.

Here's how it works:

  1. Variable Elimination with Width Control: AD eliminates variables one by one. If eliminating a variable would create new edges that increase the graph's width beyond the bound i, AD intervenes.
  2. Edge Deletion: To maintain the width constraint, AD strategically deletes edges.
  3. Approximate Decomposition Step: When edges are deleted, the exact elimination function is approximated. This is done by setting up and solving a linear program (LP). The LP aims to find a set of simpler functions (one for each subset of variables involved in the deleted edges) whose product (for upper bounds) or sum (for MAX-CSP) approximates the original complex function. This LP formulation is a key innovation, allowing for tractable computation of bounds.
  4. Bounding: The algorithm computes both upper and lower bounds for queries. If a specific type of bound (upper or lower) is desired, the algorithm is run accordingly.

The paper also defines the "cost" of a bound as the expected error in the final query result, and the LP is designed to minimize this cost, specifically focusing on the L1 distance (sum of absolute errors) for probabilistic inference and MAX-CSP.

Datasets

The paper evaluates its method on several benchmark networks:

  • CPCS2 network: A large belief network with 360 binary variables and a treewidth of 20.
  • CPCS3 network: A larger belief network with 422 binary variables and a treewidth of 22.
  • Large random networks: Networks with 115 binary variables and an average induced width of 34, making exact inference intractable.
  • Random MAX-CSP problems: Instances with 30 ternary variables and 125 binary constraints.

The paper does not introduce new datasets but uses existing, challenging benchmarks to demonstrate the effectiveness of AD.

Key Insights and Ideas

  • Width as a Tractability Measure: The paper leverages the concept of graph width as a direct measure of computational complexity. By bounding the width, AD effectively controls the complexity of the intermediate computations.
  • Linear Programming for Bounding: The core novelty lies in using linear programming to approximate complex functions arising from variable elimination. This allows for the computation of guaranteed bounds even when exact methods become intractable.
  • Tight Bounds: AD consistently produces significantly tighter bounds (smaller "Hi-Lo" ratios) compared to mini-buckets, especially on difficult problems. This means the upper and lower bounds are much closer to each other and, importantly, to the true exact answer.
  • Unified Approach: The method is presented as applicable to both probabilistic (belief inference, MPE) and deterministic (MAX-CSP) queries, demonstrating its generality.
  • Trade-off between Bound Quality and Computation Time: AD incurs overhead due to the LP solving step, making it slower than mini-buckets for the same i bound. However, the superior quality of AD's bounds often justifies this trade-off.

Key Results

The paper presents empirical results comparing AD with mini-buckets (MB) on various networks.

  • Belief Inference: On CPCS2 and CPCS3 networks, AD produced bounds that were orders of magnitude tighter than MB. For example, on CPCS2, AD's upper bound was only a factor of 1.21 higher than its lower bound, while MB's was a factor of 26.3 higher. AD's estimates also showed significantly less divergence from the exact answer.
  • MPE (Most Probable Explanation): AD again outperformed MB in producing tighter bounds and more accurate estimates. For instance, on CPCS3, AD's bounds were orders of magnitude better than MB's.
  • MAX-CSP: AD also showed superior performance in approximating the number of violated constraints, providing tighter bounds and more accurate estimates than MB.
  • Large Random Networks: For networks where exact inference was intractable, AD provided much tighter bounds than MB.

While AD was generally slower than MB for comparable i bounds, the quality of AD's results was consistently superior.

Limitations and Future Work

  • Computational Overhead: The primary limitation acknowledged is the computational cost associated with solving linear programs, making AD slower than simpler methods like mini-buckets for a given complexity bound i.
  • Approximation of Exponential Function: The LP formulation involves approximating an exponential function, which can lead to arbitrarily bad underestimation for upper bounds and overestimation for lower bounds if relative errors become very large. The paper addresses this by normalizing cost coefficients and setting very small ones to a minimum value.
  • Future Work: The authors suggest investigating a "multiple-query version" of the algorithm, potentially inspired by clique tree propagation, to further improve efficiency. They also plan to explore how to handle cases where the target function value is zero more gracefully.

Summary updated

BibTeX
@inproceedings{larkin2003approximate,
  author = {David Larkin},
  title = {{Approximate Decomposition: A Method for Bounding and Estimating Probabilistic and Deterministic Queries}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2003},
}
Figure