Generalization Under Implication by Using Or-Introduction

Abstract

In the area of inductive learning, generalization is a main operation. Already in the early 1970's Plotkin described algorithms for computation of least general generalizations of clauses under θ -subsumption. However, there is a type of generalizations, called roots of clauses, that is not possible to find by generalization under θ -subsumption. This incompleteness is important, since almost all inductive learners that use clausal representation perform generalization under θ -subsumption. In this paper a technique to eliminate this incompleteness, by reducing generalization under implication to generalization under θ -subsumption, is presented. The technique is conceptually simple and is based on an inference rule from natural deduction, called or-introduction. The technique is proved to be sound and complete, but unfortunately it suffers from complexity problems.