Implicit Learning for Reasoning in First-Order Probabilistic Logic

Luise Ge, Brendan Juba, Kris Nilsson, Alison Shao
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:1684-1694, 2026.

Abstract

Reasoning under uncertainty is a fundamental challenge, particularly when inference involves complex computations over large relational domains. Existing probabilistic inference methods typically answer probabilistic queries by leveraging symmetries to perform efficient, lifted inference assuming access to a complete model. However, the upstream task of learning such a model from partial and noisy observations is generally intractable. We propose the first polynomial-time framework for “implicit learning to reason" in a first-order relational probability logic, even over infinite domains. Our approach combines statistical signals from data with semidefinite relaxations of the moment problem, jointly informed by new observations and prior knowledge from the knowledge base. This enables verifying or refuting first-order queries without ever constructing an explicit model. We establish soundness and completeness guarantees for our algorithm, as well as a tractability result.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-ge26a, title = {Implicit Learning for Reasoning in First-Order Probabilistic Logic}, author = {Ge, Luise and Juba, Brendan and Nilsson, Kris and Shao, Alison}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {1684--1694}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/ge26a/ge26a.pdf}, url = {https://proceedings.mlr.press/v337/ge26a.html}, abstract = {Reasoning under uncertainty is a fundamental challenge, particularly when inference involves complex computations over large relational domains. Existing probabilistic inference methods typically answer probabilistic queries by leveraging symmetries to perform efficient, lifted inference assuming access to a complete model. However, the upstream task of learning such a model from partial and noisy observations is generally intractable. We propose the first polynomial-time framework for “implicit learning to reason" in a first-order relational probability logic, even over infinite domains. Our approach combines statistical signals from data with semidefinite relaxations of the moment problem, jointly informed by new observations and prior knowledge from the knowledge base. This enables verifying or refuting first-order queries without ever constructing an explicit model. We establish soundness and completeness guarantees for our algorithm, as well as a tractability result.} }
Endnote
%0 Conference Paper %T Implicit Learning for Reasoning in First-Order Probabilistic Logic %A Luise Ge %A Brendan Juba %A Kris Nilsson %A Alison Shao %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-ge26a %I PMLR %P 1684--1694 %U https://proceedings.mlr.press/v337/ge26a.html %V 337 %X Reasoning under uncertainty is a fundamental challenge, particularly when inference involves complex computations over large relational domains. Existing probabilistic inference methods typically answer probabilistic queries by leveraging symmetries to perform efficient, lifted inference assuming access to a complete model. However, the upstream task of learning such a model from partial and noisy observations is generally intractable. We propose the first polynomial-time framework for “implicit learning to reason" in a first-order relational probability logic, even over infinite domains. Our approach combines statistical signals from data with semidefinite relaxations of the moment problem, jointly informed by new observations and prior knowledge from the knowledge base. This enables verifying or refuting first-order queries without ever constructing an explicit model. We establish soundness and completeness guarantees for our algorithm, as well as a tractability result.
APA
Ge, L., Juba, B., Nilsson, K. & Shao, A.. (2026). Implicit Learning for Reasoning in First-Order Probabilistic Logic. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:1684-1694 Available from https://proceedings.mlr.press/v337/ge26a.html.

Related Material