SparsityBoost: A New Scoring Function for Learning Bayesian Network Structure

Eliot Brenner, David Sontag
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:332-341, 2013.

Abstract

We give a new consistent scoring function for structure learning of Bayesian networks. In contrast to traditional approaches to score-based structure learning, such as BDeu or MDL, the complexity penalty that we propose is data-dependent and is given by the probability that a conditional independence test correctly shows that an edge cannot exist. What really distinguishes this new scoring function from earlier work is that it has the property of becoming computationally easier to maximize as the amount of data increases. We prove a polynomial sample complexity result, showing that maximizing this score is guaranteed to correctly learn a structure with no false edges and a distribution close to the generating distribution, whenever there exists a Bayesian network which is a perfect map for the data generating distribution. Although the new score can be used with any search algorithm, we give empirical results showing that it is particularly effective when used together with a linear programming relaxation approach to Bayesian network structure learning.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-brenner13a, title = {SparsityBoost: A New Scoring Function for Learning {B}ayesian Network Structure}, author = {Brenner, Eliot and Sontag, David}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {332--341}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/brenner13a/brenner13a.pdf}, url = {https://proceedings.mlr.press/r11/brenner13a.html}, abstract = {We give a new consistent scoring function for structure learning of Bayesian networks. In contrast to traditional approaches to score-based structure learning, such as BDeu or MDL, the complexity penalty that we propose is data-dependent and is given by the probability that a conditional independence test correctly shows that an edge cannot exist. What really distinguishes this new scoring function from earlier work is that it has the property of becoming computationally easier to maximize as the amount of data increases. We prove a polynomial sample complexity result, showing that maximizing this score is guaranteed to correctly learn a structure with no false edges and a distribution close to the generating distribution, whenever there exists a Bayesian network which is a perfect map for the data generating distribution. Although the new score can be used with any search algorithm, we give empirical results showing that it is particularly effective when used together with a linear programming relaxation approach to Bayesian network structure learning.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T SparsityBoost: A New Scoring Function for Learning Bayesian Network Structure %A Eliot Brenner %A David Sontag %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-brenner13a %I PMLR %P 332--341 %U https://proceedings.mlr.press/r11/brenner13a.html %V R11 %X We give a new consistent scoring function for structure learning of Bayesian networks. In contrast to traditional approaches to score-based structure learning, such as BDeu or MDL, the complexity penalty that we propose is data-dependent and is given by the probability that a conditional independence test correctly shows that an edge cannot exist. What really distinguishes this new scoring function from earlier work is that it has the property of becoming computationally easier to maximize as the amount of data increases. We prove a polynomial sample complexity result, showing that maximizing this score is guaranteed to correctly learn a structure with no false edges and a distribution close to the generating distribution, whenever there exists a Bayesian network which is a perfect map for the data generating distribution. Although the new score can be used with any search algorithm, we give empirical results showing that it is particularly effective when used together with a linear programming relaxation approach to Bayesian network structure learning. %Z Reissued by PMLR on 04 October 2026.
APA
Brenner, E. & Sontag, D.. (2013). SparsityBoost: A New Scoring Function for Learning Bayesian Network Structure. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:332-341 Available from https://proceedings.mlr.press/r11/brenner13a.html. Reissued by PMLR on 04 October 2026.

Related Material