Deep Bucket Elimination

Razeghi, Yasaman; Kask, Kalev; Lu, Yadong; Baldi, Pierre; Agarwal, Sakshi; Dechter, Rina

doi:10.24963/ijcai.2021/582

Deep Bucket Elimination

Yasaman Razeghi, Kalev Kask, Yadong Lu, Pierre Baldi, Sakshi Agarwal, Rina Dechter

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 4235-4242.

https://doi.org/10.24963/ijcai.2021/582

Keywords

Uncertainty in AI: Approximate Probabilistic Inference
Uncertainty in AI: Exact Probabilistic Inference

Abstract

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.

Yasaman Razeghi, Kalev Kask, Yadong Lu, Pierre Baldi, Sakshi Agarwal, and Rina Dechter. 2021. Deep Bucket Elimination. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 4235–4242. https://doi.org/10.24963/ijcai.2021/582

@inproceedings{ijcai2021p582,
  title     = {Deep Bucket Elimination},
  author    = {Razeghi, Yasaman and Kask, Kalev and Lu, Yadong and Baldi, Pierre and Agarwal, Sakshi and Dechter, Rina},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {4235--4242},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/582},
  url       = {https://doi.org/10.24963/ijcai.2021/582},
}

TY  - CPAPER
TI  - Deep Bucket Elimination
AU  - Razeghi, Yasaman
AU  - Kask, Kalev
AU  - Lu, Yadong
AU  - Baldi, Pierre
AU  - Agarwal, Sakshi
AU  - Dechter, Rina
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 4235
EP  - 4242
DO  - 10.24963/ijcai.2021/582
UR  - https://doi.org/10.24963/ijcai.2021/582
ER  -