Efficient Bayesian Network Inference: Genetic Algorithms, Stochastic Local Search, and Abstraction
David C. Wilkins, Ole J. Mengshoel · 1999
Bayesian networks are a core method for uncertainty representation and reasoning in artificial intelligence. This dissertation focuses on efficient approximate Bayesian network inference for computing the most probable explanation. New algorithms for efficient approximate inference are presented, and new techniques are described for creating hard synthetic Bayesian networks. Three major research results related to speeding up Bayesian network inference are presented in this dissertation. First, improvements are made in the use of genetic algorithms. Local optima is an important problem in Bayesian network inference. Classical genetic algorithms converge, like hill-climbing algorithms, to one local optimum, while niching genetic algorithms converge to multiple local optima. This dissertation introduces the Probabilistic Crowding niching genetic algorithm, and presents theoretical and empirical results showing that Probabilistic Crowding gives predictable convergence, which at equilibrium is proportional to the utility function, which for Bayesian networks is the probability of an explanation. Second, improvements are made to stochastic local search algorithms for efficient Bayesian network inference. This dissertation presents the Stochastic Greedy Search algorithm, which introduces noisy steps that allows local search to escape local optima. We also introduce different measures of gain (or gradient) and an operator-based approach, giving several ways to search locally. Comparisons to the state-of-the-art inference algorithm Hugin show that Stochastic Greedy Search performs significantly better for satisfiability Bayesian networks as well as for certain Bayesian networks from applications. In application networks, initialization algorithms, which compute the most probable explanation in bounding cases, prove to be very valuable, and we introduce two novel initialization algorithms denoted forward and backward dynamic programming. Initialization starts the local search at points closer to local optima than when search starts from an explanation created uniformly at random. Lastly, improvements are made to the use and measurement of abstraction and aggregation to improve Bayesian network inference. A criterion is introduced that quantifies how different methods of abstraction impact the quality of inference. The criterion regards abstraction as noise and uses variance as a measure of quality. Results are presented that quantify how different methods and levels of abstraction effect accuracy. Two major research results are presented that relate to creating hard synthetic Bayesian networks for empirical research on inference algorithms. One method translates deceptive problems studied in genetic algorithms to a Bayesian network setting. We show that Bayesian networks can be deceptive, and this is important since genetic algorithm performance suffers on deceptive problems. The other result is based on translating satisfiability problems