Úvod

V této práci zavádíme a studujeme exaktní pojem (úplné) redukční analýzy A-stromů (URAS). A-stromy modelují stromy analytické roviny Pražského závislostního korpusu (PDT). URAS obsahuje všechny korektní redukce, které lze zařadit do lingvisticky korektní (manuální) redukční analýzy na A-stromech. URAS používá operace delete a shift a jeho redukce jsou minimalizovány s ohledem na počet těchto operací. Postupně zavádíme různé další omezující parametry, které je možno minimalizovat a užívat pro jemnější aproximace lingvisticky intuitivní redukční analýzy. Zavádíme tříčlennou škálu stability pro omezené URAS. Za korektní omezené URAS považujeme ty, co jsou stabilní alespoň v tom nejslabším smyslu. Stabilita pomáhá hledat spodní odhady pro intuitivní redukční analýzu. Typ stability určuje větší či menší vzdálenost od neomezené URAS.

Zavedené pojmy používáme pro klasifikaci pozorování lingvistického typu. Pozorujeme množiny A-stromů, které odpovídají českým větám a jsou zpracovány metodikou analytické roviny PDT. Odkrýváme tak řadu strukturálních vlastností takovýchto A-stromů. Povšimněme si, že prezentovaná pozorování jsou smysluplná a netriviální na konečných i nekonečných jazycích (množinách). To je ve spojitosti s lingvistikou velmi užitečné. Prezentujeme strukturální pozorování a nekombinujeme je (zatím) s pozorováními statistického typu.

1.1 Neformální úvod do redukční analýzy.

V této sekci neformálně představujeme redukční analýzu A-stromů se závislostmi a s koordinacemi. Redukční analýzou českých vět a jejímu modelování se zabýváme již delší dobu. Jako základní variantu redukční analýzy předkládáme úplnou redukční analýzu A-stromů (URAS). Navazujeme na články z minulých let (viz [2,1,3]). Při zavádění variant redukčních analýz zvýrazňujeme jejich minimalistický charakter.

URAS je založena na postupném zjednodušování Astromu po minimálních krocích. URAS definuje všechny možné posloupnosti větných redukcí -každá redukce spočívá ve vypuštění několika uzlů, nejméně však jednoho uzlu analyzovaného A-stromu. V A-stromě vypouštíme tak, abychom z A-stromu získali opět A-strom a každá cesta v novém A-stromě byla podposloupností cesty v původním A-stromě. Viz např. obrázky z příkladu 1. V některých redukcích může být kromě vypouštění použita operace shift, která přesune nějaký uzel na novou pozici v Astromě.

V našich lingvistických pozorováních budeme rozlišovat vypouštění listů a vypouštění vnitřních uzlů. Kořeny se v URAS nevypouští. Intuitivně i v URAS u většiny závislostních jevů stačí používat vypouštění listů. Ukážeme, že redukce koordinací v PDT s vypouštěním listů nevystačí.

Metoda URAS je popsaná následujícími zásadami:

(i) URAS je složena z jednotlivých redukcí; redukce používají operace dvou typů : (1) vypuštění (delete) a ( 2) přesun (shift); To znamená, že tvary jednotlivých slov (i interpunkčních znamének), jejich morfologické charakteristiky i jejich syntaktické kategorie se nemění během jednotlivých redukcí.

(ii) Struktura, která je korektním A-stromem, musí být korektním A-stromem i po redukci.

(iii) Redukce nepatří do předem vytipované množiny zakázaných redukcí. Příkladem zakázané redukce je vynechání samotného zvratného ´se´.

(iv) Uvažujeme jen nezmenšitelné redukce, t.j. vynecháme-li z libovolné redukce jednu či více operací, nastane porušení principu zachování gramatické správnosti (ii) nebo redukce se stane zakázanou a tím poruší princip (iii).

(v) URAS obsahuje všechny možné redukce splňující zásady (i) až (iv).

URAS tvoří základ, z kterého budeme odvozovat další varianty redukční analýzy, tak aby odpovídaly některým typům lingvistické (minimalisticé) intuice. Tento záměr budeme rozvíjet především ve formální části.

