Induktive logische Programmierung

Die Induktive logische Programmierung (ILP) ist ein Bereich des maschinellen Lernens, in dem Verfahren zur automatischen Erstellung von logischen Programmen aus Beispielen untersucht werden. Damit ähneln ILP-Verfahren der allgemeinen Induktion beim Denken. Der Begriff wurde 1991 in einem Artikel von Stephen Muggleton eingeführt. ^[1]

Im Gegensatz zu anderen symbolischen Lernverfahren wie ID3 und C4.5, deren Repräsentationsformat auf Aussagenlogik beschränkt ist, benutzen ILP-Verfahren eingeschränkte Formen der Prädikatenlogik als Repräsentationsformat für Beispiele, Hintergrundwissen und Hypothesen.

Problemstellung

In der normalen Problemstellung für ILP-Systeme sind Beispiele und ein Hintergrundwissen vorgegeben und das System versucht eine Theorie zu finden, die mit dem Hintergrundwissen die Beispiele korrekt herleitet. Das Hintergrundwissen B wird im Allgemeinen als Menge von Klauseln repräsentiert; die Beispiele e sind variablenfreie Atome. Dabei können positive, das heißt wahre, und negative, also falsche, Beispiele unterschieden werden. Die zu erstellende Theorie S ist eine Menge von Klauseln, die vereinigt mit B die Beispiele korrekt ableitet:

$S \cup B \models e$ für alle positiven Beispiele e

$S \cup B \not\models e$ für alle negativen Beispiele e

Daneben gibt es die sogenannte Nichtmonotone Problemstellung, die der Problemstellung des Data-Mining entspricht. Dabei ist eine Menge von Interpretationen gegeben und das Lernziel ist es, eine Klauselmenge zu finden, die in jeder Interpretation wahr ist.

Methoden

Die meisten ILP-Algorithmen induzieren die gesuchte Theorie, indem sie mit einer, eventuell leeren, Theorie beginnen und iterativ neue Klauseln hinzufügen. Positive Beispiele, die von einer neu hinzugefügten Klausel hergeleitet werden, können dann entfernt werden. Der Algorithmus terminiert, wenn alle positiven Beispiele entfernt wurden oder wenn ein anderes Kriterium erfüllt ist, etwa wenn die Beispiele nicht weiter durch neue Klauseln komprimiert werden können. Dieser Greedy-Algorithmus ist als Cover Set- oder Sequential Covering-Algorithmus bekannt.

Es gibt verschiedene Algorithmen, welche gute Klauseln, die zur Theorie hinzugefügt werden können, finden. Dabei lassen sich grob Top-Down- und Bottom-Up-Ansätze unterscheiden. In ersteren wird die Menge der Klauseln ausgehend von einer sehr allgemeinen Klausel durchsucht, im zweiten werden Klauseln direkt aus Beispielen generiert. Ein bekanntes Top-Down-System ist FOIL; ein bekanntes Beispiel für Bottom-Up-Systeme ist Golem. Systeme wie Progol, CHILLIN und ProGolem kombinieren beide Ansätze.

Konferenzen

Seit 1991 findet jedes Jahr eine Konferenz zum Thema statt.

Jahr	Datum	Ort	Vorsitz
2010	June 27-30	Florenz, Italien
2009	July 2-5	Leuven, Belgien, Katholieke Universiteit Leuven	Hendrik Blockeel, Luc De Raedt
2008	September 10-12	Prag, Tschechien, Czech Technical University	Filip Zelezny, Nada Lavrac
2007	June 19-21	Corvallis, Oregon, USA, Oregon State University	Jude Shavlik, Hendrik Blockeel, Prasad Tadepalli
2006	August 24-27	Santiago de Compostela, Spanien	Stephen Muggleton, Ramon Otero
2005	August 10-13	Bonn, Deutschland	Stephan Kramer, Bernhard Pfahringer
2004	September 6-8	Porto, Portugal	Ashwin Srinivasan, Ross King
2003	September 29-October 1	Szeged, Ungarn	Tamas Horváth, Akihiro Yamamoto
2002	July 9-11	Sydney, Australien	Stan Matwin, Claude Sammut
2001	September 9-11	Straßburg, Frankreich	Celine Rouveirol, Michele Sebag
2000	July 24-27	London, England	James Cussens, Alan Frisch
1999	June 24-27	Bled, Slowenien	Saso Dzeroski, Peter Flach
1998	July 22-24	Madison, Wisconsin, USA	C. David Page, Jr.
1997	September 17-20	Prag, Tschechien	Nada Lavrac, Saso Dzeroski
1996	August 26-28	Stockholm, Schweden	Stephen Muggleton
1995	September 4-6	Leuven, Belgien	Luc De Raedt
1994	September 12-14	Bonn, Deutschland	Stefan Wrobel
1993	April 1-3	Bled, Slowenien	Stephen Muggleton
1992	June 6-7	Tokio, Japan	Stephen Muggleton
1991	March 2-4	Viana do Castelo, Portugal	Stephen Muggleton

Implementierungen

• Progol (http://www.doc.ic.ac.uk/~shm/Software/progol5.0)
• Golem (ILP) (http://www.doc.ic.ac.uk/~shm/Software/golem)
• Aleph (http://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/Aleph/)
• ProGolem^[2]
• Foil (ftp://ftp.cs.su.oz.au/pub/foil6.sh)
• Claudien (http://www.cs.kuleuven.ac.be/~ml/CWIS/claudien-E.shtml)
• Lime (http://cs.anu.edu.au/people/Eric.McCreath/lime.html)
• ACE (http://www.cs.kuleuven.ac.be/~dtai/ACE/)
• DMax (http://www.pharmadm.com/dmax.asp)
• Warmr (http://www.cs.kuleuven.ac.be/~ml/Doc/TW_User/)
• RSD (http://labe.felk.cvut.cz/~zelezny/rsd/)
• Mio (http://kd.cs.uni-magdeburg.de/~pena/)
• DL-Learner (http://dl-learner.org)
• Mobal (http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/learning/systems/mobal/0.html)
• Kepler (https://www.aaai.org/Papers/KDD/1996/KDD96-035.pdf)
• Chillin (http://www.cs.utexas.edu/users/ml/chillin.html)

Literatur

Überblick

• H. Blockeel u.a.: Scaling Up Inductive Logic Programming by Learning from Interpretations. In: Data Mining and Knowledge Discovery 3, S. 59-93. Springer, 1999.
• S.H. Muggleton and L. De Raedt. Inductive logic programming: Theory and methods. Journal of Logic Programming, 19,20:629-679, 1994.
• S.H. 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. (Hrsg.): Probabilistic Inductive Logic Programming. (Lecture Notes in Artificial Intelligence, 4911). Springer, 2008.

Algorithmen

• Ross Quinlan. Learning logical definitions from relations. Machine Learning, 5:239–266, 1990. (beschreibt 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. (beschreibt Golem)

Weblinks

• ILP Network of Excellence

Einzelnachweise

1. ↑ S.H. Muggleton. Inductive Logic Programming. New Generation Computing, 8(4):295-318, 1991.
2. ↑ Stephen Muggleton u.A.: ProGolem: A System Based on Relative Minimal Generalisation. In: Luc de Raedt (Hrsg.): Inductive Logic Programming, 19th International Conference. Springer, Heidelberg/Berlin 2009. Seite 131-148.