Physical Sciences and Mathematics Commons^™

Reactive Bayesian Network Computation Using Feedback Control: An Empirical Study, Ole J. Mengshoel, Abe Ishihara, Erik Reed

Ole J Mengshoel

Accelerating Bayesian Network Parameter Learning Using Hadoop And Mapreduce, Aniruddha Basak, Irina Brinster, Xianheng Ma, Ole J. Mengshoel

Ole J Mengshoel

Adaptive Control Of Bayesian Network Computation, Erik Reed, Abe Ishihara, Ole J. Mengshoel

Ole J Mengshoel

Initialization And Restart In Stochastic Local Search: Computing A Most Probable Explanation In Bayesian Networks, Ole J. Mengshoel, David C. Wilkins, Dan Roth

Ole J Mengshoel

For hard computational problems, stochastic local search has proven to be a competitive approach to finding optimal or approximately optimal problem solutions. Two key research questions for stochastic local search algorithms are: Which algorithms are effective for initialization? When should the search process be restarted? In the present work, we investigate these research questions in the context of approximate computation of most probable explanations (MPEs) in Bayesian networks (BNs). We introduce a novel approach, based on the Viterbi algorithm, to explanation initialization in BNs. While the Viterbi algorithm works on sequences and trees, our approach works on BNs with arbitrary …

Understanding The Scalability Of Bayesian Network Inference Using Clique Tree Growth Curves, Ole J. Mengshoel

Ole J Mengshoel

One of the main approaches to performing computation in Bayesian networks (BNs) is clique tree clustering and propagation. The clique tree approach consists of propagation in a clique tree compiled from a BN, and while it was introduced in the 1980s, there is still a lack of understanding of how clique tree computation time depends on variations in BN size and structure. In this article, we improve this understanding by developing an approach to characterizing clique tree growth as a function of parameters that can be computed in polynomial time from BNs, specifically: (i) the ratio of the number of …

Developing Large-Scale Bayesian Networks By Composition: Fault Diagnosis Of Electrical Power Systems In Aircraft And Spacecraft, Ole J. Mengshoel, Scott Poll, Tolga Kurtoglu

Ole J Mengshoel

In this paper, we investigate the use of Bayesian networks to construct large-scale diagnostic systems. In particular, we consider the development of large-scale Bayesian networks by composition. This compositional approach reflects how (often redundant) subsystems are architected to form systems such as electrical power systems. We develop high-level specifiations, Bayesian networks, clique trees, and arithmetic circuits representing 24 different electrical power systems. The largest among these 24 Bayesian networks contains over 1,000 random variables. Another BN represents the real-world electrical power system ADAPT, which is representative of electrical power systems deployed in aerospace vehicles. In addition to demonstrating the scalability …

Controlled Generation Of Hard And Easy Bayesian Networks: Impact On Maximal Clique Size In Tree Clustering, Ole J. Mengshoel, David C. Wilkins, Dan Roth

Ole J Mengshoel

This article presents and analyzes algorithms that systematically generate random Bayesian networks of varying difficulty levels, with respect to inference using tree clustering. The results are relevant to research on efficient Bayesian network inference, such as computing a most probable explanation or belief updating, since they allow controlled experimentation to determine the impact of improvements to inference algorithms. The results are also relevant to research on machine learning of Bayesian networks, since they support controlled generation of a large number of data sets at a given difficulty level. Our generation algorithms, called BPART and MPART, support controlled but random construction …