Refining Complete Hypotheses in ILP

Ivan Bratko


University of Ljubljana, Faculty of Computer and Information Sc.
Trzaska 25, 1000 Ljubljana, Slovenia
bratko@fri.uni-lj.si



Abstract. Most ILP systems employ the covering algorithm whereby
hypotheses are constructed iteratively clause by clause. Typically the covering
algorithm is greedy in the sense that each iteration adds the best clause
according to some local evaluation criterion. Some typical problems of the
covering algorithm are: unnecessarily long hypotheses, difficulties in handling
recursion, difficulties in learning multiple predicates. This paper investigates a
non-covering approach to ILP, implemented as a Prolog program called
HYPER, whose goals were: use intensional background knowledge, handle
recursion well, and enable multi-predicate learning. Experimental results in this
paper may appear surprising in the view of the very high combinatorial
complexity of the search space associated with the non-covering approach.
References

1.	Bratko, I., Grobelnik, M. (1993) Inductive learning applied to program
construction and verification. Proc. ILP Workshop 93, Bled, Slovenia.
2.	Grobelnik, M. (1992) Markus  an optimised model inference system. Proc. ECAI
Workshop on Logical Approaches to Machine Learning, Vienna.
3.	Muggleton, S. (1995) Inverse entailment and Progol. New Generation Computing,
13 (1995), 245-286.
4.	Pompe, U. (1998) Constraint Inductive Logic Programming. Ph.D. Thesis,
University of Ljubljana, Faculty of Computer and Info. Sc. (In Slovenian).
5.	Quinlan, J.R. (1990) Learning logical definitions from relations. Machine
Learning, 5 (1990), 239-266.
