State-space Abstraction for Anytime Evaluation of Probabilistic Networks
Michael Wellman, Chao-Lin Liu
One important factor determining the computational complexity of evaluating a probabilistic network is the cardinality of the state spaces of the nodes. By varying the granularity of the state spaces, one can trade off accuracy in the result for computational efficiency. We present an anytime procedure for approximate evaluation of probabilistic networks based on this idea. On application to some simple networks, the procedure exhibits a smooth improvement in approximation quality as computation time increases. This suggests that state-space abstraction is one more useful control parameter for designing real-time probabilistic reasoners.
Keywords: Probabilistic networks, anytime algorithms, abstraction, approximation.
PS Link: ftp://eecs.umich.edu/people/wellman/uai94.ps.Z
PDF Link: /papers/94/p567-wellman.pdf
AUTHOR = "Michael Wellman
and Chao-Lin Liu",
TITLE = "State-space Abstraction for Anytime Evaluation of Probabilistic Networks",
BOOKTITLE = "Proceedings of the Tenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-94)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1994",
PAGES = "567--574"