Learning Bounded Tree-width Bayesian Networks using Integer Linear Programming

Pekka Parviainen, Hossein Shahrabi Farahani, Jens Lagergren
Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, PMLR 33:751-759, 2014.

Abstract

In many applications one wants to compute conditional probabilities given a Bayesian network. This inference problem is NP-hard in general but becomes tractable when the network has low tree-width. Since the inference problem is common in many application areas, we provide a practical algorithm for learning bounded tree-width Bayesian networks. We cast this problem as an integer linear program (ILP). The program can be solved by an anytime algorithm which provides upper bounds to assess the quality of the found solutions. A key component of our program is a novel integer linear formulation for bounding tree-width of a graph. Our tests clearly indicate that our approach works in practice, as our implementation was able to find an optimal or nearly optimal network for most of the data sets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v33-parviainen14, title = {{Learning Bounded Tree-width Bayesian Networks using Integer Linear Programming}}, author = {Parviainen, Pekka and Shahrabi Farahani, Hossein and Lagergren, Jens}, booktitle = {Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics}, pages = {751--759}, year = {2014}, editor = {Kaski, Samuel and Corander, Jukka}, volume = {33}, series = {Proceedings of Machine Learning Research}, address = {Reykjavik, Iceland}, month = {22--25 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v33/parviainen14.pdf}, url = {https://proceedings.mlr.press/v33/parviainen14.html}, abstract = {In many applications one wants to compute conditional probabilities given a Bayesian network. This inference problem is NP-hard in general but becomes tractable when the network has low tree-width. Since the inference problem is common in many application areas, we provide a practical algorithm for learning bounded tree-width Bayesian networks. We cast this problem as an integer linear program (ILP). The program can be solved by an anytime algorithm which provides upper bounds to assess the quality of the found solutions. A key component of our program is a novel integer linear formulation for bounding tree-width of a graph. Our tests clearly indicate that our approach works in practice, as our implementation was able to find an optimal or nearly optimal network for most of the data sets.} }
Endnote
%0 Conference Paper %T Learning Bounded Tree-width Bayesian Networks using Integer Linear Programming %A Pekka Parviainen %A Hossein Shahrabi Farahani %A Jens Lagergren %B Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2014 %E Samuel Kaski %E Jukka Corander %F pmlr-v33-parviainen14 %I PMLR %P 751--759 %U https://proceedings.mlr.press/v33/parviainen14.html %V 33 %X In many applications one wants to compute conditional probabilities given a Bayesian network. This inference problem is NP-hard in general but becomes tractable when the network has low tree-width. Since the inference problem is common in many application areas, we provide a practical algorithm for learning bounded tree-width Bayesian networks. We cast this problem as an integer linear program (ILP). The program can be solved by an anytime algorithm which provides upper bounds to assess the quality of the found solutions. A key component of our program is a novel integer linear formulation for bounding tree-width of a graph. Our tests clearly indicate that our approach works in practice, as our implementation was able to find an optimal or nearly optimal network for most of the data sets.
RIS
TY - CPAPER TI - Learning Bounded Tree-width Bayesian Networks using Integer Linear Programming AU - Pekka Parviainen AU - Hossein Shahrabi Farahani AU - Jens Lagergren BT - Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics DA - 2014/04/02 ED - Samuel Kaski ED - Jukka Corander ID - pmlr-v33-parviainen14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 33 SP - 751 EP - 759 L1 - http://proceedings.mlr.press/v33/parviainen14.pdf UR - https://proceedings.mlr.press/v33/parviainen14.html AB - In many applications one wants to compute conditional probabilities given a Bayesian network. This inference problem is NP-hard in general but becomes tractable when the network has low tree-width. Since the inference problem is common in many application areas, we provide a practical algorithm for learning bounded tree-width Bayesian networks. We cast this problem as an integer linear program (ILP). The program can be solved by an anytime algorithm which provides upper bounds to assess the quality of the found solutions. A key component of our program is a novel integer linear formulation for bounding tree-width of a graph. Our tests clearly indicate that our approach works in practice, as our implementation was able to find an optimal or nearly optimal network for most of the data sets. ER -
APA
Parviainen, P., Shahrabi Farahani, H. & Lagergren, J.. (2014). Learning Bounded Tree-width Bayesian Networks using Integer Linear Programming. Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 33:751-759 Available from https://proceedings.mlr.press/v33/parviainen14.html.

Related Material