´ Uvod do umˇel´e inteligence, jazyk Prolog Aleˇs Hor´ak E-mail:
[email protected] http://nlp.fi.muni.cz/uui/
Obsah: ◮
Organizace pˇredmˇetu PB016
◮
Co je “umˇel´a inteligence”
◮
Struˇcn´e shrnut´ı Prologu ´ Uvod do umˇ el´ e inteligence 1/12
1 / 19
Organizace pˇredmˇ etu PB016
Organizace pˇredmˇetu PB016 Hodnocen´ı pˇredmˇ etu: ◮ pr˚ ubˇ eˇ zn´ a p´ısemka (max 32 bod˚ u) • v 1/2 semestru – v r´ amci 6. pˇredn´aˇsky, pro vˇsechny jedin´y term´ın ◮
z´ avˇ ereˇ cn´ a p´ısemka (max 96 bod˚ u) • dva ˇr´ adn´e a jeden opravn´y term´ın
◮ ◮ ◮ ◮
hodnocen´ı – souˇcet bod˚ u za obˇe p´ısemky (max 128 bod˚ u) zn´amka A za v´ıce neˇz 115 bod˚ u zn´amka E za v´ıce neˇz 63 bod˚ u rozd´ıly zk, k, z – r˚ uzn´e limity nˇekteˇr´ı m˚ uˇzou z´ıskat body za studentsk´ e refer´ aty • aˇ z 20 bod˚ u – za kvalitn´ı text (cca 5 stran) + 10–20 minut refer´at • nutn´ e pˇred pr˚ ubˇeˇznou p´ısemkou domluvit t´ ema – projekt/program,
algoritmus z N´aplnˇe pˇredmˇetu • domluva e-mailem – n´ avrh t´ematu, kter´y mus´ı proj´ıt schv´alen´ım ◮
◮
kdo oprav´ı chybu nebo vylepˇs´ı demo pˇr´ıklady, m˚ uˇze dostat 1–5 bod˚ u (celkem max 5) aˇz 20 bod˚ u za pˇrepis vˇsech demo pˇr´ıklad˚ u do funkˇcn´ı podoby v Pythonu ´ Uvod do umˇ el´ e inteligence 1/12
2 / 19
Organizace pˇredmˇ etu PB016
Z´ akladn´ı informace
Z´akladn´ı informace ◮
pˇredn´aˇska je nepovinn´a
◮
cviˇcen´ı – samostudium, v r´amci “tˇret´ıho kreditu”
◮
web str´anka pˇredmˇetu – http://nlp.fi.muni.cz/uui/
◮
http://nlp.fi.muni.cz/uui/priklady/ – demo pˇr´ıklady
◮
slajdy – pr˚ ubˇeˇznˇe doplˇ nov´any na webu pˇredmˇetu
◮
kontakt na pˇredn´aˇsej´ıc´ıho – Aleˇs Hor´ak
(Subject: PB016 . . . ) literatura:
◮
• Russell, S. a Norvig, P.: Artificial Intelligence: A Modern Approach,
3rd ed., Prentice Hall, 2010. (prezenˇcnˇe v knihovnˇe) • Bratko, I.: Prolog Programming for Artificial Intelligence, Addison-Wesley, 2001. (prezenˇcnˇe v knihovnˇe) • slajdy na webu pˇredmˇ etu • Jirk˚ u, Petr: Programov´ an´ı v jazyku Prolog, Praha : St´atn´ı nakladatelstv´ı technick´e literatury, 1991. ´ Uvod do umˇ el´ e inteligence 1/12
3 / 19
Organizace pˇredmˇ etu PB016
N´ aplˇ n pˇredmˇ etu
N´aplˇn pˇredmˇetu 1
u ´vod do UI, jazyk Prolog
2
operace na datov´ych struktur´ach
(3.10.)
3
prohled´av´an´ı stavov´eho prostoru
(10.10.)
4
heuristiky, best-first search, A* search
5
dekompozice probl´emu, AND/OR grafy
6
hry a z´akladn´ı hern´ı strategie, pr˚ ubˇ eˇ zn´ a p´ısemka
7
probl´emy s omezuj´ıc´ımi podm´ınkami
8
logick´y agent, v´yrokov´a logika
9
logika prvn´ıho ˇr´adu a transparentn´ı intenzion´aln´ı logika
10
reprezentace a vyvozov´an´ı znalost´ı (28.11.)
11
uˇcen´ı, rozhodovac´ı stromy, neuronov´e s´ıtˇe
12
zpracov´an´ı pˇrirozen´eho jazyka
(26.9.)
(17.10.) (24.10.) (31.10.)
(7.11.)
(14.11.)
(12.12.)
´ Uvod do umˇ el´ e inteligence 1/12
4 / 19
(5.12.)
(21.11.)
Co je “umˇ el´ a inteligence”
Co je “umˇel´a inteligence” ◮ syst´ em, kter´ y se chov´ a jako ˇ clovˇ ek
Turing˚ uv test (1950)
zahrnuje: ◮
zpracov´an´ı pˇrirozen´eho jazyka (NLP)
◮
reprezentaci znalost´ı (KRepresentation)
◮
vyvozov´an´ı znalost´ı (KReasoning)
◮
strojov´e uˇcen´ı
◮
(poˇc´ıtaˇcov´e vidˇen´ı)
◮
(robotiku)
od 1991 – Loebnerova cena (Loebner Prize) → kaˇzd´y rok $4.000 za “nejlidˇstˇejˇs´ı” program, nab´ız´ı $100.000 a zlat´a medaile za sloˇzen´ı cel´eho Turingova testu ´ Uvod do umˇ el´ e inteligence 1/12
5 / 19
Co je “umˇ el´ a inteligence”
◮ syst´ em, kter´ y mysl´ı jako ˇ clovˇ ek ◮
◮
snaha porozumˇet postup˚ um lidsk´eho myˇslen´ı – kognitivn´ı (pozn´ avac´ı) vˇ eda vyuˇz´ıv´a poznatk˚ u neurologie, neurochirurgie,. . . napˇr. COLING 2000 – Angela Friederici: Language Processing in the Human Brain Max Planck Institute of Cognitive Neuroscience, Leipzig mˇeˇren´ı “Event Related Potentials” (ERP) v mozku – jako potvrzen´ı oddˇelen´ı syntaxe a s´emantiky pˇri zpracov´an´ı vˇety ´ Uvod do umˇ el´ e inteligence 1/12
6 / 19
Co je “umˇ el´ a inteligence”
od dob Aristotela (350 pˇr.n.l.) n´aplˇ n studia logiky probl´em – umˇet naj´ıt ˇreˇsen´ı teoreticky × prakticky (sloˇzitost a vyˇc´ıslitelnost) probl´em – ne´ uplnost a nejistota vstupn´ıch dat
◮ syst´ em, kter´ y mysl´ı rozumnˇ e ◮ ◮
◮
inteligentn´ı agent – syst´em, kter´y jedn´a za nˇejak´ym u ´ˇcelem jedn´a samostatnˇe jedn´a na z´akladˇe vstup˚ u ze sv´eho prostˇred´ı pracuje delˇs´ı dobu adaptuje se na zmˇeny
◮ syst´ em, kter´ y se chov´ a rozumnˇ e ◮ ◮ ◮ ◮ ◮
´ Uvod do umˇ el´ e inteligence 1/12 Co je “umˇ el´ a inteligence”
7 / 19 ˇ ım se budeme zab´ C´ yvat?
ˇ ım se budeme zab´yvat? C´
◮
z´akladn´ı struktury a algoritmy bˇeˇznˇe pouˇz´ıvan´e pˇri technik´ach programovan´ı pro inteligentn´ı agenty
◮
strategie ˇreˇsen´ı, prohled´ av´ an´ı stavov´eho prostoru, heuristiky, . . .
◮
s pˇr´ıklady v jazyce Prolog
´ Uvod do umˇ el´ e inteligence 1/12
8 / 19
Struˇ cn´ e shrnut´ı Prologu
Struˇcn´e shrnut´ı Prologu Historie: ◮
70. l. Colmerauer, Kowalski; D.H.D. Warren (WAM); → CLP, paraleln´ı syst´emy
◮
PROgramov´an´ı v LOGice; ˇc´ast predik´atov´e logiky prvn´ıho ˇr´adu (logika Hornov´ych klauzul´ı)
◮
deklarativnost (specifikace programu je pˇr´ımo programem)
◮
ˇreˇsen´ı probl´em˚ u t´ykaj´ıc´ıch se objekt˚ u a vztah˚ u mezi nimi
Prology na FI: ◮
SICStus Prolog (modul sicstus)
◮
SWI (modul pl)
◮
ECLiPSe (modul eclipse)
◮
stroje aisa, erinys, oreias, nymfe
◮
verze ´ Uvod do umˇ el´ e inteligence 1/12 Struˇ cn´ e shrnut´ı Prologu
9 / 19 Principy
Principy ◮ ◮
backtracking ˇr´ızen´y unifikac´ı, hojnˇe vyuˇz´ıv´a rekurzi spojitost s logikou: • d˚ ukaz pravdivosti c´ıle; c´ıl je dok´az´an, unifikuje-li s hlavou nˇejak´e
klauzule a vˇsechny podc´ıle v tˇele t´eto klauzule jsou rovnˇeˇz dok´az´any. Strategie v´ybˇeru podc´ıle: shora dol˚ u, zleva doprava. ◮
unifikace: • ˇr´ıdic´ı mechanismus, hled´ an´ı nejobecnˇejˇs´ıho unifik´atoru dvou term˚ u. info(Manzel,dana,Deti,svatba(’20.12.1940’)) = info(petr,dana,[jan,pavel],Info).
po unifikaci: Manzel=petr, Deti=[jan,pavel], Info=svatba(’20.12.1940’) ◮
backtracking: • standardn´ı metoda prohled´ av´an´ı stavov´eho prostoru do hloubky
(pr˚ uchod stromem → nesplniteln´y c´ıl → n´avrat k nejbliˇzˇs´ımu minul´emu bodu s alternativn´ı volbou) ◮
rekurze potomek(X,Y):- rodic(Y,X). potomek(X,Y):- rodic(Z,X), potomek(Z,Y). ´ Uvod do umˇ el´ e inteligence 1/12
10 / 19
Struˇ cn´ e shrnut´ı Prologu
Principy
Pˇr´ıklad jednoduch´y pˇr´ıklad – DB rodinn´ych vztah˚ u: otec(milan,dana). otec(milan,petr). otec(jan,david). fakty (DB)
matka(pavla,dana). matka(pavla,petr). matka(jana,david). rodic(X,Y):- otec(X,Y). rodic(X,Y):- matka(X,Y). ?− otec(X,dana). X = milan Yes
pravidla
?− rodic(X,david). X = jan ; X = jana ;
´ Uvod do umˇ el´ e inteligence 1/12 Struˇ cn´ e shrnut´ı Prologu
11 / 19 Syntax jazyka Prolog
Syntax jazyka Prolog ◮ logick´ y (prologovsk´ y) program
– seznam klauzul´ı (pravidel a fakt˚ u) – nikoli
mnoˇzina ◮ klauzule – seznam liter´ al˚ u ◮ Liter´ al pˇred :- je hlava, ostatn´ı liter´aly tvoˇr´ı tˇ elo klauzule. ◮ V´ yznam klauzule je implikace: • hlava:-tˇ elo1, tˇ elo2, . . . . • tˇ elo1 ∧ tˇ elo2 ∧ . . . ⇒ hlava • Pokud je splnˇ eno tˇ elo1 a souˇcasnˇe tˇ elo2 a souˇcasnˇe . . . , pak plat´ı
tak´e hlava. ◮
3 moˇzn´e typy klauzul´ı: • fakt: hlava bez tˇ ela. Z´apis v Prologu: p(X,Y). (ekv. p(X,Y):-true.) • pravidlo: hlava i tˇ elo. Prolog: p(Z,X) :- p(X,Y), p(Y,Z). • c´ıl: tˇ elo bez hlavy. Prolog: ?- p(g,f).
– seznam (vˇsech) klauzul´ı se stejn´ym funktorem a aritou v hlavov´em liter´alu. ◮ Zapisuje se ve tvaru funktor /arita – potomek/2.
◮ predik´ at
´ Uvod do umˇ el´ e inteligence 1/12
12 / 19
Struˇ cn´ e shrnut´ı Prologu
◮ liter´ al
Syntax jazyka Prolog
– atomick´a formule, nebo jej´ı negace
– v Prologu zcela odpov´ıd´a sloˇzen´emu termu (syntaktick´y rozd´ıl neexistuje)
◮ atomick´ a formule
◮ term: ◮
◮
◮
konstanta: a, 1, ’.’, [], sc2 atomic/1 (metalogick´e testov´an´ı na konstantu) atom/1, number/1 promˇenn´a: X, Vys, var/1 (metalogick´e testov´an´ı na promˇennou) sloˇzen´y term: f(a,X) funktor, argumenty, arita functor/3 d´av´a funktor termu, arg/3 d´av´a n-t´y argument zkratka pro z´apis seznam˚ u: [1,a,b3] odpov´ıd´a struktuˇre ’.’(1, ’.’(a, ’.’(b3, [])))
´ Uvod do umˇ el´ e inteligence 1/12 Struˇ cn´ e shrnut´ı Prologu
13 / 19 Syntax jazyka Prolog
Pˇr´ıklad predik´at sourozenci(X,Y) – je true, kdyˇz X a Y jsou (vlastn´ı) sourozenci. sourozenci(X,Y):- otec(O,X), otec(O,Y), X\=Y, matka(M,X), matka(M,Y). 1 2 3 4 5 6 7 8
otec(milan,dana). otec(milan,petr). otec(jan,david). matka(pavla,dana). matka(pavla,petr). matka(jana,david). rodic(X,Y):- otec(X,Y). rodic(X,Y):- matka(X,Y).
?− sourozenci(dana,Y). 1, otec(O,dana) % O = milan 2, otec(milan,Y) % Y = dana 3, dana \= dana % fail → backtracking 2∗, otec(milan,Y) % Y = petr 3, dana \= petr % true 4, matka(M,dana) % M = pavla 5, matka(pavla,petr) % true Y = petr Yes
´ Uvod do umˇ el´ e inteligence 1/12
14 / 19
Struˇ cn´ e shrnut´ı Prologu
Strom v´ ypoˇ ctu
Strom v´ypoˇctu Dotaz ?- sourozenci(dana,Y). sourozenci(dana,Y) 9 1 2 3 4 5 6 7 8 9 10 11
otec(milan,dana). otec(milan,petr). otec(jan,david). matka(pavla,dana). matka(pavla,petr). matka(jana,david). rodic(X,Y):- otec(X,Y). rodic(X,Y):- matka(X,Y). sourozenci(X,Y):- otec(O,X), otec(O,Y), X\=Y, matka(M,X), matka(M,Y).
otec(O,dana), otec(O,Y),. . . 1 otec(milan,Y), dana\=Y,. . . 1 dana\=dana, matka(M,dana),. . .
2 dana\=petr, matka(M,dana),. . .
unif fail
unif matka(M,dana), matka(M,petr) 4 matka(pavla,petr) 5 true Y=petr
´ Uvod do umˇ el´ e inteligence 1/12 Struˇ cn´ e shrnut´ı Prologu
15 / 19 Rozd´ıly od procedur´ aln´ıch jazyk˚ u
Rozd´ıly od procedur´aln´ıch jazyk˚ u ◮
single assignment
◮
= (unifikace) vs. pˇriˇrazovac´ı pˇr´ıkaz, == (identita), is (vyhodnocen´ı aritm. v´yrazu). rozd´ıly: ?− A=1, A=B. % B=1 Yes ?− A=1, A==B. % No ?− A=1, B is A+1. % B=2 Yes
◮
v´ıcesmˇernost predik´at˚ u (omezen´a, obzvl´aˇstˇe pˇri pouˇzit´ı ˇrezu) ?− otec(X,dana). ?− otec(milan,X). ?− otec(X,Y).
(rozliˇsen´ı vstupn´ıch/v´ystupn´ıch promˇenn´ych: + - ?) ◮
cykly, podm´ınˇen´e pˇr´ıkazy tiskniseznam(S) :- write(’seznam=[’),nl,tiskniseznam(S,1). tiskniseznam([], ) :- write(’]’),nl. tiskniseznam([H|T],N):- tab(4),write(N),write(’: ’),write(H),nl,N1 is N+1, tiskniseznam(T,N1).
´ Uvod do umˇ el´ e inteligence 1/12
16 / 19
Struˇ cn´ e shrnut´ı Prologu
Programujeme
Programujeme
consult(’program.pl’). % [’program.pl’,program2]. % listing. % trace, rodic(X,david). % notrace. % halt. %
‘‘kompiluj’’ program.pl ‘‘kompiluj’’ program.pl, program2.pl vypiˇs programov´ e predik´ aty trasuj vol´ an´ı predik´ atu zruˇs reˇzim trasov´ an´ı ukonˇ ci interpret
´ Uvod do umˇ el´ e inteligence 1/12 Struˇ cn´ e shrnut´ı Prologu
17 / 19 Fibonacciho ˇ c´ısla
Fibonacciho ˇc´ısla
Fibonacciho ˇ c´ısla jsou ˇc´ısla z ˇrady: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . . Rekurenˇcn´ı vzorec t´eto ˇrady je: fib0 = 0 fib1 = 1 fibi = fibi−1 + fibi−2 , pro i ≥ 2 Pˇrepis do Prologu je pˇr´ımoˇcar´y: fib(0,0). fib(1,1). fib(X,Y) :- X1 is X−1, X2 is X−2, fib(X1,Y1), fib(X2,Y2), Y is Y1+Y2.
´ Uvod do umˇ el´ e inteligence 1/12
18 / 19
Struˇ cn´ e shrnut´ı Prologu
Fibonacciho ˇ c´ısla
Fibonacciho ˇc´ısla II
Pˇredchoz´ı program – exponenci´ aln´ı ˇcasov´a sloˇ zitost (konstatn´ı pamˇet’ov´a) Vyuˇzit´ı extralogick´ych predik´at˚ u – line´ arn´ı ˇcasov´a sloˇ zitost (a line´arn´ı pamˇet’ov´a) fib(0,0). fib(1,1). fib(X,Y) :- X1 is X−1, X2 is X−2, fib(X1,Y1), fib(X2,Y2), Y is Y1+Y2, asserta(fib(X,Y)).
´ Uvod do umˇ el´ e inteligence 1/12
19 / 19
