Bounded Fitting for Expressive Description Logics

1 Introduction

Fitting logical formulas to labeled data examples is the basic task of computing, given some data instance I, positive examples P, and negative examples N, a formula φ fitting P,N in I, that is, φ(a) holds in I for all a ∈ P but for no a ∈ N. It underlies many higher level tasks such as example-driven query specification, data exploration, explaining the labeling of the examples, and knowledge acquisition [Martins, 2019; ten Cate et al., 2023a; Zloof, 1975]. A recently prominent approach to finding fitting formulas is bounded fitting, which rests on the idea to test whether there are fitting formulas of increasing size [ten Cate et al., 2023b; Funk et al., 2025; Neider and Gavran, 2018; Pommellet et al., 2024]. Algorithm 1 illustrates the idea for a general logic L. Bounded fitting is an attractive paradigm both from a theoretical and a practical perspective. Indeed, it is complete, meaning that it will find a fitting formula whenever there is one, and always returns a fitting formula of minimal size. The latter is desired by users since they typically prefer small fittings, and implies that bounded fitting is an Occam algorithm [Blumer et al., 1987], which in turn guarantees that the found concept generalizes well to unseen examples in the sense of Valiant's probably approximately correct (PAC) learning [Valiant, 1984; Blumer et al., 1989]. Finally, bounded fitting can often be implemented with the help of a SAT solver, allowing bounded fitting algorithms to perform well in practice.

assumptions they cannot be Occam algorithms or have PACstyle generalization guarantees.

We thus investigate as our second contribution how to extend the bounded fitting paradigm to ALCQI(f). To this end, we show first that the size-restricted fitting problem that has to be solved in Line 2 of Algorithm 1 is NP-complete for ALCQI(f), as it is for ALC and many of its fragments [Funk et al., 2025]. This paves the way to the use of SAT solvers. We then observe that inverse roles can be reduced away in a simple fashion. In contrast, adapting bounded fitting to number restrictions and feature comparisons while having a realistic implementation based on SAT solvers in mind is more challenging. We resort to allow for number restrictions and feature comparisons in a controlled and incremental way. While this is in spirit of Occam's razor, which demands to prefer simpler concepts, and can be implemented using a SAT solver, it is not immediately clear that it results in Occam algorithms as formalized by Blumer et al. (1989). Our main results are then sufficient conditions for when the constructed algorithms are indeed Occam, (and thus have PAC-style guarantees.

As our third contribution, we implement bounded fitting for ALCQI(f), using a SAT solver to solve the size-restricted fitting problem. In order to achieve competitive performance, we describe two techniques that speed up SAT-based bounded fitting. First, we propose that bisimilarity can be exploited as a preprocessing step to reduce the size of the input database. This is not specific to bounded fitting and can potentially be used to improve other concept learning systems as well. Second, we observe that bounded fitting allows easy parallelization and implement it to use multiple CPU cores.

We evaluate our implementation on several benchmarks and compare it to the state-of-the-art concept learners EvoLearner and TDL. The experiments show that the concepts learned by our implementation generalize at least as good as the ones found by EvoLearner and TDL on the standard structured machine learning (SML) benchmarks. Moreover, using a newly generated benchmark, we show that our tool is better in finding fitting ALCQ concepts than other systems. Finally, we confirm that the presented optimization are effective in practice as well. Overall, our evaluation demonstrates that bounded fitting works well in practice also for expressive DLs.

Missing proofs can be found in the full version [Funk et al., 2026].

RelatedWork. The works most relevant related to this paper are [ten Cate et al., 2023b] and [Funk et al., 2025], which introduce the bounded fitting framework for the DLs EL and ALC, respectively. Beyond the concept learners mentioned above, there is a series of other tools that rely on more classical machine learning techniques such as trained search heuristics and neural concept synthesis like ROCES [Kouagou et al., 2024], NCES/NCES2 [Kouagou et al., 2023], and Drill [Demir and Ngonga Ngomo, 2023]. As they require a separate pretraining step, it is difficult to make a meaningful comparison with them. Other concept learners are DL-Foil [Rizzo et al., 2020] and SPaCel [Tran et al., 2017].

