In this article, PAC-learning theory is applied to model inference, which concerns the problem of inferring theories from facts in first order logic. It is argued that uniform sample PAC-learnability cannot be expected with most of the ‘interesting’ model classes. Polynomial sample learnability can only be accomplished in classes of programs having a fixed maximum number of clauses. We have proved that the class of context free programs in a fixed maximum number of clauses with a fixed maximum number of literals is learnable from a polynomial number of examples. This is also proved for a more general class of programs.

Additional Metadata
Persistent URL hdl.handle.net/1765/101400
Series Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Citation
Nienhuys-Cheng, S-H, & Polman, M. (1994). Sample PAC-learnability in model inference. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Retrieved from http://hdl.handle.net/1765/101400