Testing Bayesian Networks
[edit]
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:370448, 2017.
Abstract
This work initiates a systematic investigation of testing \em highdimensional structured distributions by focusing on testing \em Bayesian networks – the prototypical family of directed graphical models. A Bayesian network is defined by a directed acyclic graph, where we associate a random variable with each node. The value at any particular node is conditionally independent of all the other nondescendant nodes once its parents are fixed. Specifically, we study the properties of identity testing and closeness testing of Bayesian networks. Our main contribution is the first nontrivial efficient testing algorithms for these problems and corresponding informationtheoretic lower bounds. For a wide range of parameter settings, our testing algorithms have sample complexity \em sublinear in the dimension and are sampleoptimal, up to constant factors.
Related Material


