Dr Mark Bartlett m.bartlett3@rgu.ac.uk
Lecturer
Integer linear programming for the Bayesian network structure learning problem.
Bartlett, Mark; Cussens, James
Authors
James Cussens
Abstract
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. 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.
Citation
BARTLETT, M. and CUSSENS, J. 2017. Integer linear programming for the Bayesian network structure learning problem. Artificial intelligence [online], 244, pages 258-271. Available from: https://doi.org/10.1016/j.artint.2015.03.003
Journal Article Type | Article |
---|---|
Acceptance Date | Mar 7, 2015 |
Online Publication Date | Mar 10, 2015 |
Publication Date | Mar 17, 2017 |
Deposit Date | Jan 20, 2020 |
Publicly Available Date | Jan 20, 2020 |
Journal | Artificial Intelligence |
Print ISSN | 0004-3702 |
Electronic ISSN | 1872-7921 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 244 |
Pages | 258-271 |
DOI | https://doi.org/10.1016/j.artint.2015.03.003 |
Keywords | Bayesian networks; Integer linear programming; Constrained optimisation; Cutting planes; Separation |
Public URL | https://rgu-repository.worktribe.com/output/816263 |
Files
BARTLETT 2017 Integer linear
(448 Kb)
PDF
Publisher Licence URL
https://creativecommons.org/licenses/by-nc-nd/4.0/
You might also like
Analysing the fitness landscape rotation for combinatorial optimisation.
(2022)
Conference Proceeding
Multi-criteria material selection for casing pipe in shale gas wells application.
(2022)
Journal Article
Towards the landscape rotation as a perturbation strategy on the quadratic assignment problem.
(2021)
Conference Proceeding
Downloadable Citations
About OpenAIR@RGU
Administrator e-mail: publications@rgu.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search