2 Background

We introduce syntax and semantics of the description logic ALCQI(f), the extension of ALCQI [Baader et al., 2017] with simple feature comparisons. Let NC, NR, NF, and NI be mutually disjoint and countably infinite sets of concept names, role names, feature names, and individual names, respectively. We assume that each feature name f has a domain dom(f), the set of values the feature f can take. We further assume a total order ≤ in every domain. An ALCQI(f) concept C is defined according to the syntax rule

where A ranges over concept names, ▷◁ ∈ {≤,≥}, R is a role name r or an inverse role R = r-, n ≥ 0, f ∈ NF is a feature name, and v ∈ dom(f). We call concepts of the shape (▷◁ n R.C) qualified number restrictions and concepts of shape (f ▷◁ v) feature comparisons. We use the standard abbreviations ⊥, C ⊔ D, ∃R.C, and ∀R.C for ¬⊤, ¬(¬C ⊓ ¬D), (≥ 1 R.C), and (≤ 0 R.¬C), respectively. We also consider the usual restrictions of ALCQI(f) that are obtained by disallowing certain constructors in the syntax. For example, ALCQ is obtained by disallowing inverse roles r- and feature comparison, while ALCI(f) is obtained by disallowing qualified number restrictions.

A database I is a finite set of facts of the formA(a), r(a, b), and f(a, v) for A ∈ NC, r ∈ NR, f ∈ NF, a, b ∈ NI, and v ∈ dom(f). We let adom(I) denote the set of all individual names that occur in I. Moreover, we assume that for every a ∈ adom(I) and f ∈ NF, I contains at most one fact of shape f(a, v). We write r-(b, a) ∈ I if r(a, b) ∈ I, and define succI(a,R) as the set

The semantics C I of an ALCQI(f) concept C in database I is defined inductively as follows. In the inductive base, we set ⊤I = adom(I) and AI = {a | A(a) ∈ I}. In the inductive step, we define (¬C)I = adom(I)\C I , (C⊓D)I = C I ∩DI , and

A signature is a finite set Σ of concept, role, and feature names. A Σ-database is a database in which all facts mention only concept, role, and feature names fromΣ. For a syntactic object O such as a concept or a database, we let ∥O∥ denote the size of O, that is, the length of a string representation of O in a suitable fixed alphabet in which concept/role/feature names contribute 1. We assume unary coding of numbers in qualified number restrictions.

Fitting Problems. Let I be a database and P,N ⊆ adom(I) be sets of individuals called positive and negative examples. We say that an ALCQI(f) concept C fits P, N in I if a ∈ C I for each a ∈ P and b /∈ C I for each b ∈ N. The fitting problem for ALCQI(f) is to decide, given I, P, N, whether there is an ALCQI(f) concept that fits P,N in I. A fitting algorithm for ALCQI(f) takes as input I, P, N as above, and returns an ALCQI(f) concept that fits P,N in I, if it exists.

The fitting problem and fitting algorithms for fragments of ALCQI(f) are defined accordingly. Observe that we make the closed world assumption in contrast to other works which study the fitting problem for knowledge bases, see, e.g. [Funk et al., 2019; Jung et al., 2022]).

The ALCQI(f) concept (≤ 1 child.(height ≥ 140cm)) fits {a}, {b} in I. Further, there is no ALCQI concept that fits {a}, {b}.

OccamAlgorithms. We recall the standard notion of Occam algorithms following [Blumer et al., 1989]. Let C be a set of DL concepts, I be a database and S ⊆ adom(I) be a set of examples. We say that C shatters S over I if for every S′ ⊆ S there is a C ∈ C such that S′ = S ∩ C I . The VC-Dimension of a set of concepts C is the largest number d ≥ 0 such that there is a database I and a set of examples S with cardinality d that is shattered by C.

