Testing Bayesian Networks

Clement L. Canonne, Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart
Proceedings of the 2017 Conference on Learning Theory, PMLR 65:370-448, 2017.

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 this Paper

BibTeX
@InProceedings{pmlr-v65-canonne17a, 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}, pages = {370--448}, year = {2017}, editor = {Kale, Satyen and Shamir, Ohad}, volume = {65}, series = {Proceedings of Machine Learning Research}, month = {07--10 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v65/canonne17a/canonne17a.pdf}, url = {https://proceedings.mlr.press/v65/canonne17a.html}, 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.} }
Endnote
%0 Conference Paper %T Testing Bayesian Networks %A Clement L. Canonne %A Ilias Diakonikolas %A Daniel M. Kane %A Alistair Stewart %B Proceedings of the 2017 Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Satyen Kale %E Ohad Shamir %F pmlr-v65-canonne17a %I PMLR %P 370--448 %U https://proceedings.mlr.press/v65/canonne17a.html %V 65 %X 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.
APA
Canonne, C.L., Diakonikolas, I., Kane, D.M. & Stewart, A.. (2017). Testing Bayesian Networks. Proceedings of the 2017 Conference on Learning Theory, in Proceedings of Machine Learning Research 65:370-448 Available from https://proceedings.mlr.press/v65/canonne17a.html.

Related Material