On the Foundations of Conflict-Driven Solving for Hybrid MKNF Knowledge Bases

• URL: http://arxiv.org/abs/2408.09626v1
• Date: Mon, 19 Aug 2024 01:13:02 GMT
• Title: On the Foundations of Conflict-Driven Solving for Hybrid MKNF Knowledge Bases
• Authors: Riley Kinahan, Spencer Killen, Kevin Wan, Jia-Huai You,
• Abstract summary: 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.
• Score: 1.6424391774944478
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hybrid MKNF Knowledge Bases (HMKNF-KBs) constitute a formalism for tightly integrated reasoning over closed-world rules and open-world ontologies. This approach allows for accurate modeling of real-world systems, which often rely on both categorical and normative reasoning. Conflict-driven solving is the leading approach for computationally hard problems, such as satisfiability (SAT) and answer set programming (ASP), in which MKNF is rooted. This paper investigates the theoretical underpinnings required for a conflict-driven solver of HMKNF-KBs. The approach 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.

Related papers

• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  The framework combines Monte Carlo Tree Search (MCTS) with iterative Self-Refine to optimize the reasoning path. The framework has been tested on general and advanced benchmarks, showing superior performance in terms of search efficiency and problem-solving capability.
  arXiv  Detail & Related papers  (2024-10-03T18:12:29Z)
• Unified continuous-time q-learning for mean-field game and mean-field control problems [4.416317245952636]
  We introduce the integrated q-function in decoupled form (decoupled Iq-function) and establish its martingale characterization together with the value function. We devise a unified q-learning algorithm for both mean-field game (MFG) and mean-field control (MFC) problems. For several examples in the jump-diffusion setting, within and beyond the LQ framework, we can obtain the exact parameterization of the decoupled Iq-functions and the value functions.
  arXiv  Detail & Related papers  (2024-07-05T14:06:59Z)
• BoardgameQA: A Dataset for Natural Language Reasoning with Contradictory Information [11.299785330182004]
  Language Models (LMs) have demonstrated complex reasoning capacities even without any finetuning. This paper formulates the problem of reasoning with contradictory information guided by preferences over sources as the classical problem of defeasible reasoning. We benchmark various LMs on BoardgameQA and the results reveal a significant gap in the reasoning capacity of state-of-the-art LMs on this problem.
  arXiv  Detail & Related papers  (2023-06-13T17:39:20Z)
• 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)
• Deep Reinforcement Learning for Orienteering Problems Based on Decomposition [13.332999086010718]
  This paper presents a new method for solving an orienteering problem (OP) by breaking it down into two parts: a knapsack problem (KP) and a traveling salesman problem (TSP) A KP solver is responsible for picking nodes, while a TSP solver is responsible for designing the proper path and assisting the KP solver in judging constraint violations. Experimental results show that the proposed algorithm can outperform conventional approaches in terms of training, inference, and ability generalization.
  arXiv  Detail & Related papers  (2022-04-25T11:45:31Z)
• Knowledge Base Question Answering by Case-based Reasoning over Subgraphs [81.22050011503933]
  We show that our model answers queries requiring complex reasoning patterns more effectively than existing KG completion algorithms. The proposed model outperforms or performs competitively with state-of-the-art models on several KBQA benchmarks.
  arXiv  Detail & Related papers  (2022-02-22T01:34:35Z)
• 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)
• Combining Rules and Embeddings via Neuro-Symbolic AI for Knowledge Base Completion [59.093293389123424]
  We show that not all rule-based Knowledge Base Completion models are the same. We propose two distinct approaches that learn in one case: 1) a mixture of relations and the other 2) a mixture of paths. When implemented on top of neuro-symbolic AI, which learns rules by extending Boolean logic to real-valued logic, the latter model leads to superior KBC accuracy outperforming state-of-the-art rule-based KBC by 2-10% in terms of mean reciprocal rank.
  arXiv  Detail & Related papers  (2021-09-16T17:54:56Z)
• Structural Learning of Probabilistic Sentential Decision Diagrams under Partial Closed-World Assumption [127.439030701253]
  Probabilistic sentential decision diagrams are a class of structured-decomposable circuits. We propose a new scheme based on a partial closed-world assumption: data implicitly provide the logical base of the circuit. Preliminary experiments show that the proposed approach might properly fit training data, and generalize well to test data, provided that these remain consistent with the underlying logical base.
  arXiv  Detail & Related papers  (2021-07-26T12:01:56Z)
• Unfounded Sets for Disjunctive Hybrid MKNF Knowledge Bases [0.0]
  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.
  arXiv  Detail & Related papers  (2021-02-25T20:44:42Z)
• Learning Likelihoods with Conditional Normalizing Flows [54.60456010771409]
  Conditional normalizing flows (CNFs) are efficient in sampling and inference. We present a study of CNFs where the base density to output space mapping is conditioned on an input x, to model conditional densities p(y|x)
  arXiv  Detail & Related papers  (2019-11-29T19:17:58Z)

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.