Polynomial-Time Relational Probabilistic Inference in Open Universes
Luise Ge, Brendan Juba, Kris Nilsson · 2025
Read Polynomial-Time Relational Probabilistic Inference in Open Universes by Luise Ge, Brendan Juba, Kris Nilsson (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-04115.txt.
Introduction
Luise Ge, Brendan Juba, and Kris Nilsson present a 2025 paper on reasoning under uncertainty in worlds with unknown objects. Artificial intelligence must weigh evidence in settings where the cast of entities is not fixed in advance. Rich languages for this are usually too slow, and fast ones too weak, a classic trade-off.
The authors extend a sum-of-squares logic of expectation to relational knowledge bases. Within a fragment that limits how objects link and how deep the statements nest, the reasoning runs in polynomial time. That holds even when the object set is endless or unknown beforehand. Their guarantees are stated in proof terms: the method finds the tightest bounds that proofs of a given size can show. The result is a rare case where power and speed coexist.
Catalog record
| CREATOR | Luise Ge, Brendan Juba, Kris Nilsson |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-04115
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Polynomial-Time Relational Probabilistic Inference in Open Universes Luise Ge, Brendan Juba, Kris Nilsson Abstract Reasoning under uncertainty is a fundamental challenge in Artificial Intelligence. As with most of these challenges, there is a harsh dilemma between the expressive power of the language used, and the tractability of the computational problem posed by reasoning. Inspired by human reasoning, we introduce a method of first-order relational probabilistic inference that satisfies both criteria, and can handle hybrid (discrete and continuous) variables. Specifically, we extend sum-of-squares logic of expectation to relational settings, demonstrating that lifted reasoning in the bounded-degree fragment for knowledge bases of bounded quantifier rank can be performed in polynomial time, even with an a priori unknown and/or countably infinite set of objects. Crucially, our notion of tractability is framed in proof-theoretic terms , which extends beyond the syntactic properties of the language or queries. We are able to derive the tightest bounds provable by proofs of a given degree and size and establish completeness in our sum-of-squares refutations for fixed degrees. 1 Introduction Intelligent agents must cope with limits to their knowledge of the world. One of the most widely studied and mature approaches treats the state of the world as probabilistic, using inference from observed evidence to draw conclusions about what is likely—and what is not—regarding unobserved parts of the world, future states, and so on. At the same time, it is profitable to use relational representations for our knowledge of the world. In this way, a single, short statement can assert a common collection of relationships about a large collection of similar objects. In a vast world, such relational knowledge enables an agent to draw on some basic understanding of situations, locations, or objects that it has never before encountered. There is substantial evidence from cognitive science showing that a core aspect of human intelligence arises from relational thinking and reasoning Hummel and Holyoak (2003) ; Krawczyk (2012) . And one can argue that relational representations are highly desirable and perhaps even essential for many areas of AI such as planning and natural language processing. Unfortunately, power rarely comes for free. Naïve approaches to both probabilistic inference and relational inference, that might explicitly consider the various possible states of the world, are not computationally feasible to perform at scale. Since our focus is on addressing a vast world, we need approaches that do not explicitly consider the possible world states, but instead operate at a more abstract “lifted” level, reasoning generically about entire classes of objects. In general, it is still challenging to carry out such a strategy efficiently, and this is an area of active research Van den Broeck et al. (2021) . In this work, we consider a new logic with a tractable fragment that can capture knowledge that is out of reach of the existing tractable methods. Our approach builds on and extends three distinct threads in the literature. The first is work on tractable probability logics. Our work presents a relational generalization of the sum-of-squares probability logic Lasserre (2001) ; Juba (2019) , while retaining a powerful tractable fragment given by bounded-degree expressions. The second thread is relational optimization. Sum-of-squares, in the primal formulation, is a family of semidefinite optimization problems. Kersting et al. Kersting et al. (2017) and Mladenov et al. Mladenov et al. (2017) respectively proposed relational generalizations of linear and convex quadratic programs, and developed tools for efficiently solving such problems. Here, we show that the techniques may be extended to countably infinite domains, and present a logic that characterizes the power of the programs we obtain via these techniques. Finally, the third thread concerns the existing technique for inference in such infinite universes: Belle Belle (2017) showed how to perform weighted first-order model counting in such open universes, which enables certain kinds of probabilistic inference. We extend Belle’s approach, and overcome two main limitations: first, that first-order model counting is only known to be tractable for various two-variable fragments, and is postulated to be intractable for many three-variable formulas and beyond Beame et al. (2015) . Second, Belle’s technique to extend to infinite universes relies on compactness for Boolean propositional logic, which clearly does not hold even for linear arithmetic—consider the example of the formulas e(x)\geq n for all integer n (where e(x) represents the expected value for x , which is included in our language), the infinite set of constraints \{e(x)\geq n:n\ \text{ is an integer}\} is unsatisfiable, whereas any finite subset is satisfiable. Our generalization, in contrast to others, enables us to reason about the expected values of random variables that take numeric values as well as bounded-degree moments. 2 Related Work Probability logics Most directly, our work proposes a logic of expectation, as discussed by Halpern and Pucella Halpern and Pucella (2007) , extended to a first-order language with a powerful tractable fragment. It directly generalizes the tractable fragment considered by Juba Juba (2019) . Indeed, it can also serve as a logic of probability, of the kind that Halpern Halpern (1990) calls a “type 2” first-order logic of probability – meaning, the probabilities are taken over valuations of the formulas, as opposed to bindings from the domain of quantification. (See Appendix C for an example) Alternatively, our knowledge is expressed as a combination of logical constraints and bounds on the marginals of certain expressions; as shown by Kuželka et al. Kuželka et al. (2018) , if we consider a maximum-entropy objective, marginal equality constraints alone capture Markov Logic Networks Richardson and Domingos (2006) , so we may obtain a (strict) generalization of such models. But rather than assuming interest in a maximum-entropy model, we will be primarily interested in what values may possibly be taken by the expected value of other expressions. Markov Logic Indeed, Markov Logic is a prominent example of the vast family of different models that have been considered as targets for probabilistic modeling and inference with relational representations; Van den Broeck et al. Van den Broeck et al. (2021) give a broad overview of this area. Typically, inference in these models is reduced to Weighted (First-Order) Model Counting (WFOMC) Chavira and Darwiche (2008) ; Van den Broeck et al. (2011) ; Van den Broeck et al. (2014) , in which possible worlds are assigned a (pseudo-) likelihood given by the product of the (explicitly defined) weights associated with the specified formulas satisfied in each such possible world. Indeed, the likelihoods assigned to possible worlds by Markov Logic (for example again) are usually defined in such a way. Again, in contrast to these works, our focus is not specifically on inference in models of such form. Moreover, we consider expectation more generally than probability per se – i.e., expressions that may take numeric values. In the literature, such models are referred to as “hybrid” probabilistic models, and reduced to Weighted (First-Order) Model Integration Belle et al. (2015) ; Feldstein and Belle (2021) . This problem is generally more challenging and is only tractable in limited cases Zeng et al. (2020) ; Feldstein and Belle (2021) . Indeed, even WFOMC, which only concerns probability, is only known to be tractable in various two-variable fragments Van den Broeck et al. (2011) ; Van den Broeck et