海报：贝叶斯网络的快速并行精确推理

4250海报：贝叶斯网络上的快速并行精确推理0Jiantong Jiang†，Zeyi Wen‡，§，Atif Mansoor†，Ajmal Mian†0†西澳大学‡香港科技大学（广州）；§香港科技大学jiantong.jiang@research.uwa.edu.au,wenzeyi@ust.hk,{atif.mansoor,ajmal.mian}@uwa.edu.au0摘要贝叶斯网络（BNs）具有图形化和可解释的机器学习模型的吸引力。然而，对于复杂问题，BNs的精确推理非常耗时。为了提高效率，我们提出了一种名为Fast-BNI的快速BN精确推理解决方案，可以在多核CPU上实现。Fast-BNI通过紧密集成粗粒度和细粒度并行性来提高精确推理的效率。我们还提出了进一步简化BN精确推理的瓶颈操作的技术。Fast-BNI源代码可以在https://github.com/jjiantong/FastBN免费获取。0CCS概念：• 计算方法学 → 并行算法；机器学习算法。0关键词：贝叶斯网络，推理，Junction Tree01 引言0贝叶斯网络（BNs）是概率图模型。BNs使用有向无环图（DAG），通常从数据中学习[2]，来表示随机变量及其条件依赖关系。贝叶斯网络上的精确推理是一项重要任务，它计算某些查询变量的条件概率，给定其他变量的某些值作为BN的知识证据。JunctionTree（JT）是最重要的贝叶斯网络精确推理算法之一。其关键思想是将BN首先转换为称为联结树的辅助结构，在树中的每个节点（称为团）和边（称为分隔符）都包含一组变量，并维护变量上的潜在表。然后，它沿着树结构传递消息（即变量上的函数）并更新所有潜在表。然而，贝叶斯网络上的精确推理被证明是NP难题。JT的复杂性随着团大小（即团的潜在表大小）的增加而显著增加，这阻碍了在复杂问题中使用BNs的应用。在多核CPU上加速JT的方法主要有两种类型。第一种类型使用粗粒度的区间并行性，将不同团的消息传递并行化[3]。但是，区间并行性不平衡负载，因为不同团的工作量差异很大。该类别中的一些方法利用指针跳转技术，但引入了由重新根化或合并操作引起的额外开销。第二种类型的方法是细粒度的内部并行性，将每个团内部的潜在表操作并行化[4]。郑[5]使用类似的思路在GPU上加速JT。然而，这种方法的效率问题在于由于频繁调用表操作而导致的大规模并行化开销。此外，区间并行性对于具有少量团的树来说性能有限，而内部并行性对于具有许多小团的树来说效率较低。因此，只有在特定的联结树结构下，这两种方法才能更高效。0未经许可，个人或课堂使用者可以制作此作品的部分或全部的数字或硬拷贝，但不得为盈利或商业优势而制作或分发拷贝，并且拷贝必须带有此通知和第一页的完整引用。必须尊重此作品中第三方组件的版权。对于其他所有用途，请联系所有者/作者。PPoPP'23，2023年2月25日至3月1日，加拿大蒙特利尔，QC，版权所有©2023版权由所有者/作者持有。ACM ISBN979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.35774760PPoPP'23，2023年2月25日至3月1日，加拿大蒙特利尔，QC，版权所有© 2023 J. Jiang等02 我们的Fast-BNI设计为了解决直接使用仅有的区间或内部并行性的效率问题，我们提出了Fast-BNI，一种快速且并行的BN精确推理解决方案，它融合了区间和内部并行性。对于区间并行性，我们首先开发了一种基于广度优先搜索的遍历方法，利用树结构之间的并行化机会。我们的遍历方法将所有的团和分隔符视为树的节点，并标记了它们所在的层次。其次，我们采用了一种根选择策略，构建了一个更加平衡的树，层数最小，以减少并行化调用的总次数。对于内部并行性，我们确定并并行化了三个主要的潜在表操作，包括潜在表的边际化、扩展和缩减。潜在表操作的关键步骤是找到原始表和更新后表之间的索引映射。因此，这些操作的复杂度取决于潜在表的大小，随着团（或分隔符）中随机变量的数量增加，复杂度会显著增加。4260BN0表1 Fast-BNI与其他实现的比较以及Fast-BNI相对于每个比较实现的加速比。0顺序实现 并行实现0Hailfinder 28.3 4.0 7.1 3.0 3.2 4.0 2.5 1.2 1.3 1.60UnBBayes Fast-BNI-seq UnBBayes Dir. Prim. Elem. Fast-BNI-par Dir. Prim. Elem.0Diabetes 90961 6944 13.1 3016 2311 3316 558.6 5.4 4.1 5.90Pathfinder 319.2 68.9 4.6 40.5 23.6 27.8 11.1 3.6 2.1 2.50Munin2 3054 2643 1.2 1951 934.7 1638 241.7 8.1 3.9 6.80Pigs 43714 3729 11.7 3353 1068 2380 221.7 15.1 4.8 10.70Munin4 258194 34198 7.6 20364 10348 21398 3021 6.7 3.4 7.103 评估 我们在一台装有两颗26核2GHz英特尔Xeon Platinum8167MCPU和768GB主内存的Linux机器上进行了实验。我们对六个不同大小的真实世界BN进行了测试，其中最后四个被认为是大规模的BN。我们从每个网络中随机生成了2000个测试用例，每个测试用例观察变量的比例为20%。表1显示了Fast-BNI的顺序和并行实现与现有实现的执行时间比较。具体来说，我们将Fast-BNI的顺序版本（即Fast-BNI-seq）与UnBBayes库中的JT实现进行了比较；我们还将Fast-BNI的并行版本（即Fast-BNI-par）与并行实现进行了比较。实现[3]（用Direct，Dir.表示）使用直接的粗粒度并行性；实现[4]（用Primitive，Prim.表示）为JT提出了四个细粒度的节点级原语；实现[5]（用Element，Elem.表示）利用细粒度的逐元素并行性。为了比较并行实现，我们将OpenMP线程数�从1变化到32，并选择执行时间最短的线程数。01 https://www.bnlearn.com/bnrepository/ 2 UnBBayes:https://sourceforge.net/projects/unbbayes/ .0从表1的“加速比”列可以看出，Fast-BNI的顺序实现比UnBBayes快1.2到13.1倍。当比较并行实现时，Fast-BNI-par比相应的对应物运行速度快1.2到15.2倍。值得注意的是，Fast-BNI在大型网络上比现有实现更具优势。对于一些小规模网络，Fast-BNI相对于其他并行实现的加速比较小，因为它们对贝叶斯推理的执行时间要求较短（例如，对于Hailfinder来说不到4秒），而小规模网络的并行化开销占据了很大比例。另一个观察结果是，在大型BN上，Fast-BNI总是在� =32时实现最短的执行时间。Munin4是一个具有1000多个节点和边的非常大的BN。在Munin4上的实验是完成时间最长的任务。这个任务在UnBBayes上运行了将近三天，在现有的并行实现上花费了3到6个小时，而使用Fast-BNI提出的方法，执行时间显著缩短到不到一小时。0致谢教授AjmalMian是澳大利亚研究理事会未来研究员奖（项目编号FT210100268）的获得者，该奖项由澳大利亚政府资助。ZeyiWen是通讯作者。0参考文献0[1]  Rommel Carvalho，KB Laskey，Paulo Costa，MarceloLadeira，Laécio Santos和Shou Matsumoto. 2010.UnBBayes：在语义Web中进行合理推理的不确定性建模.语义Web（2010），953-978。0[2]  Jiantong Jiang，Zeyi Wen和Ajmal Mian. 2022.快速并行贝叶斯网络结构学习. 在国际并行与分布式处理研讨会（IPDPS）中.IEEE，617-627。0[3]  Alexander V Kozlov和Jaswinder Pal Singh. 1994.用于概率推理的并行Lauritzen-Spiegelhalter算法.在Supercomputing'94：1994年ACM/IEEE超级计算会议论文集中.IEEE，320-329。0[4]  Yinglong Xia和Viktor K. Prasanna. 2007.用于并行精确推理的节点级基元. SBAC-PAD（2007），221-228。0[5]  Lu Zheng. 2013. 在GPU上的并行Junction Tree算法. 博士论文.卡内基梅隆大学。