Polynomial-Time Relational Probabilistic Inference in Open Universes

• URL: http://arxiv.org/abs/2505.04115v1
• Date: Wed, 07 May 2025 04:14:03 GMT
• Title: Polynomial-Time Relational Probabilistic Inference in Open Universes
• Authors: Luise Ge, Brendan Juba, Kris Nilsson,
• Abstract summary: We introduce a method of first-order probabilistic inference that satisfies both the expressive power of the language used and the tractability of the computational problem posed by reasoning.<n> Specifically, we extend sum-of-squares logic of expectation to relational settings.<n>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.
• Score: 14.312814866832804
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Soft Thinking: Unlocking the Reasoning Potential of LLMs in Continuous Concept Space [62.54887038032942]
  We introduce Soft Thinking, a training-free method that emulates human-like "soft" reasoning by generating soft, abstract concept tokens.<n>These concept tokens are created by the probability-weighted mixture of token embeddings, which form the continuous concept space.<n>In essence, each generated concept token encapsulates multiple meanings from related discrete tokens, implicitly exploring various reasoning paths to converge.
  arXiv  Detail & Related papers  (2025-05-21T17:29:15Z)
• A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds [6.6362553223890535]
  We analyze the complexity of intractable abduction problems under the seemingly overlooked but natural parameter n.<n>We obtain several positive results for $SigmaP$ as well as NP- and coNP-complete fragments.<n>We complement this with lower bounds and for many fragments rule out improvements under the (strong) exponential-time hypothesis.
  arXiv  Detail & Related papers  (2025-05-15T11:56:19Z)
• To Believe or Not to Believe Your LLM [51.2579827761899]
  We explore uncertainty quantification in large language models (LLMs) We derive an information-theoretic metric that allows to reliably detect when only epistemic uncertainty is large. We conduct a series of experiments which demonstrate the advantage of our formulation.
  arXiv  Detail & Related papers  (2024-06-04T17:58:18Z)
• Mitigating Misleading Chain-of-Thought Reasoning with Selective Filtering [59.495717939664246]
  Large language models have manifested remarkable capabilities by leveraging chain-of-thought (CoT) reasoning techniques to solve intricate questions. We propose a novel approach called the selective filtering reasoner (SelF-Reasoner) that assesses the entailment relationship between the question and the candidate reasoning chain. SelF-Reasoner improves the fine-tuned T5 baseline consistently over the ScienceQA, ECQA, and LastLetter tasks.
  arXiv  Detail & Related papers  (2024-03-28T06:28:35Z)
• When Is Inductive Inference Possible? [3.4991031406102238]
  We provide a tight characterization of inductive inference by establishing a novel link to online learning theory. We prove that inductive inference is possible if and only if the hypothesis class is a countable union of online learnable classes. Our main technical tool is a novel non-uniform online learning framework, which may be of independent interest.
  arXiv  Detail & Related papers  (2023-11-30T20:02:25Z)
• A Semantic Approach to Decidability in Epistemic Planning (Extended Version) [72.77805489645604]
  We use a novel semantic approach to achieve decidability. Specifically, we augment the logic of knowledge S5$_n$ and with an interaction axiom called (knowledge) commutativity. We prove that our framework admits a finitary non-fixpoint characterization of common knowledge, which is of independent interest.
  arXiv  Detail & Related papers  (2023-07-28T11:26:26Z)
• A Measure-Theoretic Axiomatisation of Causality [55.6970314129444]
  We argue in favour of taking Kolmogorov's measure-theoretic axiomatisation of probability as the starting point towards an axiomatisation of causality. Our proposed framework is rigorously grounded in measure theory, but it also sheds light on long-standing limitations of existing frameworks.
  arXiv  Detail & Related papers  (2023-05-19T13:15:48Z)
• An Embedding-based Approach to Inconsistency-tolerant Reasoning with Inconsistent Ontologies [12.760301272393898]
  We propose a novel approach to reasoning with inconsistent semantics based on the embeddings of axioms. We show that our embedding-based method can outperform existing inconsistency-tolerant reasoning methods based on maximal consistent subsets.
  arXiv  Detail & Related papers  (2023-04-04T09:38:02Z)
• Admissibility in Strength-based Argumentation: Complexity and Algorithms (Extended Version with Proofs) [1.5828697880068698]
  We study the adaptation of admissibility-based semantics to Strength-based Argumentation Frameworks (StrAFs) Especially, we show that the strong admissibility defined in the literature does not satisfy a desirable property, namely Dung's fundamental lemma. We propose a translation in pseudo-Boolean constraints for computing (strong and weak) extensions.
  arXiv  Detail & Related papers  (2022-07-05T18:42:04Z)
• Causal Expectation-Maximisation [70.45873402967297]
  We show that causal inference is NP-hard even in models characterised by polytree-shaped graphs. We introduce the causal EM algorithm to reconstruct the uncertainty about the latent variables from data about categorical manifest variables. We argue that there appears to be an unnoticed limitation to the trending idea that counterfactual bounds can often be computed without knowledge of the structural equations.
  arXiv  Detail & Related papers  (2020-11-04T10:25:13Z)
• Learning Implicitly with Noisy Data in Linear Arithmetic [94.66549436482306]
  We extend implicit learning in PAC-Semantics to handle intervals and threshold uncertainty in the language of linear arithmetic. We show that our implicit approach to learning optimal linear programming objective constraints significantly outperforms an explicit approach in practice.
  arXiv  Detail & Related papers  (2020-10-23T19:08:46Z)
• Probabilistic Reasoning across the Causal Hierarchy [10.138180861883635]
  Our languages are of strictly increasing expressivity. We show that satisfiability and validity for each language are decidable in space.
  arXiv  Detail & Related papers  (2020-01-09T08:52:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.