Optimal Time-Space Tradeoff in Probabilistic Inference

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 total memory assigned to the algorithm's cache. 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 for any Bayesian network many such dtrees exist. In this paper, we examine the problem of searching for an optimal caching scheme and present some optimal time-space tradeoff curves for a given dtree. We present results on several published Bayesian networks, where these curves show that significant amounts of memory can be removed from the algorithm's cache with only a minimal cost in time, allowing for exact inference in situations previously impractical