State-space Abstraction for Anytime Evaluation of Probabilistic Networks
This work addresses the problem of real-time probabilistic reasoning for designers, but it is incremental as it introduces state-space abstraction as an additional control parameter.
The authors tackled the computational complexity of evaluating probabilistic networks by varying state-space granularity, resulting in an anytime procedure that shows smooth improvement in approximation quality with increased computation time.
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.