Pac-Learning Nondeterminate Clauses

Machine Learning

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 12

PAC Learning

Several practical inductive logic programming systems efficiently learn "determinate" clauses of constant depth. Recently it has been shown that while nonrecursive constant-depth determinate clauses are pat-learnable, most of the obvious syntactic generalizations of this language are not pat-learnable. In this paper we introduce a new restriction on logic programs called "locality", and present two formal results. First, the language of nonrecursive clauses of constant locality is pac-learnable. Second, the language of nonrecursive clauses of constant locality is strictly more expressive than the language of nonrecursive determinate clauses of constant depth. Hence, constant-locality clauses are a pat-learnable generalization of constant-depth determinate clauses.