Solving MAP Exactly by Searching on Compiled Arithmetic Circuits
Solving MAP Exactly by Searching on Compiled Arithmetic Circuits
复制标题
通过搜索编译运算电路精确求解MAP
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Adnan Darwiche
中科院分区：
文献类型：
--
作者：
Jinbo Huang;M. Chavira;Adnan Darwiche
贝叶斯网络中的最大后验假设问题是在给定一组变量的补集上的部分证据的情况下，找出该组变量的最可能状态。用于找到MAP的精确解的标准的基于结构的推理方法，例如变量消除和连接树算法，在网络的受限树宽度中具有指数的复杂性。Park和Darwiche提出的一个最近的算法，只在树宽上是指数的，并且已经被证明可以处理树宽约束非常高的网络。在本文中，我们提出了一种新的算法，确切的地图，不一定是有限的可扩展性，甚至树宽。这是通过利用贝叶斯网络编译成算术电路的最新进展来实现的，这可以通过利用网络中存在的局部结构来规避树宽限制。具体来说，我们实现了一个分支定界搜索，其中使用线性时间运算的编译算术电路的边界计算。在具有局部结构的网络上，我们观察到Park和Darwiche算法的数量级改进。特别是，我们能够有效地解决许多问题，后者的算法运行内存不足，因为高树宽。
The MAP (maximum a posteriori hypothesis) problem in Bayesian networks is to find the most likely states of a set of variabls given partial evidence on the complement of that set. Standard structure-based inference methods for finding exact solutions to MAP, such as variable elimination and join-tree algorithms, have complexities that are exponential in the constrained treewidth of the network. A more recent algorithm, proposed by Park and Darwiche, is exponential only in the treewidth and has been shown to handle networks whose constrained treewidth is quite high. In this paper we present a new algorithm for exact MAP that is not necessarily limited in scalability even by the treewidth. This is achieved by leveraging recent advances in compilation of Bayesian networks into arithmetic circuits, which can circumvent treewidth-imposed limits by exploiting the local structure present in the network. Specifically, we implement a branch-and-bound search where the bounds are computed using linear-time operations on the compiled arithmetic circuit. On networks with local structure, we observe orders-of-magnitude improvements over the algorithm of Park and Darwiche. In particular, we are able to efficiently solve many problems where the latter algorithm runs out of memory because of high treewidth.