Learning Bayesian networks from data: An information-theory based approach
Artificial IntelligencePublished 1 May 2002
Jie Cheng, Russell Greiner, Jonathan Kelly, David Bell, Weiru Liu
Citations803
SJR quartileQ1
SJR score1.84
SNIP3.30
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
Algorithms that use an information-theoretic analysis to learn Bayesian network structures from data, requiring only polynomial numbers of conditional independence tests in typical cases are provided.
Abstract
This paper provides algorithms that use an information-theoretic analysis to learn Bayesian network structures from data. Based on our three-phase learning framework, we develop efficient algorithms that can effectively learn Bayesian networks, requiring only polynomial numbers of conditional independence (CI) tests in typical cases. We provide precise conditions that specify when these algorithms are guaranteed to be correct as well as empirical evidence (from real world applications and simulation tests) that demonstrates that these systems work efficiently and reliably in practice.
Keywords
Computer ScienceDecision Sciences
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.
Lecture notes in statisticsCausation, Prediction, and Search
4,740 Citations1993Peter Spirtes, Clark Glymour +1 more
The authors axiomatize the connection between causal structure and probabilistic independence, explore several varieties of causal indistinguishability, formulate a theory of manipulation, and develop asymptotically reliable procedures for searching over equivalence classes of causal models.
Machine LearningBayesian Network Classifiers
4,738 Citations1997Nir Friedman, Dan Geiger +1 more
Tree Augmented Naive Bayes (TAN) is single out, which outperforms naive Bayes, yet at the same time maintains the computational simplicity and robustness that characterize naive Baye.
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.
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.
Machine LearningLearning Bayesian networks: The combination of knowledge and statistical data
2,043 Citations1995David Heckerman, Dan Geiger +1 more
It is shown that likelihood equivalence when combined with previously made assumptions implies that the user's priors for network parameters can be encoded in a single Bayesian network for the next case to be seen—aprior network—and a single measure of confidence for that network.
Journal of the American Statistical AssociationModel Selection and Accounting for Model Uncertainty in Graphical Models Using Occam's Window
1,234 Citations1994David Madigan, Adrian E. Raftery
ACM eBooksEquivalence and Synthesis of Causal Models
997 Citations2022TS Verma, Judea Pearl
The canonical representation presented here yields an efficient algorithm for determining when two embedded causal models reflect the same dependency information, which leads to a model theoretic definition of causation in terms of statistical dependencies.
Social Science Computer ReviewAn Algorithm for Fast Recovery of Sparse Causal Graphs
946 Citations1991Peter Spirtes, Clark Glymour
An asymptotically correct algorithm whose complexity for fixed graph connectivity increases polynomially in the number of vertices, and may in practice recover sparse graphs with several hundred variables.
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.
Machine intelligence and pattern recognitionPropagating Uncertainty in Bayesian Networks by Probabilistic Logic Sampling
552 Citations1988Max Henrion
Probabilistic logic sampling is a new scheme employing stochastic simulation which can make probabilistic inferences in large, multiply connected networks, with an arbitrary degree of precision controlled by the sample size.
Journal of Artificial Intelligence ResearchOperations for Learning with Graphical Models
538 Citations1994Wray Buntine
The main original contributions here are the decompositiontechniques and the demonstration that graphical models provide a framework for understanding and developing complex learning algorithms.
IEEE Transactions on Knowledge and Data EngineeringA guide to the literature on learning probabilistic networks from data
477 Citations1996Wray Buntine
Learning Bayesian Networks with Local Structure
400 Citations1998Nir Friedman, Moisés Goldszmidt
A novel addition to the known methods for learning Bayesian networks from data that improves the quality of the learned networks and indicates that learning curves characterizing the procedure that exploits the local structure converge faster than these of the standard procedure.
Comparing Bayesian network classifiers
341 Citations1999Jie Cheng, Russell Greiner
Learning equivalence classes of Bayesian network structures
303 Citations1996David Maxwell Chickering
This work presents the general formulation of a search space for which the states of the search correspond to equivalence classes of structures, and compares greedy search performance in the proposed search space to greedy search performance in a search space for which the states correspond to individual Bayesian network structures.
Lecture notes in computer scienceLearning Bayesian Belief Network Classifiers: Algorithms and System
287 Citations2001Jie Cheng, Russell Greiner
The results show that the proposed BN and Bayes multinet classifiers are competitive with (or superior to) the best known classifiers; and that the computational time for learning and using these classifiers is relatively small, arguing that BN-based classifiers deserve more attention in the data mining community.
Learning belief networks from data
240 Citations1997Jie Cheng, David Bell +1 more
Algorithms that use an information-theoretic analysis to learn Bayesian network structures from data, requiring only polynomial numbers of conditional independence tests in typical cases are provided.
BiometrikaGraphical and Recursive Models for Contingency Tables
223 Citations1983Nanny Wermuth, Steffen L. Lauritzen
arXiv (Cornell University)Strong Completeness and Faithfulness in Bayesian Networks
199 Citations2013Christopher Meek
It is shown that in a strong measure-theoretic sense almost all discrete distributions for a given network structure are faithful; i.e. the independence facts true of the distribution are all and only those entailed by the network structure.
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.
Knowledge Discovery and Data MiningLearning Bayesian networks with discrete variables from data
164 Citations1995Peter Spirtes, Christopher Meek
This paper describes a new greedy Bayesian search algorithm (GBPS) and a new "combined" algorithm PC+GBPS for learning Bayesian networks.
Computational Statistics
148 Citations1992Dodge, Yadolah, Whittaker, Joe
A hybrid anytime algorithm for the construction of causal models from sparse data
94 Citations1999Denver Dash, Marek J. Drużdżel
A hybrid constraint-based/ Bayesian algorithm for learning causal networks in the presence of sparse data is presented and found to consistently outperform two variations of greedy search with restarts.
The Knowledge Engineering ReviewLearning probabilistic networks
89 Citations1999Paul J. Krause
This paper shows how data can be used to revise initial estimates of the parameters of a model, and how the structure of the model can be revised as data is obtained, and an introduction to probability theory and probabilistic graphical models.
Research Showcase @ Carnegie Mellon University (Carnegie Mellon University)Causality From Probability
81 Citations2018Peter Spirtes, Clark Glymour +1 more
ACM Computing SurveysEfficient reasoning
76 Citations2001Russell Greiner, Christian J. Darken +1 more
This survey formalizes these hardness results, in the context of both logic- and probability-based reasoning, then overviews the techniques now used to address, or at least side-step, this dilemma.
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.
arXiv (Cornell University)Learning Bayesian Nets that Perform Well
55 Citations2013Russell Greiner, Adam J. Grove +1 more
This paper considers the challenge of computing the BN whose performance -- read "accuracy over the distribution of queries" -- is optimal, and shows that many aspects of this learning task are more difficult than the corresponding subtasks in the standard model.
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.
National Conference on Artificial IntelligenceLearning Bayesian networks from incomplete data
48 Citations1997Moninder Singh
This work presents a principled approach to learn both the Bayesian network structure as well as the conditional probabilities from incomplete data, and presents an iterative method that uses a combination of Expectation-Maximization and Imputation techniques.
arXiv (Cornell University)An Algorithm for Finding Minimum d-Separating Sets in Belief Networks
45 Citations2013Silvia Acid, Luis M. de Campos
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.
Selecting Models from Data: Artificial Intelligence and Statistics IV
31 Citations1994Peter Cheeseman, R. Wayne Oldford
Learning Belief Networks from Data: An Information Theory Based Approach
17 Citations2007Jie Cheng, David A. Bell +1 more
Heuristic greedy search algorithms for latent variable models
14 Citations1997Peter Spirtes, Thomas Richardson +2 more
A Bayesian network consists of a directed acyclic graph (DAG or belief-network structure) and a set of parameters for the DAG, which can be used to represent both causal hypotheses and sets of probability distributions.