Approximation Fixpoint Theory with Refined Approximation Spaces

• URL: http://arxiv.org/abs/2506.16294v1
• Date: Thu, 19 Jun 2025 13:12:53 GMT
• Title: Approximation Fixpoint Theory with Refined Approximation Spaces
• Authors: Linde Vanbesien, Bart Bogaerts, Marc Denecker,
• Abstract summary: Approximation Fixpoint Theory (AFT) is a powerful theory covering various semantics of non-monotonic reasoning formalisms.<n>In this paper, we extend AFT to deal with approximations that are more refined than intervals.
• Score: 5.714553194279462
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Approximation Fixpoint Theory (AFT) is a powerful theory covering various semantics of non-monotonic reasoning formalisms in knowledge representation such as Logic Programming and Answer Set Programming. Many semantics of such non-monotonic formalisms can be characterized as suitable fixpoints of a non-monotonic operator on a suitable lattice. Instead of working on the original lattice, AFT operates on intervals in such lattice to approximate or construct the fixpoints of interest. While AFT has been applied successfully across a broad range of non-monotonic reasoning formalisms, it is confronted by its limitations in other, relatively simple, examples. In this paper, we overcome those limitations by extending consistent AFT to deal with approximations that are more refined than intervals. Therefore, we introduce a more general notion of approximation spaces, showcase the improved expressiveness and investigate relations between different approximation spaces.

Related papers

• CTRLS: Chain-of-Thought Reasoning via Latent State-Transition [57.51370433303236]
  Chain-of-thought (CoT) reasoning enables large language models to break down complex problems into interpretable intermediate steps.<n>We introduce groundingS, a framework that formulates CoT reasoning as a Markov decision process (MDP) with latent state transitions.<n>We show improvements in reasoning accuracy, diversity, and exploration efficiency across benchmark reasoning tasks.
  arXiv  Detail & Related papers  (2025-07-10T21:32:18Z)
• Eliminating Unintended Stable Fixpoints for Hybrid Reasoning Systems [5.208405959764274]
  We introduce a methodology resembling AFT that can utilize priorly computed upper bounds to more precisely capture semantics. We demonstrate our framework's applicability to hybrid MKNF (minimal knowledge and negation as failure) knowledge bases by extending the state-of-the-art approximator.
  arXiv  Detail & Related papers  (2023-07-21T01:08:15Z)
• Robust probabilistic inference via a constrained transport metric [8.85031165304586]
  We offer a novel alternative by constructing an exponentially tilted empirical likelihood carefully designed to concentrate near a parametric family of distributions. The proposed approach finds applications in a wide variety of robust inference problems, where we intend to perform inference on the parameters associated with the centering distribution. We demonstrate superior performance of our methodology when compared against state-of-the-art robust Bayesian inference methods.
  arXiv  Detail & Related papers  (2023-03-17T16:10:06Z)
• Non-Deterministic Approximation Fixpoint Theory and Its Application in Disjunctive Logic Programming [11.215352918313577]
  Approximation fixpoint theory is a framework for studying the semantics of nonmonotonic logics. We extend AFT to dealing with non-deterministic constructs that allow to handle indefinite information. The applicability and usefulness of this generalization is illustrated in the context of disjunctive logic programming.
  arXiv  Detail & Related papers  (2022-11-30T18:58:32Z)
• Data-Driven Influence Functions for Optimization-Based Causal Inference [105.5385525290466]
  We study a constructive algorithm that approximates Gateaux derivatives for statistical functionals by finite differencing. We study the case where probability distributions are not known a priori but need to be estimated from data.
  arXiv  Detail & Related papers  (2022-08-29T16:16:22Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  We propose a family of Riemannian algorithms generalizing and extending the seminal approximation framework of Robbins and Monro. Compared to their Euclidean counterparts, Riemannian algorithms are much less understood due to lack of a global linear structure on the manifold. We provide a general template of almost sure convergence results that mirrors and extends the existing theory for Euclidean Robbins-Monro schemes.
  arXiv  Detail & Related papers  (2022-06-14T12:30:11Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. We establish non-asymptotic bounds for both the operator defect and the estimation error.
  arXiv  Detail & Related papers  (2022-01-21T02:46:57Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)
• Alternating Fixpoint Operator for Hybrid MKNF Knowledge Bases as an Approximator of AFT [10.843231120912757]
  We show that Knorr et al.'s study of the well-founded semantics for hybrid MKNF knowledge bases is in fact an approximator of AFT in disguise. We show an improved approximator for these knowledge bases, of which the least stable fixpoint is information richer than the one formulated from Knorr et al.'s construction. This work is built on an extension of AFT that supports consistent as well as inconsistent pairs in the induced product bilattice.
  arXiv  Detail & Related papers  (2021-05-24T02:32:51Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)
• Independent finite approximations for Bayesian nonparametric inference [30.367795444044788]
  We propose a recipe to construct practical finite-dimensional approximations for homogeneous random measures. We upper bound the approximation error of AIFAs for a wide class of common CRMs and NCRMs. We prove that, for worst-case choices of observation likelihoods, TFAs are more efficient than AIFAs.
  arXiv  Detail & Related papers  (2020-09-22T19:37:21Z)
• Lower bounds in multiple testing: A framework based on derandomized proxies [107.69746750639584]
  This paper introduces an analysis strategy based on derandomization, illustrated by applications to various concrete models. We provide numerical simulations of some of these lower bounds, and show a close relation to the actual performance of the Benjamini-Hochberg (BH) algorithm.
  arXiv  Detail & Related papers  (2020-05-07T19:59:51Z)
• Lifted Hybrid Variational Inference [31.441922284854893]
  We investigate two approximate lifted variational approaches that are applicable to hybrid domains. We demonstrate that the proposed variational methods are both scalable and can take advantage of approximate model symmetries. We present a sufficient condition for the Bethe approximation to yield a non-trivial estimate over the marginal polytope.
  arXiv  Detail & Related papers  (2020-01-08T22:29:07Z)

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.