Advances in Bayesian Network Learning using Integer Programming

We consider the problem of learning Bayesian networks (BNs) from complete discrete data. This problem of discrete optimisation is formulated as an integer program (IP). We describe the various steps we have taken to allow efficient solving of this IP. These are (i) efficient search for cutting planes, (ii) a fast greedy algorithm to find high-scoring (perhaps not optimal) BNs and (iii) tightening the linear relaxation of the IP. After relating this BN learning problem to set covering and the multidimensional 0-1 knapsack problem, we present our empirical results. These show improvements, sometimes dramatic, over earlier results.

• Publication year

  2013

• Venue

  Conference on Uncertainty in Artificial Intelligence

• Publication date

  2013-08-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1309.6825
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Maximum Likelihood Pedigree Reconstruction Using Integer Linear Programming

  2013cited by this paper
• An Improved Admissible Heuristic for Learning Optimal Bayesian Networks

  2012cited by this paper
• Characteristic imsets for learning Bayesian network structure

  2012cited by this paper
• Bayesian network learning with cutting planes

  2011influential reference
• Properties of Bayesian Dirichlet Scores to Learn Bayesian Network Structures

  2010cited by this paper
• Learning Bayesian Network Structure using LP Relaxations

  2010influential reference
• Probabilistic Graphical Models: Principles and Techniques - Adaptive Computation and Machine Learning

  2009cited by this paper
• Bayesian network learning by compiling to weighted MAX-SAT

  2008cited by this paper
• Constraint integer programming

  2007cited by this paper
• A Simple Approach for Finding the Globally Optimal Bayesian Network Structure

  2006cited by this paper
• A Revised Implementation of the Reverse Search Vertex Enumeration Algorithm

  2000cited by this paper
• The Strongest Facets of the Acyclic Subgraph Polytope Are Unknown

  1996cited by this paper
• On the set covering polytope: I. All the facets with coefficients in {0, 1, 2}

  1986cited by this paper
• On the acyclic subgraph polytope

  1985cited by this paper
• Edmonds polytopes and a hierarchy of combinatorial problems

  1973cited by this paper
• Integer Programming

  1972cited by this paper

• Learning Bayesian Network Classifiers to Minimize the Class Variable Parameters

  2024cites this paper
• Improving Causal Bayesian Networks Using Expertise in Authoritative Medical Ontologies

  2023cites this paper
• Efficient Bayesian Network Structure Learning via Parameterized Local Search on Topological Orderings

  2021cites this paper
• Active Structure Learning of Bayesian Networks in an Observational Setting

  2021cites this paper
• Learning the structure of Bayesian networks with ancestral and/or heuristic partition

  2021cites this paper
• Temporal state change Bayesian networks for modeling of evolving multivariate state sequences: model, structure discovery and parameter estimation

  2021cites this paper
• Scalable Bayesian Network Structure Learning with Splines

  2021influential citation
• Improved Causal Models of Alzheimer's Disease

  2021cites this paper
• An Approach of Epistasis Detection Using Integer Linear Programming Optimizing Bayesian Network

  2021cites this paper
• Model Averaging Bayesian Network Classifier by Ensemble Learning

  2020cites this paper
• Capturing Causal Knowledge from Authoritative Medical Ontologies

  2020cites this paper
• A Score-and-Search Approach to Learning Bayesian Networks with Noisy-OR Relations

  2020cites this paper
• A Bayesian Approach for Estimating Causal Effects from Observational Data

  2020cites this paper
• Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks

  2020cites this paper
• A comparative analysis of Bayesian network structure learning algorithms applied to crime data

  2020cites this paper
• Learning All Credible Bayesian Network Structures for Model Averaging

  2020influential citation
• New data-driven approaches to improve probabilistic model structure learning

  2019cites this paper
• Optimization Models for Machine Learning: A Survey

  2019cites this paper
• Exact Learning Augmented Naive Bayes Classifier

  2019cites this paper
