=Paper=
{{Paper
|id=Vol-3739/abstract-9
|storemode=property
|title=On the Power and Limitations of Examples for Description Logic Concepts (Extended Abstract)
|pdfUrl=https://ceur-ws.org/Vol-3739/abstract-9.pdf
|volume=Vol-3739
|authors=Balder ten Cate,Raoul Koudijs,Ana Ozaki
|dblpUrl=https://dblp.org/rec/conf/dlog/CateKO24
}}
==On the Power and Limitations of Examples for Description Logic Concepts (Extended Abstract)==
https://ceur-ws.org/Vol-3739/abstract-9.pdf
On the Power and Limitations of Examples for Description
Logic Concepts (Extended Abstract)
Balder ten Cate1 , Raoul Koudijs2 and Ana Ozaki3,2
1
University of Amsterdam, ILLC - Postbus 94242, 1090 GE Amsterdam, The Netherlands
2
University of Bergen, HIB - ThormΓΈhlens gate 55 5006 Bergen, Norway
3
University of Oslo, GaustadallΓ©en 23B 0373 Oslo, Norway
Abstract
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 efficient 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.
Keywords
Finite Characterisations, Concept Languages, Concept Learning, Membership Queries
1. Introduction
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 [1, 2, 3, 4, 5, 6, 7]. In this extended abstract we report on
a recent study [8] into the utility of labeled examples for describing description logic concepts.
Example 1. In the description logic β°β, we may define the concept of an e-bike by means of the concept
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.
Contains
Bicycle soltera2 βββββ li360Wh Battery
Contains
Bicycle px10 βββββ b12 Basket
Contains
Car teslaY βββββ 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.
DL 2024: 37th International Workshop on Description Logics, June 18β21, 2024, Bergen, Norway
$ anaoz@uio.no (A. Ozaki)
Β https://www.mn.uio.no/ifi/personer/vit/anaoz/ (A. Ozaki)
0000-0002-3889-6207 (A. Ozaki)
Β© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
Example 2. This example involves πβπ-concepts over a signature (Ξ£πΆ , Ξ£π
) consisting of the concept
names Ξ£π
= {Animal, Cat, Dog, Red} and no role names, i.e., Ξ£π
= β
. Let πͺ furthermore be the DL-
Lite ontology {Cat β Animal, Dog β Animal, Cat β Β¬Dog} expressing that Cat and Dog are disjoint
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:
β΅
Animal, Red π πβ² Animal
β΅
Red π πβ²
β΅
Cat, Animal , Red π πβ² Cat, Animal
Dog, Animal, Red π πβ² Dog, Animal
Note that β satisfies the ontology πͺ. In the context of this interpretation, it is clear that
β’ π is a positive example for πΆ.
β’ All the other elements (that is, π, πβ² , π, πβ² , πβ² , π, and πβ² ) are negative examples for πΆ.
As it turns out, every πβπ-concept (over the specified signature) that fits these labeled examples is equivalent
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.
An ontology can help reduce the number of examples needed to uniquely characterize πΆ. Moreover, it
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 efficient computability of finite characteri- L (β,β,β₯,-,β,β,β€,β₯,Β¬) = ALCQI
zations, i.e., finite sets of labeled examples that uniquely
characterize a single concept. Finite characterizations are
fragments that do not admit finite
relevant not only for illustrating a complex concept to a characterizations
user (e.g., to verify the correctness of a concept expres- L(β,β₯,-,β,β€)
L(β,β,β₯,β,β€)
sion obtained using machine learning techniques). Their L(β,-,β,β,β€,β₯)
L(β,β,β,β)
existence is a necessary condition for exact learnability ?
with membership queries [9]. Furthermore, from a more
fragments that admit finite L(β₯,-,β)
fundamental point of view, by studying the existence of characterizations
L(β,-,β,β€,β₯)
finite characterizations, we gain insight into the power and
limitations of labeled examples as a medium for describing
fragments that admit
concepts. poly-time computable
characterizations
Finite characterisations were first studied in the com-
putational learning theory literature under the name of L(β,β)
teaching sets, with a corresponding notion of teaching di-
mension, measuring the maximal size of minimal teaching Figure 1: Summary of Thm. 1 and 2.
sets of some class of concepts [10]. Several recent works
study finite characterisations for description logic concepts ([11, 12] for β°ββ; [13] for temporal instance
queries); a systematic study of finite characterizations for syntactic fragments of modal logic was carried
out in [14].
In this prior literature, two types of examples have been considered, namely open-world examples (cf.
[12, 15]) and closed-world examples (e.g. [13, 16]). An open-world example is a pair (π, π), where π is an
ABox and π is an individual name. Such a pair is a positive example for a concept expression πΆ relative
to an ontology πͺ if π belongs to the certain answers of πΆ w.r.t. π and it is a negative example otherwise.
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.
2. Contributions
First contribution: We study the difference in descriptive power between closed-world examples
and open-world examples for description logic concepts. It was shown in [12] that β°ββ admits finite
characterizations with open-world examples under DL-Lite ontologies. We show that the same does not
hold with closed-world examples. On the other hand, for non-monotone concept languages, e.g. with
β or Β¬, it is necessary to work with closed-world rather than open-world examples. For instance,
the concepts βπ
.π΄ and βπ
.π΅ do not have any positive open-world examples (relative to an empty
ontology), and hence neither can be uniquely characterized by open-world examples.
Second contribution: We systematically study the existence of, and the complexity of computing,
finite characterisations for concept expressions in a wide range of description logics, using closed-world
examples. Specifically, we look at concept languages β(O) generated by a set of connectives O, where
{β, β} β O β {β, β, β₯, β, β, β, β€, β₯, Β¬}. In other words, we look at fragments of the description logic
πβππ¬β that contain at least the β and β constructors from β°β. Within this framework, we obtain an
almost complete classification of the concept languages that admit finite characterizations.
Theorem 1. Let {β, β} β O β {β, β, β₯, β, β, β, β€, β₯, Β¬}.
1. If O is a subset of {β, β, β, β, β€, β₯}, {β, β, β, β} or {β, β, β₯, β, β€} then β(O) admits finite
characterizations with closed-world examples.
2. Otherwise β(O) does not admit finite characterizations with closed-world examples, except possibly
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 [11] and [14].
Our main novel technical contributions are a construction of finite characterisations for β(β, β, β₯, β, β€)
and complementary negative results for β(β₯, β₯), β(β₯, β) and β(β, β, β, β). The construction of finite
characterisations for β(β, β, β₯, β, β€) is non-elementary. We give an elementary (doubly exponential)
construction for β(β, β₯, β, β€), via a novel polynomial-time algorithm for constructing frontiers (i.e.,
complete sets of minimal weakenings) of β(β, β₯, β, β€)-concepts. It also follows that subsumptions
between such concepts can be checked in polynomial time.
Next, we study which concept languages β(O) admit polynomial-time computable characterisations,
i.e., have a polynomial-time algorithm to compute finite characterisations.
Theorem 2. Let {β, β} β O β {β, β, β₯, β, β, β, β€, β₯, Β¬}.
1. If O is a subset of {β, β, β, β€, β₯}, then β(O) admits polynomial-time computable characterizations
with closed-world examples.
2. Otherwise, β(O) does not admit polynomial-time computable characterizations with closed-world
examples, assuming PΜΈ=NP.
The first item follows from known results [11]; we prove the second by establishing an exponential
lower bound on characterisations for β(β, β₯, β) and NP-hardness of computing characterisations for
β(β, β, β). Theorems 1 and 2 are summarized in Figure 1. Theorems 1 and 2 still holds true when
βadmits finite (polynomial) time computable characterisationsβ is replaced with βis exact learnable
from membership queries in finite (polynomial) timeβ. On the one hand, existence finite (polynomial)
characterisations is a necessary condition for (polynomial) membership query learnability, so the
negative results transfer immediately. On the other hand, finite characterisations always enable a brute
force membership query algorithm, and [11] shows that β(β, β, β, β€) is polynomial-time learnable
from membership queries.
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
fitting concept is equivalent to the input concept πΆ relative to πͺ (cf. Example 2).
Theorem 3. Let {β, β} β O β {β, β, β₯, β, β, β, β€, β₯, Β¬}.
1. If O is a subset of {β, β, β€, β₯}, then β(O) admits finite characterizations with closed-world
examples w.r.t. all DL-Lite ontologies.
2. Otherwise, β(O) does not admit finite characterizations with closed-world examples w.r.t. all DL-Lite
ontologies, except possibly if {β, β, β} β O β {β, β, β, β€, β₯}.
In fact, for β(β, β, β€, β₯)-concepts πΆ and DL-Lite ontologies πͺ such that πΆ is satisfiable w.r.t. πͺ, a finite
characterisation can be computed in polynomial time.
Acknowledgements
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.
References
[1] J. Lehmann, Dl-learner: Learning concepts in description logics, Journal of Machine Learning
Research 10 (2009) 2639β2642.
[2] M. Funk, J. C. Jung, C. Lutz, H. Pulcini, F. Wolter, Learning description logic concepts: When can
positive and negative examples be separated?, in: IJCAI, 2019, pp. 1682β1688.
[3] M. Funk, J. C. Jung, C. Lutz, Actively learning concept and conjunctive queries under β°βπ -
ontologies, in: IJCAI, 2021, pp. 1887β1893.
[4] A. Ozaki, Learning description logic ontologies: Five approaches. where do they stand?, KΓΌn-
stliche Intell. 34 (2020) 317β327. URL: https://doi.org/10.1007/s13218-020-00656-9. doi:10.1007/
S13218-020-00656-9.
[5] N. Fanizzi, C. dβAmato, F. Esposito, DL-FOIL concept learning in description logics, in: Proc. of
ILP, 2008, pp. 107β121.
[6] L. Iannone, I. Palmisano, N. Fanizzi, An algorithm based on counterfactuals for concept learning
in the semantic web, Appl. Intell. 26 (2007) 139β159.
[7] J. Lehmann, P. Hitzler, Concept learning in description logics using refinement operators, Mach.
Learn. 78 (2010) 203β250.
[8] B. ten Cate, R. Koudijs, A. Ozaki, On the power and limitations of examples for description logic
concepts, in: Proc. of IJCAI, 2024, pp. 739β745.
[9] D. Angluin, Queries and concept learning, Mach. Learn. 2 (1987) 319β342.
[10] S. Goldman, M. Kearns, On the complexity of teaching, Journal of Computer and System Sci-
ences 50 (1995) 20β31. URL: https://www.sciencedirect.com/science/article/pii/S0022000085710033.
doi:https://doi.org/10.1006/jcss.1995.1003.
[11] B. ten Cate, V. Dalmau, Conjunctive queries: Unique characterizations and exact learnability, ACM
Trans. Database Syst. 47 (2022). URL: https://doi.org/10.1145/3559756. doi:10.1145/3559756.
[12] M. Funk, J. C. Jung, C. Lutz, Frontiers and exact learning of ELI queries under dl-lite ontologies,
in: IJCAI, 2022, pp. 2627β2633.
[13] M. Fortin, B. Konev, V. Ryzhikov, Y. Savateev, F. Wolter, M. Zakharyaschev, Unique Characteris-
ability and Learnability of Temporal Instance Queries, in: Proceedings of the 19th International
Conference on Principles of Knowledge Representation and Reasoning, 2022, pp. 163β173. URL:
https://doi.org/10.24963/kr.2022/17. doi:10.24963/kr.2022/17.
[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.