PAC-Learnability of Determinate Logic Programs
Lists
Only you see this
Abstract
The field of Inductive Logic Programming (ILP) is concerned with inducing logic programs from examples in the presence of background knowledge. This paper defines the ILP problem, and describes the various syntactic restrictions that are commonly used for learning first-order representations. We then derive some positive results concerning the learnability of these restricted classes of logic programs, by reduction to a standard propositional learning problem. More specifically, k-clause predicate definitions consisting of determinate, function-free, non-recursve Horn clauses with variables of bounded depth are polynomially learnable under simple distributions. Similarly, recursive k-clause definitions are polynomially learnable under simple distributions if we allow existential and membership queries about the target concept.
BibTeX
@inproceedings{dzeroski1992pac,
author = {Saso Dzeroski and Stephen H. Muggleton and Stuart Russell},
title = {{PAC-Learnability of Determinate Logic Programs}},
booktitle = {Conference on Learning Theory},
year = {1992},
url = {https://openreview.net/forum?id=ua_u0maf5W},
}Loading related content...