Fast Algorithms for Relational Marginal Polytopes

Wang, Yuanhong; van Bremen, Timothy; Pu, Juhua; Wang, Yuyi; Kuzelka, Ondrej

doi:10.24963/ijcai.2021/586

Fast Algorithms for Relational Marginal Polytopes

Yuanhong Wang, Timothy van Bremen, Juhua Pu, Yuyi Wang, Ondrej Kuzelka

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 4266-4274.

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

Keywords

Uncertainty in AI: Statistical Relational AI
Machine Learning: Relational Learning

Abstract

We study the problem of constructing the relational marginal polytope (RMP) of a given set of first-order formulas. Past work has shown that the RMP construction problem can be reduced to weighted first-order model counting (WFOMC). However, existing reductions in the literature are intractable in practice, since they typically require an infeasibly large number of calls to a WFOMC oracle. In this paper, we propose an algorithm to construct RMPs using fewer oracle calls. As an application, we also show how to apply this new algorithm to improve an existing approximation scheme for WFOMC. We demonstrate the efficiency of the proposed approaches experimentally, and find that our method provides speed-ups over the baseline for RMP construction of a full order of magnitude.

Yuanhong Wang, Timothy van Bremen, Juhua Pu, Yuyi Wang, and Ondrej Kuzelka. 2021. Fast Algorithms for Relational Marginal Polytopes. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 4266–4274. https://doi.org/10.24963/ijcai.2021/586

@inproceedings{ijcai2021p586,
  title     = {Fast Algorithms for Relational Marginal Polytopes},
  author    = {Wang, Yuanhong and van Bremen, Timothy and Pu, Juhua and Wang, Yuyi and Kuzelka, Ondrej},
  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     = {4266--4274},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/586},
  url       = {https://doi.org/10.24963/ijcai.2021/586},
}

TY  - CPAPER
TI  - Fast Algorithms for Relational Marginal Polytopes
AU  - Wang, Yuanhong
AU  - van Bremen, Timothy
AU  - Pu, Juhua
AU  - Wang, Yuyi
AU  - Kuzelka, Ondrej
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 4266
EP  - 4274
DO  - 10.24963/ijcai.2021/586
UR  - https://doi.org/10.24963/ijcai.2021/586
ER  -