Integer Linear Programming for the Bayesian network structure learning problem

TY - JOUR

T1 - Integer Linear Programming for the Bayesian network structure learning problem

AU - Bartlett, Mark

AU - Cussens, James

PY - 2015/3/10

Y1 - 2015/3/10

N2 - Bayesian networks are a commonly used method of representing conditional probability relationships between a set of variables in the form of a directed acyclic graph (DAG). Determination of the DAG which best explains observed data is an NP-hard problem [1]. This problem can be stated as a constrained optimisation problem using Integer Linear Programming (ILP). This paper explores how the performance of ILP-based Bayesian network learning can be improved through ILP techniques and in particular through the addition of non-essential, implied constraints. There are exponentially many such constraints that can be added to the problem. This paper explores how these constraints may best be generated and added as needed. The results show that using these constraints in the best discovered configuration can lead to a significant improvement in performance and show significant improvement in speed using a state-of-the-art Bayesian network structure learner.

AB - Bayesian networks are a commonly used method of representing conditional probability relationships between a set of variables in the form of a directed acyclic graph (DAG). Determination of the DAG which best explains observed data is an NP-hard problem [1]. This problem can be stated as a constrained optimisation problem using Integer Linear Programming (ILP). This paper explores how the performance of ILP-based Bayesian network learning can be improved through ILP techniques and in particular through the addition of non-essential, implied constraints. There are exponentially many such constraints that can be added to the problem. This paper explores how these constraints may best be generated and added as needed. The results show that using these constraints in the best discovered configuration can lead to a significant improvement in performance and show significant improvement in speed using a state-of-the-art Bayesian network structure learner.

KW - Bayesian networks

KW - Constrained optimisation

KW - Cutting planes

KW - Integer Linear Programming

KW - Separation

UR - http://www.scopus.com/inward/record.url?scp=84924787425&partnerID=8YFLogxK

U2 - 10.1016/j.artint.2015.03.003

DO - 10.1016/j.artint.2015.03.003

M3 - Article

SN - 0004-3702

VL - 244

SP - 258

EP - 271

JO - Artificial Intelligence

JF - Artificial Intelligence

ER -