• MULTIREGRESSION DYNAMIC MODELS IN GROUP ANALYSIS

  2019cites this paper
• Integrating CBR with Data in Bayesian Networks for Decision Making in an Echelon Supply Chain Distribution Solution

  2019cites this paper
• On Structure Priors for Learning Bayesian Networks

  2019cites this paper
• The Intersection-Validation Method for Evaluating Bayesian Network Structure Learning Without Ground Truth

  2019cites this paper
• Bayesian network models for incomplete and dynamic data

  2019influential citation
• Counting and Sampling Directed Acyclic Graphs for Learning Bayesian Networks

  2019cites this paper
• An Experimental Study of Prior Dependence in Bayesian Network Structure Learning

  2019cites this paper
• Réseau bayésien dynamique étiqueté : cadre et apprentissage de structure pour application aux réseaux écologiques

  2019cites this paper
• Optimizing Regularized Cholesky Score for Order-Based Learning of Bayesian Networks

  2019cites this paper
• Integer Programming for Learning Directed Acyclic Graphs from Continuous Data

  2019cites this paper
• A group analysis using the Multiregression Dynamic Models for fMRI networked time series

  2019cites this paper
• An Order-based Algorithm for Learning Structure of Bayesian Networks

  2018influential citation
• Exact Bayesian learning of Partition Directed Acyclic Graphs

  2018cites this paper
• Finding All Bayesian Network Structures within a Factor of Optimal

  2018influential citation
• Intersection-Validation: A Method for Evaluating Structure Learning without Ground Truth

  2018cites this paper
• An Experimental Analysis of Anytime Algorithms for Bayesian Network Structure Learning

  2017influential citation
• Studying the effective brain connectivity using multiregression dynamic models

  2017cites this paper
• Probabilistic Graphical Model Structure Learning: Application to Multi-Label Classification. (Apprentissage de Structure de Modèles Graphiques Probabilistes: Application à la Classification Multi-Label)

  2017cites this paper
• Towards using the chordal graph polytope in learning decomposable models

  2017cites this paper
• Efficient learning of Bayesian networks with bounded tree-width

  2017cites this paper
• Learning Bayesian network structures under incremental construction curricula

  2017cites this paper
• Integer Linear Programming for the Bayesian network structure learning problem

  2017cites this paper
• Empirical hardness of finding optimal Bayesian network structures: algorithm selection and runtime prediction

  2017cites this paper
• The role of local partial independence in learning of Bayesian networks

  2016cites this paper
• Learning Bayesian Networks with Incomplete Data by Augmentation

  2016cites this paper
• Joint Analysis of Multiple Algorithms and Performance Measures

  2016cites this paper
• Bayesian network structure training based on a game of learning automata

  2016cites this paper
• Scale Up Bayesian Network Learning

  2016cites this paper
• BNC-PSO: structure learning of Bayesian networks by Particle Swarm Optimization

  2016cites this paper
• The Chordal Graph Polytope for Learning Decomposable Models

  2016cites this paper
• Structure Discovery in Bayesian Networks by Sampling Partial Orders

  2016cites this paper
• Learning Bayesian Networks without Assuming Missing at Random

  2016cites this paper
• Learning Bayesian Networks with Bounded Tree-width via Guided Search

  2016cites this paper
• Learning Bayesian Network Structures with Non-Decomposable Scores

  2016cites this paper
• Combinatorial Algorithms with Applications in Learning Graphical Models

  2016influential citation
• Semi-Supervised Learning for Electronic Phenotyping in Support of Precision Medicine

  2016cites this paper
• Structure Discovery in Bayesian Networks: Algorithms and Applications

  2016influential citation
• Structure learning of context-specific graphical models

  2016cites this paper
• Structure Learning in Graphical Modeling

  2016cites this paper
• Estimating relationships and relatedness from dense genome-wide data

  2016cites this paper
