Suche   SiteMap
Home
A bis Z
BIB-KAT
Andere Bibliothekskataloge
Digitale Medien
Dokumentlieferung
Fachspezifische Informationen
Suchhilfen und Datenbanken
 
Eingang zum Volltext in OPUS

Hinweis zum Urheberrecht

Dissertation zugänglich unter
URN: urn:nbn:de:hbz:385-7379
URL: http://ubt.opus.hbz-nrw.de/volltexte/2012/737/


Formal tree languages and their algorithmic learnability

Formal tree languages and their algorithmic learnability

Formale Baumsprachen und ihre Lernbarkeit mittels algorithmischer Methoden

Kasprzik, Anna

pdf-Format:
Dokument 1.pdf (891 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: Theoretische Informatik , Algorithmische Lerntheorie , Mathematische Lerntheorie
Freie Schlagwörter (Englisch): Formal languages, grammatical inference
CCS - Klassifikation: Operations , Automata , Relations , Classes de
Institut: Informatik
Fakultät: Fachbereich 4
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Hauptberichter: Fernau, Henning
Sprache: Englisch
Tag der mündlichen Prüfung: 09.02.2012
Erstellungsjahr: 2011
Publikationsdatum: 05.04.2012
Kurzfassung auf Englisch: This thesis centers on formal tree languages and on their learnability by algorithmic methods in abstractions of several learning settings.
After a general introduction, we present a survey of relevant definitions for the formal tree concept as well as special cases (strings) and refinements (multi-dimensional trees) thereof. In Chapter 3 we discuss the theoretical foundations of algorithmic learning in a specific type of setting of particular interest in the area of Grammatical Inference where the task consists in deriving a correct formal description for an unknown target language from various information sources (queries and/or finite samples) in a polynomial number of steps. We develop a parameterized meta-algorithm that incorporates several prominent learning algorithms from the literature in order to highlight the basic routines which regardless of the nature of the information sources have to be run through by all those algorithms alike. In this framework, the intended target descriptions are deterministic finite-state tree automata. We discuss the limited transferability of this approach to another class of descriptions, residual finite-state tree automata, for which we propose several learning algorithms as well. The learnable class by these techniques corresponds to the class of regular tree languages. In Chapter 4we outline a recent range of attempts in Grammatical Inference to extend the learnable language classes beyond regularity and even beyond context-freeness by techniques based on syntactic observations which can be subsumed under the term 'distributional learning', and we describe learning algorithms in several settings for the tree case taking this approach. We conclude with some general reflections on the notion of learning from structural information.
Kurzfassung auf Deutsch: Die vorliegende Arbeit befasst sich mit formalen Baumsprachen und ihrer Lernbarkeit mit Hilfe algorithmischer Methoden. In einem ersten Teil geben wir eine Übersicht über die für das formale Baumkonzept relevanten Definitionen als auch Verfeinerungen und Spezialfälle desselben. Im zweiten Teil, der den Kern der Arbeit ausmacht, diskutieren wir theoretische Grundlagen eines bestimmten Modells algorithmischen Lernens, das sich als Forschungsgegenstand der Grammatikinferenz etabliert hat, und bei dem die Aufgabe darin besteht, anhand von Beispielen aus verschiedenen Informationsquellen eine korrekte formale Beschreibung einer unbekannten Zielsprache abzuleiten. Wir entwickeln eine Art Metaalgorithmus, der mehrere Lernalgorithmen aus der einschlägigen Literatur abdeckt, um die grundlegenden Arbeitsschritte herauszustellen, die weitgehend unabhängig von der Natur der gegebenen Informationsquellen von allen Algorithmen gleichermaßen durchgeführt werden müssen. Die gewählte Sprachbeschreibung ist in diesem Fall ein deterministischer endlicher Baumautomat, und wir diskutieren die Übertragbarkeit dieses Ansatzes auf eine weitere Beschreibungsklasse, den residuellen Baumautomaten, anhand konkreter Vorschläge für entsprechende Lernalgorithmen. Die auf diese Weise lernbare Klasse umfasst die regulären Baumsprachen. Im dritten inhaltlichen Teil umreißen wir einen Komplex neuerer Forschungsansätze, die Klassen algorithmisch lernbarer Sprachen mit Hilfe bestimmter syntaktisch orientierter Methoden (zusammengefasst unter dem Begriff des 'distributionellen Lernens' auszuweiten, und geben dabei ebenfalls einige konkrete Lernalgorithmen für den Baumfall an. Wir schließen mit ein paar Überlegungen zu generellen Aspekten algorithmischer Lernbarkeit.

Home | Suchen | Veröffentlichen | Hilfe | Viewer