SAT-Based PAC Learning of Description Logic Concepts
SAT-Based PAC Learning of Description Logic Concepts
B. T. Cate,Maurice Funk,J. C. Jung,C. Lutz
TLDR
Bounded fitting is proposed as a scheme for learning description logic concepts in the presence of ontologies and it is proved that several other natural learning algorithms fail to provide theoretical guarantees regarding their generalization to unseen examples.
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.