Exact Maximum Margin Structure Learning of Bayesian Networks

Recently, there has been much interest in finding globally optimal Bayesian network structures. These techniques were developed for generative scores and can not be directly extended to discriminative scores, as desired for classification. In this paper, we propose an exact method for finding network structures maximizing the probabilistic soft margin, a successfully applied discriminative score. Our method is based on branch-and-bound techniques within a linear programming framework and maintains an any-time solution, together with worst-case sub-optimality bounds. We apply a set of order constraints for enforcing the network structure to be acyclic, which allows a compact problem representation and the use of general-purpose optimization techniques. In classification experiments, our methods clearly outperform generatively trained network structures and compete with support vector machines.

• Publication year

  2012

• Venue

  International Conference on Machine Learning

• Publication date

  2012-06-26

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1206.6431
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Stochastic margin-based structure learning of Bayesian network classifiers

  2013cited by this paper
• Maximum Margin Bayesian Network Classifiers

  2012influential reference
• Efficient Structure Learning of Bayesian Networks using Constraints

  2011cited by this paper
• LIBSVM: A library for support vector machines

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

  2011influential reference
• Maximum margin structure learning of Bayesian network classifiers

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

  2010influential reference
• Maximum likelihood pedigree reconstruction using integer programming

  2010cited by this paper
• Structure learning of Bayesian networks using constraints

  2009cited by this paper
• Exact Structure Discovery in Bayesian Networks with Less Space

  2009cited by this paper
• Probabilistic Graphical Models: Principles and Techniques - Adaptive Computation and Machine Learning

  2009cited by this paper
• Learning Bayesian networks

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

  2006cited by this paper
• Maximum Margin Bayesian Networks

  2005influential reference
• Exact Bayesian Structure Discovery in Bayesian Networks

  2004cited by this paper
• Bayesian Network Classifiers

  1997cited by this paper
• Learning Bayesian networks: The combination of knowledge and statistical data

  1994cited by this paper
• Learning Bayesian Networks is

  1994cited by this paper
• A Construction of Bayesian Networks from Databases Based on an MDL Principle

  1993influential reference
• Multi-Interval Discretization of Continuous-Valued Attributes for Classification Learning

  1993cited by this paper
• A Bayesian method for the induction of probabilistic networks from data

  1992cited by this paper
• Probabilistic reasoning in intelligent systems: Networks of plausible inference

  1991cited by this paper
• Theory Refinement on Bayesian Networks

  1991cited by this paper
• Modeling By Shortest Data Description*

  1978cited by this paper

• Effective Bayesian Causal Inference via Structural Marginalisation and Autoregressive Orders

  2024cites this paper
• Learning Bayesian Networks with the Saiyan Algorithm

  2020cites this paper
• Differentiable TAN Structure Learning for Bayesian Network Classifiers

  2020cites this paper
• Bayesian Network Structure Learning with Integer Programming: Polytopes, Facets and Complexity (Extended Abstract)

  2017cites this paper
• Bayesian Network Structure Learning with Integer Programming: Polytopes, Facets and Complexity

  2016cites this paper
• Learning Discriminative Bayesian Networks from High-Dimensional Continuous Neuroimaging Data

  2016cites this paper
• Statistical learning of high-dimensional directed acyclic graphical models

  2015cites this paper
• Learning Discriminative Bayesian Networks from High-dimensional Continuous Neuroimaging Data

  2015influential citation
• Structure Learning of Bayesian Networks with Bounded Treewidth Using Mixed Integer Linear Programming

  2014cites this paper
• Introduction to Probabilistic Graphical Models

  2014cites this paper
• Stochastic margin-based structure learning of Bayesian network classifiers

  2013cites this paper
• On Bayesian Network Classifiers with Reduced Precision Parameters

  2012cites this paper