V následujících odstavcích nejprve uvedeme jeden příklad ilustrující URAS. Příklad se týká jen redukcí, které zjednodušují závislosti. Později budou následovat příklady, týkající se koordinací. Příklady nejprve poslouží pro úvod do problematiky, později (ve výsledkové části) jako separační příklady pro taxonomii redukčních analýz. Astromy na obrázcích v našich příkladech jsou oproti stromům z PDT trochu zjednodušené. Za prvé: neobsahují identifikační uzel, který nenese žádnou syntaktickou informaci a neodpovídá žádnému slovu věty. Za druhé: značka 'Coord' je nahrazena značkou 'Cr' a za třetí vynecháváme morfologické značky.

Všimněme si, že korektní A-strom zcela určuje jednu korektní českou větu i s jejím korektním značkováním.

Příklad 1. Zde ilustrujeme URAS k větě (1). Nevypouštíme zvratnou částici se, nebot' vypuštění pouhé zvratné částice považujeme za zakázanou redukci. Zde vůbec nepoužíváme shift.

(1) Rozhodl.Pred se.AuxT dnes.Adv odstoupit.Sb ..AuxK Obrázek 1 reprezentuje schema větné redukční analýzy (tzv. UPRA). Isomorfní (velmi podobné) schema mají URAS A-stromů T1 1 a T1 2 z obrázku 2. Obrázek 1 zde zastupuje i tato schemata.

V jednotlivých redukcích URAS A-stromu T1 1 se vypouštějí jen listy, tedy redukcemi nevznikají nové hrany. U T1 2 , při redukci položky 'odstoupit.Sb', se vypouští vnitřní uzel A-stromu, tedy vzniká nová hrana a to v tomto případě signalizuje změnu významu. To není žádoucí.

Vznikne tak strom T1 Formalizace redukční analýzy analytických stromů se neobejde bez formalizace lexikální analýzy.

Formalizace lexikální analýzy

Při formalizaci lexikální analýzy rozlišujeme tři konečné množiny slov a značek. Σ p označuje tzv. vlastní slovník 1 , který obsahuje jednotlivé slovní formy a interpunkční znaménka daného jazyka. Σ c označuje tzv. kategoriální seznam, tedy množinu syntakticko-morfologických značek. Hlavní slovník Γ ⊆ Σ p × Σ c reprezentuje zjednoznačněnou lexikální analýzu daného jazyka.

Projekce z Γ + do Σ * p resp. do Σ * c přirozeně definujeme pomocí homomorfismů: slovníkovým homomorfismem h p : V abecedě kategorií v tomto příkladě jsou využity jen jednoduché závislostní kategorie (ne všechny). Kategorie mohou být složené z více značek. Kategorie pro koordinace budou obsahovat značky 'Cr', nebo 'Co'.

Γ → Σ p a kategoriálním homomorfismem h c : Γ → Σ c : h p ([a, b]) = a a h c ([a, b]) = b pro všechny [a, b] ∈ Γ. Příklad 2. V našich

Věty v našich příkladech končí sentinelem (ukončením věty), který se během redukční analýzy ani nevypouští, ani nepřesunuje. Je to [.,AuxK].

R-seznamy a A-stromy.

V následující části budeme reprezentovat věty pomocí tzv. R-seznamů a jejich syntaktické struktury pomocí Astromů. R-seznamy a A-stromy jsou datové typy, vhodné pro používání operací delete a shift. Na R-seznamech a A-stromech zavádíme uniformním způsobem redukce, založené právě na operacích delete a shift. Redukční seznamy (R-seznamy) zjemňují pojem řetězu a A-stromy nesou více informace než R-seznamy. A-strom a R-seznam se skládají z uzlů, které v PDT reprezenují výskyty lexikálních jednotek (slov, interpunkčních znamének a jejich značek) v príslušné větě.

V A-stromu jsou pomocí stromové struktury reprezentovány syntaktické vztahy, pomocí R-seznamu, jež je součástí každého A-stromu, je reprezentováno pořadí slov. R-seznam. Necht' I je konečná množina přirozených čísel, Γ konečná abeceda a V ⊆ (I × Γ), kde V reprezentuje totální zobrazení množiny I do Γ. Necht' ord je úplné uspořádání množiny V . Říkáme, že ord je redukčním seznamem (R-seznamem) na Γ. Zapisujeme ho jako seznam prvků z V . Prvky R-seznamu označujeme jako uzly. Množinu R-seznamů, která vznikla všemi možnými uspořádáními množiny V , označujeme jako ord(V ).

