I. rész. A Prolog programozási nyelv. Tanítsuk gondolkodni a gépet. SugóParti TudósParty

Tanítsuk gondolkodni a gépet

I. rész

avagy hogyan nyert a számítógép a "Mindent vagy semmit" vetélkedo˝ amerikai változatában

A Prolog programozási nyelv

Szeredi Péter [email protected] BME Számítástudományi és Információelméleti Tanszék NJSZT Mesterséges Intelligencia Szakosztály

1


2

Egy nagyobb Prolog példa

3

Kérdés-válasz rendszerek

Baja, 2012. március 30.

SugóParti TudósParty Revision 583M | Generated: Thu Mar 29 22:21:02 CEST 2012 A Prolog programozási nyelv


Programozási nyelvek osztályozása

Deklaratív programozási nyelvek A funkcionális nyelvek alapja a matematika függvényfogalma A logikai nyelvek alapja a matematika relációfogalma

Programozási nyelvek – stílusok

Imperatív Fortran Algol C C++ ...

(BME SZIT, NJSZT MI Szakosztály)

Közös tulajdonságaik A program jelentése egy matematikai állításként olvasható ki (deklaratív szemantika) ˝ ismeretlen értéket jelöl, vö. Matematikai változó egyetlen egyelore egyszeres értékadás

Deklaratív

Funkcionális

Logikai

LISP Erlang ...

SQL Prolog CLP nyelvek ...



Jelmondat MIT inkább mint HOGYAN (WHAT rather than HOW): a megoldás módja (a HOGYAN rész) helyett inkább a megoldandó feladat leírását (a MIT részt) kell megadni ˝ A gyakorlatban mindkét szemponttal foglalkozni kell – kettos szemantika: MIT (milyen feladatot) old meg a program (deklaratív rész) HOGYAN oldja meg a program a feladatot (procedurális rész) 3 / 32




4 / 32


A Prolog alapjai


Tartalom

1

A Prolog alapjai

Egy példa – családi kapcsolatok

% szülője(Gy, Sz):Gy szülője Sz. % Tényállításokból álló predikátum szülője(’Imre’, ’István’). % (sz1) szülője(’Imre’, ’Gizella’). % (sz2) szülője(’István’, ’Géza’). % (sz3) szülője(’István’, ’Sarolt’). % (sz4) szülője(’Gizella’, ’Civakodó Henrik’). % (sz5) szülője(’Gizella’, ’Burgundi Gizella’). % (sz6)

A Prolog programozási nyelv A Prolog alapjai Szintaktikus „édesítés” További vezérlési szerkezetek A Prolog adatfogalma Prolog végrehajtás

% Kik Imre nagyszülei? | ?- nagyszülője(’Imre’, NSz). NSz = ’Géza’ ? ; NSz = ’Sarolt’ ? ; NSz = ’Civakodó Henrik’ ? ; NSz = ’Burgundi Gizella’ ? ; no % Kik Géza unokái? | ?- nagyszülője(U, ’Géza’). U = ’Imre’ ? ; no

% Gyerek nagyszülője Nagyszülő. % Egyetlen szabályból álló predikátum nagyszülője(Gyerek, Nagyszülő) :szülője(Gyerek, Szülő), szülője(Szülő, Nagyszülő). % (nsz1) (BME SZIT, NJSZT MI Szakosztály)

Tanítsuk gondolkodni a gépet A Prolog programozási nyelv



5 / 32

A Prolog alapjai


A klózok logikai alakja


6 / 32


8 / 32

Szintaktikus „édesítés”

Tartalom

A klóz szabály vagy tényállítás lehet A szabály alakja „fej :- törzs.”, ahol a törzs célok konjunkciója („és” kapcsolata) A tényállítás alakja „fej.”, a törzs üres, azonosan igaz ˝ A fej és a cél tetszoleges Prolog kifejezés (term) lehet A szabály jelentése implikáció: a törzsbeli célok konjunkciójából következik a fej. Példa: nagyszülője(U,N) :szülője(U,Sz), szülője(Sz,N). Logikai alak:

1

∀UNSz(nagyszülője(U, N) ← szülője(U, Sz) ∧ szülője(Sz, N)) azaz minden U, N, Sz esetén nagyszülője(U, N) fennáll, ha szülője(U, Sz) és szülője(Sz, N) egyaránt fennáll.


Ekvivalens alak: ∀UN

(nagyszülője(U, N) ← ∃Sz(szülője(U, Sz) ∧ szülője(Sz, N)))