Let A be a fitting algorithm. For a signature Σ and s, m ≥ 1, let HA(Σ, s, m) be the set of all concepts returned by A when started on some input I, P,N such that I is a Σ-database, |P | + |N| = m, and there is a concept C with ∥C∥ ≤ s that fits P,N in I. We call A an Occam algorithm if there is a polynomial p and α ∈ [0, 1) such that for all Σ and s, m ≥ 1 the VC-Dimension of HA(Σ, s, m) is at most p(s, |Σ|) · mα.

It is well known that that every Occam algorithm has PACstyle generalization meaning that it is a sample-efficient PAC learning algorithm. As the precise definition of that notion is not important for the main part of the paper, we refer the reader to [Blumer et al., 1989] or to the supplementary material.

3 The Fitting Problem for ALCQI(f)

We begin our investigation by showing that the fitting problem for ALCQI(f) and its fragments is efficiently solvable.

Theorem 1. The fitting problems for ALCQI(f), ALCQ(f), ALCQI, and ALCQ are decidable in polynomial time.

This can be shown using standard arguments. Since some of these will be important later, we sketch the main steps here; for details see the supplementary material. We first show the theorem for ALCQ and then for the remaining languages by a reduction to ALCQ. We rely on the notion of bisimulations.

Definition 1. Let I be a database. An ALCQ bisimulation on I is a relation S ⊆ adom(I) × adom(I) such that the following conditions are satisfied for all (a, b) ∈ S:

1. for all A ∈ NC, A(a) ∈ I if and only if A(b) ∈ I;
2. for all r ∈ NR and D ⊆ succrI (a), there is E ⊆ succrI (b) such that S contains a bijection between D and E;
3. for all r ∈ NR and E ⊆ succrI (b), there is D ⊆ succrI (a) such that S contains a bijection between D and E.

We call a, b ∈ adom(I) ALCQ bisimilar, written I, a ∼ I, b, if there is an ALCQ bisimulation S on I with (a, b) ∈ S.

It is well-known that the existence of fitting ALCQ concepts is characterized by the non-existence of ALCQ bisimulations between positive and negative examples. More precisely, there is an ALCQ concept fitting P, N in I iff I, a ̸∼ I, b for all a ∈ P, b ∈ N [de Rijke, 2000]. Since bisimilarity can be decided in polynomial time, Theorem 1 for ALCQ follows.

It remains to provide the promised reductions.

Lemma 1. There are polynomial-time reductions from the fitting problem for ALCQI(f) to that for ALCQ(f), and from the fitting problem for ALCQ(f) to that of ALCQ.

Proof. For the first reduction, let I, P,N be an input to the fitting problem for ALCQI(f). Introduce a fresh role name r for every role name r that occurs in I. Then then there is an ALCQI(f) concept fitting P, N in I iff there is an ALCQ(f) concept fitting P, N in J = I ∪ {r(b, a) | r(a, b) ∈ I}.

For the second reduction, let I, P,N be an input to the fitting problem for ALCQ(f). Introduce a fresh concept name Af≥v for every feature f and value v such that there is a fact f(a, v) ∈ I. Let J be the database consisting of all facts of shape A(a) and r(a, b) from I and all facts Af≥v(a) such that there is a fact f(a, v′ ) ∈ I with v ≥ v′ . It is routine to verify that there is an ALCQ(f) concept fitting P, N in I if and only if there is an ALCQ concept fitting P, N in J.

We show next that the algorithms used to prove Theorem 1 can be made constructive in a strong sense. Note that we allow DAG representation of concepts when constructing them.

Theorem 2. There are polynomial time fitting algorithms for ALCQI(f ), ALCQ(f ), ALCQI, ALCQ which always compute a concept that fits a maximal overall number of positive and negative examples.