Necht' u ∈ V , pak u = [i, a], kde i ∈ I, a ∈ Γ. Říkáme, že i je indexem uzlu u. Slouží k jednoznačné identifikaci uzlu. Říkáme, že a je symbolem uzlu u. A-strom. A-strom nad Γ je trojice s = (V, E, ord), kde (V, E) je orientovaný strom, jehož (maximální) cesty za- čínají v listech a končí v kořeni, V je konečná množina jeho uzlů, E ⊂ V ×V konečná množina jeho hran a ord ∈ ord(V ). Říkáme, že ord je R-seznamem A-stromu s. Pí- šeme R(s) = ord. Projekce. Je-li ord = ([i 1 , a 1 ], • • • , [i n , a n ]), tak w = a 1 • • • a n je řetěz (resp. věta), který označujeme Str(s) = w nebo Str(ord) = w, a říkáme, že w je řetězem (projekcí) A-stromu s nebo řetězem (projekcí) R-seznamu ord. Normalizace. Říkáme, že A-strom s = (V, E, ord) (R- seznam ord) je normalizovaný, pokud ord má tvar ord = ([1, a 1 ], [2, a 2 ], • • • , [n, a n ]). Normalizace A-stromu s = (V, E, ord) je takový normalizovaný A-strom s 1 = (V 1 , E 1 , ord 1 ), pro který (V, E) a (V 1 , E 1 ) jsou izomorfní a Str(s) = Str(s 1 )

. Všimněme si, že normalizace A-stromu je jednoznačně daná. Ekvivalence. Dva A-stromy (R-seznamy) jsou ekvivalentní, pokud mají stejnou normalizaci. Ekvivalentní Astromy často nebudeme rozlišovat.

Operace shift a delete zavedeme tak, že převedou A-strom na A-strom.

Delete. Operace dl(i) vyřadí z množiny V a z R-seznamu ord uzel tvaru [i, a i ] a získá tím množinu V 1 a R-seznam ord 1 . Z A-stromu s = (V, E, ord) operace dl(i) udělá A- strom s 1 = (V 1 , E 1 , ord 1 ) tím, že vyřadí uzel tvaru [i, a i ] jak z množiny V , tak z R-seznamu ord. Dále vyřadí z E všechny dvojice hran tvaru ([ j, a j ], [i, a i ]) a ([i, a i ], [k, a k ]) (pokud existují). Každou takovou dvojici hran nahradí v E 1 jedinou hranou tvaru ([ j, a j ], [k, a k ]). Viz příklad 3. Shift. Operace sh(i, j) přesune v R-seznamu ord uzel s indexem i před uzel s indexem j. Vytvoří tak nový R- seznam ord 2 . Provedeme-li operaci sh(i, j) na A-strom s = (V, E, ord), získáme tím A-strom s 2 = (V, E, ord 2 ).

Operace shift mění v A-stromě pouze R-seznam, tedy slovosled. Viz příklad 4. Poznámka. Připomeňme si, že operace mají být voleny tak, že posledním uzlem trvale zůstává sentinel.

URAS (Úplná redukční analýza A-stromu).

Zavádíme URAS s možností regulace pomocí množiny (významově) zakázaných redukcí. Příkladem zakázané redukce A-stromů z PDT, je vynechání předložky z předložkové vazby, či vynechání samotné zvratné částice.

