Informationtheoretic limits of Bayesian network structure learning
[edit]
Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR 54:767775, 2017.
Abstract
In this paper, we study the informationtheoretic limits of learning the structure of Bayesian networks (BNs), on discrete as well as continuous random variables, from a finite number of samples. We show that the minimum number of samples required by any procedure to recover the correct structure grows as $Ω(m)$ and $Ω(k \log m + (k^2)/m)$ for nonsparse and sparse BNs respectively, where m is the number of variables and k is the maximum number of parents per node. We provide a simple recipe, based on an extension of the Fano’s inequality, to obtain informationtheoretic limits of structure recovery for any exponential family BN. We instantiate our result for specific conditional distributions in the exponential family to characterize the fundamental limits of learning various commonly used BNs, such as conditional probability table based networks, Gaussian BNs, noisyOR networks, and logistic regression networks. En route to obtaining our main results, we obtain tight bounds on the number of sparse and nonsparse essentialDAGs. Finally, as a byproduct, we recover the informationtheoretic limits of sparse variable selection for logistic regression.
Related Material


