Querying Inconsistent Prioritized Data with ORBITS: Algorithms, Implementation, and Experiments

• URL: http://arxiv.org/abs/2202.07980v1
• Date: Wed, 16 Feb 2022 10:44:39 GMT
• Title: Querying Inconsistent Prioritized Data with ORBITS: Algorithms, Implementation, and Experiments
• Authors: Meghyn Bienvenu, Camille Bourgaux
• Abstract summary: 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)
• Score: 12.952483242045366
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate practical algorithms for inconsistency-tolerant query answering over prioritized knowledge bases, which consist of a logical theory, a set of facts, and a priority relation between conflicting facts. We consider three well-known semantics (AR, IAR and brave) based upon two notions of optimal repairs (Pareto and completion). Deciding whether a query answer holds under these semantics is (co)NP-complete in data complexity for a large class of logical theories, and SAT-based procedures have been devised for repair-based semantics when there is no priority relation, or the relation has a special structure. The present paper introduces the first SAT encodings for Pareto- and completion-optimal repairs w.r.t. general priority relations and proposes several ways of employing existing and new encodings to compute answers under (optimal) repair-based semantics, by exploiting different reasoning modes of SAT solvers. The comprehensive experimental evaluation of our implementation compares both (i) the impact of adopting semantics based on different kinds of repairs, and (ii) the relative performances of alternative procedures for the same semantics.

Related papers

• Towards Fast Algorithms for the Preference Consistency Problem Based on Hierarchical Models [4.007697401483925]
  We construct and compare algorithmic approaches to solve the Consistency Problem for preference statements based on hierarchical models. An instance is consistent if there exists an hierarchical model on the evaluation functions that induces an order relation on the alternatives. We develop three approaches to solve this decision problem.
  arXiv  Detail & Related papers  (2024-10-31T13:48:46Z)
• Thought-Path Contrastive Learning via Premise-Oriented Data Augmentation for Logical Reading Comprehension [9.67774998354062]
  Previous research has primarily focused on enhancing logical reasoning capabilities through Chain-of-Thought (CoT) or data augmentation. We propose a Premise-Oriented Data Augmentation (PODA) framework to generate CoT rationales including analyses for both correct and incorrect options. We also introduce a novel thought-path contrastive learning method that compares reasoning paths between the original and counterfactual samples.
  arXiv  Detail & Related papers  (2024-09-22T15:44:43Z)
• H-STAR: LLM-driven Hybrid SQL-Text Adaptive Reasoning on Tables [56.73919743039263]
  This paper introduces a novel algorithm that integrates both symbolic and semantic (textual) approaches in a two-stage process to address limitations. Our experiments demonstrate that H-STAR significantly outperforms state-of-the-art methods across three question-answering (QA) and fact-verification datasets.
  arXiv  Detail & Related papers  (2024-06-29T21:24:19Z)
• Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
  We propose a new neural-symbolic method to support end-to-end learning using complex queries with provable reasoning capability. We develop a new dataset containing ten new types of queries with features that have never been considered. Our method outperforms previous methods significantly in the new dataset and also surpasses previous methods in the existing dataset at the same time.
  arXiv  Detail & Related papers  (2023-04-14T11:35:35Z)
• Language Model Decoding as Likelihood-Utility Alignment [54.70547032876017]
  We introduce a taxonomy that groups decoding strategies based on their implicit assumptions about how well the model's likelihood is aligned with the task-specific notion of utility. Specifically, by analyzing the correlation between the likelihood and the utility of predictions across a diverse set of tasks, we provide the first empirical evidence supporting the proposed taxonomy.
  arXiv  Detail & Related papers  (2022-10-13T17:55:51Z)
• SUN: Exploring Intrinsic Uncertainties in Text-to-SQL Parsers [61.48159785138462]
  This paper aims to improve the performance of text-to-dependence by exploring the intrinsic uncertainties in the neural network based approaches (called SUN) Extensive experiments on five benchmark datasets demonstrate that our method significantly outperforms competitors and achieves new state-of-the-art results.
  arXiv  Detail & Related papers  (2022-09-14T06:27:51Z)
• Learning to Hash Robustly, with Guarantees [79.68057056103014]
  In this paper, we design an NNS algorithm for the Hamming space that has worst-case guarantees essentially matching that of theoretical algorithms. We evaluate the algorithm's ability to optimize for a given dataset both theoretically and practically. Our algorithm has a 1.8x and 2.1x better recall on the worst-performing queries to the MNIST and ImageNet datasets.
  arXiv  Detail & Related papers  (2021-08-11T20:21:30Z)
• String Theories involving Regular Membership Predicates: From Practice to Theory and Back [12.98284167710378]
  An algorithm for the satisfiability problem for systems of string constraints requires a thorough understanding of the structure of constraints present in the targeted cases. In this paper, we investigate benchmarks presented in the literature containing regular expression membership predicates, extract different first order logic theories, and prove their decidability undecidability. Notably, the most common theories in real-world benchmarks are PSPACE-complete and directly lead to the implementation of a more efficient algorithm to solving string constraints.
  arXiv  Detail & Related papers  (2021-05-15T13:13:50Z)
• On Guaranteed Optimal Robust Explanations for NLP Models [16.358394218953833]
  We build on abduction-based explanations for ma-chine learning and develop a method for computing local explanations for neural network models. We present two solution algorithms, respectively based on implicit hitting sets and maximum universal subsets. We evaluate our framework on three widely used sentiment analysis tasks and texts of up to100words from SST, Twitter and IMDB datasets.
  arXiv  Detail & Related papers  (2021-05-08T08:44:48Z)
• A Constraint-Based Algorithm for the Structural Learning of Continuous-Time Bayesian Networks [70.88503833248159]
  We propose the first constraint-based algorithm for learning the structure of continuous-time Bayesian networks. We discuss the different statistical tests and the underlying hypotheses used by our proposal to establish conditional independence.
  arXiv  Detail & Related papers  (2020-07-07T07:34:09Z)
• Querying and Repairing Inconsistent Prioritized Knowledge Bases: Complexity Analysis and Links with Abstract Argumentation [5.87010466783654]
  We study the issue of inconsistency over prioritized knowledge bases (KBs) We propose a novel semantics for prioritized KBs inspired by grounded extensions and enjoys favourable properties. Our study also yields some results of independent interest concerning preference-based argumentation frameworks.
  arXiv  Detail & Related papers  (2020-03-12T12:38:37Z)

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.