Grafové algoritmy a závislostní parsing

• Název práce v češtině: Grafové algoritmy a závislostní parsing
• Název v anglickém jazyce: Graph-based dependency parsing
• Akademický rok vypsání: 2006/2007
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Ústav formální a aplikované lingvistiky (32-UFAL)
• Vedoucí / školitel: doc. RNDr. Pavel Pecina, Ph.D.
• Řešitel: MUDr. Mgr. Antonín Wimberský - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 09.11.2006
• Datum zadání: 09.11.2006
• Datum a čas obhajoby: 11.09.2007 00:00
• Datum odevzdání elektronické podoby: 11.09.2007
• Datum odevzdání tištěné podoby: 11.09.2007
• Datum proběhlé obhajoby: 11.09.2007
• Oponenti: Mgr. Pavel Schlesinger

Zásady pro vypracování

Aplikace grafových algoritmů v oblasti zpracování přirozeného jazyka se v poslední době stávají velmi populární a také úlohu závislostního parsingu je možné řešit pomocí algoritmu na hledání maximální kostry orientovaného ohodnoceného grafu. Slova analyzované věty tvoří vrcholy úplného grafu, ohodnocení hran se získá z trénovacích dat a nalezená maximální kostra pak reprezentuje nejlepší možný závislostní strom věty. Řešení bakalářské práce spočívá: a) v efektivní implementaci algoritmu pro hledání maximální kostry grafu, b) v implementaci výpočtu ohodnocení hran grafu a c) provedení experimentů.

Seznam odborné literatury

Christopher D. Manning, Hinrich Schutze: Foundations of Statistical Natural Language Processing, The MIT Press, 1999

R. McDonald, F. Pereira, K. Ribarov and J. Hajic, Non-Projective Dependency Parsing using Spanning Tree Algorithms
HLT-EMNLP, 2005