SAT-Based PAC Learning of Description Logic Concepts
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.
Cite
Text
ten Cate et al. "SAT-Based PAC Learning of Description Logic Concepts." International Joint Conference on Artificial Intelligence, 2023. doi:10.24963/IJCAI.2023/373Markdown
[ten Cate et al. "SAT-Based PAC Learning of Description Logic Concepts." International Joint Conference on Artificial Intelligence, 2023.](https://mlanthology.org/ijcai/2023/tencate2023ijcai-sat/) doi:10.24963/IJCAI.2023/373BibTeX
@inproceedings{tencate2023ijcai-sat,
title = {{SAT-Based PAC Learning of Description Logic Concepts}},
author = {ten Cate, Balder and Funk, Maurice and Jung, Jean Christoph and Lutz, Carsten},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2023},
pages = {3347-3355},
doi = {10.24963/IJCAI.2023/373},
url = {https://mlanthology.org/ijcai/2023/tencate2023ijcai-sat/}
}