Optimal Time-Space Tradeoff in Probabilistic Inference

Abstract

Recursive Conditioning, RC, is an any-space algorithm for exact inference in Bayesian networks, which can trade space for time in increments of the size of a floating point number. This smooth tradeoff is possible by varying the algorithm's cache size. When RC is run with a constrained cache size, an important problem arises: Which specific results should be cached in order to minimize the running time of the algorithm? RC is driven by a structure known as a dtree, and many such dtrees exist for a given Bayesian network. In this paper, we examine the problem of searching for an optimal caching scheme for a given dtree, and present some optimal time-space tradeoff curves for given dtrees of several published Bayesian networks. We also compare these curves to the memory requirements of state-of- the-art algorithms based on jointrees. Our results show that the memory requirements of these networks can be significantly reduced with only a minimal cost in time, allowing for exact inference in situations previously impractical. They also show that probabilistic reasoning systems can be efficiently designed to run under varying amounts of memory.