SAT-Based PAC Learning of Description Logic Concepts

2023/05/15 by Balder ten Cate, Cate, Balder ten, Maurice Funk +5 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Artificial Intelligence (cs.AI) #Biomedical Text Mining and Ontologies #FOS: Computer and information sciences #Natural Language Processing Techniques #Semantic Web and Ontologies

paper · pdf · doi:10.48550/arxiv.2305.08511

openalex publication_date 2023/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

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

Cited by

• Fitting Ontologies and Constraints to Relational Structures
• SAT-Based Bounded Fitting for the Description Logic ALC

Related

• SAT-Based Bounded Fitting for the Description Logic ALC
• Learning implicitly in reasoning in PAC-Semantics
• Exact Learning of Lightweight Description Logic Ontologies
• On the Complexity of Learning Description Logic Ontologies
• Implicitly Learning to Reason in First-Order Logic