Scalable Bayesian Network Structure Learning via Maximum Acyclic Subgraph

Pierre Gillot, Pekka Parviainen
Proceedings of the 10th International Conference on Probabilistic Graphical Models, PMLR 138:209-220, 2020.

Abstract

Learning the structure of a Bayesian network is an NP-hard problem and exact learning algorithms that are guaranteed to find an optimal structure are not feasible with large number of variables. Thus, large-scale learning is usually done using heuristics that do not provide any quality guarantees. We present a heuristic method that scales up to networks with hundreds of variables and provides quality guarantees in terms of an upper bound for the score of the optimal network. The proposed method consists of two parts. First, we simplify the problem by approximating local scores using so-called edge scores. With the edge scores learning an optimal Bayesian network structure is equivalent to finding the maximum acyclic subgraph. Second, we solve the maximum acyclic subgraph problem fast using integer linear programming. Additionally, we choose the approximation in a specific way so that an upper bound for the score of an optimal network can be obtained.

Cite this Paper

BibTeX
@InProceedings{pmlr-v138-gillot20a, title = {Scalable Bayesian Network Structure Learning via Maximum Acyclic Subgraph}, author = {Gillot, Pierre and Parviainen, Pekka}, booktitle = {Proceedings of the 10th International Conference on Probabilistic Graphical Models}, pages = {209--220}, year = {2020}, editor = {Jaeger, Manfred and Nielsen, Thomas Dyhre}, volume = {138}, series = {Proceedings of Machine Learning Research}, month = {23--25 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v138/gillot20a/gillot20a.pdf}, url = {https://proceedings.mlr.press/v138/gillot20a.html}, abstract = {Learning the structure of a Bayesian network is an NP-hard problem and exact learning algorithms that are guaranteed to find an optimal structure are not feasible with large number of variables. Thus, large-scale learning is usually done using heuristics that do not provide any quality guarantees. We present a heuristic method that scales up to networks with hundreds of variables and provides quality guarantees in terms of an upper bound for the score of the optimal network. The proposed method consists of two parts. First, we simplify the problem by approximating local scores using so-called edge scores. With the edge scores learning an optimal Bayesian network structure is equivalent to finding the maximum acyclic subgraph. Second, we solve the maximum acyclic subgraph problem fast using integer linear programming. Additionally, we choose the approximation in a specific way so that an upper bound for the score of an optimal network can be obtained.} }
Endnote
%0 Conference Paper %T Scalable Bayesian Network Structure Learning via Maximum Acyclic Subgraph %A Pierre Gillot %A Pekka Parviainen %B Proceedings of the 10th International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2020 %E Manfred Jaeger %E Thomas Dyhre Nielsen %F pmlr-v138-gillot20a %I PMLR %P 209--220 %U https://proceedings.mlr.press/v138/gillot20a.html %V 138 %X Learning the structure of a Bayesian network is an NP-hard problem and exact learning algorithms that are guaranteed to find an optimal structure are not feasible with large number of variables. Thus, large-scale learning is usually done using heuristics that do not provide any quality guarantees. We present a heuristic method that scales up to networks with hundreds of variables and provides quality guarantees in terms of an upper bound for the score of the optimal network. The proposed method consists of two parts. First, we simplify the problem by approximating local scores using so-called edge scores. With the edge scores learning an optimal Bayesian network structure is equivalent to finding the maximum acyclic subgraph. Second, we solve the maximum acyclic subgraph problem fast using integer linear programming. Additionally, we choose the approximation in a specific way so that an upper bound for the score of an optimal network can be obtained.
APA
Gillot, P. & Parviainen, P.. (2020). Scalable Bayesian Network Structure Learning via Maximum Acyclic Subgraph. Proceedings of the 10th International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 138:209-220 Available from https://proceedings.mlr.press/v138/gillot20a.html.

Related Material