More Web Proxy on the site http://driver.im/

Article

Free access

PAC-learnability of determinate logic programs

Authors:

Sašo Džeroski,

Stephen Muggleton,

Stuart RussellAuthors Info & Claims

COLT '92: Proceedings of the fifth annual workshop on Computational learning theory

Pages 128 - 135

https://doi.org/10.1145/130385.130399

Published: 01 July 1992 Publication History

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.

References

[1]

G. Benedek and A. Itai. Learnability by fixed distributions. In Proc. First A CM Workshop on Computational Learning Theory, pages 80-90, Morgan Kaufmann, San Mateo, CA, 1988.

Digital Library

[2]

L. De Raedt and M. Bruynooghe. Interactive concept learning and constructive induction by analogy. Machine Learning, 8(2): 107-150, 1992.

Digital Library

[3]

S. Dieroski and N. LavraL Refinement graphs for FOIL and LINUS. In S. H. Muggleton, editor, Inductive Logic Programming, Academic Press, London, 1992. In press.

[4]

D. Haussler. Quantifying inductive bias: AI learning algorithms and Valiant's model. Artificial Intelligence, 36(2): 177-221, 1988.

Digital Library

[5]

N. Lavra~, S. Dieroski and M. Grobelnik. Learning nonrecursive definitions of relations with LINUS. In Proc. Fifth European Working Session on Learning, pages 265-281, Springer, Berlin, 1991.

Digital Library

[6]

J. W. Lloyd. Foundations of Logic Pro~ gramming (2nd edn), Springer, Berlin, 1987.

Digital Library

[7]

M. Li and P. Vit~nyi. Learning simple concepts under simple distributions. SIAM Journal of Computing, 20(5): 911-935, 1991.

Digital Library

[8]

S. H. Muggleton. Duce, an oraclebased approach to constructive induction. In Proc. Tenth International Joint Conference on Artificial Intelligence, pages 287-292, Morgan Kaufmann, San Mateo, CA, 1989.

[9]

S. H. Muggleton. Inductive logic programming. New Generation Computing, 8(4): 295- 318, 1991.

Digital Library

[10]

S. H. Muggleton, editor. Inductive Logic Programming, Academic Press, London, 1992. In press.

[11]

S. H. Muggleton and W. Buntine. Machine invention of first-order predicates by inverting resolution. In Proc. Fifth International Conference on Machine Learning, pages 339- 352, Morgan Kaufmann, San Mateo, CA, 1988.

[12]

S. H. Muggleton and C. Feng. Efficient induction of logic programs. In Proc. First Conference on Algorithmic Learning Theory, pages 368-381, Ohmsha, Tokyo, 1990.

[13]

C. D. Page and A. M. Frisch. Generalization and learnability: a study of constrained atoms. In S. H. Mugglcton, editor, Inductive Logic Programming, Academic Press, London, 1992. In press.

[14]

J. R. Quinlan. Learning logical definitions from relations. Machine Learning, 5(3): 239- 266, 1990.

Digital Library

[15]

J. R. Quinlan. Knowledge acquisition from structured data - using determinate literals to assist search. IEEE Expert 6(6): 32-37, 1991.

Digital Library

[16]

R. Rivest. Learning decision lists. Machine Learning, 2(3): 229-246, 1987.

[17]

C. Rouveirol. Completeness for inductive procedures. In Proc. Eighth International Workshop on Machine Learning, pages 452-456, Morgan Kaufmann, San Mateo, CA, 1991.

Digital Library

[18]

E. Y. Shapiro. Algorithmic Program Debugging, The MIT Press, Cambridge, MA, 1983.

Digital Library

[19]

L. Valiant. A theory of the learnable. Communications of the ACM, 27(11): 1134-1142, 1984.

Digital Library

Cited By

