Learnability of Parameter-Bounded Bayes Nets
Arnab Bhattacharyya, Davin Choo, Sutanu Gayen, Dimitrios Myrisiotis
Abstract
Bayes nets are extensively used in practice to efficiently represent joint probability distributions over a set of random variables and capture dependency relations. Prior work has shown that given a distribution P defined as the marginal distribution of a Bayes net, it is NP-hard to decide whether there is a parameter-bounded Bayes net that represents P. They called this problem LEARN. In this work, we extend the NP-hardness result of LEARN and prove the NP-hardness of a promise search variant of LEARN, whereby the Bayes net in question is guaranteed to exist and one is asked to find such a Bayes net. We complement our hardness result with a positive result about the sample complexity that is sufficient to recover a parameter-bounded Bayes net that is close (in TV distance) to a given distribution P, represented by some parameter-bounded Bayes net, thereby generalizing a degree-bounded sample complexity literature result.
BibTeX
@article{Bhattacharyya_Choo_Gayen_Myrisiotis_2025, title={Learnability of Parameter-Bounded Bayes Nets}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/33708}, DOI={10.1609/aaai.v39i15.33708}, abstractNote={Bayes nets are extensively used in practice to efficiently represent joint probability distributions over a set of random variables and capture dependency relations.
Prior work has shown that given a distribution P defined as the marginal distribution of a Bayes net, it is NP-hard to decide whether there is a parameter-bounded Bayes net that represents P.
They called this problem LEARN.
In this work, we extend the NP-hardness result of LEARN and prove the NP-hardness of a promise search variant of LEARN, whereby the Bayes net in question is guaranteed to exist and one is asked to find such a Bayes net.
We complement our hardness result with a positive result about the sample complexity that is sufficient to recover a parameter-bounded Bayes net that is close (in TV distance) to a given distribution P, represented by some parameter-bounded Bayes net, thereby generalizing a degree-bounded sample complexity literature result.}, number={15}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Bhattacharyya, Arnab and Choo, Davin and Gayen, Sutanu and Myrisiotis, Dimitrios}, year={2025}, month={Apr.}, pages={15559-15566} }