Unfounded Sets for Disjunctive Hybrid MKNF Knowledge Bases

• URL: http://arxiv.org/abs/2102.13162v1
• Date: Thu, 25 Feb 2021 20:44:42 GMT
• Title: Unfounded Sets for Disjunctive Hybrid MKNF Knowledge Bases
• Authors: Spencer Killen, Jia-Haui You
• Abstract summary: Disjunctive hybrid MKNF knowledge bases and ASP extend in some cases without increasing the complexity of reasoning tasks. The only known method of solving disjunctive hybrid MKNF knowledge bases is based on guess-and-verify. We formalize a notion of unfounded sets for these knowledge bases, identify lower bounds, and demonstrate how we might integrate these into a solver.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combining the closed-world reasoning of answer set programming (ASP) with the open-world reasoning of ontologies broadens the space of applications of reasoners. Disjunctive hybrid MKNF knowledge bases succinctly extend ASP and in some cases without increasing the complexity of reasoning tasks. However, in many cases, solver development is lagging behind. As the result, the only known method of solving disjunctive hybrid MKNF knowledge bases is based on guess-and-verify, as formulated by Motik and Rosati in their original work. A main obstacle is understanding how constraint propagation may be performed by a solver, which, in the context of ASP, centers around the computation of \textit{unfounded atoms}, the atoms that are false given a partial interpretation. In this work, we build towards improving solvers for hybrid MKNF knowledge bases with disjunctive rules: We formalize a notion of unfounded sets for these knowledge bases, identify lower complexity bounds, and demonstrate how we might integrate these developments into a solver. We discuss challenges introduced by ontologies that are not present in the development of solvers for disjunctive logic programs, which warrant some deviations from traditional definitions of unfounded sets. We compare our work with prior definitions of unfounded sets.

Related papers

• GIVE: Structured Reasoning with Knowledge Graph Inspired Veracity Extrapolation [108.2008975785364]
  Graph Inspired Veracity Extrapolation (GIVE) is a novel reasoning framework that integrates the parametric and non-parametric memories. Our method facilitates a more logical and step-wise reasoning approach akin to experts' problem-solving, rather than gold answer retrieval.
  arXiv  Detail & Related papers  (2024-10-11T03:05:06Z)
• On the Foundations of Conflict-Driven Solving for Hybrid MKNF Knowledge Bases [1.6424391774944478]
  This paper investigates the theoretical underpinnings required for a conflict-driven solver of HMKNF-KBs. It defines a set of completion and loop formulas, whose satisfaction characterizes MKNF models. This forms the basis for a set of nogoods, which in turn can be used as the backbone for a conflict-driven solver.
  arXiv  Detail & Related papers  (2024-08-19T01:13:02Z)
• A Knowledge-Injected Curriculum Pretraining Framework for Question Answering [70.13026036388794]
  We propose a general Knowledge-Injected Curriculum Pretraining framework (KICP) to achieve comprehensive KG learning and exploitation for Knowledge-based question answering tasks. The KI module first injects knowledge into the LM by generating KG-centered pretraining corpus, and generalizes the process into three key steps. The KA module learns knowledge from the generated corpus with LM equipped with an adapter as well as keeps its original natural language understanding ability. The CR module follows human reasoning patterns to construct three corpora with increasing difficulties of reasoning, and further trains the LM from easy to hard in a curriculum manner.
  arXiv  Detail & Related papers  (2024-03-11T03:42:03Z)
• Soft Reasoning on Uncertain Knowledge Graphs [85.1968214421899]
  We study the setting of soft queries on uncertain knowledge, which is motivated by the establishment of soft constraint programming. We propose an ML-based approach with both forward inference and backward calibration to answer soft queries on large-scale, incomplete, and uncertain knowledge graphs.
  arXiv  Detail & Related papers  (2024-03-03T13:13:53Z)
• Knowledge Crosswords: Geometric Knowledge Reasoning with Large Language Models [49.23348672822087]
  We propose Knowledge Crosswords, a benchmark consisting of incomplete knowledge networks bounded by structured factual constraints. The novel setting of geometric knowledge reasoning necessitates new LM abilities beyond existing atomic/linear multi-hop QA. We conduct extensive experiments to evaluate existing LLMs and approaches on Knowledge Crosswords.
  arXiv  Detail & Related papers  (2023-10-02T15:43:53Z)
• Complexity and scalability of defeasible reasoning in many-valued weighted knowledge bases with typicality [4.447467536572624]
  Weighted knowledge bases for description logics with typicality provide a logical interpretation of MultiLayer Perceptrons. ASP has been shown to be suitable for addressing defeasible reasoning in the finitely many-valued case. This paper provides a $PNP[log]$-completeness result and new ASP encodings that deal with weighted knowledge bases with large search spaces.
  arXiv  Detail & Related papers  (2023-03-08T12:08:53Z)
• DecAF: Joint Decoding of Answers and Logical Forms for Question Answering over Knowledge Bases [81.19499764899359]
  We propose a novel framework DecAF that jointly generates both logical forms and direct answers. DecAF achieves new state-of-the-art accuracy on WebQSP, FreebaseQA, and GrailQA benchmarks.
  arXiv  Detail & Related papers  (2022-09-30T19:51:52Z)
• A Fixpoint Characterization of Three-Valued Disjunctive Hybrid MKNF Knowledge Bases [0.0]
  We present a fixpoint construction that leverages head-cuts using an operator that iteratively captures three-valued models of disjunctive hybrid MKNF knowledge bases with disjunctive rules. This work also captures partial stable models of disjunctive logic programs since a program can be expressed as a disjunctive hybrid MKNF knowledge base with an empty answer.
  arXiv  Detail & Related papers  (2022-08-05T10:47:07Z)
• Logical blocks for fault-tolerant topological quantum computation [55.41644538483948]
  We present a framework for universal fault-tolerant logic motivated by the need for platform-independent logical gate definitions. We explore novel schemes for universal logic that improve resource overheads. Motivated by the favorable logical error rates for boundaryless computation, we introduce a novel computational scheme.
  arXiv  Detail & Related papers  (2021-12-22T19:00:03Z)
• Reasoning on Multi-Relational Contextual Hierarchies via Answer Set Programming with Algebraic Measures [13.245718532835864]
  Contextualized Knowledge Repository (CKR) is rooted in description logics but links on the reasoning side strongly to logic programs. We present a generalization of CKR hierarchies to multiple contextual relations, along with their interpretation of defeasible axioms and preference. We show that for a relevant fragment of CKR hierarchies with multiple contextual relations, query answering can be realized with the popular asprin framework.
  arXiv  Detail & Related papers  (2021-08-06T13:06:45Z)
• Revisiting the Prepositional-Phrase Attachment Problem Using Explicit Commonsense Knowledge [1.0312968200748118]
  We argue that explicit commonsense knowledge bases can provide an essential ingredient for making good attachment decisions. Our results suggest that the commonsense knowledge-based approach can provide the best of both worlds, integrating rule-based and statistical techniques.
  arXiv  Detail & Related papers  (2021-02-01T15:48:36Z)

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.