Original title: Strojové učení redukční analýzy
Translated title: Machine learning of analysis by reduction
Authors: Hoffmann, Petr ; Mráz, František (advisor) ; Otto, Friedrich (referee) ; Průša, Daniel (referee)
Document type: Doctoral theses
Year: 2013
Language: eng
Abstract: [eng] [cze]
We study the inference of models of the analysis by reduction that forms an important tool for parsing natural language sentences. We prove that the inference of such models from positive and negative samples is NP-hard when requiring a small model. On the other hand, if only positive samples are considered, the problem is effectively solvable. We propose a new model of the analysis by reduction (the so-called single k-reversible restarting automaton) and propose a method for inferring it from positive samples of analyses by reduction. The power of the model lies between growing context-sensitive languages and context-sensitive languages. Benchmarks using targets based on grammars have several drawbacks. Therefore we propose a benchmark working with targets based on random automata, that can be used to evaluate inference algorithms. This benchmark is then used to evaluate our inference method. 1 Práce se zabývá učením modelů redukční analýzy, která je důležitým nástrojem pro zpracování vět přirozeného jazyka. Dokazujeme, že hledání malých modelů na základě pozitivních a negativních příkladů je NP-těžké oproti úloze uvažující pouze pozitivní příklady, pro kterou navrhujeme efek- tivní algoritmus. Navrhujeme model redukční analýzy (tzv. single k-reversi- bilní restartovací automat) a metodu pro jeho učení z pozitivních příkladů redukčních analýz. Ukazujeme, že síla tohoto modelu leží mezi rostoucími kontextovými jazyky a kontextovými jazyky. Dále navrhujeme metodu pro testování učících algoritmů, která pracuje s cílovými jazyky založenými na náhodných automatech. Ta je následně použita na otestování naší učící metody. Navíc ukazujeme několik omezení testovacích metod používajících cílové jazyky založené na gramatikách. 1
Keywords: analysis by reduction; benchmark; grammatical inference; restarting automata; gramatická inference; redukční analýza; restartovací automaty; testování

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/53328

Permalink: http://www.nusl.cz/ntk/nusl-322628


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Doctoral theses