Formal tree languages and their algorithmic learnability
Formale Baumsprachen und ihre Lernbarkeit mittels algorithmischer Methoden
- 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.
- 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.
Author: | Anna Kasprzik |
---|---|
URN: | urn:nbn:de:hbz:385-7379 |
DOI: | https://doi.org/10.25353/ubtr-xxxx-ff17-04fc |
Title Additional (English): | Formal tree languages and their algorithmic learnability |
Advisor: | Henning Fernau |
Document Type: | Doctoral Thesis |
Language: | English |
Date of completion: | 2012/04/05 |
Publishing institution: | Universität Trier |
Granting institution: | Universität Trier, Fachbereich 4 |
Date of final exam: | 2012/02/09 |
Release Date: | 2012/04/05 |
Tag: | Formal languages; grammatical inference |
GND Keyword: | Algorithmische Lerntheorie; Mathematische Lerntheorie; Theoretische Informatik |
Institutes: | Fachbereich 4 / Informatik |
Dewey Decimal Classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |