Reaching for the Stars in EL* Concept Learning

Abstract

Learning concepts from data examples is an intensively investigated topic in description logics (DLs), in particular for the EL-family. So far, hardly any of these works on concept learning consider the Kleene star to express the (reflexive) transitive closure of roles. However, the star plays a central role in some closely related settings, like learning shape expressions in graph constraint languages such as SHACL, and learning graph queries from graph data. As a first step towards developing techniques for learning SHACL shape expressions, we consider learning from examples (aka the fitting problem) for the logic EL*, which extends EL by the reflexive transitive closure of named roles. In contrast to EL, the DL EL* can express a limited form of disjunction that can result in more informative fittings. By adapting the automata-based techniques for ℰℒ, we obtain complexity bounds for deciding existence of EL* fittings that coincide with those for EL. We also develop an algorithm for computing most specific fittings in EL*.