Pac-Learning a Restricted Class of Recursive Logic Programs

William W. Cohen

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 two-clause "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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.