Abstract

Inductive Logic Programming has been drawn a big attention as a new research area of inductive inference based on first order logic. The main advantages of ILP are the very rich expressive power and the capability of utilizing arbitrary background knowledge represented in Prolog programs. However ILP usually needs enormous computational time to obtain the hypotheses. To cope with this problem, an efficient algorithm is needed. In this paper, an ILP system Progol is adopted as the target system. Progol is one of the most successful ILP systems, which induces hypotheses by first constructing the most specific hypothesis for a given example, and then searching through the subsumption lattice having empty clause and MSH as its top and bottom respectively. The second phase of Progol employes an A * -like search algorithm which is a kind of exhaustive search base on A * search strategy. In this paper, we show redundancy in A * -like algorithm from a viewpoint of imput/output relations amoung variables in the literals forming the MSH, and then propose a new search algorithm to remove the redundancy. The main advantage of the proposed algorithm is a substantial reduction of search space. By preprocessing the given search space, the redundant parts in the space can be removed. Since the search in the search space in which there is no answer can be avoided in this way, we have succeeded in reducing the number of candidate hypotheses to be generated as well as the whole computational time to induction.