Progol Algorithm

A Progol Algorithm is an inductive logic programming algorithm that combines inverse entailment with general-to-specific search via a refinement graph.

• AKA: Muggleton's Progol Algorithm, Progol Inductive Learning Algorithm, Prolog ILP Algprithm.
• Context:
  • It is usually implemented by a Progol ILP System to solve a Progol ILP Task.
  • It can also be implemented as a Rule Induction Algorithm by a Rule Induction System.
  • It was developed by Muggleton (1995).
  • It allows the use of Prolog proggrams as examples.
• Example(s):
  • Progol 4.1 (source code,examples),
  • Progol 4.2 (source code, examples),
  • Progol 4.3,
  • Progol 4.4 (source code, examples),
  • Progol 4.5 (source code, examples),
  • Progol 5.0 (source code),
  • Lambda-Progol (Pahlavi, 2010),
  • CProgol (e.g. Muggleton & Firth, 2001).
  • …
• Counter-Example(s):
  • CN2 Algorithm,
  • FINDBESTRULE Algorithm,
  • FOIL Algorithm,
  • FURIA Algorithm,
  • LEM-based Algorithms,
  • RIPPER Algorithm,
  • Rulearner Alogrithm,
  • RULEX Algorithm.
• See: , Prolog Pattern Mining Algorithm, Decision Tree Induction Algorithm, Inductive Logic Programming, If-Then Rule, First-Order Logic Rule.

---

---

References

2019a

• (Progol, 2019) ⇒ https://www.doc.ic.ac.uk/~shm/progol.html Retrieved:2019-11-12.
  • QUOTE: Progol 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 Shapiro's MIS and 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.

2019b

• (Wikipedia, 2019) ⇒ https://en.wikipedia.org/wiki/PROGOL Retrieved:2019-11-13.
  • Progol is Stephen Muggleton's implementation of inductive logic programming used in computer science 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 model inference system (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 bench-tests show that the efficiency of Progol compares favourably with FOIL.

2010

• (Pahlavi, 2010) ⇒ Niels Pahlavi. (2010). “Higher-order Logic Learning and Lambda-Progol.” In: Proceedings of Technical Communications of the 26th International Conference on Logic Programming (ICLP 2010). ISBN:978-3-939897-17-0 doi:10.4230/LIPIcs.ICLP.2010.281.
  • QUOTE: We describe a first working implementation of lambda-Progol, a HOLL system adapting the ILP system Progol and the HOL formalism lambda-Prolog. We compare lambda-Progol and Progol on the learning of recursive theories showing that HOLL can, in these cases, outperform FOLL.

2003

• (Ray et al., 2003) ⇒ Oliver Ray, Krysia Broda, and Alessandra Russo (2003, September). “Hybrid Abductive Inductive Learning: A Generalisation Of Progol". In: International Conference on Inductive Logic Programming. DOI:10.1007/978-3-540-39917-9_21.
  • QUOTE: The Progol system of Muggleton [10] is a state-of-the-art and widely applied ILP system that has been successful in significant real world applications. Progol5 [7] is the latest system in the Progol family, which is based on the inference method of Bottom Generalisation ...

2001a

• (Muggleton & Firth, 2001) ⇒ Stephen Muggleton, and John Firth (2001). “Relational Rule Induction with CProgol 4.4: A Tutorial Introduction". In: Relational data mining (pp. 160-188). Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-04599-2_7
  • QUOTE: This chapter describes the theory and use of CPROGOL4.4, a publicly distributed version of the PROGOL family of ILP systems. In order to follow the examples in this chapter, it is assumed that the reader is familiar with the aims of ILP, Horn clause logic and Prolog notation for clauses. It is also assumed that the reader is familiar with the concepts of deductive logic in order to understand the theoretical foundations of PROGOL (...)

2001b

• (Ozaki & Furukawa, 2001) ⇒ Tomonobu Ozaki, and Koichi Furukawa (2001, September). “Application Of Pruning Techniques For Propositional Learning To Progol". In: International Conference on Inductive Logic Programming. DOI:10.1007/3-540-44797-0_17
  • QUOTE: By introducing unordered search to Progol, we can incorporate the effective pruning mechanism into Progol, which is basically independent of the order of literal in MSH.

2000

• (Muggleton & Bryant, 2000) ⇒ Stephen H. Muggleton, and Christopher H. Bryant (2000, July). “Theory Completion Using Inverse Entailment". In: International conference on inductive logic programming. DOI:10.1007/3-540-44960-4_8.
  • QUOTE: Progol5.0 is tested on two different data-sets. The first dataset involves a grammar which translates numbers to their representation in English. The second dataset involves hypothesising the function of unknown genes within a network of metabolic pathways. On both datasets near complete recovery of performance is achieved after relearning when randomly chosen portions of background knowledge are removed. Progol5.0’s running times for experiments in this paper were typically under 6 seconds on a standard laptop PC.

1998

• (Eineborg & Lindberg, 1998) ⇒ (1998, July). “Induction Of Constraint Grammar-Rules Using Progol". In: International Conference on Inductive Logic Programming (pp. 116-124). Springer, Berlin, Heidelberg. DOI:10.1007/bfb0027315
  • QUOTE: The paper reports a pilot study aiming at inducing rules for disambiguating words with different possible part of speech readings in unrestricted Swedish text. The rules, which are inspired by Constraint Grammar, are learnt using the Progol inductive logic programming system. The training data is sampled from the part of speech tagged one million word Stockholm-Umeå Corpus. The results show that the induction of disambiguation rules using Progol is a realistic way of learning rules of good quality with a minimum of manual effort. When tested on unseen data, 97% of the words retain the correct reading after tagging leaving an ambiguity of 1.15 readings per word.

1997

• (Cussens, 1997) ⇒ James Cussens (1997, September). “Part-Of-Speech Tagging Using Progol". In: International Conference on Inductive Logic Programming. DOI:10.1007/3540635149_38
  • QUOTE: A system for ‘tagging’ words with their part-of-speech (POS) tags is constructed. The system has two components: a lexicon containing the set of possible POS tags for a given word, and rules which use a word's context to eliminate possible tags for a word. The Inductive Logic Programming (ILP) system Progol is used to induce these rules in the form of definite clauses. The final theory contained 885 clauses. For background knowledge, Progol uses a simple grammar, where the tags are terminals and predicates such as noun (noun phrase) are non-terminals. Progol was altered to allow the caching of information about clauses generated during the induction process which greatly increased efficiency. The system achieved a per-word accuracy of 96.4% on known words drawn from sentences without quotation marks (...)

1995

• (Muggleton, 1995) ⇒ Stephen Muggleton (1995). “Inverse Entailment And Progol". New Generation Computing, 13(3-4), 245-286. DOI:10.1007/BF03037227
  • QUOTE: This paper firstly provides a re-appraisal of the development of techniques for inverting deduction, secondly introduces Mode-Directed Inverse Entailment (MDIE) as a generalisation and enhancement of previous approaches and thirdly describes an implementation of MDIE in the Progol system. Progol is implemented in C and available by anonymous ftp. The re-assessment of previous techniques in terms of inverse implication leads to new results for learning from positive data and inverting implication between pairs of clauses.

---