Reference: Herskovits, E. & Cooper, G. F. Algorithms for Bayesian Belief-Network Precomputation. 1991.
Abstract: Bayesian belief networks show promise as a representational framework for constructing expert systems; they provide platforms for knowledge acquisition and for normative probabilistic inference. Despite the intuitive appeal of this inference paradigm, the run-time complexity of general belief-network computation may be too great for solving many complex problems in a practical amount of time. Therefore, researchers have focused their attention on developing approximate or special-case algorithms for belief-network inference. For belief networks with a highly skewed distribution of joint probabilities, storing a small number of cases to capture a large proportion of the likely uses of the network may lead to a significant increase in the speed of inference. We report here preliminary results of a set of algorithms that cache (precompute and store) a small subset of a belief network to decrease the expected running time for probability computation.