Závislostní analýza češtiny

Úvod – pro laiky

Závislostní analýza

Syntaktická analýza je postup, kterým k danému textu přiřadíme/určíme/nalezneme jeho strukturu. Tedy postup, který se na základní škole učí pod názvem větný rozbor.
Struktura textu se obvykle znázorňuje jedním ze dvou způsobů, buď pomocí větných složek (složková analýza) nebo pomocí závislostí (závislostní analýza).

Složková analýza spočívá v rozdělení věty do částí – složek a rozdělení těchto částí a jejich částí...

phrasal tree

Závislostní analýza vychází z pojmu závislost mezi slovy, kdy slovo závislé (podřízené, rozvíjející) závisí na slově řídícím.

dependency tree

Pro český jazyk se obvykle používá závislostní analýza.

Proč?

Abychom mohli větě porozumět. Pro překlad, pro přesnější vyhledávání...

Jak napsat závislostní analyzátor

Chceme vytvořit program, který dostane jako vstup větu a jako výstup vydá její závislostní strom.
To možná vypadá složitě, dokud si neuvědomíme, že strom nad větou o N slovech můžeme popsat jako vektor/pole N čísel A[i], která budou udávat, na kterém (kolikátém) slově závisí i-té slovo.

dependency vector

Kořen nezávisí na ničem – to znázorníme hodnotou 0. Provést závislostní analýzu věty, tj. přiřadit větě strom, tedy znamená vyplnit toto pole (nějakými) hodnotami.

Závislostní analyzátor dokáže napsat každý, za pět minut!

Problém bude v tom, že takový analyzátor nejspíš nebude přiřazovat správný strom.
Ale může nás utěšit, že

Správný závislostní analyzátor nedokáže napsat nikdo!

Opravdu? Jak to? Proč?

Přirozený jazyk je složitý. Některé věty lze chápat více způsoby, mají proto více stromů a neumíme říci, který je správný. Kočky žerou myši. Například. Nebo Ženu holí stroj. Ale ani pro věty, které nejsou víceznačné nebo obskurní, nemusí každý (dosavadní) analyzátor určit správně všechny závislosti. Takže existují jen více nebo méně špatné analyzátory.

Jak se měří kvalita analyzátoru?

Tak, jak by člověku napověděl rozum: Procentem správně určených závislostí.
A aby bylo možné analyzátory srovnávat, měří se na stejné množině vět z Pražského závislostní korpusu (Prague Dependency Treebank) - http://ufal.mff.cuni.cz/pdt/.

Jak dobré jsou současné závislostní analyzátory?

Aktualizovaný žebříček najdete na stránce http://ufal.mff.cuni.cz/czech-parsing/, v době psaní tohoto textu měl nejlepší analyzátor úspěšnost

85.8%

, takže každou sedmou závislost určoval špatně! Hanba!

            • každý páťák to umí dělat!
            • paní učitelka to dokáže vysvětlit a naučit!
            • nikdo to neumí naprogramovat!

Kdybyste napsali analyzátor, který i-té slovo zapojí pod (i-1)-ní, bude mít úspěšnost kolem 25%.

Jak pracují současné závislostní analyzátory?

Existuje několik přístupů: „ručně“ psaná pravidla pro zapojování a zase rozpojování hran, naučená pravidla, naučená historie... a jiné.

Pravidla představují informace o tom, mezi jakými slovy (případně v jakých souvislostech) vedou hrany. Pamatovat si takováto pravidla přímo pro slova (vlastně pro dvojice slov) by bylo příliš náročné, proto se obvykle pravidla vztahují k nějakým kategoriím slov, například

Pokud vedle sebe stojí přídavné jméno (nalevo) a podstatné jméno (napravo) a shodují se v rodě, v čísle a v pádě,
=> jde o shodný přívlastek a ono přídavné jméno bude záviset na onom podstatném jménu.

Neplatí to vždy, ale dost často ano.

