Approximate Decomposition: A Method for Bounding and Estimating Probabilistic and Deterministic Queries
This addresses computational bottlenecks in AI for reasoning under uncertainty, offering a practical method for approximate solutions in domains like belief networks and constraint satisfaction, though it appears incremental as it builds on existing approximation techniques.
The paper tackles the intractability of exact inference and optimization in dense probabilistic and deterministic reasoning tasks by mapping them to sparser approximations, enabling bounds on solutions. Empirical results show sharp bounds, such as nearly identical upper and lower bounds on conditional probabilities in a large CPCS network.
In this paper, we introduce a method for approximating the solution to inference and optimization tasks in uncertain and deterministic reasoning. Such tasks are in general intractable for exact algorithms because of the large number of dependency relationships in their structure. Our method effectively maps such a dense problem to a sparser one which is in some sense "closest". Exact methods can be run on the sparser problem to derive bounds on the original answer, which can be quite sharp. We present empirical results demonstrating that our method works well on the tasks of belief inference and finding the probability of the most probable explanation in belief networks, and finding the cost of the solution that violates the smallest number of constraints in constraint satisfaction problems. On one large CPCS network, for example, we were able to calculate upper and lower bounds on the conditional probability of a variable, given evidence, that were almost identical in the average case.