While such optimal fitting algorithms are natural candidates to be used in practice, they cannot be sample-efficient PAC learning algorithms, under standard complexity assumptions. Indeed, if a polynomial time fitting algorithm for ALCQI(f) was a sample-efficient PAC learning algorithm, it could be used as an efficient PAC learning algorithms for propositional logic which likely does not exist [Kearns and Valiant, 1994]. Hence, the algorithms in Theorem 2 are also not Occam.

4 Bounded Fitting for ALCQI(f)

Motivated by the fact that standard algorithms are not Occam or sample-efficient, we apply the bounded fitting paradigm given in Algorithm 1 to ALCQI(f), and investigate under which conditions the favorable properties are preserved. As we are interested in realistic implementations leveraging SAT solvers, we first establish that the core problem to be solved in Line 2 of Algorithm 1 is indeed NP-complete for ALCQI(f).

Formally, the size-restricted fitting problem is defined as follows. Given database I, positive and negative examples P, N and k ≥ 0, decide whether there is an ALCQI(f) concept C of size ∥C∥ ≤ k that fits P,N in I. In the context of bounded fitting, it is natural to assume k to be coded in unary.

Theorem 3. The size-restricted fitting problem for ALCQI(f) is NP-complete. Hardness already holds for inputs I, P, N where I is an {A, r, s}-database for A ∈ NC and r, s ∈ NR, and P, N are sets with |P | = |N| = 1.

Algorithm 2 Bounded fitting for ALCQ.

Input: Data instance I, examples P,N

• 1: for k := 1, 2, . . . do
• 2: if there is C ∈ ALCQkg(k) that fits P,N in I then
• 3: return C

The upper bound is established by the usual guess-andcheck argument: given I, P, N, non-deterministically guess a candidate concept of size k, and deterministically verify that it fits P,N in I in time polynomial in k and the size of I. The proof of the lower bound is more challenging. It extends the proof of the same result for ALC [Funk et al., 2025], but requires care to handle inverse roles and number restrictions.

While the NP-upper bound from Theorem 3 is encouraging from the theoretical perspective, a direct reduction to SAT in the style of Cook's theorem [Cook, 1971] is hardly practical. Previous reductions were based on the idea of measuring the complexity of the concept sought in stage k of bounded fitting in terms of the number of nodes in the syntax tree or, equivalently, the number of logical operators [ten Cate et al., 2023b; Funk et al., 2025]. The SAT solver then "guesses" the labels of the nodes in the syntax tree and evaluates whether the represented concept fits. This idea does not easily to ALCQI(f) since the numbers that occur in qualified number restrictions and feature comparisons should in some way contribute to the complexity of the concepts. We discuss below the additions I, Q, f to ALC separately for the sake of clarity. Our bounded fitting algorithm for ALCQI(f) combines all ideas.

We start with inverse roles. Observe that the first reduction in Lemma 1 provides a transparent way of dealing with them. Consider the following algorithmAI. Let I, P,N be an input for the fitting problem for ALCI. Then, AI computes J, P, N for J defined as in the proof of Lemma 1, and starts bounded fitting (for ALC) on input J, P,N. If it finds an ALC concept in this way, it outputs the corresponding ALCI concept. It follows from the reduction and the fact that bounded fitting for ALC is a complete Occam algorithm that AI is a complete Occam algorithm as well.

We next consider qualified number restrictions. Note that under the discussed measure of size (being the number of logical operators), there are, in principle, infinitely many concepts of a given size. To make the space of concepts considered in each stage of bounded fitting finite, we have to bound the numbers occurring in the concepts. To this end, we allow in stage k numbers up to g(k) in concepts, for some function g. The idea is illustrated in Algorithm 2, where ALCQkg(k) denotes the set of ALCQ concepts that allow for at most k logical operators and numbers in number restrictions at most g(k). This approach is in the spirit of Occam's razor if g is an increasing function as this reflects that larger numbers in number restrictions are considered more complex. Depending on the domain, the user may choose different functions reflecting their view on the importance of number restrictions. The following theorem provides the user with a range of functions g which make Algorithm 2 a complete Occam algorithm.

