State-space Abstraction for Anytime Evaluation of Probabilistic Networks
Preprint
Abstract
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
All Related Versions
This publication has 13 references indexed in Scilit:
- Tradeoffs in knowledge-based construction of probabilistic modelsIEEE Transactions on Systems, Man, and Cybernetics, 1994
- Metareasoning and the problem of small worldsIEEE Transactions on Systems, Man, and Cybernetics, 1994
- Dynamic belief networks for discrete monitoringIEEE Transactions on Systems, Man, and Cybernetics, 1994
- Dynamic construction and refinement of utility-based categorization modelsIEEE Transactions on Systems, Man, and Cybernetics, 1994
- Inference-driven construction of valuation systems from first-order clausesIEEE Transactions on Systems, Man, and Cybernetics, 1994
- Approximating probabilistic inference in Bayesian belief networks is NP-hardArtificial Intelligence, 1993
- A language for construction of belief networksIEEE Transactions on Pattern Analysis and Machine Intelligence, 1993
- CONSTRUCTION OF BELIEF AND DECISION NETWORKSComputational Intelligence, 1992
- An algebra of bayesian belief universes for knowledge‐based systemsNetworks, 1990
- The computational complexity of probabilistic inference using bayesian belief networksArtificial Intelligence, 1990