A tényállítás feltétel nélküli állítás, pl. Példa: szülője(’Imre’, ’István’)., logikai alakja ugyanez A tényállításban is lehetnek változók, ezekre is vonatkozik az univerzális (∀ – minden) kvantor (BME SZIT, NJSZT MI Szakosztály)



7 / 32




Szintaktikus „édesítés”


Operátorok – olvashatóbb kód

További vezérlési szerkezetek

Tartalom

Ha az aaa nevet infix operátornak deklaráljuk, akkor aaa(U, V) helyett „U aaa V” írható: :- op(700, xfx, [szülője,nagyszülője]).

˝ Infix operátorfajták: yfx (balra köt), xfy (jobbra köt), xfx (nem ismételheto) A korábbi példa: Unoka nagyszülője Nagyszülő :Unoka szülője Szülő, Szülő szülője Nagyszülő.

% ha % és

Ha az aaa nevet prefix ill. posztfix operátornak deklaráljuk, akkor aaa(U) helyett „aaa U” ill. „U aaa” írható: :- op(700, xf, [férfi,nő]).

1


Gyerek anyja Anya :Gyerek szülője Anya, Anya nő.

˝ fx/xf (nem ismételheto) ˝ Prefix/posztfix fajták: fy/yf (ismételheto), Az operátordeklarációban megadunk egy 1 és 1200 közé eso˝ prioritást. ˝ A kisebb prioritású operátor erosebben köt. Pl. :- op(500, yfx, +), op(400, yfx, *) (BME SZIT, NJSZT MI Szakosztály)



9 / 32


10 / 32


Negáció, feltételes szerkezet Amikor a nő fogalmát definiáljuk, kihasználhatjuk azt a háttértudást, hogy ˝ Emellett tényállításokban felsoroljuk a nem házas minden feleség no. ˝ noket:

Tegyük fel, hogy tároljuk a „felesége” kapcsolatokat is: :- op(700, xfx, [felesége,házastársa]). felesége ’Sarolt’. felesége ’Gizella’.

Y nő :-

_Bárki felesége Y. ’Judit’ nő. ...

A „házastársa” kapcsolat definiálhatjuk így:

A férfi fogalmának definiálásakor az ún. meghiúsulásos negációt használhatjuk: \+ Cél: lefuttatja Cél-t, ha ez sikerül, akkor a negáció meghiúsul, és fordítva, ha Cél meghiúsul, akkor \+ Cél sikerül.

X házastársa Y :X felesége Y. X házastársa Y :Y felesége X.

X férfi :\+ X nő

Egyetlen szabályként is definiálhatjuk, ha diszjukciót használunk X házastársa Y :( X felesége Y ; Y felesége X ).

% vagy



% nem igaz, hogy

Az X férfi célt csak úgy érdemes meghívni, hogy az X változó már ˝ X ember kell legyen. ismert, sot, A diszjunkcióval és negációval rokon a feltételes szerkezet: ( ; )

˝ segédpredikátummal A diszjunkció mindig kiküszöbölheto, (BME SZIT, NJSZT MI Szakosztály)


Diszjunkció

’Géza’ ’István’ ...



11 / 32

felt -> akkor egyébként


( ; )

felt, akkor \+ felt, egyébként



12 / 32


A Prolog adatfogalma


Tartalom


A Prolog adatfogalma, a Prolog kifejezés konstans (atomic) ˝ pl. 1, -2.3, 3.0e10 számkonstans (number) – egész vagy lebegop, névkonstans (atom), pl. ’István’, szuloje, +, –, <, tree_sum

1

összetett- vagy struktúra-kifejezés (compound) ún. kanonikus alak: h struktúranév i(h arg1 i, . . . , h argn i) a h struktúranév i egy névkonstans, ˝ az h argi i argumentumok tetszoleges Prolog kifejezések pl.: személy(civakodó,henrik,951), <(X,Y), is(X, +(Y,1)) ˝ szintaktikus „édesítoszerek”, operátorok, listák: [X|L] ≡ .(X,L)


változó (var) pl. X, Szulo, X2, _valt, _, _123 a változó alaphelyzetben behelyettesítetlen, értékkel nem bír, az ˝ egyesítés (mintaillesztés) muvelete ˝ során egy tetszoleges Prolog kifejezést vehet fel értékül (akár egy másik változót) (BME SZIT, NJSZT MI Szakosztály)




13 / 32



Néhány beépített predikátum


14 / 32


16 / 32

Prolog végrehajtás

Tartalom

