SAT-Based PAC Learning of Description Logic Concepts

Balder ten Cate; Maurice Funk; Jean Christoph Jung; Carsten Lutz

IJCAI 2023poster14 citations

SAT-Based PAC Learning of Description Logic Concepts

Balder ten Cate, Maurice Funk, Jean Christoph Jung, Carsten Lutz

Abstract

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 ELHr based on a SAT solver, and compare its performance to a state-of-the-art learner.

Knowledge Representation and Reasoning: KRR: Description logics and ontologiesKnowledge Representation and Reasoning: KRR: Learning and reasoning

BibTeX

@inproceedings{ijcai2023p373,
  title     = {SAT-Based PAC Learning of Description Logic Concepts},
  author    = {ten Cate, Balder and Funk, Maurice and Jung, Jean Christoph and Lutz, Carsten},
  booktitle = {Proceedings of the Thirty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-23}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Edith Elkind},
  pages     = {3347--3355},
  year      = {2023},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2023/373},
  url       = {https://doi.org/10.24963/ijcai.2023/373},
}