Značení. Necht' Γ je konečná abeceda. T (Γ) značí mno- žinu všech A-stromů na Γ. Necht' T ⊆ T (Γ). Říkáme, že T tvoří T-jazyk na Γ. Množinu R-seznamů R(T) = {R(t) | t ∈ T} nazýváme R-jazykem T-jazyka T. Analogicky, jazyk Str(T) = {Str(t) | t ∈ T} nazýváme Str-jazykem T. Necht' Z ⊂ {(s,t)|s,t ∈ T} je daná množina zakázaných redukcí na T. Označíme Str(Z) = {(Str(s), Str(t))|(s,t) ∈ Z} a R(Z) = {(R(s), R(t))|(s,⊢ Z T označujeme ⊢ Z T * . Částečné uspořádání ⊢ Z T přirozeně definuje • T 0 ⊢ Z T = {v ∈ T | ¬∃u ∈ T : v ⊢ Z T u} -množina neredu- kovatelných A-stromů T-jazyka T. • T n+1 ⊢ Z T = {v ∈ T | ∃u ∈ T n ⊢ Z T : u ⊢ Z T v} ∪ T n ⊢ Z T , n ∈ N - množina A-stromů z T, které je možné zredukovat na neredukovatelný A-strom z Tposloupností URAS- redukcí délky nanejvýš n + 1. URAS. Pro A-strom s ∈ T a zakázanou množinu Z na- zveme URAS(s, T, Z) ={u ⊢ Z T v |s ⊢ Z T * u} (úplnou) re- dukční analýzou s podle T a Z. Větev. Necht' B = (s 1 , s 2 , • • • , s n ) je posloupnost A-stromů taková, že s 1 ⊢ Z T s 2 , s 2 ⊢ Z T s 3 , • • •, s n−1 ⊢ Z T s n a s n ∈ T 0 ⊢ Z T . Říkáme, že B je větví URAS(s, T, Z) a n je její délka. DL-sekvence a DL-charakteristika. Necht' Dl i je Dl- množinou redukce s i ⊢ T s i+1 pro 1 ≤ i < n a Dl n je mno- žinou uzlů A-stromu s n . Píšeme Dl(B) = (Dl 1 , DL 2 , • • • , Dl n−1 ) a říkáme, že Dl(B) je DL-sekvencí větve B. Množina Ch(B) = ({Dl 1 , DL 2 , • • • , Dl n−1 }) je DL- charakteristikou větve B.

DL-charakteristika a DL-sekvence se liší tím, že u DLcharakteristiky nezáleží na pořadí redukčních množin, ale u DL-sekvence ano. Vidíme, že pro 1 ≤ i < j < n jsou Dl i a Dl j disjunktní.

Algebraické vlastnosti závislostí a koordinací u

analytických strom ů PDT.

Touto podsekcí začíná výsledková část příspěvku. Předkládáme výsledky dvou typů. Nejčastěji prezentujeme lingvistická pozorování, formulovaná pomocí zavedeného aparátu. Získali jsme je (neúplným) procházením materiálu z PDT. K pozorováním jsme nenašli žádné výjimky a nevěříme, že se nějaké najdou. Pozorování by měla být podnětem ke (korpusově lingvistické) diskusi. Druhým typem výsledků jsou tvrzení a důsledky matematického charakteru. Vycházejí z rozboru prezentovaných (lingvistických) příkladů a z vlastností zavedeného aparátu.

T P v následujícím textu označuje množinu korektních A-stromů s koordinacemi a závislostmi, zpracovaných metodikou analytické roviny PDT. Rozhodnout o tom, zda daný A-strom patří do T P , by měli umět lidé (lingvisté, anotátoři), ovládající češtinu a metodiku PDT.

ZP označuje množinu zakázaných redukcí pro analytickou rovinu PDT.

Příklad 3.

Tento příklad navazuje na příklady 1 a 2. Obsahuje formalizaci A-stromů T1 2 a T1 3 a tím i popis redukce T1 2 ⊢ ZP T P T1 3 : Pozorování 2. Necht' s je A-strom z T P , který neobsahuje koordinace (tj. značky ´Cr´a ´Co´). Všechny větve URAS(s, T P , ZP) mají nejen stejnou délku, ale i stejnou DL-charakteristiku. Navíc URAS(s, T P , ZP) obsahuje jediný neredukovatelný A-strom. Tedy URAS(s, T P , ZP) lze považovat za (algebraickou strukturu zvanou) svaz.

