On the Power and Limitations of Examples for Description Logic Concepts

Balder ten Cate, Raoul Koudijs, Ana Ozaki · 2024

Read On the Power and Limitations of Examples for Description Logic Concepts by Balder ten Cate, Raoul Koudijs, Ana Ozaki (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-17345.txt.

Introduction

Balder ten Cate, Raoul Koudijs, and Ana Ozaki studied what examples can say about formal concepts in a 2024 logic paper. Labeled examples, cases marked yes or no, are a handy way to share a complex concept. They serve both to build concept formulas and to show what a formula means.

The team ask when a finite set of examples pins down one concept with no rival left. They map that question across a wide range of description logics, from light to rich forms, with and without a background theory. They also ask how hard such a set is to compute. The results draw the line between concepts examples can teach and those they cannot.

Catalog record

CREATORBalder ten Cate, Raoul Koudijs, Ana Ozaki
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE180 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-17345

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Power and Limitations of Examples for Description Logic Concepts Balder ten Cate, Raoul Koudijs, Ana Ozaki 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 characterisations , i.e., finite sets of labeled examples that uniquely characterize a single concept, for a wide variety of description logics between ℰ ​ ℒ {\cal E\!L} and 𝒜 ​ ℒ ​ 𝒞 ​ 𝒬 ​ ℐ \mathcal{ALCQI} ,both without an ontology and in the presence of a DL-Lite ontology. Finite characterisations are relevant for debugging purposes, and their existence is a necessary condition for exact learnability with 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 Lehmann 2009 ; Funk et al. 2019 ; Funk et al. 2021 ; Ozaki 2020 ; Fanizzi et al. 2008 ; Iannone et al. 2007 ; Lehmann and Hitzler 2010 . Here, we study the utility of labelled examples for characterising description logic concepts, where examples are finite interpretations that can be either positively or negatively labelled. Example 1.1 . In the description logic {\cal E\!L} , we may define the concept of an e-bike by means of the concept expression C\text{ ~ := ~ }\text{Bicycle}\sqcap\exists\text{Contains}.\text{Battery} Suppose we wish to illustrate C by a collection of positive and negative examples. What would be a good choice of examples? Take the interpretation \mathcal{I} consisting of the following facts. Bicycle soltera2 \xrightarrow{\text{Contains}} li360Wh Battery Bicycle px10 \xrightarrow{\text{Contains}} b12 Basket Car teslaY \xrightarrow{\text{Contains}} li81kWh Battery In the context of this interpretation \mathcal{I} , it is clear that • soltera2 is a positive example for C , and • px10 and teslaY are negative examples for C In fact, as it turns out, C is the only {\cal E\!L} -concept (up to equivalence) that fits these three labeled examples. In other words, these three labeled examples “uniquely characterize” C within the class of all {\cal E\!L} -concepts. This shows that the above three labeled examples are a good choice of examples. Adding any additional examples would be redundant. Note, however, that this depends on the choice of description logic. For instance, the richer concept language {\cal ALC} allows for other concept expressions such as \text{Bicycle}\sqcap\neg\exists\text{Contains}.\text{Basket} that also fit. Motivated by the above example, we investigate the existence and efficient computability of finite characterisations , i.e., finite sets of labeled examples that uniquely characterize a single concept. Finite characterisations are relevant not only for illustrating a complex concept to a user (e.g., to verify the correctness of a concept expression obtained using machine learning techniques). Their existence is a necessary condition for exact learnability with membership queries Angluin 1987 . Furthermore, from a more fundamental point of view, by studying the existence of finite characterisations, we gain insight into the power and limitations of labeled examples as a medium for describing concepts. Concretely, we systematically study the existence of, and the complexity of computing, finite characterisations for description logic concepts in a wide range of expressive description logics. We look at concept languages \mathcal{L}(\mathbf{O}) that are generated by a set of connectives \mathbf{O} , where \{\exists,\sqcap\}\subseteq\mathbf{O}\subseteq\{\forall,\exists,\geq,-,\sqcap,\sqcup,\top,\bot,\neg\} . In other words, we look at fragments of the description logic \mathcal{ALCQI} that contain at least the \exists and \sqcap constructors from {\cal E\!L} . As our first result, within this framework, we obtain an almost complete classification of the concept languages that admit finite characterisations. Figure 1: Summary of Thm. 1.1 and Thm. 1.2 . Theorem 1.1 . Let \{\exists,\sqcap\}\subseteq\mathbf{O}\subseteq\{\forall,\exists,\geq,-,\sqcap,\sqcup,\top,\bot,\neg\} . 1. If \mathbf{O} is a subset of \{\exists,-,\sqcap,\sqcup,\top,\bot\} , \{\forall,\exists,\sqcup,\sqcap\} or \{\forall,\exists,\geq,\sqcap,\top\} then \mathcal{L}(\mathbf{O}) admits finite characterisations. 2. Otherwise \mathcal{L}(\mathbf{O}) does not admit finite characterisations, except possibly if \{\geq,-,\sqcap\}\subseteq\mathbf{O}\subseteq\{\exists,\geq,-,\sqcap,\top\} . The above theorem identifies three maximal fragments of \mathcal{ALCQI} that admit finite characterisations. It leaves open the status of essentially only two concept languages, namely \mathcal{L}(\exists,\geq,-,\sqcap) and \mathcal{L}(\exists,\geq,-,\sqcap,\top) (note that \exists is definable in terms of \geq ). The proof builds on prior results from Cate and Dalmau 2022 and Cate and Koudijs 2024 . Our main novel technical contributions are a construction of finite characterisations for \mathcal{L}(\forall,\exists,\geq,\sqcap,\top) and complementary negative results for \mathcal{L}(\geq,\bot),\mathcal{L}(\geq,\sqcup) and \mathcal{L}(\forall,\exists,-,\sqcap) . The construction of finite characterisations for \mathcal{L}(\forall,\exists,\geq,\sqcap,\top) is non-elementary. We give an elementary (doubly exponential) construction for \mathcal{L}(\exists,\geq,\sqcap,\top) , via a novel polynomial-time algorithm for constructing frontiers. Next, we study which concept languages \mathcal{L}(\mathbf{O}) admit polynomial-time computable characterisations , i.e., have a polynomial-time algorithm to compute finite characterisations. Theorem 1.2 . Let \{\exists,\sqcap\}\subseteq\mathbf{O}\subseteq\{\forall,\exists,\geq,-,\sqcap,\sqcup,\top,\bot,\neg\} . 1. If \mathbf{O} is a subset of \{\exists,-,\sqcap,\top,\bot\} , then \mathcal{L}(\mathbf{O}) admits polynomial-time computable characterisations. 2. Otherwise, \mathcal{L}(\mathbf{O}) does not admit polynomial-time computable characterisations, assuming P \neq NP. The first item follows from known results Cate and Dalmau 2022 ; we prove the second. Thm. 1.1 and 1.2 are summarized in Figure 1 . Finally, we investigate finite characterisations relative to an ontology \mathcal{O} , where we require the examples to be interpretations that satisfy the ontology and we require that every fitting concept is equivalent to the input concept C relative to \mathcal{O} . Theorem 1.3 . Let \{\exists,\sqcap\}\subseteq\mathbf{O}\subseteq\{\forall,\exists,\geq,-,\sqcap,\sqcup,\top,\bot,\neg\} . 1. If \mathbf{O} is a subset of \{\exists,\sqcap,\top,\bot\} , then \mathcal{L}(\mathbf{O}) admits finite characterisations w.r.t. all DL-Lite ontologies. 2. Otherwise, \mathcal{L}(\mathbf{O}) does not admit finite characterisations w.r.t. all DL-Lite ontologies, except possibly if \{\exists,\sqcap,\sqcup\}\subseteq\mathbf{O}\subseteq\{\exists,\sqcap,\sqcup,\top,\bot\} . In fact, for \mathcal{L}(\exists,\sqcap,\top,\bot) -concepts C and DL-Lite ontologies \mathcal{O} such that C is satisfiable w.r.t. \mathcal{O} , a finite characterisation can be computed in polynomial time. This shows in particular that, if we exclude \sqcup from consideration, then \mathcal{L}(\exists,\sqcap,\top,\bot) is the unique largest fragment admitting finite characterisations under DL-Lite ontologies. Outline In Section 2 , we review relevant definitions and we introduce our framework for finite characterisations. Section 3 studies the existence and polynomial-time computability of finite characterisations without an ontology. Section 4 extends the analysis to the case with DL-Lite ontologies. Section 5 discusses further implications and future directions. Related Work Finite characterisations were first studied in the computational learning theory literature under the name of teaching sets, with a corresponding notion of teaching dimension, measuring the maximal size of minimal teaching sets of some class of concepts Goldman and Kearns 1995 . The existence of finite characterisations is a necessary condition for exact learnability with membership queries. Several recent works study finite characterisations for description logic concepts ( Cate and Dalmau 2022 ; Funk et al. 2022 for \mathcal{ELI} ; Fortin et al. 2022 for temporal instance queries). We use results from Cate and Dalmau 2022 ; Funk et al. 2022 . Thm. 1.3 appears to contradict a result in Funk et al. 2022 , which states that \mathcal{ELI} admits finite characterisations under DL-Lite ontologies. However, this is

Read the complete text