PROGOL

In computer science, Progol is an implementation of Inductive Logic Programming that combines Inverse Entailment with general-to-specific search through a refinement graph. Inverse Entailment is used with mode declarations to derive the most-specific clause within the mode language which entails a given example. This clause is used to guide a refinement-graph search. Unlike the searches of Ehud Shapiro's MIS and J. Ross Quinlan's FOIL, Progol's search is efficient and has a provable guarantee of returning a solution having the maximum "compression" 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 the 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. Despite this, in bench-tests the efficiency of Progol compares favourably with FOIL.

References

* S. Muggleton (1995) "Inverse Entailment and Progol" "New Generation Computing Journal" 13, pp. 245-286
* S. Muggleton (1997), "Learning from positive data", "Proceedings of the Sixth International Workshop on Inductive Logic programming", Springer-Verlag, LNAI 1314

External links

* [http://www.doc.ic.ac.uk/~shm/progol.html Progol] page at Imperial College