Traditionally, ontology construction is conducted by knowledge engineers whose task is to formalize relevant concepts of the application domain and the relationships among them. This process is tedious and error-prone, and thus various methods to facilitate construction and, to some extent, ensure completeness of the resulting ontology by querying a domain expert have been investigated. For instance, learnability of axioms in lightweight DLs from a given set of interpretations has been studied in [1], and exact learnability of lightweight DL ontologies in Angluin's framework via queries has been studied in [2]. In [3, 4, 5, 6, 7], learning DL concepts and axioms from given examples has been investigated. Learning a DL ontology that is inseparable from a target ontology w.r.t. a query language and a fixed dataset via querying an oracle has been investigated in [ 8]. In a recent work [9], PAC learning of DL concepts has been studied. For an overview on learning DL ontologies see [10, 11]. In another line of work, Formal Concept Analysis (FCA) [12] was employed for mining an ℰℒ⊥-basis of all axioms holding in a given model [13, 14]. In [15], a further approach for mining bases with a predefined and fixed role depth of concept expressions was proposed. In a more recent work [ 16], an approach for eficient mining of axioms from graph dataset was introduced and evaluated on large datasets. The FCA-based approaches have the disadvantage that, in the worst case, they issue exponentially many queries to the domain expert. In [17], we presented an approach combining the advantages of both lines of research for completing the missing information in the ontology w.r.t. some given set of concept descriptions via issuing only polynomially many (w.r.t. the relevant quantities) queries to an expert. In the present work, we improve and implement the approach from [17] and present a PAC version of the ontology-completion method, which was initially introduced in [18] and implemented in [19]. Our solution is based on an algorithm for PAC learning a Horn envelope of an arbitrary propositional formula [20], which is itself based on an algorithm for exactly learning Horn formulas [21]. Our setting is the following. Given: • an initial TBox 0; • an expert ℰ able to answer subsumption queries w.r.t. a TBox ℰ that is unknown to us; • a set of concept descriptions built over the signature of ℰ ; • a sampling oracle that, when called, returns a subsumption query over according to a probability distribution ; • a probability and error bound with 0 < , < 1; compute a TBox such that 0 ⊆ and is, with probability at least 1 − , an -approximation of ℰ . Building on our work [17], we introduce pacco1, a tool for probably approximately correct (PAC) completion of DL TBoxes.
conjunctions of concepts from entailed by .
Definition 1. If is a TBox and is a finite set of concept descriptions, we denote by Impl( , ) = { → | , ⊆ and |
= ⊓ ⊑ ⊓ } the set of implications corresponding to GCIs over
Our approach to solving the above problem w.r.t. 0, , and ℰ is to learn a set ℒ of implications that approximates Impl( ℰ , ). For this, we need an oracle capable of answering membership and equivalence queries with respect to Impl( ℰ , ). A membership query asks whether a certain subset over of the form ℰ |= ⊓ ⊑ , where ⊆
and ∈ . of is a model of Impl( ℰ , ), and an equivalence query asks for a subset of that is a model of either Impl( ℰ , ) or ℒ but not both. We rely on a (domain) expert oracle ℰ answering subsumption queries
As a measure of approximation for TBoxes, we consider how often the two TBoxes give the same answers to subsumption queries: Definition 2.
Let 1 and 2 be two TBoxes, be a finite set of concept descriptions, and be a probability distribution of subsumption queries over . We define dist(1, 2), the --distance between 1 and 2, as the probability of getting diferent responses to a subsumption query w.r.t. 1 and 2: Pr( | (1 |= ) ⇔ (2 ̸|= )), where is a subsumption query over . For a given 0 < < 1, we call a TBox an ---approximation of * if dist( , * ) ≤ . If, in addition, upper ---approximation of * .
* |= , i.e., the set of models of * is a subset of the set of models of , then we say that is an * is equal to Pr( | ̸|= and * |= ).
Proposition 1. If is an upper ---approximation of * , then the --distance between and approximation of ℰ .
Our algorithm has access to a sampling oracle simulating a user that, when called, returns a subsumption query over according to a probability distribution . Given parameters 0 < , < it uses oracles ℰ and to compute a TBox that, with probability at least 1 − , is an upper --
The algorithm internally maintains a list of implications over such that, after termination, the corresponding set of GCIs is a desired approximation of ℰ . It starts with the empty list ℒ of implications and uses counterexamples obtained from (simulated) equivalence queries to update ℒ. In the algorithms from [21] and [20], both positive and negative counterexamples are possible. A positive counterexample may be returned if the current hypothesis contains an implication not entailed by the target Horn formula. In our setting, such an implication corresponds to a CGI not entailed by the target TBox ℰ . Since our goal is to obtain an upper approximation of ℰ , we do not allow such GCIs. Therefore, we modify the algorithm to make sure that ℒ always contains only implications corresponding to GCIs entailed by ℰ . This ensures that the resulting approximation of ℰ is an upper approximation.
We simulate every equivalence query with several calls to the sampling oracle . If not all valid GCIs are entailed by GCI(ℒ) = {⊓ ⊑ ⊓ | → ∈ ℒ}, we expect an equivalence query to return a subset of closed under ℒ but not under Impl( ℰ , ). Since we aim at an -approximation, we must be able to obtain, with an appropriate probability, such whenever dist(GCI(ℒ), ℰ ) > .
Every iteration of the algorithm starts with a search for a counterexample to GCI(ℒ). For the th iteration, our algorithm makes ⌈︁log1− (+1)
⌉︁ attempts to generate a counterexample [22]. Since ℒ contains only valid implications, the counterexample, if found, is always negative and is a model of ℒ. The rest of the iteration eliminates some counterexample ⊆ by making sure that, for every ∈ the responses to the query ⊓ ⊑ w.r.t. GCI(ℒ) and ℰ are identical. To do this, the algorithm searches ℒ for the first implication → such that = ∩ ̸= and ℰ |= ⊓ ⊑ for some ∈ ∖ . If such an implication is found, it is refined to → Compl( ), where Compl( ) is the completion of w.r.t. and ℰ , i.e., Compl( ) = { ∈ | ℰ |= ⊓ ⊑ }. Otherwise, a new implication → Compl() is added to the end of ℒ. In both cases, the new implication is valid w.r.t. 1, samples 17502 queries 18628
sampling oracle . Combining this with the results in [20], we obtain ℰ . Note that the computation of completion requires (||) queries to the oracle ℰ and no calls to the Theorem 1. Given a domain expert oracle ℰ and a sampling oracle , our algorithm computes, with probability at least 1 − , an upper ---approximation of ℰ . The number of queries to ℰ and posed by the algorithm is polynomial in ||, 1/ , 1/ , and the minimal size of an implication set equivalent to reasoner in conjunction with GO-Plant.
We evaluated our approach on a subset of the Gene Ontology (GO) [23], namely, GO-Plant2, which contains 97 classes and 155 logical axioms, among them 145 subclass axioms between concept names. For our experiments, we randomly deleted 50 of these subclass axioms and completed the resulting ontology with pacco in various test settings using the uniform distribution of subsumption queries in the sampling oracle. As base set , we took all the 97 concept names. As expert, we used the Hermit
As expected, increasing results in a smaller number of generated axioms and a larger number of unrecovered axioms, i.e., TBoxes that have larger --distance to the original TBox. The efect of varying is much smaller, since the number of sampling queries used to simulate an equivalence query depends linearly on 1/ and only logarithmically on 1/ .
We compared the resulting TBoxes with the original GO-Plant using the ontology dif tool ecco 3 [24]. Ecco finds diferences between ontologies and reports them in separate categories, one of which contains axioms from one ontology not entailed by the other. These are listed under unrecovered axioms in
In future, we plan to explore the empirical behavior of our algorithm by simulating the expert ℰ and the sampling oracle from data with diferent distributions. For example, we may sample frequently occurring subsets of to learn GCIs with high support in the sense of association rule mining. It could also be interesting to sample infrequent subsets of and learn GCIs with low support. One could say that GCIs highly supported by data can be accepted without resorting to an expert, whereas, for low-support GCIs, it is important to get a confirmation. It may be worthwhile to develop a modification of the algorithm to approximately complete both a TBox and an ABox w.r.t. a specific interpretation. This may require a slightly diferent notion of approximation accounting for the information contained in the ABox to be completed.
This work is partly supported by DFG in project 389792660 (TRR 248, Center for Perspicuous Systems),
by BMBF in ScaDS.AI, and by BMBF and DAAD in project 57616814 (SECAI).
[14] F. Distel, Learning description logic knowledge bases from data using methods from formal concept
analysis, Ph.D. thesis, Dresden University of Technology, 2011.
[15] D. Borchmann, F. Distel, F. Kriegel, Axiomatisation of general concept inclusions from finite
interpretations, Journal of Applied Non-Classical Logics 26 (2016) 1–46.
[16] F. Kriegel, Eficient axiomatization of OWL 2 EL ontologies from data by means of formal concept
analysis, in: M. J. Wooldridge, J. G. Dy, S. Natarajan (Eds.), Thirty-Eighth AAAI Conference on
Artificial Intelligence, AAAI 2024, Thirty-Sixth Conference on Innovative Applications of Artificial
Intelligence, IAAI 2024, Fourteenth Symposium on Educational Advances in Artificial Intelligence,
EAAI 2014, February 20-27, 2024, Vancouver, Canada, AAAI Press, 2024, pp. 10597–10606.
[17] S. Obiedkov, B. Sertkaya, D. Zolotukhin, Probably approximately correct completion of description
logic knowledge bases, in: M. Simkus, G. E. Weddell (Eds.), Proceedings of the 32nd International
Workshop on Description Logics, Oslo, Norway, June 18-21, 2019, volume 2373 of CEUR Workshop
Proceedings, CEUR-WS.org, 2019.
[18] F. Baader, B. Ganter, U. Sattler, B. Sertkaya, Completing Description Logic Knowledge Bases
using Formal Concept Analysis, LTCS-Report LTCS-06-02, Chair for Automata Theory,
Institute for Theoretical Computer Science, Dresden University of Technology, Germany, 2006. See
http://lat.inf.tu-dresden.de/research/reports.html.
[19] B. Sertkaya, Ontocomp system description, in: B. C. Grau, I. Horrocks, B. Motik, U. Sattler (Eds.),
Proceedings of the 22nd International Workshop on Description Logics
International Journal of Approximate Reasoning 127 (2020) 1–16. [23] T. G. O. Consortium, Gene ontology: Tool for the unification of biology, Nature Genetics 25 (2000) 25–29. [24] R. S. Gonçalves, B. Parsia, U. Sattler, Ecco: A hybrid dif tool for OWL 2 ontologies, in: P. Klinov, M. Horridge (Eds.), Proceedings of OWL: Experiences and Directions Workshop 2012, Heraklion, Crete, Greece, May 27-28, 2012, volume 849 of CEUR Workshop Proceedings, CEUR-WS.org, 2012.