Separating Positive and Negative Data Examples by Concepts and Formulas: The Case of Restricted Signatures
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.
Code (0)
등록된 구현이 없습니다.
Tasks
NegationSimilar Papers 제목 키워드 기반
Learning temporal formulas from examples is hard
We study the problem of learning linear temporal logic (LTL) formulas from examples, as a first step towards expressing a property separating positive and negative instances in a way that is comprehensible for humans. In…
Logical Separability of Labeled Data Examples under Ontologies
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…
Knowledge GraphsNegationTowards interpretable, data-derived distributional meaning representations for reasoning: A dataset of properties and concepts
This paper proposes a framework for investigating which types of semantic properties are represented by distributional data. The core of our framework consists of relations between concepts and properties. We provide hyp…
On the Power and Limitations of Examples for Description Logic Concepts
Labeled examples (i.e., positive and negative examples) are an attractive medium for communicating complex concepts. They are useful for deriving concept expressions (such as in concept learning, interactive concept spec…
DSReg: Using Distant Supervision as a Regularizer
In this paper, we aim at tackling a general issue in NLP tasks where some of the negative examples are highly similar to the positive examples, i.e., hard-negative examples. We propose the distant supervision as a regula…
Multi-Task LearningReading Comprehensiontext-classificationText Classification