Úvod do analýzy prirodzeného jazyka

Automatická analýza prirodzeného jazyka je úloha nadmieru užitočná a mimoriadne ťažká. Spadá do oblasti umelej inteligencie a aj napriek významnému pokroku v posledných rokoch sme stále ďaleko od systémov s vysokou úspešnosťou. V tomto úvode do problematiky si na niekoľkých jednoduchých príkladoch vysvetlíme algoritmus vyvinutý vo výskumnom centre Xeroxu (PARC = Palo Alto Research Center) a použitý napríklad v úspešnom vyhľadávači spoločnosti Powerset, ktorý neskôr kúpil Microsoft.

Gramatika

Pre analýzu formálnych i prirodzených jazykov sa najčastejšie používa formalizmus vymyslený Noam Chomským, významným americkým jazykovedcom. Jeho formálnych gramatík je mnoho druhov, my budeme pracovať iba s tzv. Bezkontextovými, ktorých pravidlá majú tvar

X → Y ₁... Y _n

Takto zapísané gramatiky sa nazývajú generatívne, pretože symbol na ľavej strane pravidlá "generuje" sekvenciu symbolov na pravej strane. Pri analýze vety musíme teda postupovať opačne, sprava doľava.

Na rozdiel od formálnych (programovacích) jazykov bývajú vety prirodzeného jazyka často viacznačný, náš parser musí teda vedieť odvodiť pre daný vstup viac syntaktických stromov, ak to pripúšťa gramatika. Napríklad veta "Levíča zožralo dieťa" má dve rôzne interpretácie, pretože v slovenčine nemožno u podstatných mien stredného rodu rozlíšiť koncovkou prvý pád od štvrtého. Nižšie uvidíme, ako sa s takou víceznačností vysporiadať v gramatike.

Rysy

Vo formalizmu, ktorý budeme používať, je každému slovu vstupné vety priradená množina napospol tvaroslovných vlastností, tzv. Rysov. Začneme s jednoduchým anglickým príkladom: "The girls read a book." V tomto prípade máme na vstupe nasledujúce rysy:

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

kde def = určitosť, num = číslo (sg = singulár, pl = plurál) a tenzia = čas (pres = prítomný). Zoznam rysov si môžeme predstaviť ako množinu párov zložených z názvu rysu a jeho hodnoty. Takáto množina sa nazýva zostavou rysov. Gramatiky budeme ladiť pomocou parsera, ktorý možno stiahnuť zadarmo z odkazu pod článkom. Vytvorte nasledujúci súbor a uložte ho ako 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 .

Naviac ešte budeme potrebovať (zatiaľ prázdny) súbor valency_en.txt, ku ktorému sa vrátime neskôr.

Pravidlá

V súbore grammar_en.txt sme zatiaľ nadefinovali len vstup pre gramatiku (v reálnom systémov obstará Tvaroslovné analýzu morfologický analyzátor). Musíme ešte dodať pravidlá:

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

Každé pravidlo sa skladá z bezkontextového schémy (X → Y ₁... Y _n) a množiny anotácií pre každý symbol na pravej strane pravidla. Tieto anotácie popisujú požadované hodnoty rysov a výslednú zostavu rysov pre frázu určenú ľavou stranou pravidlá. V anotáciách sa používajú dva zvláštne symboly: "^" reprezentuje zostavu rysov výslednej frázy, zatiaľ čo "." reprezentuje zostavu rysov patriaci symbolu na pravej strane pravidlá, ku ktorej sa množina anotácií viaže. U prvého pravidla teda hovoríme, že menné frázy (NP) sa skladá zo členu (determiner) nasledovanom podstatným menom (N) alebo samotného podstatného mena (N) (Det? Znamená, že symbol Det je voliteľný). V našom príklade bude výsledná zostava rysov pre "the girls" [DEF = 1, SEM FUNC = girl, SEM CAT = N, NUM = pl], vidíme teda, že zostavy rysov oboch slov sa zlúčili. Druhé pravidlo hovorí, že slovesné frázy (VP) sa skladá zo slovesa (V) a voliteľné menné frázy (NP). Anotácia ^ OBJ =. pod NP potom hovorí, že táto NP je priamym predmetom (OBJ = objekt) slovesá reprezentovaného V. Konečne tretí pravidlo hovorí, že veta (S) sa skladá z NP a VP, pričom NP je podmetom (SUBJ = subjekt).