Kifejezések egyesítése X = Y: az X és Y szimbolikus kifejezések változók ˝ behelyettesítésével azonos alakra hozhatók, azaz egyesíthetok X \= Y: az X és Y kifejezések nem hozhatók azonos alakra Aritmetikai predikátumok X is Kif: A Kif aritmetikai kifejezés értékét egyesíti X-szel. Kif1Kif2, Kif1>=Kif2, Kif1=:=Kif2 ˝ Kif1=\=Kif2 (aritmetikailag nem egyenlo) ˝ (aritmetikailag egyenlo), Fontos aritmetikai operátorok: +, -, *, /, rem, // (egész-osztás)

1


Fontos: az aritmetikai operátorokkal (+,-,. . . ) képzett kifejezések struktúra-kifejezések. Csak az aritmetikai beépített predikátumok értékelik ki ezeket! A Prolog kifejezések szimbolikusak, az aritmetikai kiértékelés a „kivétel”.




15 / 32






Prolog végrehajtás – visszalépéses keresés


Prolog végrehajtás – a 4-kapus doboz modell

Példa: „jó” számok keresése A feladat: keressük meg azokat a kétjegyu˝ számokat amelyek négyzete ˝ háromjegyu˝ és a szám fordítottjával kezdodik A program: % dec1(J): J egy pozitív decimális számjegy. dec1(1). dec1(2). dec1(3). dec1(4). dec1(5). dec1(6). dec1(7). dec1(8). dec1(9).

joszam(Sz):dec1(A), dec(B), Sz is A * 10 + B, Sz * Sz // 10 =:= B * 10 + A. joszam

% dec(J): J egy decimális számjegy. dec(0). dec(J) :- dec1(J).

Call

dec1(A)

- - A=1 ... . . . . .. 2 ..

% Az Sz szám négyzete háromjegyű és az Sz fordítottjával kezdődik. joszam(Sz):dec1(A), dec(B), Sz is A * 10 + B, Sz * Sz // 10 =:= B * 10 + A.

. ... 9 .. ...

Fail

dec(B)

Sz is A*10+B -

- B=0 ... . . . . .. 1 ..

. ... 9 .. ...

Sz*Sz//10 =:= B*10+A

igaz -Exit

hamis

...

Redo

dec1 és dec a between könyvtári predikátummal definiálható: :- use_module(library(between)). dec1(J) :- between(1, 9, J). (BME SZIT, NJSZT MI Szakosztály)

dec(J) :- between(0, 9, J).



17 / 32




18 / 32


˝ Lovagok és lókötok

II. rész Egy nagyobb Prolog példa 1


2


3


A feladat ˝ Egy szigeten minden bennszülött lovag vagy lóköto. A lovagok mindig igazat mondanak. ˝ mindig hazudnak. A lókötok Egy vagy több bennszülöttnek saját magukra vonatkozó kijelentése alapján meg kell határozni a bennszülött típusát. Példa: Találkozunk két bennszülöttel Alfréd-dal és Bélával. Alfréd azt ˝ Milyen típusú Alfréd és Béla? mondja: van köztünk lóköto. Irodalom: Raymond Smullyan: Mi a címe ennek a könyvnek?, A hölgy és a tigris, Typotex kiadó. Továbbfejlesztés: a szigeten lehetnek normális emberek is, akik néha hazudnak, néha igazat mondanak.




20 / 32



˝ – a megoldás elvei Lovagok és lókötok

˝ Prolog program Lovagok és lókötok:

Készítünk egy egyszeru˝ formális nyelvet a bennszülöttek kijelentéseire, pl. Alfréd mondja Alfréd = lókötő vagy Béla = lókötő A bennszülöttek nevei (pl. Alfréd) Prolog változók, amelyek a lovag vagy lókötő értéket veszik fel. A nyelv egyetlen alap-relácója az =. Az összeköto˝ jeleket (mondja, és, vagy, nem) Prolog operátornak deklaráljuk. Egy egyszeru˝ Prolog programmal definiáljuk a „bennszülött logikát”, azaz a nyelv állításainak igazságértékét. A feladat: egy adott mondat esetén megkeresni azokat a változó-behelyettesítéseket, amelyekre a mondat a „bennszülött logika” szerint igaz lesz.

:- op(700, fy, nem). :- op(800, yfx, és).

:- op(900, yfx, vagy). :- op(950, xfy, mondja).

% Az A bennszülött mondhatja az Áll állítást. A mondja Áll :- értéke(A mondja Áll, 1). % értéke(Áll, Érték): Áll igazságértéke Érték (1 értéke(X = X, 1). értéke(X = Y, 0) :különböző(X, Y). értéke(lovag mondja M, E) :- értéke(M, E). értéke(lókötő mondja M, E) :- értéke(nem M, E). értéke(M1 és M2, E) :értéke(M1, E1), értéke(M2, E2), E értéke(M1 vagy M2, E) :értéke(M1, E1), értéke(M2, E2), E értéke(nem M, E) :értéke(M, E1), E

= igaz, 0 = hamis).

