Abstract

This paper describes a method for optimal hypothesis search in Inductive Logic Programming. The method is based on symbiotic evolution, a variant of genetic algorithm, for improving the predictive accuracy in classifying unknown examples. Progol, the representative ILP system, employs a refinement operator and finds an optimal hypothesis which subsumes the most specific hypothesis. Progol focuses on a hypothesis which has maximum explanatory power for training data. However, ILP systems should be evaluated by their explanatory powers for unknown data. In contrast, the proposed method produces a hypothesis using symbiotic evolution, which maintains and evolves two populations: a population of partial solutions to the problem and a population of complete solutions which are formed by grouping several partial solutions together. Symbiotic evolution can conduct balanced optimization of partial solutions and complete solutions. We postulate that the diversity of the results in GA increases the fitness to unknown data. We have developed an ILP system called ILP/SE, which uses symbiotic evolution for the hypothesis search task and uses the learning algorithm of Progol for the other task. ILP/SE judges the class of unknown data by majority using multiple hypothesises obtained in repeated execution. Experiments were conducted to show the performance of ILP/SE using the mutagenesis dataset. The result indicates that the ILP/SE approach outperforms the previous method using Progol for classification accuracy.