Separating Positive and Negative Data Examples by Concepts and Formulas: The Case of Restricted Signatures

• URL: http://arxiv.org/abs/2007.02669v1
• Date: Mon, 6 Jul 2020 11:58:02 GMT
• Title: Separating Positive and Negative Data Examples by Concepts and Formulas: The Case of Restricted Signatures
• Abstract summary: 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.
• Score: 23.800397174740986
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the separation of positive and negative data examples in terms of description logic (DL) concepts and formulas of decidable FO fragments, in the presence of an ontology. In contrast to previous work, we add a signature that specifies a subset of the symbols from the data and ontology that can be used for separation. We consider weak and strong versions of the resulting problem that differ in how the negative examples are treated. Our main results are that (a projective form of) the weak version is decidable in $\mathcal{ALCI}$ while it is undecidable in the guarded fragment GF, the guarded negation fragment GNF, and the DL $\mathcal{ALCFIO}$, and that strong separability is decidable in $\mathcal{ALCI}$, GF, and GNF. We also provide (mostly tight) complexity bounds.

Related papers

• When Hard Negatives Hurt: Bridging the Generative-Discriminative Gap in Hard Negative Synthesis for Retrieval [45.5843471557695]
  We show that naively incorporating generated negatives into contrastive learning often degrades retrieval performance.<n>Our analysis reveals two compounding failure modes: discriminative-agnostic generation and source-dependent shortcuts.<n>To close this gap, we propose CausalNeg consisting of two main modules.
  arXiv  Detail & Related papers  (2026-05-31T15:48:30Z)
• Revisiting subword tokenization: A case study on affixal negation in large language models [57.75279238091522]
  We measure the impact of affixal negation on modern English large language models (LLMs) We conduct experiments using LLMs with different subword tokenization methods. We show that models can, on the whole, reliably recognize the meaning of affixal negation.
  arXiv  Detail & Related papers  (2024-04-03T03:14:27Z)
• LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Provers [60.009969929857704]
  Logical reasoning is an important task for artificial intelligence with potential impacts on science, mathematics, and society. In this work, we reformulating such tasks as modular neurosymbolic programming, which we call LINC. We observe significant performance gains on FOLIO and a balanced subset of ProofWriter for three different models in nearly all experimental conditions we evaluate.
  arXiv  Detail & Related papers  (2023-10-23T17:58:40Z)
• Your Negative May not Be True Negative: Boosting Image-Text Matching with False Negative Elimination [62.18768931714238]
  We propose a novel False Negative Elimination (FNE) strategy to select negatives via sampling. The results demonstrate the superiority of our proposed false negative elimination strategy.
  arXiv  Detail & Related papers  (2023-08-08T16:31:43Z)
• Augmentation-Free Graph Contrastive Learning of Invariant-Discriminative Representations [2.0621215354103635]
  We propose an augmentation-free graph contrastive learning method, invariant-discriminative graph contrastive learning (iGCL) iGCL designs the invariant-discriminative loss (ID loss) to learn invariant and discriminative representations. Our theoretical analysis explains the effectiveness of ID loss from the perspectives of the redundancy reduction criterion, canonical correlation analysis, and information bottleneck principle.
  arXiv  Detail & Related papers  (2022-10-15T17:36:04Z)
• Debiased Contrastive Learning of Unsupervised Sentence Representations [88.58117410398759]
  Contrastive learning is effective in improving pre-trained language models (PLM) to derive high-quality sentence representations. Previous works mostly adopt in-batch negatives or sample from training data at random. We present a new framework textbfDCLR to alleviate the influence of these improper negatives.
  arXiv  Detail & Related papers  (2022-05-02T05:07:43Z)
• Structure-Aware Hard Negative Mining for Heterogeneous Graph Contrastive Learning [21.702342154458623]
  This work investigates Contrastive Learning (CL) on Graph Neural Networks (GNNs) We first generate multiple semantic views according to metapaths and network schemas. We then push node embeddings corresponding to different semantic views close to each other (positives) and pulling other embeddings apart (negatives) Considering the complex graph structure and the smoothing nature of GNNs, we propose a structure-aware hard negative mining scheme.
  arXiv  Detail & Related papers  (2021-08-31T14:44:49Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  In high stake applications, active experimentation may be considered too risky and thus data are often collected passively. While in simple cases, such as in bandits, passive and active data collection are similarly effective, the price of passive sampling can be much higher when collecting data from a system with controlled states.
  arXiv  Detail & Related papers  (2021-06-18T07:54:23Z)
• Examining and Combating Spurious Features under Distribution Shift [94.31956965507085]
  We define and analyze robust and spurious representations using the information-theoretic concept of minimal sufficient statistics. We prove that even when there is only bias of the input distribution, models can still pick up spurious features from their training data. Inspired by our analysis, we demonstrate that group DRO can fail when groups do not directly account for various spurious correlations.
  arXiv  Detail & Related papers  (2021-06-14T05:39:09Z)
• Understanding Hard Negatives in Noise Contrastive Estimation [21.602701327267905]
  We develop analytical tools to understand the role of hard negatives. We derive a general form of the score function that unifies various architectures used in text retrieval.
  arXiv  Detail & Related papers  (2021-04-13T14:42:41Z)
• Adversarial Robustness: What fools you makes you stronger [1.14219428942199]
  We prove an exponential separation for the sample complexity between the PAC-learning model and a version of the Equivalence-Query-learning model. We show that this separation has interesting implications for adversarial robustness. We explore a vision of designing an adaptive defense that in the presence of an attacker computes a model that is provably robust.
  arXiv  Detail & Related papers  (2021-02-10T15:00:24Z)
• Logical Separability of Labeled Data Examples under Ontologies [23.800397174740986]
  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.
  arXiv  Detail & Related papers  (2020-07-03T11:00:47Z)

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.