Comparison of SAT-based and ASP-based Algorithms for Inconsistency Measurement

• URL: http://arxiv.org/abs/2304.14832v1
• Date: Fri, 28 Apr 2023 13:18:55 GMT
• Title: Comparison of SAT-based and ASP-based Algorithms for Inconsistency Measurement
• Authors: Isabelle Kuhlmann, Anna Gessler, Vivien Laszlo, Matthias Thimm
• Abstract summary: We present algorithms based on satisfiability problem (SAT) solving, as well as answer set programming (ASP) We consider six different inconsistency measures whose respective decision problems lie on the first level of the hierarchy.
• Score: 5.459753761530944
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present algorithms based on satisfiability problem (SAT) solving, as well as answer set programming (ASP), for solving the problem of determining inconsistency degrees in propositional knowledge bases. We consider six different inconsistency measures whose respective decision problems lie on the first level of the polynomial hierarchy. Namely, these are the contension inconsistency measure, the forgetting-based inconsistency measure, the hitting set inconsistency measure, the max-distance inconsistency measure, the sum-distance inconsistency measure, and the hit-distance inconsistency measure. In an extensive experimental analysis, we compare the SAT-based and ASP-based approaches with each other, as well as with a set of naive baseline algorithms. Our results demonstrate that overall, both the SAT-based and the ASP-based approaches clearly outperform the naive baseline methods in terms of runtime. The results further show that the proposed ASP-based approaches perform superior to the SAT-based ones with regard to all six inconsistency measures considered in this work. Moreover, we conduct additional experiments to explain the aforementioned results in greater detail.

Related papers

• Consistent Labeling Across Group Assignments: Variance Reduction in Conditional Average Treatment Effect Estimation [4.938762852799707]
  We highlight a common issue where many algorithms exhibit inconsistent learning behavior for the same instance across different group assignments.<n>We present a theoretical analysis showing that this inconsistency indeed contributes to higher test errors and cannot be resolved through conventional machine learning techniques.<n>We propose a general method called textbfConsistent Labeling Across Group Assignments (CLAGA) which eliminates the inconsistency and is applicable to any existing CATE estimation algorithm.
  arXiv  Detail & Related papers  (2025-07-06T10:36:39Z)
• Advancing Stochastic 3-SAT Solvers by Dissipating Oversatisfied Constraints [0.0]
  We introduce and benchmark a local search for the NP-complete satisfiability problem 3-SAT.<n>Our construction is based on the crucial observation that well established previous approaches such as WalkSAT are prone to get stuck in local minima.<n>We analyze and benchmark our algorithm on a randomly generated sample of hard but satisfiable 3-SAT instances with varying problem sizes up to N=15000.
  arXiv  Detail & Related papers  (2025-06-18T18:00:01Z)
• Stepwise Reasoning Checkpoint Analysis: A Test Time Scaling Method to Enhance LLMs' Reasoning [81.50681925980135]
  We propose Stepwise Reasoning Checkpoint Analysis (SRCA), a framework that introduces checkpoints between reasoning steps.<n>It incorporates two key strategies: (1) Answer-Clustered Search, which groups reasoning paths by their intermediate checkpoint answers to maintain diversity while ensuring quality, and (2) Checkpoint Candidate Augmentation, which leverages all intermediate answers for final decision-making.<n>Our approach effectively reduces path homogenization and creates a fault-tolerant mechanism by utilizing high-quality intermediate results.
  arXiv  Detail & Related papers  (2025-05-23T12:42:50Z)
• Absolute Ranking: An Essential Normalization for Benchmarking Optimization Algorithms [0.0]
  evaluating performance across optimization algorithms on many problems presents a complex challenge due to the diversity of numerical scales involved. This paper extensively explores the problem, making a compelling case to underscore the issue and conducting a thorough analysis of its root causes. Building on this research, this paper introduces a new mathematical model called "absolute ranking" and a sampling-based computational method.
  arXiv  Detail & Related papers  (2024-09-06T00:55:03Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  The sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs) This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models. In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.
  arXiv  Detail & Related papers  (2023-07-01T18:35:21Z)
• Explaining SAT Solving Using Causal Reasoning [30.469229388827443]
  We introduce CausalSAT, which employs causal reasoning to gain insights into the functioning of modern SAT solvers. We use CausalSAT to quantitatively verify hypotheses previously regarded as "rules of thumb" or empirical findings.
  arXiv  Detail & Related papers  (2023-06-09T22:53:16Z)
• Best-Effort Adaptation [62.00856290846247]
  We present a new theoretical analysis of sample reweighting methods, including bounds holding uniformly over the weights. We show how these bounds can guide the design of learning algorithms that we discuss in detail. We report the results of a series of experiments demonstrating the effectiveness of our best-effort adaptation and domain adaptation algorithms.
  arXiv  Detail & Related papers  (2023-05-10T00:09:07Z)
• Querying Inconsistent Prioritized Data with ORBITS: Algorithms, Implementation, and Experiments [12.952483242045366]
  We investigate practical algorithms for inconsistency-tolerant query answering over prioritized knowledge bases. We consider three well-known semantics (AR, IAR and brave) based upon two notions of optimal repairs (Pareto and completion)
  arXiv  Detail & Related papers  (2022-02-16T10:44:39Z)
• The Statistical Complexity of Interactive Decision Making [126.04974881555094]
  We provide a complexity measure, the Decision-Estimation Coefficient, that is proven to be both necessary and sufficient for sample-efficient interactive learning. A unified algorithm design principle, Estimation-to-Decisions (E2D), transforms any algorithm for supervised estimation into an online algorithm for decision making.
  arXiv  Detail & Related papers  (2021-12-27T02:53:44Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  We explore the connection between high-dimensional statistics and non-robust optimization in the presence of sparsity constraints. We develop novel and simple optimization formulations for these problems. As a corollary, we obtain that any first-order method that efficiently converges to station yields an efficient algorithm for these tasks.
  arXiv  Detail & Related papers  (2021-09-23T17:38:24Z)
• Performance Evaluation of Adversarial Attacks: Discrepancies and Solutions [51.8695223602729]
  adversarial attack methods have been developed to challenge the robustness of machine learning models. We propose a Piece-wise Sampling Curving (PSC) toolkit to effectively address the discrepancy. PSC toolkit offers options for balancing the computational cost and evaluation effectiveness.
  arXiv  Detail & Related papers  (2021-04-22T14:36:51Z)
• Constraint-Handling Techniques for Particle Swarm Optimization Algorithms [0.0]
  Population-based methods can cope with a variety of different problems, including problems of remarkably higher complexity than those traditional methods can handle. The aim here is to develop and compare different CHTs suitable for PSOs, which are incorporated to an algorithm with general-purpose settings.
  arXiv  Detail & Related papers  (2021-01-25T01:49:10Z)
• Benchmarking Simulation-Based Inference [5.3898004059026325]
  Recent advances in probabilistic modelling have led to a large number of simulation-based inference algorithms which do not require numerical evaluation of likelihoods. We provide a benchmark with inference tasks and suitable performance metrics, with an initial selection of algorithms. We found that the choice of performance metric is critical, that even state-of-the-art algorithms have substantial room for improvement, and that sequential estimation improves sample efficiency.
  arXiv  Detail & Related papers  (2021-01-12T18:31:22Z)

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.