Inductive logic programming

The Inductive logic programming ( ILP ) is an area of the machine learning , in the method for automatic generation of logic programs are examined from examples. ILP procedures are thus similar to general induction in thinking . The term was introduced in a 1991 article by Stephen Muggleton .

In contrast to other symbolic learning methods such as ID3 and C4.5 , whose representation format is restricted to propositional logic , ILP methods use restricted forms of predicate logic as a representation format for examples, background knowledge and hypotheses.

Problem

In the normal problem definition for ILP systems, examples and background knowledge are given and the system tries to find a theory that derives the examples correctly with the background knowledge. Background knowledge B is generally represented as a set of clauses ; the examples e are variable-free atoms . A distinction can be made between positive, i.e. true, and negative, i.e. false, examples. The theory S to be created is a set of clauses which, when combined with B, correctly derives the examples:

${\displaystyle S\cup B\models e}$ for all positive examples e

${\displaystyle S\cup B\not \models e}$ for all negative examples e

There is also the so-called non - monotonous problem , which corresponds to the problem of data mining . A set of interpretations is given and the learning goal is to find a set of clauses that is true in every interpretation.

Methods

Most ILP algorithms induce the desired theory by starting with a theory, possibly empty, and iteratively adding new clauses. Positive examples derived from a newly added clause can then be removed. The algorithm terminates when all positive examples have been removed or when another criterion is met, for example when the examples cannot be further compressed by new clauses. This greedy algorithm is known as the cover set or sequential covering algorithm.

There are several algorithms that can find good clauses that can be added to the theory. A rough distinction can be made between top-down and bottom-up approaches. In the former, the set of clauses is searched based on a very general clause, in the latter, clauses are generated directly from examples. A well-known top-down system is FOIL ; a well-known example of bottom-up systems is golem . Systems like Progol , CHILLIN and ProGolem combine both approaches.

Conferences

A conference on the subject has been held every year since 1991.

year	date	place	Chair
2013	August 28-30	Rio de Janeiro , Brazil
2012	September 17-19	Dubrovnik , Croatia
2011	31st July - 3rd August	Windsor Great Park, UK
2010	June 27-30	Florence , Italy
2009	July 2-5	Leuven , Belgium , Katholieke Universiteit Leuven	Hendrik Blockeel, Luc De Raedt
2008	September 10-12	Prague , Czech Republic , Czech Technical University	Filip Zelezny, Nada Lavrač
2007	June 19-21	Corvallis , Oregon , USA , Oregon State University	Jude Shavlik, Hendrik Blockeel, Prasad Tadepalli
2006	August 24-27	Santiago de Compostela , Spain	Stephen Muggleton, Ramon Otero
2005	August 10-13	Bonn , Germany	Stephan Kramer, Bernhard Pfahringer
2004	September 6-8	Porto , Portugal	Ashwin Srinivasan, Ross King
2003	September 29-October 1	Szeged , Hungary	Tamas Horváth, Akihiro Yamamoto
2002	July 9-11	Sydney , Australia	Stan Matwin, Claude Sammut
2001	September 9-11	Strasbourg , France	Celine Rouveirol, Michele Sebag
2000	July 24-27	London , England	James Cussens, Alan Frisch
1999	June 24-27	Bled , Slovenia	Saso Dzeroski, Peter Flach
1998	July 22-24	Madison , Wisconsin , USA	C. David Page, Jr.
1997	September 17-20	Prague , Czech Republic	Nada Lavrac, Saso Dzeroski
1996	August 26-28	Stockholm , Sweden	Stephen Muggleton
1995	September 4-6	Leuven , Belgium	Luc De Raedt
1994	September 12-14	Bonn , Germany	Stefan Wrobel
1993	April 1-3	Bled , Slovenia	Stephen Muggleton
1992	June 6-7	Tokyo , Japan	Stephen Muggleton
1991	March 2-4	Viana do Castelo , Portugal	Stephen Muggleton

Implementations

• Progol
• Golem (ILP)
• Aleph
• ProGolem
• Foil
• Claudias
• Lime
• ACE
• DMax
• Warmr
• RSD
• Million
• DL learner
• Mobal
• Kepler
• Chillin

literature

overview

• H. Blockeel et al. a .: Scaling Up Inductive Logic Programming by Learning from Interpretations. In: Data Mining and Knowledge Discovery 3, pp. 59-93. Springer, 1999.
• SH Muggleton and L. De Raedt. Inductive logic programming: Theory and methods. Journal of Logic Programming , 19, 20: 629-679, 1994.
• SH Nienhuys-Cheng and R. de Wolf: Foundations of Inductive Logic Programming. Lecture Notes in Artificial Intelligence (1228). Springer, 1997.
• Luc de Raedt: Logical and Relational Learning. Springer, 2008. ISBN 3540200401
• Luc De Raedt et al. (Ed.): Probabilistic Inductive Logic Programming. ( Lecture Notes in Artificial Intelligence , 4911). Springer, 2008.

Algorithms

• Ross Quinlan. Learning logical definitions from relations. Machine Learning, 5: 239-266, 1990. (describes FOIL)
• Stephen Muggleton. Inverse entailment and progol. New Generation Computing Journal, 13: 245-286, 1995.
• Stephen Muggleton and Cao Feng. Efficient induction in logic programs. In S. Muggleton, editor, Inductive Logic Programming, pages 281-298. Academic Press, 1992. (describes Golem)

Web links

• ILP Network of Excellence

Individual evidence

1. ↑ SH Muggleton. Inductive logic programming. New Generation Computing , 8 (4): 295-318, 1991.
2. ↑ http://www.doc.ic.ac.uk/~shm/Software/progol5.0
3. ↑ http://www.doc.ic.ac.uk/~shm/Software/golem
4. ↑ http://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/Aleph/
5. ↑ Stephen Muggleton and others: ProGolem: A System Based on Relative Minimal Generalization. In: Luc de Raedt (Ed.): Inductive Logic Programming, 19th International Conference. Springer, Heidelberg / Berlin 2009. Pages 131–148.
6. ↑ http://www.cs.cmu.edu/Groups/AI/areas/learning/systems/foil/
7. ↑ Archive link ( Memento of the original from June 11, 2008 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. 
8. ↑ Archive link ( Memento of the original from May 16, 2002 in the Internet Archive ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. 
9. ↑ http://www.cs.kuleuven.ac.be/~dtai/ACE/
10. ↑ Archive link ( Memento of the original dated August 30, 2009 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. 
11. ↑ - ( Memento of the original from June 7, 2008 in the Internet Archive ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. 
12. ↑ Archive link ( Memento of the original from March 1, 2007 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. 
13. ↑ Archive link ( Memento of the original from April 21, 2007 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. 
14. ↑ http://dl-learner.org
15. ↑ http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/learning/systems/mobal/0.html
16. ↑ https://www.aaai.org/Papers/KDD/1996/KDD96-035.pdf
17. ↑ http://www.cs.utexas.edu/users/ml/chillin.html