Traps and pitfalls when learning logical definitions from relations

In the paper, we present some learning tasks that cannot be solved by two wellknown systems, FOIL and FOCL. Two kinds of explanations can be provided for these failures. For some tasks, the failures can be ascribed to a wrong definition of the space in which these systems perform the search for logical definitions. By moving from θ-subsumption to a weaker, but more mechanizable and manageable, model of generalization, called θOI-subsumption, a new search space is defined in which such tasks can be solved. Such a solution has been implemented in a new version of FOCL, called FOCL-OI. However, other learning tasks cannot be solved by changing the search space. For these tasks, the conceptual problem detected both in FOIL and in FOCL concerns the generation of meaningless rules, which do not mirror at all the structure of the training instances. We claim that, whenever possible, the training/test examples should be represented as ground Horn clauses, rather than as tuples of a relational database or facts of a Prolog database.