%0 Journal Article %1 canonne2016testing %A Canonne, Clement %A Diakonikolas, Ilias %A Kane, Daniel %A Stewart, Alistair %D 2016 %K bayesian bounds hypothesis-testing readings %T Testing Bayesian Networks %U http://arxiv.org/abs/1612.03156 %X This work initiates a systematic investigation of testing high-dimensional structured distributions by focusing on testing 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 non-descendant 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 non-trivial efficient testing algorithms for these problems and corresponding information-theoretic lower bounds. For a wide range of parameter settings, our testing algorithms have sample complexity sublinear in the dimension and are sample-optimal, up to constant factors.

@article{canonne2016testing, abstract = {This work initiates a systematic investigation of testing high-dimensional structured distributions by focusing on testing 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 non-descendant 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 non-trivial efficient testing algorithms for these problems and corresponding information-theoretic lower bounds. For a wide range of parameter settings, our testing algorithms have sample complexity sublinear in the dimension and are sample-optimal, up to constant factors.}, added-at = {2020-02-26T13:43:18.000+0100}, author = {Canonne, Clement and Diakonikolas, Ilias and Kane, Daniel and Stewart, Alistair}, biburl = {https://www.bibsonomy.org/bibtex/24751e0bdc15bc1b911b47e9bf37d572b/kirk86}, description = {[1612.03156] Testing Bayesian Networks}, interhash = {a75ce48f16b1cc21d56551ebece03682}, intrahash = {4751e0bdc15bc1b911b47e9bf37d572b}, keywords = {bayesian bounds hypothesis-testing readings}, note = {cite arxiv:1612.03156Comment: To appear in IEEE Transactions on Information Theory}, timestamp = {2020-03-04T13:55:04.000+0100}, title = {Testing Bayesian Networks}, url = {http://arxiv.org/abs/1612.03156}, year = 2016 }