An Efficient and Scalable Algorithm for Local Bayesian Network Structure Discovery
Abstract
We present an efficient and scalable constraint-based algorithm, called Hybrid Parents and Children (HPC), to learn the parents and children of a target variable in a Bayesian network. Finding those variables is an important first step in many applications including Bayesian network structure learning, dimensionality reduction and feature selection. The algorithm combines ideas from incremental and divide-and-conquer methods in a principled and effective way, while still being sound in the sample limit. Extensive empirical experiments are provided on public synthetic and real-world data sets of various sample sizes. The most noteworthy feature of HPC is its ability to handle large neighborhoods contrary to current CB algorithm proposals. The number of calls to the statistical test, en hence the run-time, is empirically on the order O ( n ^1.09), where n is the number of variables, on the five benchmarks that we considered, and O ( n ^1.21) on a real drug design characterized by 138,351 features.
Cite
Text
de Morais and Aussem. "An Efficient and Scalable Algorithm for Local Bayesian Network Structure Discovery." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2010. doi:10.1007/978-3-642-15939-8_11Markdown
[de Morais and Aussem. "An Efficient and Scalable Algorithm for Local Bayesian Network Structure Discovery." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2010.](https://mlanthology.org/ecmlpkdd/2010/demorais2010ecmlpkdd-efficient/) doi:10.1007/978-3-642-15939-8_11BibTeX
@inproceedings{demorais2010ecmlpkdd-efficient,
title = {{An Efficient and Scalable Algorithm for Local Bayesian Network Structure Discovery}},
author = {de Morais, Sergio Rodrigues and Aussem, Alex},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2010},
pages = {164-179},
doi = {10.1007/978-3-642-15939-8_11},
url = {https://mlanthology.org/ecmlpkdd/2010/demorais2010ecmlpkdd-efficient/}
}