Fast Algorithms for Relational Marginal Polytopes

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

IJCAI 2021poster3 citations

Fast Algorithms for Relational Marginal Polytopes

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

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.

Uncertainty in AI: Statistical Relational AIMachine Learning: Relational Learning

BibTeX

@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    = {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},
}