=Paper=
{{Paper
|id=None
|storemode=property
|title=Redukční Analýza a Pražský Závislostní Korpus
|pdfUrl=https://ceur-ws.org/Vol-1422/43.pdf
|volume=Vol-1422
|dblpUrl=https://dblp.org/rec/conf/itat/PlatekPO15
}}
==Redukční Analýza a Pražský Závislostní Korpus==
https://ceur-ws.org/Vol-1422/43.pdf
J. Yaghob (Ed.): ITAT 2015 pp. 43–50
Charles University in Prague, Prague, 2015
Redukční analýza a Pražský závislostní korpus∗
Martin Plátek1 , Dana Pardubská2 , and Karel Oliva3
1 MFF UK Praha, Malostranské nám. 25, 118 00 Praha, Česká Republika
martin.platek@ufal.mff.cuni.cz
2 FMFI UK Bratislava, Mlynská dolina, 84248 Bratislava
pardubska@dcs.fmph.uniba.sk
3 UJČ ČAV Praha, Letenská, 118 00 Praha, Česká Republika
oliva@ujc.cas.cz
Abstrakt: Cílem tohoto příspěvku je uvést, formálně za- slova analyzované věty. V některých redukcích může být
vést a exaktně pozororovat větnou redukční analýzu sváza- kromě vypouštění použita operace shift, která přesune ně-
nou s redukční analýzu D-stromů. Tímto způsobem upřes- jaké slovo na novou pozici ve větě.
níme strukturální vlastnosti D-stromů se závislostmi a
Metoda (manuální) redukční analýzy, studovaná
koordinacemi z Pražského závislostního korpusu (PDT).
v tomto příspěvku, dodržuje následující zásady:
Zvýrazňujeme vlastnosti, kterými se závislosti a koordi-
nace liší. Snažíme se pracovat metodou, která je blízká me- (i) tvary jednotlivých slov (i interpunkčních znamének),
todám matematické lingvistiky, a to především těm, které jejich morfologické charakteristiky i jejich syntak-
formulují omezující podmínky pro syntaxi přirozených ja- tické kategorie se nemění během RA;
zyků. Ukazujeme nové možnosti takových formulací.
(ii) gramaticky správná věta (přesněji její čtení) musí zů-
stat správná i po redukci;
1 Úvod (iii) vynecháme-li z libovolné redukce jednu či více ope-
rací vypuštění nebo shift, nastane porušení principu
Postupně se věnujeme větné redukční analýze (RA) a její
zachování správnosti (ii);
vazbě na redukční analýzu D-stromů (RADS), abychom
získali nové formální prostředky vhodné pro studium (iv) předložkové vazby (např. ’o otce’), se vynechávají
strukturálních vlastností D-stromů. Na základě těchto pro- celé (jinak je možný posun významu, často i změny
středků formulujeme pozorování o D-stromech v Praž- v pádech);
ském závislostním korpusu (PDT viz [1]). Tento článek
vznikl ve spolupráci s Markétou Lopatkovou, která nám (v) věta, která obsahuje správnou větu (nebo její permu-
pomocí vybíraných příkladů zprostředkovala přístup do taci) jako svoji (případně nesouvislou) podposloup-
PDT a často s námi diskutovala, zvláště o problematice nost, musí být dále redukována;
redukcí stromů z PDT s koordinacemi.
(vi) redukce používají operaci shift jenom v případech
vynucených principem zachování korektnosti, tedy
1.1 Neformální úvod do (manuální) redukční v případech, kdy vynechání shiftu by vedlo k neko-
analýzy českých vět a redukční analýzy jejich rektnímu větnému slovosledu;
D-stromů
(vii) syntaktická struktura věty po redukci zachovává
V této sekci se pokusíme čtenáře neformálně uvést do strukturu věty před redukcí.
problematiky manuální redukční analýzy vět a poukázat
na souvislosti s redukční analýzou D-stromů, které těmto Novým prvkem mezi zásadami pro větnou redukční
větám odpovídají. Redukční analýzou českých vět a jejímu analýzu oproti [5] je položka (vii). Syntaktická struktura
modelování se zabýváme již delší dobu (viz např. [3, 5]), zde znamená větný rozbor odpovídající stromům z Praž-
naopak explicitní zmínky o redukční analýze D-stromů se ského závislostního korpusu (D-strom). Tato zásada fak-
objevují ponejprv na loňském ITATU (viz [4, 2]). Při for- ticky formuluje základní vztah mezi větnou redukční ana-
malizaci obou typů redukčních analýz zvýrazňujeme je- lýzou a redukční analýzou D-stromů. Výše uvedené zá-
jich minimalistický charakter a využíváme ho při struktu- sady postupně upřesníme ve formální části příspěvku.
rální charakterizaci D-stromů. V následujících odstavcích uvedeme serii příkladů ilu-
RA je založena na postupném zjednodušování analy- strujících prvky redukční analýzy, které se týkají redukcí
zované věty po malých krocích, viz [3, 5]. RA definuje zjednodušující jak závislosti, tak především koordinace.
možné posloupnosti větných redukcí – každá redukce RA Všimněme si, že redukce koordinací budou ve dvou aspek-
spočívá ve vypuštění několika slov, nejméně však jednoho tech složitější než redukce závislostí. Pozorování koordi-
∗ Příspěvek prezentuje výsledky dosažené v rámci projektu agentury načních jevů a formalizace těchto pozorování je hlavní no-
GAČR číslo GA15-04960S. vinkou a přínosem tohoto příspěvku.
44 M. Plátek, D. Pardubská, K. Oliva
D-stromy na našich obrázcích se liší od D-stromů z PDT bojí.Pred
jen ve dvou aspektech. Za prvé: neobsahují identifikační se.AuxT
..AuxK
uzel, který nenese žádnou syntaktickou informaci a neod-
povídá žádnému slovu věty. Za druhé: značka ’Coord’ je Obrázek 4: T3 vzniklé redukcí se shiftem z T2 nebo redukcí
nahrazena značkou ’Cr’. bez shiftu z T4 .
Příklad 1. bojí.Pred
(1) Petr.Sb se.AuxT bojí.Pred o.AuxP otce.Obj ..AuxK ..AuxK
o.AuxP
se.AuxT
Petr.Sb se.AuxT bojí.Pred o.AuxP otce.Obj ..AuxK
delete delete
otce.Obj
Petr.Sb se.AuxT bojí.Pred ..AuxK * Se.AuxT bojí.Pred o.AuxP otce.Obj ..AuxK
delete shift
Obrázek 5: T4 , vzniklé redukcí z T1 .
* Se.AuxT bojí.Pred ..AuxK Bojí.Pred se.AuxT o.AuxP otce.Obj ..AuxK
shift delete
Bojí.Pred se.AuxT ..AuxK
až 11. Všechny tři redukce D-stromu T c1 odstraňují (při
zjednodušování trojnásobné koordinace na dvojnásobnou)
Obrázek 1: Schema RA pro větu (1). dva nesouvisející uzly (podstromy). Třetí redukce navíc
Z obrázku 1 vidíme, že věta (1) může být v prvním kroku používá shift. Tyto redukce se liší od předchozího příkladu,
redukována dvěma způsoby: kde všechny redukce odtrhly jediný úplný souvislý pod-
(i) bud’ vypuštěním předložkové vazby ’o otce’; této větné strom. Zbylé redukce dvojnásobných koordinací se reali-
redukci odpovídá redukce D-stromu T1 z obrázku 2 na zují odtržením souvislého úplného podstromu, určeného
D-strom T2 z obrázku 3, jejich vrcholem, podobně jako u redukcí v předchozím pří-
(ii) nebo vypuštěním podmětu (subjektu) ’Petr’, to však kladě, týkající se závislostí.
vede k větě se špatným slovosledem. Gramatické české
věty nemohou začínat klitikou. To vede k použití přesunu
Je.Pred dědou.Obj.Co ,.AuxX otcem.Obj.Co a. Cr strýcem.Obj.Co ..AuxK
klitiky ’se’ na druhou pozici ve větě. Získáme tak korektní
větu ’Bojí se o otce.’ Této větné redukci odpovídá redukce
D-stromu T1 na D-strom T4 z obrázku 5. Je.Pred otcem.Obj.Co a.Co strýcem.Obj.Co ..AuxK
Potom pokračují redukce podobným způsobem v obou Je.Pred dědou.Obj.Co a.Cr strýcem.Obj.Co ..AuxK
větvích, až dospějeme k neredukovatelné správné větě shift
’Bojí se.’ . Této fázi odpovídají redukce D-stromů T2 a T4 Je.Pred dědou.Obj.Co a.Cr otcem.Obj.Co ..AuxK
na D-strom T3 z obrázku 4.
Předchozí příklad ilustruje přirozenou souvislost mezi Je.Pred ..AuxK
větnou redukční analýzou věty (1) a redukční analýzou
D-stromu se závislostní strukturou téže věty z obrázku 2.
Obrázek 6: RA věty (2) s vícenásobnou koordinací.
bojí.Pred
o.AuxP ..AuxK
Petr.Sb se.AuxT Příklad 3. Na obrázku 12 vidíme schema redukční ana-
otce.Obj
lýzy věty (3). Toto schema znázorňuje jedinou redukci,
která odstraňuje koordinovaná příslovečná určení, která
Obrázek 2: Závislostní strom T1 .
jsou závislá na koordinovaných predikátech. Odpovídající
redukci D-stromu ilustrují obrázky 13 a 14.
bojí.Pred
Petr.Sb se.AuxT
Příklad 4. Na obrázku 15 vidíme schema redukční
..AuxK
analýzy věty (4). Věta (4) je věta s vloženou koordi-
Obrázek 3: T2 , vzniklé redukcí z T1 .
nací. D-stromy zachycující odpovídající redukční analýzu
D-stromů jsou na obrázcích 16 až 18. Vložená koordinace
Příklad 2. Na obrázku 6 vidíme schema redukční ana- se v D-stromě T cz3 zjednodušuje tak, že se vyjme jedna
lýzy věty (2). Věta (2) obsahuje trojnásobnou koordinaci hrana s řídícím uzlem se značkou ’Cr.Co’ (ve složitějších
předmětů. Povšimněme si, že dalšímu zjemnění schematu případech i to co na ní visí). To odpovídá dvěma redukcím
zabraňují kategorie (značky), použité podle vzoru PDT. ve větné redukční analýze z obrázku 15. Tento typ redukce
Značka ’Cr’ znamená koordinující symbol (slovo), ’Co’ je nový oproti předchozím případům a je vynucen principy
značí koordinované slovo, či symbol. Schematu na obrázku zachování korektnosti a minimality ve větné redukční ana-
odovídají redukce D-stromů, které reprezentují obrázky 7 lýze.
Redukční analýza a Pražský závislostní korpus 45
Je.Pred a.Cr
jednáme.Pred.Co
pracujeme.Pred.Co
a.Cr ..AuxK
dědou.Obj.Co
strýcem.Obj.Co
Obrázek 14: T cz22 , vzniklé redukcí z T cz2 .
,.AuxX otcem.Obj.Co
Pracujeme. Pred.Co a.Cr.Co myslíme. Pred.Co i .Cr jednáme. Pred.Co ..AuxK
Obrázek 7: D-strom T c1 .
Je.Pred
Pracujeme. Pred.Co i. Cr jednáme. Pred.Co ..AuxK
a.Coord ..AuxK myslíme. Pred.Co i .Cr jednáme. Pred.Co ..AuxK
strýcem.Obj.Coord Obrázek 15: AR věty s vloženou koordinací.
otcem.Obj.Coord
2 Formalizace
Obrázek 8: T ca2 , vzniklé redukcí z T c1 .
Formalizace RA přirozených jazyků začíná formalizová-
Je.Pred ním lexikální analýzy těchto jazyků. Lexikální analýza
kromě jiného umožňuje rozlišovat možnosti uplatnení jed-
a.Cr ..AuxK
notlivých typů redukcí.
strýcem.Obj.Co
dědou.Obj.Co
2.1 Lexikální analýza
Při formalizaci lexikální analýzy pracujeme se třemi abe-
Obrázek 9: T cb2 , vzniklé redukcí z T c1 .
cedami (slovníky)- konečnými množinami slov. Σ p , tzv.
Je.Pred slovník 1 , se využívá na modelování jednotlivých slov-
ních forem. Σc označuje abecedu kategorií, například syn-
a.Cr ..AuxK taktických značek v PDT. Kombinací dostávame hlavní
otcem.Obj.Co
slovník Γ ⊆ Σ p × Σc , který umožňuje odstraňovat lexiko-
dědou.Obj.Co morfologické nejednoznačnosti jednotlivých slovních fo-
rem. Lexiko-morfologicky zjednoznačněná věta tedy vstu-
Obrázek 10: T cc2 , vzniklé redukcí z puje do RA jako retězec nad slovníkem Γ.
T c1 . Projekce z Γ∗ do Σ∗p resp. do Σ∗c přirozeně definujeme
pomocí homomorfismů: slovníkovým homomorfismem h p :
Je.Pred Γ → Σ p a kategoriálním homomorfismem hc : Γ → Σc :
h p ([a, b]) = a a hc ([a, b]) = b pro všechny [a, b] ∈ Γ.
..AuxK
Příklad 5. Definované pojmy ilustrujeme na příklade,
který vychází z příkladu 1
Obrázek 11: T c3 , vzniklé redukcí z T ca2 , T cb2 Slovník: Σ1p = { Petr, se, bojí , o, otce, . }
a T cc2 .
Abeceda kategorií: Σ1c = { Sb, AuxT, Pred, AuxP, Obj,
AuxK}
Skromně.Adv.Co a.Cr denně.Adv.Cr pracujeme. Pred.Co a.Cr jednáme. Pred.Co ..AuxK
Hlavní slovník: Γ1 = {b1 = [Petr,Sb], b2 =[se,AuxT], b3 =
[bojí,Pred], b4 =[o,AuxP], b5 = [otce,Obj], b6 =[.,AuxK]}
pracujeme. Pred.Co a.Cr jednáme. Pred.Co ..AuxK
i.Cr
a.Cr.Co
Obrázek 12: RA závislé koordinace na řídící koordinaci. jednáme.Pred.Co
a.Cr pracujeme.Pred.Co
myslíme.Pred.Co
a.Cr jednáme.Pred.Co
pracujeme.Pred.Co Obrázek 16: T cz3
skromně.Adv.Co denně. Adv.Co
1 Index p při označení abecedy se vztahuje na anglickou verzi, kde
Obrázek 13: T cz2
se používá slovo proper
46 M. Plátek, D. Pardubská, K. Oliva
i.Cr
k-omezené pokud délka slov z L 0 je nejvýše k a |u| − |v| ≤
jednáme.Pred.Co k pro všechny u L v ∈ L .
pracujeme.Pred.Co
Bylo by zvláštní, kdyby v DS-redukci přirozeného ja-
Obrázek 17: T cz31 , vzniklé redukcí z T cz3 . zyka byly ireducibilní věty dlouhé, pričemž všechny re-
dukce z L by zkracovaly věty jen málo. Zajímáme se
proto hlavně o takové DS-analýzy, v kterých ∀w ∈ L 0
i.Cr
existují u, v, u L v takové, že |u| − |v| ≥ |w|. Takovým
jednáme.Pred.Co DS-analýzám říkáme proporcionální.
myslíme.Pred.Co
Všimněme si, že redukční analýza české věty z pří-
Obrázek 18: T cz32 , vzniklé redukcí z T cz3 . kladu 1 vyhovuje podmínkám kladeným na proporcio-
nální 2-omezenou DS-analýzu, zatímco redukční analýza
české věty z příkladu 2 je proporcionální 3-omezenou DS-
V abecedě kategorií v tomto příkladě jsou jen závis- analýzou.
lostní kategorie (ne všechny). Koordinační kategorie vzni- DS-analýzu budeme považovat’ za relevantní model
kají kombinacemi se značkami ’Cr’, ’Co’. skladby přirozených i umělých jazyků, pokud to bude DS-
analýza konečných, anebo nekonečných semi-lineárnych
2.2 Formální RA jazyků, které jsou proporcionální a k-ohraničené pro
nejaké neveliké k.
V této sekci zavádíme postupně formální redukční analýzu
vět (řetězů) RA a formální redukční analýzu pro D-stromy.
Nejprve zavedeme na jazyce L tzv. DS-redukci L . 2.3 D-struktury a D-stromy
Necht’ u, v jsou řetězce. Říkáme, že u je větší než v vzhle-
V následující části zavedeme tzv. D-struktury a D-stromy,
dem k jazyku L a označujeme u >L v pokud:
ktoré jsou grafovou reprezentací struktury vět a jejich
• u, v ∈ L a |u| > |v|; odvození.2 D-struktura reprezenuje syntaktické jednotky
• v je permutace nějaké podposloupnosti u. (slova a jejich kategorie použité v príslušné větě) jako
vrcholy grafu a vzájemné syntaktické vztahy mezi nimi
Říkáme, že v je DS-redukce u vzhledem k jazyku L
hranami; pořadí slov je určené totálním uspořádáním
a označujeme u L v pokud:
vrcholů.
• u >L v a neexistuje žádné z ∈ L takové, že u >L z >L v, D-struktura na Γ je trojice D = (V, E, ord(V )), kde
t.j., platí princip minimality redukcí. (V, E) je orientovaný acyklický graf, V konečná množina
jeho vrcholů a E ⊂ V × V konečná množina jeho hran.
Reflexívní a tranzitívní uzávěr relace L označujeme Vrchol u ∈ V je dvojice u = [i, a], kde a ∈ Γ je symbol
∗L . Částečné uspořádání L přirozeně definuje (slovo) spolu s přirazenými kategoriemi, i (index/ identi-
• L 0 = {v ∈ L | ¬∃u ∈ L : v u} - množinu ireduci-
L fikační číslo) je přirozené číslo sloužící pro jednoznačnou
bilních vět jazyka L identifikaci vrcholu u a ord(V ) je totální uspořádání na V,
• L n+1
= {v ∈ L | ∃u ∈ L n : u v}∪Ln , n ∈ N - mno-
L
obvykle popsané uspořádaným seznamem prvků z V .
L
žina těch vět z jazyka, které je možné zredukovat na Hrany D-struktury interpretujeme jako syntaktické
ireducibilní větu z jazyka posloupností DS-redukcí vztahy mezi odpovídajícími lexikálními jednotkami, uspo-
délky nanejvýš n + 1. řádání ord(V ) reprezentuje pořadí slov v modelované větě.
Je-li ord(V ) = {[i1 , a1 ], · · · , [in , an ]}, tak w = a1 · · · an je ře-
Množinu L ={u L v | u, v ∈ L} nazveme množinou tězec (resp. věta), který označujeme St(D) = w, a říkáme,
DS-redukcí jazyka L. Analogicky pro větu w jazyka L na- že je projekcí D-struktury D.
zveme L (w) ={u L v |w ∗L u} DS-redukční množinou Říkáme, že D-struktura D = (V, E, ord(V )) je nor-
věty w. malizovaná, pokud ord(V ) = ([1, a1 ], [2, a2 ], · · · , [n, an ])
Fakt: L aj L (w) jsou jednoznačne určené L, resp. w pro nejaké a1 , · · · , an . Normalizace D-struktury D =
a L. (V, E, ord(V )) je taková normalizovaná D-struktura D1 =
Přistupme k formalizaci (minimalistické) redukční ana- (V1 , E1 , ord(V1 )), pro kterou (V, E) a (V1 , E1 ) jsou izo-
lýzy. Říkáme, že relace L ⊆ L je DS-(redukční) analýza morfní a St(D) = St(D1 ). Všimněme si, že normalizace
jazyka L pokud L = L 0 ∪ {v | ∃u, z : v u ∗ z ∈ L0 }.
L L D-struktury je jednoznačně daná.
Analogicky definujeme DS-analýzu L (w) pro w ∈ L; Dve D-struktury jsou ekvivalentní pokud mají stejnou
L (w) ={u L v |w ∗L u}. normalizaci. Ekvivalentní D-struktury obvykle nebudeme
Uvědomme si, že zatím co jazyk L je jednoznačne urče- rozlišovat. Uvidíme, že nenormalizované D-struktury
ný pomocí L a L 0 , věta w ∈ L může mít více DS-analýz.
(stromy) získáme z normalizovaných pomocí operací,
Různé DS-analýzy věty w v lingvistice odpovídají růz- které zavedeme.
nému čtení (porozumění) této věty.
Relace L určuje velikost zkrácení, které je možné do-
sáhnout jedním krokem redukce. Říkáme, že L a L jsou 2 prefix Dje převzatý z anglických pojmů Delete a Dependency.
Redukční analýza a Pražský závislostní korpus 47
Vzhledem k charakteru zkoumané problematiky bu- místo v ord(V ), který zachová stromovou strukturu D,
deme většinou pracovat se stromovými D-strukturami. Ří- tedy zachová všechny uzly z V a všechny hrany z E.
káme, že D-struktura D = (V, E, ord(V )) nad Γ je D-strom Druhou operaci nazveme UNC, z anglického upper-
nad Γ pokud (V, E) je kořenový strom (t.j., všechny ma- node-cut. Je typická pro redukce závislostí a při jejím za-
ximální cesty (V, E) začínají v listech a končí v jediném vádění si pomůžeme jednodušší operací LNC, z anglic-
kořeni). kého lower-node-cut. Operace UNC i LNC jsou určené
Budeme pracovat s redukcemi D-stromů - relace A a ` uzlem u D-stromu různým od kořene. Tento uzel jedno-
definované na D-stromech souvisí s realizací různých typů značně určuje rozklad D-stromu D na dva podstromy:
redukcí. Necht’ D = (V, E, ord(V )), D1 = (V1 , E1 , ord(V1 )) 1) TL (u, D) označuje výsledek LNC aplikovaného na D
jsou D-stromy. v uzlu u ; je to podstrom stromu D, který tvoří uzly le-
D A D1 pokud žící na nějaké cestě z listu do u (včetně u). Pořadí uzlů v
(1) (V1 , E1 ) je podstrom (V, E) TL (u, D) je určené pořadím v D.
(2) V1 obsahuje kořen D 2) TU (u, D) označuje výsledek UNC aplikovaného na D
v uzlu u; je to maximální podstrom D obsahující kořen D
(3) ord(V1 ) je permutace podposloupnosti ord(V ).
a všechny uzly mimo TL (u, D). Pořadí uzlů je určené pora-
D ` D1 , pokud podmínku (1) nahradíme dvěma podmín- dím v D. UNC tedy transformuje D na D-strom TU (u, D).
kami Poslední operací je UEC, z anglického upper-edge-cut.
(1a) V ⊂ V1 Použití této operace jsme videli při redukci (odstraňo-
(1b) ∀v1 , v2 ∈ V1 platí, že pokud existuje cesta z v1 do v2 vání) vložených koordinací z obr. 17 a 18. Necht’ (u, v)
ve stromě (V, E) tak existuje také cesta z v1 do v2 i ve a (v, v1 ) jsou takové hrany D-stromu D, že existuje právě
stromě (V1 , E1 ). jeden uzel u1 6= u a hrana (u1 , v) vedoucí do v. Operace
UEC aplikovaná na D podle hrany (u, v) vytvoří D-strom
Příklad 6. Následuje popis D-stromů T1 a T2 , které re- TE ((u, v), D). TE ((u, v), D) získáme následujícím způso-
prezentují obr. 2 a obr. 3: bem: nejprve aplikací UNC-operace vytvoříme TU (u, D)
T1 = (V1 , E1 , ord(V1 )), pričemž a následně z něj odstraníme uzel v spolu s hranami (u, v) a
(v, v1 ). Potom spojíme vrcholy u1 , v1 novou hranou (u1 , v1 )
V1 = {[1, b1 ], [2, b2 ], [3, b3 ], [4, b4 ], [5, b5 ], [6, b6 ]}
a získáme tak D-strom, který označujeme TE ((u, v), D).
E1 = {([1, b1 ], [3, b3 ]), ([2, b2 ], [3, b3 ]), ([4, b4 ], [3, b3 ]), Nyní zavádíme formální redukce a redukční analýzu na
([5, b5 ], [4, b4 ]), ([6, b6 ], [3, b3 ])}, D-stromech tak, abychom pokryli jak závislostní, tak ko-
ordinační jevy z PDT.
ord(V1 ) = ([1, b1 ], [2, b2 ], [3, b3 ], [4, b4 ], [5, b5 ], [6, b6 ]) Necht’ T ⊆ T (Γ), t1 ,t2 ∈ T. Symbolem `T budeme ozna-
čovat zúžení operace ` na T3
T2 = (V2 , E2 , ord(V2 )), pričemž
Říkáme, že t1 je NES-redukované na t2 ∈ T a označu-
V2 = {[1, b1 ], [2, b2 ], [3, b3 ], [6, b6 ]} jeme t1 ,→NES t2 , pokud redukci t1 `T t2 umíme popsat
pomocí množiny ON UNC-operací a/nebo množiny OE
E2 = {([1, b1 ], [3, b3 ]), ([2, b2 ], [3, b3 ]), ([6, b6 ], [3, b3 ])} UEC-operací, případně následovanými množinou shiftů
OS . Navíc, ON ∪ OE je neprázdná, každý uzel je operací
ord(V2 ) = ([1, b1 ], [2, b2 ], [3, b3 ], [6, b6 ])
z Os přesouvaný nejvýše jednou, Os může být prázdná.
Je snadno vidět, že T1 A T2 . Pokud v predchozí definici nepovolíme UEC-operace,
Takřka všechny neformální redukce z kapitoly jedna ve- budeme říkat, že t1 je NS-redukované na t2 ∈ T a označovat
dou k realizaci relace A. Neplatí to jen pro redukce na t1 ,→NS t2 .
obr. 17 a 18. Tyto redukce splňují obecnější relaci `. Pokud při redukci nepovolíme ani shifty, budeme hovo-
Tyto dvě relace reprezentují dvě varianty zachování zbylé řit o N-redukci a označovat t1 ,→N t2 .
D-struktury, vzniklé zmenšením při uplatnění redukcí re- Redukce typu NES, NE a N mohou být, v principu, apli-
dukční analýzy na D-stromech. kované na libovolné D-stromy. Nás však zajímají redukce
D-stromů daného T-jazyka, proto vyžadujeme, aby i po
Necht’ T je nejaká množina D-stromů na Γ. Říkáme, aplikování zmíněných redukcí byl vzniklý strom platným
že T tvoří T-jazyk na Γ a píšeme T ⊆ T (Γ). Analogicky, D-stromem zkoumaného jazyka. Při definování pojmu re-
množinu St(T) = {St(t) | t ∈ T} nazýváme projekcí T, dukce proto přidávame parametr T.
množina h p (St(T)) = {h p (St(t)) | t ∈ T} je vlastní jazyk Necht’ X ∈ {NES, NS, N}, T ⊆ T (Γ). Říkáme, že t1 je
pro T, a hc (St(T)) = {hc (St(t)) | t ∈ T} je kategoriální (X,T)-redukované na t2 a píšeme t1 (T,X) t2 pokud:
jazyk pro T.
• t1 ,t2 ∈ T
Zavedeme tři operace pro práci s D-stromy. Umožní
• t1 ,→X t2 a neexistuje z ∈ T tak, aby t1 ,→X z ,→X t2 ,
nám realizovat typ redukcí čistě závislostních i redukce
t.j., platí princíp minimality redukcí.
různých typů koordinací.
Najjednodušší operací je tzv. shift, což je takový posun
některého vrcholu D-stromu D = (V, E, ord(V )) na nové 3 Při ` tedy vyžadujeme, aby t i t byli z T.
T 1 2
48 M. Plátek, D. Pardubská, K. Oliva
Tranzitívní, reflexívní uzávěr (T,X) označujeme Tento fakt přímo vyplývá z definice UNC-operace.
∗(T,X) . Tranzitívní, anti-reflexívní uzávěr (T,X) označu- Předchozí fakt zpřesňuje intuitivně vnímané vlastnosti
jeme + . V situaci, kdy je Tzřejmé z kontextu, hovo- (ne)závislostí v (čistě) závislostních stromech.
(T,X)
říme jen o NES-, NE, resp. N-redukci. Následující dva principy jsou blízké algebraickému
Uvědomme si, že T a X jednoznačně určují množinu principu konfluence.
(T,X) = {u (T,X) v | u, v ∈ T }, ktorou považujeme Princip Tl-kompatibility. Požadujeme, aby všechny
za redukční analýzu T-jazyka T . Říkáme, že (T,X) je větve v NES-analýze A stromu t byly stejně dlouhé
X-redukcí T . Všimněme si rozdílu oproti DS-analýze re- a v každé větvi byl použit stejný počet UNC-operací
tězcových jazyků, která nebývá jednoznačně určená svým a UEC-operací.
jazykem. Následujicí princip je přísnější. Odlišuje čistě závis-
Necht’ X ∈ {NES, NS, N}. lostní D-stromy od D-stromů s koordinacemi.
(T, X)0 = {t ∈ T | ¬∃s ∈ L : t (T,X) s}, Princip Ta-kompatibility (Formulace závislostniho
(T, X)n+1 n
= {v ∈ T | ∃u ∈ (T, X) : v (T,X) u} ∪ T .
n
principu). Tento princip uvažuje pouze D-stromy t, které
Necht’ t ∈ T . Píšeme (T,X) (t) ={u (T,X) v |t ∗(T,X) nemají koordinační znaky, a jejichž NES-analýzy jsou
u}. Říkáme, že (T,X) (t) je X-analýza (redukční) i NS-analýzami a zároveň splňují princip Tl-compatibility.
D-stromu t. Dále zde požadujeme, aby množina UNC-operací užitých
V následující sekci budeme navíc ještě vázat použití v dané NS-analýze A byla určena libovolnou větví z A (t.j.
jednotlivých typů operací na (ne)přítomnost koordinač- v každé větvi byla ta množina stejná) a aby všechny větve
ních značek v určujících hranách a uzlech těchto operací. z A končily stejnou neredukovatelnou větou (algebraickou
O takových typech omezení uplatnění operací jsme zatím terminologií A tvoří svaz).
nemluvili. Další dva principy formulují volnější předpoklady, jak
by měla redukční analýza reprezentovat tvar analyzova-
ného D-stromu, ve kterém jsou i koordinační značky.
2.4 Principy, vlastnosti a pozorování
Princip Tb-kompatibility. Pokud máme NES-analýzu
Zde zavedeme principy, které nám umožní formulovat A D-stromu t a dva různé uzly u, v D-stromu t, které jde re-
požadavky na redukční analýzu na D-stromech a for- dukovat jako určující uzly dvou UNC-operací a přitom ne-
mulovat pozorování o jejich plnění na stromech z PDT. vede cesta mezi u a v, tak požadujeme, aby během A mohla
Při těchto pozorováních uplatníme možnost porovnávat být dříve provedena kterákoliv z těchto UNC-operací (tj.
NES-analýzy, NS-analýzy a N-analýzy D-stromů a využi- aby existovaly dvě větve z A, kde v první větvi je prove-
jeme tato porovnání pro charakterizaci (klasifikaci) těchto dena dříve redukce s u a v té druhé větvi je dříve provedena
D-stromů. redukce s v.)
Princip S-kompatibility. Nech X ∈ {NES, NS, N}. Princip Tc-kompatibility. Necht’ máme NES-analýzu
Pokud platí, že t1 (T,X) t2 a zároveň platí, že A D-stromu t, dvě hrany e1 , e2 stromu t, které neleží
Str(t1 ) Str(T ) Str(t2 ), tak říkáme, že redukce t1 (T,X) (oběma uzly) na jedné cestě v t a e1 , e2 jde obě redu-
t2 je S-kompatibilní. Neformálně řečeno, pokud redukci kovat jako určující hrany UEC-operací. Požadujeme, aby
D-stromů odpovídá řetězová redukce na řetězech získa- během A mohla být dříve provedena kterákoliv z těchto
ných projekcí ze stromů, která je vztažena k jazyku řetězů UNC-operací (tj. existují dvě větve z A , kde v první je
Str(T ), daných množinou stromů T . provedena dříve redukce s e1 a v té druhé je redukována
Podobně říkáme, že (T,X) (t) je S-kompatibilní, pokud dříve e2 . Poznamenejme, že v jedné větvi nemusí být nutně
všechny jeho X-redukce jsou S-kompatibilní a pokud za provedeny obě tyto redukce.
předpokladu u ∈ (T, X)0 a t ∗(T,X) u platí, že Str(u) ∈ Říkáme, že X-analýza (T,X) je k-omezená, pokud po-
Str(T )0 . čet vypuštěných uzlů v jednotlivých X-redukcích z (T,X)
Říkáme, že X-analýza (T,X) je S-kompatibilní pokud nepřesahuje k a (T, X)0 neobsahuje D-strom s více uzly
všechny její D-stromy mají S-kompatibilní X-analýzu. než k.
Fakt. Vidíme, že (T,X) (t) je S-kompatibilní pokud Analogicky lze zavést k-omezenou X-analýzu jednotli-
Str( (T,X) (t)) = {Str(u) > Str(v) | u (T,X) v ∈ (T,X) vého stromu.
(t)} tvoří DS-analýzu věty Str(t) vzhledem k jazyku Říkáme, že X-analýza (T,X) (t) D-stromu t je propor-
Str(T ). cionální, pokud Str( (T,X) (t)) je proporcionální.
Princip S-kompatibility je tak požadavkem, který Máme také možnost měřit složitost X-redukcí pomocí
zaručuje přirozený vztah mezi větnou DS-analýzou počtu operací užitých v jednotlivých X-redukcích.
a X-analýzami na D-stromech.
Fakt. Uvažujeme NS-analýzu A D-stromu t. Platí, že Příklad 7. D-strom reprezentující obrázek 4:
uzel u, který je ve stromě t na cestě ke kořenu blíže než T3 = ({[2, b2 ], [3, b3 ], [6, b6 ]},
uzel v, nemůže být v žádne větvi NS-analýzy A vypuštěn {([2, b2 ], [3, b3 ]), ([6, b6 ], [3, b3 ])}, ([3, b3 ], [2, b2 ], [6, b6 ]))
dříve než v. D-strom representující obrázek 5:
Redukční analýza a Pražský závislostní korpus 49
T4 = ({[2, b2 ], [3, b3 ], [4, b4 ], [5, b5 ], [6, b6 ]}, A1 je NS-analýzou věty (D-stromu) s trojnásobnou (ne-
{([2, b2 ], [3, b3 ]), ([4, b4 ], [3, b3 ]), ([5, b5 ], [4, b4 ]), zapuštěnou) koordinací.
([6, b6 ], [3, b3 ])}, A1 není Ta-kompatibilní, protože množiny UNC-operací
([3, b3 ], [2, b2 ], [4, b4 ], [5, b5 ], [6, b6 ])) v jednotlivých větvích nejsou stejné.
A1 obsahuje redukce, které používají dvě UNC-operace.
Příklad 8. Vidíme, že D-strom T1 má jen značky odpo-
Tím se liší od závislostních redukcí, které používají jen
vídající závislostem (nemá značky Cr, Co pro koordinace).
jednu UNC-operaci.
Let R2 = {T1 , T2 , T3 , T4 }, kde D-stromy T1 , T2 , T3 , T4 byly
Všimněme si, že určující uzly dvou UNC-operací v jedné
popsány v předchozích příkladech.
redukci visí na stejném uzlu (se značkou Cr) a odstraněné
Vidíme, že
podstromy tvoří souvislý úsek v uspořádání uzlů.
(R2 ,NES) = {T1 (R2 ,NES) T2 , T2 (R2 ,NES) T3 ,
Povšimněme si ještě, že budeme-li uvažovat N-analýzu
T1 (R2 ,NES) T4 , T4 (R2 ,NES) T3 },
A2 D-stromu T c1 , tak přijdeme o poslední větev se
a dále že (R2 ,NES) je rovno nejen (R2 ,NES) (T1 ) ale,
shiftem. A2 je také S-kompatibilní, Tl-kompatibilní,
i (R2 ,NS) (T1 ).
Tb-kompatibilní a proporciální. A2 má tedy také pěkné
Platí, že (R2 , NES)0 = {T3 }. vlastnosti.
(R2 ,NES) (T1 ) je tedy NS-analýzou věty T1 , ale Vymezení závislostně-koordinačních D-stromů
není její N-analýzou, jelikož NS-redukce T2 (R2 ,NS) T3 bez vložených koordinací. Podobné vlastnosti jako
a T1 (R2 ,NS) T4 používají shift. má NS-analýza D-stromu T c1 požadujeme po všech
Vidíme také, že (R2 ,NS) (T1 ) je S-kompatibilní, a že její D-stromech bez vložených koordinací. Má to být
redukce používají jedinou UNC-operaci a maximálně je- NS-analýza, která je S-kompatibilní, Tl-kompatibilní a
den shift. Tb-kompatibilní (triviálně i Tc-kompatibilní). Může pou-
(R2 ,NS) (T1 ) je také Ta-kompatibilní, Tb-kompatibilní žívat dvě UNC-operace v jedné redukci, které odstraňují
(a triviálně Tc-kompatibilní a Tl-kompatibilní), dva vedlejší podstromy visící na jednom uzlu.
2-omezená, a proporcionální. Pozorování. V PDT jsme zatím nezpozorovali žádnou
Vymezení čistě závislostních D-stromů. Podobné odchylku proti předchozímu vymezení. Pokud však bu-
vlastnosti jako má NS-analýza D-stromu T1 požadujeme deme uvažovat jen NS-analýzu D-stromu T c1 , která bude
po všech čistě závislostních D-stromech (obsahují jen pracovat s jedinou UNC-operací v redukci, tak ta není
hrany (uzly) se závislostními kategoriemi (značkami)). S-kompatibilní.
Čistě závislostní D-stromy mají NS-analýzu, jejíž re- Poznamenejme, že malou technickou změnou v metodě
dukce obsahují jedinou operaci UNC a nejvýše tři shifty. zobrazování vícenásobných koordinací v PDT bychom
Každá NS-analýza čistě závislostního D-stromu má být dosáhli toho, že by pro zachování S-kompability u re-
S-kompatibilní, Ta-kompatibilní, Tb-kompatibilní (trivi- dukcí tohoto jevu by nebylo třeba použít více než jednu
álně i Tc-kompatibilní a Tl-kompatibilní) a proporciální UNC-operaci.
vzhledem k množině všech korektních NS-redukcí korekt- Příklad 10.
ních čistě závislostních stromů. Toto formální vymezení V tomto příkladě budeme pozorovat D-strom T cz3 z ob-
závislostních stromů odpovídá rozšířenému intuitivnímu rázku 16, jeho NES-analýzu A3 na obrázcích 16 až 18
vnímání závislostí a je logickým vzorem i pro vymezení a jeho DS-analýzu z obrázku 8.
D-stromů s koordinacemi. T cz3 obsahuje uzel s dvojicí značek Cr, Co i hranu,
Pozorování a poznámka. V PDT jsme nezpozo- která má oba uzly se značkou Co.
rovali žádnou odchylku proti předchozímu vymezení A3 je S-kompatibilní, Tl-kompatibilní a Tb-kompatibilní
u D-stromů s čistě závislostními značkami. Pokud však i Tc-kompatibilní.
budeme uvažovat jen N-analýzu D-stromu T1 , tak ta není A3 je NES-analýzou věty (D-stromu) s vloženou koordi-
ani S-kompatibilní, ani Ta-kompatibilní. Pozorování pří- nací, kde UEC-operace jsou uplatněny na hrany u kterých
kladů tohoto typu nás vedla k rozšíření původně užívané mají oba uzly značku Co, tedy hrany vložené koordinace.
N-analýzy na vhodnější NS-analýzu, kterou lze uplatňo- Řídící uzel těchto hran mívá ještě značku Cr.
vat zřejmě na celou třídu čistě závislostních D-stromů při Uvažujeme-li NS-analýzu A4 D-stromu T cz3 , tak vi-
zachování výše požadovaných principů. díme, že A4 není S-kompatibilní, jelikož nemá na rozdíl od
Příklad 9. V tomto příkladě budeme pozorovat D-strom odpovídající DS-analýzy z obrázku 8 žádné redukce.
T c1 z obrázku 9, jeho NES-analýzu A1 na obrázcích 10 až Vymezení závislostně-koordinačních D-stromů. Po-
13 a jeho DS-analýzu z obrázku 6. T c1 neobsahuje uzel dobné vlastnosti jako má NES-analýza D-stromu T cz3
s dvojicí značek Cr, Co, ani hranu, která má oba uzly se požadujeme po všech D-stromech s koordinacemi
značkou Co. a závislostmi. Má to být NES-analýza, která je
Vidíme, že A1 D-stromu T c1 je NS-analýzou (nepoužívá S-kompatibilní, Tl-kompatibilní a Tb-kompatibilní (trivi-
UEC-operace). álně i Tc-kompatibilní). Může používat UEC-operace s ur-
A1 je S-kompatibilní, Tl-kompatibilní a Tb-kompatibilní čující hranou jejíž oba uzly nesou značku Co (jiné UEC-
(triviálně i Tc-kompatibilní) a proporciální. operace nejsou povoleny).
50 M. Plátek, D. Pardubská, K. Oliva
Pozorování. V PDT jsme zatím nezpozorovali žádnou vání D-stromů z Pražského závislostního korpusu (PDT)
odchylku proti předchozímu vymezení. a to D-stromů, které kromě modelování závislostí, mo-
Pozorování obr. 19. Na obrázku 19 je jeden z auten- delují také složené koordinace. Tři (přesněji čtyři) typy
tických stromů z PDT. Podle vzoru tohoto stromu vznikly redukčních analýz D-stromů nám dávají přirozenou ta-
naše obrázky 12 až 18 pro tři různé typy redukcí koordi- xonomii závislostních a koordinačních jevů zachycených
nací. D-stromy z PDT.
Připomeňme, že symbol Coord z obrázku 19 je sym- Domníváme se, že zavedený aparát dovolí hlouběji
bol Cr na našich obrázcích, symbol Coord_Co je v našich porozumět neprojektivitě a jejím mírám a volnosti slo-
obrázcích nahrazen symbolem Cr.Co. Symbol Coord_Co vosledu. To bude jedno z témat, kterým se budeme zabývat
je značkou, která má označovat řídící uzel (otce) vložené v blízké budoucnosti.
koordinace. V obrázku 19 je tento symbol jednou užit ne- Dále se domníváme, že uvedená metoda by měla po-
správně, a to pro frázi ’skromě a Coord_Co každodenně’. moci při odhalování nekonzistencí (či chyb) v PDT, po-
Tato fráze zde není vloženou koordinací, ale koordinova- dobně jako to bylo v případě D-stromu z obrázku 19.
nou závislostí podobně jako na obrázku 13. V blízké budoucnosti bychom také rádi zahrnuli do
NES-analýzou získáme z obrázku 19 několik dále nere- metody redukční analýzy zbylé syntaktické jevy, které
dukovalných vět s koordinacemi, které mají bez identifi- jsou v PDT rozlišeny. Máme na mysli hlavně koordinace
kačního uzlu a uzlu pro tečku jen tři uzly. NES-analýza s elipsami.
bude S-kompatibilní, Tl-kompatibilní a Tb-kompatibilní Na závěr děkujeme Markétě Lopatkové za poskytování
i Tc-kompatibilní. informací o PDT i za komentáře k poskytnutému materiálu
Použijeme-li na stejný D-strom jen NS-analýzu, ne- a ochotu o něm diskutovat.
dostaneme se u redukovaných a dále neredukovatelných
D-stromů pod sedm uzlů. Toto poslední pozorování při-
pomíná pozorování z [2], kde se implicitně uvažují re- Reference
dukce, používající maximálně jednu UNC-operaci a žád-
[1] Hajič, J. Panevová, J., Hajičová, E., Sgall, P., Pajas, P.,
nou UEC-operaci.
Štěpánek, J., Havelka, J., Mikulová, M., Žabokrtský, Z.,
NS-analýza D-stromu z obrázku 19 nemůže být Ševčíková-Razímová, M.: Prague Dependency Tree-
S-kompatibilní. bank 2.0. Linguistic Data Consortium, Philadelphia, 2006.
[2] Lopatková, M., Mírovský, J., Kubon, V.: Gramatické zá-
vislosti vs. koordinace z pohledu redukční analýzy. In:
Proceedings of the Main Track of the 14th Conference
on Information Technologies – Applications and Theory
(ITAT 2014), with selected papers from Znalosti 2014 collo-
cated with Znalosti 2014, Demanovska Dolina – Jasna, Slo-
vakia, September 25–29, 2014., pages 61–67, 2014.
[3] Lopatková, M., Plátek, M., Kuboň, V.: Modeling syntax
of free word-order languages: dependency analysis by re-
duction. In: Matoušek, V. et al., editor, Proceedings of
TSD 2005, volume 3658 of LNCS, pages 140–147. Springer,
2005.
[4] Plátek, M.: Analysis by reduction of d-trees. In: Proceedings
of the main track of the 14th Conference on Information
Technologies – Applications and Theory (ITAT 2014), with
selected papers from Znalosti 2014 collocated with Zna-
losti 2014, Demanovska Dolina – Jasna, Slovakia, Septem-
Obrázek 19: Autentický D-strom z PDT. ber 25–29, 2014., pages 68–71, 2014.
[5] Plátek, M., Pardubská, D., Lopatková, M.: On minimalism
of analysis by reduction by restarting automata. In: Formal
2.5 Shrnutí Grammar – 19th International Conference, FG 2014, Tü-
bingen, Germany, August 16–17, 2014. Proceedings, pages
V tomto příspěvku jsme exaktně zavedli pojmy větné re- 155–170, 2014.
dukční analýzy a tři typy redukční analýzy D-stromů. For-
mulovali jsme požadavky na kompabilitu větné redukční
analýzy a redukční analýzy D-stromů. Našli jsme operace
a typy redukcí, které dovolí provádět redukční analýzu
D-stromů se závislostmi a koordinacemi stejně jemně a se
stejnými k-omezeními jako větnou redukční analýzu. To
je hlavní přínos tohoto příspěvku. Při formulaci typů re-
dukčních analýz pro D-stromy jsme vycházeli z pozoro-