Zpracování přirozeného jazyka
Aleš Horák
E-mail: hales@fi.muni.cz
http://nlp.fi.muni.cz/uui/
Obsah:
Komunikace
Gramatiky a syntaktická analýza
Analýza přirozeného jazyka
PA026 – Projekt z umělé inteligence
Úvod do umělé inteligence 12/12 1 / 37
Komunikace Přirozený jazyk – prostředek komunikace
Přirozený jazyk – prostředek komunikace
komunikace = cílená výměna informace pomocí produkce a vnímání
(sdílených) pokynů
– zvířata – až stovky pokynů (šimpanz, delfín, . . . )
– člověk – potenciálně neomezené množství, díky přirozenému jazyku
Úvod do umělé inteligence 12/12 2 / 37
Komunikace Přirozený jazyk – prostředek komunikace
Přirozený jazyk – prostředek komunikace
komunikace = cílená výměna informace pomocí produkce a vnímání
(sdílených) pokynů
– zvířata – až stovky pokynů (šimpanz, delfín, . . . )
– člověk – potenciálně neomezené množství, díky přirozenému jazyku
2 náhledy na přirozený jazyk:
klasický (před 1953) – jazyk se skládá z vět, které jsou buď pravdivé
nebo nepravdivé (srovnej s logikou)
moderní (po 1953) – užití jazyka je jedna z možných akcí
Wittgenstein (1953) Philosophical Investigations
Searle (1969) Speech Acts
Úvod do umělé inteligence 12/12 2 / 37
Komunikace Přirozený jazyk – prostředek komunikace
Přirozený jazyk – prostředek komunikace
komunikace = cílená výměna informace pomocí produkce a vnímání
(sdílených) pokynů
– zvířata – až stovky pokynů (šimpanz, delfín, . . . )
– člověk – potenciálně neomezené množství, díky přirozenému jazyku
2 náhledy na přirozený jazyk:
klasický (před 1953) – jazyk se skládá z vět, které jsou buď pravdivé
nebo nepravdivé (srovnej s logikou)
moderní (po 1953) – užití jazyka je jedna z možných akcí
Wittgenstein (1953) Philosophical Investigations
Searle (1969) Speech Acts
Turingův test založen na jazyku ⇐ jazyk je pevně spojen s myšlením
komunikace se tvoří pomocí řečových aktů (speech acts) jako jeden z
typů agentových akcí
cíl komunikace –
Úvod do umělé inteligence 12/12 2 / 37
Komunikace Přirozený jazyk – prostředek komunikace
Přirozený jazyk – prostředek komunikace
komunikace = cílená výměna informace pomocí produkce a vnímání
(sdílených) pokynů
– zvířata – až stovky pokynů (šimpanz, delfín, . . . )
– člověk – potenciálně neomezené množství, díky přirozenému jazyku
2 náhledy na přirozený jazyk:
klasický (před 1953) – jazyk se skládá z vět, které jsou buď pravdivé
nebo nepravdivé (srovnej s logikou)
moderní (po 1953) – užití jazyka je jedna z možných akcí
Wittgenstein (1953) Philosophical Investigations
Searle (1969) Speech Acts
Turingův test založen na jazyku ⇐ jazyk je pevně spojen s myšlením
komunikace se tvoří pomocí řečových aktů (speech acts) jako jeden z
typů agentových akcí
cíl komunikace – změnit akce ostatních agentů
Úvod do umělé inteligence 12/12 2 / 37
Komunikace Řečové akty
Řečové akty
Komunikační situace
Mluvčí (speaker) → Promluva (utterance) → Posluchač (hearer)
řečové akty směřují k naplnění cílů mluvčího:
– informovat (inform) “Před tebou je jáma.”
– ptát se (query) “Vidíš zlato?”
– přikázat/žádat (command/request) “Zvedni to.”
– slíbit/svěřit se s plánem (promise, commit
to plan)
“Rozdělím se s tebou o zlato.”
– potvrdit (acknowledge) “OK”
plánování řečových aktů vyžaduje znalosti:
– komunikační situace
– sémantiky a syntaxe (sdílených konvencí)
– informace o Posluchači – cíle, znalosti, rozumnost
Úvod do umělé inteligence 12/12 3 / 37
Komunikace Komunikační fáze (při informování)
Komunikační fáze (při informování)
průběh promluvy je možné rozložit na fáze:
– záměr (intention) M chce informovat Po, že Pr
– generování (generation) M vybírá slova W pro vyjádření Pr
– syntéza (synthesis) M říká slova W
– vnímání (perception) Po vnímá W ′
– analýza (analysis) Po odvozuje možné významy Pr1, . . . , Prn
– zjednoznačnění
(disambiguation)
Po vybírá zamýšlený význam Pri
– zahrnutí (incorporation) Po zahrne Pri do své báze znalostí
Úvod do umělé inteligence 12/12 4 / 37
Komunikace Komunikační fáze (při informování)
Komunikační fáze (při informování)
průběh promluvy je možné rozložit na fáze:
– záměr (intention) M chce informovat Po, že Pr
– generování (generation) M vybírá slova W pro vyjádření Pr
– syntéza (synthesis) M říká slova W
– vnímání (perception) Po vnímá W ′
– analýza (analysis) Po odvozuje možné významy Pr1, . . . , Prn
– zjednoznačnění
(disambiguation)
Po vybírá zamýšlený význam Pri
– zahrnutí (incorporation) Po zahrne Pri do své báze znalostí
Může přitom vzniknout chyba?
– neupřímnost (Po nevěří Pr)
– víceznačnost promluvy (Po zvolí špatné Pri )
– různé pochopení aktuální situace (zamýšlený význam mezi Pri není)
Úvod do umělé inteligence 12/12 4 / 37
Komunikace Komunikační fáze (při informování)
Komunikační fáze – příklad
Mluvčízáměr generování syntéza
Vědět(Po, “Wumpus je mrtvý.” [v u m p u s j e m r t v i:]
¬Na_živu(Wumpus1, S3))
Posluchačvnímání analýza zjednoznačnění
“Wumpus
je mrtvý.”
syntaktická
analýza:
S
NP
Noun
Wumpus
VP
Verb
je
Adjective
mrtvý
sémantická
interpretace:
¬Na_živu(Wumpus, Teď )
Unavený(Wumpus, Teď )
pragmatická
interpretace:
¬Na_živu(Wumpus1, S3)
Unavený(Wumpus1, S3)
¬Na_živu(Wumpus1, S3))
zahrnutí
Tell(KB,
¬Na_živu(Wumpus1, S3))
Úvod do umělé inteligence 12/12 5 / 37
Gramatiky a syntaktická analýza
Obsah
1 Komunikace
Přirozený jazyk – prostředek komunikace
Řečové akty
Komunikační fáze (při informování)
2 Gramatiky a syntaktická analýza
Gramatiky pro analýzu jazyka
Lexikon pro agenta ve Wumpusově jeskyni
Syntaktický strom
Test na shodu
Syntaktická analýza pomocí strojového učení
3 Analýza přirozeného jazyka
Význam syntaktické analýzy
Problémy při analýze přirozeného jazyka
Reálná syntaktická analýza přirozeného jazyka
4 PA026 – Projekt z umělé inteligence
Úvod do umělé inteligence 12/12 6 / 37
Gramatiky a syntaktická analýza
Gramatiky a syntaktická analýza
zvířata používají místo vět izolované symboly ⇒ omezená sada
komunikovatelných situací → žádná generativní kapacita
gramatika specifikuje skladební strukturu složených pokynů – definuje
formální jazyk pokynů
formální jazyk = množina řetězců (vět) teminálních symbolů (slov)
2 náhledy na vztah věty a gramatiky:
– S je správný řetězec/věta z jazyka ⇔ S je analyzovatelný danou gramatikou
– příslušná gramatika generuje S ⇔ S je správný řetězec/věta z jazyka
gramatika je zadána jako množina přepisovacích pravidel
S → NP VP
Pronoun → já | ty | on | . . .
v tomto příkladu: S větný symbol – kořenový symbol gramatiky
NP, VP neterminály
já, ty, . . . terminály
Úvod do umělé inteligence 12/12 7 / 37
Gramatiky a syntaktická analýza Typy gramatik
Typy gramatik
regulární (regular) neterminál → terminál[neterminál]
S → aS
S → b
ekvivalentní síle konečných automatů, neumí an
bn
bezkontextové (context-free) neterminál → cokoliv
S → aSb
ekvivalentní síle zásobníkových automatů, umí an
bn
, neumí an
bn
cn
kontextové (context-sensitive) – víc termů na levé straně (kontext neterminálu)
ASB → AAaBB
umí an
bn
cn
rekurzivně vyčíslitelné (recursively enumerable) – bez omezení
ekvivalentní síle Turingova stroje
přirozený jazyk byl dlouho pokládán za bezkontextový → nyní prokázáno,
že obsahuje kontextové prvky SliDo
Úvod do umělé inteligence 12/12 8 / 37
Gramatiky a syntaktická analýza Typy gramatik
Přesnost a pokrytí gramatiky
u složitějších jazyků (např. přirozených)
→ jazyk L1 (generovaný gramatikou) se liší od zamýšleného jazyka L2
L1 L2
chybně generované chybně negenerované
kvalita gramatiky:
– pokrytí – procento vět jazyka L2 generovatelných gramatikou (|L1 ∩ L2|/|L2|)
– přesnost – procento generovaných vět, které jsou správné věty jazyka L2(|L1 ∩ L2|/|L1|)
– kombinová F-míra – harmonický průměr 2 ·
přesnost·pokrytí
přesnost+pokrytí
tvorba gramatiky . . . postupný proces zvyšování pokrytí a přesnosti
gramatiky přirozených jazyků – velmi rozsáhlé a přesto většinou nepopisují
plně ani angličtinu
Úvod do umělé inteligence 12/12 9 / 37
Gramatiky a syntaktická analýza Gramatiky pro analýzu jazyka
Gramatiky pro analýzu jazyka
využívané pro syntaktickou analýzu
pro lokální varianty – regulární gramatiky (regulární výrazy, např. pro
extrakci informací )
pro vyjmenované větné struktury – bezkontextové gramatiky
pro plný jazyk – (mírně) kontextové gramatiky
praktické nástroje – většinou rozšíření bezkontextových gramatik (CFG):
• Prolog – definite clause grammars, DCG
• Java, Python – ANTLR (ANother Tool for Language Recognition)
grammar Expr;
prog: (expr NEWLINE)∗ ;
expr: expr (’*’|’/’) expr
| expr (’+’|’-’) expr
| INT
| ’(’ expr ’)’
;
NEWLINE: [\r\n]+ ;
INT: [0-9]+ ;
Úvod do umělé inteligence 12/12 10 / 37
Gramatiky a syntaktická analýza Gramatiky pro analýzu jazyka
Gramatika – příklad 1
gramatika vět typu “The young boy sings a song.”
# 1. část – pravidla
sentence → noun_phrase, verb_phrase.
noun_phrase → determiner, noun_phrase2.
noun_phrase → noun_phrase2.
noun_phrase2 → adjective, noun_phrase2.
noun_phrase2 → noun.
verb_phrase → verb.
verb_phrase → verb, noun_phrase.
# 2. část – lexikon
determiner → ’the’. noun → ’boy’.
determiner → ’a’. noun → ’song’.
verb → ’sings’. adjective → ’young’.
sentence([’the’, ’young’, ’boy’, ’sings’, ’a’, ’song’]).
True
Úvod do umělé inteligence 12/12 11 / 37
Gramatiky a syntaktická analýza Lexikon pro agenta ve Wumpusově jeskyni
Lexikon pro agenta ve Wumpusově jeskyni
Gramatika přímo na slovech je příliš rozsáhlá. Řešením je rozdělení slov do
kategorií:
podst. jméno: Noun → zápach | vánek | třpyt | nic | wumpuse | jáma
| zlato | . . .
sloveso: Verb → jsem | je | vidím | cítím | působí | zapáchá
| jdu | . . .
příd. jméno: Adjective → levý | pravý | východní | jižní | . . .
příslovce: Adverb → tady | tam | blízko | vpředu | vpravo | vlevo
| východně | jižně | vzadu | . . .
vl. jméno: Name → Petr | Honza | Brno | FI MU | . . .
zájmeno: Pronoun → já | ty | mě | toho | ten | ta . . .
předložka: Preposition → do | v | na | u | . . .
spojka: Conjunction → a | nebo | ale | . . .
číslice: Digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
kategorie můžeme dělit na otevřené (vyvíjející se) a uzavřené (stálé)
Úvod do umělé inteligence 12/12 12 / 37
Gramatiky a syntaktická analýza Lexikon pro agenta ve Wumpusově jeskyni
Morfologická analýza
v češtině u lexikonu nestačí prostý výčet tvarů – je nutná morfologická analýza
(morfologie=tvarosloví)
skloňovaná a časovaná slova se rozkládají na segmenty
pří-lež-it-ost-n-ými:
pří – prefix; lež – kořen; it, ost, n – suffixy; ými – koncovka
Úvod do umělé inteligence 12/12 13 / 37
Gramatiky a syntaktická analýza Lexikon pro agenta ve Wumpusově jeskyni
Morfologická analýza
v češtině u lexikonu nestačí prostý výčet tvarů – je nutná morfologická analýza
(morfologie=tvarosloví)
skloňovaná a časovaná slova se rozkládají na segmenty
pří-lež-it-ost-n-ými:
pří – prefix; lež – kořen; it, ost, n – suffixy; ými – koncovka
základní tvar slova (lemma), podle koncovky se určují gramatické kategorie
# slovník základních gramatických kategorií: sl_druh(lemma, pád, číslo, rod) → slovo.
adj(’chytrý’, ’1’, ’j’, ’mž’) → ’chytrý’.
adj(’chytrý’, ’2’, ’j’, ’mž’) → ’chytrého’.
adj(’chytrý’, ’1’, ’mn’, ’mž’) → ’chytří’.
Úvod do umělé inteligence 12/12 13 / 37
Gramatiky a syntaktická analýza Lexikon pro agenta ve Wumpusově jeskyni
Morfologická analýza
v češtině u lexikonu nestačí prostý výčet tvarů – je nutná morfologická analýza
(morfologie=tvarosloví)
skloňovaná a časovaná slova se rozkládají na segmenty
pří-lež-it-ost-n-ými:
pří – prefix; lež – kořen; it, ost, n – suffixy; ými – koncovka
základní tvar slova (lemma), podle koncovky se určují gramatické kategorie
# slovník základních gramatických kategorií: sl_druh(lemma, pád, číslo, rod) → slovo.
adj(’chytrý’, ’1’, ’j’, ’mž’) → ’chytrý’.
adj(’chytrý’, ’2’, ’j’, ’mž’) → ’chytrého’.
adj(’chytrý’, ’1’, ’mn’, ’mž’) → ’chytří’.
reálná morfologická analýza ČJ – program Majka na FI MU
http://nlp.fi.muni.cz/projekty/wwwajka/
ajka>nejneuvěřitelněji
<s> nej-ne=uvěřiteln==ěji= (1022)
<l>uvěřitelně
<c>k6xMeNd3
ajka>hnát
<s> ==hná=t= (618)
<l>hnát
<c>k5eAmFaI
<s> =hnát=== (1030)
<l>hnát
<c>k1gInSc1,k1gInSc4
Úvod do umělé inteligence 12/12 13 / 37
Gramatiky a syntaktická analýza Lexikon pro agenta ve Wumpusově jeskyni
Gramatická pravidla pro agenta ve Wumpusově jeskyni
S → NP VP % já + cítím vánek
| S Conjunction S % já cítím vánek + a + já jdu
% na východ
NP → Pronoun % já
| Noun % jáma
| Adjective Noun % levá jáma
| Pronoun NP % toho + wumpuse
| Noun Digit ‘,’ Digit % pole + 3,4
| NP PP % jáma + na východě
| NP RelClause % toho wumpuse + ,který
% zapáchá
VP → Verb % zapáchá
| VP NP % cítím + vánek
| VP Adjective % je + třpytivý
| VP PP % jdu + na východ
| VP Adverb | Adverb VP % jdu + dopředu
PP → Preposition NP % na + východ
RelClause → ‘, který’ VP % ,který + zapáchá
Úvod do umělé inteligence 12/12 14 / 37
Gramatiky a syntaktická analýza Syntaktický strom
Syntaktický strom
syntaktický strom vzniká během syntaktické analýzy a dává záznam
o jejím průběhu:
S
NP
Adjective
Východní
Noun
jáma
VP
VP
Adverb
tady
VP
Verb
působí
NP
Noun
vánek
Úvod do umělé inteligence 12/12 15 / 37
Gramatiky a syntaktická analýza Syntaktický strom
Syntaktický strom
syntaktický strom vzniká během syntaktické analýzy a dává záznam
o jejím průběhu:
S
NP
Adjective
Východní
Noun
jáma
VP
VP
Adverb
tady
VP
Verb
působí
NP
Noun
vánek
Úvod do umělé inteligence 12/12 15 / 37
Gramatiky a syntaktická analýza Syntaktický strom
Syntaktický strom
syntaktický strom vzniká během syntaktické analýzy a dává záznam
o jejím průběhu:
S
NP
Adjective
Východní
Noun
jáma
VP
VP
Adverb
tady
VP
Verb
působí
NP
Noun
vánek
Úvod do umělé inteligence 12/12 15 / 37
Gramatiky a syntaktická analýza Syntaktický strom
Syntaktický strom
syntaktický strom vzniká během syntaktické analýzy a dává záznam
o jejím průběhu:
S
NP
Adjective
Východní
Noun
jáma
VP
VP
Adverb
tady
VP
Verb
působí
NP
Noun
vánek
Úvod do umělé inteligence 12/12 15 / 37
Gramatiky a syntaktická analýza Syntaktický strom
Syntaktický strom
syntaktický strom vzniká během syntaktické analýzy a dává záznam
o jejím průběhu:
S
NP
Adjective
Východní
Noun
jáma
VP
VP
Adverb
tady
VP
Verb
působí
NP
Noun
vánek
Úvod do umělé inteligence 12/12 15 / 37
Gramatiky a syntaktická analýza Syntaktický strom
Syntaktický strom
syntaktický strom vzniká během syntaktické analýzy a dává záznam
o jejím průběhu:
S
NP
Adjective
Východní
Noun
jáma
VP
VP
Adverb
tady
VP
Verb
působí
NP
Noun
vánek
Úvod do umělé inteligence 12/12 15 / 37
Gramatiky a syntaktická analýza Syntaktický strom
Konstrukce derivačního stromu
Neterminály opatříme argumentem:
sentence(sentence(NP,VP)) → noun_phrase(NP), verb_phrase(VP).
sentence(s(N,V)) → noun_phrase(N), verb_phrase(V).
noun_phrase(np(D,N)) → determiner(D), noun_phrase2(N).
noun_phrase(np(N)) → noun_phrase2(N).
noun_phrase2(np2(A,N)) → adjective(A), noun_phrase2(N).
noun_phrase2(np2(N)) → noun(N).
verb_phrase(vp(V)) → verb(V).
verb_phrase(vp(V,N)) → verb(V), noun_phrase(N).
determiner(det(the)) → ’the’.
determiner(det(a)) → ’a’.
adjective (adj(young)) → ’young’.
noun(noun(boy)) → ’boy’.
noun(noun(song)) → ’song’.
verb(verb( sings )) → ’sings’.
Úvod do umělé inteligence 12/12 16 / 37
Gramatiky a syntaktická analýza Syntaktický strom
Konstrukce derivačního stromu
Neterminály opatříme argumentem:
sentence(sentence(NP,VP)) → noun_phrase(NP), verb_phrase(VP).
sentence(s(N,V)) → noun_phrase(N), verb_phrase(V).
noun_phrase(np(D,N)) → determiner(D), noun_phrase2(N).
noun_phrase(np(N)) → noun_phrase2(N).
noun_phrase2(np2(A,N)) → adjective(A), noun_phrase2(N).
noun_phrase2(np2(N)) → noun(N).
verb_phrase(vp(V)) → verb(V).
verb_phrase(vp(V,N)) → verb(V), noun_phrase(N).
determiner(det(the)) → ’the’.
determiner(det(a)) → ’a’.
adjective (adj(young)) → ’young’.
noun(noun(boy)) → ’boy’.
noun(noun(song)) → ’song’.
verb(verb( sings )) → ’sings’.
sentence(Tree, [’the’, ’young’, ’boy’, ’sings’, ’a’, ’song’])
Tree=s(np(det(’the’),np2(adj(’young’),np2(noun(’boy’)))),
vp(verb(’sings’),np(det(’a’),np2(noun(’song’)))))
Úvod do umělé inteligence 12/12 16 / 37
Gramatiky a syntaktická analýza Syntaktický strom
Derivační strom analýzy v gramatikách
sentence(Tree, [’the’, ’young’, ’boy’, ’sings’, ’a’, ’song’] , [ ]).
Tree=s(np(det(’the’), np2(adj(’young’), np2(noun(’boy’)))),
vp(verb(’sings’), np(det(’a’), np2(noun(’song’)))))
s
np
det
the
np2
adj
young
np2
noun
boy
vp
verb
sings
np
det
a
np2
noun
song
Úvod do umělé inteligence 12/12 17 / 37
Gramatiky a syntaktická analýza Test na shodu
Test na shodu
Pokud však rozšíříme slovník:
noun(noun(boys)) → ’boys’.
verb(verb(sing)) → ’sing’.
Narazíme na problém se shodou v čísle:
sentence(_,[’a’, ’young’, ’boys’, ’sings’]).
True
sentence(_,[’a’, ’boy’, ’sing’]).
True
Úvod do umělé inteligence 12/12 18 / 37
Gramatiky a syntaktická analýza Test na shodu
Test na shodu
Pokud však rozšíříme slovník:
noun(noun(boys)) → ’boys’.
verb(verb(sing)) → ’sing’.
Narazíme na problém se shodou v čísle:
sentence(_,[’a’, ’young’, ’boys’, ’sings’]).
True
sentence(_,[’a’, ’boy’, ’sing’]).
True
Proto rozšíříme neterminály o další argument Num, ve kterém můžeme
testovat shodu:
sentence(sentence(NP,VP)) → noun_phrase(NP,Num), verb_phrase(VP,Num).
Úvod do umělé inteligence 12/12 18 / 37
Gramatiky a syntaktická analýza Test na shodu
Gramatika s testy na shodu
sentence(sentence(N,V)) → noun_phrase(N,Num), verb_phrase(V,Num).
noun_phrase(np(D,N),Num) → determiner(D,Num), noun_phrase2(N,Num).
noun_phrase(np(N),Num) → noun_phrase2(N,Num).
noun_phrase2(np2(A,N),Num) → adjective(A), noun_phrase2(N,Num).
noun_phrase2(np2(N),Num) → noun(N,Num).
verb_phrase(vp(V),Num) → verb(V,Num).
verb_phrase(vp(V,N),Num) → verb(V,Num), noun_phrase(N,Num1).
determiner(det(the),_) → ’the’. noun(noun(boy),sg) → ’boy’.
determiner(det(a),sg) → ’a’. noun(noun(song),sg) → ’song’.
verb(verb(sings),sg) → ’sings’. noun(noun(boys),pl) → ’boys’.
verb(verb(sing), pl) → ’sing’. noun(noun(songs),pl) → ’songs’.
adjective (adj(young)) → ’young’.
Úvod do umělé inteligence 12/12 19 / 37
Gramatiky a syntaktická analýza Test na shodu
Gramatika s testy na shodu
sentence(sentence(N,V)) → noun_phrase(N,Num), verb_phrase(V,Num).
noun_phrase(np(D,N),Num) → determiner(D,Num), noun_phrase2(N,Num).
noun_phrase(np(N),Num) → noun_phrase2(N,Num).
noun_phrase2(np2(A,N),Num) → adjective(A), noun_phrase2(N,Num).
noun_phrase2(np2(N),Num) → noun(N,Num).
verb_phrase(vp(V),Num) → verb(V,Num).
verb_phrase(vp(V,N),Num) → verb(V,Num), noun_phrase(N,Num1).
determiner(det(the),_) → ’the’. noun(noun(boy),sg) → ’boy’.
determiner(det(a),sg) → ’a’. noun(noun(song),sg) → ’song’.
verb(verb(sings),sg) → ’sings’. noun(noun(boys),pl) → ’boys’.
verb(verb(sing), pl) → ’sing’. noun(noun(songs),pl) → ’songs’.
adjective (adj(young)) → ’young’.
sentence(_, [’a’, ’young’, ’boys’, ’sings’]).
False
Úvod do umělé inteligence 12/12 19 / 37
Gramatiky a syntaktická analýza Test na shodu
Gramatika s testy na shodu
sentence(sentence(N,V)) → noun_phrase(N,Num), verb_phrase(V,Num).
noun_phrase(np(D,N),Num) → determiner(D,Num), noun_phrase2(N,Num).
noun_phrase(np(N),Num) → noun_phrase2(N,Num).
noun_phrase2(np2(A,N),Num) → adjective(A), noun_phrase2(N,Num).
noun_phrase2(np2(N),Num) → noun(N,Num).
verb_phrase(vp(V),Num) → verb(V,Num).
verb_phrase(vp(V,N),Num) → verb(V,Num), noun_phrase(N,Num1).
determiner(det(the),_) → ’the’. noun(noun(boy),sg) → ’boy’.
determiner(det(a),sg) → ’a’. noun(noun(song),sg) → ’song’.
verb(verb(sings),sg) → ’sings’. noun(noun(boys),pl) → ’boys’.
verb(verb(sing), pl) → ’sing’. noun(noun(songs),pl) → ’songs’.
adjective (adj(young)) → ’young’.
sentence(_, [’a’, ’young’, ’boys’, ’sings’]).
False
sentence(_, [’the’, ’boys’, ’sings’, ’a’, ’song’]).
False
Úvod do umělé inteligence 12/12 19 / 37
Gramatiky a syntaktická analýza Test na shodu
Gramatika s testy na shodu
sentence(sentence(N,V)) → noun_phrase(N,Num), verb_phrase(V,Num).
noun_phrase(np(D,N),Num) → determiner(D,Num), noun_phrase2(N,Num).
noun_phrase(np(N),Num) → noun_phrase2(N,Num).
noun_phrase2(np2(A,N),Num) → adjective(A), noun_phrase2(N,Num).
noun_phrase2(np2(N),Num) → noun(N,Num).
verb_phrase(vp(V),Num) → verb(V,Num).
verb_phrase(vp(V,N),Num) → verb(V,Num), noun_phrase(N,Num1).
determiner(det(the),_) → ’the’. noun(noun(boy),sg) → ’boy’.
determiner(det(a),sg) → ’a’. noun(noun(song),sg) → ’song’.
verb(verb(sings),sg) → ’sings’. noun(noun(boys),pl) → ’boys’.
verb(verb(sing), pl) → ’sing’. noun(noun(songs),pl) → ’songs’.
adjective (adj(young)) → ’young’.
sentence(_, [’a’, ’young’, ’boys’, ’sings’]).
False
sentence(_, [’the’, ’boys’, ’sings’, ’a’, ’song’]).
False
sentence(_, [’the’, ’boys’, ’sing’, ’a’, ’song’]).
True
Úvod do umělé inteligence 12/12 19 / 37
Gramatiky a syntaktická analýza Test na shodu
Podmínky v těle pravidel
Gramatiky mohou mít pomocné podmínky v těle pravidel (kód)
CFG pro vyhodnocení artimetického výrazu: E → T + E | T − E | T
T → F ∗ T | F/T | F
F → (E) | f
zapíšeme včetně výpočtu hodnoty výrazu:
expr(X) → term(Y), ’+’, expr(Z), {X is Y+Z}.
expr(X) → term(Y), ’-’, expr(Z), {X is Y-Z}.
expr(X) → term(X).
term(X) → factor(Y), ’*’, term(Z), {X is Y∗Z}.
term(X) → factor(Y), ’/’, term(Z), {X is Y/Z}.
term(X) → factor(X).
factor (X) → ’(’, expr(X), ’)’.
factor (X) → X, {integer(X)}.
Úvod do umělé inteligence 12/12 20 / 37
Gramatiky a syntaktická analýza Test na shodu
Podmínky v těle pravidel
Gramatiky mohou mít pomocné podmínky v těle pravidel (kód)
CFG pro vyhodnocení artimetického výrazu: E → T + E | T − E | T
T → F ∗ T | F/T | F
F → (E) | f
zapíšeme včetně výpočtu hodnoty výrazu:
expr(X) → term(Y), ’+’, expr(Z), {X is Y+Z}.
expr(X) → term(Y), ’-’, expr(Z), {X is Y-Z}.
expr(X) → term(X).
term(X) → factor(Y), ’*’, term(Z), {X is Y∗Z}.
term(X) → factor(Y), ’/’, term(Z), {X is Y/Z}.
term(X) → factor(X).
factor (X) → ’(’, expr(X), ’)’.
factor (X) → X, {integer(X)}.
# 3 + 4/2 − (2∗6/3 + 2) = −1
expr(X,[’3’,’+’,’4’,’/’,’2’,’-’,’(’,’2’,’*’,’6’,’/’,’3’,’+’,’2’,’)’]).
X = -1
Úvod do umělé inteligence 12/12 20 / 37
Gramatiky a syntaktická analýza Generativní síla gramatik
Generativní síla gramatik
Generativní (rozpoznávací) síla analyzačních gramatik je často větší než CFG
např. jazyk anbncn:
abc → a(N), b(N), c(N).
a(0) → []. # ϵ
a(s(N)) → ’a’, a(N).
b(0) → [].
b(s(N)) → ’b’, b(N).
c(0) → [].
c(s(N)) → ’c’, c(N).
Úvod do umělé inteligence 12/12 21 / 37
Gramatiky a syntaktická analýza Generativní síla gramatik
Generativní síla gramatik
Generativní (rozpoznávací) síla analyzačních gramatik je často větší než CFG
např. jazyk anbncn:
abc → a(N), b(N), c(N).
a(0) → []. # ϵ
a(s(N)) → ’a’, a(N).
b(0) → [].
b(s(N)) → ’b’, b(N).
c(0) → [].
c(s(N)) → ’c’, c(N).
abc(X,[]).
Úvod do umělé inteligence 12/12 21 / 37
Gramatiky a syntaktická analýza Generativní síla gramatik
Generativní síla gramatik
Generativní (rozpoznávací) síla analyzačních gramatik je často větší než CFG
např. jazyk anbncn:
abc → a(N), b(N), c(N).
a(0) → []. # ϵ
a(s(N)) → ’a’, a(N).
b(0) → [].
b(s(N)) → ’b’, b(N).
c(0) → [].
c(s(N)) → ’c’, c(N).
abc(X,[]).
X = []
Úvod do umělé inteligence 12/12 21 / 37
Gramatiky a syntaktická analýza Generativní síla gramatik
Generativní síla gramatik
Generativní (rozpoznávací) síla analyzačních gramatik je často větší než CFG
např. jazyk anbncn:
abc → a(N), b(N), c(N).
a(0) → []. # ϵ
a(s(N)) → ’a’, a(N).
b(0) → [].
b(s(N)) → ’b’, b(N).
c(0) → [].
c(s(N)) → ’c’, c(N).
abc(X,[]).
X = []
X = [’a’, ’b’, ’c’]
Úvod do umělé inteligence 12/12 21 / 37
Gramatiky a syntaktická analýza Generativní síla gramatik
Generativní síla gramatik
Generativní (rozpoznávací) síla analyzačních gramatik je často větší než CFG
např. jazyk anbncn:
abc → a(N), b(N), c(N).
a(0) → []. # ϵ
a(s(N)) → ’a’, a(N).
b(0) → [].
b(s(N)) → ’b’, b(N).
c(0) → [].
c(s(N)) → ’c’, c(N).
abc(X,[]).
X = []
X = [’a’, ’b’, ’c’]
X = [’a’, ’a’, ’b’, ’b’, ’c’, ’c’]
Úvod do umělé inteligence 12/12 21 / 37
Gramatiky a syntaktická analýza Generativní síla gramatik
Generativní síla gramatik
Generativní (rozpoznávací) síla analyzačních gramatik je často větší než CFG
např. jazyk anbncn:
abc → a(N), b(N), c(N).
a(0) → []. # ϵ
a(s(N)) → ’a’, a(N).
b(0) → [].
b(s(N)) → ’b’, b(N).
c(0) → [].
c(s(N)) → ’c’, c(N).
abc(X,[]).
X = []
X = [’a’, ’b’, ’c’]
X = [’a’, ’a’, ’b’, ’b’, ’c’, ’c’]
X = [’a’, ’a’, ’a’, ’b’, ’b’, ’b’, ’c’, ’c’, ’c’]
...
Úvod do umělé inteligence 12/12 21 / 37
Gramatiky a syntaktická analýza Strojové učení
Syntaktická analýza pomocí strojového učení
využití anotovaných stromových korpusů (treebanks)
lidé anotují textový korpus – doplní syntaktické stromy
strojové učení hledá pravidla/váhy parametrů
univerzální napříč jazyky (do jisté míry)
anotování je drahé
modifikace pro různé účely je obtížnější
často není dost dat
Úvod do umělé inteligence 12/12 22 / 37
Gramatiky a syntaktická analýza Strojové učení
Závislostní analýza
jedna hrana pro každé slovo
• hlava – řídící slovo
• závislé/rozvíjející slovo – modifikátor
• typ – popisek hrany
obtížné pro neprojektivní stromy
Úvod do umělé inteligence 12/12 23 / 37
Gramatiky a syntaktická analýza Strojové učení
Online učení skóre hrany
učení matice vah rysů w
w(k+1)
= w(k)
+ f(X, Y+
) − f(X, Y−
)
Úvod do umělé inteligence 12/12 24 / 37
Analýza přirozeného jazyka Význam syntaktické analýzy
Obsah
1 Komunikace
Přirozený jazyk – prostředek komunikace
Řečové akty
Komunikační fáze (při informování)
2 Gramatiky a syntaktická analýza
Gramatiky pro analýzu jazyka
Lexikon pro agenta ve Wumpusově jeskyni
Syntaktický strom
Test na shodu
Syntaktická analýza pomocí strojového učení
3 Analýza přirozeného jazyka
Význam syntaktické analýzy
Problémy při analýze přirozeného jazyka
Reálná syntaktická analýza přirozeného jazyka
4 PA026 – Projekt z umělé inteligence
Úvod do umělé inteligence 12/12 25 / 37
Analýza přirozeného jazyka Význam syntaktické analýzy
Význam syntaktické analýzy
analýza syntaxe je podkladem pro analýzu významu
většina teorií analýzy významu využívá princip kompozicionality:
Význam složeného výrazu je funkcí významu jednotlivých podvýrazů
proces sémantické analýzy:
• buď vychází z výsledků syntaktické analýzy
• nebo probíhá současně se syntaktickou analýzou; pak může zasahovat i do
tvorby syntaktického stromu
Úvod do umělé inteligence 12/12 26 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Problémy při analýze přirozeného jazyka
víceznačnost
anaforické výrazy
indexické výrazy
nejasnost
nekompozicionalita
struktura promluvy
metonymie
metafory
Úvod do umělé inteligence 12/12 27 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Víceznačnost
ambiguity
víceznačnost může být lexikální, syntaktická, sémantická a referenční
Úvod do umělé inteligence 12/12 28 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Víceznačnost
ambiguity
víceznačnost může být lexikální, syntaktická, sémantická a referenční
lexikální – “stát,” “žena,” “hnát”
Úvod do umělé inteligence 12/12 28 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Víceznačnost
ambiguity
víceznačnost může být lexikální, syntaktická, sémantická a referenční
lexikální – “stát,” “žena,” “hnát”
syntaktická – “Jím špagety s masem.”
Úvod do umělé inteligence 12/12 28 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Víceznačnost
ambiguity
víceznačnost může být lexikální, syntaktická, sémantická a referenční
lexikální – “stát,” “žena,” “hnát”
syntaktická – “Jím špagety s masem.”
“Jím špagety se salátem.”
Úvod do umělé inteligence 12/12 28 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Víceznačnost
ambiguity
víceznačnost může být lexikální, syntaktická, sémantická a referenční
lexikální – “stát,” “žena,” “hnát”
syntaktická – “Jím špagety s masem.”
“Jím špagety se salátem.”
“Jím špagety s použitím vidličky.”
Úvod do umělé inteligence 12/12 28 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Víceznačnost
ambiguity
víceznačnost může být lexikální, syntaktická, sémantická a referenční
lexikální – “stát,” “žena,” “hnát”
syntaktická – “Jím špagety s masem.”
“Jím špagety se salátem.”
“Jím špagety s použitím vidličky.”
“Jím špagety se sebezapřením.”
Úvod do umělé inteligence 12/12 28 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Víceznačnost
ambiguity
víceznačnost může být lexikální, syntaktická, sémantická a referenční
lexikální – “stát,” “žena,” “hnát”
syntaktická – “Jím špagety s masem.”
“Jím špagety se salátem.”
“Jím špagety s použitím vidličky.”
“Jím špagety se sebezapřením.”
“Jím špagety s přítelem.”
Úvod do umělé inteligence 12/12 28 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Víceznačnost
ambiguity
víceznačnost může být lexikální, syntaktická, sémantická a referenční
lexikální – “stát,” “žena,” “hnát”
syntaktická – “Jím špagety s masem.”
“Jím špagety se salátem.”
“Jím špagety s použitím vidličky.”
“Jím špagety se sebezapřením.”
“Jím špagety s přítelem.”
sémantická – “Jeřáb je vysoký.” “Viděli jsme veliké oko.”
Úvod do umělé inteligence 12/12 28 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Víceznačnost
ambiguity
víceznačnost může být lexikální, syntaktická, sémantická a referenční
lexikální – “stát,” “žena,” “hnát”
syntaktická – “Jím špagety s masem.”
“Jím špagety se salátem.”
“Jím špagety s použitím vidličky.”
“Jím špagety se sebezapřením.”
“Jím špagety s přítelem.”
sémantická – “Jeřáb je vysoký.” “Viděli jsme veliké oko.”
referenční – “Oni přišli pozdě.” “Můžeš mi půjčit knihu?”
“Ředitel vyhodil dělníka, protože (on) byl agresivní.”
SliDo
Úvod do umělé inteligence 12/12 28 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Anaforické a indexické výrazy
anaforické výrazy:
anaphora
používají zájmena pro odkazování na objekty zmíněné dříve
Úvod do umělé inteligence 12/12 29 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Anaforické a indexické výrazy
anaforické výrazy:
anaphora
používají zájmena pro odkazování na objekty zmíněné dříve
“Poté co se Honza s Marií rozhodli se vzít, (oni) vyhledali kněze, aby je oddal.”
Úvod do umělé inteligence 12/12 29 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Anaforické a indexické výrazy
anaforické výrazy:
anaphora
používají zájmena pro odkazování na objekty zmíněné dříve
“Poté co se Honza s Marií rozhodli se vzít, (oni) vyhledali kněze, aby je oddal.”
Úvod do umělé inteligence 12/12 29 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Anaforické a indexické výrazy
anaforické výrazy:
anaphora
používají zájmena pro odkazování na objekty zmíněné dříve
“Poté co se Honza s Marií rozhodli se vzít, (oni) vyhledali kněze, aby je oddal.”
“Marie uviděla ve výloze prstýnek a požádala Honzu, aby jí ho koupil.”
Úvod do umělé inteligence 12/12 29 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Anaforické a indexické výrazy
anaforické výrazy:
anaphora
používají zájmena pro odkazování na objekty zmíněné dříve
“Poté co se Honza s Marií rozhodli se vzít, (oni) vyhledali kněze, aby je oddal.”
“Marie uviděla ve výloze prstýnek a požádala Honzu, aby jí ho koupil.”
Úvod do umělé inteligence 12/12 29 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Anaforické a indexické výrazy
anaforické výrazy:
anaphora
používají zájmena pro odkazování na objekty zmíněné dříve
“Poté co se Honza s Marií rozhodli se vzít, (oni) vyhledali kněze, aby je oddal.”
“Marie uviděla ve výloze prstýnek a požádala Honzu, aby jí ho koupil.”
indexické výrazy:
indexicals
odkazují se na údaje v jiných částech promluvy nebo mimo promluvu
Úvod do umělé inteligence 12/12 29 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Anaforické a indexické výrazy
anaforické výrazy:
anaphora
používají zájmena pro odkazování na objekty zmíněné dříve
“Poté co se Honza s Marií rozhodli se vzít, (oni) vyhledali kněze, aby je oddal.”
“Marie uviděla ve výloze prstýnek a požádala Honzu, aby jí ho koupil.”
indexické výrazy:
indexicals
odkazují se na údaje v jiných částech promluvy nebo mimo promluvu
“Já jsem tady.”
Úvod do umělé inteligence 12/12 29 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Anaforické a indexické výrazy
anaforické výrazy:
anaphora
používají zájmena pro odkazování na objekty zmíněné dříve
“Poté co se Honza s Marií rozhodli se vzít, (oni) vyhledali kněze, aby je oddal.”
“Marie uviděla ve výloze prstýnek a požádala Honzu, aby jí ho koupil.”
indexické výrazy:
indexicals
odkazují se na údaje v jiných částech promluvy nebo mimo promluvu
“Já jsem tady.”
“Proč jsi to udělal?”
Úvod do umělé inteligence 12/12 29 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Metafora a metonymie
metafora:
metaphor
použití slov v přeneseném významu (na základě podobnosti), často
systematicky
Úvod do umělé inteligence 12/12 30 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Metafora a metonymie
metafora:
metaphor
použití slov v přeneseném významu (na základě podobnosti), často
systematicky
“Zkoušel jsem ten proces zabít, ale nešlo to.”
Úvod do umělé inteligence 12/12 30 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Metafora a metonymie
metafora:
metaphor
použití slov v přeneseném významu (na základě podobnosti), často
systematicky
“Zkoušel jsem ten proces zabít, ale nešlo to.”
“Bouře se vzteká.”
Úvod do umělé inteligence 12/12 30 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Metafora a metonymie
metafora:
metaphor
použití slov v přeneseném významu (na základě podobnosti), často
systematicky
“Zkoušel jsem ten proces zabít, ale nešlo to.”
“Bouře se vzteká.”
metonymie:
metonymy
používání jména jedné věci pro (často zkrácené) označení věci jiné
Úvod do umělé inteligence 12/12 30 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Metafora a metonymie
metafora:
metaphor
použití slov v přeneseném významu (na základě podobnosti), často
systematicky
“Zkoušel jsem ten proces zabít, ale nešlo to.”
“Bouře se vzteká.”
metonymie:
metonymy
používání jména jedné věci pro (často zkrácené) označení věci jiné
“Čtu Shakespeara.”
Úvod do umělé inteligence 12/12 30 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Metafora a metonymie
metafora:
metaphor
použití slov v přeneseném významu (na základě podobnosti), často
systematicky
“Zkoušel jsem ten proces zabít, ale nešlo to.”
“Bouře se vzteká.”
metonymie:
metonymy
používání jména jedné věci pro (často zkrácené) označení věci jiné
“Čtu Shakespeara.”
“Chrysler oznámil rekordní zisk.”
Úvod do umělé inteligence 12/12 30 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Metafora a metonymie
metafora:
metaphor
použití slov v přeneseném významu (na základě podobnosti), často
systematicky
“Zkoušel jsem ten proces zabít, ale nešlo to.”
“Bouře se vzteká.”
metonymie:
metonymy
používání jména jedné věci pro (často zkrácené) označení věci jiné
“Čtu Shakespeara.”
“Chrysler oznámil rekordní zisk.”
“Ten pstruh na másle u stolu 3 chce další pivo.”
Úvod do umělé inteligence 12/12 30 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Nekompozicionalita
noncompositionality
příklady porušení pravidla kompozicionality u ustálených termínů nebo
přednost jiného možného významu při určitých spojeních
Úvod do umělé inteligence 12/12 31 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Nekompozicionalita
noncompositionality
příklady porušení pravidla kompozicionality u ustálených termínů nebo
přednost jiného možného významu při určitých spojeních
“aligátoří boty,” “basketbalové boty,” “dětské boty”
Úvod do umělé inteligence 12/12 31 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Nekompozicionalita
noncompositionality
příklady porušení pravidla kompozicionality u ustálených termínů nebo
přednost jiného možného významu při určitých spojeních
“aligátoří boty,” “basketbalové boty,” “dětské boty”
“pata sloupu”
Úvod do umělé inteligence 12/12 31 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Nekompozicionalita
noncompositionality
příklady porušení pravidla kompozicionality u ustálených termínů nebo
přednost jiného možného významu při určitých spojeních
“aligátoří boty,” “basketbalové boty,” “dětské boty”
“pata sloupu”
“červená kniha,” “červené pero”
Úvod do umělé inteligence 12/12 31 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Nekompozicionalita
noncompositionality
příklady porušení pravidla kompozicionality u ustálených termínů nebo
přednost jiného možného významu při určitých spojeních
“aligátoří boty,” “basketbalové boty,” “dětské boty”
“pata sloupu”
“červená kniha,” “červené pero”
“bílý trpaslík”
Úvod do umělé inteligence 12/12 31 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Nekompozicionalita
noncompositionality
příklady porušení pravidla kompozicionality u ustálených termínů nebo
přednost jiného možného významu při určitých spojeních
“aligátoří boty,” “basketbalové boty,” “dětské boty”
“pata sloupu”
“červená kniha,” “červené pero”
“bílý trpaslík”
“dřevěný pes,” “umělá tráva”
Úvod do umělé inteligence 12/12 31 / 37
Analýza přirozeného jazyka Problémy při analýze přirozeného jazyka
Nekompozicionalita
noncompositionality
příklady porušení pravidla kompozicionality u ustálených termínů nebo
přednost jiného možného významu při určitých spojeních
“aligátoří boty,” “basketbalové boty,” “dětské boty”
“pata sloupu”
“červená kniha,” “červené pero”
“bílý trpaslík”
“dřevěný pes,” “umělá tráva”
“velká molekula”
Úvod do umělé inteligence 12/12 31 / 37
Analýza přirozeného jazyka Reálná syntaktická analýza přirozeného jazyka
Reálná syntaktická analýza přirozeného jazyka
velice rozsáhlé gramatiky (desítky až stovky tisíc pravidel)
silná víceznačnost – někdy až obrovské množství (>milióny) možných
syntaktických stromů
Obehnat Šalounův pomník mistra Jana Husa na pražském Staroměstském
náměstí živým plotem z hustých keřů s trny navrhuje občanské
sdružení Společnost Jana Jesenia.
existují efektivní algoritmy pro takové gramatiky
např. tabulkový analyzátor (chart parser), beží v O(n3), tisíce
slov/sekundu
Úvod do umělé inteligence 12/12 32 / 37
Analýza přirozeného jazyka Reálná syntaktická analýza přirozeného jazyka
Reálná syntaktická analýza přirozeného jazyka
velice rozsáhlé gramatiky (desítky až stovky tisíc pravidel)
silná víceznačnost – někdy až obrovské množství (>milióny) možných
syntaktických stromů
Obehnat Šalounův pomník mistra Jana Husa na pražském Staroměstském
náměstí živým plotem z hustých keřů s trny navrhuje
občanské sdružení Společnost Jana Jesenia.
existují efektivní algoritmy pro takové gramatiky
např. tabulkový analyzátor (chart parser), beží v O(n3), tisíce
slov/sekundu
Úvod do umělé inteligence 12/12 32 / 37
Analýza přirozeného jazyka Reálná syntaktická analýza přirozeného jazyka
Příklad stromu analýzy v systému synt
start
sentence
clause
np
ADJ
Postižených np
N
cestovek
VBL
bylo part_adv
ADV
víc
’,’
, clause
np
np
NUMK
dvě
pp
PREP
z np
PRONPER
nich
VL
udělaly np
N
bankrot
’,’
, clause
VL
vyprávěla np
PRONPER
nám
np
np_prop_names
NPR
Ludmila
NPR
Janočková
’,’
, np
np
N
majitelka
np
N
agentury
ends
’.’
.
http://nlp.fi.muni.cz/projekty/wwwsynt/
Úvod do umělé inteligence 12/12 33 / 37
Analýza přirozeného jazyka Reálná syntaktická analýza přirozeného jazyka
Příklad logické analýzy v systému synt
Když je pořádná zima s množstvím sněhu, ani velký nával návštěvníků
přírodě příliš nevadí.
λw1λt2 když_aniw1t2
,
λw3λt4(∃i5) [pořádnýw3t4
, i5] ∧ [zimaw3t4 , i5] ∧
sw3t4 , [Of, množství, sníh] w3t4
, i5 ,
λw6λt7 Not, Truew6t7 , λw8λt9(∃x10)(∃i11)(∃i12)
Doesw8t9 , i12, [Impw8
, x10] ∧ [přírodaw8t9
, i11] ∧
x10 ⊂ [vadit, i11]w8 ∧ [příliš, x10] ∧
velký, [Of, nával, návštěvník] w8t9
, i12 . . . oτω
Úvod do umělé inteligence 12/12 34 / 37
Analýza přirozeného jazyka Reálná syntaktická analýza přirozeného jazyka
NLP – Natural Language Processing
část umělé inteligence zaměřená na zpracování textu a řeči
Významné úkoly v NLP (předmět IA161)
analýza textu v přirozeném jazyce – morfologická, syntaktická, sémantická
generování textu v přirozeném jazyce
syntéza a rozpoznávání řeči
získávání informací (Information retrieval)
extrakce informací (Information extraction, Text mining)
určení typu dokumentu (Text classification/clustering)
strojový překlad (Machine translation)
odpovídání na otázky (Question answering)
korektura textu (Spell-checking, Grammar checking)
výtah z textu (Text summarization)
určení stylu dokumentu/autora (Stylometry, Authorship attribution)
porozumění (obsahu) textu (Natural language understanding)
komunikace člověk-stroj (Man-machine communication, Chatbots)
SliDo https://beta.openai.com/playground
Úvod do umělé inteligence 12/12 35 / 37
PA026 – Projekt z umělé inteligence
Obsah
1 Komunikace
Přirozený jazyk – prostředek komunikace
Řečové akty
Komunikační fáze (při informování)
2 Gramatiky a syntaktická analýza
Gramatiky pro analýzu jazyka
Lexikon pro agenta ve Wumpusově jeskyni
Syntaktický strom
Test na shodu
Syntaktická analýza pomocí strojového učení
3 Analýza přirozeného jazyka
Význam syntaktické analýzy
Problémy při analýze přirozeného jazyka
Reálná syntaktická analýza přirozeného jazyka
4 PA026 – Projekt z umělé inteligence
Úvod do umělé inteligence 12/12 36 / 37
PA026 – Projekt z umělé inteligence
PA026 – Projekt z umělé inteligence
navazuje na předmět PB016 Úvod do umělé inteligence
volba programovacího jazyka není omezena
samostatná volba tématu v rozsahu ≥ 1 semestru
předmět probíhá jako prezentace a konzultace
zajímavé výsledky (http://nlp.fi.muni.cz/uiprojekt/)
• projekt elnet – > 5 let spolupráce na grantových projektech simulace
elektrorozvodných sítí
• projekt plagiaty_z_webu – vyhledávání shod s dokumenty na celém webu
• projekt robot_johnny_5 – sestavení a “oživení” robota – mobilního počítače
• robot Karel Pepper – https://nlp.fi.muni.cz/projects/pepper
Úvod do umělé inteligence 12/12 37 / 37