Approximating Bounded Tree-Width Bayesian Network Classifiers with OBDD
Abstract
It is shown that Bayesian network classifiers of tree-width $k$ have an OBDD approximation computable in polynomial time in the parameters, for every fixed $k$. This is shown by approximating a polynomial threshold function representing the classifier. The approximation error can be measured with respect to any distribution which can be approximated by a mixture of bounded width distributions. This includes the input distribution of the classifier.
Cite
Text
Chubarian and Turán. "Approximating Bounded Tree-Width Bayesian Network Classifiers with OBDD." Proceedings of pgm 2020, 2020.Markdown
[Chubarian and Turán. "Approximating Bounded Tree-Width Bayesian Network Classifiers with OBDD." Proceedings of pgm 2020, 2020.](https://mlanthology.org/pgm/2020/chubarian2020pgm-approximating/)BibTeX
@inproceedings{chubarian2020pgm-approximating,
title = {{Approximating Bounded Tree-Width Bayesian Network Classifiers with OBDD}},
author = {Chubarian, Karine and Turán, György},
booktitle = {Proceedings of pgm 2020},
year = {2020},
pages = {113-124},
volume = {138},
url = {https://mlanthology.org/pgm/2020/chubarian2020pgm-approximating/}
}