imported>Eriosw: archivlinks geprüft

2025-05-10T13:37:33Z

archivlinks geprüft

Neue Seite

Die '''Induktive logische Programmierung''' (''ILP'') ist ein Bereich des [[Maschinelles Lernen|maschinellen Lernens]], in dem Verfahren zur automatischen Erstellung von [[Logische Programmierung|logischen Programmen]] aus Beispielen untersucht werden. Damit ähneln ILP-Verfahren der allgemeinen [[Induktion (Philosophie)|Induktion beim Denken]]. Der Begriff wurde 1991 in einem Artikel von [[Stephen Muggleton]] eingeführt.<ref>S.H. Muggleton. Inductive Logic Programming. ''New Generation Computing'', 8(4):295-318, 1991.</ref>

Im Gegensatz zu anderen [[Maschinelles Lernen#Repräsentation des Wissens|symbolischen]] Lernverfahren wie [[Iterative Dichotomiser 3|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 [[Disjunktionsterm|Klauseln]] repräsentiert; die Beispiele ''e'' sind variablenfreie [[Atom]]e. 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:

<math>S \cup B \models e</math> für alle positiven Beispiele e

<math>S \cup B \not\models e</math> 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 [[Interpretation (Logik)|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 (ILP)|Golem]]. Systeme wie [[Progol]], [[CHILLIN]] und [[ProGolem]] kombinieren beide Ansätze.

== Konferenzen ==
Seit 1991 findet jedes Jahr eine Konferenz zum Thema statt.
{| class="wikitable"
|- bgcolor="#CCCCCC"
! Jahr !! Datum !! Ort!! Vorsitz
|-
|[[2022]]<ref name=":0">{{Internetquelle |autor=IJCLR 2022 |url=https://ijclr22.doc.ic.ac.uk/ilp2022.html/ |titel=32st International Conference on Inductive Logic Programming · International Joint Conference on Learning & Reasoning |sprache=en-us |abruf=2023-05-01}}</ref>
|September 28-30
|[[Windsor Great Park]], [[Vereinigtes Königreich|Großbritannien]]
|
|-
|[[2021]]<ref name=":0" />
|Oktober 25-27
|Virtuell
|
|-
|[[2019]]<ref name=":0" />
|September 3-5
|[[Plowdiw]], [[Bulgarien]]
|
|-
|[[2018]]<ref name=":0" />
|September 2-4
|[[Ferrara]], [[Italien]]
|
|-
|[[2017]]<ref name=":0" />
|September 4-6
|[[Orléans|Orleáns]], [[Frankreich]]
|
|-
|[[2016]]<ref name=":0" />
|September 4-6
|[[London]], [[Vereinigtes Königreich|Großbritannien]]
|
|-
|[[2015]]<ref name=":0" />
|August 20-22
|[[Kyōto|Kyoto]], [[Japan]]
|
|-
|[[2014]]<ref name=":0" />
|September 14-16
|[[Nancy]], [[Frankreich]]
|
|-
| [http://ilp13.cos.ufrj.br/ 2013] || August 28-30 || [[Rio de Janeiro]], [[Brasilien]] ||
|-
| [http://ida.felk.cvut.cz/ilp2012/ 2012] || September 17-19 || [[Dubrovnik]], [[Kroatien]] ||
|-
| [http://ilp11.doc.ic.ac.uk/ 2011] || 31st July - 3rd August || Windsor Great Park, [[Vereinigtes Königreich|Großbritannien]] ||
|-
| [http://ilp2010.dsi.unifi.it/ 2010] || June 27-30 || [[Florenz]], [[Italien]] ||
|-
| [http://www.cs.kuleuven.be/~dtai/ilp-mlg-srl/index.php 2009] || July 2-5 || [[Leuven]], [[Belgien]], [[Katholieke Universiteit Leuven]] || Hendrik Blockeel, Luc De Raedt
|-
| [http://ida.felk.cvut.cz/ilp2008/ 2008] || September 10-12 || [[Prag]], [[Tschechien]], [[Czech Technical University]] || Filip Zelezny, [[Nada Lavrač]]
|-
| [http://oregonstate.edu/conferences/ilp2007/ 2007] || June 19-21 || [[Corvallis, Oregon|Corvallis]], [[Oregon]], [[USA]], [[Oregon State University]] || Jude Shavlik, Hendrik Blockeel, Prasad Tadepalli
|-
| [http://ilp06.doc.ic.ac.uk/ 2006] || August 24-27 || [[Santiago de Compostela]], [[Spanien]] || Stephen Muggleton, Ramon Otero
|-
| [http://ilp2005.in.tum.de/ 2005] || August 10-13 || [[Bonn]], [[Deutschland]] || Stephan Kramer, Bernhard Pfahringer
|-
| [http://ilp.fe.up.pt/ilp/ 2004] || September 6-8 || [[Porto]], [[Portugal]] || Ashwin Srinivasan, Ross King
|-
| [http://www.inf.u-szeged.hu/kutatas/konferenciak/ilp2003/ 2003] || September 29-October 1 || [[Szeged]], [[Ungarn]] || Tamas Horváth, Akihiro Yamamoto
|-
| [http://www.site.uottawa.ca/~stan/ilp2002/ 2002] || July 9-11 || [[Sydney]], [[Australien]] || Stan Matwin, Claude Sammut
|-
| 2001 || September 9-11 || [[Straßburg]], [[Frankreich]] || Céline Rouveirol, [[Michèle Sebag]]
|-
| [http://www.cs.york.ac.uk/ILP-events/ILP-2000/ 2000] || July 24-27 || [[London]], [[England]] || James Cussens, Alan Frisch
|-
| 1999 || June 24-27 || [[Bled]], [[Slowenien]] || Saso Dzeroski, Peter Flach
|-
| [http://pages.cs.wisc.edu/~dpage/ilp98.html 1998] || July 22-24 || [[Madison, Wisconsin|Madison]], [[Wisconsin]], [[USA]] || C. David Page, Jr.
|-
| [http://www-ai.ijs.si/SasoDzeroski/ilp97.html 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]]<ref>http://www.doc.ic.ac.uk/~shm/Software/progol5.0</ref>
* [[Golem (ILP)]]<ref>http://www.doc.ic.ac.uk/~shm/Software/golem</ref>
* [[Aleph (inductive logic programming)|Aleph]]<ref>http://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/Aleph/</ref>
* ProGolem<ref>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.</ref>
* Foil<ref>http://www.cs.cmu.edu/Groups/AI/areas/learning/systems/foil/</ref>
* Claudien<ref>{{Webarchiv |url=http://www.cs.kuleuven.ac.be/~ml/CWIS/claudien-E.shtml |text=Claudien |wayback=20080611191846}}; abgerufen am 4. März 2024.</ref>
* Lime<ref>{{Webarchiv|text=Archivlink |url=http://cs.anu.edu.au/people/Eric.McCreath/lime.html |wayback=20020516195248 }}. Abgerufen am 4. April 2024.</ref>
* ACE<ref>{{Internetquelle |url=http://www.cs.kuleuven.ac.be/~dtai/ACE/ | titel=The ACE Datamining System | sprache=en | abruf=2025-05-10}}</ref>
* DMax<ref>{{Webarchiv|text=Archivlink |url=http://www.pharmadm.com/dmax.asp |wayback=20090830031456 }}</ref>
* Warmr<ref>{{Webarchiv|url=http://www.cs.kuleuven.ac.be/~ml/Doc/TW_User/ |wayback=20080607112634 |text=Tilde und Warmr User Manual }}</ref>
* RSD<ref>{{Webarchiv|text=Archivlink |url=http://labe.felk.cvut.cz/~zelezny/rsd/ |wayback=20070301162526 }}</ref>
* Mio<ref>{{Webarchiv|text=Archivlink |url=http://kd.cs.uni-magdeburg.de/~pena/ |wayback=20070421195136 }}</ref>
* DL-Learner<ref>http://dl-learner.org</ref>
* Mobal<ref>http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/areas/learning/systems/mobal/0.html</ref>
* Kepler<ref>https://www.aaai.org/Papers/KDD/1996/KDD96-035.pdf</ref>
* Chillin<ref>http://www.cs.utexas.edu/users/ml/chillin.html</ref>

== 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 ==
* [http://www-ai.ijs.si/~ilpnet2/ ILP Network of Excellence]

== Einzelnachweise ==
<references />

[[Kategorie:Maschinelles Lernen]]
[[Kategorie:Programmierparadigma]]

Induktive logische Programmierung - Versionsgeschichte

imported>Eriosw: archivlinks geprüft