Fast Algorithms for Relational Marginal Polytopes
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.
Cite
Text
Wang et al. "Fast Algorithms for Relational Marginal Polytopes." International Joint Conference on Artificial Intelligence, 2021. doi:10.24963/IJCAI.2021/586Markdown
[Wang et al. "Fast Algorithms for Relational Marginal Polytopes." International Joint Conference on Artificial Intelligence, 2021.](https://mlanthology.org/ijcai/2021/wang2021ijcai-fast/) doi:10.24963/IJCAI.2021/586BibTeX
@inproceedings{wang2021ijcai-fast,
title = {{Fast Algorithms for Relational Marginal Polytopes}},
author = {Wang, Yuanhong and van Bremen, Timothy and Pu, Juhua and Wang, Yuyi and Kuzelka, Ondrej},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2021},
pages = {4266-4274},
doi = {10.24963/IJCAI.2021/586},
url = {https://mlanthology.org/ijcai/2021/wang2021ijcai-fast/}
}