The max-min hill-climbing Bayesian network structure learning algorithm

We present a new algorithm for Bayesian network structure learning, called Max-Min Hill-Climbing (MMHC). The algorithm combines ideas from local learning, constraint-based, and search-and-score techniques in a principled and effective way. It first reconstructs the skeleton of a Bayesian network and then performs a Bayesian-scoring greedy hill-climbing search to orient the edges. In our extensive empirical evaluation MMHC outperforms on average and in terms of various metrics several prototypical and state-of-the-art algorithms, namely the PC, Sparse Candidate, Three Phase Dependency Analysis, Optimal Reinsertion, Greedy Equivalence Search, and Greedy Search. These are the first empirical results simultaneously comparing most of the major Bayesian network algorithms against each other. MMHC offers certain theoretical advantages, specifically over the Sparse Candidate algorithm, corroborated by our experiments. MMHC and detailed results of our study are publicly available at http://www.dsl-lab.org/supplements/mmhc_paper/mmhc_index.html. Editor: Andrew W. Moore     

Expert system for predicting unstable angina based on Bayesian networks

The use of computer-based clinical decision support (CDS) tools is growing significantly in recent years. These tools help reduce waiting lists, minimise patient risks and, at the same time, optimise the cost health resources. In this paper, we present a CDS application that predicts the probability of having unstable angina based on clinical data. Due to the characteristics of the variables (mostly binary) a Bayesian network model was chosen to support the system. Bayesian-network model was constructed using a population of 1164 patients, and subsequently was validated with a population of 103 patients. The validation results, with a negative predictive value (NPV) of 91%, demonstrate its applicability to help clinicians. The final model was implemented as a web application that is currently been validated by clinician specialists.     

A Comparison of Bayesian and Belief Function Reasoning

The goal of this paper is to compare the similarities and differences between Bayesian and belief function reasoning. Our main conclusion is that although there are obvious differences in semantics, representations, and the rules for combining and marginalizing representations, there are many similarities. We claim that the two calculi have roughly the same expressive power. Each calculus has its own semantics that allow us to construct models suited for these semantics. Once we have a model in either calculus, one can transform it to the other by means of a suitable transformation.     

Improving ecosystem services modelling: Insights from a Bayesian network tools review

Numerous studies attempt to unravel the role played by Biodiversity in ecosystems and ES reliance on Biodiversity. Achieving this aim is difficult given: the multi-layered Biodiversity-ES relationship; the temporal and spatial heterogeneity of ES; and, the interactions between biotic and abiotic components in ecosystems influencing processes and services. Bayesian networks have recently gained importance in ecological modelling. The integration of empirical data with expert knowledge and the explicit treatment of uncertainties, demonstrate their usefulness. Publications describing network-based Biodiversity-ES models, demonstrate their application is still limited. A watershed's environmental risk management network modelled from a Biodiversity-ES perspective is discussed. It demonstrates an improvement on conventional approaches, expressing risk in terms of the underlying causal relations between environmental risk events, triggers, controls and consequences. The model is developed in AgenaRisk and two other tools, Netica and Hugin. A comparison between them highlights the dependence on the tool of choice.     

SR-30 turbojet engine real-time sensor health monitoring using neural networks,and Bayesian belief networks

This paper describes the use of artificial intelligence-based techniques for detecting and isolating sensor failures in a turbojet engine. Specifically, three artificial intelligence (AI) techniques are employed: artificial neural networks (NNs), statistical expectations, and Bayesian belief networks (BBNs). These techniques are combined into an overall system that is capable of distinguishing between sensor failure and engine failure—a critical capability in the operation of turbojet engines. The turbojet engine used in this study is an SR-30 developed by Turbine Technologies. Initially, NNs were designed and trained to recognize sensor failure in the engine. The increased random noise output from failing sensors was used as the key indicator. Next, a Bayesian statistical method was used to recognize sensor failure based on the bias error occurring in the sensors. Finally, a BBN was developed to interpret the results of the NN and statistical evaluations. The BBN determines whether single or multiple sensor failures signify engine failure, or whether sensor failures represent separate, unrelated incidences. The BBN algorithm is also used to distinguish between bias and noise errors on sensors used to monitor turbojet performance. The overall system is demonstrated to work equally well during start-up and main-stage operation of the engine. Results show that the method can efficiently detect and isolate single or multiple sensor failures within this dynamic environment.     

On the completeness of an identifiability algorithm for semi-Markovian models

