Název: Strojové učení redukční analýzy
Překlad názvu: Machine learning of analysis by reduction
Autoři: Hoffmann, Petr ; Mráz, František (vedoucí práce) ; Otto, Friedrich (oponent) ; Průša, Daniel (oponent)
Typ dokumentu: Disertační práce
Rok: 2013
Jazyk: eng
Abstrakt: [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
Klíčová slova: gramatická inference; redukční analýza; restartovací automaty; testování; analysis by reduction; benchmark; grammatical inference; restarting automata

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/53328

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-322628


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Disertační práce