Optimal inference with local expressions

Graduation date: 1999Probabilistic inference using Bayesian networks is now a well-established\ud approach for reasoning under uncertainty. Among many e ciency-driven tech-\ud niques which have been developed, the Optimal Factoring Problem (OFP) is\ud distinguished for presenting a combinatorial optimization point of view on the\ud problem.\ud The contribution of this thesis is to extend OFP into a theoretical frame-\ud work that not only covers the standard Bayesian networks but also includes\ud non-standard Bayesian networks. A non-standard Bayesian network has struc-\ud tures within its local distributions that are signi cant to the problem. This\ud thesis presents value sets algebra as a coherent framework that facilitates formal\ud treatments of inference in both standard and non-standard Bayesian networks\ud as a combinatorial optimization problem.\ud Parallel to value sets algebra theory local expression languages allow one\ud to symbolically encode Bayesian network distributions. Such symbolic encod-\ud ings allow all the structural and numerical information in distributions to be\ud represented in the most compact form. However, the symbolic and syntactic \ud exibilities in local expression languages have the usual drawback of allow-\ud ing possible incoherent expressions. Value sets algebra leads us to an e cient\ud coherency veri cation on such expressions.\ud This thesis views optimal inference with local expressions as an optimal\ud search problem. The search space for this problem is shown to be so large that\ud it renders any exhaustive search impractical. Hence it is necessary to turn to\ud heuristic solutions. Using A* heuristic framework and ideas from OFP, which\ud is the counterpart of this problem for standard Bayesian networks, a heuris-\ud tic algorithm for the problem is developed. As a key feature, this algorithm\ud di erentiates between symbolic combinations of expressions and arithmetic op-\ud erations in the expressions. Cost bearing arithmetic operations are performed\ud only when su cient information is available to guarantee that no saving oppor-\ud tunities are lost. On the other hand, expressions are combined in a way that\ud quickly provides maximum opportunity for e cient arithmetic operations.\ud This thesis also explores the representation of Intercausal Independencies\ud (ICI) in Bayesian networks and de nes some new operators in local expression\ud language which are shown to facilitate more e cient ICI representations