Fast and Accurate Density Estimation with Extremely Randomized Cutset Networks
Abstract
Cutset Networks (CNets) are density estimators leveraging context-specific independencies recently introduced to provide exact inference in polynomial time. Learning a CNet is done by firstly building a weighted probabilistic OR tree and then estimating tractable distributions as its leaves. Specifically, selecting an optimal OR split node requires cubic time in the number of the data features, and even approximate heuristics still scale in quadratic time. We introduce Extremely Randomized Cutset Networks (XCNets), CNets whose OR tree is learned by performing random conditioning. This simple yet surprisingly effective approach reduces the complexity of OR node selection to constant time. While the likelihood of an XCNet is slightly worse than an optimally learned CNet, ensembles of XCNets outperform state-of-the-art density estimators on a series of standard benchmark datasets, yet employing only a fraction of the time needed to learn the competitors. Code and data related to this chapter are available at: https://github.com/nicoladimauro/cnet .
Cite
Text
Di Mauro et al. "Fast and Accurate Density Estimation with Extremely Randomized Cutset Networks." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2017. doi:10.1007/978-3-319-71249-9_13Markdown
[Di Mauro et al. "Fast and Accurate Density Estimation with Extremely Randomized Cutset Networks." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2017.](https://mlanthology.org/ecmlpkdd/2017/mauro2017ecmlpkdd-fast/) doi:10.1007/978-3-319-71249-9_13BibTeX
@inproceedings{mauro2017ecmlpkdd-fast,
title = {{Fast and Accurate Density Estimation with Extremely Randomized Cutset Networks}},
author = {Di Mauro, Nicola and Vergari, Antonio and Basile, Teresa Maria Altomare and Esposito, Floriana},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2017},
pages = {203-219},
doi = {10.1007/978-3-319-71249-9_13},
url = {https://mlanthology.org/ecmlpkdd/2017/mauro2017ecmlpkdd-fast/}
}