Difference between revisions of "Progol Algorithm"

From GM-RKB
Jump to: navigation, search
(ContinuousReplacement)
(Tag: continuous replacement)
Line 1: Line 1:
A [[Progol Algorithm]] is [[Inductive Logic Programming Algorithm]] that combines [[inverse entailment]] with [[general-to-specific search]] via a [[refinement graph]].
+
A [[Progol Algorithm]] is an [[inductive logic programming algorithm]] that combines [[inverse entailment]] with [[general-to-specific search]] via a [[refinement graph]].
 
* <B>AKA:</B> [[Progol Algorithm|Muggleton's Progol Algorithm]], [[Progol Algorithm|Progol Inductive Learning Algorithm]], [[Prolog ILP Algprithm]].
 
* <B>AKA:</B> [[Progol Algorithm|Muggleton's Progol Algorithm]], [[Progol Algorithm|Progol Inductive Learning Algorithm]], [[Prolog ILP Algprithm]].
 
* <B>Context:</U></B>
 
* <B>Context:</U></B>
Line 64: Line 64:
 
=== 1997 ===
 
=== 1997 ===
 
* (Cussens, 1997) ⇒ [[James Cussens]] (1997, September). [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.7266&rep=rep1&type=pdf "Part-Of-Speech Tagging Using Progol"]. In: International Conference on Inductive Logic Programming. [https://doi.org/10.1007/3540635149_38 DOI:10.1007/3540635149_38]
 
* (Cussens, 1997) ⇒ [[James Cussens]] (1997, September). [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.7266&rep=rep1&type=pdf "Part-Of-Speech Tagging Using Progol"]. In: International Conference on Inductive Logic Programming. [https://doi.org/10.1007/3540635149_38 DOI:10.1007/3540635149_38]
** QUOTE: A [[Tagging System|system for ‘tagging’]] words with their [[part-of-speech (POS) tag]]s is constructed. The system has two components: a [[lexicon]] containing the set of possible [[POS]] [[tag]]s for a given word, and [[rule]]s which use a word's context to eliminate possible tags for a word. The [[Inductive Logic Programming (ILP) system]] [[Progol Algorithm|Progol]] is used to [[Rule Induction|induce these rule]]s in the form of [[definite clause]]s. The final theory contained 885 [[clause]]s. For [[background knowledge]], [[Progol Algorithm|Progol]] uses a simple [[grammar]], where the tags are terminals and predicates such as noun ([[noun phrase]]) are [[non-terminal]]s. [[Progol Algorithm|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 mark]]s (...)
+
** QUOTE: A [[Tagging System|system for ‘tagging’]] words with their [[part-of-speech (POS) tag]]s is constructed. The system has two components: a [[lexicon]] containing the set of possible [[POS]] [[tag]]s for a given word, and [[rule]]s which use a word's context to eliminate possible tags for a word. The [[Inductive Logic Programming (ILP) system]] [[Progol Algorithm|Progol]] is used to [[Rule Induction|induce these rule]]s in the form of [[definite clause]]s. The final theory contained 885 [[clause]]s. For background knowledge, [[Progol Algorithm|Progol]] uses a simple [[grammar]], where the [[programming language tag|tag]]s are [[terminal]]s and [[programming language predicate|predicate]]s such as [[noun (noun phrase)]] are [[non-terminal]]s. [[Progol Algorithm|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 mark]]s (...)
  
 
=== 1995 ===
 
=== 1995 ===

Revision as of 17:55, 14 February 2020

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



References

2019a

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. [1] "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

2003

2001a

2001b

2000

1998

1997

1995