• Machine Learning of Bayesian Networks Using Constraint Programming

  2015cites this paper
• Integration of AI and OR Techniques in Constraint Programming: 12th International Conference, CPAIOR 2015, Barcelona, Spain, May 18-22, 2015, Proceedings

  2015cites this paper
• MaxSAT-Based Cutting Planes for Learning Graphical Models

  2015cites this paper
• Scale Up Bayesian Networks Learning Dissertation Proposal

  2015cites this paper
• Statistical Tests for Joint Analysis of Performance Measures

  2015cites this paper
• Anchored Discrete Factor Analysis

  2015influential citation
• Bayesian Networks of Bounded Treewidth: A Performance Analysis

  2015cites this paper
• Learning discrete decomposable graphical models via constraint optimization

  2015cites this paper
• Learning Optimal Chain Graphs with Answer Set Programming

  2015cites this paper
• Curriculum Learning of Bayesian Network Structures

  2015cites this paper
• Structure Learning in Bayesian Networks of a Moderate Size by Efficient Sampling

  2015cites this paper
• Averaged Extended Tree Augmented Naive Classifier

  2015cites this paper
• Polyhedral aspects of score equivalence in Bayesian network structure learning

  2015cites this paper
• How matroids occur in the context of learning Bayesian network structure

  2015cites this paper
• Tractable Bayesian Network Structure Learning with Bounded Vertex Cover Number

  2015influential citation
• Searching Multiregression Dynamic Models of Resting-State fMRI Networks Using Integer Programming

  2015cites this paper
• Re-implementing and Extending a Hybrid SAT-IP Approach to Maximum Satisfiability

  2015cites this paper
• Impact of Learning Strategies on the Quality of Bayesian Networks: An Empirical Evaluation

  2015cites this paper
• Multi-classifiers of Small Treewidth

  2015cites this paper
• Survey of contemporary Bayesian Network Structure Learning methods

  2015cites this paper
• Toward a Multisubject Analysis of Neural Connectivity

  2014cites this paper
• A hybrid algorithm for Bayesian network structure learning with application to multi-label learning

  2014cites this paper
• Predicting the Hardness of Learning Bayesian Networks

  2014cites this paper
• Finding Optimal Bayesian Network Structures with Constraints Learned from Data

  2014cites this paper
• Exact estimation of multiple directed acyclic graphs

  2014influential citation
• Learning Optimal Bounded Treewidth Bayesian Networks via Maximum Satisfiability

  2014cites this paper
• Learning Chordal Markov Networks by Dynamic Programming

  2014influential citation
• Learning Bounded Tree-width Bayesian Networks using Integer Linear Programming

  2014cites this paper
• Improved maximum likelihood reconstruction of complex multi-generational pedigrees.

  2014cites this paper
• Structure Learning of Bayesian Networks with Bounded Treewidth Using Mixed Integer Linear Programming

  2014cites this paper
• Integer Programming for Bayesian Network Structure Learning

  2014influential citation
• Marginal Pseudo-Likelihood Learning of Markov Network structures

  2014cites this paper
• Min-BDeu and Max-BDeu Scores for Learning Bayesian Networks

  2014cites this paper
• PMCE: efficient inference of expressive models of cancer evolution with high prognostic power

  2014influential citation
• Bayesian Networks Structure Learning Second Exam Literature Review

  2014cites this paper
• Estimating Causal Structure Using Conditional DAG Models

  2014cites this paper
• Advances in Learning Bayesian Networks of Bounded Treewidth

  2014cites this paper
• Finding the k-best Equivalence Classes of Bayesian Network Structures for Model Averaging

  2014cites this paper
• QuickLexSort: An efficient algorithm for lexicographically sorting nested restrictions of a database

  2013cites this paper
• Learning Chordal Markov Networks by Constraint Satisfaction

  2013cites this paper
• Learning Bayesian Network Classifiers to Minimize Class Variable Parameters

  year unknowncites this paper