PROGOL
Encyclopedia
Progol is an 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.
Inductive logic programming
Inductive logic programming is a subfield of machine learning which uses logic programming as a uniform representation for examples, background knowledge and hypotheses...
used in computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
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
Ehud Shapiro
Ehud Shapiro is an Israeli computer scientist at the Weizmann Institute of Science. He received his Ph.D from Yale for his dissertation entitled "Algorithmic Program Debugging" which was an ACM distinguished dissertation for 1982. He has been an exponent of the Prolog computer language and logic...
's Model Inference System (MIS) and J. Ross Quinlan
Ross Quinlan
John Ross Quinlan is a computer science researcher in data mining and decision theory. He has contributed extensively to the development of decision tree algorithms, including inventing the canonical C4.5 and ID3 algorithms...
's FOIL
First Order Inductive Learner
In machine learning, First Order Inductive Learner is a rule-based learning algorithm.-Background:Developed in 1990 by Ross Quinlan, FOIL learns function-free Horn clauses, a subset of first-order predicate calculus...
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
Prolog
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
programs as background knowledge and arbitrary definite clauses as examples. Despite this bench-tests show that the efficiency of Progol compares favourably with FOIL.