SAT-Based Bounded Fitting for the Description Logic ALC
This addresses the challenge of learning description logic concepts with theoretical guarantees, which is incremental as it builds on existing bounded fitting paradigms.
The paper tackles the problem of learning logical formulas in the description logic ALC from data examples, showing that the bounded fitting approach is NP-complete and provides probabilistic guarantees, unlike other methods, with an implementation based on a SAT solver.
Bounded fitting is a general paradigm for learning logical formulas from positive and negative data examples, that has received considerable interest recently. We investigate bounded fitting for the description logic ALC and its syntactic fragments. We show that the underlying size-restricted fitting problem is NP-complete for all studied fragments, even in the special case of a single positive and a single negative example. By design, bounded fitting comes with probabilistic guarantees in Valiant's PAC learning framework. In contrast, we show that other classes of algorithms for learning ALC concepts do not provide such guarantees. Finally, we present an implementation of bounded fitting in ALC and its fragments based on a SAT solver. We discuss optimizations and compare our implementation to other concept learning tools.