T1 2 = (V 2 , E 2 , ord 2 ), pričemž V 2 = {[1, b 1 ], [2, b 2 ], [3, b 3 ], [4, b 4 ], [5, b 5 ]} E 2 = {([2, b 2 ], [1, b 1 ]), ([3, b 3 ], [4, b 4 ]), ([4, b 4 ], [1, b 1 ]), ([5, b 5 ], [1, b 1 ])}, ord 2 = ([1, b 1 ], [2, b 2 ], [3, b 3 ], [4, b 4 ], [5, b 5 ]) T1 3 = (V 3 , E 3 , ord 3 ), pričemž V 3 = {[1, b 1 ], [2, b 2 ], [3, b 3 ], [5, b 5 ]} E 3 = {([2, b 2 ], [1, b 1 ]), ([3, b 3 ], [1, b 1 ]), ([5, b 5 ], [1, b 1 ])} ord 3 = ([1, b 1 ], [2, b 2 ], [3

Pozorování 3. Necht' s je A-strom z T P , který neobsahuje koordinace a r 1 , r 2 jsou dvě různé redukce z URAS(s, T P , ZP). Platí, že r 1 a r 2 mají disjunktní DLmnožiny.

Pozorování 4. Necht' s je A-strom z T P , který obsahuje koordinaci alespoň tří členů. Existují dvě větve URAS(s, T P , ZP) s různou DL-charakteristikou.

Pozorování 5. Necht' s je A-strom z T P , který obsahuje koordinaci alespoň tří členů. Existují dvě redukce z URAS(s, T P , ZP), které nemají disjunktní DL-množiny. Průnik těchto DL-množin obsahuje uzel se spojkou nebo čárkou se značkou ¨AuxX¨.

Předchozí dvě pozorování jsou ilustrovány příkladem 4. Tvrzení 1. Existuje t ∈ T P , jehož URAS obsahuje více než jeden neredukovalelný A-strom.

Předchozí tvrzení lze dokázat pomocí A-stromu k větě 'Přišel, viděl, zvítězil.'.

UPRA (úplná větná redukční analýza.)

Abychom mohli dát do souvislosti URAS se starším pojmem, větnou redukční analýzou, zavádíme úplnou větnou redukční analýzu (UPRA), viz [3]. Do UPRA vstupuje věta ve formě R-seznamu. UPRA zavádíme zcela analogicky jako URAS. Redukce. Mějme jazyk L a R-seznam u takový, že

Str(u) ∈ L. Říkáme, že u je R-seznamem k jazyku L a pí- šeme u ∈ R(L). Necht' U ⊂ {(u, v)|u, v ∈ R(L)} je daná množina zakázaných redukcí. Zavedeme k R(L) a dané U redukce ≻ U L . Necht' u, v ∈ R(L). Říkáme, že u je redukovatelné na v podle L a U a označujeme u ≻ U L v, pokud: • |Str(u)| > |Str(v)| a (u,v) není z U;

• R-seznam v je získán z u provedením množiny operací vypuštění (deletů) Dl a následně postupným provedením shiftů z uspořádané množiny Sh. Dl je povinně neprázdná, Sh může být prázdná.

• Libovolný uzel je přesouván pomocí Sh maximálně jednou.

• Operační nezmenšitelnost redukce. Pokud bychom vynechali při aplikaci na u jednu nebo více operací z Dl nebo z Sh, získali bychom R-seznam z takový, že Zbývající potřebné pojmy pro UPRA lze zavést zcela analogicky jako pro URAS.

Str(z) / ∈ L, nebo (u, z) ∈ U. • Jako Dl(u, v) označujeme množinu uzlů R-seznamu u,

Nesouvislosti a stabilita redukcí.

Zavádíme dvě míry nesouvislosti redukcí, které se vzájemně doplňují. S ohledem na tyto a další míry zavádíme několik typů stability pro URAS, které nám dovolí klasifikovat omezená URAS jako stabilní, nebo nestabilní. Stabilita URAS pro jednotlivé A-stromy je formálním kriteriem pro lingvistickou adekvátnost redukční analýzy, s ohledem na daná omezení. Budeme hledat maximální omezení taková, která zachovávají alespoň nejslabší typ stability. Následuje několik formálních definic. URAS s omezením na velikost mezer. Necht' i je přirozené číslo. Označíme jako URAS(s, T, Z : ns ≤ i) podmnožinu URAS(s, T, Z), která obsahuje všechny redukce z URAS(s, T, Z), které nemají velikost mezer větší než i. Omezení můžeme i skládat. Např. URAS(s, T, Z; pk ≤ i, ns ≤ j) = URAS(s, T, Z; pk ≤ i) ∩ URAS(s, T, Z; ns ≤ j). Množiny strom ů stabililní s ohledem na omezení. Budeme používat následující typy značení pro množiny Astromů splňující daná omezení.

Graf

Např. TRAS(T, Z; pk ≤ 1, ns ≤ 0; T-st ) = {t ∈ T | URAS(t, T, Z; pk ≤ 1, ns ≤ 0) je T-stabilní }. Analogicky TRAS(T, Z; pk ≤ 1; CH-st ) = {t ∈ T | URAS(t, T, Z; pk ≤ 1) je CH-stabilní }.

Podobně budeme popisovat množiny A-stromů z T parametrizované dalšími omezeními a různými typy stability ze škály T-stabilní, CH-stabilní, Mn-stabilní.

Rozlišení závislostí a koordinací pomocí

(ne)souvislosti.

Předchozí pojmy a následující příklady využijeme k formulaci nových pozorování o PDT.

Příklad 4.

Tento příklad ilustruje redukce vícenásobných koordinací a použití grafově nesouvislé redukce v URAS. Obrázek 12: T 5 3 , vzniklé redukcí z T5 1 .

= (dl(i 1 ), dl(i 2 ), • • • , dl(i n )) a IN(dl(i 1 )) ≤ IN(dl(i 2 )), • • • , IN(dl(i n−1 )) ≤ IN(dl(i n )).

• TRAS(T P , ZP; MinIN ≤ 1, MaxIn ≤ 1; Mn-st ) ⊆ T P .

Poznámka. Pro každé t ∈ T P , které jsme pozorovali, bylo URAS(t, T P , ZP; MinIN ≤ 1) Mn-stabilní. Neumíme odhadnout, zda existuje A-strom t ∈ T P takový, že URAS(t, T P , ZP; MinIN ≤ 1) není Mn-stabilní, tedy zda TRAS(T P , ZP, MinIN ≤ 1, MaxInPc ≤ 1; Mn-st ) = T P . Podle našich pozorování a naší notace platí, že L P = Str(T P ), R(L P ) = R(T P ) a UP = R(ZP).

Pozorování 14. Necht' s ⊢ ZP T P t, pak R(s) ≻ UP L P R(t). Necht' s,t ∈ T P a R(s) ≻ UP L P R(t), pak s ⊢ ZP T P t. Předchozí pozorování formuluje vlastnost konzistence mezi UPRA a PRAS. Říká, že A-stromy z PDT jsou konstruovány v souladu s větnou redukční analýzou. Toto pozorování je naším základním pozorováním analytické roviny PDT. Přirozeně všechny zde prezentované příklady na URAS a UPRA splňují podmínky konzistence mezi URAS a UPRA.

Další omezení a výhledy do budoucna.

Následující omezení mají, na rozdíl od předchozích podobnou platnost pro URAS i pro UPRA. URAS s omezením na počet delet ů. Necht' i je přirozené číslo. Označíme jako URAS(s, T, Z : dl ≤ i) podmnožinu URAS(s, T, Z), která obsahuje všechny redukce z URAS(s, T, Z), které nemají počet deletů větší než i. URAS s omezením na vzdálenost vypouštěných uzl ů. Necht' k je přirozené číslo. Označíme jako URAS(s, T, Z : ds ≤ k) podmnožinu URAS(s, T, Z), která obsahuje všechny redukce z URAS(s, T, Z), které nemají vzdálenost mezi vypouštěnými uzly (podle uspořádání v R-seznamu) větší než k. Podobné tvrzení platí pro bezkontextové jazyky, které nejsou regulární.

Poznamenejme, že v následujícím zřejmém tvrzení mají označení UPRA(u, L, / 0; ds ≤ k) a Mn-stabilita analogický význam jako pro URAS.

Tvrzení 7. Ke každému bezkontextovému jazyku L existuje k ∈ N takové, že pro libovolné u ∈ R(L) platí, že UPRA(u, L, / 0; ds ≤ k) je Mn-stabilní.

Předchozí příklad a tvrzení uvádíme, abychom poukázali na souvislosti našich lingvistických pozorování T P a formální teorií (nekonečných) jazyků. Vidíme, že z pohledu formální redukční analýzy, nejsou A-stromy z T P příliš složité. Přesto jsme (na základě lingvistického folklóru) očekávali jednodušší a uniformější výsledky.

V budoucnu plánujeme zavést míry neprojektivity a řetězové nesouvislosti založené na redukční analýze a konfrontovat tyto míry s PDT. Očekáváme, že se ukáže souvislost těchto měr s časovou složitostí redukční analýzy.