DFKI Document-93-15

[Back]

D-93-15



Sprache: Deutsch

by Robert Laux

Untersuchung maschineller Lernverfahren und heuristischer Methoden im Hinblick auf deren Kombination zur Unterstützung eines Chart-Parsers

86 Seiten

Zusammenfassung

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.

This document is available as PDF-File

The next abstract is here, and the previous abstract is here.

DFKI-Bibliothek (bib@dfki.uni-kl.de)

Note: This page was written to look best with CSS stylesheet support Level 1 or higher. Since you can see this, your browser obviously doesn't support CSS, or you have turned it off. We highly recommend you use a browser that supports and uses CSS, and review this page once you do. However, don't fear, we've tried to write this page to still work and be readable without CSS.