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.

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:

für alle positiven Beispiele 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.

JahrDatumOrtVorsitz
2022 September 28-30 Windsor Great Park, Großbritannien
2021 Oktober 25-27 Virtuell
2019 September 3-5 Plowdiw, Bulgarien
2018 September 2-4 Ferrara, Italien
2017 September 4-6 Orleáns, Frankreich
2016 September 4-6 London, Großbritannien
2015 August 20-22 Kyoto, Japan
2014 September 14-16 Nancy, Frankreich
2013August 28-30Rio de Janeiro, Brasilien
2012September 17-19Dubrovnik, Kroatien
201131st July - 3rd AugustWindsor Great Park, Großbritannien
2010June 27-30Florenz, Italien
2009July 2-5Leuven, Belgien, Katholieke Universiteit LeuvenHendrik Blockeel, Luc De Raedt
2008September 10-12Prag, Tschechien, Czech Technical UniversityFilip Zelezny, Nada Lavrač
2007June 19-21Corvallis, Oregon, USA, Oregon State UniversityJude Shavlik, Hendrik Blockeel, Prasad Tadepalli
2006August 24-27Santiago de Compostela, SpanienStephen Muggleton, Ramon Otero
2005August 10-13Bonn, DeutschlandStephan Kramer, Bernhard Pfahringer
2004September 6-8Porto, PortugalAshwin Srinivasan, Ross King
2003September 29-October 1Szeged, UngarnTamas Horváth, Akihiro Yamamoto
2002July 9-11Sydney, AustralienStan Matwin, Claude Sammut
2001September 9-11Straßburg, FrankreichCéline Rouveirol, Michèle Sebag
2000July 24-27London, EnglandJames Cussens, Alan Frisch
1999June 24-27Bled, SlowenienSaso Dzeroski, Peter Flach
1998July 22-24Madison, Wisconsin, USAC. David Page, Jr.
1997September 17-20Prag, TschechienNada Lavrac, Saso Dzeroski
1996August 26-28Stockholm, SchwedenStephen Muggleton
1995September 4-6Leuven, BelgienLuc De Raedt
1994September 12-14Bonn, DeutschlandStefan Wrobel
1993April 1-3Bled, SlowenienStephen Muggleton
1992June 6-7Tokio, JapanStephen Muggleton
1991March 2-4Viana do Castelo, PortugalStephen Muggleton

Implementierungen

  • Progol
  • Golem (ILP)
  • Aleph
  • ProGolem
  • Foil
  • Claudien
  • Lime
  • ACE
  • DMax
  • Warmr
  • RSD
  • Mio
  • DL-Learner
  • Mobal
  • Kepler
  • Chillin

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)

Einzelnachweise

  1. ↑ S.H. Muggleton. Inductive Logic Programming. New Generation Computing, 8(4):295-318, 1991.
  2. 1 2 3 4 5 6 7 8 IJCLR 2022: 32st International Conference on Inductive Logic Programming · International Joint Conference on Learning & Reasoning. Abgerufen am 1. Mai 2023 (amerikanisches Englisch).
  3. ↑ http://www.doc.ic.ac.uk/~shm/Software/progol5.0
  4. ↑ http://www.doc.ic.ac.uk/~shm/Software/golem
  5. ↑ http://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/Aleph/
  6. ↑ 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.
  7. ↑ http://www.cs.cmu.edu/Groups/AI/areas/learning/systems/foil/
  8. ↑ Archivlink (Memento des Originals vom 11. Juni 2008 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.
  9. ↑ Archivlink (Memento des Originals vom 16. Mai 2002 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.
  10. ↑ http://www.cs.kuleuven.ac.be/~dtai/ACE/
  11. ↑ Archivlink (Memento des Originals vom 30. August 2009 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.
  12. ↑ — (Memento des Originals vom 7. Juni 2008 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.
  13. ↑ Archivlink (Memento des Originals vom 1. März 2007 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.
  14. ↑ Archivlink (Memento des Originals vom 21. April 2007 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.
  15. ↑ http://dl-learner.org
  16. ↑ http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/learning/systems/mobal/0.html
  17. ↑ https://www.aaai.org/Papers/KDD/1996/KDD96-035.pdf
  18. ↑ http://www.cs.utexas.edu/users/ml/chillin.html
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.