Pravidla můžeme napsat sami (pokud známe dobře jazyk) nebo můžeme nechat program, aby se je naučil – již zmíněný Pražský závislostní korpus obsahuje ve skutečnosti tři sady vět: věty pro učení, věty pro testování a věty pro vyhodnocování; program může přečíst všechny věty určené pro učení, zapamatovat si, mezi jakými slovy (případně za jakých podmínek) vedou hrany a tuto znalost potom použít pro analýzu testovacích dat.

Historie Z testovacích dat se nemusíme učit jenom údaje o hranách – jako kdybyste se chtěli naučit hrát fotbal, můžete buďto vycházet z pravidel, nebo můžete nějakou dobu pozorovat hráče a učit se, co v které situaci dělá.
Analyzátory založené na tomto principu používají nějaký abstraktní „stroj“, jehož kroky postupně čtou větu a zapojují případně mění hrany mezi jejími slovy.
Tento stroj nechají pracovat na větách z učící množiny, kdy vědí, jaký strom má být výsledkem a tedy vědí, jaké akce má stroj v tu kterou chvíli provádět – a snaží se naučit pravidla pro výběr správné akce.
Takovým strojem může být třeba zásobníkový automat používaný například pro analýzu programovacích jazyků.

Download

Program pro konverzi vět z PDT

Věty v Pražském závislostním korpusu obsahují mnoho informací, v mnoha souborech v mnoha adresářích.
Tento program z vytvoří jednoduchá data pro jednoduché pokusy. Výstupem je jeden textový soubor, ve kterém je každá věta uložená na třech řádcích uvozených písmenem T, M nebo G obsahujících slova původní věty, morfologickou značku a číslo nadřízeného slova, vždy odděleno mezerou:

T to je užitečná funkce .
M PDNS1---------- VB-S---3P-AA--- AAFS1----1A---- NNFS1-----A---- Z
G 2 0 4 2 0

Zdrojový kód v Pascalu/Delphi: P66.dpr

Použití: p66.exe train p66.exe dtest p66.exe etest

Zásobníkový analyzátor

Tento program představuje analyzátor založený na učení se rozhodování zásobníkového analyzátoru. Podrobnosti viz publikace.
Má různé možnosti nastavení pomocí parametrů příkazové řádky (z jakých dat se učit, jestli před učením trénovací věty zprojektivnit (to překvapivě pomáhá), jestli tečce na konci věty nastavovat závislost 0 atd.) Další volby jsou v zakomentovaných částech zdrojového kódu.

Zdrojový kód v Pascalu/Delphi: P59.dpr

Kombinace analyzátorů

Program kombinující výsledky analyzátorů a hledající váhy pro vážené hlasování.

Zdrojový kód v Pascalu/Delphi: P48.dpr

Publikace:

Cizí:

  1. McDonald Ryan, Pereira Fernando, Ribarov Kiril, Hajič Jan: Non-Projective Dependency Parsing using Spanning Tree Algorithms
  2. Michael Collins: Head-Driven Statistical Models for Natural Language Parsing. PhD Dissertation, University of Pennsylvania, 1999.
  3. Daniel M. Bikel: Intricacies of Collins’ Parsing Model. in Computational Linguistics, 30(4), pp. 479-511., 2004.
  4. Nivre, J. and Nilsson, J. (2005) Pseudo-Projective Dependency Parsing.
  5. Nivre, J. (2003) An Efficient Algorithm for Projective Dependency Parsing. In Proceedings of the 8th International Workshop on Parsing Technologies (IWPT 03), Nancy, France, 23-25 April 2003, pp. 149-160.
  6. Nivre, J., Hall, J. and Nilsson, J. (2004) Memory-Based Dependency Parsing. In Ng, H. T. and Riloff, E. (eds.) Proceedings of the Eighth Conference on Computational Natural Language Learning (CoNLL), May 6-7, 2004, Boston, Massachusetts, pp. 49-56.
  7. Nivre, J. and Nilsson, J. (2003) Three Algorithms for Deterministic DependencyParsing. Proceedings of NoDaLiDa-2003.
  8. Matthias T. Kromann: Learning massively probabilistic grammars from treebanks using hierarchical partition models, to appear in Acta Linguistica Hafniensis.

  9. Kiril Ribarov: Automatic Building of a Dependency Tree - The Rule-Based Approach and Beyond
  10. Petr Kavan: Perceptronový parsing českých vět
  11. Daniel Zeman: Pravděpodobnostní model významových zápisů vět (Diplomová práce)
  12. Daniel Zeman: Parsing with a Statistical Dependency (PhD thesis)

