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.