Syntaktický strom

Analyzátor spustíme príkazom "parser grammar_en.txt valency_en.txt". Výsledkom je syntaktický strom a zostava rysov pre celú vetu:

-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 sa u rysu SEM. Tento nie je Tvaroslovné, ale obsahuje lexikálne sémantické informácie o slovách, v našom príklade len Lemma (FUNC = funktory) a syntaktickú kategórii (CAT). Tento rys je dôležitý pre náväznú sémantickú analýzu, ku ktorej sa dostaneme v niektorom z ďalších dielov.

Analýza slovenské vety

Teraz sa pozrime na analýzu slovenskej vety. Čeština má na rozdiel od angličtiny pomerne voľný slovosled, vyššie uvedenú anglickú vetu môžeme preložiť ako "Dievčatá čítajú knihu", "Knihu čítajú dievčaťa", "Knihu dievčatá čítajú", "Dievčatá knihu čítajú" a pod. Je teda na prvý pohľad zrejmé, že gramatika bude zásadne odlišná od tej pre angličtinu. Ak vynecháme nateraz pravidlo, že v slovenčine stojí príklonka v pevnom poradí vždy na druhom mieste vo vete (vrátime sa k nemu neskôr), máme pre češtinu na úrovni vety len jedno pravidlo:

S → X ⁺

kde X môže byť V alebo NP (neskôr sa dostaneme aj k ďalším kategóriám napr. pre príslovky a predložkové frázy) a Kleenovo + znamená, že symbolov na pravej strane je ľubovoľné množstvo (prinajmenšom jeden). Vlastne sa jedná o metapravidlo, pretože príslušné anotácie sa líši podľa kategórie slova, NP bude mať iné ako V apod. Uložte nasledujúci zdrojový kód obsahujúce vstup pre vetu "Levíča zožralo dieťa" a gramatiku pre slovenčinu 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+ .
  ^=. ;

Pravidlami hovoríme, že veta (S) bude mať rovnaké rysy ako sloveso (V), ku ktorým pridáme rysy dodanej pravidlami. Druhé pravidlo hovorí, že NP v prvom páde (nom) môže byť podmetom (SUBJ). Tretie pravidlo hovorí, že NP vo štvrtom páde (acc) môže byť priamym predmetom (dobj). Pretože obe NP na vstupe sú viacznačný, tieto pravidlá nám hovoria, že každá z nich môžeme byť vo vete buď podmet, alebo priamy predmet. Teoreticky teda vznikajú štyri možnosti, pretože však každá veta môže mať nanajvýš jeden podmet a jeden priamy predmet, zostávajú iba dve.

Teraz spustite analyzátor príkazom "parser grammar_cz.txt valency_cz.txt". Vidíme, že výsledky sú dva, lebo - ako už sme si povedali - táto veta je jednoslovných, pretože nemožno bez kontextu (sémantiky) určiť, ktorá NP je podmetom a ktorá priamym predmetom. Všimnite si, že vstup pre "levíča" a "dieťa" teraz zahŕňa dve položky, jedna hovorí, že dané slovo v prvom páde (CASE = nom, tj. Nominative), druhá, že je vo štvrtom páde (CASE = acc, tj . akuzatív). Anotácia pre sloveso iba hovoria, že jeho podmet je menné frázy stredného rodu v jednotnom čísle.

Nabudúce si ukážeme, ako jednoduchý parser pre prirodzený jazyk naimplementovať vo Swiftu.

Parser pre OS X, Linux a Windows si môžete stiahnuť tu.