Publication
Untersuchung maschineller Lernverfahren und heuristischer Methoden im Hinblick auf deren Kombination zur Unterstützung eines Chart-Parsers
Robert Laux
DFKI, DFKI Documents (D), Vol. 93-15, 1993.
Abstract
Die schlechte Komplexität von Graph-Parsern für allgemeine Graphgrammatiken (NP-Vollständigkeit) legt die Verwendung von Heuristiken nahe. Aufgabe dieser Arbeit war es, zur Unterstützung des chart-basierten Graph- Parsers GraPaKL (für die Graphgrammatikklasse NRCFGG) eine Heuristikkomponente, die das benötigte Kontrollwissen durch ein Lernverfahren akquiriert, zu entwickeln. Dazu wurden zunächst verschiedene Repräsentationsarten von Kontrollwissen sowie verschiedene Lernverfahren zur Akquisition des Kontrollwissens diskutiert und festgestellt, daß sich die Repräsentation des Kontrollwissens in Form einer Bewertungsfunktion in Kombination mit dem konnektionistischen Lernverfahren Backpropagation am besten eignet. Die entwickelte Heuristikkomponente besteht aus zwei Modulen, dem Bewertungs- und dem Lernmodul. Das Bewertungsmodul steuert den Parser, indem es mittels einer Bewertungsfunktion Prioritäten an die Alternativen in der Agenda vergibt. Aufgrund der Tatsache, daß die Güte der Alternativen wesentlich vom Zustand des Parsers abhängt, setzt sich die Bewertungsfunktion aus zwei Teilen zusammen: einem statischen, d.h. vom aktuellen Zustand des Parsers unabhängigen, als auch einem dynamischen, also vom Parserzustand abhängigen Teil. Dabei kommt der dynamischen, situationsabhängigen Teilbewertung die Rolle der Primärsteuerung zu. Die dynamische Teilbewertungsfunktion wird durch das Lernmodul akquiriert. Der Benutzer bzw. Experte präsentiert Beispielparse, mit denen das Lernmodul die Bewertungsfunktion entsprechend verändert. Der Benutzer kann somit GraPaKL nur mittelbar, und zwar über das Lernmodul (durch die Präsentation von Beispielparsen) steuern; die konkrete Bewertungsfunktion bleibt dem Benutzer verborgen. Bemerkenswert ist, daß die Architektur der Heuristikkomponente unabhängig von der zugrundeliegenden Graphgrammatik (Domäne) ist. Darüberhinaus läßt sie sich durchaus auch auf agenda-basierte Chart-Parser für Stringgrammatiken übertragen. In (provisorischen) experimentellen Untersuchungen konnte die prinzipielle Eignung einerseits der Konzeption der Bewertungsfunktion und andererseits der Wahl des Lernverfahrens aufgezeigt werden. Ein systematisches Training mit verschiedenen Netzarchitekturen und Parameterkonstellationen konnte im Rahmen dieser Arbeit nicht durchgeführt werden, da dies aufwendige Testreihen erfordert hätte.