Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Lekce 2 - Úvod do analýzy přirozeného jazyka

V minulé lekci, Testování algoritmu pro podvod s ruletou, jsme se podívali na údajně výherní algoritmus virtuální rulety.

Automatická analýza přirozeného jazyka je úloha nadmíru užitečná a mimořádně těžká. Spadá do oblasti umělé inteligence a i přes významný pokrok v posledních letech jsme stále daleko od systémů s vysokou úspěšností. V tomto úvodu do problematiky si na několika jednoduchých příkladech vysvětlíme algoritmus vyvinutý ve výzkumném centru Xeroxu (PARC=Palo Alto Research Center) a použitý například v úspěšném vyhledávači společnosti Powerset, jejž později koupil Microsoft.

Gramatika

Pro analýzu formálních i přirozených jazyků se nejčastěji používá formalismus vymyšlený Noamem Chomským, významným americkým jazykovědcem. Jeho formálních gramatik je mnoho druhů, my budeme pracovat pouze s tzv. bezkontextovými, jejichž pravidla mají tvar

X → Y1 ... Yn

Takto zapsané gramatiky se nazývají generativní, protože symbol na levé straně pravidla "generuje" sekvenci symbolů na pravé straně. Při analýze věty musíme tedy postupovat opačně, zprava doleva.

Na rozdíl od formálních (programovacích) jazyků bývají věty přirozeného jazyka často víceznačné, náš parser musí tedy umět odvodit pro daný vstup více syntaktických stromů, pokud to připouští gramatika. Například věta "Lvíče sežralo dítě" má dvě různé interpretace, protože v češtině nelze u podstatných jmen středního rodu rozlišit koncovkou první pád od čtvrtého. Níže uvidíme, jak se s takovou víceznačností vypořádat v gramatice.

Rysy

Ve formalismu, který budeme používat, je každému slovu vstupní věty přiřazena množina vesměs tvaroslovných vlastností, tzv. rysů. Začneme s jednoduchým anglickým příkladem: "The girls read a book." V tomto případě máme na vstupu následující rysy:

the def=1
girls num=pl
read tense=pres
a def=0
book num=sg

kde def=určitost, num=číslo (sg=singulár, pl=plurál) a tense=čas (pres=přítomný). Seznam rysů si můžeme představit jako množinu párů skládajících se z názvu rysu a jeho hodnoty. Taková množina se nazývá sestavou rysů. Gramatiky budeme ladit pomocí parseru, který lze stáhnout zdarma z odkazu pod článkem. Vytvořte následující soubor a uložte jej jako grammar_en.txt:

0 Det   ^DEF=1 .
1 N     ^SEM FUNC=girl ^SEM CAT=N ^NUM=pl .
2 V     ^SEM FUNC=read ^SEM CAT=V ^TENSE=pres .
3 Det   ^DEF=0 .
4 N     ^SEM FUNC=book ^SEM CAT=N ^NUM=sg .

Navíc ještě budeme potřebovat (prozatím prázdný) soubor valency_en.txt, k němuž se vrátíme později.

Pravidla

V souboru grammar_en.txt jsme zatím nadefinovali jen vstup pro gramatiku (v reálném systémů obstará tvaroslovnou analýzu morfologický analyzátor). Musíme ještě dodat pravidla:

NP -> Det? N .
    ^=. ; ^=. ;
VP -> V NP? .
    ^=. ; ^OBJ=. ;
S -> NP VP .
    ^SUBJ=. ; ^=. ;

Každé pravidlo se skládá z bezkontextového schématu (X → Y1 ... Yn) a množiny anotací pro každý symbol na pravé straně pravidla. Tyto anotace popisují vyžadované hodnoty rysů a výslednou sestavu rysů pro frázi určenou levou stranou pravidla. V anotacích se používají dva zvláštní symboly: "^" reprezentuje sestavu rysů výsledné fráze, zatímco "." reprezentuje sestavu rysů patřící symbolu na pravé straně pravidla, ke které se množina anotací váže. U prvního pravidla tedy říkáme, že jmenná fráze (NP) se skládá ze členu (determiner) následovaném podstatným jménem (N) nebo samotného podstatného jména (N) (Det? znamená, že symbol Det je nepovinný). V našem příkladě bude výsledná sestava rysů pro "the girls" [DEF=1, SEM FUNC=girl, SEM CAT=N, NUM=pl], vidíme tedy, že sestavy rysů obou slov se sloučily. Druhé pravidlo říká, že slovesná fráze (VP) se skládá ze slovesa (V) a volitelné jmenné fráze (NP). Anotace ^OBJ=. pod NP pak říká, že tato NP je přímým předmětem (OBJ=objekt) slovesa reprezentovaného V. Konečně třetí pravidlo říká, že věta (S) se skládá z NP a VP, přičemž NP je podmětem (SUBJ=subjekt).

Syntaktický strom

