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 specification, and concept refinement) as well as for illustrating concept expressions to a user or domain expert. We investigate the power of labeled examples for describing description logic concepts. Specifically, we systematically study the existence and eficient computability of finite characterizations , i.e., finite sets of labeled examples that uniquely characterize a single concept, for a wide variety of description logics between ℰℒ and ℒℐ, both without an ontology and in the presence of a DL-Lite ontology. Finite characterizations are relevant for debugging purposes, and their existence is a necessary condition for exact learnability with membership queries.
Labeled examples (i.e., positive and negative examples) are an attractive medium for communicating
complex concepts. They are useful as data for deriving concept expressions (such as in concept learning,
interactive concept specification, and example-driven concept refinement) as well as for illustrating
concept expressions to a user or domain expert [
expression := Bicycle ⊓ ∃Contains.Battery. Suppose we wish to illustrate by a collection of positive and negative examples. What would be a good choice of examples? Take the interpretation ℐ consisting of the following facts.
Bicycle soltera2− →−− − Contains
Bicycle px10− →−− −
Contains Contains li360Wh Battery b12 Basket li81kWh Battery In the context of this interpretation ℐ, it is clear that soltera2 is a positive example for , and px10 and teslaY are negative examples for . In fact, as it turns out, is the only ℰ ℒ-concept (up to equivalence) that is consistent with, or ‘ fits ’ these three labeled examples. In other words, these three labeled examples “uniquely characterize” within the class of all ℰ ℒ-concepts. This shows that the above three labeled examples are a good choice of examples. Further examples would be redundant. Note, however, that this depends on the choice of the description logic. For instance, the richer concept language ℒ allows for concept expressions such as Bicycle ⊓ ¬∃Contains.Basket that also fit.
names Σ = {Animal, Cat, Dog, Red} and no role names, i.e., Σ = ∅. Let furthermore be the DL
subconcepts of Animal. Consider the concept := Cat ⊓ Red. If we wish to illustrate by a collection of positive and negative examples, what would be a good choice of examples? Take the interpretation ℐ consisting of the following facts:
Red ⊵
′ ′ Cat, Animal ′ Dog, Animal
• is a positive example for .
• All the other elements (that is, , ′, , ′, ′, , and ′) are negative examples for .
to under the ontology . In other words, the above labeled examples uniquely characterize relative to and the signature (Σ , Σ ). On the other hand, these labeled examples do not uniquely characterize in the absence of an ontology, because, for instance, Cat ⊓ Red ⊓ ¬Dog and Cat ⊓ Red ⊓ Animal also fit but are not equivalent to in the absence of the ontology.
can help avoid unnatural examples. For instance, without an ontology, a unique characterization for would need to include negative examples satisfying Cat ⊓ Red ⊓ Dog and Cat ⊓ Red ⊓ ¬Animal.
Motivated by the above examples, we investigate the
existence and eficient computability of finite characteri- L (∀,∃,≥,-,⊓,⊔,⊤,⊥,¬) = ALCQI
zations, i.e., finite sets of labeled examples that uniquely
characterize a single concept. Finite characterizations are
relevant not only for illustrating a complex concept to a fragmenctshathraacttdeoriznaottioandsmit finite
suisoenr o(eb.tga.i,nteodvuesriinfyg tmhaecchoinrreecletanrensisnogftaecchonniqceupets)e.xTphreeisr- L(∃,-,⊓,⊔,⊤,⊥) L(∀,∃,⊓,⊔) L(∀,∃,≥,⊓,⊤) L(∃,≥,-,⊓,⊤)
existence is a necessary condition for exact learnability ?
with membership queries [
Finite characterisations were first studied in the com- characterizations
putational learning theory literature under the name of L(∃,⊓)
teaching sets, with a corresponding notion of teaching
dimension, measuring the maximal size of minimal teaching Figure 1: Summary of Thm. 1 and 2.
sets of some class of concepts [
In this prior literature, two types of examples have been considered, namely open-world examples (cf.
[
In contrast, a closed-world example is a pair (ℐ, ) where ℐ is a finite interpretation satisfying the ontology , and is an element in the domain of ℐ. Such a pair is a positive example for a concept expression if ∈ ℐ , and it is a negative example otherwise.
First contribution: We study the diference in descriptive power between closed-world examples
and open-world examples for description logic concepts. It was shown in [
1. If O is a subset of {∃, − , ⊓, ⊔, ⊤, ⊥}, {∀, ∃, ⊔, ⊓} or {∀, ∃, ≥ , ⊓, ⊤} then ℒ(O) admits finite characterizations with closed-world examples.
if {≥ , − , ⊓} ⊆ O ⊆ {∃ , ≥ , − , ⊓, ⊤}.
The above theorem identifies three maximal fragments of ℒℐ that admit finite characterisations.
It leaves open the status of essentially only two concept languages, namely ℒ(∃, ≥ , − , ⊓) and ℒ(∃, ≥
, − , ⊓, ⊤) (note that ∃ is definable in terms of ≥ ). The proof builds on prior results from [
i.e., have a polynomial-time algorithm to compute finite characterisations. Theorem 2. Let {∃, ⊓} ⊆ O ⊆ {∀ , ∃, ≥ , − , ⊓, ⊔, ⊤, ⊥, ¬}.
with closed-world examples.
examples, assuming P̸=NP.
The first item follows from known results [
Finally, we investigate finite characterizations relative to an ontology , where we require all the (positive and negative) examples to be interpretations satisfying the ontology , and require that every iftting concept is equivalent to the input concept relative to (cf. Example 2).
Theorem 3. Let {∃, ⊓} ⊆ O ⊆ {∀ , ∃, ≥ , − , ⊓, ⊔, ⊤, ⊥, ¬}.
examples w.r.t. all DL-Lite ontologies.
ontologies, except possibly if {∃, ⊓, ⊔} ⊆ O ⊆ {∃ , ⊓, ⊔, ⊤, ⊥}.
characterisation can be computed in polynomial time.
Balder ten Cate is supported by the European Union’s Horizon 2020 research and innovation programme under grant MSCA-101031081. Raoul Koudijs and Ana Ozaki are supported by the Research Council of Norway, project number 316022, led by Ana Ozaki. [14] B. t. Cate, R. Koudijs, Characterising modal formulas with examples, ACM Trans. Comput. Logic (2024). URL: https://doi.org/10.1145/3649461. doi:10.1145/3649461, just Accepted. [15] J. C. Jung, V. Ryzhikov, F. Wolter, M. Zakharyaschev, Temporalising unique characterisability and learnability of ontology-mediated queries (extended abstract), in: O. Kutz, C. Lutz, A. Ozaki (Eds.), Proceedings of the 36th International Workshop on Description Logics (DL 2023) co-located with the 20th International Conference on Principles of Knowledge Representation and Reasoning and the 21st International Workshop on Non-Monotonic Reasoning (KR 2023 and NMR 2023)., Rhodes, Greece, September 2-4, 2023, volume 3515 of CEUR Workshop Proceedings, CEUR-WS.org, 2023.
URL: https://ceur-ws.org/Vol-3515/abstract-13.pdf. [16] L. De Raedt, Logical settings for concept-learning, Artificial Intelligence 95 (1997) 187–201. URL: https://www.sciencedirect.com/science/article/pii/S0004370297000416. doi:https://doi.org/ 10.1016/S0004-3702(97)00041-6.