Strojové učení základem pro hybridní lemmatizační algoritmus

Rok / Year: 2012

Svazek / Volume: 14

Číslo / Issue: 5

Strojové učení základem pro hybridní lemmatizační algoritmus Machine learning as a cornerstone for hybrid lemmatization algorithm Jan Karásek, Ondřej Morský, Pavel Šanda, Radim Burget [email protected], [email protected], [email protected], [email protected] Fakulta elektrotechniky a komunikačních technologií VUT v Brně.

Abstrakt: Lemmatizace je jednou ze základních technik předzpracování textu. Hlavním účelem tohoto procesu je nalezení normalizované formy slova. V tomto článku bude představen lemmatizační algoritmus založený na lemmatizačních pravidlech naučených pomocí Ripple-Down Rules patřících mezi techniky strojového učení. Výhodou tohoto přístupu je, že nevyžaduje znalost morfologie českého jazyka. Dále jsou představeny metody řešící lemmatizaci výjimek a specifických typů slov, které dokážou zvýšit přesnost lemmatizace českého jazyka. V závěru článku jsou diskutovány dosažené výsledky a další potenciální rozšíření, která by pomohla úspěšnost navrženého lemmatizátoru dále zvyšovat. Je také uvedeno srovnání dosažených výsledků s již existujícím systémem LemmaGen pro lemmatizaci českého jazyka, založeném na stejném principu strojového učení, stejně tak jako srovnání se systémy využívajícími morfologickou analýzu a desambiguaci.

Abstract: Lemmatization is one of the basic techniques of text preprocessing. The main purpose of this process is to find a standard form of words. In this article will be presented a lemmatization algorithm based on rules learned by Ripple-Down Rules technique belonging to the machine learning techniques. The advantage of this approach is that it does not require knowledge of the morphology of the Czech language. In addition, methods presented in this article are dealing with exceptions in lemmatization which can increase the accuracy lemmatization of Czech language. In conclusion, the article discusses the achievements and further potential extensions that would help improve the accuracy of algorithm. At the end of the article is also presented a comparison of the results obtained by the existing system LemmaGen, based on the same principle of machine learning, as well as compared to systems that use morphological analysis and disambiguation.

2012/57 – 7. 9. 2012

Strojové učení základem pro hybridní lemmatizační algoritmus Jan Karásek , Pavel Šanda , Radim Burget , Ondřej Morský Fakulta elektrotechniky a komunikačních technologií VUT v Brně Email: {karasek.jan, ondrej.morsky}@phd.feec.vutbr.cz, [email protected], [email protected]

Abstrakt – Lemmatizace je jednou ze základních technik předzpracování textu. Hlavním účelem tohoto procesu je nalezení normalizované formy slova. V tomto článku bude představen lemmatizační algoritmus založený na lemmatizačních pravidlech naučených pomocí Ripple-Down Rules patřících mezi techniky strojového učení. Výhodou tohoto přístupu je, že nevyžaduje znalost morfologie českého jazyka. Dále jsou představeny metody řešící lemmatizaci výjimek a specifických typů slov, které dokážou zvýšit přesnost lemmatizace českého jazyka. V závěru článku jsou diskutovány dosažené výsledky a další potenciální rozšíření, která by pomohla úspěšnost navrženého lemmatizátoru dále zvyšovat. Je také uvedeno srovnání dosažených výsledků s již existujícím systémem LemmaGen pro lemmatizaci českého jazyka, založeném na stejném principu strojového učení, stejně tak jako srovnání se systémy využívajícími morfologickou analýzu a desambiguaci.

1 Úvod Lemmatizace je proces hledání normalizované formy slova. Jde o jednu ze základních metod předzpracování textu, která je využívána při procesu dolování znalostí z textových dat v mnoha aplikačních oblastech, jako je např. vyhledávání informací (information extraction), vyhledávání v textu (information retrieval) nebo klasifikace textů (natural language processing) atd. Termín lemmatizace se často vzájemně zaměňuje s termínem stemming. Lemmatizace, jak již bylo řečeno, hledá normalizovanou formu slova (lemma), kdežto během stemmingu jde o nalezení kořenu slova (stem). Výsledný stem však nemusí být zcela shodný s morfologickým kořenem slova (není zaručeno jeho nalezení). V takovém případě by měla být výsledkem alespoň nejdelší společná část. [1] Proces lemmatizace je v dnešní době pro český jazyk již téměř vyřešen. Klíčové poznámky pro řešení této problematiky jsou popsány v literatuře [2, 3]. R. Sedláček již v roce 1999 publikoval jako svou diplomovou práci morfologický analyzátor českého jazyka – AIKA [4], jehož nedílnou součástí je i lemmatizátor. Ve zmiňovaných publikacích [2, 3] jde o morfologickou analýzu, kdežto v tomto článku se zabýváme návrhem jednoduchého lemmatizačního algoritmu založeného na strojovém učení – tedy bez nutné znalosti morfologie lemmatizovaného jazyka. Navržený systém založený na automatickém trénování pravidel je později rozšiřován o zpracování výjimek, které se v českém jazyce vyskytují. Systém AIKA [4] i systém pro morfologickou analýzu vyvíjený na Ústavu formální a aplikované lingvistiky při Univerzitě Karlově [5] (pro tento systém bude dále v textu použita zkratka UFAL) jsou zatíženy licenčními podmínkami, které jsou pro projekt, v rámci kterého je popisovaný lemmatizační

