PAC-learnability of determinate logic programs
- 1 July 1992
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 128-135
- https://doi.org/10.1145/130385.130399
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.Keywords
This publication has 11 references indexed in Scilit:
- Interactive Concept-Learning and Constructive Induction by AnalogyMachine Learning, 1992
- Knowledge acquisition from structured data: using determinate literals to assist searchIEEE Expert, 1991
- Learning Simple Concepts under Simple DistributionsSIAM Journal on Computing, 1991
- Inductive logic programmingNew Generation Computing, 1991
- Editorial: Advice to Machine Learning AuthorsMachine Learning, 1990
- Quantifying inductive bias: AI learning algorithms and Valiant's learning frameworkArtificial Intelligence, 1988
- Machine Invention of First-order Predicates by Inverting ResolutionPublished by Elsevier ,1988
- Foundations of Logic ProgrammingPublished by Springer Nature ,1987
- Learning Decision ListsMachine Learning, 1987
- A theory of the learnableCommunications of the ACM, 1984