Diplomarbeit


Meine Diplomarbeit [Postscript (121 Seiten)] mit dem Titel Inductive Functional Programming - a Term-Construction and Folding Approach ist fertig. Ich habe sie bei Prof. Wysotzki an der Fachgruppe Methoden der Künstlichen Intelligenz geschrieben.

Zusammenfassung

IPAL ist ein integriertes System zur induktiven Synthese rekursiver, funktionaler Programme. Induktive Synthese entspricht dem Lernen eines Programms von einer unvollständigen Spezifikation, im Allgemeinen gegeben durch eine endliche Menge von Eingabe-/Ausgabe- Beispielen. Das inferierte Programm soll sowohl die Beispielmenge richtig berechnen, als auch eine "angemessene" Generalisierung darstellen. Das heisst, es soll neue Eingaben wie vom Benutzer erwartet berechnen. Das IPAL-System beinhaltet Planung, Plan-Transformation und das Falten. Der Synthese-Prozess orientiert sich an klassischen Ansätzen zur induktiven Synthese von funktionalen Programmen. Diese verfahren in zwei Schritten: Zunächst wird ein nicht rekursives Programm konstruiert, das genau die Beispielmenge richtig berechnet. Anschliessend wird, basierend auf dem Finden und Generalisieren von rekurrenten syntaktischen Mustern in dem nicht rekursiven Programm, ein rekursives Programm induziert. In IPAL wird der erste Schritt durch Planen und Plan-Transformation erledigt, der zweite durch Falten. Während der Falter auf Grundlagen von klassischen Ansätzen beruht und diese erweitert, sind Planen und Plan-Transformation neue Ansätze zum Erledigen des ersten Synthese-Schritts. Die Methoden, die in IPAL entwickelt wurden, stellen einen Fortschritt gegenüber früheren Methoden dar. Der Plan-Transformations-Prozess, der ein nicht rekursives Programm für einen universellen Plan als Eingabe liefert, ist jedoch noch nicht so gut entwickelt wie das Planen und Falten. Da das Falten von der Plan-Transformation abhängig ist, bleiben die Möglichkeiten von IPAL als einem integrierten System hinter denen des Planens und des Faltens zurück. In dieser Arbeit untersuche ich den Plan-Transformations-Prozess und entwickle einige Verbesserungen. Ausserdem lege ich einen theoretischen Rahmen für den Falter vor. Drittens reflektiere ich die Entscheidung, Planung und Plan-Transformation zu benutzen, um den ersten Synthese-Schritt zu realisieren. Ich zeige, dass diese Entscheidung substantielle Auswirkungen bezüglich der Klasse der Algorithmen, die prinzipiell synthetisiert werden können, hat.

Implementation

Alle Algorithmen sind in LISP implementiert und eingebettet in die existierenden IPAL-Implementationen.

IPAL

Aktuelle IPAL-Implementationen sind auf der IPAL-Projekt-Homepage zu finden: http://www.inf.uos.de/schmid/ipal.html. Sie beinhalten die universalen Planer DPlan und FPlan, den Falter und eine Implementation des größten Teils eines bisherigen Plan-Transformations-Algorithmus' (aus Kapitel 8 der Habilitationsarbeit von Ute Schmid, zu finden unter http://www.inf.uos.de/schmid/publications.html).

Aktueller Stand bei der Plan-Transformations-Implementation

Momentan existieren drei mehr oder weniger verschiedene Ansätze zum Transformieren von Plänen in Programmterme, die zum Generalisieren brauchbar sind, nebeneinander. Erstens der Ansatz, der im Techreport Wysotzki, F. and Schmid, U. (2001). Synthesis of Recursive Programs from Finite Examples by Detection of Macro-Functions. Technical Report, Number 01-2, Dept. of Computer Science, TU Berlin. (zu finden auf http://ki.cs.tu-berlin.de/pubs.html) berichtet wird und den ich in meiner Diplomarbeit in Abschnitt 4.2.1 behandele. Dieser war bisher überhaupt nicht implementiert. Zweitens der Ansatz, der in Kapitel 8 von Schmid, U. (Mai, 2001). Inductive Synthesis of Functional Programs -- Learning Domain-Specific Control Rules and Abstract Schemes. (Habilitation Thesis, published as Springer LNAI 2654, 2003) (zu finden auf http://www.inf.uos.de/schmid/publications.html) berichtet wird und auf den ich in Abschnitt 4.2.2 in meiner Diplomarbeit kurz eingehe. Dieser ist größtenteils implementiert. Und drittens meine Erweiterungen und Verbesserungen zum ersten Ansatz, die ich in meiner Diplomarbeit in Abschnitt 4.3, speziell in Abschnitt 4.3.4, erläutere.

Meine Implementationen

Während der Arbeit an meiner Diplomarbeit habe ich die meisten Algorithmen aus Kapitel 4 (Plan-Transformation) implementiert. Das sind teils Algorithmen des ersten Ansatzes, teils meine Erweiterungen. Im Einzelnen: Alle Codes und eine Readme-Datei beinhaltet das Paket da_codes.gzip.

Links


Emanuel Kitzelmann
Last modified: Mon Jun 14 14:01:04 MEST 2004