Genetic Relational Search for Inductive Concept Learning: a Memetic Algorithm for Ilp

Learning from examples in First Order Logic, also known as Inductive Logic Programming (ILP), constitutes a central topic in Machine Learning, with relevant applications to problems in complex domains, e.g., natural language and computational biology. Learning can be viewed as a search problem in the space of all possible hypotheses. Given a background knowledge, a set of positive examples and a set of negative examples, expressed in First Order Logic, one has to find a hypothesis which covers all positive examples and none of the negative ones. This problem is NP-hard even if the language to represent hypotheses is propositional logic. When FOL hypotheses are used, this complexity is combined with the complexity of evaluating hypotheses. This book describes an evolutionary algorithm for ILP. The algorithm, called ECL (for Evolutionary Concept Learner), evolves a population of Horn clauses by repeated selection, mutation and optimization of more fit clauses. ECL relies on four greedy mutation operators for searching the hypothesis space, and employs an optimization phase that follows each mutation. Experimental results show that ECL works well in practice.