Analyzátor spustíme příkazem "parser grammar_en.txt valency_en.txt". Výsledkem je syntaktický strom a sestava rysů pro celou větu:

-0- S -5- S(NP(Det,N),VP(V,NP(Det,N)))

SEM FUNC read
    CAT V
TENSE pres
OBJ SEM FUNC book
        CAT N
    NUM sg
    DEF 0
SUBJ DEF 1
     SEM FUNC girl
         CAT N
     NUM pl

Zastavme se u rysu SEM. Tento není tvaroslovný, ale obsahuje lexikálně sémantické informace o slovech, v našem příkladu pouze lemma (FUNC=funktor) a syntaktickou kategorii (CAT). Tento rys je důležitý pro návaznou sémantickou analýzu, k níž se dostaneme v některém z dalších dílů.

Analýza české věty

Teď se podívejme na analýzu české věty. Čeština má na rozdíl od angličtiny poměrně volný slovosled, výše uvedenou anglickou větu můžeme přeložit jako "Dívky čtou knihu", "Knihu čtou dívky", "Knihu dívky čtou", "Dívky knihu čtou" apod. Je tedy na první pohled zřejmé, že gramatika bude zásadně odlišná od té pro angličtinu. Pomineme-li prozatím pravidlo, že v češtině stojí příklonky v pevném pořadí vždy na druhém místě ve větě (vrátíme se k němu později), máme pro češtinu na úrovni věty jen jedno pravidlo:

S → X+

kde X může být V nebo NP (později se dostaneme i k dalším kategoriím např. pro příslovce a předložkové fráze) a Kleenovo + znamená, že symbolů na pravé straně je libovolné množství (přinejmenším jeden). Vlastně se jedná o metapravidlo, protože příslušné anotace se liší podle kategorie slova, NP bude mít jiné než V apod. Uložte následující zdrojový kód obsahující vstup pro větu "Lvíče sežralo dítě" a gramatiku pro češtinu do grammar_cz.txt:

0 N     ^SEM FUNC=lvíče ^SEM CAT=N ^NUM=sg ^GENDER=neut ^CASE=nom .
0 N     ^SEM FUNC=lvíče ^SEM CAT=N ^NUM=sg ^GENDER=neut ^CASE=acc .
1 V ^SEM FUNC=sežrat ^SEM CAT=V ^TENSE=past ^SUBJ GENDER=neut ^SUBJ NUM=sg .
2 N     ^SEM FUNC=dítě ^SEM CAT=N ^NUM=sg ^GENDER=neut ^CASE=nom .
2 N     ^SEM FUNC=dítě ^SEM CAT=N ^NUM=sg ^GENDER=neut ^CASE=acc .

NP -> Det? N .
  ^=. ; ^=. ;
X -> NP .
  .CASE=nom ^SUBJ=. ;
X -> NP .
  .CASE=acc ^DOBJ=. ;
X -> V .
  ^=. ;
S -> X+ .
  ^=. ;

Pravidly říkáme, že věta (S) bude mít stejné rysy jako sloveso (V), k nimž přidáme rysy dodané pravidly. Druhé pravidlo říká, že NP v prvním pádě (nom) může být podmětem (SUBJ). Třetí pravidlo říká, že NP ve čtvrtém pádě (acc) může být přímým předmětem (DOBJ). Protože obě NP na vstupu jsou víceznačné, tato pravidla nám říkají, že každá z nich můžeme být ve větě buď podmět, nebo přímý předmět. Teoreticky tedy vznikají čtyři možnosti, protože však každá věta může mít nanejvýš jeden podmět a jeden přímý předmět, zůstávají pouze dvě.

Nyní spusťte analýzator příkazem "parser grammar_cz.txt valency_cz.txt". Vidíme, že výsledky jsou dva, neboť - jak už jsme si řekli - tato věta je víceznačná, protože nelze bez kontextu (sémantiky) určit, která NP je podmětem a která přímým předmětem. Všimněte si, že vstup pro "lvíče" a "dítě" nyní zahrnuje dvě položky, jedna říká, že dané slovo v prvním pádě (CASE=nom, tj. nominative), druhá, že je ve čtvrtém pádě (CASE=acc, tj. akuzativ). Anotace pro sloveso pouze říkají, že jeho podmět je jmenná fráze středního rodu v jednotném čísle.

Příště si ukážeme, jak jednoduchý parser pro přirozený jazyk naimplementovat ve Swiftu.

Parser pro OS X, Linux a Windows si můžete stáhnout zde nebo níže při výpadku.


 

Stáhnout

Stažením následujícího souboru souhlasíš s licenčními podmínkami

Staženo 220x (2.18 MB)

 

Předchozí článek
Testování algoritmu pro podvod s ruletou
Všechny články v sekci
Ostatní algoritmy
Článek pro vás napsal Peter Tigranjan
Avatar
Uživatelské hodnocení:
5 hlasů
Aktivity