algoritmus vyvíjen (MPO reg. č. FR-TI4/151), nevhodné, na internetu jsou volně dostupné pouze demo verze, a proto vyvstala potřeba vlastního algoritmu. Navíc, pro snadné začlenění lemmatizátoru do vyvíjeného systému bude ideální, když bude algoritmus implementován v programovacím jazyce JAVA, čemuž neodpovídá systém LemmaGen (C#), ze kterého vycházíme, ani systém AIKA (C). Automatická morfologická analýza a syntéza jsou východiskem automatické lemmatizace systému [4, 5]. Algoritmus pro automatickou morfologickou analýzu češtiny se snaží simulovat systém české flexe – ohýbání slov. Algoritmus lemmatizace představený v tomto článku využívá vlastních automaticky naučených pravidel. Všechny systémy lze v podstatě zařadit do kategorie hybridních algoritmů, jelikož pracují částečně na principu zpracování předpon/přípon a částečně na principu hrubé síly, která využívá několik tabulek pro vyhledávání klíčových slov. V případě [4, 5] je analyzovanému tvaru během morfologické analýzy přiřazen gramatický význam (slovní druh), vzor atd. Lemmatizační algoritmus navržený v tomto článku se takovouto analýzou nezabývá a jeho výstupem je prostý normalizovaný tvar zadaného slova (textu). Problémem systémů založených na vyhledávání v tabulkách může být paměťová náročnost, jelikož je třeba udržovat několik velmi rozsáhlých tabulek, např. se slovními kořeny, slovními koncovkami, intersegmenty atd. Úspěšně naučený algoritmus na základě strojového učení takovými problémy zatížen nebude, jelikož si žádné rozsáhlé datové struktury v paměti udržovat nebude a text bude zpracováván primárně na základě naučených pravidel. Pouze jako sekundární zpracování bude systém využívat několik tabulek, které budou ošetřovat výjimky. Článek si neklade za cíl provést podrobnou morfologickou analýzu textu, ale představit jednoduchý a relativně nenáročný algoritmus, který dokáže s vysokou přesností převést slovo do normalizované formy a připravit je tak k dalšímu zpracování. Hlavním přínosem článku je tedy představit algoritmus založený na technice strojového učení a dále představit metody pro zdokonalení procesu lemmatizace českého jazyka a celkově podat čtenáři bližší informace o této technice předzpracování textu. Nový lemmatizátor [6] českého jazyka s pracovním názvem Lemming, včetně metod zvyšujících úspěšnost procesu lemmatizace, byl implementován na základě tzv. RippleDown Rules (RDR) pravidel spadajících mezi techniky strojového učení vytrénovaných pomocí existujícího a relativně úspěšného lemmatizátoru LemmaGen [7]. Tato automaticky sestavená pravidla musela být manuálně upravena a vyčištěna, jelikož obsahovala přetrénované vzorky pravidel. Algoritmus byl následně doplněn o další metody zpřesňující výsledky lemmatizace nepravidelných slov a různých výjimek a jeho výstup je tak lépe připraven pro další zpracování.

57 – 1

VOL.14, NO.5, OCTOBER 2012

2012/57 – 7. 9. 2012 Článek je rozdělen do kapitol následovně. Druhá kapitola poskytuje přehled algoritmů, na jejichž základě funguje prakticky každý, v současné době používaný, stemmer či lemmatizátor textu. Ve třetí kapitole jsou popsány specifické požadavky, které musí lemmatizátor českého jazyka splňovat. Ve čtvrté kapitole je popsán učící se proces a samotný lemmatizační systém LemmaGen, ze kterého v dalším textu vycházíme. V páté kapitole jsou rozepsány metody zvyšující úspěšnost lemmatizace českého jazyka a implementace nově navrženého lemmatizátoru. V šesté kapitole jsou popsány dosažené výsledky a je provedeno srovnání obou lemmatizátorů založených na strojovém učení, stejně jako srovnání se systémy [4, 5] založenými na morfologické analýze. V sedmé, závěrečné kapitole, jsou zhodnoceny dosažené výsledky a diskutovány možnosti dalšího rozšíření lemmatizátoru.

2 Algoritmy pro stemming a lemmatizaci Základem každého algoritmu jsou vstupní data. Tato data mohou být buď ve tvaru přesně definovaném značkami (strukturovaná data, např. XML), může jít o běžné textové dokumenty nejrůznějších formátů (semi-strukturovaná data, např. DOCX, RTF, ODT), nebo o prostý text, který reprezentuje většina článků na internetu (nestrukturovaná data). Jelikož nestrukturovaného textu je v současné době drtivá většina, což pro jeho další zpracování není ideální, je třeba tento text nějakým způsobem dalším algoritmům předzpracovat.

textu vhodného pro další zpracování. Pro stemming a lemmatizaci se používá několik typů algoritmů, jejichž přehled je sepsán v následujících podkapitolách. 2.1 Algoritmy využívající hrubou sílu/slovník Algoritmy hrubé síly (brute-force algorithms) pracují na principu prohledávání slovníku (představuje ji tabulka či jiná vhodněji definovaná datová struktura např. trie). Slovník obsahuje relace mezi kořenem slova/základním tvarem a skloňovanými výrazy, tedy různými tvary slova odvozenými od jeho kořene slova = stem (v případě stemmingu) či normalizované formy slova = lemma (v případě lemmatizace). Nevýhodou tohoto přístupu je, že algoritmus potřebuje pro správnou funkci obrovské množství záznamů ve slovníku. Musí obsahovat pro každé slovo všechny možné tvary, což je prakticky nemožné, jelikož jazyk se neustále vyvíjí a vznikají stále nová a nová slova. Tuto metodu však lze s výhodou kombinovat s jinými algoritmy, kde bude v tabulce uložen tvar např. pouze pro nepravidelná slova a pro slova, pro jejichž tvoření platí určitá pravidla, bude použit nějaký algoritmus. 2.2 Algoritmy zpracovávající přípony Algoritmy zpracovávající přípony slov (tzv. suffix-stripping algorithms) pracují na principu sady pravidel, podle kterých se řídí a vytvářejí požadovaný výsledek. Základní myšlenka je velice jednoduchá, jde pouze o odstraňování přípon na základě lingvistických a morfologických znalostí daného jazyka. Bohužel, selhávají v případě nepravidelného tvoření slov. Mezi nejznámější zástupce této skupiny patří algoritmus Lovinsové [8] a Porterův algoritmus [9]. Jak tyto algoritmy pracují, překračuje rámec rozsahu tohoto článku. Bližší informace lze najít v literatuře [6, 8, 9]. 2.3 Lemmatizační algoritmy Většina lemmatizačních algoritmů pracuje na principu určení slovního druhu a následném použití sady pravidel odpovídající danému slovnímu druhu. Algoritmy vycházejí z algoritmů zpracovávajících přípony slova, navíc se pouze snaží nejprve určit slovní druh, který napomůže přesnější aplikaci pravidel [10]. 2.4 Stochastické algoritmy

Obrázek 1: Průběh zpracování textu. Na Obrázku 1 je znázorněn obecný diagram průběhu zpracování textu. Vstupem je nestrukturovaný text, který je podroben tokenizaci – tedy rozdělení textu na jednotlivé elementy (odstavce, věty, slova), dále následuje volitelné předzpracování, jako je úprava mezer, odstranění stop slov – což jsou slova s minimální nebo žádnou informací (např. spojky, předložky atd.) a odstranění interpunkčních znamének. Dále může následovat kontrola pravopisu/překlepů, nahrazení synonym jedním společným či rovnou nadřazeným slovem (např. může být použita lexikální databáze jako je WordNET), následuje stemming /lemmatizace a nakonec vytvoření strukturovaného

Stochastické algoritmy používají k určení stemu/lemmatu pravděpodobnost. Patří mezi tzv. učící se algoritmy. Jako trénovací množinu používají tabulku skloňovaných slov a jim odpovídajících stemů/lemmatů, ze kterých si vylepšují pravděpodobnostní tabulku v případě správného určení slova. Při hledání stemu/lemmatu je tabulce předloženo slovo, na jehož základě se vybere nejpravděpodobnější kořen slova [10]. 2.5 Hybridní algoritmy Hybridní algoritmy kombinují výše uvedené způsoby, např. obsahují tabulku pro slova nepravidelná a na ostatní slova se snaží aplikovat algoritmy zpracovávající přípony.

57 – 2

VOL.14, NO.5, OCTOBER 2012

2012/57 – 7. 9. 2012

3 Specifika českého jazyka

Tabulka 1: Koncovky spisovné češtiny a dialektů.

Specifika popsaná v této sekci mohou s mírnými úpravami platit i pro ostatní slovanské jazyky, jelikož s většinou z nich sdílí čeština silný gramatický základ. Morfologie (tvarosloví) češtiny spadá do skupiny flektivních jazyků. To znamená, že základním principem gramatické funkce je ohýbání (flexe) – pod tímto termínem si lze představit skloňování, časování a užití přípon a předpon. V češtině existuje deset slovních druhů, pro názornost jsou morfologicky rozděleny na obrázku 2. Prvních šest druhů je nositeli hlavní informace, ostatní mají význam pouze doplňující. Slovní druhy lze dále rozdělit na ohebné a neohebné. Ohebné lze dále dělit na skloňované a časované. Neohebné slovní druhy nenesou žádnou nebo jen minimální informaci a bývají při zpracování textu odstraněny.

Obrázek 2: Morfologické rozdělení slovních druhů. Normalizovanou formou slova, nebo též jeho základním tvarem (lemmatem), je u podstatných jmen první pád jednotného čísla, u přídavných jmen první pád jednotného čísla základního (prvního) stupně mužského rodu a podobně je tomu i u zájmen a číslovek. U sloves je lemmatem tvar slova v infinitivu a u příslovcí je lemmatem pozitiv, stejně jako u přídavných jmen. Ostatní slovní druhy patří mezi slovní druhy s minimálním významem a při zpracování textu nebývají uvažovány, nebo jsou z textu úplně odstraněny. V češtině, stejně jako v ostatních jazycích, existují nejrůznější nářečí, slangové výrazy, vulgarismy a také nespisovná slova. Se všemi těmito výrazy je nutné se při zpracování textu vypořádat [1, 6]. V tabulce 1 jsou pro ilustraci uvedeny alespoň dva nejrozsáhlejší dialekty na území České republiky, český a moravský. Na základě této tabulky je možné vytvořit buď speciální pravidla, nebo zavést tabulku výjimek.

Český dialekt

Moravský dialekt

koncovka

dialekt

koncovka

dialekt

ý

ej

ý

é

é

ý/í

é

ý/í

ú

ou

ú

ó

ó

ú

ó

ú

4 LemmaGen a Ripple-Down Rules Lemmatizační systém LemmaGen obsahuje v době psaní tohoto článku asi nejpropracovanější soubor pravidel pro lemmatizaci českého jazyka, která nejsou vytvořena na základě morfologické analýzy. Byť u některých pravidel došlo k přetrénování a některá slova nejsou převedena do úplně správné podoby, jedná se o velmi dobrou startovní pozici pro vývoj nového lemmatizátoru bez dokonalé jazykové znalosti. Učení pravidel v tomto systému je založeno na principu tzv. Ripple-Down Rules (RDR) [11, 12]. Ripple-Down Rules byla poprvé představena na konci osmdesátých let minulého století [13]. V dnešní době existuje mnoho různých typů RDR, všechny však mají společnou strukturu podobnou rozhodovacím stromům. Vytvoření těchto pravidel je založeno na automatickém procesu získávání znalostí (knowledge acquisition) z trenovacích dat. Idea tohoto přístupu tkví v postupném přidávání pravidel pro rozhodování do systému. Tato pravidla říkají, jakým způsobem se mají nahrazovat písmena braná od konce ohnutých slov, aby vznikla požadovaná lemmata. Vždy, když je k dispozici nový vzorek (pár: slovo, lemma), je vytvořeno nové rozhodovací pravidlo a přidáno do seznamu stávajících pravidel. Tímto způsobem však může vzniknout kolize, kdy starší pravidlo může tomu nově naučenému odporovat. Proto jsou přidávány výjimky do již původních pravidel. RDR pravidla ve své podstatě představují konstrukci známé podmínky IF-THEN-ELSE, doplněnou o větev EXCEPT (výjimku). Pravidla pak formují stromovou strukturu pro rozhodování. Kostra takového pravidla je znázorněna na obrázku 3. Proces učení RDR lze vysvětlit následovně: Pokud je pravidlo moc obecné, je konkretizováno přidáváním výjimek – větev EXCEPT. Pokud je pravidlo moc konkrétní, je zobecňováno přidáním alternativy – větev ELSE.

57 – 3

IF ___C1___ THEN ___R1____ EXCEPT IF ___C3___ THEN ___R3___ EXCEPT IF ___C4___ THEN ___R4___ ELSE IF ___C2___ THEN ___R2___ Obrázek 3: Příklad Ripple-Down Rules.

VOL.14, NO.5, OCTOBER 2012

2012/57 – 7. 9. 2012 Pravidla a jejich výjimky jsou hierarchicky uspořádány ve stromu a první pravidlo, které je i se všemi výjimkami splněno, aplikuje na slovo požadovanou změnu. Příklad takového pravidla pro lemmatizaci českého jazyka je uveden na obrázku 4. Představme si případ, kdy ve stromu nejvyšší pravidlo v hierarchii IF-THEN zjišťuje pouze poslední písmeno slova, např. pokud končí na „a“. Tedy IF „a“ a dále nevyhovuje žádná výjimka ve větvích EXCEPT, větev THEN říká, že se neprovede nic „“ → „“. Ve větvi THEN je v tuto chvíli pravidlo, že „“ (nic, prázdný řetězec) → (se změní) na „“ (opět nic, prázdný řetězec). Ovšem vezměme v úvahu např. slovo „chleba“ – 2. pád, čísla jednotného, rod mužský. V tomto případě je splněna první výjimka, kde vyhovuje zakončení na „ba“. Zanořujeme se tedy hlouběji do hierarchie stromu a odebíráme stále více písmen z konce slova. I pro tohle pravidlo je splněna další výjimka, a to IF „leba“ (konec slova se rovná „leba“) THEN „eba“ → „éb“ (změň konec slova roven řetězci „eba“ na „éb“ a z chleba dostaneme lemma „chléb“). Každé IF-THEN pravidlo je rozšířeno o výjimky, podle kterých se nakonec vyhledá správné pravidlo, které má být na daný konec slova použito. Jak je z obrázku 4 patrné, je možné narazit i na speciální znak #, který může být v podmínce obsažen. Tento speciální znak indikuje, že slovo po lemmatizaci musí být shodné se slovem v podmínce (po odstranění onoho speciálního znaku #), aby byla tato podmínka splněna. Původní učící se algoritmus těchto pravidel je popsán v [11, 12]. Tento přístup byl postupem času zdokonalován a konkrétní metody a postupy jsou více popsány v [14, 15].

5 Návrh nového lemmatizátoru V této sekci bude popsán návrh nového lemmatizátoru Lemming založeného na pravidlech naučených pomocí systému RDR lemmatizátorem LemmaGen. Schéma navrženého lemmatizátoru je zobrazeno na obrázku 5. Po předání vstupního textu algoritmu je nejprve standardně provedena tokenizace na úroveň jednotlivých slov. Dále každý token prochází procesem předzpracování, který jej upraví do žádoucí podoby, nebo jej v některých případech úplně odstraní. Nejprve jsou odstraněny nadbytečné mezery v textu, dále je možné volitelně odstranit interpunkci a slova s minimálním významem, tzv. stop slova. Seznam interpunkčních znamének, která jsou v současné verzi odstraňována, je vidět v Příloze A. Seznam stop slov je uveden v Příloze B.

V případě lemmatizace probíhá trénování následovně: 

Trénovací data jsou v párech (slovo, lemma)



Podmínka v pravidlech představuje konec slova (konec slova chápeme jako několik písmen od konce)



Pokud je podmínka splněna, v závislosti na všech výjimkách, je aplikováno pravidlo měnící daný konec slova, čímž je vytvořena výsledná lemma.

IF „a“ THEN „“ -> „“ { Obrázek 5: Průběh zpracování textu.

EXCEPT IF „ba“ THEN „“ -> „“ { EXCEPT IF „leba“ THEN „eba“ -> „éb“ EXCEPT IF „#alba“ THEN „a“ -> „um“ EXCEPT IF „umba“ THEN „a“ -> „us“ EXCEPT IF „kuba“ THEN „a“ -> „“ } } Obrázek 4: Příklad pravidla pro lemmatizaci.

Dalším blokem v lemmatizátoru je algoritmus pracující na principu hrubé síly. Tento algoritmus byl implementován, jelikož se v českém jazyce vyskytují jisté nepravidelnosti, které není možné ošetřit obecnějšími pravidly pro změnu konce slov. Typickým příkladem, který tento algoritmus zpracovává, je slovo „jsem“, tedy v základním tvaru „být“. Mezi další nepravidelnosti patří např. přídavná jména či příslovce v různých stupních, např. slova „dobrý“ – „lepší“ – „nejlepší“, které mají společné lemma „dobrý“. Podobně je tomu u zmiňovaných příslovcí. Výstupní tokeny z předzpracování jsou tedy poslány nejprve do algoritmu hrubé síly, kde jsou hledány shody. Pokud se některá slova z původního textu shodují s výskyty v tabulce algoritmu, jsou nahrazena. Pokud

57 – 4

VOL.14, NO.5, OCTOBER 2012

2012/57 – 7. 9. 2012 není shoda nalezena, pokračuje se dalším blokem, kterým je algoritmus zpracovávající konce slov pomocí naučených pravidel vytrénovaných systémem LemmaGen. Jelikož tato pravidla byla přetrénována, bylo nutné je manuálně projít a vyčistit. Toto čištění bylo provedeno následovně. Byla vytvořena trénovací množina dat, ke které byl expertem vytvořen výsledek, který by poskytl ideální lemmatizátor. Tam, kde pravidlo selhalo, byla zjištěna příčina selhání a toto pravidlo bylo opraveno, odstraněno, nebo doplněno o další výjimku. V tomto stádiu je již vytvořen hybridní algoritmus pro lemmatizaci. Následuje však ještě popis několika dalších metod, které jsme při lemmatizaci testovali. Některé z těchto metod byly pouze otestovány, ale díky svým výpočetním nárokům zatím nebyly implementovány natrvalo. Některé metody však vyhovovaly i výpočetním nárokům (převod v reálném čase) a byly tak implementovány jako součást hybridního lemmatizačního algoritmu. Jelikož algoritmus zpracovávající slova na principu naučených pravidel pracuje pouze se slovy kompletně zapsanými malými písmeny, je vhodné dávat během lemmatizace pozor na to, kde se původně vyskytovala písmena velká, která mohou reprezentovat začátek věty, názvy, jména, zkratky apod. Pokud se vyskytne na vstupu lemmatizátoru takovéto slovo, je mu nastaven příznak, zda je počáteční písmeno velké, či zda jsou všechna písmena velká, a podle toho se po lemmatizaci vrátí tato písmena do původní podoby. První metodou zpřesňující lemmatizaci je detekce zkratek. Zkratky jsou jedinečné kombinace písmen a není na ně možné použít klasická pravidla pro změnu konce slova. Zkratky ze všech oblastí českého jazyka přesahují počet 11 tisíc. Nejprve byl tedy vytvořen seznam všech zkratek. Díky tak obrovskému počtu byl proces lemmatizace výrazně zpomalen. Proto bylo s výhodou využito faktu, že se většina zkratek zapisuje velkými písmeny, např. VUT (Vysoké učení technické). Na základě tohoto faktu jsou všechna slova psaná velkými písmeny z procesu lemmatizace vynechána. Existují ovšem i zkratky psané malými písmeny, např. „prof“ (profesor), jejich počet se pohybuje kolem 2,5 tisíc. Pro tyto zkratky byl tedy vytvořen nový seznam, který již aplikaci výpočetně tolik nezatěžuje a je akceptovatelný pro implementaci. Tímto je zajištěno, že zkratka zůstane v původním stavu a nejsou na ni dále aplikována lemmatizační pravidla pro změnu konce slova. Komplikací jsou však slova, kde je každé písmeno jinak velké, např. slovo DDoS (Distributed Denial-of-Service attack), taková slova jsou v současné době ignorována, do budoucna by mohla být ošetřena podobnou tabulkou jako nepravidelné tvary slov. Další metodou zvyšující přesnost lemmatizátoru je zpracování prefixů. Nejčastějšími předponami v českém jazyce je negativní prefix „NE“ a superlativní prefix „NEJ“. Dalším je futurální slovesný prefix „PO“, který ale nepovažujeme za tolik frekventovaný oproti dvěma předchozím, a tak je prozatím ponechán pouze lemmatizaci pomocí naučených pravidel. Jako příklad, proč byla zavedena tato výjimka, lze uvést slovo „nebyl“, kdy může dojít buď k úplnému odstranění části slova „ebyl“ a bude vráceno „n“, nebo může dokonce dojít ke změně významu a bude vráceno „byl“. Abychom předešli takovýmto případům, je vždy před zpracováním slova algoritmem zjištěno, zda slovo nezačíná jednou z těchto předpon. V případě, že dané slovo předponu obsahuje, nedojde k jejímu odstranění, aby nedošlo ke změně významu. Implementačně jde zase o

nastavení příznaku, zda slovo předponu obsahuje, následně je provedena změna konce slova a poté je slovu vrácena jeho původní předpona, aby nedošlo ke změně významu. U těchto slov však existuje ještě další výjimka. A to, že se v případě „NE“ či „NEJ“ na začátku slova nejedná o předponu, ale o přímou součást slova. Došlo-li by k jejímu odstranění, je slovo znehodnoceno natolik, že již nebude možné provést ani korektní změnu konce slova. Příklady takového slova jsou např. „nebesa“, „nehet“, „nevěsta“, „nejapný“ atd. Pro takováto slova byly vytvořeny dvě tabulky výjimek, které jsou prohledávány, má-li být takovéto slovo zpracováno. Problémem při lemmatizaci je také zcela jistě lemmatizace jmen a příjmení, která musí být převedena do 1. pádu čísla jednotného, ale rod by měl zůstat zachován, aby bylo jasné, o jaké pohlaví se jedná, např. pro další zpracování textu, kde může být znalost pohlaví důležitá. Tato problematika v současných pravidlech není ošetřena vůbec, a jak pro mužská, tak ženská jména dochází k převedení většinou na nesmyslný výsledek. U příjmení je problematika ještě složitější, protože česká příjmení jsou velmi rozmanitá a neustále se vyvíjejí a vznikají nová. Jako nejlepší řešení tohoto problému se jeví použití programu Ispell [16], který slouží ke kontrole pravopisu. Pracuje na principu generování všech možných tvarů daného slova dle určitých příznaků a následném porovnání se slovem zpracovávaným (příznaky určují, jaké tvary daného slova se budou generovat). Toto východisko je velice účinné, protože jsou obsaženy všechny možné tvary daného jména (příjmení). Více o této problematice a její implementaci do nového lemmatizátoru je možné nalézt v [6]. Jelikož však čeština obsahuje tisíce jmen a příjmení, a ve všech tvarech se jedná o statisíce či milióny záznamů, má tato implementace velmi negativní vliv na výkon lemmatizátoru, co se časového zpracování týká. Nakonec byla tedy tato metoda z poslední verze lemmatizátoru odstraněna. Dalším problémem lemmatizace jsou mnohoznačná slova. Jde o to, že v českém jazyce existuje určitý seznam slov, u kterých není zcela jednoznačný jejich základní tvar. Jako příklad uveďme slovo „jí“. V tomto případě se může jednat buď o tvar zájmena „ona“, nebo tvar slovesa „jíst“. Při čtení textu člověk snadno pozná podle kontextu, o jaký slovní druh se jedná, a tím pádem bez problému dokáže určit lemma tohoto slova. V případě strojového zpracování pomocí lemmatizátoru není správný postup jednoduché rozpoznat. Tuto problematiku řeší tzv. morfologická desambiguace [17]. Princip morfologické desambiguace je založen na existenci vztahu mezi správným gramatickým významem vztahu aktuálně zpracovávaného slova a gramatickými významy slov v kontextu. Z tohoto kontextu je možné určit, jaký základní tvar slova je správný. Tato problematika byla během vývoje lemmatizátoru konzultována s předními odborníky z Ústavu pro jazyk český, Filozofické fakulty Univerzity Karlovy a Fakulty informatiky Masarykovy Univerzity. Jelikož takovýto morfologický desambiguátor nemáme k dispozici a jeho vytvoření by vydalo na sepsání disertační práce, rozhodli jsme se takováto mnohoznačná slova pouze opticky zvýraznit v lemmatizovaném textu a dále je nezpracovávat. Těmto slovům byl na obě strany pro zvýraznění umístěn znak *, výstupem je tedy např. *jí*. Nakonec byl také vytvořen i seznam takovýchto slov, která dalšímu zpracování lemmatizátoru nepodléhají.

57 – 5

VOL.14, NO.5, OCTOBER 2012

2012/57 – 7. 9. 2012

6 Výsledky lemmatizace a vyhodnocení Testování a srovnávání lemmatizačních systémů probíhalo v několika krocích. V prvním kroku byla otestována vybraná slova spadající do kategorie nepravidelných slov nebo slov obsahujících předpony „PO“, „NE“ a „NEJ“. Ve druhém kroku byly vyhodnoceny dva referenční texty. První text neobsahoval jména, příjmení, názvy a mnohoznačná slova. Druhý text takováto slova obsahoval. Ve třetím kroku byla vytvořena testovací sada obsahující 1000 slov. Tato sada byla vytvořena z různých odstavců článku internetových novin. Posledním testem je otestování procentuální úspěšnosti navrženého systému Lemming na testovací sadě o velikosti 100 odstavců ze 100 různě tematicky laděných článků zpravodajských serverů, volně dostupných na internetu. Ke každému takovému textu byl manuálně vytvořen text, který představuje onen text převedený expertem (ideálním lemmatizátorem). V součtu obsahuje tato testovací data přibližně sto šest tisíc slov. Tomuto testu byl nakonec podroben pouze nově navržený lemmatizační systém, jelikož všechny ostatní systémy jsou dostupné jen v demo verzi a neumožňují manipulaci s takto velkým množstvím dat. 6.1 Lemmatizace speciálních slov V této sekci je uveden příklad lemmatizace speciálních slov, která nemají pravidelný tvar, nebo se jinak vymykají běžné lemmatizaci, např. protože obsahují předponu či začátek slova pouze jako předpona vypadá, ale je jeho přímou součástí. Tabulka 2: Testovací slova a slova s předponou „PO“. syst./slovo

běžme

zlomme

popojedou

poznáváme

Lemming

běžet

zlomit

popojet

poznávat

LemmaGen

běžit

zlomme

popojet

poznávat

AIKA

běžet

zlomit

popojet

poznávat

UFAL

běžet

zlomit

popojet

poznávat

Tabulka 3: Testovací slova a slova s předponou „NE“. syst./slovo

ševce

cti

neonem

nekolidující

Lemming

švec

ctít

neon

nekolidující

LemmaGen

švec

čest

on

kolidující

AIKA

švec

čest

neon

nekolidující

UFAL

švec

čest

neon

nekolidující

Tabulka 4: Testovací slova s předponou „NE“ a „NEJ“. syst./slovo

nejednotní

nejlepší

nejnebezpečnější

Lemming

nejednotný

dobrý

nebezpečný

LemmaGen

jednotný

dobrý

bezpečný

AIKA

nejednotný

dobrý

nebezpečný

UFAL

jednotný

dobrý

bezpečný

Vyhodnocení Jak je vidět z tabulek 2 – 4, systém Lemming si se všemi náhodně vybranými slovy poradil. Je také vidět, že předčí systém LemmaGen, ze kterého původem vychází. Systémy AIKA a UFAL si vedly taktéž výborně. Systém UFAL v některých případech správně neurčil slova s předponou „NE“ a v některých ano. Pro např. mnohoznačné slovo „cti“ našel systém Lemming lemma „ctít“ (sloveso) a ostatní systémy podstatné jméno „čest“. Jelikož jde o lemmatizaci slov a není zde žádný kontext, obě vrácená slova jsou správná. 6.2 Text bez jmen, příjmení, názvů a mnohoznačných slov V této sekci je lemmatizován krátký jednoduchý odstavec, neobsahující jména, příjmení, názvy a mnohoznačná slova, všemi dostupnými lemmatizátory. Odstavec obsahuje 66 slov. Výsledek procentuální úspěšnosti jsme získali jako počet správně určených slov k celkovému počtu slov. Původní text k lemmatizaci Žraloci liščí často vplouvají do míst obývaných rybkami, které jejich tělo ochotně zbaví odumřelé kůže a parazitů. Frekvence, s jakou tyto paryby přirozené myčky navštěvují, přesvědčila vědce, že nejde o náhodu, ale o zcela vědomé chování. To bylo u žraloků liščích zaznamenáno vůbec poprvé. Paryby těmito místy, hustě obývanými rybkami a jinými živočichy, kteří jsou schopni zbavit tělo mohutných predátorů nečistot a škůdců, proplouvají velmi často. Manuálně lemmatizovaný text žralok liščí často vplouvat do místo obývaný rybka který jeho tělo ochotně zbavit odumřelý kůže a parazit frekvence s jaký tento paryba přirozený myčka navštěvovat přesvědčit vědec že nejít o náhoda ale o zcela vědomý chování to být u žralok liščí zaznamenat vůbec poprvé paryba tento místo hustě obývaný rybka a jiný živočich který být schopný zbavit tělo mohutný predátor nečistota a škůdce proplouvat velmi často Lemming žralok liščí často vplouvat do místo obývaný rybka který jeho tělo ochotně zbavit odumřelý kůže a parazit frekvence s jaký tento paryba přirozený myčka navštěvovat přesvědčit vědec že nejít o náhoda ale o zcela vědomý chování to být u žralok liščí zaznamenat vůbec poprvé paryba tento místo hustě obývaný rybka a jiný živočich který být schopný zbavit tělo mohutný predátor nečistota a škůdce proplouvat velmi často LemmaGen žraloc liščí často vplouvat dobrý místo obývaný rybka který jeho tělo ochotně zbavit odumřelý kůže a parazit frekvence s jaký tento paryba přirozený myčka navštěvovat přesvědčit vědec že jít on náhoda ale on zcela vědomý chování to být u žralok liščí zaznamenat vůbec poprvé paryba tento místo hustit obývaný rybka a jiný živočich který být schopný zbavit tělo mohutný predátor čistota a škůdce proplouvat velmi často AIKA žralok liščí často vplouvat do místo obývaný rybka který jejich tělo ochotně zbavit odumřelý kůže a parazit frekvence s jaký

57 – 6

VOL.14, NO.5, OCTOBER 2012

2012/57 – 7. 9. 2012 tento paryba přirozený myčka navštěvovat přesvědčit vědec že nejít o náhoda ala o zcela vědomý chování ten být u žralok liščí zaznamenat vůbec poprvé paryba tento místo hustit obývaný rybka a jiné živočich který být schopen zbavit tělo mohutný predátor nečistota a škůdce proplouvat velmi často

U systému UFAL se vyskytují ojedinělé chyby při převodu sloves či zájmen a jak již bylo zmíněno v předešlé podsekci, systém nebere v potaz zápornou předponu. Pokud je zapnutá desambiguace textu, úspěšnost se zvyšuje o jednotky procent, ale některé chyby stále přetrvávají.

UFAL bez desambiguace žralok liščí často vplouvají do místo obývaný rybka který jeho tělo ochotně zbavit odumřelý kůže a parazit frekvence s jaký tento paryby přirozený myčka navštěvovat přesvědčit vědec že jít o náhodu, ale o zcela vědomý chování ten být u žralok liščí zaznamenat vůbec poprvé paryby tento místo hustě obývaný rybka a jiný živočich který být schopný zbavit tělo mohutný predátor nečistota a škůdce proplouvat velmi často

6.3 Text se jmény, příjmeními, názvy a mnohoznačnými slovy

UFAL s desambiguací žralok liščí často vyplouvat do místo obývaný rybka který jeho tělo ochotně zbavit odumřelý kůže a parazit frekvence s jaký tento paryba přirozený myčka navštěvovat přesvědčit vědec že jít o náhoda, ale o zcela vědomý chování ten být u žralok liščí zaznamenat vůbec poprvé paryba tento místy hustě obývaný rybka a jiný živočich který být schopný zbavit tělo mohutný predátor nečistota a škůdce proplouvat velmi často.

Původní text k lemmatizaci Až deset let vězení hrozí ředitelce jedné pražské realitní kanceláře za to, že zpronevěřila peníze svých klientů. Čtyřiačtyřicetiletou manažerku z Tachovska státní zástupce viní z trestných činů zpronevěry a podvodu. Škoda je podle náměstka plzeňské krajské státní zástupkyně Zbyňka Egera přes osm miliónů korun. Od klientů si nechala zasílat peníze určené na úhradu kupní ceny prodávaných nemovitostí a daně z jejich převodu přímo na konto realitní kanceláře a nikoliv na depozitní bankovní účet, tak jak to ukládají příslušné směrnice.

Vyhodnocení Tabulka 5: Lemmatizace odstavce bez jmen, příjmení, názvů a mnohoznačných slov, UFAL_1 představuje systém bez zapnuté desambiguace, UFAL_2 se zapnutou desambiguací. Systém

Úspěsnost [%]

Lemming

100,00

LemmaGen

90,90

AIKA

90,90

UFAL_1

92,42

UFAL_2

95,45

Mezi hlavní chyby lemmatizátoru LemmaGen patří ne úplně přesně naučená pravidla pro zpracování konců slov. Hned první chybou je např. lemmatizace slova „žraloci“ na „žraloc“, které má být korektně převedeno na „žralok“. Z předcházejících výsledků lze vypozorovat daleko více takovýchto případů, např. předložka „o“ je chybně převedena na zájmeno „on“, nebo příslovce „hustě“ na sloveso „hustit“. Jak je vidět z tabulky 5, námi vyvinutý lemmatizátor má na tomto vzorku textu stoprocentní úspěšnost, jelikož chyby původního lemmatizátoru byly odstraněny. U systému AIKA si webové rozhraní neporadilo s čárkou ani tečkou ve větě, které tedy byly odstraněny pro všechny lemmatizátory. Dále u některých slov, např. u slova „parazitů“ vrací dva tvary „parazit“ a „parazita“, což pokládáme za chybu (jedná se o druhý a čtvrtý pád), jelikož pro další zpracování potřebujeme od lemmatizátoru jen jeden výsledek, bereme tedy první v pořadí. U slova „tyto“ je vráceno „tento“ a „tyt“. U slova „ale“ vrací na prvním místě „ala“ a „ale“ až na druhém místě. U slova „to“ vrací na prvním místě „ten“ a až na druhém místě „to“ atd.

V této sekci je lemmatizován krátký složitější odstavec, obsahující jména, příjmení, názvy a mnohoznačná slova, všemi dostupnými lemmatizátory. Odstavec obsahuje 79 slov. Výsledek procentuální úspěšnosti jsme získali jako počet správně určených slov k celkovému počtu slov.

Manuálně lemmatizovaný text až deset rok vězení hrozit ředitelka jeden pražský realitní kancelář za to že zpronevěřit peníz svůj klient čtyřiačtyřicetiletý manažerka z tachovsko státní zástupce vinit z trestný čin zpronevěra a podvod škoda být podle náměstek plzeňský krajský státní zástupkyně zbyněk eger přes osm milión koruna od klient se nechat zasílat peníz určený na úhrada kupní cena prodávaný nemovitost a daň z jeho převod přímo na konto realitní kancelář a nikoliv na depozitní bankovní účet tak jak to ukládat příslušný směrnice Lemming až deset *let* vězení hrozit ředitelka jeden pražský realitní kancelář za to že zpronevěřit peníz svůj klient čtyřiačtyřicetiletý manažerku z tachovsko státní zástupce vinit z trestný čin zpronevěra a podvod škoda *je* podle náměstek plzeňský krajský státní zástupkyně zbyňka eger přes osm milión koruna od klient se nechat zasílat peníz určený na úhrada kupní cena prodávaný nemovitost a *daně* z jeho převod přímo na konto realitní kancelář a nikoliv na depozitní bankovní účet tak jak to ukládat příslušný směrnice LemmaGen až deset let vězení hrozit ředitelka jeden pražský realitní kancelář za to že zpronevěřit peníz svůj klient čtyřiačtyřicetiletý manažerk z tachovsko státní zástupce vinit z trestný čin zpronevěra a podvod škoda on podle náměstek plzeňský krajský státní zástupkyně zbyňka eger přes osm milión koruna od klient se nechat zasílat peníz určený na úhrada kupní cena prodávaný nemovitost a daň z jeho převod přímo na konto realitní kancelář a nikoliv na depozitní bankovní účet tak jak to ukládat příslušný směrnice

57 – 7

VOL.14, NO.5, OCTOBER 2012

2012/57 – 7. 9. 2012

AIKA až deset léto vězený hrozit ředitelka jeden pražský realitní kancelář za ten že zpronevěřit peníze svůj klient čtyřiatřicetiletý manažerka z tachovsko státní zástupka vinit z trestný čin zpronevěra a podvod škoda být podle náměstka plzeňský krajský státní zástupkyně zbyněk ___ přes osm milión koruna od klient se nechat zaslat peníze určený na úhrada kupný cena prodávaný nemovitost a daň z jejich převod přímo na konto realitní kancelář a nikoliv na depozitní bankovní účet tak jak to ukládat příslušný směrnice UFAL bez desambiguace až deset let vězení hrozit ředitelka jeden pražský realitní kancelář za ten že zpronevěřit peníz svůj klient čtyriačtyřicetiletý manažerka z tachovsko státní zástupce vinit z trestný čin zpronevěra a podvod škoda být podle náměstek plzeňské krajský státní zástupkyně zbyněk eger přes osm milión koruna od klient být nechat zasílat peníz určený na úhrada kupní cena prodávaný nemovitost a daň z jeho převod přímo na konto realitní kancelář a nikoliv na depozitní bankovní účet tak jak ten ukládat příslušný směrnice UFAL s desambiguací až deset rok vězení hrozit ředitelka jeden pražský realitní kancelář za to že zpronevěřit peníz svůj klient čtyřiačtyřicetiletý manažerka z tachovsko státní zástupce vinit z trestný čin zpronevěra a podvod škoda být podle náměstek plzeňský krajský státní zástupkyně zbyněk eger přes osm milión koruna od klient se nechat zasílat peníz určený na úhrada kupní cena prodávaný nemovitost a daň z jeho převod přímo na konto realitní kancelář a nikoli na depozitní bankovní účet tak jak ten ukládat příslušný směrnice Vyhodnocení Tabulka 6: Lemmatizace odstavce se jménem, příjmením, názvy a mnohoznačnými slovy, UFAL_1 představuje systém bez zapnuté desambiguace, UFAL_2 se zapnutou.

UFAL se opět potvrdilo, že zapojení desambiguace má výrazný vliv na dosažené výsledky. 6.4 Porovnání systému na testovací sadě o 1000 slovech V této sekci byla vytvořena testovací sada o velikosti 1000 slov, složená z různých internetových článků. Tato sada byla manuálně zpracována a byly otestovány všechny lemmatizační systémy. Přehled úspěšnosti systémů je uveden v tabulce 7. Nejlépe si vedl systém UFAL. Systém UFAL_1 bez zapnuté desambiguace byl úspěšný na 91,8%, pokud byla zapnuta desambiguace (UFAL_2) zvýšila se tato úspěšnost na 96,2%. Největší chybou, kterou tento systém dělal, bylo odstraňování negativní předpony, čímž se pak zničil význam textu. Pokud by systém správně zpracoval negativní předpony (UFAL_3), zvýšila by se jeho úspěšnost až na teoretickou hranici 96,9%. Systém AIKA měl obecně během celého testování problémy se vstupním textem, který obsahoval interpunkci, což je velkou chybou. Nicméně, aby bylo možné porovnat výsledky, vstupní text byl manuálně upraven. Jelikož systém AIKA nevrací žádný výstup pro slova, která nemá ve slovníku, je jeho úspěšnost dále snižována. Stejně tak je snižována, pokud na prvním místě vrátí nevhodně zpracované slovo. Úspěšnost systému AIKA byla 84,4%, pokud by systém alespoň vrátil čísla, která jsou v lemmatizovaném textu obsažena, byla by úspěšnost lemmatizace 87,2%. Lepších výsledů by bylo dosaženo po zapojení morfologické desambiguace, tak jak je tomu u systému UFAL. Systém LemmaGen byl úspěšný z 90,8%, což je velmi dobrý výsledek, zvláště jedná-li se o zpracování, které není postaveno na morfologické znalosti českého jazyka. Systém Lemming, vycházející ze systému LemmaGen, byl při převodu textu úspěšný z 94,0%. Je tedy vidět určitý posun oproti původnímu systému a také lze usuzovat, že je konkurenceschopný ve srovnání s ostatními porovnávanými systémy. Tabulka 7: Přehled úspěšnosti lemmatizačních systémů na testovací sadě o velikosti 1000 slov, AIKA_1 je běžně nastavený systém AIKA s podporou lemmatizace prefixů, AIKA_2 je teoretická úspěšnost, pokud by byla lemmatizována čísla, UFAL_1 představuje systém bez zapnuté desambiguace, UFAL_2 se zapnutou desambiguací a UFAL_3 představuje teoretickou úspěšnost, pokud by systém dokázal zpracovat záporný prefix „NE“ jako ostatní lemmatizátory.

Systém

Úspěsnost [%]

Lemming

94,93

LemmaGen

94,93

AIKA

87,34

UFAL_1

94,93

Systém

Úspěsnost [%]

UFAL_2

98,73

Lemming

94,00

LemmaGen

90,80

AIKA_1

84,40

AIKA_2

87,20

UFAL_1

91,80

UFAL_2

96,20

UFAL_3

96,90

Při začlenění jmen, příjmení, názvů a mnohoznačných slov do textu se u navrhovaného lemmatizátoru snížila úspěšnost a z tabulky 6 je vidět, že je stejná jako u lemmatizátoru LemmaGen, ze kterého vychází. Dále je také vidět, že ve slovech, ve kterých LemmaGen chyboval, systém Lemming převede správně a že chyby jsou hlavně v mnohoznačných slovech, jelikož tato nejsou nikterak ošetřena. Systém AIKA si v tomto testu nevedl moc dobře, jelikož jsme u každého lemmatizačního systému brali v potaz pouze první vrácené slovo, aby byly výsledky relevantní. U systému

57 – 8

VOL.14, NO.5, OCTOBER 2012

2012/57 – 7. 9. 2012 6.5 Výsledky systému Lemming na celé testovací sadě V této sekci je popsáno testování systému Lemming na sadě čítající 100 odstavců složených z tematicky různě zaměřených článků (celkem přes sto tisíc slov). Jelikož k ostatním systémům lze přistupovat pouze v online demo verzi, nebylo možné jimi takovéto kvantum dat nechat zpracovat. Bez ohodnocení mnohoznačných slov V tomto případě nejsou detekovaná mnohoznačná slova vůbec začleněna do výsledné procentuální úspěšnosti lemmatizátoru. Je to z toho důvodu, aby bylo objektivně objasněno, jaká je reálná hodnota úspěšnosti lemmatizátoru bez vlivu těchto slov. Po provedení lemmatizace trénovací množiny bylo dosaženo výsledku 96,94%. S ohodnocením mnohoznačnými slovy Zde jsou mnohoznačná slova zahrnuta do procentuálního výsledku lemmatizátoru. Bylo dosaženo výsledku s úspěšností lemmatizace 93,68%. Očividné snížení této hodnoty je zapříčiněno právě zahrnutím těchto slov. Avšak mnohoznačná slova jsou pouze označena pomocí znaku hvězdičky po obou stranách a nejsou nijak upravována. V některých případech by však mohlo náhodně dojít ke správnému určení základního tvaru slova i bez implementovaného morfologického desambiguátoru.

vede také velmi dobře, jeho úspěšnost se pohybovala vždy kolem 94%. Nejlépe ovšem dopadl systém UFAL, který obsahuje i morfologický desambiguátor. Jeho úspěšnost se pohybovala kolem 97%. Nakonec byl systém Lemming otestován na sadě čítající přes sto tisíc slov. Výsledná úspěšnost opět potvrdila předchozí výsledky. Systém Lemming pracoval s úspěšností kolem 94%. Závěrem lze tedy konstatovat, že navržený systém Lemming je konkurenceschopný a použitá metoda strojového učení může být velmi dobrým přístupem pro zpracování textu bez znalosti zpracovávaného jazyka. Při vývoji systému Lemming jsme však narazili i na několik komplikací, které zpomalovaly výkon lemmatizátoru, a do současné verze tak nebyly zařazeny. Tyto problémy mohou být taktéž považovány za náměty budoucího vylepšení. Jde např. o problematiku lemmatizace jmen a příjmení, či zařazení morfologické desambiguace pro porozumění kontextu lemmatizovaného textu a správné převedení mnohoznačných slov.

Poděkování Vznik článku byl podpořen výzkumným projektem Ministerstva průmyslu a obchodu ČR, č. FR-TI4/151 a interním grantem Fakulty elektrotechniky a komunikačních technologií Vysokého učení technického, evidenční č. FEKT-S-11-17.

Literatura

Bez detekce mnohoznačných slov V této části je vypnuta detekce mnohoznačných slov (není zapnuto jejich označování znakem *) a všechna slova jsou tedy podrobena lemmatizaci. Úspěšnost se oproti předcházejícímu případu mírně zlepšila, a to na hodnotu 94,47%. V případě mnohoznačných slov se tedy jedná o zcela náhodné určení základního tvaru slova, ale v některých případech se docílí požadovaného výsledku.

[1] Hellebrand, D.; Nalezení slovních kořenů v češtině: diplomová práce. Brno: Vysoké učení technické v Brně, Fakulta informatiky, Ústav informačních systémů, 2010. 58s. Vedoucím práce byl Ing. Petr Chmelař.

Vyhodnocení I na velkém počtu slov vykazuje navržený lemmatizátor velice dobré výsledky. Srovnání s lemmatizátorem LemmaGen není v tomto měření k dispozici, protože jsme neměli přístup k takovému rozhraní, které by dokázalo obsloužit takové množství textu automaticky a ohodnotit je.

[3] Hajič, J.; Disambiguation of Rich Inflection (Computational Morphology of Czech). Karolinum, Charles University Press, Praha, 2004.

7 Závěr V tomto článku byla rozebrána problematika lemmatizace česky psaného textu, byly zmíněny nejpoužívanější typy algoritmů pro stemming a lemmatizaci. Samotnému procesu lemmatizace, jeho učení a zvýšení úspěšnosti lemmatizace byly věnovány sekce 4 a 5. V sekci 6 jsou shrnuty výsledky. Nejprve je provedena ukázka na náhodných slovech – nepravidelných a obsahujících nejčastější předpony. Dále je ukázána lemmatizace na dvou různě složitých příkladech, aby bylo poukázáno na úspěšnost vylepšeného řešení před původním systémem LemmaGen a konkurenceschopnost vůči systému AIKA a UFAL. Dále bylo nové řešení otestováno na rozsáhlejší trénovací sadě, která čítala 1000 slov. Zde si navržený systém Lemming

[2] Sedláček, R.; Morfologický analyzátor češtiny. diplomová práce, Brno. Masarykova Univerzita, Fakulta Informatiky,83s.

[4] Morfologický analyzátor ajka – interaktivní režim. [online]. Masarykova univerzita, Fakulta informatiky, NLP centrum. Dostupné z www: < http://nlp.fi.muni.cz/projekty/wwwajka/WwwAjkaSkripty/ > [5] Morphological Analysis of Czech Word Forms, [online]. Dostupné z www: < http://quest.ms.mff.cuni.cz/morph/ > [6] Šanda, P.; Určení základního tvaru slova: diplomová práce. Brno: Vysoké učení technické v Brně, Fakulta elektrotechniky a komunikačních technologií, Ústav telekomunikací, 2010. 68s. Vedoucí práce byl Ing. Jan Karásek. [7] Juršič, M.; LemmaGen – Multilingual Open Source Lemmatization. Jožef Stefan Institute, Department of knowledge technologies. 2010. [online] Dostupné z www:

57 – 9

VOL.14, NO.5, OCTOBER 2012

2012/57 – 7. 9. 2012 [8] Lovins, J. B.; Development of a Stemming Algorithm. Mechanical Translation and Computational Linguistic, Ročník 11, Číslo 1 a 2, březen a červen 1968. [online]. Dostupné z www: http://journal.mercubuana.ac.id/data/MT-1968Lovins.pdf [9] Porter, M. F.; An Algorithm for Suffix Stripping [online]. Computer Laboratory, Cambridge Dostupné z www: [11] Plisson, J., Lavrač, N., Mladenić, D. A.; Rule based approach to word lemmatization. Proc. 7th International MultiConference Information Society IS-2004 C, s. 83-86, 2004.

mí, mně, moje, moji, možná, můj, muset, musí, my, na, nad, nade, nám, námi, naproti, náš, náš, naše, naši, ne, ně, nebo, nebyl, nebyla, nebyli, nebylo, nebyly, něco, nedělá, nedělají, nedělám, neděláme, neděláš, neděláte, nějak, nejsi, někde, někdo, některý, nemají, nemáme, nemáte, neměl, němu, nestačí, nevadí, než, ní, nic, nich, ním, nimi, o, od, ode, on, ona, oni, ono, ony, pak, po, podle, pořád, potom, pozdě, pro, proč, prosím, prostě, proti, protože, před, přes, přese, rovně, s, se, si, skoro, smí, snad, spolu, svůj, svých, ta, tady, tak, takhle, taky, tam, tamhle, támhleto, tamto, té, tě, tebe, tebou, tedy, těchto, těm, těmto, ten, tento, této, ti, tím, tímto, to, tobě, tohle, tom, toto, trošku, třeba, tvá, tvé, tvoje, tvůj, ty, u, určitě, už, v, vám, vámi, vás, váš, vaše, vaši, ve, vedle, více, vlastně, všechno, všichni, vůbec, vy, vždy, z, za, zač, zatím, zatímco, zato, zda, ze, že.

[12] Plisson, J., Lavrač, N., Mladenić, D., Erjavec, T.; Ripple Down Rule Learning for Automated Word Lemmatisation. AI Communication, s. 15-26. 2008. [13] Compton, P.; Jansen, R.; Knowledge in Context: a strategy for expert system maintenance. Proc. Second Australian Joint Artificial Intelligence Conference. 1988. s. 292–306. [14] Juršič, M., Mozetič, I., Lavrač, N.; Learning Ripple Down Rules For Efficient Lemmatization. Zbornik 10. mezinarodne multikonference informacijska družba IS 2007. Ljubljana: Institut „Jožef Stefa“, s. 206-209. 2007. [15] Juršič, M., Mozetič, I., Erjavec, T., Lavrač, N.; LemmaGen: Multilingual Lemmatisation with Induced Ripple-Down Rules. Journal of Universal Computer Science. Ročník 16, Číslo 9. 2010. [16] Dictionaries for International Ispell, [online]. Dostupné z www: < http://lars.cs.ucla.edu/geoff/ispell.html > [17] Šmerk, P. Aktivní učení pravidel pro morfologickou desambiguaci: diplomová práce. Brno: Masarykova Univerzita, Fakulta Informatiky, 2002. 45s. Vedoucím práce byl: Mgr. Miroslav Nepil.

Příloha A \ ‘ | #

[ § ( $

] > ) %

= < _ -

, ° + ~

. : ^

/ „ &

` ? *

; { !

„“ } @

Příloha B A, ačkoli, ahoj, ale, anebo, ano, asi, aspoň, až, bez, beze, bohužel, by, bys, čau, co, či, dál, dále, daleko, děkovat, děkuje, děkujeme, děkuješ, děkujete, děkuji, děkují, do, docela, ho, i, já, jak, jde, jeho, její, jejich, jemu, jen, jenom, jenž, jestli, jestliže, ještě, jež, jich, jimi, již, k, kam, kde, kdo, kdy, když, ke, kolik, kromě, která, které, který, kteří, kvůli, mé, mě, mezi,

57 – 10

VOL.14, NO.5, OCTOBER 2012