There IS a Free Lunch: Constraints for Learning Bayesian Networks

Xiannian Fan Graduate Center CUNY, Brandon Malone "Helsinki Institute for Information Technology Finland", Changhe Yuan City University of New York
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:186-195, 2014.

Abstract

Several recent algorithms for learning Bayesian network structures first calculate potentially optimal parent sets (POPS) for all variables and then use various optimization techniques to find a set of POPS, one for each variable, that constitutes an optimal network structure. This paper makes the observation that there is useful information implicit in the POPS. Specifically, the POPS of a variable constrain its parent candidates. Moreover, the parent candidates of all variables together give a directed cyclic graph, which often decomposes into a set of strongly connected components (SCCs). Each SCC corresponds to a smaller subproblem which can be solved independently of the others. Our results show that solving the constrained subproblems significantly improves the efficiency and scalability of heuristic search-based structure learning algorithms. Further, we show that by considering only the top p POPS of each variable, we quickly find provably very high quality networks for large datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-cuny14a, title = {There {IS} a Free Lunch: Constraints for Learning {B}ayesian Networks}, author = {CUNY, Xiannian Fan Graduate Center and Finland", Brandon Malone "Helsinki Institute for Information Technology and York, Changhe Yuan City University of New}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {186--195}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/cuny14a/cuny14a.pdf}, url = {https://proceedings.mlr.press/r12/cuny14a.html}, abstract = {Several recent algorithms for learning Bayesian network structures first calculate potentially optimal parent sets (POPS) for all variables and then use various optimization techniques to find a set of POPS, one for each variable, that constitutes an optimal network structure. This paper makes the observation that there is useful information implicit in the POPS. Specifically, the POPS of a variable constrain its parent candidates. Moreover, the parent candidates of all variables together give a directed cyclic graph, which often decomposes into a set of strongly connected components (SCCs). Each SCC corresponds to a smaller subproblem which can be solved independently of the others. Our results show that solving the constrained subproblems significantly improves the efficiency and scalability of heuristic search-based structure learning algorithms. Further, we show that by considering only the top p POPS of each variable, we quickly find provably very high quality networks for large datasets.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T There IS a Free Lunch: Constraints for Learning Bayesian Networks %A Xiannian Fan Graduate Center CUNY %A Brandon Malone "Helsinki Institute for Information Technology Finland" %A Changhe Yuan City University of New York %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-cuny14a %I PMLR %P 186--195 %U https://proceedings.mlr.press/r12/cuny14a.html %V R12 %X Several recent algorithms for learning Bayesian network structures first calculate potentially optimal parent sets (POPS) for all variables and then use various optimization techniques to find a set of POPS, one for each variable, that constitutes an optimal network structure. This paper makes the observation that there is useful information implicit in the POPS. Specifically, the POPS of a variable constrain its parent candidates. Moreover, the parent candidates of all variables together give a directed cyclic graph, which often decomposes into a set of strongly connected components (SCCs). Each SCC corresponds to a smaller subproblem which can be solved independently of the others. Our results show that solving the constrained subproblems significantly improves the efficiency and scalability of heuristic search-based structure learning algorithms. Further, we show that by considering only the top p POPS of each variable, we quickly find provably very high quality networks for large datasets. %Z Reissued by PMLR on 04 October 2026.
APA
CUNY, X.F.G.C., Finland", B.M.".I.f.I.T. & York, C.Y.C.U.o.N.. (2014). There IS a Free Lunch: Constraints for Learning Bayesian Networks. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:186-195 Available from https://proceedings.mlr.press/r12/cuny14a.html. Reissued by PMLR on 04 October 2026.

Related Material