Sample PAC-Learnability in Model Inference
Abstract
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.
Cite
Text
Nienhuys-Cheng and Polman. "Sample PAC-Learnability in Model Inference." European Conference on Machine Learning, 1994. doi:10.1007/3-540-57868-4_60Markdown
[Nienhuys-Cheng and Polman. "Sample PAC-Learnability in Model Inference." European Conference on Machine Learning, 1994.](https://mlanthology.org/ecmlpkdd/1994/nienhuyscheng1994ecml-sample/) doi:10.1007/3-540-57868-4_60BibTeX
@inproceedings{nienhuyscheng1994ecml-sample,
title = {{Sample PAC-Learnability in Model Inference}},
author = {Nienhuys-Cheng, Shan-Hwei and Polman, Mark},
booktitle = {European Conference on Machine Learning},
year = {1994},
pages = {217-230},
doi = {10.1007/3-540-57868-4_60},
url = {https://mlanthology.org/ecmlpkdd/1994/nienhuyscheng1994ecml-sample/}
}