Bounding probabilistic relationships in Bayesian networks using qualitative influences: Methods and applications

C-L Liu and MP Wellman

International Journal of Approximate Reasoning 36:31-73, 2004.
Copyright © 2004 Published by Elsevier Science Inc. All rights reserved.

Abstract

We present conditions under which one can bound the probabilistic relationships between random variables in a Bayesian network by exploiting known or induced qualitative relationships. Generic strengthening and weakening operations produce bounds on cumulative distributions, and the directions of these bounds are maintained through qualitative influences. We show how to incorporate these operations in a state-space abstraction method, so that bounds provably tighten as an approximate network is refined. We apply these techniques to qualitative tradeoff resolution demonstrating an ability to identify qualitative relationships among random variables without exhaustively using the probabilistic information encoded in the given network. In an application to path planning, we present an anytime algorithm with run-time computable error bounds.

This article includes material from two UAI-98 papers:

• Incremental tradeoff resolution in qualitative probabilistic networks, Fourteenth Conference on Uncertainty in Artificial Intelligence, 1998, pp. 338–345

• Using qualitative relationships for bounding probability distributions, Fourteenth Conference on Uncertainty in Artificial Intelligence, 1998, pp. 346–353