Induktive logische Programmierung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

Seit 1991 findet jedes Jahr eine Konferenz zum Thema statt.

Jahr Datum Ort Vorsitz
2013 August 28-30 Rio de Janeiro, Brasilien
2012 September 17-19 Dubrovnik, Kroatien
2011 31st July - 3rd August Windsor Great Park, Großbritannien
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[Bearbeiten]

Literatur[Bearbeiten]

Überblick[Bearbeiten]

  • 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[Bearbeiten]

  • 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[Bearbeiten]

Einzelnachweise[Bearbeiten]

  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.