The problem of learning logic programs has been researched extensively, but other knowledge representation 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.
One of the keys for designing induction algorithms in Description Logics are refinement operators. They allow for an efficient traversal of the subsumption hierarchy of concepts. One way to assess the suitability of a refinement operator for learning algorithms is to look at its properties. We analysed the properties completeness, weak completeness, properness, redundancy, finiteness, minimality, and their combinations, in particular we show theoretical limitations of refinement operators in Descriptions Logics.
Learning algorithms can be designed by combining a refinement operator with a a search heuristic. We propose an operator and show that it is close to the best we can hope for. We then create a sound 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 are also proposed.