Generalization Under Implication by Recursive Anti-Unification

Abstract

In the area of inductive learning, generalization is a main operation, and the usual definition of induction is based on logical implication. Recently there has been a rising interest in clausal representation of knowledge in machine learning. Almost all inductive learners that use clausal representation perform generalization under θ-subsumption rather than generalization under implication. The main reason is that there is a well- known and reasonably efficient technique to compute least general generalizations under θ-subsumption, but not under implication. Generalization under θ-subsumption is incomplete with respect to implication, and this incompleteness only occurs for recursive clauses. For recursive clauses there is a type of generalizations, called indirect roots, which are not possible to find under θ- subsumption. We will describe a technique, called recursive anti-unification, to compute indirect roots. By this technique we can also compute minimally general common indirect roots of clauses, which are guaranteed to be minimally general generalizations under implication.