Version space algorithms on hierarchies with exceptions

Abstract

In this paper, we present version space algorithms working on hierarchies with exceptions, exceptions meaning that some nodes may not be covered by some of their predecessors. Such representations are known from nonmonotonic reasoning. We give formal definitions and correctness results for the algorithms. Then we discuss what happens when the background knowledge is slightly modified by introduction of a new exception. Here lies the major advantage of our approach: when the knowledge is dynamically (nonmonotonically) modified, it is still possible to save almost all of the learned information instead of having to restart the version space learning method from scratch. Finally, we discuss the version space method in case several hierarchy trees (with or without exceptions) are combined to form a conjunctive concept.