Úvod Zpracování textů The Sketch Engine Výpočet thesauru kontextů ve velkých textových korpusech Informatické kolokvium Karel Pala Pavel Rychlý Centrum zpracování přirozeného jazyka 13. března, 2007 Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru Obsah □ Úvod B Zpracování textů El The Sketch Engine Q Výpočet thesauru Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru Co je to NLP? ■ NLP je zkratka pro "Natural Language Processing", ■ česky "(počítačové) zpracování přirozeného jazyka". ■ Který jazyk je přirozený? ■ přirozený jazyk je jazyk, který vznikl přirozeným vývojem a lidé ho používají k běžné komunikaci (čeština, angličtina, ...) ■ umělý/formálníjazyk je uměle navržený, explicitně definovaný jazyk, např. programovací jazyky, matematické formalismy, ... Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru Co znamená zpracovávat počítačově přirozený jazyk? ■ snažit se popsat formálně (formalizovane) přirozený jazyk tak, aby s ním bylo možné (alespoň do určité míry) strojově manipulovat, například: ■ automaticky analyzovat strukturu jazykových výrazů ■ překládat počítačem texty mezi různými jazyky ■ zachytit významy obsažené v textech, vyhledávat je ■ zlepšit různé aplikace znalostmi o jazyku (např. information retrieval, rozhraní k databázím/informačním systémům) ■ hlavní motivací je plnohodnotná (obousměrná) komunikace s počítačem v přirozeném jazyce (což je jedna z hlavních úloh v oblasti AI) Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru Motivace Použití velkých textových korpusů ■ korpusový manažer Manatee/Bonito ■ Sketch Engine ■ OUPwww.askoxford.com/oec ■ Manatee se užívá v ÚČNK, ÚJČ, SNK, Berlínské akademii, pro maďarský, slovinský, chorvatský, ruský korpus ■ učení se cizím jazykům Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru Jak se počítačově zpracovává přirozený jazyk? korpus - rozsáhlý soubor textů ■ umožňuje nám nahlédnout, jak se jazyk používá ■ lze na něm zkoumat různé pravidelnosti/zákonitosti (která slova se často používají spolu s jinými slovy atp.) statistické metody a strojové učení ■ máme-li dostatečně rozsáhlá ručně zpracovaná data, je možné v nich obsaženou "znalosť'/informaci použít pomocí metod statistiky a strojového učení na zpracování nových dat a mnoho dalšího ... Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru Velikost korpusu korpus - rozsáhlý soubor textů Co znamená rozsáhlý? první koprusy: 1 milion slov ■ příliš malé pro zajímavější výsledky ■ dostačující pro globální statistiky ■ délka věty/slova, nejčastější slova nyní běžně stovky milionů slov ■ průměrná rychlost čtení je 125-225 slov za minutu ■ 200 * 60 * 18 = 216000 slov za den (18 hodin) ■ ^> 79 milionů za rok (365 dní) ■ dost velká slovní zásoba pro větší jazyky jsou nyní dostupné giga-korpusy ■ více než miliarda slov ■ zhruba 50 let čtení při 4 hodinách denně ■ málokdo dokáže přečíst více Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru Mohou počítače porozumět volnému textu? v korpusech máme dostatek infomací zpracování informací na počítači: manipulace se symboly potřeba definovat různé úrovně elementů/symbolů m znak (UTF-8) ■ slovo (znaky mezi mezerami, oddělovači) ■ lemma (základní tvar) ■ význam Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru významy Slovo (a jeho některé části) jsou základními nositeli významu ■ slovo bez kontextu - žádný význam, mnoho potenciálních významů ■ stejné slovo v různých kontextech - různé významy ■ slovo v podobných kontextech - stejný význam ■ co to je kontext? Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru Co to je kontext? Kontext jsou slova v okolí klíčového slova. ■ Jaké okolí?: ■ následující slovo ■ předcházející slovo ■ okno, +1 až +5 ■ okno, -5 až -1 ■ Ne všechna slova v okolí jsou důležitá. ■ Jak určíme důležitost? ■ nejčastější kolokace - ale to je "tne" ■ (statisticky) nejvýznamnější-jaký vzorec? Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Uvod Zpracování textů The Sketch Engine Výpočet thesauru Word Sketch Jednostránkový souhrn chování slova' Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru Word Sketch Jak jej lze vytvořit ■ Velký vyvážený korpus ■ Vyhledáme závislé prvky (subjects, objects, heads, modifiers etc) ■ Seznam kolokací pro každou gramatickou relaci ■ Statistika pro třídění každého seznamu Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru The Sketch Engine ■ Vstup: ■ libovolný korpus, libovolný jazyk ■ lemmatizovaný, značkovaný ■ specifikace gramatických relací ■ Výstup: ■ Word sketches ■ Thesaurus ■ Dotazovací systém Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru Koeficient výnačnosti ■ počty výskytů {word^, gramrel, wordz) ■ AScore{w^ ,R,w2) = Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru Koeficient podobnosti ■ porovnání profilů slov w-\ a w2 ■ pouze důležité (význačné) kontexty ■ jaký je překryv ■ počty (word-\, (gramrel, word,)) a (word2, (gramrel, word,)) „. , , S(ŕup„ŕup,)e{ŕupWl ntupswA ASi + ASJ ~ (ASi ~ ASj)2/50 Sim(wA,w2) =-'--—2--j=- 2-> tup, e {tupWi u tupW2} M Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru Velikosti dat Velikosti kor pusů, jejich slovníků a počty slov v koni extech Korpus Velikost Slov Lemat Různé k. Všechny k. BNC SYN2000 OEC Itwac 111m 114m 1,12g 1,92g 776k 1,65m 3,67m 6,32m 722k 776k 3,12m 4,76m 23m 19m 84m 67m 63m 58m 569m 587m Velikosti slovníků i počty různých kontextů rostou sublineárně s velikostí korpusu. Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru Velikost matice ■ Podobnost všech dvojic lemmat ■ Matice velikosti N2, kde N je 700k- 5m ■ Počet prvků v řádech tera (1012) ■ Matice je naštěstí velice řídká ■ Většina hodnot je 0 nebo "skoro" 0 ■ Dokonce většina celých řádků/sloupců je prázdných Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru Praktické velikosti dat ■ Výpočet pouze pro slova s minimální četností ■ Lépe limitovat počty kontextů než prostých výskytů ■ Z kontextů brát pouze statisticky významné Korpus MIN Lemmat KWIC CTX BNC 1 152k 5.7m 608k BNC 20 68k 5.6m 588k OEC 2 269k 27.5m 994k OEC 20 128k 27.3m 981 k OEC 200 48k 26.7m 965k Itwac 20 137k 24.8m 1.1m Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Uvod Zpracování textů The Sketch Engine Výpočet thesauru Praktické velikosti dat Matice velikosti N2, kde N je 50k - 200k Počet prvků v řádech giga (1010) Hodnota každého prvku vznikne aplikací funkce podobnosti na vektory délky K = 500k - 1 m. Přímočarý algoritmus pro výpočet celé matice má časovou složitost 0(N2K). Složitost je polynomiální, ale algoritmus je prakticky nepoužitelný pro dané rozsahy hodnot. Odhadované doby výpočtu jsou v měsících až letech. Heuristiky snižují velikosti N a K na úkor přesnosti výsledných hodnot. Doba výpočtu je potom v řádech dnů s chybou 1-4%. Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru Efektivní algoritmus ■ I menší matice je velice řídká ■ Není potřeba počítat podobnost pro slova, která nemají nic společného, ■ tedy nemají žádný společný kontext. ■ Hlavní cyklus algoritmu tedy nevedeme přes slova, ale přes kontexty. Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru Efektivní algoritmus ■ Vstup: seznam všech možných slov v kontextech, (w, r, w'), s četnostmi výskytů v korpusu ■ Výstup: matice podobností slov sim{w^, w2) for (r, w') in CONTEXTS: WLIST = set of all w where (w, r, w') exists for wi in WLIST: for w2 in WLIST: sim(w-\, w2)+ = f {frequencies) Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru Optimalizace ■ Pokud | WLIST\ > 10000, daný kontext přeskočíme. ■ Matici sim(wi, w2) během výpočtu nedržíme celou v paměti. ■ Opakovaný běh hlavního cyklu pro omezený rozsah w*. ■ Místo sim(w-\, w2)+ = x generujeme na výstup (w-\, w2, x). m Výstupní seznam potom setřídíme a sčítáme jednotlivé x. m Využití TMMS (Two Phase Multi-way Merge Sort) s průběžným sčítáním. ■ Místo několika stovek GB třídíme jednotky GB. Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech Úvod Zpracování textů The Sketch Engine Výpočet thesauru Výsledky ■ Algoritmus je řádově rychlejší než přímočarý algoritmus. (18 dnů x 2 hodiny)_ Korpus MIN Lemmat KWIC CTX čas BNC 1 152k 5.7m 608k 13m 9s BNC 20 68k 5.6m 588k 9m 30s OEC 2 269k 27.5m 994k 1h 40m OEC 20 128k 27.3m 981 k 1h 27m OEC 200 48k 26.7m 965k 1h 10m Itwac 20 137k 24.8m 1.1m 1h 16m ■ Bez omezení přesnosti. ■ Možnost snadné paralelizace. Karel Pala, Pavel Rychlý Podobnost kontextů ve velkých textových korpusech