This paper addresses the problem of identifying causal effects from nonexperimental data in a causal Bayesian network, i.e., a directed acyclic graph that represents causal relationships. The identifiability question asks whether it is possible to compute the probability of some set of (effect) variables given intervention on another set of (intervention) variables, in the presence of non-observable (i.e., hidden or latent) variables. It is well known that the answer to the question depends on the structure of the causal Bayesian network, the set of observable variables, the set of effect variables, and the set of intervention variables. Sound algorithms for identifiability have been proposed, but no complete algorithm is known. We show that the identify algorithm that Tian and Pearl defined for semi-Markovian models (Tian and Pearl 2002, 2002, 2003), an important special case of causal Bayesian networks, is both sound and complete. We believe that this result will prove useful to solve the identifiability question for general causal Bayesian networks.      

Credal networks

This paper presents a complete theory of credal networks, structures that associate convex sets of probability measures with directed acyclic graphs. Credal networks are graphical models for precise/imprecise beliefs. The main contribution of this work is a theory of credal networks that displays as much flexibility and representational power as the theory of standard Bayesian networks. Results in this paper show how to express judgements of irrelevance and independence, and how to compute inferences in credal networks. A credal network admits several extensions—several sets of probability measures comply with the constraints represented by a network. Two types of extensions are investigated. The properties of strong extensions are clarified through a new generalization of d-separation, and exact and approximate inference methods are described for strong extensions. Novel results are presented for natural extensions, and linear fractional programming methods are described for natural extensions. The paper also investigates credal networks that are defined globally through perturbations of a single network.     

A Bayesian Method for the Induction of Probabilistic Networks from Data

This paper presents a Bayesian method for constructing probabilistic networks from databases. In particular, we focus on constructing Bayesian belief networks. Potential applications include computer-assisted hypothesis testing, automated scientific discovery, and automated construction of probabilistic expert systems. We extend the basic method to handle missing data and hidden (latent) variables. We show how to perform probabilistic inference by averaging over the inferences of multiple belief networks. Results are presented of a preliminary evaluation of an algorithm for constructing a belief network from a database of cases. Finally, we relate the methods in this paper to previous work, and we discuss open problems.     

Temporal Reasoning and Bayesian Networks

This work examines important issues in probabilistic temporal representation and reasoning using Bayesian networks (also known as belief networks). The representation proposed here utilizes temporal (or dynamic) probabilities to represent facts, events, and the effects of events. The architecture of a belief network may change with time to indicate a different causal context. Probability variations with time capture temporal properties such as persistence and causation. They also capture event interaction, and when the interaction between events follows known models such as the competing risks model, the additive model, or the dominating event model, the net effect of many interacting events on the temporal probabilities can be calculated efficiently. This representation of reasoning also exploits the notion of temporal degeneration of relevance due to information obsolescence to improve the efficiency.     

A GUI for Jess

The paper describes JessGUI, a graphical user interface developed on top of the Jess expert system shell. The central idea of the JessGUI project was to make building, revising, updating, and testing Jess-based expert systems easier, more flexible, and more user friendly. There are many other expert system building tools providing a rich and comfortable integrated development environment to expert system builders. However, they are all either commercial or proprietary products. Jess and JessGUI are open-source freeware, and yet they are well suited for building even complex expert system applications, both stand-alone and Web-based ones. An important feature of JessGUI is its capability of saving knowledge bases in XML format (in addition to the original Jess format), thus making them potentially easy to interoperate with other knowledge bases on the Internet. Jess and JessGUI are also used as practical knowledge engineering tools to support both introductory and advanced university courses on expert systems. The paper presents design details of JessGUI, explains its links with the underlying Jess knowledge representation and reasoning tools, and shows examples of using JessGUI in expert system development. It also discusses some of the current efforts in extending Jess/JessGUI in order to provide intelligent features originally not supported in Jess.     

A comparative study for forecasting using neural networks vs genetically identified Box&Jenkins models

This paper aims to discuss the results and conclusions of an extensive comparative study on the forecasting performance between two different techniques: a genetic expert system in which a genetic algorithm carries out the identification stage embraced in the three- phase Box&Jenkins univariate methodology; and a connectionist approach. At the heart of the former, an expert system rules the identification-estimation-diagnostic checking cyclical process to end up with the predictions provided by the SARIMA model which best fits the data. We will present the connectionist approach as technically equivalent to the latter process and due to its, alas, lack of any conclusive existent algorithm able to identify both the optimal model and architecture for a given problem, the three most common models presently at use and 20 different architectures for each model will be examined. It seems natural that if a comparison is to be made in order to provide a straight answer as to whether or not a connectionist approach outperforms the univariate Box&Jenkins methodology, the benchmark should clearly be the set of time series analysed in the work Time Series Analysis. Forecasting and Control by G. E. Box and G. M. Jenkins. Series BJA through to BJG give a total of 1200 plus measures to evaluate and compare the predictive power for different models, architectures, prediction horizons and pre-processing transformations.     

多模块贝叶斯网络中推理的简化

