Progol

Not to be confused with Prolog.

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

Progol

Developer(s)	Stephen Muggleton
Stable release	4.4 / 16 May 2009; 15 years ago (2009-05-16)
Repository	https://www.doc.ic.ac.uk/~shm/Software/progol4.4/
Written in	C
Type	Inductive logic programming system
Website	https://www.doc.ic.ac.uk/~shm/progol.html

Features

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

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

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.