Bounded Fitting for Expressive Description Logics
For researchers in description logic learning, this work provides a practical and theoretically grounded approach to learning expressive concepts.
The paper extends bounded fitting to expressive description logics with inverse roles, qualified number restrictions, and feature comparisons, showing it retains favorable theoretical properties and achieves encouraging results compared to state-of-the-art concept learners.
Bounded fitting is an attractive paradigm for learning logical formulas from labeled data examples that offers PAC-style generalization guarantees and can often be implemented leveraging SAT solvers. It has been successfully applied to learning concepts of the description logic ALC. We study bounded fitting for learning concepts in expressive description logics that extend ALC with inverse roles, qualified number restrictions, and feature comparisons. We investigate under which conditions bounded fitting keeps its favorable theoretical properties in this setting, and implement it using a SAT solver. We compare our tool with state-of-the-art concept learners with encouraging results, demonstrating that it is a practical approach to expressive concept learning.