Exact maximum margin structure learning of Bayesian networks

Robert Peharz, Franz Pernkopf

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationProceedings of the 29th International Conference on Machine Learning, ICML 2012
Number of pages8
Publication statusPublished - 10 Oct 2012
Externally publishedYes
Event29th International Conference on Machine Learning (ICML 2012) - Edinburgh, United Kingdom
Duration: 26 Jun 20121 Jul 2012
Conference number: 29


Conference29th International Conference on Machine Learning (ICML 2012)
Abbreviated titleICML 2012
Country/TerritoryUnited Kingdom


Dive into the research topics of 'Exact maximum margin structure learning of Bayesian networks'. Together they form a unique fingerprint.

Cite this