arXiv (Cornell University) · 2013 · 70 citations · 9 references
ComputingComputer ScienceMathematicsAlgorithmsDiscrete MathematicsMachine LearningBayesian LearningCombinatorial OptimizationDiscrete OptimizationGreedy AlgorithmsInteger ProgrammingOptimization For Machine Learning0-1 Knapsack ProblemBayesian Network Structure LearningBayesian NetworksCutting PlanesGreedy HeuristicsInteger Programming RelaxationsKnapsack ProblemsSet Covering Problem
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.
9
Learning Bayesian Network Structure using LP Relaxations
Tommi Jaakkola, David Sontag, Amir Globerson et al. · DSpace@MIT (Massachusetts Institute of Technology) · 2010 · 181 citations · Full text
Bayesian network learning with cutting planes
James Cussens · arXiv (Cornell University) · 2012 · 168 citations · Full text
On the acyclic subgraph polytope
Martin Grötschel, Michael Jünger, Gerhard Reinelt · Mathematical Programming · 1985 · 112 citations