Theorem 4. Let g ∈ Ω(k) ∩O(2p(k) ) for some polynomial p. Then Algorithm 2 is a complete Occam algorithm.

Completeness follows from g ∈ Ω(k). For showing that Algorithm 2 is Occam we carefully analyze its space HA(Σ, s, m) and show that its VC-dimension is polynomially bounded for any g as in the theorem.

We next look at feature comparisons. Similar to the number restrictions, there are potentially infinitely many concepts with a given number of logical operators, since features may have an infinite domain. Similar to what was done for ALCQ, we could obtain an Occam algorithm by allowing in every stage k of bounded fitting for, say, k bits in the representation of the feature values. From a practical perspective, however, we believe that different feature values should contribute in the same way to a learned concept, e.g., the complexity of feature comparisons (salary ≥ n) should not depend on n. This perspective suggests to remove the feature comparisons via the reduction given in Lemma 1, similar to what we did for inverses. Unfortunately, this does not lead to an Occam algorithm. Let Af be the algorithm obtained by first applying the reduction of fitting in ALC(f) to fitting in ALC from Lemma 1 and then applying bounded fitting for ALC to the result. Clearly, Af is complete, but:

Theorem 5. AlgorithmAf is not an Occam algorithm.

The intuitive reason for this is that for sufficiently large s,m, one can find inputs to the algorithm so that Af returns concepts of the form ∃r.((f ≤ j) ⊓ (f ≥ j)), for any j ∈ N. While an infinite space HAf (Σ, s,m) does not rule out being an Occam algorithm, we show that these concepts shatter exponentially sized sets of examples, making the VC dimension not polynomially bounded. Indeed, we show the stronger statement that Af is not a sample-efficient PAC learning algorithm.

The proof of Theorem 5 relies on the presence of an unbounded number of feature values and on databases with unbounded outdegree. We next show that both these assumptions are necessary to achieve exponential VC-dimension. A class of databases has bounded outdegree if there is a constant ℓ such that for all a ∈ adom(I), there are at most ℓ facts of shape r(a, b) ∈ I. Similarly, the class of databases has bounded domains if the cardinalities of all feature domains are bounded by some constant.

Theorem 6. Algorithm Af is an Occam Algorithm if input databases have bounded outdegree or bounded domains.

If domains are bounded, one can replace features with a fixed number of concept names. For bounded outdegree, we observe that for a concept C of a given size s, there is an at most exponential number of feature values "visible" by C in any given set of m examples. This allows us to bound the VC-dimension of the space HAf (Σ, s, m) over databases of bounded outdegree.

From a practical point of view, the preconditions in Theorem 6 are not guaranteed to hold in all datasets, but in relevant cases, e.g., for features that describe days of the week, age of employees, or for roles such as child or spouse. A limitation in practice, however, is that using this route introduces a potentially large number of concept names which, as we shall see, is reflected in an increased number of propositional variables. We describe in Section 5.2 how we address this problem in our tool.

5 Implementation

We implemented bounded fitting for ALCQI(f). Our implementation follows the same general approach as ALCSAT [Funk et al., 2025]: in each stage of bounded fitting, the size-restricted fitting problem is solved by checking satisfiability of a suitable propositional formula, using a SAT solver. Users may specify the fragment of ALCQI(f) that they are interested in. Moreover, our tool implements an approximation strategy that tries to compute a concept that fits the maximum number of examples. In the remainder of the section, we describe the reduction to SAT for ALCQ, discuss how we handle inverses (I) and features (f), and describe two optimizations.

5.1 SAT Encoding for ALCQ

