We propose bounded fitting as a scheme for learning description logic concepts in the presence of ontologies. Two main advantages are (1) theoretical guarantees regarding the generalization of the learned concepts to unseen examples in the sense of PAC learning and (2) the fact that implementation can leverage SAT solvers in a natural way. We also present our system SPELL which implements bounded iftting based on a SAT solver and compare its performance to a state-of-the-art learner.
to the same distribution. It is well-known that PAC learning is intimately linked to Occam
algorithms which guarantee to find a hypothesis of small size [
The second advantage is that, in important cases, bounded fitting enables learning based
on SAT solvers and thus leverages the practical eficiency of these systems. In particular, this
is the case for concepts formulated in ℰℒ and ontologies formulated in ℰℒℋ. In this case,
the size-restricted fitting problem , which is defined like the fitting problem except that the
maximum size of fitting concepts to be considered is given as an additional input (in unary),
is NP-complete [
As a further contribution, we analyze the generalization ability of other relevant approaches
to constructing fitting ℰℒ-concepts. We start with algorithms that return fittings that are
‘prominent’ from a logical perspective in that they are most specific or most general or of
minimum quantifier depth among all fittings. Algorithms with such characteristics and their
applications are discussed in [
We next turn to algorithms based on so-called downward refinement operators which underlie all implemented DL learning systems that we are aware of. We consider two natural such operators that are rather similar to one another and combine them with a breadth-first search strategy. The first operator can be described as exploring ‘most-general specializations’ of the current hypotheses and the second one does the same, but is made ‘artificially Occam’ (with, most likely, a negative impact on practicality). We prove that while the first operator does not lead to a sample-eficient algorithm (even without ontologies), the second one does. This leaves open whether or not implemented systems based on refinement operators admit generalization guarantees, as they implement complex heuristics and optimizations.
As our final contribution we present SPELL (for SAT-based PAC ℰℒ concept Learner), a
SATbased system that implements bounded fitting of ℰℒ-concepts under ℰℒℋ-ontologies.1 We
evaluate SPELL on several datasets and compare it to the only other available learning system
for ℰℒ that we are aware of, the ℰℒ tree learner (ELTL) component of the DL-Learner system [
3.5 []s 3.0 iem 2.5 t ign 2.0 nn 1.5 u r0 1.0 1 lgo 0.5 0.0 240 200 160 120 80 40 number of examples 4 5 6 7 8 9
exist. restrictions SPELL 240 200 160 120 80 40 number of examples 4 5 6 7 8 9
exist. restrictions
ELTL
Experimental Results
We refer to [
Definition 1. Let ℒ be an ontology language, a concept language and let A be an algorithm for the size-restricted fitting problem for -concepts under ℒ-ontologies. Then Bounded-FittingA is the algorithm that, given a collection of labeled data examples and an ℒ-ontology , runs A with input (, , ) to decide whether there is a ∈ with |||| ≤ that fits w.r.t. , for = 1, 2, 3 . . ., returning a fitting concept as soon as it finds one.
As mentioned in the introduction, the size-restricted fitting problem for ℰℒ-concepts under
ℰℒℋ-ontologies is NP-complete. On top of that, it admits a natural translation to SAT. Along
with some optimizations, e.g., to break symmetries in the solution space for the resulting SAT
formulas, we have implemented this translation in the system SPELL. We have evaluated SPELL
on several newly crafted benchmarks and compared it to the ELTL component of the DL-Learner
system [
The first benchmark uses the Yago 4 knowledge base [
=1 .⊤ where each is a role name that represents a property of actors in Yago and is increased to obtain larger queries. The positive examples are selected by querying Yago with and the negative examples by querying Yago with generalizations of . The results are presented in Figure 1. They show that the size of the target concept has a strong impact on the running time whereas the impact of the number of positive and negative examples is much more modest. We also find that SPELL performs ∼ 1.5 orders of magnitude better than ELTL, meaning in particular that it can handle larger target queries.
Since Yago has only a very restricted ontology that essentially consists of inclusions ⊑
with , concept names, we complement the above experiment with a second one based on
OWL2Bench. OWL2Bench is a benchmark for ontology-mediated querying that combines
a database generator with a hand-crafted ontology which extends the University Ontology
Benchmark [
We also performed initial experiments to evaluate how well the constructed fittings generalize to unseen data. We again use the Yago benchmark, but now split the examples into training data and testing data (assuming a uniform probability distribution). Table 2 lists the median accuracies of returned fittings (over 20 experiments) where the number of examples in the training data ranges from 5 to 65. As expected, fittings returned by SPELL generalize extremely well, even when the number of training examples is remarkably small. To our surprise, ELTL exhibits the same characteristics. This may be due to the fact that some heuristics of ELTL prefer ifttings of smaller size, which might make ELTL an Occam algorithm. It would be interesting to carry out more extensive experiments on this aspect.
In [