2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | L.1.2 | ||
| Paper Title | Provable Efficient Skeleton Learning of Encodable Discrete Bayes Nets in Poly-Time and Sample Complexity | ||
| Authors | Adarsh Barik, Jean Honorio, Purdue University, United States | ||
| Session | L.1: Application-Specific Learning | ||
| Presentation | Lecture | ||
| Track | Statistics and Learning Theory | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | In this paper, we study the problem of skeleton learning for Bayesian networks from data. In particular, we focus on nodes taking discrete values, and the learning of all the edges while disregarding their directionality, i.e., the skeleton of the Bayesian network. The problem of learning the structure of a Bayesian network is NP-hard in general. However, we show that under certain conditions we can recover the true skeleton with sufficient number of samples. We develop a mathematical model which does not assume any specific conditional probability distributions for the nodes. We use a primal-dual witness construction to prove that, under some technical conditions on the interaction between node pairs, we can do exact recovery of the parents and children of a node by performing group l_12-regularized multivariate regression. Thus, we recover the true Bayesian network skeleton. If degree of a node is bounded then the sample complexity of our proposed approach grows logarithmically with respect to the number of nodes in the Bayesian network. Furthermore, our method runs in polynomial time. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
