SAT-Based PAC Learning of Description Logic Concepts
This work addresses the challenge of ensuring theoretical generalization guarantees in learning description logic concepts, which is important for applications in knowledge representation and reasoning, though it appears incremental as it builds on existing SAT-based methods.
The paper tackles the problem of learning description logic concepts with ontologies by proposing bounded fitting, which provides PAC learning guarantees for generalization to unseen examples, and demonstrates that other natural algorithms fail to offer such guarantees. It introduces the system SPELL, which efficiently implements bounded fitting for the logic $\mathcal{ELH}^r$ using a SAT solver and shows competitive performance compared to a state-of-the-art learner.
We propose bounded fitting as a scheme for learning description logic concepts in the presence of ontologies. A main advantage is that the resulting learning algorithms come with theoretical guarantees regarding their generalization to unseen examples in the sense of PAC learning. We prove that, in contrast, several other natural learning algorithms fail to provide such guarantees. As a further contribution, we present the system SPELL which efficiently implements bounded fitting for the description logic $\mathcal{ELH}^r$ based on a SAT solver, and compare its performance to a state-of-the-art learner.