多模块贝叶斯网络(MSBN)引入了模块化和面向对象思想,是复杂大系统建模的有力工具．目前,如何简化MSBN中局部和全局推理的时空复杂度已成为影响其应用的关键问题．首先分析了用于局部贝叶斯网络推理的两类经典算法的时空复杂度,证明了它们本质上的一致性,并给出了统一的理论解释;进而用实验证明了影响推理复杂度的决定性因素是网络模型相应导出图的导出宽度,并指出了可以精确推理的贝叶斯网络族．最后,分析了降低MSBN全局推理复杂度的可行性,给出了简化MSBN全局推理的指导性原则．     

Complex Probabilistic Modeling with Recursive Relational Bayesian Networks

A number of representation systems have been proposed that extend the purely propositional Bayesian network paradigm with representation tools for some types of first-order probabilistic dependencies. Examples of such systems are dynamic Bayesian networks and systems for knowledge based model construction. We can identify the representation of probabilistic relational models as a common well-defined semantic core of such systems.Recursive relational Bayesian networks (RRBNs) are a framework for the representation of probabilistic relational models. A main design goal for RRBNs is to achieve greatest possible expressiveness with as few elementary syntactic constructs as possible. The advantage of such an approach is that a system based on a small number of elementary constructs will be much more amenable to a thorough mathematical investigation of its semantic and algorithmic properties than a system based on a larger number of high-level constructs. In this paper we show that with RRBNs we have achieved our goal, by showing, first, how to solve within that framework a number of non-trivial representation problems. In the second part of the paper we show how to construct from a RRBN and a specific query, a standard Bayesian network in which the answer to the query can be computed with standard inference algorithms. Here the simplicity of the underlying representation framework greatly facilitates the development of simple algorithms and correctness proofs. As a result we obtain a construction algorithm that even for RRBNs that represent models for complex first-order and statistical dependencies generates standard Bayesian networks of size polynomial in the size of the domain given in a specific application instance.     

An Introduction to Variational Methods for Graphical Models

This paper presents a tutorial introduction to the use of variational methods for inference and learning in graphical models (Bayesian networks and Markov random fields). We present a number of examples of graphical models, including the QMR-DT database, the sigmoid belief network, the Boltzmann machine, and several variants of hidden Markov models, in which it is infeasible to run exact inference algorithms. We then introduce variational methods, which exploit laws of large numbers to transform the original graphical model into a simplified graphical model in which inference is efficient. Inference in the simpified model provides bounds on probabilities of interest in the original model. We describe a general framework for generating variational transformations based on convex duality. Finally we return to the examples and demonstrate how variational algorithms can be formulated in each case.     

Sequential decision-theoretic models and expert systems

Sequential decision models are an important component of expert systems since, in general, the cost of acquiring information is significant and there is a trade-off between the cost and the value of information. Many expert systems in various domains (business, engineering, medicine etc.), needing costly inputs that are not known until the system operates, have to face this problem. In the last decade the field of sequential decision models based on decision theory (sequential decision-theoretic models) have become more and more important due to both the continuous progress made by research in Bayesian networks and the availability of modern powerful tools for building Bayesian networks and for probability propagation. This paper provides readers (especially knowledge engineers and expert system designers) with a unified and integrated presentation of the disparate literature in the field of sequential decision-making based on decision theory, in order to improve comprehensibility and accessibility. Besides the presentation of the general theory, a view of sequential diagnosis as an instance of the general concept of sequential decision-theoretic models is also shown.     

A Bayesian method for learning belief networks that contain hidden variables

This paper presents a Bayesian method for computing the probability of a Bayesian belief-network structure from a database. In particular, the paper focuses on computing the probability of a belief-network structure that contains a hidden (latent) variable. A hidden variable represents a postulated entity that has not been directly measured. After reviewing related techniques, which previously were reported, this paper presents a new, more efficient method for handling hidden variables in belief networks.     

A method of sensor fault detection and identification

A method of Bayesian belief network (BBN)-based sensor fault detection and identification is presented. It is applicable to processes operating in transient or at steady-state. A single-sensor BBN model with adaptable nodes is used to handle cases in which process is in transient. The single-sensor BBN model is used as a building block to develop a multi-stage BBN model for all sensors in the process under consideration. In the context of BBN, conditional probability data represents correlation between process measurable variables. For a multi-stage BBN model, the conditional probability data should be available at each time instant during transient periods. This requires generating and processing a massive data bank that reduces computational efficiency. This paper presents a method that reduces the size of the required conditional probability data to one set. The method improves the computational efficiency without sacrificing detection and identification effectiveness. It is applicable to model- and data-driven techniques of generating conditional probability data. Therefore, there is no limitation on the source of process information. Through real-time operation and simulation of two processes, the application and performance of the proposed BBN method are shown. Detection and identification of different sensor fault types (bias, drift and noise) are presented. For one process, a first-principles model is used to generate the conditional probability data, while for the other, real-time process data (measurements) are used.