Logical Separability of Labeled Data Examples under Ontologies

• URL: http://arxiv.org/abs/2007.01610v2
• Date: Wed, 17 Aug 2022 12:29:41 GMT
• Title: Logical Separability of Labeled Data Examples under Ontologies
• Abstract summary: We investigate the existence of a separating formula for data in the presence of an ontology. For separation, we consider the description logic $mathcalALCI$, the guarded fragment, the two-variable fragment, and the guarded fragment. Our results are model-theoretic characterizations of (all variants of) separability, the comparison of the separating power of different languages, and the investigation of the computational complexity of deciding separability.
• Score: 23.800397174740986
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding a logical formula that separates positive and negative examples given in the form of labeled data items is fundamental in applications such as concept learning, reverse engineering of database queries, generating referring expressions, and entity comparison in knowledge graphs. In this paper, we investigate the existence of a separating formula for data in the presence of an ontology. Both for the ontology language and the separation language, we concentrate on first-order logic and the following important fragments thereof: the description logic $\mathcal{ALCI}$, the guarded fragment, the two-variable fragment, and the guarded negation fragment. For separation, we also consider (unions of) conjunctive queries. We consider several forms of separability that differ in the treatment of negative examples and in whether or not they admit the use of additional helper symbols to achieve separation. Our main results are model-theoretic characterizations of (all variants of) separability, the comparison of the separating power of different languages, and the investigation of the computational complexity of deciding separability.

Related papers

• Contrastive Analysis of Linguistic Representations in Large Language Model Outputs through Structured Synthetic Data Generation and Abstracted N-gram Associations [0.0]
  We present a methodological framework to discover linguistic and discursive patterns associated to different social groups.<n>We aim to characterize subtle expressions of bias, instead of diagnosing bias through a pre-determined list of words or expressions.
  arXiv  Detail & Related papers  (2026-04-19T12:02:17Z)
• Enhancing Retrieval Systems with Inference-Time Logical Reasoning [9.526027847179677]
  We propose a novel inference-time logical reasoning framework that explicitly incorporates logical reasoning into the retrieval process. Our method extracts logical reasoning structures from natural language queries and then composes the individual cosine similarity scores to formulate the final document scores.
  arXiv  Detail & Related papers  (2025-03-22T20:40:18Z)
• Neuro-Symbolic Contrastive Learning for Cross-domain Inference [13.649270716741535]
  inductive logic programming (ILP) excels at inferring logical relationships across diverse, sparse and limited datasets. This paper proposes a bridge between the two approaches: neuro-symbolic contrastive learning.
  arXiv  Detail & Related papers  (2025-02-13T11:48:46Z)
• Model Alignment Search [0.0]
  We introduce Model Alignment Search (MAS), a method for causally exploring distributed representational similarity as it relates to behavior. We first show that the method can be used to transfer values of specific causal variables between networks with different training seeds and different architectures. We then explore open questions in number cognition by comparing different types of numeric representations in models trained on structurally different tasks.
  arXiv  Detail & Related papers  (2025-01-10T18:39:29Z)
• 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)
• An Encoding of Abstract Dialectical Frameworks into Higher-Order Logic [57.24311218570012]
  This approach allows for the computer-assisted analysis of abstract dialectical frameworks. Exemplary applications include the formal analysis and verification of meta-theoretical properties.
  arXiv  Detail & Related papers  (2023-12-08T09:32:26Z)
• LOGICSEG: Parsing Visual Semantics with Neural Logic Learning and Reasoning [73.98142349171552]
  LOGICSEG is a holistic visual semantic that integrates neural inductive learning and logic reasoning with both rich data and symbolic knowledge. During fuzzy logic-based continuous relaxation, logical formulae are grounded onto data and neural computational graphs, hence enabling logic-induced network training. These designs together make LOGICSEG a general and compact neural-logic machine that is readily integrated into existing segmentation models.
  arXiv  Detail & Related papers  (2023-09-24T05:43:19Z)
• 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)
• Tackling Morphological Analogies Using Deep Learning -- Extended Version [8.288496996031684]
  Analogical proportions are statements of the form "A is to B as C is to D" We propose an approach using deep learning to detect and solve morphological analogies. We demonstrate our model's competitive performance on analogy detection and resolution over multiple languages.
  arXiv  Detail & Related papers  (2021-11-09T13:45:23Z)
• Weakly-Supervised Aspect-Based Sentiment Analysis via Joint Aspect-Sentiment Topic Embedding [71.2260967797055]
  We propose a weakly-supervised approach for aspect-based sentiment analysis. We learn sentiment, aspect> joint topic embeddings in the word embedding space. We then use neural models to generalize the word-level discriminative information.
  arXiv  Detail & Related papers  (2020-10-13T21:33:24Z)
• Few-shot Visual Reasoning with Meta-analogical Contrastive Learning [141.2562447971]
  We propose to solve a few-shot (or low-shot) visual reasoning problem, by resorting to analogical reasoning. We extract structural relationships between elements in both domains, and enforce them to be as similar as possible with analogical learning. We validate our method on RAVEN dataset, on which it outperforms state-of-the-art method, with larger gains when the training data is scarce.
  arXiv  Detail & Related papers  (2020-07-23T14:00:34Z)
• Separating Positive and Negative Data Examples by Concepts and Formulas: The Case of Restricted Signatures [23.800397174740986]
  We study the separation of positive and negative data examples in terms of description logic concepts and formulas. We consider weak and strong versions of the resulting problem that differ in how the negative examples are treated.
  arXiv  Detail & Related papers  (2020-07-06T11:58:02Z)
• Logical Inferences with Comparatives and Generalized Quantifiers [18.58482811176484]
  A logical inference system for comparatives has not been sufficiently developed for use in the Natural Language Inference task. We present a compositional semantics that maps various comparative constructions in English to semantic representations via Category Grammar (CCG) We show that the system outperforms previous logic-based systems as well as recent deep learning-based models.
  arXiv  Detail & Related papers  (2020-05-16T11:11:48Z)
• A logic-based relational learning approach to relation extraction: The OntoILPER system [0.9176056742068812]
  We present OntoILPER, a logic-based relational learning approach to Relation Extraction. OntoILPER takes profit of a rich relational representation of examples, which can alleviate the drawbacks. The proposed relational approach seems to be more suitable for Relation Extraction than statistical ones.
  arXiv  Detail & Related papers  (2020-01-13T12:47:49Z)

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.