Abstract

Inductive Logic Programming employs expressive representation languages, i.e. Prolog Programs, so that ILP can handle structural data which other traditional inductive learner can not or hardly do. In this reason, ILP has been regarded as one of the most important technologies in the area of Data Mining and Knowledge Discovery in Databases recently. However, ILP usually needs enormous computational time to obtain the results from a huge amount of data appearing in such problems as Data Mining. To cope with this problem and to make ILP more practical, we need more efficient algorithms. Since learning by ILP can be regarded as the search problem, we need to consider the reduction of the number of hypotheses to be evaluated and the efficient evaluation algorithm in order to make ILP more efficient. One of the most effective ways in reducing the hypothesis space to be searched is to compute a Most Specific Hypothesis from one positive example by Inverse Entailment. Since MSH bounds the hypothesis space, it is important to decide which example should be used to generate MSH. In this paper, in order to reduce the computational time, we propose the following three algorithms for ILP systems which employ coverset algorithm, inverse entailment and top-down search strategy: selection of search space, incremental search within one class, integration of hypothesis spaces among the different classes. The main common feature of these three algorithms is that, instead of single MSH, plural MSHs are considered in the search process. Experiments were conducted to assess the effectiveness of the proposed algorithms. The results show that the proposed algorithms are useful for reducing the number of candidate hypotheses to be evaluated as well as the total computational time for induction.