Parallel Splash Belief Propagation
Parallel Splash Belief Propagation
复制标题
并行飞溅置信传播
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Carlos Guestrin
中科院分区：
文献类型：
--
作者：
Joseph Gonzalez;Yucheng Low;Carlos Guestrin
随着计算机体系结构向指数增长的过渡，我们被迫在机器学习算法设计的基本层面上采用并行性。在本文中，我们关注并行图形模型推断。我们证明，信仰传播的自然，同步并行化高效。通过界定链图形模型中可实现的并行性能，我们对信仰传播的平行局限性产生了理论理解。然后，我们提供了一种新的平行信念传播算法，可实现最佳性能。使用几个具有挑战性的现实世界任务，我们从经验上评估了算法在大型环状图形模型上的性能，在该模型中，我们在线性并行缩放缩放并执行替代算法上实现了替代算法。
As computer architectures transition towards exponentially increasing parallelism we are forced to adopt parallelism at a fundamental level in the design of machine learning algorithms. In this paper we focus on parallel graphical model inference. We demonstrate that the natural, synchronous parallelization of belief propagation is highly inefficient. By bounding the achievable parallel performance in chain graphical models we develop a theoretical understanding of the parallel limitations of belief propagation. We then provide a new parallel belief propagation algorithm which achieves optimal performance. Using several challenging real-world tasks, we empirically evaluate the performance of our algorithm on large cyclic graphical models where we achieve near linear parallel scaling and out perform alternative algorithms.