Advances in Bayesian Network Learning using Integer Programming
This work addresses a specific optimization challenge in machine learning for researchers and practitioners in probabilistic modeling, but it appears incremental as it builds on existing integer programming approaches.
The paper tackles the problem of learning Bayesian networks from complete discrete data by formulating it as an integer program and introduces methods like cutting planes and a greedy algorithm to improve efficiency, resulting in dramatic improvements over earlier results.
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.