FIRST-ORDER JK-CLAUSAL THEORIES ARE PAC-LEARNABLE

We present positive PAC-learning results for the nonmonotonic inductiv e logic programming setting. In particular, we show that first-order r ange-restricted clausal theories that consist of clauses with up to k literals of size at most j each are polynomial-sample polynomial-time PAC-learnable with one-sided error from positive examples only. In our framework, concepts are clausal theories and examples are finite inte rpretations. We discuss the problems encountered when learning theorie s which only have infinite nontrivial models and propose a way to avoi d these problems using a representation change called flattening. Fina lly, we compare our results to PAC-learnability results for the normal inductive logic programming setting.