Evaluating Bayesian Networks via Data Streams
Evaluating Bayesian Networks via Data Streams
复制标题
通过数据流评估贝叶斯网络
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
H. Vu
中科院分区：
文献类型：
--
作者：
A. Mcgregor;H. Vu
Consider a stream of n-tuples that empirically define the joint distribution of n discrete random variables (X_1, ldots , X_n). Previous work of Indyk and McGregor [6] and Braverman et al. [1, 2] addresses the problem of determining whether these variables are n-wise independent by measuring the (ell _p) distance between the joint distribution and the product distribution of the marginals. An open problem in this line of work is to answer more general questions about the dependencies between the variables. One powerful way to express such dependencies is via Bayesian networks where nodes correspond to variables and directed edges encode dependencies. We consider the problem of testing such dependencies in the streaming setting. Our main results are:
1.
A tight upper and lower bound of ( ilde{Theta }(nk^{d})) on the space required to test whether the data is consistent with a given Bayesian network where k is the size of the range of each (X_i) and d is the max in-degree of the network.
2.
A tight upper and lower bound of ( ilde{Theta }(k^d)) on the space required to compute any 2-approximation of the log-likelihood of the network.
3.
Finally, we show space/accuracy trade-offs for the problem of independence testing using (ell _1) and (ell _2) distances.
