Local Structure Discovery in Bayesian Networks

Teppo Niinimaki, Pekka Parviainen
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:633-642, 2012.

Abstract

Learning a Bayesian network structure from data is an NP-hard problem and thus exact algorithms are feasible only for small data sets. Therefore, network structures for larger networks are usually learned with various heuristics. Another approach to scaling up the structure learning is local learning. In local learning, the modeler has one or more target variables that are of special interest; he wants to learn the structure near the target variables and is not interested in the rest of the variables. In this paper, we present a score-based local learning algorithm called SLL. We conjecture that our algorithm is theoretically sound in the sense that it is optimal in the limit of large sample size. Empirical results suggest that SLL is competitive when compared to the constraint-based HITON algorithm. We also study the prospects of constructing the network structure for the whole node set based on local results by presenting two algorithms and comparing them to several heuristics.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-niinimaki12a, title = {Local Structure Discovery in {B}ayesian Networks}, author = {Niinimaki, Teppo and Parviainen, Pekka}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {633--642}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/niinimaki12a/niinimaki12a.pdf}, url = {https://proceedings.mlr.press/r10/niinimaki12a.html}, abstract = {Learning a Bayesian network structure from data is an NP-hard problem and thus exact algorithms are feasible only for small data sets. Therefore, network structures for larger networks are usually learned with various heuristics. Another approach to scaling up the structure learning is local learning. In local learning, the modeler has one or more target variables that are of special interest; he wants to learn the structure near the target variables and is not interested in the rest of the variables. In this paper, we present a score-based local learning algorithm called SLL. We conjecture that our algorithm is theoretically sound in the sense that it is optimal in the limit of large sample size. Empirical results suggest that SLL is competitive when compared to the constraint-based HITON algorithm. We also study the prospects of constructing the network structure for the whole node set based on local results by presenting two algorithms and comparing them to several heuristics.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Local Structure Discovery in Bayesian Networks %A Teppo Niinimaki %A Pekka Parviainen %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-niinimaki12a %I PMLR %P 633--642 %U https://proceedings.mlr.press/r10/niinimaki12a.html %V R10 %X Learning a Bayesian network structure from data is an NP-hard problem and thus exact algorithms are feasible only for small data sets. Therefore, network structures for larger networks are usually learned with various heuristics. Another approach to scaling up the structure learning is local learning. In local learning, the modeler has one or more target variables that are of special interest; he wants to learn the structure near the target variables and is not interested in the rest of the variables. In this paper, we present a score-based local learning algorithm called SLL. We conjecture that our algorithm is theoretically sound in the sense that it is optimal in the limit of large sample size. Empirical results suggest that SLL is competitive when compared to the constraint-based HITON algorithm. We also study the prospects of constructing the network structure for the whole node set based on local results by presenting two algorithms and comparing them to several heuristics. %Z Reissued by PMLR on 04 October 2026.
APA
Niinimaki, T. & Parviainen, P.. (2012). Local Structure Discovery in Bayesian Networks. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:633-642 Available from https://proceedings.mlr.press/r10/niinimaki12a.html. Reissued by PMLR on 04 October 2026.

Related Material