# Zkouška ## Úvod - počítačová lingvistika vs. zpracování přirozeného jazyka - počítačová lingvistika – formální popis vlastností/fungování přirozených jazyků a jejich automatické zpracování - počítačové zpracování přirozeného jazyka – aplikace metod strojového učení na jazyková data - oblasti počítačové lingvistiky - morfologie (tvarosloví), syntaxe (skladba), sémantika (význam), formalismy (syntaktické), korpusová lingvistika, strojový překlad, rozpoznávání/generování mluvené řeči, vyhledávání informací v textu, dialogové systémy ## Morfologie - historie - indický lingvista Pānini ve 4. století př.n.l. formuloval pravidla morfologie sanskrtu - bylo to blízké složkové gramatice - jeden ze zakladatelů moderní lingvistiky, Ferdinand de Saussure, byl profesorem sanskrtu - morfologií se zabývala i řecko-římská gramatická tradice, protože stará řečtina a latina jsou flektivní jazyky - morfologie - studuje vnitřní strukturu slov - lexikologie – slova se studují jako jednotky slovní zásoby - lexikografie – sestavování slovníků - morfém – nejmenší znaková jednotka jazyka nesoucí význam - lexikální morfém – nese význam slova jako takového - gramatický morfém – určuje gramatickou roli slovního tvaru - příklad: „zahradou“ - „zahrad“ je lexikální morfém - „ou“ je gramatický morfém - další pojmy - morfologie studuje skloňování a časování - tvaroslovné dublety – odlišné slovní tvary mající stejnou gramatickou funkci (na hradě / o hradu, o balíčcích/balíčkách apod.) - homonymní tvary – stejné slovní tvary odvozené od různých slovních základů (žena, tři, hnát, stát, už apod.) - alternace – změna hlásek uvnitř kmene (vůz – vozu, švec – ševce, prkno – prken) - autosémantická (plnovýznamová) slova - synsémantická (pomocná) slova - morfologická typologie jazyků - přílkad: vyjádření množného čísla - nulový rozdíl – např. sheep - funkční slovo – označuje plurál - afixace – např. koncové -s (obecně předpona/přípona) - zvukový rozdíl – např. man × men - reduplikace – zdvojení slova - jazyky - analytické – slovo = morfém - izolační jazyky – vietnamština, čínština - syntetické – slovo > morfém - flektivní jazyky (skloňování, časování, hodně tvarů ke každému základu) – latina, stará řečtina, slovanské jazyky - introflexe – změny probíhají v kořeni - aglutinační jazyky (lepí se k sobě morfémy) – maďarština, japonština - polysyntetické – slovo = věta - inuitské a indiánské jazyky - žádný moderní jazyk ale obvykle nemá výhradně čisté vlastnosti jednoho z těchto typů – jazyky se navzájem ovlivňují, tak vznikají výjimky - přístupy ke zpracování morfologie - morfologie založená na morfémech - slovo = řetízek morfémů, jako korálky na niti - to odpovídá aglutinačním jazykům - morfologie založená na lexémech - slovo = výsledek aplikace pravidel, která slovo mění a tím vytváří nový slovní tvar - viz Two-Level Morphology - morfologie založená na slovech (vzorech) - centrální roli mají vzory - ze základního tvaru slova a vzoru, k němuž slovo patří, umíme vygenerovat všechny tvary - Two-Level Morphology - první obecný model zpracování morfologie přirozeného jazyka - založen na konečných automatech - pro každý jazyk bylo nutné vytvořit slovník a pravidla, mechanismus morfologie byl společný - tradiční počítačové zpracování morfologie (do té doby) se orientovalo na generování tvarů slov ze základního tvaru - nebralo v úvahu, že opačný směr (analýza) může být víceznačný - uplatnění pravidel bývalo sekvenční - 2 úrovně – lexikální a povrchová - základní myšlenky - pravidla se aplikují paralelně, ne sekvenčně - podmínky se mohou vztahovat k jedné nebo oběma úrovním - lexikální vyhledávání (pomocí trie) a morfologická analýza probíhají současně - morfologie založená na vzorech - potřebujeme slovník kmenů slov (s informacemi o jejich vzoru) a seznam koncovek, které u sebe mají seznam vzorů, rodů, čísel a pádů/osob - algoritmus - v textu se vyskytl slovní tvar „kačena“ - odtrhneme všechny možné koncovky → „kačen“, „kače“, „kač“ - kmen „kačen“ je ve slovníku s informací, že je to podstatné jméno vzoru žena - ze seznamu u příslušné koncovky vybereme čísla a pády uvedené pro vzor žena - výsledkem je Kačena(podstatné jméno, rod ženský, 1. pád čísla jednotného) - poznámky - výsledek morfologické analýzy bývá víceznačný - neřešíme zde změny uvnitř kmene, o ty je třeba algoritmus obohatit - morfologické značky (part of speech tags) - něco jako slovní druhy - v kontextu angličtiny to stačí pro identifikaci všech morfologických vlastností slovního tvaru - je to spíše izolační jazyk - POS značky dělíme na dva základní typy – otevřenou a uzavřenou třídu slovních druhů - otevřené slovní druhy – seznam slov, která k nim patří, není nikdy kompletní, protože se jazyk vyvíjí - podstatná jména, přídavná jména, slovesa, příslovce - uzavřené slovní druhy – slova každého z nich lze v podstatě popsat výčtem (další nepřibývají) - předložky, pomocná slova, spojky, … - tagset (sada používaných značek) se liší i mezi různými přístupy v rámci téhož jazyka – PennTreebank používá 45 značek, Brown Corpus jich má 87 - kdybychom chtěli stejně přistupovat k češtině, muselo by značek být přes tisíc - česká morfologie - vyvíjena od roku 1989 zejména profesorem Hajičem - využívá poziční značky, každá pozice má svůj jednoznačný význam - značky jsou 15místné, rozeznává se ale pouze 13 kategorií - kategorie: pos, subpos, gender, number, case, possgender, possnumber, person, tense, grade, negation, voice, var - příklad: AAFP3----3N---- - adjective, regular, feminine, plural, dative, (no poss. gender, no poss. number, no person, no tense), superlative, negated, (no voice, reserve1, reserve2, base variant) - činnosti využívající morfologii - morfologická analýza – na vstupu slovní tvar, na výstupu seznam všech lemmat a značek, které jsou pravděpodobné - morfologické značkování (tagging) – proces výběru správné značky v daném kontextu (statistické metody) - lemmatizace – na vstupu slovní tvar, na výstupu lemma (důležité pro vyhledávání v textech) - lemma – jednoznačný identifikátor slova - sloveso stát → lemma „stát-1“ - šel → lemma „jít“ - stemming – odříznutí koncovky (na vstupu slovní tvar, na výstupu kmen slova), populární je Porterův stemmer - generování – výběr správného slovního tvaru na základě lemmatu a kombinace gramatických kategorií - Částečná morfologická desambiguace založená na pravidlech - Oliva, Petkevič - pomocí spolehlivých pravidel redukuje počet značek - pravidla mají dvě části – popis kontextu a akce (odstranění nevhodných značek nebo potvrzení správné značky) - pravidla byla tvořena ručně a testována na anotovaném korpusu, jsou na sobě nezávislá - cílem bylo snížit počet variant značek, aby následné statistické značkování mělo lehčí úlohu - opravdu došlo k nepatrnému zlepšení celkového výsledku - v podstatě se tak potvrdilo, že statistický přístup založený na anotovaném korpusu se dokáže správně rozhodovat velmi podobně jako lingvistický expert - příklad pravidla: pokud je po slově „se“ sloveso, pak „se“ nemůže být předložka, protože mezi předložkou a jejím řídícím podstatným jménem nemůže být sloveso - značkování (POS tagging) - výběr nejpravděpodobnější morfologické značky pro daný slovní tvar - neřešíme slova izolovaně, hledáme nejpravděpodobnější posloupnost značek pro celou větu - použijeme MAP estimation: $\hat t_1^n=\text{argmax}_{t_1^n}\, P(w_1^n\mid t_1^n)\cdot P(t_1^n)$ - nutná zjednodušení - pravděpodobnost výskytu slovního tvaru závisí pouze na jeho značce - pravděpodobnost výskytu značky závisí pouze na předchozí značce - po úpravě: $\hat t_1^n\approx\text{argmax}_{t_1^n}\, \prod_{i=1}^n P(w_i\mid t_i)\cdot P(t_i\mid t_{i-1})$ - obvykle značkování bere v úvahu kontext přibližně tří slov - skryté Markovovy modely (HMM) - standardní metoda analýzy řad (posloupností událostí v čase) na základě kontextu - posloupnost rozhodnutí, která jsou na sobě závislá - Markovova hypotéza – kontext je možno zkrátit na délku, která je spočitatelná (bigramy, trigramy) - skryté – některé vlastnosti posloupnosti nejsou pozorovatelné (vidíme slova, nikoliv jejich morfologické značky) - jedná se v podstatě o stochastický konečný automat - HMM se skládají z následujících komponent - množina N stavů - matice přechodových pravděpodobností (pravděpodobnost přechodu z jednoho stavu do druhého) - posloupnost pravděpodobností pozorování (pravděpodobnost nějakého pozorování v konkrétním stavu) - počáteční distribuce pravděpodobností nad stavy - tři základní úlohy s HMM - učení statistického modelu - je dána struktura modelu (počet skrytých stavů) a trénovací množina, cílem je najít parametry modelu (pravděpodobnosti přechodů mezi stavy a pravděpodobnosti jednotlivých prvků posloupnosti) - Baum–Welshův algoritmus - rozpoznávání (ohodnocení) statistického modelu - jsou dány parametry HMM, cílem je spočítat pravděpodobnost, že je pozorována posloupnost X - dynamické programování, forward-backward algoritmus - dekódování - hledání nejpravděpodobnější posloupnosti skrytých stavů (pro daný statistický model a posloupnost pozorování) - dynamické programování, Viterbiho algoritmus - Viterbiho algoritmus - v podstatě hledání nejkratší cesty v grafu - ohodnocení hran grafu odpovídají pravděpodobnostem přechodu - kontrola překlepů - základní požadavky při kontrole překlepů – je obtížné je splnit všechny najednou - všechny překlepy musejí být nalezeny a opraveny - musejí být přezkoušeny kontextové podmínky korigované verze - slova, která systém nezná, by neměla být hlášena jako chyby - systém by neměl dávat falešná chybová hlášení - korektura musí být co nejvíce automatická - čas zpracování musí být velmi krátký - měření úspěšnosti - precision $P = {TP\over TP+FP}$ - počet správně zachycených chyb ÷ celkový počet chybových hlášení - recall $R = {TP\over TP+FN}$ - počet správně zachycených chyb ÷ celkový počet chyb v textu - F-measure/F-score (míra F / F skóre) - $F_1 = {2PR\over P+R}=\frac{TP + TP}{TP+FP+TP+FN}$ - kontrola překlepů – 2 základní metody - porovnávání řetězců se slovy ve slovníků - buď seznam všech slovních tvarů (wordlist), nebo seznam lemmat + morfologická analýza - spolehlivé a jednoduché, ale pomalé a náročné na kvalitu slovníku, nerozezná to chybná slova od neznámých - srovnávání skupin znaků, hledání nedovolených kombinací - rychle a nezávislé na slovníku, ale velmi neúplné, jelikož spousta chybných slov se skládá z vhodných kombinací znaků - jak nabízet opravy - chceme nabízet pouze relevantní opravy – ale ne všechny, chceme je uspořádat podle relevance a vybrat několik málo možností - co lze zohlednit při nabízení oprav - okolnosti vzniku chyb (blízké klávesy apod.) - statistiku chyb - možné pravopisné chyby (mně × mě) - heuristiku na oddělení chyb a neznámých slov - syntax a sémantiku - kontext (lze porovnávat s korpusy apod.) - lze použít Levenštejnovu vzdálenost – minimální počet elementárních editačních operací - komerční řešení - k omezení množství nabízených tvarů se používá Levenštejnova vzdálenost - upřednostňuje se přesnost (nenalezené chyby autor nevidí :)) a rychlost - uživatel nechce být rušen – kontrola se provádí na pozadí, nemusí se ručně pouštět - uživatelsky definované slovníky nemají morfologii :( - omezená možnost dalšího rozvoje – vylepšení jdou směrem k většímu uplatnění kontextu - kontextové metody kontroly překlepů - některé chyby nelze odhalit jen pomocí slovníku – weather/whether, there/their, form/from apod. - spellcheckery využívající kontext obvykle používají statistické metody nebo strojové učení - kvalita výsledků je ovlivněna velikostí tréninkových dat a podobností tréninkových dat a vstupního textu - příklady kontextových spellcheckerů - Ghotit - WinSpell - používá záměnnou množinu (confusion set) – to je množina tvarů, u nichž může snadno dojít k záměně - systém ASIMUT - „Automatická selekce informací metodou úplného textu“ - Králíková, Panevová - vyhledává klíčová slova v rozsáhlé množině textů (sbírka zákonů, technické texty, sady návodů apod.) - nemá kompletní slovník českých lemmat – využívá pravidelnost české morfologie - aby mohl vyhledávat vyskloňované tvary klíčových slov, využívá pozorování, že mnoho slov, která mají v základním tvaru stejný koncový segment, se stejně skloňuje - toto pozorování vychází z retrográdního slovníku dr. Slavíčkové - je uplatněno v *jazykovém modulu* - výjimky je možné uložit do zvláštního slovníku výjimek - řeší rovněž různé varianty kmenů - algoritmus - porovnávají se jednotlivé znaky základního slova odzadu, dokud není možné jednoznačně určit, jak slovo skloňovat - rovněž se generují alternativní kmeny (v případě změn kmenových hlásek) - projde se slovník výjimek odpovídajících konkrétnímu koncovému segmentu - všem slovním základům se přidají všechny pádové koncovky pro daný vzor - perlička – slova, která končí na „ý“ a nejsou to přídavná jména podle vzoru mladý: úterý, prý, čehý - problémy - někdy nám nepomůže libovolně dlouhý koncový segment – trávník × právník - příliš hrubá klasifikace (31 vzorů podstatných a přídavných jmen), pádové koncovky mají varianty, je nutné je všechny vygenerovat - malý rozsah retrográdního slovníku – je nutné přidávat výjimky - nefunguje tak spolehlivě pro slovesa (víceznačné koncové segmenty) - negativní slovník - slova, která nás nezajímají - typicky spojky, částice - konkordance - všem slovním tvarům nezařazeným do negativního slovníku byla přiřazena adresa a frekvence výskytu - používá se pro urychlení hledání - slova z negativního slovníku obdržela pouze adresu kvůli správnému určení vzdálenosti mezi významovými slovy v textu - systém Mozaika - MOSAIC, Morphemic Oriented System of Automatic Indexing and Condensation - indexace dokumentů - řada přípon a koncovek nese význam, např. v angličtině: - -er/-or … konatel děje - -tion … činnost - -ity/-ness … vlastnosti - algoritmus - na vstupu nepředzpracovaný text - lematizace a morfologická analýza poskytnou lemata a morfologické značky - nalezená lemata jsou profiltrována (typicky pomocí minimální délky slov nebo pomocí malého negativního slovníku, také obvykle požadujeme, aby se slova týkala dané tematické oblasti) - syntaktická analýza jmenných skupin pomocí Q-systémů (některé termíny mají více slov) - přiřazení vah na základě výskytu termínů v různě důležitých místech textu (nadpisy, první a poslední odstavce apod.) - normalizace vah vzhledem k délce dokumentů - výstupem je seznam deseti nejvýznamnějších termínů seřazených podle četnosti výskytu - výhody - není nutné vytvářet slovníky odborných termínů, vystačí si s množinou relevantních přípon a koncovek + pravidly a negativním slovníkem - lokální syntaktická analýza umožňuje větší flexibilitu při hledání termínů - problémy - pracné vytváření slovníků a omezujících pravidel podle tematické oblasti - neřeší to, že ve větách může být nějaké slovo přítomno jako nevyjádřený podmět ## Syntaxe - používají se dva hlavní datové typy - závislostní strom - přibližně to, co se učí ve škole (akorát klíčové je sloveso, pod něj se všechno napojuje) - dependency grammar - složkový strom - anglosaská tradice - phrase structure grammar - závislostní strom - pětice $T=\braket{N,E,Q,WO,L}$ - $(N,E)$ … orientovaný graf - $Q$ … gramatické kategorie (popisky uzlů) - $WO\subseteq N\times N$ … silné úplné uspořádání (určuje pořádek slov) - $L:N\to Q$ … ohodnocovací funkce (určuje gramatické kategorie uzlů) - závislostní strom vytvořený podle této definice má přesně tolik uzlů, kolik je prvků (tokenů) ve větě (slova, interpunkční znaménka) - vlastnosti závislostního stromu - nedává informace o postupu vytváření – jen o vztazích mezi uzly - zachycuje vztahy mezi větnými členy - nedává návod, jak strom získat - ne všechny vztahy ve větě jsou přirozeně popsatelné jako závislost, není vždy jasné, co na čem závisí - třeba u souřadného spojení „Petr a Pavel“ (tzv. koordinace) si musíme vybrat, kdo bude nadřazený - slovo „Petr“ reprezentuje celou skupinu, je v čísle jednotném, ale skupina je v čísle množném - asi by nejlépe fungovalo, kdybychom přidali speciální uzel za koordinaci - podobně problematické jsou předložky – není jasné, jestli mají být nad nebo pod jménem - složkový strom - složka (constituent) = skupina slov, která fungují společně a tvoří jednu syntaktickou jednotku - složku můžeme ve větě rozpoznat například pomocí nahrazovacího testu - Studenti potkali **své přátele** po vyučování. - Studenti **je** potkali po vyučování. - nebo testem přesunem - Jane bought a hat **from that strange** little shop. - \***From that strange** Jane bought a hat little shop. - v češtině se dá často pořadí slov měnit - ale existuje [Wackernagelův zákon](https://cs.wikipedia.org/wiki/Wackernagel%C5%AFv_z%C3%A1kon) - vlastnosti složkového stromu - odpovídá derivačnímu stromu bezkontextové gramatiky - je méně přehledný, mnohdy obsahuje spoustu nadbytečných uzlů - přirozené jazyky nebývají bezkontextové - neprojektivní konstrukce - příklady - Soubor se nepodařilo otevřít. - Vánoční nadešel čas. - Které děvčata chtěla dostat ovoce? - Tuto knihu jsem se mu rozhodl dát k narozeninám. - větu nelze rozdělit do složkového stromu – vertikály z uzlů protínají hrany - některá slovesa mají povinné vazby - jakmile jsou ve větě dlouhé neprojektivní vazby nad rámec těch povinných, můžou být nejednoznačné - závislostní strom je projektivní, pokud neobsahuje neprojektivní závislosti - pokrytí uzlu v závislostním stromu je množina indexů uzlů, které jsou (i nepřímo) závislé na daném uzlu - do pokrytí kořene patří indexy všech uzlů - pokud má uzel $u$ např. pokrytí $4, 5, 6, 8, 9$, pak uzly $6, 8$ tvoří tzv. díru v pokrytí uzlu $u$ - počet děr v závislostním stromu je spolehlivou mírou složitosti syntaktické analýzy - Q-systémy - Alain Colmerauer 1969 - nástroj pro syntaktickou analýzu - formalismus pro transformaci grafů - popisky hran v grafech reprezentují slova nebo syntaktické stromy - stromy jsou linearizovány, což usnadňuje práci s nimi - kompletní gramatika se může skládat z více Q-systémů, které na sebe navazují - používá se závislostní gramatika - základní vlastnosti - grafový analyzátor (chart parser) - tři typy proměnných: atomy, stromy, seznamy stromů - pravidla mají omezený počet proměnných - typy jsou implicitní – podle toho, jaké písmeno použijeme pro název proměnné (např. atomy používají písmena A–J) - operátory `-DANS-`, `-HORS-`, `-ET-`, `-NON-`, … - vstupní graf se postupně upravuje podle gramatiky - čištění stromu - první fáze – odstranění hran, které byly použity na levé straně libovolného pravidla - druhá fáze – odstranění hran, které nejsou umístěny na žádné cestě vedoucí od startovního nebo do koncového uzlu - těmito operacemi se graf zbaví nežádoucích dílčích výsledků před vstupem do navazujícího Q-systému → tak se dá složitá gramatika rozdělit na jednodušší části ## Gramatické formalismy - předchůdci transformační gramatiky - deskriptivismus - jazyková data klasifikuje, ale nevysvětluje - zpracovává zejména povrchovou větnou strukturu - cestování po indiánských rezervacích - analytická syntax - logický přístup - kategoriální gramatika - využívá koncept povrchové a hloubkové syntaktické struktury - povrch … konkrétní vyjádření - hloubka … význam - jednomu významu může odpovídat více vyjádření - jedno vyjádření může mít více významů - transformační gramatika - Noam Chomsky - povrchová a hloubková syntaktická struktura - třeba bychom chtěli větu pasivní snadno převést na aktivní - nebo tázací, rozkazovací apod. - tedy jak z jedné hloubkové syntaktické struktury odvozovat různé povrchové - 3 základní komponenty transformační gramatiky - báze - soubor bezkontextových pravidel, která generují složkové stromy, tzv. frázové ukazatele (phrase markers) - transformační komponenta - transformační pravidla operující na celých frázových ukazatelích - pravidla se dělí na obligatorní a fakultativní - fonologická komponenta - obsahuje regulární přepisovací pravidla přidělující řetězcům morfémů fonetické interpretace - generativní procedura - vytváří množinu přijatelných vět daného jazyka - je to soubor konečného počtu přepisovacích pravidel - je to v podstatě bezkontextová nebo kontextová gramatika - není schopna zachytit vztahy mezi variantami vět (tázací × ozmanovací) - transformační složka - obsahuje pravidla, která z frázových ukazatelů vytváření povrchovou strukturu věty - John chose a book → a book was chosen by John - vývoj transformační gramatiky - Standard Theory - Extended Standard Theory - Government-binding theory - založená na obecných principech univerzální gramatiky a parametrech platných pro jednotlivé jazyky - Chomsky si myslí, že schopnost naučit se lidský jazyk je univerzální vrozenou schopností každého člověka a že odlišnost jazyků je způsobena různými parametry - Teorie minimalismu - pouze dvě roviny – rovina logické formy (LF) a fonetická rovina (PF) - PF – rozhraní mezi zvukem a reprezentací jazyka - LF – rozhraní mezi reprezentací jazyka a významem - kritika Chomského teorií – jeho základní předpoklady se dají těžko dokázat, nejsou založeny na datech - tree adjoining grammars - substituce stromů - elementární struktury jsou stromy - některé uzly je možné substituovat stromem (ty jsou označené šipkou ↓) - v daném uzlu je neterminál (např. N), můžeme tam substituovat jenom stromy, které mají stejný neterminál v kořeni - pořadí substitucí nehraje roli - proces končí, pokud už žádný neterminál nelze nahradit - nakonec dostaneme strom reprezentující syntaktickou strukturu věty - generativní síla odpovídá bezkontextovým gramatikám, po modifikacích mohou být i silnější (kontextové) - kategoriální gramatiky - slova vyžadují určité konstrukce – to reprezentujeme pomocí tzv. kategorií - kategorie reprezentuje popis syntaktických vlastností dané slovní formy - sloveso likes má kategorii (NP\\S)/NP - obecně mají kategorie formát $\alpha/\beta$ nebo $\beta\backslash\alpha$, lomítko určuje pozici argumentu (používají se ale i jiné notace) - „čistá“ kategoriální gramatika umožňuje jenom dvě pravidla - `X/Y Y => X` - `Y Y\X => X` - obvykle se úkoly syntaktické analýzy rozdělují mezi gramatiku a slovník - v kategoriálních gramatikách jsou však všechny podstatné gramatické informace obsaženy ve slovníku - čekali bychom, že gramatika bude popisovat třídy slov – ne jednotlivá slova - pokud tyhle informace přesuneme do slovníku přímo ke slovům, bude jich strašně moc - kombinatorická kategoriální gramatika - pravidlo se dá vyjádřit jednou pro všechny jeho permutace - unifikační gramatiky - objekt je popsán tzv. sestavou rysů (feature structure) - rys (feature) je dvojice `klíč : hodnota` - unifikace = spojování dvou sestav rysů popisujících stejný objekt - je povolena, pokud si rysy neodporují - máme definována gramatická pravidla, která unifikaci ovlivňují - hodnotou vlastnosti může být i sestava rysů nebo proměnná - proměnná nám vynutí, aby se při další unifikaci dva rysy nemohly lišit - problém: je možné unifikovat vlastnosti, které spolu nijak nesouvisejí - typované sestavy rysů – typ sestavy určuje její vlastnosti (typ *verb* → vlastnosti *person, number, mode*) - funkční generativní popis - Sgall, Hajičová, Panevová - navazuje na Pražskou lingvistickou školu - základní vlastnosti - stratifikační teorie (5 rovin – fonetická, fonologická, morfematická, povrchová, tektogramatická) - formy a funkce – jednotka na vyšší rovině reprezentuje funkci jednotky na rovině nižší (TG rovina je nejvyšší) - závislostní reprezentace - teorie valence (vazby, vyžadované nebo povolené řídícími slovy, zejména slovesy) - valence - popisuje schopnost některých slovních druhů vázat k sobě jiná slova nebo skupiny slov ve větě - v závislostním pojetí hrají klíčovou roli slovesa – větné členy, které jsou na nich závislé, tvoří jakousi kostru závislostního stromu - dva základní druhy závislých členů - aktanty – každý může být ve větě pouze jednou (ale samozřejmě je lze koordinovat) - konatel (aktor, agens) - patient - adresát - origo - efekt - volná doplnění – může jich být více (typicky příslovečná určení) - další dělení – obligatorní a fakultativní - obligatorní aktant ve větě nesmí chybět (na tektogramatické rovině – naopak může chybět na povrchové rovině, je-li známý z kontextu apod.) - Petr (k.) předělal Pavlovi (a.) loutku (p.) z kašpárka (o.) na čerta (e.). - typické sloveso může mít více valencí - valenční rámec – seznam aktantů (obligatorních i fakultativních) a obligatorních volných doplnění - dialogový test – pokud na doplňující otázku nelze odpovědět „nevím“, jedná se o obligatorní aktant - příklad: Moji přátelé přijeli. - kam? ~~nevím~~ … obligatorní aktant - odkud? nevím … fakultativní aktant - valenční slovník češtiny (Vallex) a angličtiny (EngVallex) - kontrola gramatické správnosti - problematické příklady - Sportovci věnovali plyšáka. - (Co si kdo kam donesl?) Tatínek šli do práce. - problémy specifické pro češtinu - gramatická shoda (zejména podmětu s přísudkem) - interpunkce - neprojektivní konstrukce - zájmena (mě/mně) - jak kontrolovat? - chybové vzorky – vhodnější pro jazyky s pevným slovosledem, kde se chybné konstrukce vyskytují převážně v lokálním kontextu - gramatika – nelze rozeznat, kdy je konstrukce chybná pouze vzhledem k neúplné gramatice a kdy je opravdu špatně - v korpusech jsou pozitivní příklady - chybí nám negativní data - to, že v korpusu žádná věta nemá dva podměty, ještě neznamená, že je to špatně - metoda redukční analýzy - z věty postupně vyhazujeme závislá slova - izolujeme chybnou konstrukci (např. podmět a přísudek, pokud se neshodují) - po redukční analýze nám zůstane minimální chybová konfigurace - homonymie je problematická - příklad: Jeho čelisti (cellisti) klapali naprázdno. - RFODG - robust free-order dependency grammar - jedno pravidlo gramatiky může popisovat správnou i chybnou konstrukci zároveň - výpočet probíhá ve fázích, interpret gramatiky rozhoduje, jak se bude stejné gramatické pravidlo používat - tvrdé a měkké podmínky - 3 fáze - pozitivní projektivní - všechny měkké podmínky chápu jako tvrdé - když to vyjde, tak vím, že je věta dobře - negativní projektivní nebo pozitivní neprojektivní - buď je ve větě chyba, nebo neprojektivní konstrukce - negativní neprojektivní - jakmile nenajdu správnou variantu a hledám chybu, začíná to být náročné, variant je mnoho - LanGR - nástroj pro desambiguaci české morfologie - redukční metoda – snaha udržet 100% přesnost - pracuje s pozitivními a negativními desambiguačními pravidly - mohou mít neomezený kontext - psána ručně, avšak na základě dat z korpusu - vzájemně nezávislá, neuspořádaná, uplatňována v cyklech - 4 části: kontext, desambiguační část, report, akce - příklad - The letter a(Article|Noun) from(Preposition) the given alphabet is represented in blue. - máme pravidlo, které říká, že před slovesem/předložkou/spojkou nemůže být člen ## Korpusová lingvistika - studium jazyka - studium struktury – to jsme řešili doposud - identifikuje strukturní jednotky a třídy jazyka - popisuje, jak se malé jednotky mohou kombinovat a tvořit velké - studium užití – jak mluvčí (a pisatelé) jazyk používají? - potřebujeme velké objemy (pokud možno anotovaných) dat - můžeme objevovat hlubší spojení mezi jazykovými jednotkami - jazykový korpus - sbírka textů, vzorek jazyka - může být doplněn o značky (tagy) identifikující a klasifikující slova nebo jiné útvary - v Česku až do 90. let nebyla dostatečná technika pro sběr a zpracování takového množství dat - charakteristika moderních korpusů - výběr vzorků a reprezentativnost – snaha o vyváženost (jazyk je nekonečný, korpus je konečný) - konečná velikost – korpusy mají obvykle pevnou velikost, která umožňuje kvantitativní výzkum, výjimkou jsou monitorovací korpusy, kam jsou data stále přidávána - strojově čitelná forma - standardní reference – korpus splňuje standardy, aby byl široce použitelný - typy korpusů - psaný × mluvený jazyk - typy značek – morfologické (POS) značky nebo stromy a syntaktické (analytické) značky, někdy také sémantické značky - rozdíl ve velikosti - jednojazyčné × paralelní - paralelní … jednání kanadského a evropského parlamentu - obecné × doménově specifické - doménově specifické: nářečí, slang, texty nerodilých mluvčích, … - synchronní × diachronní - diachronní se snaží zachytit vývoj jazyka v čase, obvykle nebývají uzavřené - konzistence korpusových anotací - problém konzistence morfologických nebo syntaktických značek - na anotaci korpusů se podílí spousta lidí - některé složité jevy se těžko anotují, je potřeba, aby se anotátoři dohodli, jak je budou anotovat - metody zajištění konzistence - detailní manuály - pravidelná setkání anotátorů - automatické metody odhalování chyb v anotaci - měření shody mezi anotátory (IAA, Inter-Annotator Agreement) - Cohenovo $\kappa=\frac{p_O-p_E}{1-p_E}$ - $p_O$ … pozorovaná shoda - $p_E$ … shoda, kdyby byla anotace náhodná - $\kappa\in[-1,1]$ - 1 odpovídá naprosté shodě - 0 značí shodu odpovídající náhodnému výběru - negativní skóre indikuje, že anotátoři použili odlišná kritéria - Brown Corpus of Standard American English - texty vytištěné v roce 1961 - náhodně vybírané, aby byl korpus dostatečně reprezentativní - milion slov - morfologické značky - Penn Treebank - články z Wall Street Journal - milion slov - existuje překlad do češtiny - syntakticky anotovaný korpus (složkové stromy) - Český národní korpus - UK, MUNI, ÚJČ AV - morfologické značky - v současné době téměř 5 miliard slov - první SYN2000 - zatím poslední SYN2020 - největší je SYN2013PUB - 935 milionů slov publicistických textů z let 2005–2009 - Pražský závislostní korpus (PDT) - propracované anotační schéma aplikovatelné na jazyky různých typů - data jsou malou podmnožinou ČNK - teoretický základ – teorie funkčního generativního popisu profesora Petra Sgalla - 100 000 vět, 1,25 milionu běžných slov - úrovně anotace - morfologie - analytická rovina (povrchově syntaktická) - tektogramatická rovina (4 podroviny) - prosazení závislostních stromů - postupně se ukázalo, že závislostní stromy jsou užitečnější → dnes jsou výrazně častěji zastoupeny - Prague Arabic Dependency Treebank - iniciativa Universal Dependencies - snaha o vybudování jednotného značkování - aby se stejné jevy v morfologii anotovaly stejně - díky této komunitě se závislostní stromy staly standardem ## Strojový překlad - proč je to tak těžké? - slovník - morfologie - syntax - ustálená spojení - kulturní kontext - trojúhelník strojového překladu - analýza – morfologická a syntaktická, někdy také (částečná) sémantická - transfer – převod lexikálních jednotek a transformace syntaktického stromu - generování – rozpouštění syntaktického stromu do správné povrchové formy - teoreticky bychom se mohli obejít bez transferu - pro danou dvojici jazyků může existovat interlingua – logická (formální) reprezentace významu věty společná pro oba jazyky - žádná taková obecně akceptovaná formální reprezentace významu (zatím) neexistuje - [![Vauquoisův trojúhelník](https://upload.wikimedia.org/wikipedia/commons/c/c2/The_Vauquois_triangle_version_1985.svg)](https://commons.wikimedia.org/wiki/File:The_Vauquois_triangle_version_1985.svg?uselang=cs) - první generace - dvojjazyčný slovník – nestačí - předpony, kmeny, přípony – moc nefunguje (viz němčina → čeština) - preediting – nic moc - postediting – používá/používal se např. v EU - použití pivotního jazyka (např. angličtiny) - první úspěch - Georgetownský experiment - velké zjednodušení problému (omezení domény a používaných jazykových prostředků) - padesátá léta, ruština → angličtina - následoval bouřlivý rozvoj - příklon k teorii, práce se syntaxí jazyka, druhá generace systémů - pak přišlo vystřízlivění - zpráva ALPAC (American Language Processing Advisory Committee) - konstatuje nutnost investic do dlouhodobého teoretického lingvistického výzkumu - důsledkem byl konec podpory - ale práce mimo USA pokračovaly - první úspěšný komerční systém - TAUM METEO (1976) - překlad meteorologických zpráv z angličtiny do francouzštiny - podobná situace jako s Georgetownským experimentem - dobře definovaná a výrazně omezená podmnožina jazyka - používal Q-systémy - systém sám rozezná text, který mu dělá potíže, a předá jej lidskému překladateli - další významné systémy - SYSTRAN - překlad dokumentů EU - přímý překlad mezi cca 20 páry jazyků, ale uspokojivá kvalita jen u nejstarších párů (angličtina, francouzština, němčina) - EUROTRA - oficiální projekt EU - megalomanie – 72 jazykových párů - nezvládnutá modularita - do jisté míry podobný negativní efekt jako zpráva ALPAC - strojem podporovaný překlad - vhodný zejména pro opakované překlady mírně aktualizovaných textů (příklad: technické manuály) - *překladová paměť* obsahuje páry přeložených segmentů obohacené o sadu metadat umožňující efektivní správu pamětí - nové vstupní věty se vyhledávají v paměti – v případě nalezení se nabídnou překladateli se zvýrazněnými rozdíly - praxe ukazuje, že při shodě menší než 70 % je lepší větu přeložit celou znovu - dva základní přístupy - věta po větě - každá věta je samostatně vyhledávána v překladové paměti, překladatel postupně prochází celý text (vidí kontext věty) - IBM Translation Manager, TRADOS Studio - překladová tabulka - překladatel nevidí kompletní kontext - překládá každou větu pouze jednou - Déjà Vu (Atril) - RUSLAN - překlad manuálů k operačním systémům sálových počítačů - manuály byly potřeba v češtině a v němčině, ale musely být také v ruštině (ty nikdo nečetl) - výzkum zastaven v roce 1990 těsně před provozními zkouškami - fungování - klasický dvojjazyčný slovník + transdukční slovník - klasická architektura: analýza, transfer, syntéza - gramatika zapsaná pomocí Q-systémů - záchranná pravidla pro případ problémů při syntaktické analýze - původně 1 věta za 4 minuty, později třeba i za 20 sekund - stačilo počkat 10 let na výkonnější počítače - nejvíc času nyní zabírá ukládání do souborů (Q-systémy mezi fázemi používají textové soubory k ukládání mezivýsledků) - transdukční slovník (algoritmus) - některá (zvláště technická) slova založená na řeckém nebo latinském základu se dají přeložit jenom přepsáním koncového úseku - příklad: statistický → статистический (statističeskij) - překvapivě transdukční slovníky pro překlad *angličtina → čeština* a *ruština → čeština* vypadají hodně podobně (mají podobnou množinu slov) - valenční rámce sloves jsou v ruštině podobné jako v češtině - idea: určit, zda se sloveso váže s životnými nebo neživotnými jmény - to nefungovalo, lingvisté si neuměli představit použití (např. program může běžet) - systém Česílko - lokalizace velkých softwarových systémů - SAP a jeho manuály - nejdřív kvalitní ruční překlad do češtiny, pak automatizovaný překlad do dalších jazyků (např. slovenštiny) - idea: využití příbuznosti jazyků - typ překladu - FAHQ (plně automatizovaný, vysoce kvalitní) - velmi blízké jazyky - statistické značkování češtiny - dvojjazyčný slovník – slova nelze přímo přepisovat - ukázalo se, že… - pro dobrý překlad mezi češtinou a slovenštinou nestačí transdukční slovník - příklad: české „jarní“, slovenské „jarný/jarná/jarné“ - shodná syntax, většinou shodné pořadí slov ve větě, ale odlišné slovníky (jistá pravidelnost), odlišné tvarosloví - překladatelé používali systémy asistovaného překladu s překladovou pamětí - dalo se do ní něco přidávat - idea: překladatel z němčiny do polštiny při překladu nové věty uvidí (polskou) nabídku, kterou vygeneroval počítač automaticky na základě české verze věty - zajímavý syntaktický rozdíl - bude-li (…) → ak (…) bude - překvapivě překlad do polštiny byl méně kvalitní než do litevštiny (větný pořádek je v polštině jiný než v češtině) - PC Translator 2003 - asi nejlepší český komerční systém - dlouho byl lepší než Google Translate - ten pak používal statistický strojový překlad, dnes se používají neuronové sítě - statistický překlad - příklad: in (angličtina) → dans, à, de (francouzština) - pravděpodobnost vs. relativní četnost - pokud máme hodně dat, relativní četnost se může začít blížit reálné pravděpodobnosti jevů - hlavní úkol: předpovědět následující slovo v běžném textu - nemůžeme používat celou historii, praktičtější je používat poslední tři slova (3-gramy) - problémem je velikost dat – trojrozměrná matice pro slovník se 40k slovy by byla z většiny prázdná (taková matice by měla $6{,}4\cdot 10^{13}$ buněk, ale trénovací data mají obvykle stamiliony slov, tedy $10^8$) - místo nul tam musíme dát hodně malá čísla, aby se nám to pronásobením nevynulovalo - tzv. vyhlazování - akorát pak nemůžeme rozlišovat kombinace, které opravdu neexistují - jak to funguje u překladu? - idea: použijeme paralelní korpus jako trénovací data - metoda zašuměného kanálu - hledáme pravděpodobnost $P(a\mid f)$, tedy pravděpodobnost konkrétní anglické věty $a$ jako překladu francouzského originálu $f$ - z Bayesovy věty odvodíme $P(a\mid f)=\frac{P(f\mid a)\cdot P(a)}{P(f)}$ - jmenovatel není závislý na $a$ - pravděpodobnosti tak můžeme získat ze dvou modelů - $P(f\mid a)$ z překladového modelu - $P(a)$ z jazykového modelu cílového jazyka - „obrátili“ jsme směr překladu - jako bychom obdrželi (anglickou) větu „pokaženou“ přenosem přes nespolehlivý kanál, hledáme její správný originál - překladový model $P(F\mid A)$ může být založen na poměrně malém paralelním korpusu - budujeme ho v opačném směru než chceme reálně překládat - jazykový model $P(A)$ může být trigramový model založený na rozsáhlém korpusu cílového jazyka - odfiltruje nepodařené překlady, vyrovná chyby překladového modelu - vybírá pouze „hezké věty“, nemá vztah k originálu - ale hledání překladových hypotéz (tzv. dekódování) je těžké samo o sobě - metrika BLEU - slouží k evaluaci systémů automatického překladu - neexistuje nic jako jediný správný překlad - porovnáváme dvě verze systému – dva možné překlady - máme k dispozici tři referenční lidské překlady - stačí, když se kandidátský překlad shoduje s aspoň jedním referenčním - n-gramové přesnosti - unigramová přesnost … $C/N$ - $N$ … počet slov, které kandidát obsahuje - $C$ … počet slov z kandidáta, které se vyskytují v alespoň jednom referenčním překladu - můžeme zobecnit na n-gramy - penalizace za stručnost (n-gramová přesnost má tendenci zvýhodňovat krátké věty) - $BLEU=BP\cdot\sqrt[4]{p_1p_2p_3p_4}$ - $BP$ … penalizace za stručnost (brevity penalty) - $p_n$ … $n$-gramová přesnost - $BLEU\in[0,1]$ - v češtině by to nefungovalo moc dobře, různé tvary téhož slova by se vyhodnotily jako různá slova - také by byl problém s volným slovosledem – rozbily by se n-gramy - výhody: rychlý výpočet, poměrně objektivní míra, koreluje s lidským hodnocením, stala se obecně přijímaným standardem - nevýhody - získání dostatečného počtu referenčním překladů je drahé - favorizuje statistické systémy, které se vůči ní ladí - špatně zachycuje varianty (slovosledné, lexikální, morfologické) - často se používá špatným způsobem (k porovnávání různých systémů a odlišných jazykových párů) - přeceňuje se, není tak univerzální, jak vypadá - podmínky, kdy metrika funguje - porovnává různé verze stejného systému (ne různé systémy) - více referenčních překladů - velké množství testovacích vět - taky nedává smysl takto porovnávat různé jazyky - možné vylepšení: pracovat se slovníkem synonym (ale pak už systém nebude tak jednoduchý) ## Sémantika - základní poznámky k sémantice - popis syntaxe umožňuje rozlišit správně a nesprávně utvořené věty - i syntakticky správné věty však můžou být nesmyslné - význam a pravdivost sdělení (v přirozených jazycích) jsou odlišné záležitosti – i nepravdivá sdělení mají svůj význam - u formálních jazyků spolu pravdivost a význam často úzce souvisejí - vyplývání – věta v sobě často nese i další informace, které nejsou explicitně zmíněny - příklad: Karel prodal auto sousedovi → Karel měl auto, už ho nemá, soused je od něj koupil a teď ho má - Fregeho princip kompozicionality - význam složeného výrazu je jednoznačně určen významy jeho částí a způsobem jejich kombinace - lexikální sémantika - význam slov můžeme popisovat pomocí nějakého (meta)jazyka - formálního - přirozeného - či v reálném světě kombinací jazyka a situace - příklad: „Toto je křída.“ - význam často závisí na kontextu - význam slov můžeme nezávisle na kontextu popisovat pomocí významových (sémantických) tříd (rysů) - ontologie = množina tříd objektů, ty klasifikují objekty universa - možné třídy: fyzické objekty, kvantity, vztahy, vlastnosti, akce, … - tyto třídy lze dále zjemňovat - existují doménové (domain) a vrcholové (upper) ontologie - význam slov ale není jednoznačný (některá slova mají více lexikálních významů) - lexikální význam – jeden z významů daného slova (např. koruna – královská koruna) - jak reprezentovat význam slov - ve slovnících – několik způsobů - synonyma - definice - množina vybraných primitivních výrazů daného přirozeného jazyka - speciální metajazyk – sémantické rysy - pomocí sémantické sítě - lepší zachycení víceznačností - lze pracovat s hierarchií pojmů - výhodnější pro počítačové zpracování - WordNet - anglická podstatná a přídavná jména, slovesa a příslovce - seskupená do množiny synonym (synsetů) - každý synset vyjadřuje určitý koncept, jsou mezi sebou navzájem propojeny sémantickými a lexikálními relacemi - volně k dispozici - EuroWordNet - několik jazyků - vrcholové ontologie (63 nejdůležitějších jazykově nezávislých konceptů) - množiny základních konceptů - jazykově nezávislý soubor indexů - vztahy ekvivalence - není k dispozici zdarma - aplikace WordNetu - automatický překlad – může fungovat jako slovník - extrakce informací (IE) – umožňuje pracovat se sémantickými vztahy (zejména se synonymy), může sloužit při vícejazyčném vyhledávání - určování významů slov (word sense disambiguation) - reprezentace znalostí, odvozování - vyhodnocování kvality překladu (zlepšení BLEU a podobných metrik) - reprezentace významu věty - predikátová logika 1. řádu - z částí věty se sestaví logická formule - pokud chceme reprezentovat modalitu, čas a postoj, musíme přidat nové operátory, které mají jako argumenty formule - presupozice – předpoklad, který musí být pravdivý, aby celá věta vůbec měla pravdivostní hodnotu - příklad: Jupiterův měsíc má oranžové pruhy. – Jupiter musí mít právě jeden měsíc. - neurčitost (fuzziness) - někdy potřebujeme jemnější dělení než true/false - anafora - výraz, jehož interpretace závisí na kontextu - druhy anafory - exofora – odkazování mimo text - „Vidíš ho?“ - endofora – odkazování v rámci textu - anafora (zpětně) - „Petr vyzradil tajemství. To neměl dělat.“ - katafora (dopředu) - „Věřte tomu nebo ne, máme schodkový rozpočet.“ - reference – vztah mezi objekty, kde jeden odkazuje na jiný (např. zájmeno na podstatné jméno) - anaforický vztah předchůdce – následník - typy výrazů - zájmena a „nulové výrazy“ (nevyjádřený podmět nebo jiný větný člen) - „Petr si koupil vstupenku. Vsunul ji do kapsy. Byla děravá.“ - určité jmenné výrazy - „Elektronický zesilovač Tesla… Toto zařízení…“ - elipsa (vypuštěné části výrazů na základě paralelismu s předchůdcem), jmenná a slovesná - „Včera jsem šel pěšky. Kam? Domů.“ - „Petr přinesl dva stoly. Dřevěný a kovový.“ - textové spojovací výrazy vyjadřující mezivětné souvislosti v textu - na jedné straně – na druhé straně - jednak – jednak - důležitost pro aplikace: získávání informací z textu, automatický překlad, dialogové systémy - řešení – používáme celou řadu informací - morfologické značky (u zájmen musí být shoda v rodě) - syntaktická struktura věty - statistické přístupy - členění věty – rozlišujeme jádro a ohnisko věty (viz algoritmus Zásoba sdílených znalostí) - rozsáhlé pomocné znalosti – např. sémantické sítě, tezaury, ontologie - Zásoba sdílených znalostí - modeluje zásobu znalostí, o které mluvčí předpokládá, že ji sdílí s posluchačem - zásoba se mění podle toho, co je „v centru pozornosti“ v daném okamžiku - každý objekt má určitý stupeň aktivace (čím menší, tím více je „v centru pozornosti“) - jednoduchá pravidla - pokud k objektu referujeme, jeho stupeň se nemění - pokud ho explicitně zmíníme ve větě, jeho stupeň aktivace klesá na 0 nebo 1 (podle toho, na jakém místě ho zmiňujeme) - všechny objekty asociované s daným objektem (nemusely v textu vůbec zaznít) mají aktivaci o dva vyšší - po každé větě se stupeň nezmíněných objektů zvyšuje o dva - má své slabiny