Deep Bucket Elimination
Deep Bucket Elimination
复制标题
DOI：
10.24963/ijcai.2021/582
复制
发表时间：
2021-08
期刊：
影响因子：
--
通讯作者：
Yasaman Razeghi;Kalev Kask;Yadong Lu;P. Baldi;Sakshi Agarwal;R. Dechter
中科院分区：
文献类型：
--
作者：
Yasaman Razeghi;Kalev Kask;Yadong Lu;P. Baldi;Sakshi Agarwal;R. Dechter
桶消除（BE）是一种通用的推理方案，可以准确地解决概率性和确定性图模型上的大多数任务。然而，它通常需要指数级高水平的内存（在诱导宽度中），从而阻止其执行。本着利用深度学习进行推理任务的精神，在本文中，我们将使用神经网络来近似 BE。由此产生的深桶消除（DBE）算法是为了计算配分函数而开发的。我们使用来自多个不同基准的实例进行了经验性的概念验证，表明 DBE 可以是比当前最先进的 BE 近似方法（例如迷你桶方案）更准确的近似值，特别是当问题足够困难时。
Bucket Elimination (BE) is a universal inference scheme that can solve most tasks over probabilistic and deterministic graphical models exactly. However, it often requires exponentially high levels of memory (in the induced-width) preventing its execution. In the spirit of exploiting Deep Learning for inference tasks, in this paper, we will use neural networks to approximate BE. The resulting Deep Bucket Elimination (DBE) algorithm is developed for computing the partition function. We provide a proof-of-concept empirically using instances from several different benchmarks, showing that DBE can be a more accurate approximation than current state-of-the-art approaches for approximating BE (e.g. the mini-bucket schemes), especially when problems are sufficiently hard.