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 pro- pose is data-dependent and is given by the probability that a conditional independence test correctly shows that an edge cannot ex- ist. What really distinguishes this new scor- ing function from earlier work is that it has the property of becoming computationally easier to maximize as the amount of data in- creases. We prove a polynomial sample com- plexity result, showing that maximizing this score is guaranteed to correctly learn a struc- ture with no false edges and a distribution close to the generating distribution, when- ever there exists a Bayesian network which is a perfect map for the data generating distri- bution. Although the new score can be used with any search algorithm, we give empirical results showing that it is particularly effec- tive when used together with a linear pro- gramming 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 pro- pose is data-dependent and is given by the probability that a conditional independence test correctly shows that an edge cannot ex- ist. What really distinguishes this new scor- ing function from earlier work is that it has the property of becoming computationally easier to maximize as the amount of data in- creases. We prove a polynomial sample com- plexity result, showing that maximizing this score is guaranteed to correctly learn a struc- ture with no false edges and a distribution close to the generating distribution, when- ever there exists a Bayesian network which is a perfect map for the data generating distri- bution. Although the new score can be used with any search algorithm, we give empirical results showing that it is particularly effec- tive when used together with a linear pro- gramming 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 pro- pose is data-dependent and is given by the probability that a conditional independence test correctly shows that an edge cannot ex- ist. What really distinguishes this new scor- ing function from earlier work is that it has the property of becoming computationally easier to maximize as the amount of data in- creases. We prove a polynomial sample com- plexity result, showing that maximizing this score is guaranteed to correctly learn a struc- ture with no false edges and a distribution close to the generating distribution, when- ever there exists a Bayesian network which is a perfect map for the data generating distri- bution. Although the new score can be used with any search algorithm, we give empirical results showing that it is particularly effec- tive when used together with a linear pro- gramming 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