Efficient Bayesian network inference: Genetic algorithms, stochastic local search, and abstraction

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. First, improvements are made to niching genetic algorithms, which converge to multiple local optima. Local optima is an important problem in Bayesian network inference. 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 Bayesian network inference. We present the Stochastic Greedy Search algorithm, which uses noisy search steps, different measures of gain, and an operator-based approach, giving different ways to perform the local search. 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 application networks. In application networks, initialization algorithms prove to be very valuable, and we introduce novel initialization algorithms.; and aggregation to improve Bayesian network inference. A criterion is introduced variance as a measure of quality. Results are presented that quantify how 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, showing that Bayesian networks can be deceptive. The other result is based on translating satisfiability problems into Bayesian networks. We describe how connectivity, value of conditional probability tables as well as the degree of regularity of the underlying graph affect the speed of inference for Hugin and Stochastic Greedy Search.