We briefly recall some details of ALCSAT's implementation [Funk et al., 2025] in order to explain how we extend it to ALCQ. Let I, P, N, k be an instance of the size-restricted fitting problem for ALC. ALCSAT constructs a propositional formula φ that is satisfiable if and only if there exists an ALC concept C of size k that fits P, N in I. Moreover, such a fitting concept can directly be obtained from a model of φ. Let ΣC and ΣR be the sets of concept and role names that occur in I. The formula φ encodes the syntax tree of an ALC concept with k nodes and its semantics such that in a model of φ, for all i, j ∈ {1, . . . , k}, a ∈ adom(I) and v a node label from V = {⊤, ⊥, ¬, ⊓, ⊔} ∪ ΣC ∪ {∃r, ∀r | r ∈ ΣR}, the variable xi,v is true iff node i of the syntax tree is labeled with v, the variable y1,i,j is true iff node i has the single successor j, the variable y2,i,j is true iff node i has the two successors j and j + 1, and the variable zi,a is true iff a ∈ C I i where Ci is the concept represented by node i in the syntax tree. For example, the semantics of existential restrictions is encoded by clauses that express

for 1 ≤ i, j ≤ k, r ∈ Σr, a ∈ adom(I). The requirement that the concept C1 fits P, N in I is then encoded using ∧a∈P z1,a and ∧a∈N ¬z1,a.

Our implementation extends this encoding by allowing additional vertex labels for qualified number restrictions and by encoding their semantics. Given a bound g(k) (recall Algorithm 2 from the previous section) for numbers in qualified number restrictions, we use node labels (≤ n r) and (≥ n r) for all r ∈ Σr and n with 0 ≤ n ≤ g(k). Then, we encode the semantics of qualified number restrictions by adding clauses that encode

for all i, j with 1 ≤ i, j ≤ k, 0 ≤ n ≤ g(k), r ∈ Σr and a ∈ ∆I to φ. To encode the cardinality constraints in the above formulas as clauses, we employ a sequential counter encoding, which for a bound of k on n literals uses O(n · k) additional variables and clauses [Sinz, 2005]. In total, this results in O(k2 · |I| · |Σ| · g(k)2 ) additional clauses.

5.2 Handling Inverses and Features

We treat inverses as described in the previous section, that is, via the (first) reduction in Lemma 1. It is worth noting that EvoLearner implements the same strategy [Heindorf et al., 2022].

To handle features, we implement a variant of the (second) reduction in Lemma 1. Instead of introducing a single concept name Af≥v for every value v that occurs in I, we introduce such concept names only for a restricted number nf of these values. This alone would result in an incomplete algorithm (as we may miss fitting concepts), so we incrementally increase the number nf along with the stages of bounded fitting. In practice we split the dom(f) into nf equally sized intervals.

DL-Learner follows a similar approach [Lehmann, 2010]. EvoLearner extends that by an entropy-based selection of the values given at the examples P,N [Heindorf et al., 2022].

5.3 Optimizations

We present two optimizations. The first relies on ALCQ bisimulations and is not specific to bounded fitting; it can in principle be used with all other tools. The idea is to exploit that ALCQ concepts cannot distinguish between ALCQ bisimilar individuals, and hence to replace the input database I with a smaller database I ′ in which few elements are bisimilar; we need to keep copies of bisimilar elements, due to the qualified number restrictions.

For a database I and for every a ∈ adom(I), let [a] denote the ∼-equivalence class of a in I. The ∼-quotient of I is the database I ′ over individuals ⟨[a], i⟩ with a ∈ adom(I) and

and the following facts for all A ∈ NC and r ∈ NR:

Using the observation that I, a is ALCQ bisimilar to I ′ , ⟨a, i⟩ for any i, one can show the following.

Lemma 2. Let I, P,N be a fitting problem instance for ALCQ. Every ALCQ concept C fits P, N in I if and only if C fits {⟨[p], 1⟩ | p ∈ P}, {⟨[n], 1⟩ | n ∈ N} in I ′ .

Hence, on input I, P,N our implementation computes I ′ , and then runs bounded fitting on I ′ . To compute the ALCQ bisimulation equivalence classes in I, we use a variant of the color refinement algorithm (see e.g. [Grohe et al., 2021]), which can be implemented to run in O(|I| log |I|).

