Ausarbeitung und Implementierung von Methoden, um den Overfitting-Effect im GeLog-System zu vermeiden

Student:Benjamin Landorff
Title:Ausarbeitung und Implementierung von Methoden, um den Overfitting-Effect im GeLog-System zu vermeiden
Type:diploma thesis
Advisors:Kókai, G.; Schneider, H.
State:submitted on July 9, 2002
Prerequisits:

Das Ziel des \emph{GeLog}-Systems ist, die Vorteile der Methoden der genetischen Algorithmen und induktiv logischen Programmierung zu nutzen. Dieses System ist auch bei umfangreichen Problemstellungen noch effizient einsetzbar und lässt sich sehr leicht auf das Erlernen von Zusammenhängen aus verschiedenen Aufgabenbereichen anpassen.

Mit dem automatischen Lernsystem {\it Gelog} können logische Programme erzeugt werden, die eine Lösung für eine gegebene Aufgabe darstellen. Die erlernten Programme liegen anschließend als Quelltext in der \hbox{logischen} Programmiersprache PROLOG vor und sind in dieser Form direkt ausführbar.
Zur Formulierung der Aufgabenstellung werden aus der induktiv \hbox{logischen} Programmierung bekannte Komponenten verwendet. Anhand von \emph{Beispieldaten} erlernt das System die \hbox{logischen} Zusammenhänge und formuliert diese mit Hilfe von Bausteinen aus dem \emph{Hintergrundwissen} als PROLOG-Programm.
Der eigentliche Lernvorgang basiert auf einem genetischen Algorithmus. Zu Beginn wird aus Elementen des Hintergrundwissens zufällig eine Menge von Programmen erzeugt, die eine sogenannte Population von Individuen bildet. Diese Individuen durchlaufen einen wiederkehrenden Evolutionszyklus, in dem Generation für Generation das Erbgut der Individuen weitergegeben, kombiniert und mutiert wird.
Dabei wird der Lernfortschritt eines einzelnen Individuums mit Hilfe der Beispieldaten ermittelt und bestimmt die Eignung des Individuums. Daraus leitet sich die Wahrscheinlichkeit ab, mit der die Erbinformation eines Individuums in die nächste Generation weitergegeben wird.
Um ein Programm an das Beispielwissen anzupassen, haben die Operatoren zur Rekombination und Mutation die gleichen Auswirkungen auf die Erbinformation wie die Generalisierungs- und Spezialisierungsmethoden der induktiv \hbox{logischen} Programmierung.
Genetische Algorithmen sind in der Lage auch große Ergebnisräume auf effiziente Weise zu durchsuchen und die darin enthaltenen vielversprechenden Regionen ausfindig zu machen. Dies ist ein entscheidender Vorteil für die Bearbeitung umfangreicher und komplexer Problemstellungen.
Die aus der induktiv \hbox{logischen} Programmierung stammenden Elemente Hintergrundwissen und Beispieldaten erlauben dabei eine einfache und flexible Anpassung des genetischen Algorithmus an die jeweilige Aufgabenstellung, ohne dass Eingriffe in das System selbst nötig sind.
Durch eine universelle Datenrepräsentation und die vielseitigen Möglichkeiten den Evolutionsverlauf durch Parameter zu beeinflussen, kann eine Vielzahl verschiedener Problemstellungen bearbeitet werden.

Topic:

Ein bekanntes Problem bei Lernalgorithmen ist das sogenannte overfitting der erlernten Hypothesen. Hierunter versteht man die zu starke Anpassung der gefundenen Relationen an die Trainingsbeispiele. Ist dies der Fall, werden oftmals Hypothesen erzeugt, die im Bezug auf die Beispiele komplett und konsistent sind, unbekannte Objekte aber mit einer hohen Wahrscheinlichkeit falsch klassifizieren.
Suche nach Mechanismen im Literatur, die die Behebung von overfitting beschreiben.
Auswertung der verschiedenen Methoden im Hinsicht auf die Anwendungsmöglichkeit in GeLog
Implementierung, Integration und Bewertung der ausgewählten Verfahren in GeLog

watermark seal