Bounded fitting is a general paradigm for learning logical formulas from positive and negative data examples, that has received considerable interest recently. We investigate bounded fitting for concepts formulated in the description logic ℒ and its syntactic fragments. We show that the underlying size-restricted fitting problem is NP-complete for all studied fragments, even in the special case of a single positive and a single negative example. By design, bounded fitting is an Occam algorithm and thus is a sample-eficient PAC learning algorithm, regardless of the studied fragment. We complement this by showing that eficient PAC learning is impossible under standard complexity theoretic assumptions, and that other natural learning algorithms are typically not sample-eficient PAC learning algorithms. Finally, we present an implementation of bounded fitting in ℒ and its fragments based on a SAT solver. We discuss optimizations and compare our implementation to other concept learning tools.
Learning description logic (DL) concepts from given data examples is an important task when working
with large knowledge bases [
In this paper, we study the problem of learning concepts formulated in the description logic ℒ,
which is the basic logic underlying the web ontology language OWL 2 DL [
Input: Positive examples , negative examples 1 for := 1, 2, . . . do 2 if there is a concept ∈ ℒ of size that fits , then 3 return
Algorithm 1: Bounded Fitting for description logic ℒ. abstract description of bounded fitting for a given description logic ℒ. It should be clear that, if any iftting concept exists, bounded fitting always returns a fitting concept of minimal size, which is often a desirable property. From the practical perspective, human users typically prefer shorter, that is, simpler concepts in the applications sketched above. From a theoretical perspective, this property makes bounded fitting an Occam algorithm which implies that it comes with probabilistic generalization guarantees in Valiant’s probably approximately correct (PAC) learning framework [20, 21]. Intuitively, this means that bounded fitting needs only few examples to be able to generalize to unseen examples.
The basic DL ℒ provides the logical constructors conjunction ⊓, disjunction ⊔, negation ¬, existential restriction ∃, and universal restriction ∀ to build complex concepts from concept names and ⊥ and ⊤. Motivated by the fact that, depending on the application, one may not need all concept constructors, fragments ℒ() of ℒ have been studied which allow only a subset ⊆ {⊓ , ⊔, ¬, ∃, ∀} of the available constructors. For instance, the mentioned DL ℰℒ is defined by {⊓, ∃}, another popular logic is ℱℒ0, which is defined by {⊓, ∀}. Bounded fitting has been studied recently for ℰℒ, and we extend this study here to all other syntactical fragments.
The paper corresponding to this extended abstract has been accepted for publication at ISWC 2025 [22]. The full paper with all proof details is available on arXiv [23].
Our main contributions are as follows. First, we study the size-restricted fitting problem : given positive examples , negative examples , and a size bound in unary encoding, determine whether there is a concept of size at most that fits and . Clearly, this is precisely the problem to be solved in Line 2 of bounded fitting. Then, motivated by the ability of bounded fitting to generalize well from few examples, we investigate the generalization abilities of fitting algorithms for DLs ℒ() in Valiant’s PAC learning framework. Finally, we provide an implementation of bounded fitting for ℒ and its fragments, that relies on a SAT solver to solve size-restricted fitting in Line 2 of bounded fitting. We give now a more detailed overview.
Complexity of size-restricted fitting. We show that size-restricted fitting is NP-complete for ℒ and all its syntactic fragments ℒ() such that contains at least ∃ or ∀. This was known for the fragment ℰℒ [24]. Containment in NP can be shown by a simple guess and check argument. The lower bound is more technical and rather strong: it applies already in the case of only one positive and one negative example and over a signature consisting of two role names and one concept name. It thus strengthens the mentioned result for ℰℒ which requires a non-constant number of positive examples. The proof is by reduction from the hitting set problem. The examples constructed in the reduction admit a fitting ℒ concept if and only if there is a fitting ℒ(∃) concept, which means that it shows NP-hardness for all ℒ() with containing ∃. NP-hardness for the other fragments follows by applying a duality principle.
Theorem 1. Size-restricted fitting for ℒ() is NP-complete for every ⊆ {⊓ , ⊔, ¬, ∃, ∀} with {∃, ∀} ∩ ̸= ∅. This already holds if only a single positive and a single negative example are allowed, and over a signature consisting of two role names and one concept name.
Generalization. We investigate the learnability of ℒ concepts in Valiant’s PAC learning framework [20]. A PAC learning algorithm is a fitting algorithm that, given suficiently many labeled examples drawn from an unknown distribution, returns a concept that generalizes well (that is, has a small error when evaluated over the entire distribution) with high probability. We call such an algorithm eficient if it runs in polynomial time and sample-eficient if a polynomial number of examples sufices to ensure the described probabilistic generalization guarantees. For a precise definition, see the full paper but also [25]. We start with observing that under reasonable complexity theoretic assumptions, no ℒ() admits an eficient PAC learning algorithm, that is, an algorithm that runs in polynomial time and produces a concept that satisfies the definition of PAC learning. This is stated in the following theorem. Theorem 2. Let ⊆ {⊓ , ⊔, ¬, ∃, ∀}. If there is an eficient PAC learning algorithm for ℒ(), then: 1. NP = RP, if contains at least one of ∃/∀ and {⊓, ⊔} ̸⊆ ; 2. RSA encryption is polynomial time invertible, if {⊓, ⊔} ⊆ .
We then analyze the generalization ability of fitting algorithms that have favorable properties from a logical perspective in that they return fitting concepts that are most specific, most general, or of minimal quantifier depth among all fitting concepts. More precisely, we investigate whether there can be PAC learning algorithms with such properties that are sample-eficient. We show that, with one exception, all such algorithms are not sample-eficient, and hence do not generalize well. This was already known for the fragment ℰℒ of ℒ [16], and some of our proofs rely on similar techniques. Our results are summarized by the following theorem.
Theorem 3. Let ⊆ {⊓ , ⊔, ¬, ∃, ∀} be any set containing at least one of ∃/∀ and at least one of ⊓/⊔, and let be a fitting algorithm for ℒ(). Then is not a sample-eficient PAC learning algorithm, if: 1. ̸= {∃, ⊔} and always returns a most specific fitting if one exists; 2. ̸= {∀, ⊓} and always returns a most general fitting if one exists; 3. always returns a fitting of minimal quantifier depth if some fitting exists.
The exceptions in the theorem are the cases of = {∃, ⊔} and = {∀, ⊓}. For these fragments, bounded fitting is a sample-eficient PAC learning algorithm that returns a most specific or most general, respectively, fitting concept if it exists.
Implementation. We implemented bounded fitting for ℒ and its fragments using a SAT solver to decide the NP-complete size-restricted fitting problems by encoding size-restricted fitting into a propositional formula.1 We present two optimizations of the basic encoding, one where the structure of concepts is precomputed and then supplied to the SAT solver and another, where types of elements are used instead of individual concept names. Additionally, our implementation supports approximate iftting, the optimization variant of the fitting problem, where one searches for a concept that fits as many positive and negative examples as possible.
We compare our implementation ALC-SAT+ to other systems that support learning of ℒ concepts,
namely CELOE [12], SParCEL [