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
- 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.