Using Qualitative Relationships for Bounding Probability Distributions

Using the signs of qualitative relationships, we can implement abstraction operations that are guaranteed to bound the distributions of interest in the desired direction. By evaluating incrementally improved approximate networks, our algorithm obtains monotonically tightening bounds that converge to exact distributions. For supermodular utility functions, the tightening bounds monotonically reduce the set of admissible decision alternatives as well. 1 Introduction Approximation techniques have gained increasing interest among those employing Bayesian networks for probabilistic reasoning, despite the fact that computing a desired probability distribution to a fixed degree of accuracy has been shown to be NPhard (Dagum & Luby 1993). Approximation techniques offer reasonable prospects of significant accuracy, and increased opportunity to consider applications larger than we could otherwise. For instance, approximation techniques can be useful for applications that need to respond to requests for solutions under time constraints. By appropriately managing the reasoning process, we may obtain approximate solutions that meet the needs of these applications in cases where we would not be able to compute exact solutions given the time constraints.