Our second optimization concerns parallelization. By design, bounded fitting is suitable for parallelization: we can simply start each stage in its own thread. We follow a slightly different route that was proposed in the context of fitting LTL formulas [Riener, 2019]. We split the search space at a given stage k into several pieces and start search in each subspace on a different core based on the topology of the concepts. For this purpose we enumerate (outside the SAT solver) all possible topologies of syntax trees, split them into the number of available threads and start bounded fitting in each thread with the additional constraint to consider only the given topologies.

6 Experiments

We evaluate different aspects of our tool on the SMLBenchmarks [Westphal et al., 2019] and on benchmarks for ALCQ fitting we generated from the YAGO 4.5 knowledge base [Suchanek et al., 2024]. All experiments were executed on a MacBook Pro with M3 Pro chip and 36GB RAM. 1

We refer to accuracy and F1-score of concepts C on examples P,N in I. With accuracy we mean the percentage of elements of P and N that are labeled correctly by C, formally |CI ∩P|+|N\CI | |P |+|N| . As usual, with F1-score we mean the harmonic mean of precision and recall of C.

6.1 Evaluating Generalization

We compare the ability of our implementation to produce ALCQ(f) concepts that generalize to unseen examples on the standard SML-benchmarks with the state-of-the art concept learning implementations EvoLearner and TDL 2 as well as the algorithm underlying Theorem 2. We do not compare against the standard DL-Learner algorithms CELOE and OCEL, as EvoLearner is known to deliver concepts of higher F1-score [Heindorf et al., 2022]. We configured all systems to learn ALCQ(f) concepts with number restrictions up to a cardinality of 3. In the case of TDL this means disabling nominals. This places TDL at a disadvantage as it does not support numerical features (only Boolean features). We allowed all tools to run for 5 minutes. TDL and the algorithm underlying Theorem 2 always terminated before; for the anytime algorithms EvoLearner and our tool, we used the best concept produced so far.

Table 1 shows the results (mean and standard deviation over all runs) of 10-fold cross validation measuring the resulting concept size and F1-score on each data set. We omit results for the Mutagenesis and Nctrer benchmarks, as they possess a small perfect fitting ALCQ(f) concept that is almost always discovered by the systems. We remark that no implementation performs particularly well on the Carcinogenesis benchmark, where already the concept ⊤ achieves an F1-score of 0.71.

Overall these results demonstrate that bounded fitting performs competitively with state-of-the-art concept learners and is suitable to produce good concepts in practice. As expected, the algorithm underlying Theorem 2 produces very large concepts that overfit and do not generalize.

6.2 Evaluating Fitting for Number Restrictions

We compare the ability of our implementation to find fitting ALCQ concepts with that of EvoLearner and TDL. To this end, we created a new benchmark which contains difficult concept learning problems, where qualified number restrictions are essential to separate the positive examples from the negative examples. That is, it contains only instances I, P,N such that there is an ALCQ concept fitting P, N, but no ALC-concept.

1 Our implementation, the benchmarks, and instructions to reproduce our experiments are available at https://github.com/ SAT-based-Concept-Learning/ALCSAT.

2 We use the implementations of these systems available in OntoLearn https://github.com/dice-group/Ontolearn development version fd38beec65e85e56e50733d404360b1feb5f5a68, as TDL of version 0.9.2 of OntoLearn reported wrong accuracies

For this, we extract examples from the YAGO 4.5 knowledge base [Suchanek et al., 2024], focusing on the relations children, spouse, and gender. We first construct from each ALC-bisimulation equivalence class a single benchmark, by partitioning the equivalence class into ALCQ bisimulation equivalence classes, taking representatives of half the ALCQ bisimulation equivalence classes as positive examples and representatives of the other half as negative examples. In a second step, we generate benchmarks with a larger number of examples by combining the positive and negative examples of two benchmarks generated in the first step. We generate 120 benchmarks with the number of examples ranging from 4 to 35. An example of a fitting ALCQ concept in these benchmarks is the concept (≤ 3 children.⊤) ⊓ (≤ 1 children.∃ spouse.⊤). We believe that these benchmarks are of independent interest to evaluate the ability of concept learning implementations to find good ALCQ on real-world data.

