First-order jk-clausal theories are PAC-learnable

摘要

We present positive PAC-learning results for the nonmonotonic inductive logic programming setting. In particular, we show that first-order range-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 interpretations. We discuss the problems encountered when learning theories which only have infinite nontrivial models and propose a way to avoid these problems using a representation change called flattening. Finally, we compare our results to PAC-learnability results for the normal inductive logic programming setting.