Ji RXia JXiong YHu Z(2021)Generalizable synthesis through unificationProceedings of the ACM on Programming Languages10.1145/34855445:OOPSLA(1-28)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485544
Wang BBaluta TKolluri ASaxena PSpinellis DGousios GChechik MDi Penta M(2021)SynGuar: guaranteeing generalization in programming by exampleProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468621(677-689)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468621
Gromowski MSiebers MSchmid U(2021)A process framework for inducing and explaining Datalog theoriesAdvances in Data Analysis and Classification10.1007/s11634-020-00422-7Online publication date: 5-Jan-2021
https://doi.org/10.1007/s11634-020-00422-7
Show More Cited By

Index Terms

PAC-learnability of determinate logic programs
1. Theory of computation
  1. Logic
    1. Constraint and logic programming

Recommendations

Semantics for disjunctive logic programs
Learnability of constrained logic programs
ECML'93: Proceedings of the 6th European Conference on Machine Learning

The field of Inductive Logic Programming (ILP) is concerned with inducing logic programs from examples in the presence of back-ground knowledge. This paper defines the ILP problem and describes several syntactic restrictions that are often used in ILP. ...
Constructing the Least Models for Positive Modal Logic Programs

We give algorithms to construct the least L-model for a given positive modal logic program P, where L can be one of the modal logics KD, T, KDB, B, KD4, S4, KD5, KD45, and S5. If L ∈ {KD5,KD45,S5}, or L ∈ {KD,T,KDB,B} and the modal depth of P is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

COLT '92: Proceedings of the fifth annual workshop on Computational learning theory

July 1992

452 pages

ISBN:089791497X

DOI:10.1145/130385

Chairman:
David Haussler

Copyright © 1992 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1992

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

COLT92

Sponsor:

COLT92: 5th Annual Workshop on Computational Learning Theory

July 27 - 29, 1992

Pennsylvania, Pittsburgh, USA

Acceptance Rates

Overall Acceptance Rate 35 of 71 submissions, 49%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

129
Total Citations
View Citations
173
Total Downloads

Downloads (Last 12 months)72
Downloads (Last 6 weeks)12

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ji RXia JXiong YHu Z(2021)Generalizable synthesis through unificationProceedings of the ACM on Programming Languages10.1145/34855445:OOPSLA(1-28)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485544
Wang BBaluta TKolluri ASaxena PSpinellis DGousios GChechik MDi Penta M(2021)SynGuar: guaranteeing generalization in programming by exampleProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468621(677-689)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468621
Gromowski MSiebers MSchmid U(2021)A process framework for inducing and explaining Datalog theoriesAdvances in Data Analysis and Classification10.1007/s11634-020-00422-7Online publication date: 5-Jan-2021
https://doi.org/10.1007/s11634-020-00422-7
Veeraraghavan KLee DWester BOuyang JChen PFlinn JNarayanasamy S(2012)DoublePlayACM Transactions on Computer Systems10.1145/2110356.211035930:1(1-24)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1145/2110356.2110359
Alameldeen AWagner IChishti ZWu WWilkerson CLu S(2011)Energy-efficient cache design using variable-strength error-correcting codesACM SIGARCH Computer Architecture News10.1145/2024723.200011839:3(461-472)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/2024723.2000118
Ma KLi XChen MWang X(2011)Scalable power control for many-core architectures running multi-threaded applicationsACM SIGARCH Computer Architecture News10.1145/2024723.200011739:3(449-460)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/2024723.2000117
Udipi AMuralimanohar NBalasubramonian RDavis AJouppi N(2011)Combining memory and a controller with photonics through 3D-stacking to enable scalable and energy-efficient systemsACM SIGARCH Computer Architecture News10.1145/2024723.200011539:3(425-436)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/2024723.2000115
Ma SEnright Jerger NWang Z(2011)DBARACM SIGARCH Computer Architecture News10.1145/2024723.200011339:3(413-424)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/2024723.2000113
Romm A(2011)Solution to Exchanges 8.2 puzzleACM SIGecom Exchanges10.1145/1978721.197873210:1(40-44)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1145/1978721.1978732
Wright JJiang ALeyton-Brown K(2011)Linear solvers for nonlinear gamesACM SIGecom Exchanges10.1145/1978721.197872410:1(9-12)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1145/1978721.1978724
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten