Integration von Ausnahmen in MILES

Studienarbeit Nr. 1283



Zusammenfassung

Die Induktive Logikprogrammierung ist ein Forschungsgebiet im Schnittbereich von Maschinellem Lernen und Logikprogrammierung. Das Ziel der ILP ist, aus vorgegebenen endlichen Mengen von positiven und negativen Beispielen ein Logikprogramm zu induzieren, das die positiven Beispiele von den negativen unterscheidet und auch neu hinzukommende Beispiele richtig als positive oder negative Instanzen klassifiziert.

Das induzierte Logikprogramm heißt vollständig, wenn es alle positiven Beispiele abdeckt, und konsistent, wenn es kein negatives Beispiel abdeckt. Thema dieser Arbeit ist die Korrektur von inkonsistenten Logikprogrammen durch Deklaration von Ausnahmen. Die Aufgabenstellung wird zunächst aus theoretischer Sicht analysiert. Dann wird eine Wissensrevisionskomponente für das experimentelle ILP--System MILES vorgestellt, die inkonsistente Logikprogramme durch Deklara\-tion von Ausnahmen für einzelne Klauseln spezialisiert.

Der Kern der Wissensrevisionskomponente ist ein dreistufiges Konfidenzmodell zur heuristischen Auswahl der Klauseln, die spezialisiert werden. Das flexible Konfidenzmodell ist eine Verallgemeinerung des zweistufigen Konfidenzmodells von MOBAL [1] und läßt sich an verschiedene Induktionsverfahren anpassen, indem es mit Konfidenzklassen, heuristischen Konfidenzmaßen und einer Funktion zur Bewertung der empirischen Evidenz instanziiert wird. Auch die Einbindung eines Orakels ist möglich.

Die Spezialisierung durch Ausnahmen kann als Ausgangspunkt für das Erfinden neuer Prädikate dienen. Die Ausnahmen einer Klausel sind eine extensionale Darstellung von Wissen. Um sie durch eine intensionale Darstellung zu ersetzen, wird ein neues Prädikat generiert, das die erlaubten Instanziierungen einer Klausel von den Ausnahmen unterscheidet. Eine minimale Menge von Variablen der Klausel, die eine vollständige Unterscheidung zwischen zulässigen und unzulässigen Instanziierungen erlaubt, bildet die Argumente des neuen Prädikats. Dieser Ansatz liegt auch der DBC zugrunde [2]. Da sich der DBC--Algorithmus nicht auf die in MILES gegebene Aufgabenstellung übertragen läßt, wird eine Variante des DBC--Verfahrens entwickelt, die mit Begriffen der Rough Set--Theorie nach [3] beschrieben wird.


  1. S. Wrobel. On the proper definition of minimality in specialization and theory revision. In Machine Learning: ECML-93, European Conference on Machine Learning, Wien, Austria. Springer, 1993.
  2. B. Kijsirikul, M. Numao, and M. Shimura. Discrimination-based constructive induction of logic programs. In Proc. of the 10th National Conference on AI, 1992.
  3. Z. Pawlak, S. K. M. Wong, and W. Ziarko. Rough sets: probabilistic versus deterministic approach. Int. J. Man-Machine Studies, 11:81-95, 1988.

I. Weber / weberi@informatik.uni-stuttgart.de