State-space abstraction methods for approximate evaluation of Bayesian networks.

Abstract

Bayesian networks provide a useful mechanism for encoding and reasoning about uncertainty. Recent progress in the design of inference algorithms for Bayesian networks has expanded the acceptance of Bayesian networks into a wide range of real-world applications. Inference algorithms for Bayesian networks can return exact or approximate solutions of the probability of interest, depending on the design of the algorithms. Approximate solutions of the desired probability can be instrumental in some situations: for instance, when allocated time does not permit the computation of exact solutions and when approximate solutions already satisfy the requirements of intended applications. This thesis presents algorithms for computing approximations of conditional probabilities of interest. These algorithms employ state-space abstraction techniques for computing approximations in the forms of point-valued probabilities and bounds of probability distributions. State-space abstraction techniques aggregate states of variables for obtaining approximations at reduced computational cost. Iterative algorithms designed with these techniques have demonstrated desirable anytime performance in experiments. This thesis also discusses properties of approximations. I present theorems that relate quality of approximations to conditional independence among variables in Bayesian networks. These theorems identify variables that are affected by the state-space abstraction operations and specify how the marginal probabilities of these variables are affected. Applying these theorems, we can design control heuristics that aim to optimize the performance profiles of the iterative algorithms designed with state-space abstraction techniques. In addition, this thesis reports conditions under which we can apply the state-space abstraction techniques to compute bounds of distributions. These bounds tighten over computation time, and can be useful for a variety of applications. In particular, these bounds of probability distribution can be applied to resolve tradeoffs in qualitative probabilistic networks. This thesis discusses the applications of state-space abstraction and incremental node marginalization techniques to this tradeoff resolution problem.