Fast Belief Update Using Order-of-Magnitude Probabilities
We present an algorithm, called Predict, for updating beliefs in causal networks quantified with order-of-magnitude probabilities. The algorithm takes advantage of both the structure and the quantification of the network and presents a polynomial asymptotic complexity. Predict exhibits a conservative behavior in that it is always sound but not always complete. We provide sufficient conditions for completeness and present algorithms for testing these conditions and for computing a complete set of plausible values. We propose Predict as an efficient method to estimate probabilistic values and illustrate its use in conjunction with two known algorithms for probabilistic inference. Finally, we describe an application of Predict to plan evaluation, present experimental results, and discuss issues regarding its use with conditional logics of belief, and in the characterization of irrelevance.
Keywords: Foundations of uncertainty concepts, algorithms for uncertain
PS Link: file://rpal.rockwell.com/public/users/moises/predict95.ps
PDF Link: /papers/95/p208-goldszmidt.pdf
AUTHOR = "Moises Goldszmidt
TITLE = "Fast Belief Update Using Order-of-Magnitude Probabilities",
BOOKTITLE = "Proceedings of the Eleventh Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-95)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1995",
PAGES = "208--216"