Pac-Learning a Restricted Class of Recursive Logic Programs

A crucial problem in “inductive logic programming” is learning recursive logic programs from examples alone; current systems such as GOLEM and FOIL often achieve success only for carefully selected sets of examples. We describe a program called FORCE2 that uses the new technique of “forced simulation” to learn twoclause “closed” linear recursive ij-determinate programs; although this class of programs is fairly restricted, it does include most of the standard benchmark problems. Experimentally, FORCE2 requires fewer examples than FOIL, and is more accurate when learning from randomly chosen datasets. Formally, FORCE2 is also shown to be a pat-learning algorithm in a variant of Valiant’ s [1984] model, in which we assume the ability to make two types of queries: one which gives an upper bound on the depth of the proof for an example, and one which determines if an example can be proved in unit depth.

Authors

• William W. Cohen Google AI

Keywords

No keywords are indexed for this paper.