Pac-learning Recursive Logic Programs: Negative Results
<|reference_start|>Pac-learning Recursive Logic Programs: Negative Results: In a companion paper it was shown that the class of constant-depth determinate k-ary recursive clauses is efficiently learnable. In this paper we present negative results showing that any natural generalization of this class is hard to learn in Valiant's model of pac-learnability. In particular, we show that the following program classes are cryptographically hard to learn: programs with an unbounded number of constant-depth linear recursive clauses; programs with one constant-depth determinate clause containing an unbounded number of recursive calls; and programs with one linear recursive clause of constant locality. These results immediately imply the non-learnability of any more general class of programs. We also show that learning a constant-depth determinate program with either two linear recursive clauses or one linear recursive clause and one non-recursive clause is as hard as learning boolean DNF. Together with positive results from the companion paper, these negative results establish a boundary of efficient learnability for recursive function-free clauses.<|reference_end|>
@article{cohen1995pac-learning,
    title={Pac-learning Recursive Logic Programs: Negative Results},
    author={W. W. Cohen},
    journal={Journal of Artificial Intelligence Research, Vol 2, (1995),
  541-573},
    year={1995},
    archivePrefix={arXiv},
    eprint={cs/9505105},
    primaryClass={cs.AI}
}