Fast Approximate Score Computation on Large-Scale Distributed Data for Learning Multinomial Bayesian Networks
Fast Approximate Score Computation on Large-Scale Distributed Data for Learning Multinomial Bayesian Networks
复制标题
DOI：
10.1145/3301304
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
A. Katib;P. Rao;Kobus Barnard;Charles A. Kamhoua
中科院分区：
文献类型：
--
作者：
A. Katib;P. Rao;Kobus Barnard;Charles A. Kamhoua
在这篇文章中，我们关注的是在存储在商品集群中的分布式数据上学习贝叶斯网络的问题。具体地说，我们解决了以高效和可伸缩的方式计算分布式数据的评分函数的挑战，这是学习过程中的一项基本任务。虽然准确的分数计算可以使用MapReduce式计算来完成，但我们的目标是以可伸缩的方式以概率误差界更快地计算近似分数。我们提出了一种新的方法，旨在实现以下目的：(A)使用八卦原则来实现分散的分数计算；(B)通过使用马尔可夫链的属性来使用概率方法来维护分数来降低资源消耗；以及(C)通过协同结合众所周知的散列技术来在分数计算过程中有效地分配任务。我们从计算分数所需统计量的收敛速度、内存和网络带宽消耗等方面对该方法进行了理论分析。我们还讨论了当有新数据可用时，我们的方法如何能够有效地重新计算分数。我们对我们的方法进行了全面的评估，并与在16节点集群上使用不同特征的数据集进行的MapReduce式计算进行了比较。当MapReduce式计算为分数计算提供准确的统计数据时，它比我们的方法慢了近10倍。虽然它在随机采样的数据集上的运行速度比在整个数据集上的运行速度快，但在准确性方面比我们的方法更差。我们的方法在所有测试数据集上获得了高精度(平均相对误差低于6%)的统计量估计以进行近似分数计算。综上所述，为大规模分布式数据的快速近似得分计算提供了计算时间和精度之间的一种可行的折衷。
In this article, we focus on the problem of learning a Bayesian network over distributed data stored in a commodity cluster. Specifically, we address the challenge of computing the scoring function over distributed data in an efficient and scalable manner, which is a fundamental task during learning. While exact score computation can be done using the MapReduce-style computation, our goal is to compute approximate scores much faster with probabilistic error bounds and in a scalable manner. We propose a novel approach, which is designed to achieve the following: (a) decentralized score computation using the principle of gossiping; (b) lower resource consumption via a probabilistic approach for maintaining scores using the properties of a Markov chain; and (c) effective distribution of tasks during score computation (on large datasets) by synergistically combining well-known hashing techniques. We conduct theoretical analysis of our approach in terms of convergence speed of the statistics required for score computation, and memory and network bandwidth consumption. We also discuss how our approach is capable of efficiently recomputing scores when new data are available. We conducted a comprehensive evaluation of our approach and compared with the MapReduce-style computation using datasets of different characteristics on a 16-node cluster. When the MapReduce-style computation provided exact statistics for score computation, it was nearly 10 times slower than our approach. Although it ran faster on randomly sampled datasets than on the entire datasets, it performed worse than our approach in terms of accuracy. Our approach achieved high accuracy (below 6% average relative error) in estimating the statistics for approximate score computation on all the tested datasets. In conclusion, it provides a feasible tradeoff between computation time and accuracy for fast approximate score computation on large-scale distributed data.