Comparative Study of Structural Most Specific Generalizations Used in Machine Learning.

摘要

The paper compares three basic approaches of learning most specific generalizations (MSGs) in a unifying framework. By reducing them to each other it shows that even in some simple subset of first-order logic, it is NP-hard to decide if there exists a consistent inductive generalization. It then reviews a polynomial approach, learning most specific ij-determinate Horn clauses, within this framework and shows that even the relaxation from ij-determinate Horn clauses to determinate Horn clauses leads to exponentially longer MSGs. (Copyright (c) GMD 1992.)