Jump to content

Progol

From Wikipedia, the free encyclopedia

Progol
Developer(s)Stephen Muggleton
Stable release
4.4 / 16 May 2009; 15 years ago (2009-05-16)
Repositoryhttps://www.doc.ic.ac.uk/~shm/Software/progol4.4/
Written inC
TypeInductive logic programming system
Websitehttps://www.doc.ic.ac.uk/~shm/progol.html

Progol is an implementation of inductive logic programming that combines inverse entailment with general-to-specific search through a refinement graph.[1][2]

Features

[edit]

Inverse entailment is used with mode declarations to derive the bottom clause, the most-specific clause within the mode language[definition needed] which subsume a given example. This clause is used to guide a refinement-graph search.

Unlike the searches of Ehud Shapiro's model inference system (MIS) and J. Ross Quinlan's FOIL, Progol's search has a provable guarantee of returning a solution having the maximum compression[definition needed] in the search-space. To do so it performs an admissible A*-like search, guided by compression, over clauses which subsume the most specific clause.

Progol deals with noisy data by using a compression measure to trade off the description of errors against the hypothesis description length. Progol allows arbitrary Prolog programs as background knowledge and arbitrary definite clauses as examples.

History

[edit]

Progol was introduced by Stephen Muggleton in 1995. In 1996, it was used by Ashwin Srinivasan, Muggleton, Michael Sternberg and Ross King[3] to predict the mutagenic activity in nitroaromatic compounds. This was considered a landmark application for inductive logic programming, as a general purpose inductive learner had discovered results that were both novel and meaningful to domain experts.[4]

Progol proved very influential in the field, and the widely-used inductive logic programming system Aleph builds directly on Progol. [5]

References

[edit]
  1. ^ Muggleton, S. (1995). "Inverse entailment and progol". New Generation Computing. 13 (3–4): 245–286. CiteSeerX 10.1.1.31.1630. doi:10.1007/BF03037227. S2CID 12643399.
  2. ^ Muggleton, S. (1997). "Learning from positive data". Inductive Logic Programming. Lecture Notes in Computer Science. Vol. 1314. pp. 358–376. doi:10.1007/3-540-63494-0_65. ISBN 978-3-540-63494-2.
  3. ^ Srinivasan, A.; Muggieton, S.H.; Sternberg, M.J.E.; King, R.D. (1996). "Theories for mutagenicity: a study in first-order and feature-based induction". Artificial Intelligence. 84 (1–2): 357. doi:10.1016/0004-3702(96)81369-5. ISSN 0004-3702.
  4. ^ De Raedt, Luc (2008), Logical and Relational Learning, Berlin, Heidelberg: Springer, p. 5, ISBN 978-3-540-20040-6
  5. ^ Cropper, Andrew; Dumančić, Sebastijan (15 June 2022). "Inductive Logic Programming At 30: A New Introduction". Journal of Artificial Intelligence Research. 74: 808. arXiv:2008.07912. doi:10.1613/jair.1.13507. ISSN 1076-9757.