A Constraint-Based Induction Algorithm in FOL

We present a bottom-up generalization which builds the maximally general terms covering a positive example and rejecting negative examples in first-order logic (FOL), i.e. in terms of Version Spaces, the set G. This algorithm is based on rewriting negative examples as constraints upon the generalization of the positive example at hand. The constraints space is partially ordered, inducing a partial order on negative examples ; the near-misses as defined by Winston can then be formalized in FOL as negative examples minimal with respect to this partial order. As expected, only near-misses are necessary to build the set G. Moreover, constraints can be used directly to classify further examples. 1 INTRODUCTION Recently, the number of empirical induction algorithms in first order logic (FOL) is rapidly increased : to cite but a few, see FOIL (Quinlan 90, Quinlan 93), ML-Smart (Bergadano et al. 88, Botta Giordana 93), Golem (Muggleton Feng 90), KBG (Bisson 90), (Bisson 92)... We focus on dis..