Constructive Interpolation and Concept-Based Beth Definability for Description Logics via Sequents

• URL: http://arxiv.org/abs/2404.15840v3
• Date: Fri, 18 Oct 2024 11:22:32 GMT
• Title: Constructive Interpolation and Concept-Based Beth Definability for Description Logics via Sequents
• Authors: Tim S. Lyon, Jonas Karge,
• Abstract summary: We introduce a constructive method for establishing the concept-based Beth definability property (CBP) based on sequent systems. Using the highly expressive DL RIQ as a case study, we show how certain interpolants can be computed from sequent calculus. This is the first sequent-based approach to computing interpolants and definitions within the context of description logics.
• Score: 0.0
• License:
• Abstract: We introduce a constructive method applicable to a large number of description logics (DLs) for establishing the concept-based Beth definability property (CBP) based on sequent systems. Using the highly expressive DL RIQ as a case study, we introduce novel sequent calculi for RIQ-ontologies and show how certain interpolants can be computed from sequent calculus proofs, which permit the extraction of explicit definitions of implicitly definable concepts. To the best of our knowledge, this is the first sequent-based approach to computing interpolants and definitions within the context of DLs, as well as the first proof that RIQ enjoys the CBP. Moreover, due to the modularity of our sequent systems, our results hold for restrictions of RIQ, and are applicable to other DLs by suitable modifications.

Related papers

• FI-CBL: A Probabilistic Method for Concept-Based Learning with Expert Rules [2.2120851074630177]
  The main idea behind the method is to divide each concept-annotated image into patches, to transform the patches into embeddings by using an autoencoder, and to cluster the embeddings. To find concepts of a new image, the method implements the frequentist inference by computing prior and posterior probabilities of concepts. Numerical experiments show that FI-CBL outperforms the concept bottleneck model in cases when the number of training data is small.
  arXiv  Detail & Related papers  (2024-06-28T13:05:17Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models. A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters. We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
  arXiv  Detail & Related papers  (2023-10-05T07:10:40Z)
• 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)
• Modeling Hierarchical Reasoning Chains by Linking Discourse Units and Key Phrases for Reading Comprehension [80.99865844249106]
  We propose a holistic graph network (HGN) which deals with context at both discourse level and word level, as the basis for logical reasoning. Specifically, node-level and type-level relations, which can be interpreted as bridges in the reasoning process, are modeled by a hierarchical interaction mechanism.
  arXiv  Detail & Related papers  (2023-06-21T07:34:27Z)
• Querying Circumscribed Description Logic Knowledge Bases [9.526604375441073]
  Circumscription is one of the main approaches for defining non-monotonic description logics. We prove decidability of (U)CQ evaluation on circumscribed DL KBs. We also study the much simpler atomic queries (AQs)
  arXiv  Detail & Related papers  (2023-06-07T15:50:15Z)
• 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)
• 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)
• Entropy-based Logic Explanations of Neural Networks [24.43410365335306]
  We propose an end-to-end differentiable approach for extracting logic explanations from neural networks. The method relies on an entropy-based criterion which automatically identifies the most relevant concepts. We consider four different case studies to demonstrate that: (i) this entropy-based criterion enables the distillation of concise logic explanations in safety-critical domains from clinical data to computer vision; (ii) the proposed approach outperforms state-of-the-art white-box models in terms of classification accuracy.
  arXiv  Detail & Related papers  (2021-06-12T15:50:47Z)
• An ASP approach for reasoning in a concept-aware multipreferential lightweight DL [0.0]
  We develop a concept aware multi-preferential semantics for dealing with typicality in description logics. The construction of the concept-aware multipreference semantics is related to Brewka's framework for qualitative preferences.
  arXiv  Detail & Related papers  (2020-06-08T07:15:38Z)
• An ASP-Based Approach to Counterfactual Explanations for Classification [0.0]
  We propose answer-set programs that specify and compute counterfactual interventions as a basis for causality-based explanations to decisions produced by classification models. They can be applied with black-box models and models that can be specified as logic programs, such as rule-based classifiers.
  arXiv  Detail & Related papers  (2020-04-28T01:36:26Z)

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.