Any-Space Probabilistic Inference
This work addresses the space-time tradeoff problem in probabilistic inference for researchers and practitioners in AI and machine learning, offering incremental improvements to an existing algorithm.
The paper extends Recursive Conditioning (RC) for exact inference in Bayesian networks to more general probability distributions, introduces a forgetting mechanism that reduces space requirements, and develops a version for maximum a posteriori (MAP) hypotheses that allows time-space tradeoffs and reuses computations across queries, showing orders of magnitude improvements in space in some cases.
We have recently introduced an any-space algorithm for exact inference in Bayesian networks, called Recursive Conditioning, RC, which allows one to trade space with time at increments of X-bytes, where X is the number of bytes needed to cache a floating point number. In this paper, we present three key extensions of RC. First, we modify the algorithm so it applies to more general factorization of probability distributions, including (but not limited to) Bayesian network factorizations. Second, we present a forgetting mechanism which reduces the space requirements of RC considerably and then compare such requirmenets with those of variable elimination on a number of realistic networks, showing orders of magnitude improvements in certain cases. Third, we present a version of RC for computing maximum a posteriori hypotheses (MAP), which turns out to be the first MAP algorithm allowing a smooth time-space tradeoff. A key advantage of presented MAP algorithm is that it does not have to start from scratch each time a new query is presented, but can reuse some of its computations across multiple queries, leading to significant savings in ceratain cases.