is E1/\E2. is E1\/E2. is 1-E1.

% különböző(A, B): A és B különböző típusú bennszülöttek. különböző(lovag, lókötő). különböző(lókötő, lovag). | ?- Alfréd mondja Alfréd = lókötő vagy Béla = lókötő. Béla = lókötő, Alfréd = lovag ? ; no




21 / 32




22 / 32


˝ általában A kérdés-válasz rendszerekrol

III. rész Kérdés-válasz rendszerek 1


2


3


A megoldandó feladatok ˝ A tudás ábrázolása – egyre inkább logikai alapokon (elsorend u˝ logika, leíró logika, stb.) Tények, adatok (adatdoboz): akár adatbázisban is tárolható Szabályok, háttértudás (terminológiai doboz): valamilyen logikai formalizmus Természetes nyelvi interfészek Szöveges információ nyelvtani elemzése → elemzési fa → logikai alak (mind az eltárolandó állítások, mind a kérdések esetén ) Eredmények szöveggé alakítása: logikai eredmény → szöveg Válasz kinyerése – logikai következtetés ˝ Példák – az eloadás fennmaradó részének tartalomjegyzéke Egy nagyon egyszeru˝ magyar nyelvu˝ kérdés-válasz rendszer ˝ Prologban („Beszélgeto”) Hogyan végzik a nyelvtani elemzést a Watson rendszerben (BME SZIT, NJSZT MI Szakosztály)



24 / 32


˝ program Prologban A „beszélgeto”


˝ program – egy beszélgetés Magyar nyelvu˝ „tudáskezelo”

Tartalom

3

| ?- párbeszéd. |: Magyar legény vagyok én. Felfogtam. |: Ki vagyok én? Magyar legény |: Péter kicsoda? Nem tudom. |: Péter tanuló. Felfogtam. |: Péter jó tanuló. Felfogtam. |: Péter kicsoda? tanuló jó tanuló |: Boldog vagyok. Felfogtam.

Kérdés-válasz rendszerek ˝ program Prologban A „beszélgeto” A Watson kérdés-válasz rendszer



Tanítsuk gondolkodni a gépet Kérdés-válasz rendszerek



25 / 32


|: Én vagyok Jeromos. Felfogtam. |: Te egy Prolog program vagy. Felfogtam. |: Ki vagyok én? Magyar legény Boldog Jeromos |: Okos vagy. Felfogtam. |: Ki vagy te? egy Prolog program Okos |: Valóban? Nem értem |: Unlak. Én is.


˝ – a mondatszerkezet elemzése Magyar nyelvu˝ „tudáskezelo”


26 / 32


28 / 32

A Watson kérdés-válasz rendszer

Tartalom

Ez a kóddarab a teljes kód kb. 25%-a, három további dián elfér a többi. % mondat(Alany, Áll, L0, L): L0-L kielemezhető egy Alany alanyból és Áll % állítmányból álló mondattá. Alany lehet első vagy második személyű % névmás, vagy egyetlen szóból álló (harmadik személyű) alany. mondat(Alany, Áll) --> {én_te(Alany, Ige)}, én_te_perm(Alany, Ige, Áll). mondat(Alany, Áll) --> szó(Alany), szavak(Áll). % én_te(Alany, Ige): % Az Alany első/második személyű névmásnak megfelelő létige az Ige. én_te("én", "vagyok"). én_te("te", "vagy").

3

Kérdés-válasz rendszerek ˝ program Prologban A „beszélgeto” A Watson kérdés-válasz rendszer

% én_te_perm(Ki, Ige, Áll, L0, L): L0-L kielemezhető egy Ki % névmásból, Ige igealakból és Áll állítmányból álló mondattá. én_te_perm(Alany, Ige, Áll) --> ( szó(Alany), szó(Ige), szavak(Áll) ; szó(Alany), szavak(Áll), szó(Ige) ; szavak(Áll), szó(Ige), szó(Alany) ; szavak(Áll), szó(Ige) ). (BME SZIT, NJSZT MI Szakosztály)



27 / 32






˝ A gép és az ember vetélkedoje

Nyelvtani elemzés a Watson rendszerben – egy példakérdés Példa kérdésre a POETS & POETRY kategóriában: He was a bank clerk in the Yukon before he published „Songs of a Sourdough” in 1907. Az elemzési fa Prolog tényállítások formájában (a számok a fa csomópontjainak felelnek meg):

