# Progol

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Progol
> Markdown URL: https://mediated.wiki/source/Progol.md
> Source: https://en.wikipedia.org/wiki/Progol
> Source revision: 1286013304
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Not to be confused with [Prolog](/source/Prolog).

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

**Progol** is an implementation of [inductive logic programming](/source/Inductive_logic_programming) that combines [inverse entailment](/source/Inverse_entailment) with general-to-specific search through a [refinement graph](/source/Refinement_graph).[1][2]

## Features

Inverse entailment is used with mode declarations to derive the bottom clause, the most-specific clause within the mode language[*[definition needed](https://en.wikipedia.org/wiki/Wikipedia:Please_clarify)*] which [subsume](/source/Theta-subsumption) a given example. This clause is used to guide a refinement-graph search.

Unlike the searches of [Ehud Shapiro](/source/Ehud_Shapiro)'s [model inference system](https://en.wikipedia.org/w/index.php?title=Model_inference_system&action=edit&redlink=1) (MIS) and [J. Ross Quinlan](/source/Ross_Quinlan)'s [FOIL](/source/First_Order_Inductive_Learner), Progol's search has a provable guarantee of returning a solution having the maximum compression[*[definition needed](https://en.wikipedia.org/wiki/Wikipedia:Please_clarify)*] in the search-space. To do so it performs an admissible [A*](/source/A*_search_algorithm)-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](/source/Prolog) programs as background knowledge and arbitrary definite clauses as examples.

## History

Progol was introduced by [Stephen Muggleton](/source/Stephen_Muggleton) in 1995. In 1996, it was used by Ashwin Srinivasan, Muggleton, [Michael Sternberg](/source/Michael_Sternberg) and Ross King[3] to predict the [mutagenic](/source/Mutagenicity) activity in [nitroaromatic compounds](/source/Nitroaromatic_compound). This was considered a landmark application for [inductive logic programming](/source/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](/source/Aleph_(ILP)) builds directly on Progol. [5]

## References

1. **[^](#cite_ref-1)** Muggleton, S. (1995). "Inverse entailment and progol". *New Generation Computing*. **13** (3–4): 245–286. [CiteSeerX](/source/CiteSeerX_(identifier)) [10.1.1.31.1630](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.1630). [doi](/source/Doi_(identifier)):[10.1007/BF03037227](https://doi.org/10.1007%2FBF03037227). [S2CID](/source/S2CID_(identifier)) [12643399](https://api.semanticscholar.org/CorpusID:12643399).

1. **[^](#cite_ref-2)** Muggleton, S. (1997). "Learning from positive data". *Inductive Logic Programming*. Lecture Notes in Computer Science. Vol. 1314. pp. 358–376. [doi](/source/Doi_(identifier)):[10.1007/3-540-63494-0_65](https://doi.org/10.1007%2F3-540-63494-0_65). [ISBN](/source/ISBN_(identifier)) [978-3-540-63494-2](https://en.wikipedia.org/wiki/Special:BookSources/978-3-540-63494-2).

1. **[^](#cite_ref-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"](https://doi.org/10.1016%2F0004-3702%2896%2981369-5). *Artificial Intelligence*. **84** (1–2): 357. [doi](/source/Doi_(identifier)):[10.1016/0004-3702(96)81369-5](https://doi.org/10.1016%2F0004-3702%2896%2981369-5). [ISSN](/source/ISSN_(identifier)) [0004-3702](https://search.worldcat.org/issn/0004-3702).

1. **[^](#cite_ref-4)** De Raedt, Luc (2008), *Logical and Relational Learning*, Berlin, Heidelberg: Springer, p. 5, [ISBN](/source/ISBN_(identifier)) [978-3-540-20040-6](https://en.wikipedia.org/wiki/Special:BookSources/978-3-540-20040-6)

1. **[^](#cite_ref-:3_5-0)** Cropper, Andrew; Dumančić, Sebastijan (15 June 2022). ["Inductive Logic Programming At 30: A New Introduction"](https://doi.org/10.1613%2Fjair.1.13507). *Journal of Artificial Intelligence Research*. **74**: 808. [arXiv](/source/ArXiv_(identifier)):[2008.07912](https://arxiv.org/abs/2008.07912). [doi](/source/Doi_(identifier)):[10.1613/jair.1.13507](https://doi.org/10.1613%2Fjair.1.13507). [ISSN](/source/ISSN_(identifier)) [1076-9757](https://search.worldcat.org/issn/1076-9757).

---
Adapted from the Wikipedia article [Progol](https://en.wikipedia.org/wiki/Progol) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Progol?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.