Controlled Generation of Hard and Easy Bayesian Networks: Impact on Maximal Clique Size in Tree Clustering
Ole J. Mengshoel, David C. Wilkins, Dan Roth
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 of bipartite and multipartite Bayesian networks. The Bayesian network parameters that we vary are the total number of nodes, degree of connectivity, the ratio of the number of non-root nodes to the number of root nodes, regularity of the underlying graph, and characteristics of the conditional probability tables. The main dependent parameter is the size of the maximal clique as generated by tree clustering. This article presents extensive empirical analysis using the Hugin tree clustering approach as well as theoretical analysis related to the random generation of Bayesian networks using BPART and MPART.
Published in: Artificial Intelligence, Volume 170 , Issue 16-17, Pages 1137-1174, 2006.
Sensor Validation using Bayesian Networks
Ole J. Mengshoel, Adnan Darwiche, Serdar Uckun
One of NASA’s key mission requirements is robust state estimation. Sensing, using a wide range of sensors and sensor fusion approaches, plays a central role in robust state estimation, and there is a need to diagnose sensor failure as well as component failure. Sensor validation techniques address this problem: given a vector of sensor readings, decide whether sensors have failed, therefore producing bad data. We take in this paper a probabilistic approach, using Bayesian networks, to diagnosis and sensor validation, and investigate several relevant but slightly different Bayesian network queries. We emphasize that on-board inference can be performed on a compiled model, giving fast and predictable execution times. Our results are illustrated using an electrical power system, and we show that a Bayesian network with over 400 nodes can be compiled into an arithmetic circuit that can correctly answer queries in less than 500 microseconds on average.
Published in: 9th International Symposium on Artificial Intelligence, Robotics, and Automation in Space (iSAIRAS-08), February 25-29, 2008, Los Angeles, CA.
Advanced Diagnostics and Prognostics Testbed
Scott Poll, Ann Patterson-Hine, Joe Camisa, David Garcia, David Hall, Charles Lee, Ole J. Mengshoel, Christian Neukom, David Nishikawa, John Ossenfort, Adam Sweet, Serge Yentus, Indranil Roychoudhury,
Researchers in the diagnosis community have developed a number of promising techniques for system health management. However, realistic empirical evaluation and comparison of these approaches is often hampered by a lack of standard data sets and suitable testbeds. In this paper we describe the Advanced Diagnostics and Prognostics Testbed (ADAPT) at NASA Ames Research Center. The purpose of the testbed is to measure, evaluate, and mature diagnostic and prognostic health management technologies. This paper describes the testbed’s hardware, software architecture, and concept of operations. A simulation testbed that accompanies ADAPT, and some of the diagnostic and decision support approaches being investigated are also discussed.
Published in: The 18th International Workshop on Principles of Diagnosis (DX-07), Pages 178-185, Nashville, TN, May 29-31, 2007.
Probabilistic Crowding: Deterministic Crowding with Probabilistic Replacement
Ole J. Mengshoel, David E. Goldberg
This paper presents a novel niching algorithm, probabilistic crowding. Like its predecessor deterministic crowding, probabilistic crowding is fast, simple, and requires no parameters beyond that of the classical GA. In probabilistic crowding, subpopulations are maintained reliably, and we analyze and predict how this maintenance takes place. This paper also identifies probabilistic crowding as a member of a family of algorithms, which we call integrated tournament algorithms. Integrated tournament algorithms also include deterministic crowding, restricted tournament selection, elitist recombination, parallel recombinative simulated annealing, the Metropolis algorithm, and simulated annealing.
Published in: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-99), Pages 409-416, Orlando, FL, July 13-17, 1999.
Designing Resource-Bounded Reasoners using Bayesian Networks: System Health Monitoring and Diagnosis
Ole J. Mengshoel
In this work we are concerned with the conceptual design of large-scale diagnostic and health management systems that use Bayesian networks. While they are potentially powerful, improperly designed Bayesian networks can result in too high memory requirements or too long inference times, to they point where they may not be acceptable for real-time diagnosis and health management in resource-bounded systems such as NASA\'s aerospace vehicles. We investigate the clique tree clustering approach to Bayesian network inference, where increasing the size and connectivity of a Bayesian network typically also increases clique tree size. This paper combines techniques for analytically characterizing clique tree growth with bounds on clique tree size imposed by resource constraints, thereby aiding the design and optimization of large-scale Bayesian networks in resource-bounded systems. We provide both theoretical and experimental results, and illustrate our approach using a NASA case study. Published in: Proceedings of the 18th International Workshop on Principles of Diagnosis (DX-076), Pages 330-337, Nashville, TN, May 29-31, 2007.
Macroscopic Models of Clique Tree Growth for Bayesian Networks
Ole J. Mengshoel
In clique tree clustering, inference consists of propagation in a clique tree compiled from a Bayesian network. In this paper, we develop an analytical approach to characterizing clique tree growth as a function of increasing Bayesian network connectedness, specifically: (i) the expected number of moral edges in their moral graphs or (ii) the ratio of the number of non-root nodes to the number of root nodes. In experiments, we systematically increase the connectivity of bipartite Bayesian networks, and find that clique tree size growth is well-approximated by Gompertz growth curves. This research improves the understanding of the scaling behavior of clique tree clustering, provides a foundation for benchmarking and developing improved BN inference algorithms, and presents an aid for analytical trade-off studies of tree clustering using growth curves. Published in: Proceedings of the Twenty-second AAAI Conference on Artificial Intelligence (AAAI-07), Pages 1256-1262, Vancouver, British Columbia, 2007.
Information Filtering using Bayesian Networks: Effective User Interfaces for Aviation Weather Data
Corinne Clinton Ruokangas, Ole J. Mengshoel
Weather is a complex, dynamic process with tremendous impact on aviation. While pilots often have access to large amounts of aviation weather data, they find it difficult and time-consuming to identify weather hazards, due to the sheer amount and cryptic formatting of the data. To address this challenge, we have developed information filtering concepts based on a unified Bayesian network model, integrating text and graphical weather data in the context of specific mission, equipment and personal profiles. Based on these concepts, we have implemented three applications, all of which were compared to existing technology. Using one of the applications, the AWARE Preflight system, pilots found significantly more hazards in about half the time compared to using the current technology. Published in: Proceedings of the 8th International Conference on Intelligent User Interfaces (IUI-03), Pages: 280 - 283, Miami, FL, 2003.
Diagnosing Faults in Electrical Power Systems of Spacecraft and Aircraft
Ole J. Mengshoel, Adnan Darwiche, Keith Cascio, Mark Chavira, Scott Poll, Serdar Uckun
Electrical power systems play a critical role in spacecraft and aircraft. This paper discusses our development of a diagnostic capability for an electrical power system testbed, ADAPT, using probabilistic techniques. In the context of ADAPT, we present two challenges, regarding modelling and real-time performance, often encountered in real-world diagnostic applications. To meet the modelling challenge, we discuss our novel high-level specification language which supports auto-generation of Bayesian networks. To meet the real-time challenge, we compile Bayesian networks into arithmetic circuits. Arithmetic circuits typically have small footprints and are optimized for the real-time avionics systems found in spacecraft and aircraft. Using our approach, we present how Bayesian networks with over 400 nodes are auto-generated and then compiled into arithmetic circuits. Using real-world data from ADAPT as well as simulated data, we obtain average inference times smaller than one millisecond when computing diagnostic queries using arithmetic circuits that model our real-world electrical power system. Published in: Proceedings of the Twentieth IAAI Conference on Artificial Intelligence (IAAI-08), Chicago, IL, 2008.
Understanding the Role of Noise in Stochastic Local Search: Analysis and Experiments
Ole J. Mengshoel
Stochastic local search (SLS) algorithms have recently been proven to be among the best approaches to solving computationally hard problems. SLS algorithms typically have a number of parameters, optimized empirically, that characterize and determine their performance. In this article, we focus on the noise parameter. The theoretical foundation of SLS, including an understanding of how to the optimal noise varies with problem difficulty, is lagging compared to the strong empirical results obtained using these algorithms. A purely empirical approach to understanding and optimizing SLS noise, as problem instances vary, can be very computationally intensive. To complement existing experimental results, we formulate and analyze several Markov chain models of SLS. In particular, we compute expected hitting times and show that they are rational functions for individual problem instances as well as their mixtures. Expected hitting time curves are analytical counterparts to noise response curves reported in the experimental literature. Hitting time analysis using polynomials and convex functions is also discussed. In addition, we present examples and experimental results illustrating the impact of varying noise probability on SLS run time. In experiments, where most probable explanations in Bayesian networks are computed, we use synthetic problem instances as well as problem instances from applications. We believe that our results provide an improved theoretical understanding of the role of noise in stochastic local search, thereby providing a foundation for further progress in this area. Published in: Artificial Intelligence, Volume 172, Issues 8-9, May 2008, Pages: 955-990.
Constraint Handling Using Tournament Selection: Abductive Inference in Partly Deterministic Bayesian Network
Severino F. Galan, Ole J. Mengshoel
Constraints occur in many application areas of interest to evolutionary computation. The area considered here is Bayesian networks (BNs), which is a probability-based method for representing and reasoning with uncertain knowledge. This work deals with constraints in BNs and investigates how tournament selection can be adapted to better process such constraints in the context of abductive inference. Abductive inference in BNs consists of finding the most probable explanation given some evidence. Since exact abductive inference is NP-hard, several approximate approaches to this inference task have been developed. One of them applies evolutionary techniques in order to find optimal or close-to-optimal explanations. A problem with the traditional evolutionary approach is this: As the number of constraints determined by the zeros in the conditional probability tables grows, performance deteriorates because the number of explanations whose probability is greater than zero decreases. To minimize this problem, this paper presents and analyzes a new evolutionary approach to abductive inference in BNs. By considering abductive inference as a constraint optimization problem, the novel approach improves performance dramatically when a BN\'s conditional probability tables contain a significant number of zeros. Experimental results are presented comparing the performances of the traditional evolutionary approach and the approach introduced in this work. The results show that the new approach significantly outperforms the traditional one. Accepted for publication in Evolutionary Computation.
The Crowding Approach to Niching in Genetic Algorithms
Ole J. Mengshoel, David E. Goldberg
A wide range of niching techniques have been investigated in evolutionary and genetic algorithms. In this article, we focus on niching using crowding techniques in the context of what we call local tournament algorithms. In addition to deterministic and probabilistic crowding, the family of local tournament algorithms includes the Metropolis algorithm, simulated annealing, restricted tournament selection, and parallel recombinative simulated annealing. We describe an algorithmic and analytical framework which is applicable to a wide range of crowding algorithms. As an example of utilizing this framework, we present and analyze the probabilistic crowding niching algorithm. Like the closely related deterministic crowding approach, probabilistic crowding is fast, simple, and requires no parameters beyond those of classical genetic algorithms. In probabilistic crowding, sub-populations are maintained reliably, and we show that it is possible to analyze and predict how this maintenance takes place. We also provide novel results for deterministic crowding, show how different crowding replacement rules can be combined in portfolios, and discuss population sizing. Our analysis is backed up by experiments that further increase the understanding of probabilistic crowding. Accepted for publication in Evolutionary Computation.