Testing Bayesian Networks
Abstract
This work initiates a systematic investigation of testing \em high-dimensional 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 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 \em sublinear in the dimension and are sample-optimal, up to constant factors.
Cite
Text
Canonne et al. "Testing Bayesian Networks." Proceedings of the 2017 Conference on Learning Theory, 2017.Markdown
[Canonne et al. "Testing Bayesian Networks." Proceedings of the 2017 Conference on Learning Theory, 2017.](https://mlanthology.org/colt/2017/canonne2017colt-testing/)BibTeX
@inproceedings{canonne2017colt-testing,
title = {{Testing Bayesian Networks}},
author = {Canonne, Clement L. and Diakonikolas, Ilias and Kane, Daniel M. and Stewart, Alistair},
booktitle = {Proceedings of the 2017 Conference on Learning Theory},
year = {2017},
pages = {370-448},
volume = {65},
url = {https://mlanthology.org/colt/2017/canonne2017colt-testing/}
}