Figure 1 shows the result of comparing mean accuracy and F1-score of the best concept produced within 5 minutes (as in Sec. 6.1) by TDL, EvoLearner (configured to optimize accuracy or F1-score), and our tool on these benchmarks, ordered by increasing number of examples. In all benchmarks, our tool is able to find concepts of higher accuracy and F1-score, in some cases even discovering perfect fittings. This indicates that our approach to handle qualified number restrictions has advantages over other tools, for fitting real-world examples.

6.3 Effect of Features Value Selection

We evaluate the effect of our approach to fit ALCQ(f) concepts by reduction to the fitting problem for ALCQ. For this, we run our implementation of bounded fitting up to size 8 on SML-benchmarks and vary the number of selected feature values. We use the SML-Benchmarks Mammographic, Mutagenesis, and Suramin, which contain features with domains of size 74, 529, and 157, respectively. Other SML-Benchmarks do not use numeric features to the same extent.

The measured accuracy on the training data and running time in seconds for different number of values are shown in Table 2, averaged over three runs. The first row for 0 values reports results when only Boolean features are used. As expected, increasing the number of values allows bounded fitting to find concepts that achieve higher accuracy, but this generally also increases running time, due to additional concept names. However, the running time does not always monotonically increase, as the running time of the SAT solver varies unpredictably with small changes. These results show that our approach to encode values to obtain a propositional formula is effective, and that on the SML-benchmark already a small number of such values suffices.

6.4 Effect of Optimizations

We evaluate the effect of the two presented optimizations. First, we run our implementation of bounded fitting up to size 8 on SML-benchmarks, and measure the required running time with and without the bisimulation-based preprocessing. We also vary the fragment of ALCQI(f) and measure the number of individuals before and after preprocessing.

Table 3 shows the results on the Mammographic, Hepatitis and Lymphography benchmarks. Again, we report the average of the running time over three runs. The measured number of individuals shows that on some benchmarks like Lymphography, the preprocessing has no effect, but also does not slow down the implementation. On other benchmarks, like Mammographic, the number of individuals is reduced which directly results in faster computation. Naturally, when fitting an ALC concept more individuals can be identified as when fitting a more expressive concept. This indicates that exploiting bisimilarity is an effective preprocessing step for fitting algorithms, especially when fitting a concept from a less expressive logic.

Second, we determine the efficacy of the implemented parallelization scheme by comparing the running times of our implementation with different number of threads on a selection of the SML-benchmarks. We measure the needed running time on the Mammographic, Carcinogenesis and Lymphography benchmarks to run bounded fitting up to size 8 with t = 1, 2, 4 and 8 worker threads.

We report full results in the long version [Funk et al., 2026], and only mention the results on the Lymphography benchmark here: the mean measured running time over three runs with one worker thread is 51.8 seconds, with two worker threads 30.8 seconds, with four worker threads 21.5 seconds and with 8 worker threads 19.6 seconds. Thus, the running times decrease when the number of threads is increased. This effect is strongest when going from 1 to 2 threads.

These results indicate that our parallelization scheme is effective in making use of multiple threads, and enables our implementation to find larger concepts in practical time frames.

7 Conclusion

Our theoretical investigation has shown how to extend bounded fitting to handle inverse roles, qualified number restrictions, and feature comparisons, to preserve theoretical guarantees about its generalization abilities. Our practical evaluation confirms our findings and shows that bounded fitting is a promising approach for description logic concept learning, also for expressive description logics.

We believe that new benchmarks are needed to better evaluate single features of the implemented systems. We made a first step into this direction by providing a new benchmark using which we can test the ability of concept learners to deal with qualified number restrictions. We would like to create similar benchmarks for inverse roles and feature comparisons.

Ethical Statement

There are no ethical issues.

Acknowledgments

Jean Christoph Jung and Tom Voellmer were supported by DFG grant JU 3197/1-1.