Moje:

  1. A. HORÁK et. al. Dependency and Phrasal Parsers of the Czech Language: A Comparison. In: V. Matoušek and P. Mautner (Eds.): TSD 2007, LNAI 4629, pp. 76–84, 2007. Springer-Verlag Berlin Heidelberg 2007
  2. HOLAN, Tomáš et. al. On Complexity of Word Order. Les grammaires de dépendance - Traitement automatique des langues, 2000, vol. 41, no. 1, p. 273-300 . C3
  3. HOLAN, Tomáš. Segmentace vět pomocí šablon. In Vojtáš, Peter. ITAT 2006 Information Technologies – Applications and Theory. Košice: UPJŠ, 2006. s.181-184.
  4. HOLAN, Tomáš and ŽABOKRTSKÝ, Zdeněk. Combining Czech Dependency Parsers. In: Petr Sojka and Ivan Kopeček and Karel Pala. LNAI 4188. TSD'2006, Berlin Heidelberg: Springer-Verlag, 2006. s.95-102.
  5. HOLAN, Tomáš. Genetické učení závislostních analyzátorů. In Vojtáš, Peter. ITAT 2005 Information Technologies – Applications and Theory. Košice: UPJŠ, 2005. s.47-54.
  6. HOLAN, Tomáš et. al. A Theoretical Basis of an Architecture of a Shell of a Reasonably Robust Syntactic Analyser. In Matoušek, Václav and Mautner, Pavel. LNAI 2807. TSD '2003. Berlin/Heidelberg: Springer, 2003. s. 58-65.
  7. HOLAN, Tomáš a PLÁTEK, Martin. DR-parsing a DR-analýza. In Andrejková, Gabriela and Lencses, Rastislav. ITAT '2002 Information Technologies – Applications and Theory.. Košice: UPJŠ, 2002. s.1-10.
  8. HOLAN, Tomáš. Dependency Analyser Configurable by Measures. In: Petr Sojka and Ivan Kopeček and Karel Pala. LNAI 2448. TSD'2002. Berlin Heidelberg: Springer-Verlag, 2002. s.81-88.
  9. PLÁTEK, Martin et. al. Word-Order Relaxations and Restrictions within a Dependency Grammar. In Andrejková, Gabriela a Krajči, Stanislav. ITAT '2001: Information Technologies – Applications and Theory. Košice: UPJŠ, 2001. s.5-25.
  10. PLÁTEK, Martin et. al. Word-Order Relaxations and Restrictions within a Dependency Grammar. In Proceedings of International Workshop on Parsing Technologies. Peking: Tsingshua University Press, 2001. s. 237-240.
  11. PLÁTEK, Martin and HOLAN, Tomáš and KUBOŇ, Vladislav. On Relax-ability of Word-Order by D-grammars. In: Calude, C.S. and Dinneen, M. J. Combinatorics, Computability and Logic. Berlin: Springer Verlag, 2001. s. 159-174.
  12. HOLAN, Tomáš et. al. Two Useful Measures of Word Order Complexity. In: Kahane, Sylvain and Polguere, Alain. Proceedings of the Dependency-Based Grammars Workshop, the COLING - ACL Conference. Montreal: ACL, 1998. s. 21-28.
  13. HOLAN, Tomáš and KUBOŇ, Vladislav and PLÁTEK, Martin. A Prototype of a Grammar Checker for Czech. In: Proceedings of the Fifth Conference on Applied Natural Language Processing. Washington, DC, USA: Association for Computational Linguistics, 1997. s.147-154.
  14. PLÁTEK, Martin and KUBOŇ, Vladislav and HOLAN, Tomáš. Formal Tools for Separating Syntactically Correct and Incorrect Structures. In: Bunt Harry. Proceedings of the Conference IWPT'97. Boston, MA, USA: Massachusetts Institute of Technology, 1997. s. 247-248.
  15. HOLAN, Tomáš and KUBOŇ, Vladislav and PLÁTEK, Martin. Parsing of Free-word-order Languages. In:Bartošek, Miroslav and Staudek, Jan and Wiedermann, Jiří. LNCS 1012 SOFSEM 95 Proceedings of the 22nd Seminar on Current Trends in Theory and Practice of Informatic. Berlin: Springer-Verlag, 1995. s. 379-384.
  16. HOLAN, Tomáš. Tvorba závislostního syntaktického analyzátoru --- rok poté. In Obdržálek, David a Štanclová Jana a Plátek, Martin: MIS 2005, Sborník semináře. Praha: Matfyzpress, 2005. s.29-37.
  17. PLÁTEK, Martin a HOLAN, Tomáš. Závislostní a složkové modelování syntaxe jazyků. In Obdržálek, David a Tesková Jana: MIS 2004, Sborník semináře. Praha: Matfyzpress, 2004. s. 115-150.
  18. HOLAN, Tomáš. Tvorba závislostního syntaktického analyzátoru. In Obdržálek, David a Tesková Jana: MIS 2004, Sborník semináře. Praha: Matfyzpress, 2004. s. 16-26.
  19. HOLAN, Tomáš. K syntaktické analýze českých (!) vět. In Obdržálek, David a Tesková Jana: MIS 2003, Sborník semináře. Praha: Matfyzpress, 2003. s. 66-74.
  20. HOLAN, Tomáš and KUBOŇ, Vladislav and PLÁTEK, Martin. An Implementation of Syntactic Analysis of Czech. In:Bunt Harry. Fourth International Workshop on Parsing Technologies. Praha: Institute of Formal and Applied Linguistics, Charles University, Prague, 1995. s. 126-135. D.
  21. HOLAN, Tomáš et. al. Robustness with Reason. Technical Report TR-2002-11. Wien: Österreichisches Forschungsinstitut für Artificial Intelligence, 2002.
  22. Holan Tomáš. Nástroje pro vývoj závislostních anayzátorů přirozených jazyků s volným slovosledem. Disertační práce. Praha: MFF UK, 2001.
  23. Plátek Martin et. al. Word-Order Relaxations and Restrictions within a Dependency Grammar. Technická zpráva 2001/2. Praha: MFF UK, 2001.
  24. Plátek Martin et. al. On Relax-ability of Word-Order by D-grammars. Technická zpráva 2001/1. Praha: MFF UK, 2001.
  25. HOLAN, Tomáš et. al. On Complexity of Word Order. Technická zpráva 2000/8. Praha: MFF UK, 2000.
  26. HOLAN, Tomáš et. al. Two Useful Measures of Word Order Freedom. Technická zpráva 98/4. Praha: MFF UK, 1998.
  27. HOLAN, Tomáš and KUBOŇ, Vladislav and PLÁTEK, Martin. Formal Tools Supporting Development of a Grammar Checker. Technická zpráva 9/1996. Praha: MFF UK, 1996.
  28. KUBOŇ, Vladislav and HOLAN, Tomáš and PLÁTEK, Martin. A Grammar-Checker for Czech. Technická zpráva TR 1997-02. Praha: ÚFAL MFF UK, 1997.
  29. HOLAN, Tomáš and KUBOŇ, Vladislav and PLÁTEK, Martin. Parsing of free-word-order languages. Technická zpráva 5/1995. Praha: MFF UK, 1995.
---