论文标题
有限度贝叶斯网络的独立性测试
Independence Testing for Bounded Degree Bayesian Network
论文作者
论文摘要
我们研究以下独立测试问题：从$ \ {0,1 \}^n $上访问$ p $的样品，确定$ p $是产品分配还是$ \ varepsilon $ - 与任何产品分配的总变化距离。对于任意分布，此问题需要$ \ exp（n）$样本。我们在这项工作中表明，如果$ p $具有稀疏的结构，那么实际上只需要线性许多样本。具体而言，如果$ p $相对于贝叶斯网络是马尔可夫人的基础dag，其基础dag具有$ d $的限制，则$ \tildeθ（2^{d/2} \ cdot n/\ cdot n/\ varepsilon^2）$样品是必需的，并且足以进行独立测试。
We study the following independence testing problem: given access to samples from a distribution $P$ over $\{0,1\}^n$, decide whether $P$ is a product distribution or whether it is $\varepsilon$-far in total variation distance from any product distribution. For arbitrary distributions, this problem requires $\exp(n)$ samples. We show in this work that if $P$ has a sparse structure, then in fact only linearly many samples are required. Specifically, if $P$ is Markov with respect to a Bayesian network whose underlying DAG has in-degree bounded by $d$, then $\tildeΘ(2^{d/2}\cdot n/\varepsilon^2)$ samples are necessary and sufficient for independence testing.
