Learning Bayesian network structures by searching for the best ordering with genetic algorithms
IEEE Transactions on Systems Man and Cybernetics - Part A Systems and HumansPublished 1 July 1996
Pedro Larrañaga, C.M.H. Kuijpers, R.H. Murga, Y. Yurramendi
Citations268
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new methodology for inducing Bayesian network structures from a database of cases based on searching for the best ordering of the system variables by means of genetic algorithms using genetic operators developed for the traveling salesman problem.
Abstract
Presents a new methodology for inducing Bayesian network structures from a database of cases. The methodology is based on searching for the best ordering of the system variables by means of genetic algorithms. Since this problem of finding an optimal ordering of variables resembles the traveling salesman problem, the authors use genetic operators that were developed for the latter problem. The quality of a variable ordering is evaluated with the structure-learning algorithm K2. The authors present empirical results that were obtained with a simulation of the ALARM network.
Keywords
Computer ScienceEngineering
IEEE Transactions on Automatic ControlA new look at the statistical model identification
50,732 Citations1974Hirotugu Akaike
Choice Reviews OnlineGenetic algorithms in search, optimization, and machine learning
49,278 Citations1989
This book brings together the computer techniques, mathematical tools, and research results that will enable both students and practitioners to apply genetic algorithms to problems in many fields.
Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference
16,927 Citations1988Judea Pearl
The author provides a coherent explication of probability as a language for reasoning with partial belief and offers a unifying perspective on other AI approaches to uncertainty, such as the Dempster-Shafer formalism, truth maintenance systems, and nonmonotonic logic.
Artificial intelligenceGenetic Algorithms + Data Structures = Evolution Programs
11,598 Citations1992Zbigniew Michalewicz
Handbook of Genetic Algorithms
7,308 Citations1991Lawrence Davis
AutomaticaModeling by shortest data description
5,944 Citations1978J. Rissanen
The number of digits it takes to write down an observed sequence x1,...,xN of a time series depends on the model with its parameters that one assumes to have generated the observed data.
Machine LearningA Bayesian Method for the Induction of Probabilistic Networks from Data
3,525 Citations1992Gregory F. Cooper, Edward H. Herskovits
This paper presents a Bayesian method for constructing probabilistic networks from databases, focusing on constructing Bayesian belief networks, and extends the basic method to handle missing data and hidden variables.
Machine LearningLearning Bayesian Networks: The Combination of Knowledge and Statistical Data
3,242 Citations1995David Heckerman, Dan Geiger +1 more
A methodology for assessing informative priors needed for learning Bayesian networks from a combination of prior knowledge and statistical data is developed and how to compute the relative posterior probabilities of network structures given data is shown.
IEEE Transactions on Information TheoryApproximating discrete probability distributions with dependence trees
2,640 Citations1968Chee Lap Chow, C. Liu
It is shown that the procedure derived in this paper yields an approximation of a minimum difference in information when applied to empirical observations from an unknown distribution of tree dependence, and the procedure is the maximum-likelihood estimate of the distribution.
Introduction to Bayesian Networks
2,585 Citations2019
Machine LearningA Bayesian method for the induction of probabilistic networks from data
2,344 Citations1992Gregory F. Cooper, Edward H. Herskovits
This paper presents a Bayesian method for constructing probabilistic networks from databases, focusing on constructing Bayesian belief networks, and extends the basic method to handle missing data and hidden variables.
IEEE Transactions on Neural NetworksConvergence analysis of canonical genetic algorithms
1,456 Citations1994Günter Rudolph
This paper analyzes the convergence properties of the canonical genetic algorithm with mutation, crossover and proportional reproduction applied to static optimization problems and shows variants of CGA's that always maintain the best solution in the population are shown to converge to the global optimum due to the irreducibility property of the underlying original nonconvergent CGA.
Computational IntelligenceLEARNING BAYESIAN BELIEF NETWORKS: AN APPROACH BASED ON THE MDL PRINCIPLE
773 Citations1994Wai Lam, Fahiem Bacchus
A new approach for learning Bayesian belief networks from raw data is presented, based on Rissanen's minimal description length (MDL) principle, which can learn unrestricted multiply‐connected belief networks and allows for trade off accuracy and complexity in the learned model.
Lecture notes in medical informaticsThe ALARM Monitoring System: A Case Study with two Probabilistic Inference Techniques for Belief Networks
741 Citations1989Ingo A. Beinlich, Henri J. Suermondt +2 more
Two algorithms were applied to this belief network: a message-passing algorithm by Pearl for probability updating in multiply connected networks using the method of conditioning and the Lauritzen-Spiegelhalter algorithm for local probability computations on graphical structures.
International Joint Conference on Artificial IntelligenceApplying adaptive algorithms to epistatic domains
646 Citations1985Lawrence Davis
New techniques for applying adaptive algorithms to epistatic domains, while retaining some of the strength of Holland's convergence proof are described, for two-dimensional bin-packing problems and graph coloring problems.
TechnometricsProbabilistic Reasoning in Expert Systems, Theory and Algorithms
616 Citations1992Peter M. Jones, Richard E. Neapolitan
This text is a reprint of the seminal 1989 book Probabilistic Reasoning in Expert systems: Theory and Algorithms, which helped serve to create the field the authors now call Bayesian networks and provides an insightful comparison of the two most prominent approaches to probability.
IEEE Transactions on Pattern Analysis and Machine IntelligenceStructure learning of Bayesian networks by genetic algorithms: a performance analysis of control parameters
398 Citations1996Pedro Larrañaga, M. Poza +3 more
This work tackles the problem of the search for the best Bayesian network structure, given a database of cases, using the genetic algorithm philosophy for searching among alternative structures, by assuming an ordering between the nodes of the network structures.
Lecture notes in computer scienceParallel genetic algorithms, population genetics and combinatorial optimization
369 Citations1991Heinz Mühlenbein
This paper has applied ASPARAGOS to an important combinatorial optimization problem, the quadratic assignment problem, and found a new optimum for the largest published problem.
Elsevier eBooksLearning Bayesian Networks: The Combination of Knowledge and Statistical Data
259 Citations1994David Heckerman, Dan Geiger +1 more
Lecture notes in computer scienceGlobal convergence of genetic algorithms: A markov chain analysis
229 Citations1991A. E. Eiben, Emile Aarts +1 more
An abstract stochastic algorithm is set up that generalizes and unifies genetic algorithms and simulated annealing, such that any GA or SA algorithm at hand is an instance of the authors' abstract algorithm.
Learning Bayesian Networks: Search Methods and Experimental Results
214 Citations1995Max Chickering, Dan Geiger +1 more
A metric for computing the relative posterior probability of a network structure given data developed by Heckerman et al. (1994a,b,c) has a property useful for inferring causation from data and is described.
International Journal of Approximate ReasoningConstruction of Bayesian network structures from data: A brief survey and an efficient algorithm
174 Citations1995Moninder Singh, Marco Valtorta
This work presents an algorithm that integrates CI tests to generate an ordering on the nodes from the database, which is then used to recover the underlying Bayesian network structure using a non-CI-test-based method.
Biological CyberneticsThe “molecular” traveling salesman
150 Citations1990Wolfgang Banzhaf
A method for optimization of NP-problems motivated by natural evolution is considered and the concept of isolated evolution is introduced to maintain a certain degree of variance in the population.
Uncertainty in Artificial IntelligenceA Construction of Bayesian Networks from Databases Based on an MDL Principle
149 Citations1993Joe Suzuki
The extended version of the algorithm of Chow and Liu in that the learning algorithm selects the model in the range where the dependencies among the attributes are represented by some general plural number of trees.
Computer-based probabilistic-network construction
117 Citations1992Edward H. Herskovits
This dissertation demonstrates that nonparametric, efficient, computer-based algorithms for determining the important associations among variables in a domain are conceptually feasible, robust to noise, computationally efficient, theoretically sound, and that they generate models that can classify new cases accurately.
Elsevier eBooksProperties of Bayesian Belief Network Learning Algorithms
105 Citations1994Remco Bouckaert
Experimental results suggest that for learning probabilities of belief networks smoothing is helpful, which justifies the use of search heuristics based on the Bayesian measure of Cooper and Herskovits and a minimum description length measure.
Uncertainty in Artificial IntelligenceAn Algorithm for the Construction of Bayesian Network Structures from Data
99 Citations1993Moninder Singh, Marco Valtorta
An algorithm is presented that integrates two approaches to the construction of Bayesian belief network structures from data - CI tests are used to generate an ordering on the nodes from the database which is then used to recover the underlying Bayesian network structure using a non CI based method.
Constructor: a system for the induction of probabilistic models
70 Citations1990Robert Fung, Stuart L. Crawford
The probabilistic network technology is a knowledge-based technique which focuses on reasoning under uncertainty and is finding increasing application in fields such as medical diagnosis, machine vision, military situation assessment, petroleum exploration, and information retrieval.
Uncertainty in Artificial IntelligenceUsing Causal Information and Local Measures to Learn Bayesian Networks
65 Citations1993Wai Lam, Fahiem Bacchus
A new local way of computing the description length is presented, which allows for significant improvements in the search algorithm and opens the door for local refinement of an existent network.
Machine intelligence and pattern recognitionAutomated construction of sparse Bayesian networks from unstructured probabilistic models and domain information
51 Citations1990Sampath Srinivas, Stuart Russell +1 more
An algorithm for automated construction of a sparse Bayesian network given an unstructured probabilistic model and causal domain information from an expert has been developed and implemented to obtain a network that explicitly reveals as much information regarding conditional independence as possible.
Lecture notes in statisticsLearning Bayesian Networks Using Feature Selection
47 Citations1996Gregory Provan, Moninder Singh
The new approach selects a subset of features that maximizes predictive accuracy prior to the network learning phase, and generates networks that are computationally simpler to evaluate and display predictive accuracy comparable to that of Bayesian networks which model all attributes.
Lecture notes in statisticsStrategies for Graphical Model Selection
45 Citations1994David Madigan, Adrian E. Raftery +3 more
This work considers the problem of model selection for Bayesian graphical models, and embeds it in the larger context of accounting for model uncertainty, and examines the predictive performance of two recently proposed model averaging schemes.
International Journal of Approximate ReasoningThe recovery of causal poly-trees from statistical data
42 Citations1988
Information Processing LettersUsing reliability analysis to estimate the number of generations to convergence in genetic algorithms
36 Citations1993Uday K. Chakraborty, Debabrata Ghosh Dastidar
A stochastic reliability model for the haploid, binary, fixed-length genetic algorithm is presented and empirical evidence is provided.
Lecture notes in statisticsStructure Learning of Bayesian Networks by Hybrid Genetic Algorithms
33 Citations1996Pedro Larrañaga, R.H. Murga +2 more
This paper demonstrates how genetic algorithms can be used to discover the structure of a Bayesian network from a given database with cases by applying four different types of genetic algorithms to simulations of the ALARM Network.
Journal of Applied StatisticsSTENO:an expert system for medical diagnosis based on graphical models and model search
27 Citations1991Lars Rude Andersen, Jens Herman Krebs +1 more
The theoretical basis for and the implementation of an expert system based on causal probabilistic networks is described, which contains facilities for storing knowledge and propagating new knowledge, and mechanisms for building the knowledge base by semi-automated analysis of a large sparse contingency table.
Uncertainty in Artificial IntelligenceOptimizing Causal Orderings for Generating DAGs from Data
26 Citations1992Remco Bouckaert
An algorithm for generating the structure of a directed acyclic graph from data using the notion of causal input lists is presented and the resulting DAG is a minimal I-map.
IEEE Transactions on Systems Man and Cybernetics - Part A Systems and HumansA new method for evaluating weapon systems using fuzzy set theory
23 Citations1996Shyi‐Ming Chen
This paper presents a new method for evaluating weapon systems using fuzzy set theory, which is more flexible than the one presented in Mon et al. (1994) due to the fact that it allows each item of criteria to have a different weight represented by a triangular fuzzy number.
Lecture notes in computer scienceLearning with CASTLE
16 Citations1991Silvia Acid, Luis M. de Campos +3 more
The learning algorithms implemented in CASTLE, (Causal Structures From Inductive Learning), are described, to learn about causal structures from examples.
Lecture notes in statisticsModel Selection for Diagnosis and Treatment Using Temporal Influence Diagrams
14 Citations1994Gregory Provan
The model-selection process for a temporal influence diagram formalization of the diagnosis and treatment of acute abdominal pain and the choice of most appropriate stochastic process to model the temporal evolution of the system is described.
Analyzing multi-agent systems with probabilistic model checking approach
9 Citations2012Songzheng Song, Jianye Hao +4 more
This work proposes to apply probabilistic model checking to analyze multi-agent systems to guarantee the correctness of their behaviors due to the complex nature of the autonomous agents, especially when they have stochastic characteristics.