Progol
| Developer(s) | Stephen Muggleton |
|---|---|
| Stable release | 4.4
/ 16 May 2009 |
| 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 |
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]- ^ 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.
- ^ 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.
- ^ 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.
- ^ De Raedt, Luc (2008), Logical and Relational Learning, Berlin, Heidelberg: Springer, p. 5, ISBN 978-3-540-20040-6
- ^ 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.