Testing Bayesian Networks

2016/12/09 by Clement L. Canonne, Clément L. Canonne, Clement Canonne +8 · 8 citations
Computer Science · Mathematics · #Algorithm #Artificial intelligence #Bayesian Modeling and Causal Inference #Bayesian network #Bayesian probability #Closeness #Computer science #Conditional independence #Directed acyclic graph #Graphical model #Machine Learning and Algorithms #Mathematics #Node (physics) #Statistical Methods and Inference #Theoretical computer science #cs.DS #cs.IT #cs.LG #math.IT #math.ST #stat.TH

paper · pdf · doi:10.1109/tit.2020.2971625

published in IEEE Transactions on Information Theory 66(5), 3132-3170 (Institute of Electrical and Electronics Engineers) · To appear in IEEE Transactions on Information Theory

arxiv created 2020/01/25 · arxiv updated 2020/01/28 · openalex publication_date 2020/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• The Generalization of Student's Ratio

Cited by

• Total Variation Distance Estimation in Autoregressive Models
• Uniformity Testing under User-Level Local Privacy
• Entropy Equivalence Testing
• Product distribution learning with imperfect advice
• Dimension Agnostic Testing of Survey Data Credibility through the Lens of Regression
• Pauli Measurements Are Near-Optimal for Single-Qubit Tomography
• Replicable Distribution Testing
• Tight simulation of a distribution using conditional samples

Related

• Learning restricted Bayesian network structures
• Efficient Sampling and Structure Learning of Bayesian Networks
• Reliable and Efficient Inference of Bayesian Networks from Sparse Data by Statistical Learning Theory
• On Testing Whether an Embedded Bayesian Network Represents a Probability Model
• Testing Sparsity Assumptions in Bayesian Networks