˝ Jeopardy – Magyarországon „Mindent vagy semmit” A vetélkedo: 1964 óta sugározzák (megszakításokkal) Bajnokok (össznyeremények): Ken Jennings – $2.520.700, Brad Rutter – $3.455.102 A kihívó: a Watson számítógéprendszer Hardver: 90 db IBM Power 750 szerver, egyenként 4 chip, chipenként 8 db 3.5 GHz mag; 16 Terabyte RAM Szoftver: A DeepQA (mély kérdés-válasz) tudáskezelo˝ rendszer SUSE Linux Enterprise Server 11 operációs rendszer fo˝ nyelvek: Java, C++, de fontos részekben Prolog is ˝ Jennings, Watson, Rutter A meccs: 2011. február 14-16, résztvevok: 1. forduló: Jennings – $4.800, Watson – $35.734, Rutter – $10.400. Vége: Jennings – $24.000, Watson – $77.147, Rutter – $21.600. (febr. 28.-án: 5 kongr. képviselo˝ – $30.000, Watson – $40.300.) További információ: http://www.research.ibm.com/deepqa/deepqa.shtml (BME SZIT, NJSZT MI Szakosztály)



29 / 32

lemma(1, "he"). lemma(2, "publish"). lemma(3, "Songs of a Sourdough"). subject(2, 1).

authorOf(Author, Composition) :-% publishing(Verb), % subject(Verb, Author), % author(Author), % object(Verb, Composition), % composition(Composition). %

Az Author a Composition mű szerzője ha Verb egy publikálást kifejező ige, Author ennek az állításnak az alanya, Author egy szerző, Composition ennek az állításnak a tárgya, Composition egy szerzemény.

publishing(Verb) :% Verb egy publikálást kifejező ige ha partOfSpeech(Verb, verb), % Verb szófaja ige lemma(Verb, VerbLemma), % Verb szöveges alakja VerbLemma member(VerbLemma, ["write","publish",...]). % VerbLemma szerepel az adott listában. (BME SZIT, NJSZT MI Szakosztály)


authorOf(Author, Composition) :-% Az Author a Composition mű szerzője ha composition(Composition), % Composition egy szerzemény. argument(Composition, Preposition), % Composition a Preposition argumentuma, lemma(Preposition, "by"), % a Preposition szöveges alakja "by", objectOfPreposition(Preposition, Author), % Author ennek az elöljárószónak a tárgya, author(Author), % Author egy szerző.

A fenti példamondat elemzését ezzel a szabállyal elvégezve egy olyan állítást nyerünk, amellyel a "Robert W. Service" egy plauzibilis válasz. A mintaillesztésre korábban több saját eszközt fejlesztett az IBM. „ These frameworks tend to end up replicating some of the features of Prolog but lack the full feature set of Prolog or the efficiency of a good Prolog implementation. Using Prolog for this task has significantly improved our productivity in developing new pattern matching rules and has delivered the execution efficiency necessary in order to be competitive in a Jeopardy! game.” Baja, 2012. március 30.


30 / 32


Összefoglalás

Tegyük fel, hogy a Watson rendszer háttértudásában szerepel ez a mondat: Songs of a Sourdough by Robert W. Service. Az authorOf Prolog predikátumhoz több szabály is tartozik, köztük ez:


partOfSpeech(1, pronoun). partOfSpeech(2, verb). partOfSpeech(2, noun). object(2, 3).

˝ kapcsolat leírása Prolog szabályokkal (leegyszerusítve): A „szerzoje” ˝


Nyelvtani elemzés a Watson rendszerben – a tények kezelése



31 / 32

˝ intelligens, emberközeli, tudásalapú informatika A jövo: a tudásábrázolás régen jelen levo˝ formája: (matematikai) logika a tudáskezelés: (logikai) következtetés Logika a jelenben – néhány példa: Logikai programozás magasszintu, ˝ jól párhuzamosítható (többmagos processzorok) ˝ következtetést korlát-kiterjesztései (constraint) kiugróan eros adnak (pl. ILOG – IBM) Szemantikus technológiák ˝ ne csak olvassák, értsék is Szemantikus világháló – a keresok, a világhálót! Szemantikus integráció – alkalmazások automatikus összeépítése ˝ rendszerek – pl. az orvostudományban Tudásalapú (szakérto) (Watson javasolt alkalmazása) (BME SZIT, NJSZT MI Szakosztály)



32 / 32

I. rész. A Prolog programozási nyelv. Tanítsuk gondolkodni a gépet. SugóParti TudósParty

Recommend Documents