Concept Learning in Description Logics

Diplom thesis by Jens Lehmann

Supervisor Steffen Hölldobler
Wissensverarbeitung
12 September 2006 – 12 September 2006
Download

The problem of learning logic programs has been researched extensively, but other knowledge

representations formalisms like Description Logics are also an interesting target language. The importance of inductive reasoning in Description Logics has increased with the rise of the Semantic Web, because the learning algorithms can be used as a means for the computer aided building of ontologies. Ontology construction is a burdensome task and powerful tools are needed to support knowledge engineers.

The thesis focuses on learning ALC concept definitions, although many ideas apply to concept learning in general. It deeply researches the properties of ALC refinement operators, which are an efficient way to traverse the space of concepts ordered by subsumption. We give a full theoretical analysis of interesting properties of such operators. Based on this analysis, we propose a suitable concrete refinement operator and research its properties. We show that it is not possible to define better operators with respect to the properties we are investigating and establish a complete learning algorithm by adding an intelligent search heuristic.

As a second approach we investigate the use of Genetic Programming to solve the learning problem in Description Logics. We discuss the characteristics of Genetic Programming in this context and show a way to incorporate refinement operators in the Genetic Programming framework. Again, we define a suitable operator and analyse it. Some further extensions like learning from uncertain data and concept invention are also proposed.

Besides the analysis of the two learning approaches mentioned above, we will also briefly investigate current problems in evaluating concepts and describe possible solutions.