Complexity and scalability of defeasible reasoning in many-valued weighted knowledge bases with typicality

• URL: http://arxiv.org/abs/2303.04534v2
• Date: Mon, 27 Mar 2023 17:12:47 GMT
• Title: Complexity and scalability of defeasible reasoning in many-valued weighted knowledge bases with typicality
• Authors: Mario Alviano, Laura Giordano, Daniele Theseider Dupr\'e
• Abstract summary: 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.
• Score: 4.447467536572624
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Weighted knowledge bases for description logics with typicality under a "concept-wise" multi-preferential semantics provide a logical interpretation of MultiLayer Perceptrons. In this context, Answer Set Programming (ASP) has been shown to be suitable for addressing defeasible reasoning in the finitely many-valued case, providing a $\Pi^p_2$ upper bound on the complexity of the problem, nonetheless leaving unknown the exact complexity and only providing a proof-of-concept implementation. This paper fulfils the lack by providing a $P^{NP[log]}$-completeness result and new ASP encodings that deal with weighted knowledge bases with large search spaces.

Related papers

• The Computational Complexity of Circuit Discovery for Inner Interpretability [0.30723404270319693]
  We study circuit discovery with classical and parameterized computational complexity theory. Our findings reveal a challenging complexity landscape. This framework allows us to understand the scope and limits of interpretability queries.
  arXiv  Detail & Related papers  (2024-10-10T15:22:48Z)
• Cost-Based Semantics for Querying Inconsistent Weighted Knowledge Bases [5.222978725954348]
  We consider weighted knowledge bases in which both axioms and assertions have (possibly infinite) weights. Two notions of certain and possible answer are defined by either considering interpretations whose cost does not exceed a given bound. Our main contribution is a comprehensive analysis of the combined and data complexity of bounded cost satisfiability and certain and possible answer recognition.
  arXiv  Detail & Related papers  (2024-07-30T11:56:02Z)
• Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning [89.89857766491475]
  We propose a complex reasoning schema over KG upon large language models (LLMs) We augment the arbitrary first-order logical queries via binary tree decomposition to stimulate the reasoning capability of LLMs. Experiments across widely used datasets demonstrate that LACT has substantial improvements(brings an average +5.5% MRR score) over advanced methods.
  arXiv  Detail & Related papers  (2024-05-02T18:12:08Z)
• 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)
• When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
  We propose complexity-impacted reasoning score (CIRS) to measure correlation between code and reasoning abilities. Specifically, we use the abstract syntax tree to encode the structural information and calculate logical complexity. Code will be integrated into the EasyInstruct framework at https://github.com/zjunlp/EasyInstruct.
  arXiv  Detail & Related papers  (2023-08-29T17:22:39Z)
• Learnability with PAC Semantics for Multi-agent Beliefs [38.88111785113001]
  The tension between deduction and induction is perhaps the most fundamental issue in areas such as philosophy, cognition and artificial intelligence. Valiant recognised that the challenge of learning should be integrated with deduction. Although weaker than classical entailment, it allows for a powerful model-theoretic framework for answering queries.
  arXiv  Detail & Related papers  (2023-06-08T18:22:46Z)
• Logical Message Passing Networks with One-hop Inference on Atomic Formulas [57.47174363091452]
  We propose a framework for complex query answering that decomposes the Knowledge Graph embeddings from neural set operators. On top of the query graph, we propose the Logical Message Passing Neural Network (LMPNN) that connects the local one-hop inferences on atomic formulas to the global logical reasoning. Our approach yields the new state-of-the-art neural CQA model.
  arXiv  Detail & Related papers  (2023-01-21T02:34:06Z)
• An ASP approach for reasoning on neural networks under a finitely many-valued semantics for weighted conditional knowledge bases [0.0]
  We consider conditional ALC knowledge bases with typicality in the finitely many-valued case. We exploit ASP and "asprin" for reasoning with the concept-wise multipreferences.
  arXiv  Detail & Related papers  (2022-02-02T16:30:28Z)
• 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)
• From LSAT: The Progress and Challenges of Complex Reasoning [56.07448735248901]
  We study the three challenging and domain-general tasks of the Law School Admission Test (LSAT), including analytical reasoning, logical reasoning and reading comprehension. We propose a hybrid reasoning system to integrate these three tasks and achieve impressive overall performance on the LSAT tests.
  arXiv  Detail & Related papers  (2021-08-02T05:43:03Z)
• 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)

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.