Advances in Bayesian Network Learning using Integer Programming

Mark Bartlett; James Cussens

Advances in Bayesian Network Learning using Integer Programming

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English
Title of host publication	Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence (UAI 2013)
Publisher	AUAI Press
Pages	182-191
Number of pages	10
Publication status	Published - 2013

Access to Document

http://auai.org/uai2013/prints/papers/18.pdf

Cite this

@inproceedings{0167e5152c484b4d971d4b2deed4719d,

title = "Advances in Bayesian Network Learning using Integer Programming",

abstract = " 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.",

author = "Mark Bartlett and James Cussens",

year = "2013",

language = "English",

pages = "182--191",

booktitle = "Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence (UAI 2013)",

publisher = "AUAI Press",

}

TY - GEN

T1 - Advances in Bayesian Network Learning using Integer Programming

AU - Bartlett, Mark

AU - Cussens, James

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

M3 - Conference contribution

SP - 182

EP - 191

BT - Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence (UAI 2013)

PB - AUAI Press

ER -