Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza PLIN015 Proseminář z počítačové lingvistiky II Miloš Jakubíček Centrum zpracování přirozeného jazyka Fakulty informatiky, Masarykova univerzita xjakub@fi.muni.cz 10. dubna 2014 Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Obsah 1 Organizační pokyny 2 Algoritmická složitost 3 Datové struktury 4 CQL 5 Syntax a syntaktická analýza Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Cíl kursu navázat na PLIN013, obdobná skladba a cíle Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Požadavky k zápočtu přiměřená účast (max. 3 neomluvené absence) vyhotovení 3 průběžných úkolů a složení závěrečného testu tentokrát zkusíme celkem 60 bodů ;) Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Osnova ne nutně pevná, máte-li náměty, ozvěte se algoritmická složitost a její vazba na korpusové databáze pro ZPJ vyhledávání v korpusech, jazyk CQL syntaktická analýza, elementární algoritmy, ukázka gramatik Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza cíl: změřit „výkon“, příp. „náročnost“ programu/algoritmu výsledky by měly být reprezentativní, odrážet skutečné vlastnosti algoritmu, ne jeho konkrétní chování na určitém typu HW klíčové otázky: Co měřit? Jak měřit? Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Co měřit? čas – časová složitost: kolik času potřebuje program na své vykonání? paměť – prostorová/paměťová složitost: kolik paměti (úložného prostoru) program ke svému běhu potřebuje? obě vlastnosti jsou do určité míry komplementární – proč? budeme se zabývat především časovou složitostí Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Jak měřit? Uvažujme následující posloupnosti, ve kterých chceme vyhledat zadaný prvek, např. 3 3 18 1 1 18 3 1 18 2 5 3 1 18 2 5 27 11 3 1 18 1 3 1 1 1 18 2 5 87 12 2 32 45 12 1 3 Kdy nám to potrvá nejdéle? Na čem to závisí? Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Asymptotická složitost cíl: vyjádřit složitost jako funkci vstupu (resp. jeho velikosti, délky), tedy říct, jak roste složitost algoritmu vzhledem k rostoucímu vstupu Můžeme uvažovat složitost v nejlepším případě, průměrném případě, nejhorším případě nebo amortizovanou složitost. 3 18 2 5 1 1 18 3 5 1 1 18 2 5 3 V mnoha případech (ale ne vždy!) nás zajímá hlavně složitost v nejhorším případě. Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Základní složitosti seřazené od „nejmenší“, s užitím tzv. O-notace název složitost n = 102, c = 10 n = 106, c = 10 konstantní O(1) = c 10 10 logaritmická O(log n) 6,64 19,9 lineární O(n) 100 1 000 000 lineárnělogaritmická O(n · log n) 664 19 900 000 kvadratická O(n2) 10 000 1012 kubická O(n3) 1 000 000 1018 obecná polynomiální O(nc) 1020 10600 exponenciální O(cn) 10100 101000000 faktoriálová O(n!) moc strašně moc:) Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Složitost problému vs. složitost algoritmu Složitost algoritmu Složitostí algoritmu rozumíme složitost konkrétní instance zadaného algoritmu (implementovatelného v nějakém programovacím jazyce). Algoritmy pracující s lepší než exponenciální/faktoriálovou složitostí označujeme jako efektivní. Složitost problému Složitostí problému rozumíme složitost optimálního algoritmu korektně řešícího zadaný problém. Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Vyhledávání v neseřazené posloupnosti jaká je složitost demonstrovaného algoritmu? O(n). jaká je složitost problému (tj. jde to lépe) a proč? Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Vyhledávání v seřazené posloupnosti tzv. binárním vyhledáváním nebo-li půlením intervalů jaká je složitost demonstrovaného algoritmu? O(log2 n). jaká je složitost problému (tj. jde to lépe) a proč? Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Vztah asymptotické složitosti a výkonu HW uvažujme jeden krok výpočtu jako 1 s, 10 min odpovídá 600 krokům lineární algoritmus složitosti 3 · n: 10 min stačí na vykonání pro vstup velikosti 200 exponenciální algoritmus 2n: 10 min stačí na vykonání pro vstup velikosti 9 (29 = 512, 210 = 1024) uvažujme dvakrát vykonnější HW: jeden krok výpočtu = 0,5 s, 10 min odpovídá 1 200 krokům lineární algoritmus složitosti 3 · n: 10 min stačí na vykonání pro vstup velikosti 400 exponenciální algoritmus 2n: 10 min stačí na vykonání pro vstup velikosti 10 (211 = 2048) Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Algoritmy a datové struktury datová struktura: způsob uložení dat algoritmus: postup zpracování úzce propojené – datová struktura vynucuje algoritmus a obráceně ⇒ budeme mluvit o složitosti úkolu na konkrétní datové struktuře Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Datové struktury ukázkové příklady: pole a lineární spojový seznam operace: přístup k n-tému prvku, vložení prvku, odstranění n-tého prvku Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Indexování klíč – identifikátor záznamu (např. v relační databázi – „tabulce“), podle okolností jednoznačný či nikoli index – seřazená posloupnost hodnot pro jeden klíč, s ukazateli na záznam vybudování indexu ⇒ rychlé vyhledávání Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Pole (array) uložení n hodnot v souvislé paměťové oblasti indexování číslem (→ adresou v paměti) prostorová složitost: O(c · n), kde n je počet záznamů, c velikost jednoho záznamu (konstanta) přístup k n-tému prvku: O(1) (adresování v paměti) vložení prvku: O(n) (realokace) odstranění prvku: O(n) (realokace) Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Seznam (list) I uložení n hodnot v nesouvislé paměťové oblasti s každou hodnotou je asociovaný ukazatel na následníka prostorová složitost: O(c · n), kde n je počet záznamů, c velikost jednoho záznamu (konstanta) – ale: záznam zde musí obsahovat i ukazatel na následníka ⇒ vyšší paměťové nároky než pole přístup k n-tému prvku: O(n) (lineární průchod seznamem) vložení prvku: O(1) (přepojení ukazatelů) odstranění prvku: O(1) (přepojení ukazatelů) Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Seznam (list) II Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Shrnutí: pole vs. seznam pole: rychlejší přístup, pomalejší modifikace seznam: pomalejší přístup, rychlejší modifikace ⇒ vhodnost použití závisí na datech Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Hashování v předchozích příklade bylo indexem vždy číslo můžeme ovšem chtít indexovat např. řetězcem („ke každému slovu přiřaď četnost“) nutná transformace nečíselné hodnoty na číslo – vytvoření tzv. hashe pomocí hashovací funkce Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Hashovací funkce I h : D → N, kde D je doména dat; požadavky: rychlá deterministická (pro stejná data vždy stejný výsledek) uniformní (výstupní hodnoty mají přibližně stejnou pravděpodobnost, všechny mají stejnou velikost) výstup volitelné délky obtížná reverzibilita (použití: hesla) minimální změna vstupu vyvolá velkou změnu výstupu Hashovací funkci nazýváme perfektní, je-li její zúžení na konkrétních vstupních datech injektivní. Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Hashovací funkce II obecně je hashovací funkce vždy neinjektivní a vznikají kolize důlěžitý požadavek: neměnnost vstupních dat po vytvoření hashe (immutability) Python: list = [], dict = {} Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Fronta (queue, buffer) = datová struktura typu FIFO (First In First Out) implementace pomocí pole nebo spojového seznamu Python: list.append(), list.pop(0), ale pomalé (collections.deque)! př. použití: prohledávání stromu do šířky Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Zásobník (stack) = datová struktura typu LIFO (Last In First Out) implementace pomocí pole nebo spojového seznamu Python: list.append(), list.pop() př. použití: prohledávání stromu do hloubky Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Binární halda (binary heap) datová struktura pro rychlé získávání minima (duálně maxima) bez třídění operace: vložení prvku, získání minima, odebrání minima (všechny O(log(n))) http://en.wikipedia.org/wiki/Binary_heap Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Řadicí algoritmy mnoho různých algoritmů, zde pouze: bubblesort, quicksort, heapsort, mergesort složitost problému: O(n · log(n)) http://en.wikipedia.org/wiki/Sorting_algorithm Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Vyhledávání v korpusech – CQL Korpus: poziční atributy – slovo, lemma, značka, . . . struktury a strukturní atributy – dokument (autor, id, rok, . . . ), odstavec, věta vyhledávání: Manatee/Bonito/Sketch Engine http://corpora.fi.muni.cz http://the.sketchengine.co.uk Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Indexace korpusu v Manatee tvorba tzv. lexikonu ⇒ očíslování řetězců ⇒ operace nad čísly místo nad řetězci operace pro převod: řetězec (str) – číslo (id) – pozice (poss) lexikon: id2str, str2id invertovaný (reverzní) index: id2poss text korpusu: pos2id tranzitivně lze i pos2str, str2poss základní myšlenka: seřazené proudy pozic a jejich slévání Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Zipf’s law I Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Zipf’s law II may be simplified to inductive definition: Zipf’s law (simplified) frequency of the n-th element fn ≈ 1 n · f1 ⇒ frequency is inversely proportional to the rank according to frequency ⇒ one needs really large corpora to capture all the variety of many language phenomena Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Zipf’s law III Substantives + Verb tags on the Brown corpus Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Vyhodnocování CQL dotazu Příklad: [tag=”ADJ”] [(word=”record” | word=”process”) & tag=”NOUN”] within Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Today’s Corpora in SkE LARGE (= billions of tokens, and it’s going to be worse) complex multi-level multi-value annotation wide range of languages growing demand on complex searching – moving from morphology to syntax and semantics search API for automatic information retrieval and post-processing in particular applications needed Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza CQL = Corpus Query Language (Christ and Schulze, 1994) positions and positional attributes: [attr="value"] structures and structural attributes: query: [tag="N.*"]+ within and alternative meet/union query: (meet [lemma="take"] [tag="N.*"] -5 +5) (union (meet ...) (meet ...)) Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza CQL in Manatee/Bonito ehnancements and differences to the original CQL syntax within and containing meet/union (sub)query inequality comparisons frequency function Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza within/containing queries searching for particles: [tag="PR.*"] within [tag="V.*"] [tag="AT0"]? [tag="AJ0"]* [tag="(PR.?|N.*)"] [tag="PR.*"] within searching for a Czech idiom “hnout někomu žlučí” (“to get somebody’s goat”): word-by-word translated as: hnout “move” [V, infinitive] někomu “somebody” [N, dative] žlučí “bile” [N, instrumental]. containing [lemma="hnout"] containing [tag=".*c3.*"] containing [word="žlučí"] Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza within/containing queries structure boundaries: begin: , whole structure: , end: changes: within not allowed anymore, use within Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza meet/union queries combined with regular query: containing (meet [lemma="have"] [tag="P.*"] -5 5) containing (meet [tag="N.*"] [lemma="blue"]) changes: meet/union queries can be used on any position, they can contain labels and no MU keyword is required (and deprecated): (meet 1:[] 2:[]) & 1.tag = 2.tag Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Inequality comparisons former comparisons allowed only equality and its negation: [attr="value"] [attr!="value"] inequality comparisons implemented: [attr<="value"] [attr>="value"] [attr!<="value"] [attr!>="value"] intended usage: [tag="AJ.*"] [tag="NN.*"] within ="2009» sophisticated comparison performed on the attribute value: 10 Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Performance evaluation Tabulka: Query performance evaluation – corpora legend: ◦ BNC (110M tokens), • BiWeC (version with 9.5G tokens), ∗ Czes (1.2G tokens) query # of results time (m:s) ◦ [lemma="time"] 179,321 0.07 ◦ [lemma="t.*"] 14,660,881 3.12 ◦ Ex: particles 1,219,973 33.36 • Ex: particles 97,671,485 32:26.48 ∗ Ex: idioms 66 1:6.86 ◦ Ex: meet/union 3 8.47 • Ex: meet/union 1457 7:13.12 Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Rozhraní systému Manatee podrobnější dokumentace k CQL: http: //trac.sketchengine.co.uk/wiki/SkE/CorpusQuerying corpquery CORPUSNAME QUERY lsclex CORPUS ATTR lsslex CORPUS STRUCT ATTR Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Precision, recall for classification problems in NLP, the standard evaluation is by means of precision and recall precision = |test ∩ gold| |test| recall = |test ∩ gold| |gold| two numbers, we just want to have one – F-score F1 score = 2·precision·recall precision+recall Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza F-score also F-measure general form: Fβ score Fβ score = (1 + β2) · precision·recall (β2+precision)+recall special case of β = 1 corresponds to the harmonic mean of precision and recall β can be used for favouring precision over recall (for β < 1) or vice versa (for β > 1) Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Zkuste si Na korpusu DESAM a czes vyzkoušejte: hledat výskyty přechodníků (přítomných i minulých) hledat jmenné fráze s genitivní vazbou hledat věty obsahující reflexivní slovesa hledat výskyty svého oblíbeného idiomu hledat shodné jmenné fráze do délky 4 Termín: do 21. 4. 2014, do odevzdávárny vložte textový soubor s příslušnými dotazy v CQL Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Exploiting CQL for word sketches word sketch – one-page summary of word’s collocational behaviour building a distributional thesaurus on top of word sketches using association metrics (scores) for measurung collocability of words Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Word association scores I T-Score fAB − fAfB N√ fAB MI-Score log2 fABN fAfB Church and Hanks, Word Association Norms, Mutual Information, and Lexicography, in Computational Linguistics, 16(1):22-29, 1990 MI3-Score log2 f 3 ABN fAfB Oakes, Statistics for Corpus Linguistics, 1998 Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Word association scores II minimum sensitivity min( fAB fB , fAB fA ) Pedersen, Dependent Bigram Identification, in Proc. Fifteenth National Conference on Artificial Intelligence, 1998 MI.log-f (formerly called salience) MI-Score · ln(fAB + 1) Kilgariff, Rychly, Smrz, Tugwell, “The Sketch Engine” Proc. Euralex 2004. Dice 2 · fAB fA + fB Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Measuring IAA naïve approach: count how many times people agreed on problem: it does not account for agreement by chance Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Chance-corrected coefficients for IAA S (Benett, Alpert and Goldstein, 1954) π (Scott, 1955) κ (Cohen, 1960) (there is lot of terminology confusion, we follow Ron Artstein, Massimo Poesio: Inter-coder Agreement for Computational Linguistics, 2008) Ao – observed agreement Ae – expected (chance) agreement for all coefficients, they compute: S, π, κ = Ao − Ae 1 − Ae Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Chance-corrected coefficients for IAA S (Benett, Alpert and Goldstein, 1954) assumes that all categories and all annotators have uniform probability distribution π (Scott, 1955) assumes that different categories have different distributions shared across annotators κ (Cohen, 1960) assumes that different categories and different annotators have different distributions devised for 2 annotators, various modifications for more than 2 annotators available Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza sed, diff, comm sed – zkratka z „stream editor“ sed ’s/REGEX/NAHRADA/’ – provede náhradu regulárního výrazu REGEX za řetězec NAHRADA diff – zkratka z „difference“ diff SOUBOR1 SOUBOR2 – porovná soubory a vypíše nalezené rozdíly comm – zkratka z „compare“ comm -1 -2 -3 SOUBOR1 SOUBOR2 – vynechá řádky vyskytující se pouze v souboru 1 / 2 / obou (soubory musí být seřazené). ajka, majka, desamb Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Gramatika → PLIN004: G = (Σ, N, P, S) Chomského hierarchie, podle omezení na podobu pravidel (A, B ∈ N, a ∈ Σ, α, β ∈ (N ∪ Σ)∗): typ 3: regulární gramatika: A → a, A → aB, typ 2: bezkontextová gramatika: A → β, typ 1: kontextová gramatika: α → β, |α| ≤ |β|, typ 0: frázová gramatika: α → β. pojetí gramatiky coby generátoru – regulární gramatika generuje regulární jazyk (a obdobně pro ostatní typy) potřeba „protikusu“ ke generátoru (syntetizátoru) – analyzátor → GRAMATIKA – JAZYK – ANALYZÁTOR z PLIN004 již znáte: regulární gramatika – regulární jazyk (popsatelný regulárním výrazem) – konečný automat Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Gramatika a analyzátor s postupnou relaxací omezení na tvar pravidel roste vyjadřovací síla gramatiky („složitost“ generovatelného jazyka) pochopitelně s tím rostou i nároky na analyzátor, zejména časová složitost analýzy (n značí délku vstupního řetězce): regulární gramatika: O(n) – proč? bezkontextová gramatika: O(n3 ) kontextová gramatika: O(n6 ) komplexní gramatické formalismy, některé zahrnující i sémantiku (LFG, HPSG, TAG, CCG, . . . ) – viz IB030 Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Přirozené jazyky a gramatiky Jak složité jsou přirozené jazyky? Lze přímočaře uplatnit Chomského hierarchii? Co je úkolem syntaktického analyzátoru přirozeného jazyka? Jaké jsou důsledky teorie formálních jazyků pro syntaktickou analýzu přirozeného jazyka? Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Bezkontextová gramatika, zásobníkový automat bezkontextová gramatika = context-free grammar = CFG konečný automat = finite-state automaton = FSA zásobníkový automat = pushdown automaton = PDA podobně jako jazyk generovaný reg. gramatikou lze analyzovat FSA, můžeme jazyk generovaný CFG analyzovat pomocí PDA PDA: analýza shora dolů a zdola nahoru Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza ZPJ a teorie formálních jazyků skripta a slidy (s poděkováním) Shuly Wintner, University of Haifa: http://cs.haifa.ac.il/~shuly/teaching/09/ nlp/complexity-handout.pdf a ve studijních materiálech skripta Černá-Kučera-Křetínský – FI:IB005 Formální jazyky a automaty: http://is.muni.cz/elportal/estud/fi/js06/ ib005/Formalni_jazyky_a_automaty_I.pdf Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Nedeterministická bezkontextová analýza shora dolů (Lookup-Rewrite) na začátku analýzy obsahuje zásobník počáteční neterminál operace: Lookup (najdi shodný prefix zásobníku a vstupu; odmaž – „přečti“), Rewrite (přepiš vrchol zásobníku podle pravidla gramatiky – nahraď pravou stranou) nedeterminismus: vhodná volba pořadí operací Lookup-Rewrite úspěšná analýza: prázdný zásobník, vstup byl celý přečten zdola nahoru (Shift-Reduce) na začátku analýzy je zásobník prázdný operace: Shift (vlož do zásobníku další slovo ze vstupu), Reduce (přepiš vrchol zásobníku podle pravidla gramatiky – nahraď levou stranou) nedeterminismus: vhodná volba pořadí operací Shift-Reduce úspěšná analýza: zásobník obsahuje právě počáteční neterminál, vstup byl celý přečten Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Handling ambiguity Backtracking – try all options sequentially (usually degrades to factorial time complexity) Determinism – choose one option (preferably a good one) and keep to it Parallelism – try all options in parallel Underspecification – do not specify the ambiguous phenomenon Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Deterministická analýza CKY / CYK (zdola nahoru, vyžaduje CNF) Earleyho parser (shora dolů) GLR (Generalized Left-to-right Right-most derivation parser) (zdola nahoru) Chart parser (zdola nahoru / shora dolů / řízený hlavou) → IB030 Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza složková analýza (phrase structure analysis) závislostní analýza (dependency analysis) co je cílem syntaktické analýzy? metody vyhodnocování (LAA, Parseval) Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II Obsah Organizační pokyny Algoritmická složitost Datové struktury CQL Syntax a syntaktická analýza Příprava korpusu 1 Ujasnění obsahu korpusu (K čemu má sloužit? Jak získám vhodný text?) 2 Získání dat (Crawling, ne Google; wget, links) 3 Základní anotace (dokument, odstavce, specifické atributy) 4 Tokenizace (unitok.py, don’t, A4) 5 Segmentace do vět (tecky.pl, MUDr., atd.) 6 Morfologická anotace / desambiguace (ajka / majka / desamb) 7 Další specifická anotace (např. syntaktická) 8 Zakódování (Manatee / encodevert; Corpus Architect) Miloš Jakubíček NLP FI MU Brno PLIN015 Proseminář z počítačové lingvistiky II