{{Use dmy dates|date=September 2017}} {{distinguish|Prolog}} {{Infobox software | title = Progol | developer = [[Stephen Muggleton]] | latest release version = 4.4 | latest release date = {{Start date and age|2009|5|16|df=yes}} | repo = https://www.doc.ic.ac.uk/~shm/Software/progol4.4/ | programming language = [[C (programming language)|C]] | genre = [[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]].<ref>{{Cite journal | last1 = Muggleton | first1 = S. | title = Inverse entailment and progol | doi = 10.1007/BF03037227 | journal = New Generation Computing | volume = 13 | issue = 3–4 | pages = 245–286 | year = 1995 | citeseerx = 10.1.1.31.1630 | s2cid = 12643399 }}</ref><ref>{{Cite book | last1 = Muggleton | first1 = S. | title = Inductive Logic Programming | chapter = Learning from positive data | doi = 10.1007/3-540-63494-0_65 | volume = 1314 | pages = 358–376 | year = 1997 | series = Lecture Notes in Computer Science | isbn = 978-3-540-63494-2 }}</ref>
== Features == Inverse entailment is used with mode declarations to derive the bottom clause, the most-specific clause within the mode language{{define?|date=April 2021}} which [[Theta-subsumption|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 [[Ross Quinlan|J. Ross Quinlan]]'s [[First Order Inductive Learner|FOIL]], Progol's search has a provable guarantee of returning a solution having the maximum compression{{define?|date=April 2021}} in the search-space. To do so it performs an admissible [[A* search algorithm|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<ref>{{Cite journal |last1=Srinivasan |first1=A. |last2=Muggieton |first2=S.H. |last3=Sternberg |first3=M.J.E. |last4=King |first4=R.D. |date=1996 |title=Theories for mutagenicity: a study in first-order and feature-based induction |journal=Artificial Intelligence |volume=84 |issue=1–2 |pages=357 |doi=10.1016/0004-3702(96)81369-5 |issn=0004-3702|doi-access=free }}</ref> to predict the [[Mutagenicity|mutagenic]] activity in [[Nitroaromatic compound|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.<ref>{{Citation |last=De Raedt |first=Luc |title=Logical and Relational Learning |page=5 |year=2008 |access-date= |place=Berlin, Heidelberg |publisher=Springer |isbn=978-3-540-20040-6}}</ref>
Progol proved very influential in the field, and the widely-used inductive logic programming system [[Aleph (ILP)|Aleph]] builds directly on Progol. <ref name=":3">{{Cite journal |last1=Cropper |first1=Andrew |last2=Dumančić |first2=Sebastijan |date=2022-06-15 |title=Inductive Logic Programming At 30: A New Introduction |journal=Journal of Artificial Intelligence Research |volume=74 |page=808 |doi=10.1613/jair.1.13507 |issn=1076-9757|doi-access=free |arxiv=2008.07912 }}</ref>
==References== {{reflist}} [[Category:Inductive logic programming]]