364

Mesterséges Intelligencia Csató Lehel

Mesterséges Intelligencia Csató Lehel Matematika-Informatika Tanszék Babe¸s–Bolyai Tudományegyetem, Kolozsvár

2010/2011

1/364

˝ Az Eloadások Témái Mesterséges Intelligencia

˝ mi a mesterséges intelligencia ... Bevezeto:

1

„Tudás”–reprezentáció

Csató Lehel

Gráfkeresési stratégiák

Tudnivalók

Szemantikus hálók / Keretrendszerek

Bevezeto˝ ˝ Fejlodés

Játékok modellezése

Könyvészet

Bizonytalanság kezelése

Eredmények

Fuzzy rendszerek Grafikus modellek Tanuló rendszerek Szimulált kifutés, ˝ Genetikus algoritmusok A perceptron modell ˝ Neurális hálók, önszervezodés Gépi tanulás 2/364

Admin ... Mesterséges Intelligencia

... trívia

http://www.cs.ubbcluj.ro/~csatol/mestint

1 Csató Lehel Tudnivalók

Vizsga Szóbeli (60%) + Gyakorlat (40%)


Laborgyakorlatok:

Könyvészet Eredmények

1

Gráfok ábrázolása - dedukciós algoritmus

18%

2

Játékelmélet

10%

3

Matlab - tanulási algoritmus

12%

4

Opcionális feladatok - max. 3/személy

Bemutatók (5–20 pont) Alkalmazások bemutatása, melyek adaptív, gépi tanulásos vagy mestint módszereket alkalmaznak. 3/364

sok%

A „mesterséges intelligencia” Mesterséges Intelligencia

1

Nincs pontos definíció.

Csató Lehel Tudnivalók Bevezeto˝ ˝ Fejlodés Könyvészet Eredmények

„Elvárások” intelligens viselkedés racionális viselkedés gondolkodó rendszer cselekvo˝ rendszer 4/364

Cog.Bot.Lab – München

J. Schmidthuber

Turing-teszt Mesterséges Intelligencia

1 Csató Lehel Tudnivalók Bevezeto˝ ˝ Fejlodés Könyvészet

Egy megfigyelo˝ tesztel egy ˝ nem rendszert, melyrol tudja, hogy ember vagy gép. Feladat, hogy a feltett kérdések nyomán találjuk ki, hogy a rendszert gép vagy ember vezérli.

? M.I. rendszer

Eredmények

Kérdésfelvetés: Alan Turing

Képessé teheto˝ – programozható – a számítógép a gondolkodás muveletére? ˝

Neumann János A fogalmak eléggé pontos specifikálása esetén a gép „intelligens” lesz. 5/364

Turing-teszt Mesterséges Intelligencia


Egy megfigyelo˝ tesztel egy ˝ nem rendszert, melyrol tudja, hogy ember vagy gép. Feladat, hogy a feltett kérdések nyomán találjuk ki, hogy a rendszert gép vagy ember vezérli.

? M.I. rendszer

Eredmények

Kérdésfelvetés: Alan Turing

Képessé teheto˝ – programozható – a számítógép a gondolkodás muveletére? ˝

Neumann János A fogalmak eléggé pontos specifikálása esetén a gép „intelligens” lesz. 5/364

Bevezeto˝ fogalmak Mesterséges Intelligencia

1

Mesterséges Intelligencia – „A.I.” Emberhez hasonlóan gondolkodó rendszerek Bellman: döntéshozatal, problémamegoldás, tanulás automatizálása. Emberhez hasonlóan cselekvo˝ rendszerek Rich: Végeztetni dolgokat, melyeket az emberek jobban tudnak.

Csató Lehel Tudnivalók Bevezeto˝ ˝ Fejlodés Könyvészet Eredmények

6/364

Racionálisan gondolkodó rendszerek Charniak: Mentális képességek tanulmányozása. Racionálisan cselekvo˝ rendszerek Schalkoff: Utánozni és magyarázni az intelligens viselkedést. Russell, 1996

˝ Az M.I. fejlodése Mesterséges Intelligencia

1956 – elso˝ M.I. konferencia Darthmouth-ban. „Alapítók”:

1

Minsky (Logo, Neurális háló), McCarthy (Lisp), Shannon (információ-elmélet)

Csató Lehel Tudnivalók Bevezeto˝ ˝ Fejlodés Könyvészet

˝ Fejlodési területek: szimbolikus M.I. ˝ rendszerek szakértoi dedukciós algoritmusok

Eredmények

„konnekcionista” megközelítések neurális hálók Boltzmann gépek evolúciós algoritmusok

Ezekkel párhuzamosan: kognitív tudományok - cognitive neuroscience (CNS) Fuzzy algoritmusok

7/364

˝ M.I. fejlodésgrafikon Mesterséges Intelligencia


Bonyolultságelmélet

˝ Fejlodési grafikon cikkek száma, konferenciák látogatottsága ... ’56

Eredmények

82–88

’00

kezdetek - elméleti háttér: dedukciós algoritmusok, feladatok meghatározása, ’80-as években – nagyon nagy a támogatottsága, ˝ az érdeklodés ˝ késobb csökkent, de 1997-ben a DEEP BLUE nyer a sakk-világbajnok ellen 8/364

˝ M.I. fejlodése évszámokban ’50 Turing: „Computing Machinery and Intelligence”;

Mesterséges Intelligencia

1

’56 Dartmouth: „Mesterséges Intelligencia”;

Csató Lehel

’52–’69 „Look, Ma, no hands!”1 ;

Tudnivalók

’50– Sakk – Samuel, logika – Newell & Simon, „Geometry Engine” – Gelernter;


’65 logikai következteto˝ algoritmus – Robinson;


’66–’73 Bonyolultságelmélet – csökkeno˝ támogatottság; ’69–’79 Tudásalapú rendszerek; ’80– M.I. ipari ágazat; ’86– Neurális háló modellek újra népszeruek; ˝ ’87– M.I. tudományág; 1 9/364

˝ sora. Utolsó: „Look, Ma, no teeth!” vicc utolsó elotti

˝ M.I. jelen idoben

I


„Modern AI focuses on practical engineering tasks”

1

‡ Egy pragmatikus megközelítés.

Csató Lehel Tudnivalók Bevezeto˝ ˝ Fejlodés

Tudományterületek, melyek kiváltak:

Könyvészet

Felismero˝ rendszerek: minta-, beszéd-, OCR;

Eredmények

˝ rendszerek; Szakértoi Gépi fordítás; Robotika; Játékelmélet; Dedukciós algoritmusok – Maple, Mathematica a Fermat–tétel bizonyítása, stb. ‡ http://wikipedia.org 10/364

˝ M.I. – jelen idoben Mesterséges Intelligencia

1

Cinikusan: M.I. feladat ˝ jó megoldás nem ismert; = egyelore

Csató Lehel

= bizonyított, hogy a megoldáshoz nagyon hosszú ido˝ kell.

Tudnivalók Bevezeto˝ ˝ Fejlodés Könyvészet

Sikerek:

Eredmények

˝ Deep Blue, 1997 – Gary Kasparov-ot legyozi ˝ (rendszerek, melyek legyozik a Deep Blue-t), Robbins sejtés bizonyítása, tervezés – ütemezés az 1991-es iraki háborúban: 50.000 egység koordinálása, Proverb – keresztrejtvények megfejtése. 11/364

II

Könyvészet I Mesterséges Intelligencia

S.J. Russell, P. Norvig Mesterséges intelligencia modern közelítésben. (második kiadás) Panem, 2005.

1 Csató Lehel Tudnivalók

I. Futó (szerk) Mesterséges intelligencia. Aula, 1999.

Bevezeto˝ ˝ Fejlodés Könyvészet

S.J. Russell, P. Norvig Artificial Intelligence: a Modern Approach. Prentice Hall, 1995.

Eredmények

T.M. Mitchell Machine Learning. McGraw-Hill, 1997. C.M. Bishop Pattern Recognition and Machine Learning. Springer Verlag, 2006. 12/364

Könyvészet II Mesterséges Intelligencia

C.M. Bishop Neural Networks for Pattern Recognition. Oxford University Press, 1995.

1 Csató Lehel

M.A. Arbib The Handbook of Brain Theory and Neural Networks. The MIT Press, 2003.

Tudnivalók Bevezeto˝ ˝ Fejlodés Könyvészet Eredmények

Könyvészet olvasása kötelezo˝ ˝ Az eloadás anyaga csupán útmutató a tanuláshoz és segít a jegyzetelés megkönnyítésében.

Könyvészet olvasása kötelezo˝ II A vetített anyag nem elégséges a vizsgához. 13/364

M.I. algoritmusok gyakorlatban Mesterséges Intelligencia

1

Index - ’05 okt. 2 – Nyelveket tanul a szoftver Automatic DIstillation Of Structures (ADIOS)

Csató Lehel Tudnivalók Bevezeto˝

„Cél az agyban lévo˝ szintaktikus és szemantikus ismeretek ... számítógépes modellezése.”

˝ Fejlodés Könyvészet Eredmények

„A rendszer nyers adatokból (szöveg, beszéd, aminósav, hangjegy) SZABÁLYOKAT határoz meg.”

http://adios.tau.ac.il 14/364

I


1

www.agent.ai – ’05 szept. 19 – Pontosan utánoz a mukéz ˝

Csató Lehel Tudnivalók

A Southampton-i Egyetem mesterséges végtagja

Bevezeto˝ ˝ Fejlodés Könyvészet Eredmények

A „Remedi-Hand” (Rehabilitation and Medical Research Trust) parányi feldolgozó egységen keresztül kapcsolódik a karizmokkal. A készüléket a csuklót mozgató izmok összehúzódásai vezérlik. 15/364

II


III

www.agent.ai – ’05 szept. 16 – Tökéletes ujjlenyomatok

1 Csató Lehel

Genetikus algoritmusok a bunüldözésben ˝

Tudnivalók Bevezeto˝ ˝ Fejlodés

Ujjlenyomatokról készült képek tömörítésekor nagyon óvatosan kell eljárni: a legcsekélyebb torzulás is hasznavehetetlenné teheti az ujjlemyonat képét.


16/364


1 Csató Lehel Tudnivalók Bevezeto˝ ˝ Fejlodés Könyvészet Eredmények

yahoo.com – ’05 okt. 9 – Stanford Volkswagen Wins $2M Robot Race Defense Advanced Research Projects Agency, DARPA director Dr. Tony Tether, sets a medal on Stanford Racing Team’s Stanley #03.

http://robots.stanford.edu/ 17/364

Sebastian Thrun

IV

Let’s Talk! The computer can translate

V


mouthing words in Mandarin

1 Csató Lehel

11 electrodes attached on face and neck

Tudnivalók Bevezeto˝ ˝ Fejlodés Könyvészet

computer program to figure out what he was saying

Eredmények

http://www.postgazette.com/pg/05301/596293.stm

Fontos kérdések az implementáció folyamán: Milyen 18/364

modellek

,

rendszerek

,

algoritmusok

voltak használva.

Feladat

?házi?


1 Csató Lehel Tudnivalók Bevezeto˝

Találjatok a fentiekhez hasonló példákat, ahol a „mesterséges intelligens” eszközök sikeresek voltak.

˝ Fejlodés Könyvészet Eredmények

+5 pont - kis bemutató

19/364



2


Csató Lehel


Reprezentáció


Állapottér


Keresés Hill-climbing


Backtracking Gráfkeresés

Fuzzy rendszerek

Dekompozíció Predikátumkalkulus Rezolúció

Grafikus modellek

˝ Keresorendszerek

Tanuló rendszerek Szimulált kifutés, ˝ Genetikus algoritmusok A perceptron modell ˝ Neurális hálók, önszervezodés Gépi tanulás 20/364

Admin ...



2 Csató Lehel Reprezentáció

... trívia


Állapottér Keresés Hill-climbing

Laborgyakorlatok:


1


18%

2

Játékelmélet

10%

3


12%

4



˝ Keresorendszerek


sok%

„Tudás”reprezentáció Mesterséges Intelligencia

2

Ismeretek számítógépes formában való tárolása

Csató Lehel Reprezentáció Állapottér Keresés Hill-climbing Backtracking Gráfkeresés Dekompozíció Predikátumkalkulus Rezolúció

˝ Keresorendszerek

vagy: Hanoi tornyok feladata

1 22/364

2

3

„Tudás”reprezentáció Mesterséges Intelligencia

2

Hanoi tornyok feladata

Csató Lehel Reprezentáció

1

Állapottér Keresés

2

3

Hill-climbing

Dekompozíció

1

2

3

vég Állapotok


=⇒

kezdeti

(3, 3, 3)

Predikátumkalkulus

=⇒

(1, 1, 1)

Rezolúció

˝ Keresorendszerek

Szabály: nem helyezheto˝ egy korong egy nála kisebb korong tetejére. Szabály =⇒ Állapottér 23/364

„Állapottér” Mesterséges Intelligencia

2 Csató Lehel Reprezentáció Állapottér Keresés Hill-climbing Backtracking Gráfkeresés

(3,3,3)

Állapottér: szabályos lépések sorozata. Ábrázolási mód: irányítatlan gráf, minden lépés megfordítható.

(1,2,3)

(1,1,3)

(2,2,3) (3,1,3) (3,2,3)

(1,1,2)

Predikátumkalkulus

˝ Keresorendszerek

(1,3,3)

(2,1,3)

Dekompozíció

Rezolúció

(2,3,3)

(2,2,1)

Csúcs – állapot (3,1,2)

(2,1,2)

(1,2,1)

(3,2,1)

Él – lépés (3,2,2)

(2,3,2) (1,3,1)

(3,1,1)

Gráf

(2,2,2) (1,2,2) (1,3,2) (3,3,2) (3,3,1) (2,3,1) (2,1,1) (1,1,1) 24/364

„Feladat” Mesterséges Intelligencia

2 Csató Lehel Reprezentáció Állapottér Keresés

Feladat: a kezdeti állapotból: (3, 3, 3) a cél-állapotba (1, 1, 1) eljutni.

(3,3,3) (2,3,3)

Kezd˝o (1,3,3) (1,2,3)

Hill-climbing Backtracking Gráfkeresés Dekompozíció

Gráfkiterjesztés költséges

Predikátumkalkulus Rezolúció

˝ Keresorendszerek

(3,2,1) (3,1,1)

Cél (2,3,1) (2,1,1) (1,1,1) 25/364

Megoldáskeresés az állapottérben Mesterséges Intelligencia

Hegymászó módszer

2 Csató Lehel Reprezentáció Állapottér Keresés

Heurisztika: az állapotokhoz rendel egy numerikus függvényt, mely maximum a kezdeti állapotban és minimum a vég állapotban.

Hill-climbing Backtracking

Val(CS) =

Gráfkeresés Dekompozíció Predikátumkalkulus

X

Rezolúció

k

˝ Keresorendszerek

kezdeti = 9 vég = 3

26/364

Pozk

Megoldás a hegymászó módszerrel Mesterséges Intelligencia

2

(3,3,3)

Hegymászó módszer (Hill climbing)

(2,3,3)

Csató Lehel

(1,3,3)

Hegymászó: Reprezentáció

(1,2,3)

˝ ÁLLAPOT ⇐ kezdoállapot

Állapottér Keresés

Amíg ÁLLAPOT 6= CÉLÁLLAPOT

Hill-climbing

(2,2,3)


Válassz ÚJ_ÁLLAPOT-ot ÁLLAPOT ⇐ ÚJ_ÁLLAPOT


(3,2,3) (2,2,1)

˝ Keresorendszerek

(1,2,1)

A következo˝ lépés: A Val(CS) legkisebb – ˝ ol ˝ különbözo˝ – szülot csúcs.

(1,3,1)

(3,2,1) (3,1,1)

(3,3,1) (2,3,1) (2,1,1) (1,1,1) 27/364

Hegymászó módszer Mesterséges Intelligencia

(3,3,3)

2 (2,3,3)

Csató Lehel Reprezentáció Állapottér

˝ Jellemzok: Heurisztika nem bizonyítható a konvergencia,

Keresés Hill-climbing Backtracking Gráfkeresés Dekompozíció

(1,3,3)

(2,1,3)

(1,2,3)

(1,1,3)

(2,2,3) (3,1,3) (3,2,3) (2,2,1)

Predikátumkalkulus

Nem kerüli el a ciklusokat,

Rezolúció

˝ Keresorendszerek

˝ függ a paraméterezéstol: például a (2, 2, 2)-be nem írható algoritmus.

(1,2,1) (1,3,1)

(3,2,1) (3,1,1)

(3,3,1) (2,3,1) (2,1,1) (1,1,1) 28/364

Backtracking Mesterséges Intelligencia

2 Csató Lehel

I (3,3,3)

Visszalépéses keresés Visszalép:

(2,3,3)

(1,3,3)

˝ ÚT ←− kezdoállapot

Reprezentáció Állapottér

(1,2,3)

Amíg ÚT–vég nem CÉL

Keresés

Válassz SZ az út végére alkalmazható muveletek ˝ v. visszalép ÚT ←− SZ(ÚT)

Hill-climbing Backtracking Gráfkeresés Dekompozíció Predikátumkalkulus Rezolúció

(2,2,3) (3,2,3) (2,2,1)

˝ Keresorendszerek

(1,2,1)

A választásnál lehet a definiált célfüggvényt használni.

(1,3,1)

(3,2,1) (3,1,1)

SZ = szabály (3,3,2) (3,3,1) (2,3,1) (2,1,1) (1,1,1) 29/364

Backtracking Mesterséges Intelligencia

Összefoglaló (3,3,3)

Visszalépéses keresés

2 (2,3,3)

Csató Lehel

(1,3,3)

Reprezentáció

(1,2,3)


Fontos:

Backtracking

(2,2,3)

a heurisztika → hatékonyság,


(3,2,3) (2,2,1)

maximális úthossz korlátozás,

Rezolúció

˝ Keresorendszerek

jobb megoldás de nem optimális.

(1,2,1) (1,3,1)

(3,2,1) (3,1,1)

(3,3,2) (3,3,1) (2,3,1) (2,1,1) (1,1,1) 30/364

Gráfkeresés Mesterséges Intelligencia

I 1

Keresés gráfban

(3,3,3)

2 Csató Lehel

Algoritmus:

2

(2,3,3)

(1,3,3)

˝ GRÁF ←− kezdoállapot


3

(1,2,3)

Amíg GRÁF 3 CÉL


Válassz SZ GRÁF-ra alkalmazható muveletek ˝ GRÁF ←− SZ(GRÁF)

Backtracking Gráfkeresés Dekompozíció Predikátumkalkulus Rezolúció

˝ Keresorendszerek

A választásnál lehet a definiált célfüggvényt használni. SZ = szabály 31/364

4

(2,2,3)

(3,2,3)

5

(2,2,1) 6

8

(1,2,1)

(3,2,1)

7

9

(1,3,1)

(3,1,1)

(3,3,1) (2,3,1) (2,1,1) (1,1,1)

Gráfkeresés

II 1


2

(3,3,3)

Keresés gráfban

Csató Lehel

2

(2,3,3)

(1,3,3) 3


Felépíti a gráfot,

Keresés

A legköltségesebb,


nem találja meg a legrövidebb utat;

Gráfkeresés Dekompozíció Predikátumkalkulus Rezolúció

(1,2,3) 4

(2,2,3)

(3,2,3)

5

(2,2,1)

Elérhetjük a célcsúcsot úgy is, hogy

˝ Keresorendszerek

olyan csúcso(ka)t hagyunk ki, melyek a legrövidebb út részei lennének.

6

8

(1,2,1)

(3,2,1)

7

9

(1,3,1)

(3,1,1)

(3,3,1) (2,3,1) (2,1,1) (1,1,1) 32/364

Feladat dekompozíció Mesterséges Intelligencia

2 Csató Lehel

Rekurzív függvényhívás iskolapéldája Jelölje: hn, i, j, ki a muveletet, ˝ melyben a legfelso˝ n korongot


az i-edik rúdról

Keresés

a j-edik rúdra helyezzük

Hill-climbing Backtracking Gráfkeresés

a k-adik rúd segítségével


˝ Keresorendszerek

A feladat dekomponálható: hn, i, j, ki −→ hn − 1, i, k, ji h1, i, j, ki hn − 1, k, j, ii ha n > 1 n = 1 – nem kell tovább bontani a feladatot 33/364

I

Feladat dekompozíció

II

h3, 3, 1, 2i


2 Csató Lehel

h2, 3, 2, 1i

h1, 3, 1, _i

h2, 2, 1, 3i

Reprezentáció Állapottér Keresés

h1, 3, 1, _i

h1, 3, 2, _i

h1, 1, 2, _i

h1, 2, 3, _i

h1, 2, 1, _i

h1, 3, 1, _i

Hill-climbing Backtracking Gráfkeresés Dekompozíció Predikátumkalkulus

ÉS/VAGY gráf:

Rezolúció

csúcs = probléma

˝ Keresorendszerek

köteg - a részfeladatok, melyeket meg kell oldani a feladat megoldásához. Itt nincs VAGY csúcs. megoldás = részgráf, melyben minden részprobléma csupa megoldható problémára vezetheto˝ vissza. 34/364

Predikátumkalkulus Mesterséges Intelligencia

2

I

Szabályalapú következtetés t(i, j) – legfelso˝ korong i ⇒ j mozgatása.

Csató Lehel Reprezentáció Állapottér Keresés

A feladat megoldása mozgatások sorozata ⇒ lista Lista: a.b.c.nil

Hill-climbing Backtracking Gráfkeresés

A(·, ·, ·) – append

Lista axiómái:

Dekompozíció Predikátumkalkulus

(1)

Rezolúció

˝ Keresorendszerek

(2)

A(nil, r, r) A(u, v, w) → A(s.u, v, s.w)

(1) – Üres lista nem változtat az eredményen ˝ (2) – Ha w az u és v összetétele, ez érvényes egy s elotaggal is. 35/364


Hanoi tornyai axiómái:

2 Csató Lehel

(3)

H(1, i, j, k, t(i, j).nil)

Reprezentáció

(4)

H(n − 1, i, k, j, y) ∧ H(1, i, j, k, t(i, j).nil) ∧ H(n − 1, k, j, i, z) ∧ A(y, t(i, j).z, x)

Állapottér

→ H(n, i, j, k, x)

Keresés Hill-climbing Backtracking Gráfkeresés Dekompozíció Predikátumkalkulus Rezolúció

˝ Keresorendszerek

(3) – 1 elemet átteszünk: t(i, j) ˝ n − 1 elemet mozgatunk y (4) – n elem áttételéhez elobb sorozattal, egy elemet t(i, j)-vel, majd n − 1-et vissza.

Kérdés:

(5)

(∃x) H(2, 1, 2, 3, x)

(5) – azon mozgatások, melyek megvalósítják 2 korong mozgatását. 36/364

II


Algoritmus:

2

GRÁF ⇐= célállítás

Csató Lehel

Amíg GRÁF-ban nincs ellentmondásmentes levezetés


Válassz SZ a GRÁF-hoz alkalmazható illesztések vagy visszalépés

Keresés Hill-climbing Backtracking Gráfkeresés Dekompozíció

GRÁF ⇐= SZ(GRÁF)

Predikátumkalkulus Rezolúció

˝ Keresorendszerek

Egy ÉS/VAGY gráfot járunk be és keresünk egy gráfot, ˝ mely tényekben végzodik és nem ellentmondóak az illesztések. 37/364

III

Rezolúció Mesterséges Intelligencia

I

Két elemu˝ Hanoi-toronyra a kérdés:

2 (∃x) H(2, 1, 2, 3, x)

Csató Lehel Reprezentáció Állapottér Keresés Hill-climbing Backtracking Gráfkeresés Dekompozíció Predikátumkalkulus

Rezolúció: bizonyítani, hogy az axiómákból következik a célállítás. Módszer: Tagadjuk a kijelentést és bizonyítjuk, hogy ez utóbbi hamis.

Rezolúció

˝ Keresorendszerek

A→B

⇔

A∨B

⇔

A∧B

⇐⇒ (1) ∧ (2) ∧ (3) ∧ (4) ∧ (5)

38/364

kielégíthetetlen

(5) = (∀x) H(2, 1, 2, 3, x)


2 Csató Lehel Reprezentáció Állapottér

II

Bizonyítás: ellentmondásos axiómarendszer: (1)

(∀r)

A(nil, r, r)

(2)

(∀ . . .) A(u, v, w) ∨ A(s.u, v, s.w)

(3)

(∀ . . .) H(1, i, j, k, t(i, j).nil)

(4)

(∀ . . .) H(n − 1, i, k, j, y) ∨ H(1, i, j, k, t(i, j).nil) ∨

Keresés Hill-climbing Backtracking Gráfkeresés Dekompozíció Predikátumkalkulus Rezolúció

H(n − 1, k, j, i, z) ∨ A(y, t(i, j).z, x) ∨ H(n, i, j, k, x)

˝ Keresorendszerek

(5)

(∀x)

H(2, 1, 2, 3, x)

Cáfolati gráf: létezik út, melyre fennáll az (1) − (4) és (5). 39/364

Figyeljük meg az univerzális kvantorokat!


Példa H(2, 1, 2, 3, x)

2

H(n, i, j, k, x)


H(1, 1, 3, 2, y) H(1, 1, 2, 3, t(1, 2).nil) H(1, 3, 2, 1, z) A(y, t(1, 2).z, x)

Hill-climbing

y=t(1,3).nil

Backtracking Gráfkeresés Dekompozíció Predikátumkalkulus

z=t(3,2).nil

H(1, i, j, k, t(i, j).nil) H(1, i, j, k, t(i, j).nil) H(1, i, j, k, t(i, j).nil)

Rezolúció

˝ Keresorendszerek

A(s.u, v, s.w) A(nil, r, r) s=t(1,3) v=t(1,2).z

A(nil, t(1, 2).z, w) w=t(1,2).z

A(nil, r, r) 40/364


Példa H(2, 1, 2, 3, x)

2

H(n, i, j, k, x)


H(1, 1, 3, 2, y) H(1, 1, 2, 3, t(1, 2).nil) H(1, 3, 2, 1, z) A(y, t(1, 2).z, x)

Hill-climbing

y=t(1,3).nil


z=t(3,2).nil


Rezolúció

˝ Keresorendszerek


A(nil, t(1, 2).z, w) w=t(1,2).z

A(nil, r, r) 40/364


Példa H(2, 1, 2, 3, x)

2

H(n, i, j, k, x)


H(1, 1, 3, 2, y) H(1, 1, 2, 3, t(1, 2).nil) H(1, 3, 2, 1, z) A(y, t(1, 2).z, x)

Hill-climbing

y=t(1,3).nil


z=t(3,2).nil


Rezolúció

˝ Keresorendszerek


A(nil, t(1, 2).z, w) w=t(1,2).z

A(nil, r, r) 40/364


Példa H(2, 1, 2, 3, x)

2

H(n, i, j, k, x)


H(1, 1, 3, 2, y) H(1, 1, 2, 3, t(1, 2).nil) H(1, 3, 2, 1, z) A(y, t(1, 2).z, x)

Hill-climbing

y=t(1,3).nil


z=t(3,2).nil


Rezolúció

˝ Keresorendszerek


A(nil, t(1, 2).z, w) w=t(1,2).z

A(nil, r, r) 40/364


Példa H(2, 1, 2, 3, x)

2

H(n, i, j, k, x)


H(1, 1, 3, 2, y) H(1, 1, 2, 3, t(1, 2).nil) H(1, 3, 2, 1, z) A(y, t(1, 2).z, x)

Hill-climbing

y=t(1,3).nil


z=t(3,2).nil


Rezolúció

˝ Keresorendszerek


A(nil, t(1, 2).z, w) w=t(1,2).z

A(nil, r, r) 40/364


Példa H(2, 1, 2, 3, x)

2

H(n, i, j, k, x)


H(1, 1, 3, 2, y) H(1, 1, 2, 3, t(1, 2).nil) H(1, 3, 2, 1, z) A(y, t(1, 2).z, x)

Hill-climbing

y=t(1,3).nil


z=t(3,2).nil


Rezolúció

˝ Keresorendszerek


A(nil, t(1, 2).z, w) w=t(1,2).z

A(nil, r, r) 40/364


Példa H(2, 1, 2, 3, x)

2

H(n, i, j, k, x)


H(1, 1, 3, 2, y) H(1, 1, 2, 3, t(1, 2).nil) H(1, 3, 2, 1, z) A(y, t(1, 2).z, x)

Hill-climbing

y=t(1,3).nil


z=t(3,2).nil


Rezolúció

˝ Keresorendszerek


A(nil, t(1, 2).z, w) w=t(1,2).z

A(nil, r, r) 40/364


Példa H(2, 1, 2, 3, x)

2

H(n, i, j, k, x)


H(1, 1, 3, 2, y) H(1, 1, 2, 3, t(1, 2).nil) H(1, 3, 2, 1, z) A(y, t(1, 2).z, x)

Hill-climbing

y=t(1,3).nil


z=t(3,2).nil


Rezolúció

˝ Keresorendszerek


A(nil, t(1, 2).z, w) w=t(1,2).z

A(nil, r, r) 40/364


Példa H(2, 1, 2, 3, x) x=t(1,3).t(1,2).t(3,2).nil

2

H(n, i, j, k, x)

Csató Lehel

x=y.t(1,2).z

Reprezentáció Állapottér Keresés

H(1, 1, 3, 2, y) H(1, 1, 2, 3, t(1, 2).nil) H(1, 3, 2, 1, z) A(y, t(1, 2).z, x)

Hill-climbing

y=t(1,3).nil


z=t(3,2).nil


Rezolúció

˝ Keresorendszerek


A(nil, t(1, 2).z, w) w=t(1,2).z

A(nil, r, r) 40/364

˝ Keresorendszerek Mesterséges Intelligencia

2 Csató Lehel

˝ Keresorendszerek (Production systems)


Különválasztják a

Keresés

feladat adatait ;


az adatokon értelmezett muveleteket ˝ ;


a vezérlést, mely a muveleteket ˝ algoritmussá szervezi.

Rezolúció

˝ Keresorendszerek

˝ Keresorendszer: (Adat,Szabály,Vezérlés)

41/364

I

˝ Keresorendszerek

II


2

Általános stratégia: ADAT ← Kezdeti adatbázis

Csató Lehel

AMÍG ADAT nem terminális

Reprezentáció

Válassz SZ az ADAT-ra alkalmazható szabályok közül,


ADAT ← SZ(ADAT)


˝ Keresorendszerek

Keresési stratégia: az alkalmazható szabályok közül egyet kiválaszt. Keresési stratégia: ˝ elorehaladó – visszafelé haladó – kétirányú – bidirectional 42/364

hegymászó, visszalépés, gráf szabályalapú

˝ Keresorendszerek

II


2


Csató Lehel


Reprezentáció



ADAT ← SZ(ADAT)


˝ Keresorendszerek



˝ Keresorendszerek

II


2


Csató Lehel


Reprezentáció



ADAT ← SZ(ADAT)


˝ Keresorendszerek



Ismeretábrázolás Mesterséges Intelligencia

2 Csató Lehel

Ismeretek osztályozása:

Reprezentáció

deklaratív ismeret

Állapottér

állapot,részprobléma,axiómák

procedurális ismeret


vezérlési ismeret

Backtracking

muvelet, ˝ dekompozíció VAL függvény


˝ Keresorendszerek

Közös vonás: gráf ADAT

43/364

= =

=⇒

gráfreprezentáció.

a reprezentációs gráf egy részgráfja. „Ablak”, melyet a szabályok módosítanak, egy csúcs, egy részgráf.

Keresési stratégiák Mesterséges Intelligencia

2 Csató Lehel

Gráfkeresési stratégiák: ˝ Elsodleges stratégia


nem-módosítható stratégia (hegymászó, rezolúció) módosítható stratégia (szabályok választása)

Keresés Hill-climbing Backtracking

másodlagos stratégia – figyelembe veszi az adott reprezentációt.


˝ Keresorendszerek

Módosítható stratégiák: visszalépéses keresés – BackTracking gráfkereso˝ – GraphSearch

44/364

2 Csató Lehel

bá Sza


alm lyalk

Keresés Hill-climbing Backtracking Gráfkeresés Dekompozíció Predikátumkalkulus

azás

Rezolúció

˝ Keresorendszerek

Futási ido˝

Vál asz tás


köl tsé ge

Költség

A heurisztika szerepe

Információ No free lunch. 45/364

˝ optimizálni. Nehéz a futási idot Közelíto˝ megoldások „javasoltak”.

Négyes hanoi torony

Opc. feladat


2 Csató Lehel Reprezentáció Állapottér Keresés Hill-climbing Backtracking Gráfkeresés Dekompozíció Predikátumkalkulus Rezolúció

A háromoszlopos hanoi toronynál az elso˝ oszlop korongjait kell egyenként áthelyezni a második oszlopra úgy, hogy mindhárom ˝ felfele oszlopon a korongok lentrol csökkeno˝ sorrendben legyenek.

1

2

3

4

Három oszlop esetében N korong áthelyezéséhez szükséges lépések száma 2N − 1. A feladatot módosítjuk úgy, hogy egy negyedik oszlopra is pakolhatunk. Ekkor a lépések száma csökken. Negy oszlopos Hanoi torony

Hanoi 3 −−−−−−−−−−−− Kettot levesz

1e10 1e9 1e8 1e7 1e6

˝ Keresorendszerek

Feladat Írjunk programot mely a négy-oszlopos .Hanoi tornyokat kevés lépésszámmal oldja meg.

(5 pont) 46/364

1e5

5

10

15

20

25

30

35

Opcionális feladat



3


Csató Lehel


Hogyan írjunk jól angolul?


Gráfok ábrázolása

Játékok modellezése Bizonytalanság kezelése

Irányított gráfok Irányított utak Optimális út

Fuzzy rendszerek

Irányított fa ÉS/VAGY gráfok

Grafikus modellek

ÉS/VAGY gráfok átalakítása

Tanuló rendszerek

Problémák reprezentációja

Szimulált kifutés, ˝ Genetikus algoritmusok

Gráfkereso˝ algoritmusok

A perceptron modell

Visszalépés

Gráfkeresési feladatok

˝ Neurális hálók, önszervezodés Gépi tanulás 47/364

Admin ...



3 Csató Lehel Hogyan írjunk jól angolul? Gráfok ábrázolása

... trívia

Vizsga Szóbeli (60%) + Gyakorlat (40%) Laborgyakorlatok:

Irányított gráfok Irányított utak Optimális út

1


18%

2

Játékelmélet

10%

3


12%

4


Irányított fa ÉS/VAGY gráfok ÉS/VAGY gráfok átalakítása

Problémák reprezentációja Gráfkereso˝ algoritmusok Visszalépés



sok%

Hogyan írjunk jól angolul? Mesterséges Intelligencia

˝ szoftvere. A WhiteSmoke “szövegérto”


˝ „Elofordul, hogy jól beszélünk angolul, ám fontos leveleinkbe ˝ becsúsznak hibák és a címzett az eredeti szándéktól különbözonek olvashatja mondandónkat. Egy izraeli szoftver a helyesíráson és a nyelvtanon túlmutató megoldást kínál.”

Irányított gráfok Irányított utak Optimális út Irányított fa ÉS/VAGY gráfok ÉS/VAGY gráfok átalakítása

˝ oje ˝ csak e két Míg például a Word helyesírási és nyelvtani ellenorz területen hatékony, addig jelen szoftver lényegesen többet tud: a


szöveget mesterséges intelligencia segítségével fürkészi át, majd azt pontosabbá, egyértelmubbé ˝ és folyékonyabbá tevo˝ javaslatokkal áll


˝ (azaz ?kozmetikáz?) elo.

Visszalépés


agent.ai 49/364

I

Hogyan írjunk jól angolul? Mesterséges Intelligencia

3 Csató Lehel Hogyan írjunk jól angolul? Gráfok ábrázolása Irányított gráfok Irányított utak Optimális út Irányított fa ÉS/VAGY gráfok ÉS/VAGY gráfok átalakítása



50/364

II

Gráfkereso˝ stratégiák Mesterséges Intelligencia

3

˝ Egy korai M.I. terület - külön tudományággá fejlodött

Csató Lehel Hogyan írjunk jól angolul? Gráfok ábrázolása

Nagyon sok feladatot lehet gráfokkal reprezentálni: a gráfreprezentáció az algoritmusok keresési tere.

Irányított gráfok

1

irányított gráfok

2

ÉS/VAGY gráfok

Irányított utak Optimális út Irányított fa ÉS/VAGY gráfok ÉS/VAGY gráfok átalakítása


Példák:


Hanoi tornyok

Visszalépés

Irányított gráf?


51/364

reverzibilis lépések – irányítatlan gráf

Irányított GRÁFOK Mesterséges Intelligencia

3

Jelölés:

1

N – csúcsok (nodes)

Csató Lehel

A – élek A ⊂ N × N (adjacency)


szülo˝ – 1 a 2-nek

Gráfok ábrázolása Irányított gráfok

6 4

3

utód – . . .

Irányított utak

7

Optimális út

c(n, m) – költség


2

5

Tulajdonságok:



σ-tulajdonság:

∃σ ∀n |{m|(n, m) ∈ A}| ≤ σ

δ-tulajdonság:

∃δ > 0 ∀(n, m) ∈ A c(n, m) ≥ δ hyper

52/364

Gráfok ábrázolása Mesterséges Intelligencia

3

δ-gráfok = a δ és σ tulajdonsággal rendelkezo˝ gráfok.

Csató Lehel Hogyan írjunk jól angolul? Gráfok ábrázolása Irányított gráfok Irányított utak Optimális út Irányított fa ÉS/VAGY gráfok ÉS/VAGY gráfok átalakítása


× 1 2 3 4 5 6 7

1 . . . . 1 1 1

2 1 . . . . . .

3 . 1 . 1 . . 1

4 . . 1 . . . .

5 . . . . . 1 .

6 . . . . . . .

7 . . . 1 1 . .

1 2

6 4

3 7 5

Gráfkereso˝ algoritmusok Visszalépés


Konvenció: amennyiben nem specifikáljuk, az élek bejárásának a költsége 1. 53/364

Irányított utak Mesterséges Intelligencia


˝ az m-be Irányított út – út: az n-bol Ha ∃ n1 , . . . , nk úgy hogy {(n, n1 ), . . . , (nk , m)} ∈ A. Út: α = (n = n0 , n1 , . . . , nk = m)

1

Irányított gráfok Irányított utak Optimális út Irányított fa ÉS/VAGY gráfok

2

Út költsége

6 4


Problémák reprezentációja Gráfkereso˝ algoritmusok

α

c (n, m) =

k X j=1

3

c(nj−1 , nj )

7 5

Visszalépés


Példa: α = (6, 5, 7, 3, 4, 3, 4, 7, 5, 1, 2) költsége 10. 54/364

Irányított utak Mesterséges Intelligencia


˝ az m-be Irányított út – út: az n-bol Ha ∃ n1 , . . . , nk úgy hogy {(n, n1 ), . . . , (nk , m)} ∈ A. Út: α = (n = n0 , n1 , . . . , nk = m)

1

Irányított gráfok Irányított utak Optimális út Irányított fa ÉS/VAGY gráfok

2

Út költsége

6 4



α

c (n, m) =

k X j=1

3

c(nj−1 , nj )

7 5

Visszalépés


Példa: α = (6, 5, 7, 3, 4, 3, 4, 7, 5, 1, 2) költsége 10. 54/364

Optimális út Mesterséges Intelligencia

3

˝ az m-be Optimális költség: az n-bol c∗ (n, m) =

Csató Lehel Hogyan írjunk jól angolul? Gráfok ábrázolása Irányított gráfok

min

cα (n, m)

α∈{n→m}

˝ az m-be Optimális út: az n-bol

Irányított utak Optimális út

α∗ (n, m) = arg


min

cα (n, m)

α∈{n→m}


?

Visszalépés

Létezik mindig – optimális – út?


Amennyiben igen, egyedi? 55/364

nem. Ekkor az út hossza ∞ nem - δ-gráf


3



min

cα (n, m)

α∈{n→m}



α∗ (n, m) = arg


min

cα (n, m)

α∈{n→m}


?

Visszalépés






3



min

cα (n, m)

α∈{n→m}



α∗ (n, m) = arg


min

cα (n, m)

α∈{n→m}


?

Visszalépés






3



min

cα (n, m)

α∈{n→m}



α∗ (n, m) = arg


min

cα (n, m)

α∈{n→m}


?

Visszalépés





Irányított Fa Mesterséges Intelligencia

3

Irányított fa: gráf, melyben egy kitüntetett csúcsból - a ˝ – minden más csúcsba csak egy út vezet. gyökérbol

Csató Lehel Hogyan írjunk jól angolul?

A gyökérbe nem vezet él.

Gráfok ábrázolása Irányított gráfok Irányított utak Optimális út

˝ nem vezet ki él. Levél – csúcs, melybol



Tulajdonságok: Bejárása egyszeru; ˝

Visszalépés


Nem minden feladat ábrázolható faként. 56/364

ÉS/VAGY gráfok Mesterséges Intelligencia


ÉS/VAGY gráfok Olyan irányított hipergráfok, melyekben egy hiperél egy csúcsból egy csúcshalmazba vezet. R(N, A)

ahol

A ⊆ {(n, M) ∈ N × 2N |0 6= |M| ≤ ∞}




Hiperélek: (1, {2, 3}) (1, {4}) (2, {5, 6}) (3, {7}) (4, {6, 7}) (7, {6})

1

2

3

4

Élköltség: c(n, M) Kérdés: σ és δ tulajdonságok G 57/364

5

6

7

Hiperutak ÉS/VAGY gráfokban Mesterséges Intelligencia

3 Csató Lehel Hogyan írjunk jól angolul?

Irányított hiperút (n, M) között Részgráf, melyben mindegyik csúcsból legfeljebb egy hiperél indul ki. ˝ nem indul hiperél. M-bol

Gráfok ábrázolása Irányított gráfok Irányított utak

Hiperutak 1 → {5, 6}:

1

Optimális út Irányított fa ÉS/VAGY gráfok ÉS/VAGY gráfok átalakítása

(1, {2, 3}), (2, {5, 6})


2

3

4

(1, {2, 3}), (3, {6}),


(1, {4}), (4, {5})


58/364

5

6

7

ÉS/VAGY gráfok átalakítása Mesterséges Intelligencia

3 Csató Lehel Hogyan írjunk jól angolul? Gráfok ábrázolása Irányított gráfok Irányított utak Optimális út

ÉS/VAGY gráfok kezelése nehézkes. Átalakíthatóak irányított gráfokká. Új csúcsok bevezetése: utódcsúcs = átalakítandó hiperél utódainak halmaza. ˝ A fenti muveletet ˝ kiterjesszük a kezdocsúcstól a célig. 1



Feladat: az 1 → {5, 6} egy hiperútjának megfelelo˝ gráfátalakítás.


2

5 59/364

3

4

6

7

8-as kirakós játék Mesterséges Intelligencia

2 8 3 1 4 7 6 5

3 Csató Lehel Hogyan írjunk jól angolul?

I

1 2 3 8 4 7 6 5

Gráfok ábrázolása Irányított gráfok Irányított utak Optimális út Irányított fa ÉS/VAGY gráfok

˝ Kódolás: 9 hely – 9! = 362880 lehetoség.



Üres hely mozgatása – meghatároz egy állapotgráfot.



60/364

8-as kirakós játék

II 2 8 3 1 4 7 6 5


3 Csató Lehel 2 8 3 1 6 4 7 5


2 8 3 1 4 7 6 5

2 3 1 8 4 7 6 5

2 8 3 1 4 7 6 5

2 3 1 8 4 7 6 5

2 3 1 8 4 7 6 5

2 8 1 4 3 7 6 5

1 2 3 8 4 7 6 5

2 3 4 1 8 7 6 5

Gráfok ábrázolása Irányított gráfok Irányított utak Optimális út Irányított fa

2 8 3 1 4 5 7 6

ÉS/VAGY gráfok ÉS/VAGY gráfok átalakítása


1 2 3 7 8 4 6 5


61/364

1 2 3 8 4 7 6 5

2 3 4 1 8 7 6 5

2 3 4 1 8 5 7 6

4 királyno˝ Mesterséges Intelligencia

3 Csató Lehel

˝ 4 × 4-es táblán 4 királynot elhelyezni.


Állapottér: sakk–állások ˝ 1 − 4 királynovel.


Muvelet: ˝ egy királyno˝ egy ˝ helyezése. mezore


˝ Kezdoállapot: üres sakktábla.


˝ Célállapot: 4 királynot tartalmazó sakktábla.

Visszalépés


62/364

Gráfkereso˝ algoritmusok Mesterséges Intelligencia

3

Nem-módosítható keresések: Egy lépést – szabályt – nem lehet visszavonni.

Csató Lehel 1 Hogyan írjunk jól angolul?

Hegymászó algoritmus (hill-climbing) kritérium-függvény, mely „vezérli” az algoritmust. nem-determinisztikus gond a lokális minimum jelenléte

Gráfok ábrázolása Irányított gráfok Irányított utak Optimális út

2


Kommutatív rendszerek (commutative systems) a D-re alkalmazható szabályok alkalmazhatóak a D leszármazottjaira is. ˝ eloállított ˝ a D-bol adatbázis független a muveletek ˝ ˝ – felcserélheto. ˝ sorrendjétol ha a D kielégíti a terminálási feltételt, akkor annak minden leszármazottja is.



Nincs bonyolult stratégia. Heurisztika =⇒ hatékonyság. 63/364

I

Visszalépés Mesterséges Intelligencia

Egy utat tart nyilván a reprezentációs gráfból.

3 Csató Lehel

Induló érték: start-csúcs.

Hogyan írjunk jól angolul? Gráfok ábrázolása Irányított gráfok Irányított utak

Vezérlési stratégia – visszalépés alkalmazása ha:




64/364

1

nincs több él – zsákutca;

2

nincs több „jó út” – vágás;

3

minden továbbvezeto˝ útról visszaléptünk – torkolat;

4

egy már bejárt csúcshoz jutunk – kör;

5

túl hosszú a bejárt út – mélységi korlát.

I


3

Visszalépés ha


1


2


3


4


5


Irányított utak Optimális út Irányított fa ÉS/VAGY gráfok ÉS/VAGY gráfok átalakítása


Tétel A visszalépéses algoritmus az (1) és (2) feltételekkel terminál véges és körmentes gráfokon.

Visszalépés


65/364

II


3

Visszalépés ha


1


2


3


4


5





Tétel A visszalépéses algoritmus az (1)–(5) feltételekkel mindig terminál. Ha létezik a mélységi korlátnál nem hosszabb megoldás, megtalálja azt.

65/364

II

Buvös ˝ négyzetek I Mesterséges Intelligencia

3

Feladat: ábrázoljuk a buvös ˝ négyzetek keresését gráf-kiterjesztési feladatként: építsük fel a feladat állapotterét; defniáljunk egy gráfot a helyes megoldásokat eredményezo˝ kitöltések folyamataként;


definiáljunk egy gráfkiterjesztési procedúrát;

Irányított gráfok Irányított utak

keressük meg az összes lehetséges megoldást gráfkereso˝ (?backtracking?) módszerrel.



1. laborfeladat

Buvös ˝ négyzet: az az N × N-es négyzet, melyben az elemek száma megegyezik sorok és oszlopok szerint.



Ssor

N2 N N2 + 1 1 X 1 N2 N2 + 1 = n= · = N N 2 2 n=1

66/364

Buvös ˝ négyzetek II Mesterséges Intelligencia

1. laborfeladat

Követelmények:

3

Dokumentáció, mely tartalmazza a

Csató Lehel 1 Hogyan írjunk jól angolul?

2 3

Gráfok ábrázolása

paraméterterét a feladatnak, a gráfkiterjesztés lépéseit, a gráfbejárás sorrendjét.

Irányított gráfok Irányított utak

Program, mely az N szám ismeretében kiírja (pl. egy TXT állományba) az összes megoldást valamint kiírja ˝ a megoldások számát. a képernyore



.

Visszalépés

A bemutatás személyesen történik – valamely futtatási környezetben – úgy, hogy a programban módosítani lehessen paramétereket.


(8 pont) 67/364

Kötelezo˝ feladat

Buvös ˝ négyzetek II Mesterséges Intelligencia

3 Csató Lehel Hogyan írjunk jól angolul? Gráfok ábrázolása Irányított gráfok Irányított utak Optimális út Irányított fa ÉS/VAGY gráfok ÉS/VAGY gráfok átalakítása



Example: 93 108 123 107 122 137 121 136 151 135 150 165 149 164 10 163 9 24 8 23 38 22 37 52 36 51 53 50 65 67 64 66 81 78 80 95 79 94 109 68/364

138 152 166 11 25 39 40 54 68 82 96 110 124

153 167 12 26 27 41 55 69 83 97 111 125 139

168 13 14 28 42 56 70 84 98 112 126 140 154

Példa 1 15 29 43 57 71 85 99 113 127 141 155 169

16 30 44 58 72 86 100 114 128 142 156 157 2

31 45 59 73 87 101 115 129 143 144 158 3 17

46 60 74 88 102 116 130 131 145 159 4 18 32

61 75 89 103 117 118 132 146 160 5 19 33 47

76 90 104 105 119 133 147 161 6 20 34 48 62

91 92 106 120 134 148 162 7 21 35 49 63 77

Sudoku Mesterséges Intelligencia

3 Csató Lehel

2. laborfeladat

A sudoku-ban számokat helyezünk el egy n2 × n2 méretu˝ négyzetrácsban. Az {1, . . . , n2 } számokat úgy helyezzük el n2 -szer úgy, hogy egy oszlopban, egy sorban és minden kisebb négyzetben egy szám egyszer szerepeljen (lásd ábra). Az n = 2-re mi a paraméter–tér?


1p.

Jelenítsük meg „szépen” a megoldásokat az n = 2 és n = 3 esetekre. 1p.


Az n = 2 esetre generáljuk az összes megoldást.

Optimális út Irányított fa ÉS/VAGY gráfok

1p.



Találjuk meg egy részlegesen kitöltött feladat kitöltött változatát.

3p.

× Generáljunk egy sudoku rejtvényt: egy részlegesen kitöltött feladat, melynek csak egy megoldása van.

4p.


(10 pont) 69/364

Kötelezo˝ feladat



4


Csató Lehel


Alapalgoritmus


Általános algoritmus


Példa Mélységi


Szélességi Egyenletes

Fuzzy rendszerek

˝ Eloretekint o˝

Grafikus modellek

A alg

Tanuló rendszerek

A* és Ac


Opcionális feladatok

A perceptron modell ˝ Neurális hálók, önszervezodés Gépi tanulás 70/364

Admin ...



4 Csató Lehel Alapalgoritmus

... trívia



Példa Mélységi

Laborgyakorlatok:


1


18%

2

Játékelmélet

10%

3


12%

4


˝ Eloretekint o˝ A alg A* és Ac Opcionális feladatok


sok%

Bioinformatika Mesterséges Intelligencia

4 Csató Lehel Alapalgoritmus Általános algoritmus

A számítástudomány és a molekuláris biológia között2 David Haussler & Judea Pearl Kifejlesztették az emberi genomot feltérképezo˝ ˝ programokat. A lehetoséget a számítógép-

Mélységi

˝ technológia és a biokémia fejlodése biztosította. ˝ A genom biológiai összetevoinek felderítését és

Szélességi

elemzését a tudós által kidolgozott

Egyenletes

valószínuségi ˝ megközelítés alapozta meg.

Példa


Az emberi génállomány mintegy hárommilliárd alappárt képez: a ˝ spirál-alakú DNS négy alap-nukleotidból (A, C, G, T) épül fel; kettos Minden egyes nukleotid része egy párnak. A mennyiség nagyon nagy, a munka csak számítógépes módszerekkel végezheto˝ el.

agent.ai 2 72/364

Pearl J (2000):Causality: Models, Reasoning, and Inference, The CUP Press

Bioinformatika Mesterséges Intelligencia


Példa Mélységi Szélességi Egyenletes ˝ Eloretekint o˝ A alg A* és Ac Opcionális feladatok

2001. júliusában közölték a módszer vázlatait, majd az emberi és egyéb organizmusok (egér, ˝ patkány, stb.) génszekvenciáit elemzo, jegyzetekkel ellátott interaktív webalapú ˝ keresoket fejlesztettek. Tudományos fórumot teremtettek, míg programjaikat gyakran használják különbözo˝ biomedikális kutatásoknál, kísérleteknél. A gének evolúciója A CBSE kutatásai az interdiszciplináris megközelítés jegyében folynak. Biológia, információs és nanotechnológia fúziójára, minél kisebb szerkezetek létrehozására törekednek. Az emberi genom evolúciójának jobb megértése az egyik fo"irány: a cél érdekében permanensen fejlesztik az új statisztikai és algoritmikus módszereket. 73/364

Gráfkeresés Mesterséges Intelligencia

1

4 Csató Lehel

2

6

Alapalgoritmus

4


3

Példa Mélységi

7


Feladatok:

˝ Eloretekint o˝ A alg

egy megoldás megtalálása

A* és Ac Opcionális feladatok

minimális út keresése Módszerek:

74/364

5

„Alapalgoritmus∗ ” (∗ – Futó: Mesterséges Intelligencia, 73.o)


4 Csató Lehel

I

Visszalépés – backtracking – hátránya, hogy nem találja meg az optimális utat.

Alapalgoritmus Általános algoritmus

Gráfkereso˝ algoritmus:

Példa Mélységi

a startcsúcsból indul

Szélességi

feltárja a reprezentációs gráfot

Egyenletes

1

˝ Eloretekint o˝ A alg

2

A* és Ac

s G

kiválaszt egy csúcsot, melynek utódai n ∈ NYILT nem ismertek, S kiterjeszti a választott csúcsot G ← G Γ (n)

NYILT ← NYILT S \ {n} NYILT ← NYILT Γ (n)


addig keres, amíg egy célcsúcsot nem talál és van kiterjesztheto˝ csúcs. 75/364

Alapalgoritmus Mesterséges Intelligencia

4 Csató Lehel

II

Kommutatív rendszer – a kiterjesztések bármilyen sorrendben végrehajthatók. =⇒

Alapalgoritmus

A vezérlési stratégia nem informatív,


Másodlagos stratégia ⇒ továbblépés.

Példa Mélységi Szélességi Egyenletes

Módosítás: n ← argmin f(m)

˝ Eloretekint o˝ A alg A* és Ac

m∈NYILT

ahol f : NYILT → R kiértékelo˝ függvény, amely egy csúcs „jósága”,


˝ m-be vivo˝ legkisebb út hossza. pl. az s-bol ⇒ dinamikus függvény. 76/364

(felületes def.)


III

Bevezetjük:

4 Csató Lehel

kitüntetett szülo˝ csúcsot (parent) ˝ egy utat specifikál). (az s-bol

p:G→G p(s) = nil

költségfüggvényt: ˝ m-be vivo˝ út költsége. g(m) az s-bol

g:G→R


Példa Mélységi Szélességi

Az n csúcs minden k utód-csúcsára ∀k ∈ Γ (n):

Egyenletes ˝ Eloretekint o˝

Ha k új csúcs, vagy

k 6∈ G

Ha nem új és g(k) > g(n) + c(n, k), akkor

k∈G

A alg A* és Ac Opcionális feladatok

p(k) ← n g(k) ← g(n) + c(n, k) 77/364




Probléma: ha k zárt, korábban megkerestük utódjait és rövidebb utat találtunk, ⇒ a g,p függvények nem helyesek a k utódain; ˝ nem optimális. a feszítofa Megoldások: 1 k összes leszármazottját újraértékeljük; 2 a k csúcsot visszatesszük a NYILT halmazba. Hátrány: ˝ Nagyobb futási ido; p nem mindig optimális. 3

78/364

Olyan f választása, mely garantálja, hogy nem lesz ilyen k.

IV




Probléma: ha k zárt, korábban megkerestük utódjait és rövidebb utat találtunk, ⇒ a g,p függvények nem helyesek a k utódain; ˝ nem optimális. a feszítofa Megoldások: 1 k összes leszármazottját újraértékeljük; 2 a k csúcsot visszatesszük a NYILT halmazba. Hátrány: ˝ Nagyobb futási ido; p nem mindig optimális. 3

78/364

Olyan f választása, mely garantálja, hogy nem lesz ilyen k.

IV

Általános algoritmus Mesterséges Intelligencia

G ← {s}, NYILT ← {s}, g(s) ← 0, p(s) ← nil.

4

While nem ures(NYILT ),

Csató Lehel

n ← arg minm∈NYILT f(m) If cél(n) then kilép.


Példa

NYILT ← NYILT \ {n}

Mélységi

For ∀k ∈ Γ (n) If

Szélességi

k 6∈ G or g(k) > g(n) + c(n, k)

Egyenletes

p(k) ← n

˝ Eloretekint o˝

g(k) ← g(n) + c(n, k)

A alg

NYILT ← NYILT ∪ {k}


endfor

G ← G ∪ Γ (n) endwhile 79/364

Az általános algoritmus tulajdonságai Mesterséges Intelligencia

4

Tulajdonságok Az általános gráfkereso˝ algoritmus egy csúcsot véges sokszor terjeszt ki;

Csató Lehel

véges gráfban mindig terminál;

Alapalgoritmus

∗

˝ ∀s→n mindegyik n ∈ NYILT csúcs kiterjesztése elott van m csúcs az optimális úton, mely


Példa Mélységi

1

Szélességi

2

Egyenletes

3

m ∈ NYILT , g(m) = g∗ (m), ˝ o˝ csúcs az úton zárt; minden m-et eloz

˝ Eloretekint o˝

Egy véges gráfban, ha létezik megoldás, akkor az algoritmus egy célcsúcs megtalálásával terminál.

A alg A* és Ac

˝ Csökkeno˝ kiértékelofüggvény használata mellett ˝ optimális és konzisztens a feszítofa.


Bizonyítás

80/364

Nevezetes gráfkereso˝ algoritmusok Mesterséges Intelligencia

Futó: Mesterséges Intelligencia – pp. 83

4 Nem-informált gráfkeresések

Csató Lehel Alapalgoritmus

1

Mélységi keresés

2

Szélességi keresés

3

Egyenletes keresés


Példa Mélységi Szélességi Egyenletes ˝ Eloretekint o˝

Heurisztikus keresések

A alg A* és Ac

1

˝ Eloretekint o˝ keresés


2

A algoritmus

3

A∗ algoritmus

4

Ac algoritmus

81/364

Példa gráfkeresésre Mesterséges Intelligencia

1

4

2

Csató Lehel

3

Alapalgoritmus Példa

6

Mélységi

5

Szélességi Egyenletes ˝ Eloretekint o˝ A alg A* és Ac Opcionális feladatok

82/364

– nyílt csúcsok

l

– zárt csúcsok – p() szülo˝

4


k


1

4

2

Csató Lehel

3


6

Mélységi

5


82/364

– nyílt csúcsok

l


4


k


1

4

2

Csató Lehel

3


6

Mélységi

5


82/364

– nyílt csúcsok

l


4


k


1

4

2

Csató Lehel

3


6

Mélységi

5


82/364

– nyílt csúcsok

l


4


k


1

4

2

Csató Lehel

3


6

Mélységi

5


82/364

– nyílt csúcsok

l


4


k


1

4

2

Csató Lehel

3


7

Mélységi

6 5

Szélességi

8

Egyenletes ˝ Eloretekint o˝ A alg A* és Ac Opcionális feladatok

82/364

– nyílt csúcsok

l


4


k


1

4

2

Csató Lehel

3


7

Mélységi

6 5

Szélességi

8


82/364

– nyílt csúcsok

l


4


k


1

4

2

Csató Lehel

k

– nyílt csúcsok

l

– zárt csúcsok

3

Alapalgoritmus

– p() szülo˝

4


Példa

7

Mélységi

6 5

Szélességi

8

Egyenletes ˝ Eloretekint o˝ A alg A* és Ac

A harmadik iteráció végén tehát a zárt csúcsok halmaza {1, 4, 5};


a nyílt csúcsok halmaza {2, 3, 6, 7, 8}; ˝ a szülo-függvény (z, p(z)) párok: {(2, 1), (3, 1), (4, 1), (5, 4), (6, 4), (7, 5), (8, 5)} 82/364


1

4

2

Csató Lehel

3

Alapalgoritmus

k

– nyílt csúcsok

l


4


Példa

7

Mélységi

6 5

Szélességi

8


A következo˝ csúcs kiválasztása a nyílt halmazból bármilyen kritérium alapján történhet. A kritérium alapja az f(·) függvény. A függvény megválasztásával különbözo˝ keresési stratégiákhoz jutunk. 82/364

Mélységi keresés Mesterséges Intelligencia

Mindig a legmélyebben fekvo˝ nyílt csúcsot választjuk,

4 Csató Lehel

Ha minden él költsége ugyanannyi (pl. c(m, n) = 1), akkor a kiértékelo˝ függvény:


Példa

f(n) = −g(n)

Mélységi

∀n ∈ NYILT,

Szélességi Egyenletes ˝ Eloretekint o˝

Szükséges (? – mikor) a mélységi korlát bevezetése,

A alg A* és Ac

Az algoritmus nem mindig talál megoldást,


Iteratív növelése a mélységi korlátnak – megoldást talál (?optimális?). 83/364


4

Példák

Kiterjesztési sorrend: 1

Ellenpélda: A

Csató Lehel

2

Alapalgoritmus

7

8


Példa

3

6

9

12

10

11

Mélységi

D

B

C

F

G

E


4

5

˝ Eloretekint o˝

Ha megjegyezzük a csúcsokat: A, B, D, F, E, C, G;


Ha nem: A, B, F, E, A, B, . . . http://en.wikipedia.org/wiki/Depth_first_search

84/364


4

Példák

Kiterjesztési sorrend: 1

Ellenpélda: A

Csató Lehel

2

Alapalgoritmus

7

8


Példa

3

6

9

12

10

11

Mélységi

D

B

C

F

G

E


4

5

˝ Eloretekint o˝

Ha megjegyezzük a csúcsokat: A, B, D, F, E, C, G;


Ha nem: A, B, F, E, A, B, . . . http://en.wikipedia.org/wiki/Depth_first_search

84/364

Szélességi keresés Mesterséges Intelligencia

A mélységi keresés ellentettje,

4 Csató Lehel

1 2

Mindig a legmagasabban fekvo˝ nyílt csúcsot választjuk,


Példa Mélységi

5 9


3

6

10

4 7

8

11

12

Ha minden él költsége ugyanannyi (pl. c(m, n) = 1), akkor a kiértékelo˝ függvény:


f(n) = g(n)


∀n ∈ NYILT

Az algoritmus mindig talál megoldást – amennyiben ez létezik. 85/364

Egyenletes keresés Mesterséges Intelligencia

4

Súlyozott változata a szélességi keresésnek,


A kiértékelo˝ függvény (általános c(m, n) esetén):


Példa

f(n) = g(n)

Mélységi

∀n ∈ NYILT

Szélességi Egyenletes ˝ Eloretekint o˝ A alg

Az algoritmus mindig talál megoldást – amennyiben ez létezik,


Dijkstra algoritmusa (1959). 86/364

˝ Eloretekint o˝ keresés Mesterséges Intelligencia

Heurisztikus kereso˝ algoritmus,

4

A kiértékelo˝ függvény csak a heurisztika:

Csató Lehel

f(n) = h(n)

Alapalgoritmus

∀n ∈ NYILT


Példa Mélységi

h(n) – heurisztikus függvény.

Szélességi

pl. f(n) = W(n) – a 8–as kirakójátékban;

Egyenletes

˝ A keresográf kisebb, mint az egyenletes keresés esetében;


˝ A keresográf nem optimális;


˝ ˝ ˝ Erosen függ a választott keresofüggvényt ol.

87/364

„A” algoritmus Mesterséges Intelligencia

4 Csató Lehel

Futó: Mesterséges Intelligencia – pp. 90 ˝ „. . . ötvözi az egyenletes keresés óvatosságát az eloretekint o˝ keresés ˝ célratörésével, egyesítve elonyös tulajdonságaikat.”


Példa

Kiértékelo˝ függvény:

Mélységi Szélességi

f(n) = g(n) + h(n)

Egyenletes ˝ Eloretekint o˝

∀n ∈ NYILT

ahol h(n) > 0.


˝ a cél–csúcsba vivo˝ optimális h(n) „becsüli” az n-bol út költségét.

88/364

„A” algoritmus tulajdonságai Mesterséges Intelligencia

4

Tulajdonságok f∗ (n) = g∗ (n) + h∗ (n) - a startból a célba az n-en keresztül vivo˝ optimális út költségének a becslése.

Csató Lehel Alapalgoritmus Általános algoritmus

Példa

Ha az A algoritmus nem terminál, akkor minden NYILT halmazba került csúcs véges sok lépés után kiterjesztésre kerül.

Mélységi Szélességi Egyenletes ˝ Eloretekint o˝

Az A algoritmus mindig talál megoldást feltéve, hogy létezik megoldás.


89/364

„A*” algoritmus Mesterséges Intelligencia

A algoritmus kiértékelo˝ függvénye, ahol

4

A heurisztikus függvény bármely csúcsban alulról becsüli a a célba vezeto˝ optimális út költségét, azaz


h(n) < h∗ (n)


∀n ∈ G

Példa Mélységi

˝ A fenti kritérium a heurisztika megengedhetosége.

Szélességi

˝ ha megoldás Egy gráfkereso˝ algoritmus megengedheto,

Egyenletes

létezése esetén megtalálja az optimális megoldást.


A∗ tulajdonságai Bármely kiterjesztésre választott csúcsra f(n) ≤ f∗ (n).


Mindig optimális megoldással terminál, feltéve ha az létezik. 90/364

„Ac ” algoritmus Mesterséges Intelligencia

Korlátozás a heurisztikus függvényre: h(n) kielégíti a monoton megszorítás (monotone restriction) feltételét, ha

4 Csató Lehel Alapalgoritmus

h(n) − h(m) ≤ c(n, m)


∀(n, m) ∈ A

Példa Mélységi Szélességi Egyenletes

˝ Egy n csúcs nem kedvezotlen, ha egy utód m csúcs ˝ nagyon kedvezo.


Ac algoritmus: az olyan A algoritmus, ahol h(n) monoton megszorításos és h(t) = 0 minden terminális csúcsra. 91/364

„Ac ” algoritmus tulajdonságai Mesterséges Intelligencia

4 Csató Lehel

Ac tulajdonságai Ha teljesül a monoton megszorítás, akkor egy n ˝ csúcsba vezeto˝ optimális út mentén a g + h növekvo.


Példa Mélységi

Bármely n kiterjesztésre választott csúcshoz az optimális út van megjelölve:

Szélességi Egyenletes ˝ Eloretekint o˝

g(n) = g∗ (n)


Mindig optimális megoldással terminál, feltéve ha az létezik. 92/364

Gráfkereso˝ összefoglaló Mesterséges Intelligencia

a heurisztika nagyon fontos – egy algoritmus alkalmazhatósága a választott heurisztikán áll vagy bukik.


Heurisztikus

Példa

Nem-informált

Mélységi Szélességi Egyenletes ˝ Eloretekint o˝

A

A alg

A∗

Egyenletes

AC

A

Szélességi


Mélységi ˝ Eloretekint o˝ 93/364

Opcionális feladatok Mesterséges Intelligencia

Gyakorló feladatok gráfokkal Az A∗ algoritmust használva jussunk el egy I1 I2 I3 számból egy J1 J2 J3 számba. Keressük meg az {1, . . . , N} halmaz k részbe való felosztását. Fejtsük meg a SEND + MORE = MONEY feladatot.


Példa Mélységi

.

(10 pont)

Írjunk programot, mely megoldja a háromszög-kirakós játékot. .

(12 pont)

Rubik-kígyó megoldása. .

(10 pont)


. 94/364

http://.../feladatok/labor.pdf



5


Csató Lehel


Szemantikus halok


Definiciós hálók


Keretrendszerek

Bizonytalanság kezelése Fuzzy rendszerek Grafikus modellek Tanuló rendszerek Szimulált kifutés, ˝ Genetikus algoritmusok A perceptron modell ˝ Neurális hálók, önszervezodés Gépi tanulás 95/364

Admin ...



5 Csató Lehel Szemantikus halok Definiciós hálók Keretrendszerek

... trívia

Vizsga Szóbeli (60%) + Gyakorlat (40%) Laborgyakorlatok: 1


18%

2

Játékelmélet

10%

3


12%

4



sok%

Blogbányászat Mesterséges Intelligencia

5 Csató Lehel Szemantikus halok Definiciós hálók

Ok-okozati viszonyokat tanul a gép Amerikai kutatók3 blogok elemzésére tanítják rendszerüket, mely történetmesélésre összpontosítva, nyelvi jegyek alapján szelektál közülük. A gyujtött ˝ adatokból a kialakuló trendekre és viselkedésformákra következtet a rendszer. A „tanítás” menete:

Keretrendszerek

1

Blog-bejegyzéseket osztályoztak manuálisan a történet / nem történet osztályokba. . Eredmény: a narratívák azonosítása.

2

A történetek elemei között az oksági kapcsolatok keresése. Pl: késo˝ volt, lefeküdtem. . Eredmény: tények + oksági kapcsolatok.

A rendszer sosem unatkozik Távlati cél egy rendszer kidolgozása, mely napi rendszerességgel gyujt ˝ és rendszerez adatokat.Ez fontos, mert más forrásokból hozzáférhetetlen, muködése ˝ hasonló Google sertésinfluenza-követo˝ programjához. Mire jó a blogbányászat? A blog-ok általában azonnali reagálást jelentenek, ezért garantált a gyujtött ˝ „bányászott” információ ˝ területeit érintik: filmek, könyvek, termékek, nemzetiségi-, vallási aktualitása. Az élet legkülönbözobb ellentétek, kábítószer-kereskedelem... 3 97/364

Andrew Gordon Kreatív Technológiák Intézete Link

Szemantikus hálók Futó: Mesterséges Intelligencia, pp. 186


5 Csató Lehel

Szemantikus háló: az emberi információtárolás és keresés modellezése (Quillian & Collins);

Szemantikus halok Definiciós hálók

gyakori név az asszociatív háló.

Keretrendszerek

kognitív pszichológiai kísérletek az „alapjai”; Tulajdonságok: objektumokhoz tulajdonságokat rendelünk; hierarchia az objektumok szintjén ⇒

absztrakció

˝ szinten asszociálódnak. a tulajdonságok a legfelsobb

98/364

Quillian és Collins kísérlete: Mesterséges Intelligencia

5 Csató Lehel Szemantikus halok

˝ Kísérlet: kérdések a madarakról és a reakcióidok mérése. Kérdések:

Definiciós hálók Keretrendszerek

1

Tud-e a kanári énekelni?

1.3mp

2

Tud-e a kanári repülni?

1.4mp

3

˝ Van-e a kanárinak bore?

1.5mp

Hosszabb asszociációs lánc az utolsó kérdésnél. ˝ és az Magyarázat: egy szemantikus hálóban a bore énekel tulajdonságok nem egyforma távolságra vannak a kanári-tól. 99/364

Szemantikus hálók Futó: Mesterséges Intelligencia, pp. 186


5 Csató Lehel

Szemantikus háló: az emberi információtárolás és keresés modellezése (Quillian & Collins);


gyakori név az asszociatív háló.

Keretrendszerek

kognitív pszichológiai kísérletek az „alapjai”; Tulajdonságok: objektumokhoz tulajdonságokat rendelünk; hierarchia az objektumok szintjén ⇒

absztrakció

˝ szinten asszociálódnak. a tulajdonságok a legfelsobb

100/364

Kanári szemantikus háló lélegezni


5 Csató Lehel Szemantikus halok

tud

Állat

bõre van

Szemantikus háló:

Definiciós hálók

repülni

Élek: a csúcsok közötti kapcsolat neve. 101/364

tud

Madár

Csúcsok: objektumok, objektumosztályok és tulajdonságok értékei;

Keretrendszerek

tud mozogni

egy

Irányított gráf, ahol

van

egy

Kanári

szárnya

van tollazata

egy

Strucc

tud

tud

énekelni

repülni

nem_tud

repülni

méret

nagy

Wordnet Mesterséges Intelligencia


http://wordnetweb.princeton.edu 102/364

Nagy szemantikus háló

Feladatmegoldás szemantikus hálókkal Mesterséges Intelligencia

5 Csató Lehel

Feladat: lekérdezés megválaszolása adott tárgyköri tudással.

Szemantikus halok Definiciós hálók Keretrendszerek

Tárgyköri tudás: egy taxonomikus hierarchia – azaz egymásba ágyazott objektumok halmaza – számítógépes reprezentációja. Adatbázis Lekérdezés: egy célháló illesztése a szemantikus hálóba. Illesztés

103/364

Milyen feladatokra megfelelo˝ Mesterséges Intelligencia

5

Klasszikus logika nyelvén:

Állat

Csató Lehel Szemantikus halok

∀x x ∈ MADARAK ⇒ x ∈ REPUL egy


Kivételek kezelése (strucc) nehézkes.

Madár

tud

repülni

Melyik alkalmazás modellezheto˝ szemantikus hálóval: játékok, vízelemzo˝ rendszerek, rendszerkonfigurálás ?. 104/364

osztályozás, nyelvelemzés

Összefoglaló – szemantikus hálók Mesterséges Intelligencia

5

Fogalmak és kapcsolataik modellezése.


Asszociatív memóriák.


Információk egyszeru˝ reprezentációja – !smiley! programozási paradigma jött létre. Ezt használjuk információ reprezentálására?

Történelem

105/364

Keretrendszerek

Definciós hálók

Kitéro˝ http://www.jfsowa.com/pubs/semnet.htm



Porfirius (i.sz. 300 körül) - magyarázata Arisztotelész „Kategóriá”jához. ˝ Típus és különbözoség szerint rajzolt egy definiciós hálót, ahol alá- és fölérendelt kategóriákat különböztetett meg. 106/364

Keretrendszerek Mesterséges Intelligencia

5

Keretalapú Ismeretreprezentáció

Futó. pp.198

Csató Lehel

1975 Minsky - látás egy pszichológiai modelljének a leírása.


A tanulmányozott világ fizikai vagy fogalmi entitásainak egy strukturált szimbolikus modellje.

Keretrendszerek

hasonlít a szemantikus hálókhoz – annak továbbfejlesztése. Új elem a procedurális reprezentáció. Majdnem OOP - a különbség, hogy az OOP keretrendszer célja a kódolás és nem a tudásreprezentáció. Level 5 Object 107/364

FRAME-es reprezentáció Mesterséges Intelligencia


frame Személy instance-of: Class azonosító: személyi vezetéknév: keresztnév: end ˝ frame Foiskolás is-a: Személy közös-cím: ’[email protected]’ levél-cím: end frame Kosarazó is-a: Személy havi-juttatás: end frame Kosár-center is-a: Kosárlabdázó end

108/364

frame Kosárcsapat instance-of: Class ˝ Személy edzo: játékosok: collection-of Személy end ˝ frame Foiskolás-kosárcsapat instance-of: Kosárcsapat ˝ Oktató edzo: ˝ játékosok: collection-of Foiskolás frame Szöcskék ˝ instance-of: Foiskolás-kosárcsapat játékosok: Péter, Tamás, ... end frame Péter ˝ instance-of: Foiskolás instane-of: Kosár-center levél-cím: ’[email protected]’ magasság: 193 havi-juttatás: 10000 end

Démonok Mesterséges Intelligencia

5

Démonok Eljárások, melyeket osztályokhoz illetve azok attribútumaihoz lehet hozzárendelni.


„paraméterezés”: mikor lépjenek muködésbe ˝ (milyen esemény bekövetkeztekor).


when-needed-demon when-changed-demon when-deleted-demon when-added-demon

Frame-rendszer muködése: ˝ rendszer összes démonának együttes muködése ˝ ˝ (pl. útkeresztezodés muködtetése). ˝ 109/364

FRAME-ek tulajdonságai Mesterséges Intelligencia

Egy keret vagy osztály vagy példány. Különbség az is-a illetve az instance-of között.

5 Csató Lehel

˝ Többszörös öröklodés - amikor egy osztály lehet több osztálynak az utóda.


Példányok a hierarchia alján - nem lehet tovább példányosítani.

Keretrendszerek

Mi történik egy hiányos osztályleírás esetén? A rendszer a megszorítások alapján kiegészíti vagy nem ˝ a hiányzó információkat (pl. Péter nem foiskolás). 110/364



6


Csató Lehel


Jatekelmelet


Kétszemélyes játékok NIM


Tic–Tac–Toe Nyero Strat.


Strat. keresés Minimax alg. Negamax

Fuzzy rendszerek

Alfabéta Játékprogramok

Grafikus modellek

˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra

Tanuló rendszerek

Példa


Összefoglaló

A perceptron modell ˝ Neurális hálók, önszervezodés Gépi tanulás 111/364

Admin ...



6 Csató Lehel Jatekelmelet

... trívia


Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat.

Laborgyakorlatok:

Strat. keresés Minimax alg.

1


18%

2

Játékelmélet

10%

3


12%

4


Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló


sok%

Játékelmélet Mesterséges Intelligencia

6

Futó, pp. 215

... problems arising when we try to plan ahead in presence of hostile agents ... Russell&Norvig, pp. 122

Csató Lehel Jatekelmelet

Babbage (1846) - gépet tervez, mely Tic-tac-toe-t játszik,


Leonardo Torres y Quevedo (1890) - sakk végjáték,


von Neumann & Morgenstern (1944) - Theory of games and Economic Behaviour Shannon és Turing (1950) - sakkprogram, mert

Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra

1

Példa Összefoglaló

2 3

„intelligencia” szükséges a játékhoz, egyszeru˝ szabályok, teljes informáltság,

McCarthy (1956) - vágások. 113/364

Játékok és keresés Mesterséges Intelligencia

„Ismeretlen” ellenfél:

6

Nem ismerjük a lépéseit,

Csató Lehel

Feltételezzük, hogy nyerni akar.

Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax

Válasz: egy stratégia, mely az ellenfél minden lehetséges lépését figyelembe veszi.

Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

˝ Sakk-program esetében: nincs lehetoség az összes ˝ lehetoség vizsgálatára ⇒ szükségesek a közelítések.

Mit közelítünk? 114/364

Játékok típusai Mesterséges Intelligencia

6 Csató Lehel Jatekelmelet Kétszemélyes játékok NIM

Teljes információs Részleges információs

determinisztikus sakk, go

valószínuségi ˝ Dáma, Monopoly

battleship

bridge, póker

Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

?? Kupacos játék - Maya.

115/364

Kétszemélyes játékok Mesterséges Intelligencia

Kétszemélyes teljes információs játékok:

6

két játékos lép felváltva, adott szabályok szerint;

Csató Lehel

a játékosok minden információval rendelkeznek;

Jatekelmelet

minden állapotban véges számú lépés létezik;

Kétszemélyes játékok NIM

véges a játszma ideje;

Tic–Tac–Toe Nyero Strat.

az egyik játékos mindig nyer (esetenként lehetséges döntetlen...)

Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

Ezzel a játékosztállyal foglalkozunk.

116/364

I

Kétszemélyes játékok Mesterséges Intelligencia

6

Formális definíció:

Csató Lehel

Két játékos, legyen MAX illetve MIN;

Jatekelmelet Kétszemélyes játékok NIM

MAX kezd;

Tic–Tac–Toe Nyero Strat. Strat. keresés

˝ ismert kezdoállapot;

Minimax alg. Negamax Alfabéta

muveletek, ˝ melyek leírják a lehetséges lépéseket;

Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra

játék végének a tesztje;


nyereség-függvény; Stratégia: szabály az egyik – MAX – játékos optimális lépéseinek megadására. 117/364

II

Nim játék Mesterséges Intelligencia

Nim = „nip” + „muster”

6 Csató Lehel

Játék: gyufaszálak több sorban;

Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax

adott gyufaszál minden sorban;

[n1 , . . . , nm ]

lépés = egy sorból valahány gyufaszál elvétele;

i 0 ≤ ni0 < ni

Alfabéta

játék vége: elfogynak a gyufaszálak;

Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok

m

∀i; ni = 0

veszít az a játékos, mely már nem tud gyufaszálat felvenni.

Neumann-tétel kevert stratégiákra Példa Összefoglaló

˝ nem Változatok: vesztes az utolsó gyufaszálat felvevo; ˝ lehet tetszoleges számú elemet felvenni, etc. 118/364

Nim játék Mesterséges Intelligencia


A játék állásai: Nyero˝ – ha a játékos tud úgy lépni, ˝ függetlenül hogy az ellenfél lépéseitol nyer; Veszto˝ – ha nincs nyero˝ lépés.

Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés

Nyero˝ stratégia:

Minimax alg. Negamax

0 0 1 1


0 1 0 1

1 0 0 1

1 = 3 1 = 5 0 = 8 0 (XOR)

˝ melyekre az Állítás: azon állások vesztok, XOR csupa nullát eredményez. 119/364

Nim játék tulajdonságai Mesterséges Intelligencia


˝ melyekre az XOR csupa Állítás: azon állások vesztok, nullát eredményez. 1. Lemma Ha egy állásban az XOR nem csupa nullát eredményez, akkor van lépés, mely az XOR szerint nullát eredményez.

Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok

2. Lemma Ha egy állapotban az XOR csupa nulla, akkor nincs lépés, mely eredményeként az XOR nulla lesz.


Nyero˝ stratégia Ha XOR nem nulla, akkor le tudjuk nullázni és az ellenfél nem tud olyat lépni, hogy számunkra megint nulla legyen. =⇒ nyero˝ stratégia. 120/364















Nim játék példa Mesterséges Intelligencia

Kezdeti állapot:

6 0 0 1 1

Csató Lehel Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe

0 1 0 1

1 0 0 1

1 = 3 1 = 5 0 = 8 0 (XOR)

Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok

Válasszuk az utolsó (8 elemes) sort. Ahhoz, hogy mindenhol 0 legyen

˝ o˝ játékok Ismétlod Null-összegu˝ játékok

0 1 1 0 = 6


kell maradjon, tehát 2 elemet kell elvenni. Az új pozíció vesztes. 121/364

Nim játék gráfja Mesterséges Intelligencia

1, 2 A lép

6 Csató Lehel

játék gráfja véges mélységu; ˝

Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat.

0, 2 B lép

1, 1 B lép

1, 0 B lép

0, 1 A lép

0, 0 A lép

1, 0 A lép


Nyero˝ stratégia:

Alfabéta

mindig van legalább egy olyan ˝ gyozni ˝ lépés, melybol tud;

Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra

függetlenül attól, hogy az ellenfél mit lép;


0, 0 B lép 122/364

˝ Tic-Tac-Toe – amoba MAX(X) Mesterséges Intelligencia

6 Csató Lehel

MIN(O)

Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés

MAX(X)

Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra

MIN(O)


Vég Jutalom: 123/364

A játék gráfja −1

0

1

Nyero˝ stratégia létezése Mesterséges Intelligencia

6 Csató Lehel Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax

Tétel Egy teljes információjú kétszemélyes játék esetén mindig létezik egy játékos számára nyero˝ stratégia (ha nincs döntetlen).

.

MAX


Bizonyítás: ˝ Az élek címkézése lentrol felfelé. Ha B lép, ∃ ág, mely B-vel van címkézve, akkor B, ellenkezo˝ esetben A. 124/364

.

B

.

B

A

.

B

A

MIN

A

MAX

Majdnem NIM Mesterséges Intelligencia

6 Csató Lehel Jatekelmelet Kétszemélyes játékok

Példa

Kuglizás – ahol az összes bábú egy sorban van, tehát csak egy vagy két – egymásmelletti – bábút tudunk leütni. ˝ Vesztes, akinek eloször nem marad bábúja. Feladat:

NIM Tic–Tac–Toe

Határozzuk meg a játék állapotterét k = 3 egymásmelletti bábúra;

Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta

Határozzuk meg, hogy az kezdo˝ játékos nyer vagy veszít.

Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa

Számítsuk ki, hogy a kezdo˝ játékos nyertes-e k = 5 egymás-melletti bábú esetén.

Összefoglaló

Írjunk programot, mely meghatározza, hogy a kezdo˝ ˝ játékos nyer-e tetszoleges konfigurációnál. 125/364

Stratégiák keresése Mesterséges Intelligencia

Stratégia nem keresheto˝ mert a teljes gráf nem fér el a memóriában;


túl sok állapot.

Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés

Sakk:


≈ 45 lépés tehát 90 mélységu˝ fa, ˝ ≈ 35 lehetoség; 3590 = 10139 levél. 1080 összes elektron


Deep Blue – 32CPU × 8 dedikált sakk-processzor (13-30 mélységig; 30 milliárd lépés/perc) 126/364

Minimax algoritmus Mesterséges Intelligencia

Minimax algoritmus:

6 Csató Lehel

bonyolultabb játékok esetén használják;

Jatekelmelet Kétszemélyes játékok NIM

nem építheto˝ meg a teljes játékfa;

Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax

nem talál biztosan nyero˝ stratégiát;


˝ vagy „elég jó” lépés; „eros”


˝ Közelítéseket adunk a nyero/vesztes értékelés helyett. 127/364

Minimax algoritmus játékfákon Mesterséges Intelligencia

Játékfa építése adott mélységig;

6

3

MAX

Levelek címkézése: kiértékelo˝ függvény

Csató Lehel Jatekelmelet Kétszemélyes játékok

Értékek visszaterjesztése lásd Nyero˝ stratégia ;

NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg.

3

2

MIN

2

Negamax

A gyökér-címke értéku˝ lépés megtétele;


3

128/364

12

8

2

4

6

14

5

2

MAX



6

3

MAX





3

2

MIN

2

Negamax



3

128/364

12

8

2

4

6

14

5

2

MAX



6

3

MAX





3

2

MIN

2

Negamax



3

128/364

12

8

2

4

6

14

5

2

MAX



6

3

MAX





3

2

MIN

2

Negamax



3

128/364

12

8

2

4

6

14

5

2

MAX

Negamax algoritmus Mesterséges Intelligencia

6

A minimax algoritmusnál a különbözo˝ játékosok lépéseinél minimumot vagy maximumot kerestünk;


A negamax algoritmus egyesíti a kétfajta optimális lépést:

NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta

minden lépésben maximumot számol,


˝ o˝ szint negált értékei szerint. ellenben az eloz


a javasolt lépés a csúcs negált értéku˝ utódjába történo˝ lépés;

129/364

Negamax algoritmus muködése ˝ Mesterséges Intelligencia

6

3

-MAX

Csató Lehel Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax

-3

Alfabéta

-2

-MAX

-2

Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

3 130/364

12

8

2

4

6

14

5

2

-MAX


6

3

-MAX


-3

Alfabéta

-2

-MAX

-2


3 130/364

12

8

2

4

6

14

5

2

-MAX


6

3

-MAX


-3

Alfabéta

-2

-MAX

-2


3 130/364

12

8

2

4

6

14

5

2

-MAX


6

3

-MAX


-3

Alfabéta

-2

-MAX

-2


3 130/364

12

8

2

4

6

14

5

2

-MAX

Minimax/Negamax tulajdonságok Mesterséges Intelligencia

Tulajdonságok:

6

Teljesség – megtalálja az optimális lépést, ha ilyen létezik? Ha a játékfa véges. igen


Optimalitás – a legjobb lépést találja meg? Ha az ellenfél is racionális.

Nyero Strat. Strat. keresés Minimax alg.

igen

Negamax Alfabéta

Bonyolultság: O(bm )

Játékprogramok

kimeno˝ élek – b kiértékelés mélysége – m


Memóriaigény: O(bm)


Sakk-program: b ≈ 35, 90

35

m ≈ 100, ⇒ 3590 = 10139 levél v.ö: 1080 összes elektron

Hatékonyság növelése: VÁGÁSOK 131/364


Tulajdonságok:

6





igen

Negamax Alfabéta


Játékprogramok






35




Tulajdonságok:

6





igen

Negamax Alfabéta


Játékprogramok






35




Tulajdonságok:

6





igen

Negamax Alfabéta


Játékprogramok






35




Tulajdonságok:

6





igen

Negamax Alfabéta


Játékprogramok






35




Tulajdonságok:

6





igen

Negamax Alfabéta


Játékprogramok






35



Alfa-béta vágás Mesterséges Intelligencia

I

Minimax/negamax algoritmus költséges mert nagyon sok csúcsot kell generálni; azonban

6

Tudjuk, hogy az értékelés a minimax szabály szerint történik;


Az alfa-béta vágások módszere figyelembe veszi a már kiszámított csúcsok értékét (McCarthy 1956 – sakk)

NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax

és csak olyan csúcsokat nem értékel ki, ahova racionális játék során eljutunk.

Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa

Kiértékelés során bevezetett változók:

α – MAX szint utódjainak maximuma;

Összefoglaló

csak növekedhet.

β – MIN szint utódjainak minimuma; csak csökkenhet. 132/364

Alfa-béta vágás Mesterséges Intelligencia

6 Csató Lehel

II

Vágás: muvelet, ˝ melynek eredményeként nem értékeljük ki egy csúcshoz tartozó többi utódcsúcsot. Vágási kritériumok:

Jatekelmelet

˝ MIN csúcs alatt vágunk, ha az egyik oséhez rendelt

Kétszemélyes játékok

α érték nagyobb, mint a csúcs β értéke.

NIM Tic–Tac–Toe Nyero Strat.

alfa vágás

Strat. keresés Minimax alg.

˝ MAX csúcs alatt vágunk, ha az egyik oséhez rendelt

Negamax Alfabéta

β érték kisebb, mint a csúcs α értéke.


béta vágás


Egy kiértékelést abba lehet hagyni, ha:

α≥β 133/364

Alfa-béta vágás – példa Mesterséges Intelligencia

≥3

MAX

6 Csató Lehel Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés

3


2

2<3

X

X

MIN


3

134/364

12

8

2

14

5

2

MAX


≥3

MAX


3


2

2<3

X

X

MIN


3

134/364

12

8

2

14

5

2

MAX


≥3

MAX


3


2

2<3

X

X

MIN


3

134/364

12

8

2

14

5

2

MAX


≥3

MAX


3


2

2<3

X

X

MIN

< 14


3

134/364

12

8

2

14

5

2

MAX


≥3

MAX

6 Csató Lehel Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat.

<5

Strat. keresés

3


2

2<3

X

X

MIN


3

134/364

12

8

2

14

5

2

MAX


≥3

MAX


3


2

2<3

X

X

MIN

2


3

134/364

12

8

2

14

5

2

MAX


3

≥3

MAX

6 Csató Lehel Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat.

<5 < 14

Strat. keresés

3


2

2<3

X

X

2

MIN


3

134/364

12

8

2

14

5

2

MAX

Alfa-béta algoritmus tulajdonságai Mesterséges Intelligencia

6 Csató Lehel

˝ a vágások nem módosítják a megoldások minoségét;

Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés

hatékony vágások (elso˝ eset) megvalósítása a ˝ csúcsok rendezésével: ido-komplexitás: O(bm/2 )

Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

Fontos a tudás – hol lehet „jó csúcsokat” találni – kódolása.

135/364

Létezo˝ játékprogramok: Dáma – Chinook program 40 éves nyerési sorozatot szakított meg ...


6

Sakk – Deep Blue 1997-ben megverte Kasparov-ot.

Csató Lehel

Reversi – nem játszanak: gép ... mindig nyer.

Jatekelmelet

Go – nem játszanak: gép ... mindig veszít.

Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

136/364

Játékelmélet Mesterséges Intelligencia

Neumann János

˝ Jellemzok:

6

két játékos van: a sor illetve az oszlop játékos.

Csató Lehel

a sor-játékos a számára elérheto˝ m stratégia közül pontosan egyet választ.

Jatekelmelet Kétszemélyes játékok

az oszlop-játékos a számára elérheto˝ n stratégia közül pontosan egyet választ.


A választások egymástól függetlenek.

Negamax Alfabéta

Ha a sor játékos az i opciót, az oszlop játékos a j opciót választotta, a sor játékos nyeresége aij .


˝ Stratégia: szabályrendszer, mely eloírja, hogy egy játékos mit kell lépjen. Neumann János tétele - kevert stratégiákra null-összegu˝ játékokon. 137/364

Stratégia játékokban Mesterséges Intelligencia

6

Példa

Két játékos, mindegyiknek van valahány stratégiája, melyek közül választhat (A → 3, illetve B → 4).


Nyereségmátrix az A számára; veszteség B-nek.

NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax

A.1 A.2 A.3


B.1 −1 5 8

B.2 3 4 −2

B.3 2 −2 6

B.4 9 6 −2


Ha A nem tudja, hogy B mit fog lépni, melyik a legjobb lépés? ?

138/364

Minimax tulajdonság Mesterséges Intelligencia

Nyereségmátrix: (a sor játékos számára)

6 −1 5 8

Csató Lehel Jatekelmelet Kétszemélyes játékok NIM

3 4 −2

2 −2 6

9 6 −2

Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta

Azon stratégiát válassza, mely a legkisebb nyereségek maximumát adja.


Minimax játékos: max min Mij ≤ min max Mij i

Összefoglaló

j

j

azaz: az A legalább min max-ot nyer.

139/364

i

Minimax tulajdonság Mesterséges Intelligencia

Nyereségmátrix: (a sor játékos számára)

6 −1 5 8

Csató Lehel Jatekelmelet Kétszemélyes játékok NIM

3 4 −2

2 −2 6

9 6 −2

−1 −2 −2

Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta

Azon stratégiát válassza, mely a legkisebb nyereségek maximumát adja.


Minimax játékos: max min Mij ≤ min max Mij i

Összefoglaló

j

j

i

azaz: az A legalább min max-ot nyer. A sor-játékos az elso˝ sort választja −1 nyereséggel 139/364

Kevert stratégia Mesterséges Intelligencia

Nyereségmátrix:

6

−1 5 8

Csató Lehel Jatekelmelet

3 4 −2

2 −2 6

9 6 −2

−1 −2 −2

Kétszemélyes játékok NIM Tic–Tac–Toe

De: vannak a nyereségmátrixnak sokkal nagyobb elemei is, tehát kell legyen jobb választás; Kevert stratégiával játszunk: a sorjátékos válassza:

Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok

x1 valószínuséggel ˝ az elso˝ sort; x2 valószínuséggel ˝ a második sort; x3 valószínuséggel ˝ a harmadik sort (x3 = 1 − x1 − x2 );

˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

Az oszlop játékos ugyanígy választhat. Feltételezzük, hogy sokszor játsszuk ugyanazon mátrix szerint. 140/364

Kevert stratégia létezési tétele Mesterséges Intelligencia


Neumann-tétel Minden nulla-összegu˝ játék esetén létezik egy olyan keveréke a stratégiáknak, mely minimax tulajdonsággal rendelkezik.

NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod

Bizonyítás: y Átlagnyereség: x T My

x = [x1 , . . . , xn ] ∈ Π n

y ∈ Πm

Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa

y= max min x T My

Összefoglaló

x∈Πn m∈Πm

V=V | {z }

y = min max x T My m∈Πm x∈Πn

teljes biz. Finta - operációs kutatások

141/364

Kevert stratégia létezési tétele Mesterséges Intelligencia


Neumann-tétel Minden nulla-összegu˝ játék esetén létezik egy olyan keveréke a stratégiáknak, mely minimax tulajdonsággal rendelkezik.

NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod

Bizonyítás: y Átlagnyereség: x T My

x = [x1 , . . . , xn ] ∈ Π n

y ∈ Πm

Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa

y= max min x T My

Összefoglaló

x∈Πn m∈Πm

V=V | {z }

y = min max x T My m∈Πm x∈Πn

teljes biz. Finta - operációs kutatások

141/364

Minimax tétel Mesterséges Intelligencia

6

Példa:

0 2

T 1 x y Arányokkal: M 1−x 1−y 0

XMAPLE KÓD

Csató Lehel Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat. Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

˝ A nyeresége maximális, ha 2/3 valószínuséggel ˝ az elso, 1/3-dal a második stratégia szerint játszik. 142/364

Olló – papír – ko˝ Mesterséges Intelligencia

6 Csató Lehel

Szabályok: két játékos játszik egyszerre mutatnak egy ... papírt követ ollót

Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe

papír: becsomagolja a követ;


0 1 −1 −1 0 1 1 −1 0

˝ kicsorbítja az ollót; ko:

Negamax Alfabéta

olló: elvágja a papírt


Teljes szimmetria ⇒ nincs optimális stratégia. „Optimális” kevert stratégia: [1/3, 1/3, 1/3]. 143/364

Egy paradoxon

–

Stratégiák

Székely J.G.: Paradoxonok a véletlen matematikájában. Mesterséges Intelligencia

Ketten játszanak: Q és R. Egy vagy két ujjat mutatnak fel;

6

Páros ujj-szám esetén Q fizet R-nek, ellenkezo˝ esetben fordítva;


annyit nyernek/veszítenek, ahány ujjat felmutattak.

NIM Tic–Tac–Toe Nyero Strat. Strat. keresés

Ismételt játékok esetén mi a nyero˝ stratégia?

Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa

Nyereség–mátrix: Q.1 Q.2 R.1 2 −3 R.2 −3 4

Összefoglaló

T r M q = 2r1 q1 − 3r1 q2 − 3r2 q1 + 4r2 q2

Mindegyik játékos úgy játszik, hogy az eredmény ne függjön a másik játékostól, valamint tudva, hogy p2 = 1 − p1 és q2 = 1 − q1 , a játék értéke: V = (12r1 − 7)q1 + (4 − 7r1 ) R választása: 12r1 − 7 = 0. A megoldás: r1 = 7/12, r2 = 5/12, q1 = 7/12, q2 = 5/12 Átlagnyereség: −1/12

144/364

Tizenegyes-rúgások

Példa


Tizenegyes–rúgásn: a játékos rúg, a kapus véd.

6

˝ elmozdul. A kapus a lövés elott

Csató Lehel

˝ dönt. A játékos szintén a lövés elott Jatekelmelet

B K J

B 5 8 9

K 8 4 8

J 9 8 5


Milyen stratégiát kövessenek? ˝ Balra, Középre, vagy Jobbra lehet loni, ˝ a kapus is erre A buntet ˝ ot

Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod

˝ vetodhet.

Kevert stratégiákat keresünk. Játékos x = [x1 , x2 , 1 − x1 − x2 ] és kapus y = [y1 , y2 , 1 − y1 − y2 ].

Null-összegu˝ játékok

xT M y =

Neumann-tétel kevert stratégiákra Példa

−8y1 x1 − 4y1 x2 + 4y1 − 7y2 x2 + 3y2 + 4x1 − 4x1 y2 + 3x2 + 5 = −x1 (8y1 + 4y2 − 4) − x2 (4y1 + 7y2 − 3) + 4y1 + 3y2 + 5

Összefoglaló

Innen: y1 = 2/5 ; y2 = 1/5 ⇒ y3 = 2/5. (szimmetria okán a kapus ugyanígy kell eljárjon.) 145/364

Tizenegyes-rúgások

Példa


Tizenegyes–rúgásn: a játékos rúg, a kapus véd.

6

˝ elmozdul. A kapus a lövés elott

Csató Lehel

˝ dönt. A játékos szintén a lövés elott Jatekelmelet

B K J

B 5 8 9

K 8 4 8

J 9 8 5


Milyen stratégiát kövessenek? ˝ Balra, Középre, vagy Jobbra lehet loni, ˝ a kapus is erre A buntet ˝ ot

Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod

˝ vetodhet.

Kevert stratégiákat keresünk. Játékos x = [x1 , x2 , 1 − x1 − x2 ] és kapus y = [y1 , y2 , 1 − y1 − y2 ].

Null-összegu˝ játékok

xT M y =

Neumann-tétel kevert stratégiákra Példa

−8y1 x1 − 4y1 x2 + 4y1 − 7y2 x2 + 3y2 + 4x1 − 4x1 y2 + 3x2 + 5 = −x1 (8y1 + 4y2 − 4) − x2 (4y1 + 7y2 − 3) + 4y1 + 3y2 + 5

Összefoglaló

Innen: y1 = 2/5 ; y2 = 1/5 ⇒ y3 = 2/5. (szimmetria okán a kapus ugyanígy kell eljárjon.) 145/364

Játékok – összefoglaló Mesterséges Intelligencia

Játékok – fontos szemlélteto˝ eszközök:

6

Nincs tökéletes megoldás, tehát közelítenünk kell;

Csató Lehel Jatekelmelet Kétszemélyes játékok NIM Tic–Tac–Toe Nyero Strat.

Formalizálás: „jó ötlet azon gondolkodni, hogy min kell gondolkodni”;

Strat. keresés Minimax alg. Negamax Alfabéta Játékprogramok ˝ o˝ játékok Ismétlod Null-összegu˝ játékok Neumann-tétel kevert stratégiákra Példa Összefoglaló

Játékok: mint a Formula 1 az autók számára.

146/364



7


Csató Lehel


Numerikus modellek


Bayes modell Bayes hálók


Esettanulmány


Admin ...

... trívia



7 Csató Lehel Numerikus modellek


Bayes modell Bayes hálók Esettanulmány

Laborgyakorlatok: 1


18%

2

Játékelmélet

10%

3


12%

4



sok%

Bizonytalanság Mesterséges Intelligencia

7

Russell & Norvig, 1995, 415. o. „In which we see what an agent should do when not all is crystal clear.” Futó et.al. 321–372

Csató Lehel Numerikus modellek

Ezidáig: következtetések olyan esetekben, ahol tudtuk egy esemény – tény – bekövetkezését.

Bayes modell Bayes hálók

ismertük az események közötti kapcsolatrendszert: ok–okozat

Esettanulmány

Problémamegoldás során a tudásunk: hiányos

– nem tudunk/akarunk válaszolni;

nem megbízható – tudjuk, hogy max. 70%... nem precíz – nincs megfelelo˝ formalizmus a leíráshoz; ellentmondásos – több forrás ⇒ konfliktus; 149/364

Bizonytalanság típusai Mesterséges Intelligencia

Hiányzó adat

Rosszul kitöltött kér˝ doív Bizonytalan A betegség csak valóadat színusíthet ˝ o˝ Bizonytalan fo- Pl. „gyorsan hajtott” galmak Ellentmondások Összegzésnél egymásnak ellentmondó adatok

7 Csató Lehel Numerikus modellek Bayes modell Bayes hálók Esettanulmány

150/364

Bizonytalanság kezelése Mesterséges Intelligencia

7

Numerikus modellek

Csató Lehel

Bayes-modell,

Numerikus modellek

Bayes-hálók,


Dempster–Schafer: megbízhatóságelmélet, Fuzzy modell

151/364

Szimbolikus modellek nem-monoton rendszerek

Cardano és Galilei Mesterséges Intelligencia

7 Csató Lehel Numerikus modellek Bayes modell Bayes hálók Esettanulmány

Gerolamo Cardano (1501–1576): Liber de ludo aleae - 1663 „Olasz matematikus, természettudós, csillagász és hazárdjátékos.” ˝ Eloször írja le a tífuszt. Legismertebbek az algebrában elért eredményei: megoldotta a harmad- és negyedfokú egyenleteket – Ars Magna – és a megoldás során felismerte az imaginárius rész szükségességét. Termodinamikai megfontolások alapján tagadta az örökmozgók létezését. Mindig pénzszukében ˝ volt – ?⇒? – sakkozott és kockázott. Az ˝ játékokról írt könyve eloször foglalkozik a valószínuség ˝ fogalmával.

Cardano wiki

Galileo Galilei (1564–1642) Olasz természettudós, matematikus, csillagász és filozófus, a ˝ tudományos forradalom úttöroje. ˝ S. Hawking: „Galileo a modern tudományok úttöroje.” ˝ Javított a teleszkópok képességein, tökéletesítette a körzot, ˝ bevezette a kinematikát, az asztronómiát, eloször írta le a Vénusz fázisait. Kijelentette, hogy a természet törvényei matematikai jelleguek, ˝ valamint azt, hogy a Föld forog a Nap körül, (majdnem megégett).

152/364

Galileo wiki

Bayes modell Mesterséges Intelligencia

I

A legrégebbi modell, legjobban definiált technika (kockajáték);

7 Csató Lehel

Alapja a valószínuségszámítás; ˝

Numerikus modellek

Elso˝ modellt Cardano4 alkotta; illetve Galilei 1660 körül, majd Borel és Kolmogorov a XX. században;


Valószínuségszámítás: ˝ véletlen kísérletek; Kísérletek eredményei: elemi események; Eseménytér: összes esemény Ω teljes esemény üres esemény ellentett esemény egymást kizáró események 4 153/364

T = Ω, T = ∅, A = Ω \ A, ha A ∩ B = ∅,

Gerolamo Cardano (1501–1576): De Ludo Aleae (1663)

rev. Thomas Bayes Mesterséges Intelligencia

7 Csató Lehel Numerikus modellek

Thomas Bayes (1702–1761): angol matematikus és ˝ elnevezett tétel egy specifikus alakját lelkész, a nevérol alkotta meg.


Bayes wiki 154/364


7

II

Valószínuség: ˝ P : 2Ω −→ [0, 1] függvény, melyre

Csató Lehel

P(T ) = 1

T teljes esemény;

P(F) = 0

F üres esemény;

Numerikus modellek Bayes modell Bayes hálók Esettanulmány

P(A ∪ B) = P(A) + P(B) ha A és B egymást kizáró események. P(A) – az A esemény bekövetkeztének a valószínusége ˝ ha semmi információ nem áll rendelkezésünkre más ˝ események bekövetkeztérol. Tulajdonság: P(A) + P(A) = 1. 155/364


7

III

Teljes eseményrendszer azon {A1 , . . . , AN }, N > 0 halmazok, melyekre

Csató Lehel

A1 ∪ A2 ∪ · · · ∪ AN = Ω és Ai ∩ Aj = ∅

Numerikus modellek

∀i 6= j


Tétel: minden {A1 , . . . , AN } teljes eseményrendszer esetén P(A1 )+P(A2 )+· · ·+P(AN ) = P(A1 ∪A2 ∪· · ·∪AN ) = P(Ω) = 1 Jelölés:

def A ∩ B def = AB és P(A ∩ B) = P(AB).

Feltételes valószínuség: ˝ B esemény hatása az A-ra: 156/364

P(A|B)


7

Bayes szabály: feltételes valószínuség ˝ szabálya

Csató Lehel

azaz P(A|B) =

Numerikus modellek Bayes modell Bayes hálók

IV

P(AB) P(B)

ha P(B) 6= 0

Tipikus felírás:

Esettanulmány

P(A|B) =

P(B|A)P(A) P(B|A)P(A) + P(B|A)P(A)

ha P(B) 6= 0

Általános Bayes-szabály Egy {A1 , . . . , AN } teljes eseményrendszer esetén P(B|Ai )P(Ai ) P(Ai |B) = P j P(B|Aj )P(Aj ) 157/364

ha P(B) 6= 0


P(B|Ai )P(Ai ) P(Ai |B) = P j P(B|Aj )P(Aj )

7 Csató Lehel Numerikus modellek Bayes modell Bayes hálók

V

ha P(B) 6= 0

˝ következtetünk az Ai esemény feltételes A B eseménybol valószínuségére. ˝

Esettanulmány

˝ Ismernünk kell az elsodleges valószínuségeket ˝ – a–priori valószínuségeket: ˝ P(Aj ); P(B|Aj ) feltételes valószínuségeket. ˝

158/364


7

példa

Adott a következo˝ szabály: Ha a beteg megfázott, akkor lázas. (75%)

Csató Lehel

Kérdés: Numerikus modellek Bayes modell

Ha a beteg lázas, akkor megfázott.

Jelölés:

??%

M – a beteg megfázott L – a beteg lázas

Bayes hálók Esettanulmány

Szükségesek: P(M) = 0.2 – megfázott P(L|M) = 0.75 – lázas, feltéve, hogy megfázott P(L|M) = 0.2 – lázas, feltéve, hogy nem fázott meg Ekkor: P(M|L) =

P(L|M)P(M) P(L|M)P(M) + P(L|M)P(M)

Azaz P(M|L) = 0.15/0.31 = 0.483 159/364

ha P(L) 6= 0


összefoglaló

Alkalmazható, ha minden információval rendelkezünk.

7 Csató Lehel

Gyakorlatban az egymást kizáró eseményrendszer ritka...


˝ Elonyök:

Esettanulmány

Elméleti alap, Jól definiált szemantika;

Hátrányok: nagyon sok valószínuséget ˝ kell megadni, valószínuséget ˝ megadása nehéz, változ(tat)ások követése nehéz. 160/364

Bayes hálók Mesterséges Intelligencia

Bayes–modell hátránya a nagy valószínuségi ˝ tábla specifikálása,

7 Csató Lehel

Bayes–háló (vélekedésháló, belief network) egyszerusíti ˝ ezt a feladatot,

Numerikus modellek Bayes modell

Eszköze az oksági kapcsolatok leírása.


Bayes–háló Egy adott feladat változóinak oksági struktúráját leíró irányított körmentes gráf. Csomópontok az állítások, élek a kapcsolatok. Élekhez rendelünk feltételes valószínuségi ˝ táblákat: összegzik a szülo˝ változó hatását. 161/364

I

Bayes hálók

II


7

M

Kiegészítés: ˝ T - tüdogyulladásos a beteg

L


P(M) 0.2


M 0 1

P(M) 0.2

P(L|M) 0.20 0.75

P(T ) 0.03

M

T

Fordítva: L M L 0 1

162/364

P(M|L) 0.07246 0.48387

L P(L) 0.31

MT 00 01 10 11

P(L|M, T ) 0.10 0.60 0.75 1.00

Bayes hálók

II


7

M


L


P(M) 0.2


M 0 1

P(M) 0.2

P(L|M) 0.20 0.75

P(T ) 0.03

M

T


162/364

P(M|L) 0.07246 0.48387

L P(L) 0.31

MT 00 01 10 11

P(L|M, T ) 0.10 0.60 0.75 1.00

Bayes hálók

II


7

M


L


P(M) 0.2


M 0 1

P(M) 0.2

P(L|M) 0.20 0.75

P(T ) 0.03

M

T


162/364

P(M|L) 0.07246 0.48387

L P(L) 0.31

MT 00 01 10 11

P(L|M, T ) 0.10 0.60 0.75 1.00


7 Csató Lehel

III

Bayes–háló – egy adott terület teljes köru˝ leírása. „Algoritmus”:

Numerikus modellek

1

A területet leíró változók meghatározása;

2

Írjuk fel a többi változótól független csomópontokat – tehát gyökérváltozók;

3

Amíg vannak csomópont nélküli változók:


163/364

1

Válasszunk egy olyant, mely csak a már leírt változóktól függ.

2

Képezzük azt a minimális halmazt, melyek mind közvetlenül hatnak az új csomópontra;

3

Rajzoljuk be az új éleket és töltsük ki a felt.val. táblát;


7

Háló építésének az alapja P(v1 , v2 , . . . , vN ) = P(v1 |v2 , . . . , vN )P(v2 , . . . , vN )

Csató Lehel Numerikus modellek Bayes modell

IV

˝ Az indirekt függoségek kiesnek.


A felt.val. törvénye érvényes bármely rendezésre: P(vπ1 , vπ2 , . . . , vπN ) = P(vπ1 |vπ2 , . . . , vπN )P(vπ2 , . . . , vπN ) ahol π egy permutáció.

Jó – könnyen értelmezheto˝ – Bayes–hálónál fontos az építés sorrendje. 164/364

Bayes hálók

Példa I Russell & Norvig pp. 437


P(B) 0.01

7

P(F) 0.02

Földrengés

P(M|R) 0.01 0.70

Mária hívás

Betörés


BF 00 01 10 11


R 0 1

P(J|R) 0.05 0.90

P(R|B, F) 0.001 0.30 0.94 0.95

János hívás

Riasztó

R 0 1

Sorrend a háló építésénél: B, F, R, M, J . 165/364


7

Példa II

János hívás

János hívás

Csató Lehel

Mária hívás

Mária hívás


Földrengés

Esettanulmány

Riasztó

Betörés

Riasztó Földrengés

Sorrend: J, M, R, B, F . 166/364

Betörés

Sorrend: J, M, F, B, R .


7

Példa II

János hívás

János hívás

Csató Lehel

Mária hívás

Mária hívás


Földrengés

Esettanulmány

Riasztó

Betörés

Riasztó Földrengés

Sorrend: J, M, R, B, F . 166/364

Betörés

Sorrend: J, M, F, B, R .


Felhasználások

Diagnosztizáló: hatásokból az okokra;

7 Csató Lehel

Oksági kapcsolatokat vizsgáló;


Kölcsönös kapcsolatokat vizsgáló;

Egyszeru˝ muveletek, ˝ ha a háló egyszeresen összekötött. Példa: Számoljuk ki a betörés (B) valószínuségét ˝ ha János hívott (J): P(B|J) illetve akkor, ha hallottuk, hogy földmozgás is volt (F): P(B|J, F) Grafikus modelleknél visszatérünk

167/364


Felhasználások


7 Csató Lehel





167/364


Felhasználások


7 Csató Lehel





167/364


Felhasználások


7 Csató Lehel





167/364

Esettanulmány – PathFinder

I Russell & Norvig, pp. 457


7 Csató Lehel

PATHFINDER:

Numerikus modellek Bayes modell

˝ rendszer szakértoi nyirokmirigy-gyulladások diagnosztizálására;


˝ D. Heckermann; Fejlesztoje Stanford Medical Computer Science ’80-as években; > 60 betegségtípus és > 100 szimptóma illetve teszt-eredmények. http://research.microsoft.com/~heckerman 168/364

Esettanulmány – PathFinder Mesterséges Intelligencia

7

Verziók: I – szabályalapú rendszer, bizonytalanság beépítése nélkül;


II – kísérletek különbözo˝ modellekkel: Bayes háló a legjobb (10%).


III – Az „alig-valószínu” ˝ események. IV – Valószínuségi ˝ háló – Belief Net – használata. 8 óra – szótár meghatározása; 35 óra – háló meghatározása; 40 óra – val.-ek becslése (1400 val.g). ˝ PATHFINDER IV – „jobb”, mint az azt alkotó szakértok. 169/364

II



8


Csató Lehel


D-S modell


D-S definíció Példa D-S logika


Fuzzy rendszerek


Tört. visszatekintés Fuzzy halmazok Fuzzy logika

Fuzzy rendszerek

Fuzzy szabályok

Grafikus modellek Tanuló rendszerek Szimulált kifutés, ˝ Genetikus algoritmusok A perceptron modell ˝ Neurális hálók, önszervezodés Gépi tanulás 170/364

Admin ...

... trívia



8 Csató Lehel D-S modell D-S definíció


Példa D-S logika

Fuzzy rendszerek

Laborgyakorlatok:

Tört. visszatekintés Fuzzy halmazok

1


18%

2

Játékelmélet

10%

3


12%

4


Fuzzy logika Fuzzy szabályok


sok%

Dempster–Schafer modell Mesterséges Intelligencia

8

Bevezeto˝ I

Motiváció: szeretnénk döntéseket hozni akkor is, ha az események valószínuségeit ˝ nem ismerjük.

Csató Lehel D-S modell D-S definíció Példa D-S logika

˝ Például: Pacino-t meggyilkoltatta a maffia. A rendorség a következo˝ tényeket gyujtötte ˝ össze:

Fuzzy rendszerek

három bérgyilkos van: Tom, John, illetve Angie;


a gyilkos kiválasztása a következo˝ volt: ha egy dobás fej, akkor Tom, ellenkezo˝ esetben John vagy Angie;


DNS-vizsgálatok eredménye 80%-ban férfit valószínusít. ˝ Kérdés: Mekkora az egyes személyek bunösségének ˝ a valószínusége? ˝ 172/364


8

Bevezeto˝ II

Nincs megfelelo˝ valószínuségi ˝ modell, mely egyesíteni tudná a két állítást.


Bizonytalanság: A tények ismeretében nem tudunk személyt azonosítani.

Fuzzy rendszerek Tört. visszatekintés Fuzzy halmazok Fuzzy logika Fuzzy szabályok

Ábrázolás: a két tényhalmazt ábrázoljuk mértékekkel (e1 és e2 arányban megbízható információ) : ˝ e1 – m(T ) = e1 · 50% és m(J, A) = e1 · 50% Elso: Második: e2 – m(T, J) = e2 · 80% és m(A) = e2 · 20% Ismerethiány: nem tudunk valószínuségi ˝ modellt építeni, melyben ábrázolhatjuk mindkét forrást. 173/364


8 Csató Lehel

Bevezeto˝ III

Dempster-Schafer modell Egy módja a többféle információ–forrás összetételének.

D-S modell D-S definíció Példa D-S logika

Fuzzy rendszerek Tört. visszatekintés

Amennyiben e1 + e2 = 1 m(T ) + m(J, A) + m(T, J) + m(A) = 1

Fuzzy halmazok Fuzzy logika Fuzzy szabályok

Ha e1 = e2 = 50%, tudjuk a halmazok valószínuségét. ˝ Nem tudjuk a személyek valószínuségeit. ˝ Szeretnénk a fenti információkkal muveleteket ˝ végezni. 174/364


I

Cél: megkülönböztetni

8

a bizonytalanságot (uncertainty) az ismerethiánytól (ignorance).


Egy atomi B esemény valószínuségét ˝ nem ismerjük;


A valószínuség-tábla: ˝ m(T ) 25%

m(J, A) 25%

m(T, J) 40%

m(A) 10%

Például: a fentiek alapján tudjuk, hogy p(T ) ≥ 25%, ugyanakkor p(T ) ≤ 65%. 175/364


8

II

Nyilvántartjuk azt, hogy mennyire támogatunk egy állítást Bel(F);

Csató Lehel

mennyire „esélyes” az állítás Pl(F);

D-S modell

(belief)

(plausibility)



˝ Példa: egy érme szabályossága a vizsgálat elott:

Fuzzy halmazok Fuzzy logika

Bel(F) = 0

Fuzzy szabályok

illetve

Bel(F) = 0

de ha 90%-ban megállapítottuk, hogy szabályos, akkor Bel(F) = 0.5 · 0.9

illetve

Bel(F) = 0.5 · 0.9

A „fennmaradó” 10% a bizonytalanságot tükrözi. 176/364


8

Példa folyt.:

III intervallum-logika

˝ p(F) ∈ [0, 1]; vizsgálat elott:

Csató Lehel

vizsgálat után: p(F) ∈ [0.45, 0.55];


Fuzzy rendszerek

Dempster-Shafer modell: intervallumok kombinálása.

Tört. visszatekintés Fuzzy halmazok Fuzzy logika Fuzzy szabályok

Bayes analógia: alsó- illetve felso˝ korlátai egy esemény valószínuségének. ˝ Segédfüggvények bevezetése: Bel(Ai ) – alsó korlát; Pl(Ai ) – felso˝ korlát; 177/364

Belief Plausibility


8

„Belief” Bel (A1 ∪ A2 ) ≥

Csató Lehel

2 X

D-S modell D-S definíció

Bel(Ai ) − Bel(A1 ∩ A2 )

IV

„Plausibility” Pl (A1 ∩ A2 ) ≤ 2 X

i=1

Példa

Pl(Ai ) − Pl(A1 ∪ A2 )

i=1

D-S logika


A Bel és Pl függvények jellemzése: Egy m : 2Ω → [0, 1] függvény segítségével, melyre X m(∅) = 0 , m(A) = 1 Bel(A) =

X B⊂A

178/364

A∈Ω

m(B) ,

Pl(A) =

X B∩A6=∅

m(B)


Bel(A) =

8

X

m(B) ,

Tulajdonságok X

Pl(A) =

m(B)

B∩A6=∅

B⊂A

Csató Lehel

bármely A halmazra Bel(A) ≤ Pl(A)


B ⊂ A ⇒ B ∩ A 6= ∅

Példa D-S logika

Fuzzy rendszerek

bármely A halmazra Bel(A) = 1 − Pl(A)


B ⊂ A ⇔ B ∩ A 6= ∅


B⊂A ⇔ B∩A=∅

a Bel függvény szubadditív: Bel(A ∪ B) ≤ Bel(A) + Bel(B) C⊂A∧C⊂B ⇒ C⊂A∪B

a Pl függvény szuperadditív: Pl(A ∪ B) ≥ Pl(A) + Pl(B) 179/364

Dempster–Schafer Mesterséges Intelligencia

8

Példa

˝ Jellemezzük az érménket megfigyelés elott: legyen m({F, I}) = 1 és minden másra m(B) = 0;

Csató Lehel

ekkor Bel(F) = m({F}) = 0 és Pl(F) = m({F}) + m({F, I}) = 1.


Fuzzy rendszerek Tört. visszatekintés Fuzzy halmazok

Megfigyelések után:

Fuzzy logika

m({F}) = m({I}) = 0.45 és m({F, I}) = 0.1; – az összeg 1; ezért:

Fuzzy szabályok

1 2

Bel(F) = m({F}) = 0.45, illetve Pl(F) = m({F}) + m({F, I}) = 0.55;

azonosítani tudjuk a „határozatlan” részt: m({F, I}) = 0.1 180/364

Dempster–Schafer modell Logikai muveletek ˝ Mesterséges Intelligencia

8

Logikai muveletek ˝ definíciója: logikai és: Bel(A1 ∧ A2 )

Csató Lehel

X

=

m(B);

B⊂(A1 ∩A2 )

D-S modell

Pl(A1 ∧ A2 )

D-S definíció Példa

X

=

m(B);

B∩(A1 ∩A2 )6=∅

D-S logika

Fuzzy rendszerek

logikai vagy:

Tört. visszatekintés

Bel(A1 ∨ A2 )


X

=

Fuzzy szabályok

m(B);

B⊂(A1 ∪A2 )

Pl(A1 ∨ A2 )

X

=

m(B);

B∩(A1 ∪A2 )6=∅

Általánosított entrópia: AU(Bel) = max − px

181/364

X x∈Ω

! px log px

,

Bel(A) ≤

X x∈A

px


8

Kondicionálás

Feltételes Bel és Pl függvények

Csató Lehel

Amennyiben megfigyelünk egy eseményt, a halmazokhoz rendelt súly változik:


Ha C igaz, akkor csak a C-t tartalmazó halmazok ˝ a C-t töröljük, mint véletlen maradnak, melyekbol eseményt:

Fuzzy rendszerek Tört. visszatekintés Fuzzy halmazok Fuzzy logika

1

Fuzzy szabályok

2

a súlyokat újraszámoljuk; normalizáljuk a rendszert.

Egy más „univerzum” keletkezik. A C nem teljesül, akkor csak C-t nem tartalmazó halmazokat használjuk. 182/364

Dempster–Schafer modell alkalmazása Mesterséges Intelligencia

8

Használják: . . .



www.c3.lanl.gov/~joslyn/ 183/364


Összefoglaló

Konzisztens keretrendszer, mellyel lehet számításokat végezni;


A Bel(·) és Pl(·) függvények definíciója „természetes”;

Példa D-S logika


Könnyu˝ bizonytalanságot rendelni az eseményekhez – ignorancia;


Megfigyelt események kezelése – kondicionálás –nagyon nehéz, újra kell számolni a függvények értelmezési tartományát.

184/364

Fuzzy rendszerek Mesterséges Intelligencia


Bevezeto˝

Döntések bizonytalan helyzetekben – a D.S. rendszerhez hasonlóan akkor, amikor a valószínuség ˝ szabályai nem alkalmazhatóak. Tipikusan:

Példa

„Tények” gyorsan hajtott, magas ember, kb. 180 cm, olajos ruha, . . .

D-S logika


„Szabályok” ha gyorsan hajt és lassan lélegzik akkor lassítson az elektronika . . . Szükség van egy keretrendszerre, mely a fentieket képes programozni:

185/364

1

Szabályokat tudunk megadni;

2

Információt – adatokat – tudunk bevinni;

3

Következtetéseket tudunk levonni ⇒ döntéshozatal;

Bevezeto˝ II


8

Egy fuzzy rendszer építésének logikai sémája:


Megrendelo˝


Fejleszto˝


186/364

Fuzzy Szabályok Fuzzy motor, következtetések

Defuzzyfikálás

XIn

Fuzzyfikálás

Fuzzy szabályok

ZOut

Bevezeto˝ II


8

Egy fuzzy rendszer építésének logikai sémája: ˝ A megrendelo˝ közli a fejlesztovel a

Csató Lehel

változókat szabályokat

D-S modell D-S definíció Példa

a fejleszt o˝ a szabályokat „átírja” a fuzzy logika szerint; Megrendel o˝

D-S logika

Fuzzy rendszerek

˝ ami a a szabályok köré építi a „következtetot”, ˝ Fejleszt o rendszert eredményezi.


186/364

Fuzzy Szabályok Fuzzy motor, következtetések

Defuzzyfikálás

XIn

Fuzzyfikálás

Fuzzy szabályok

ZOut


8 Csató Lehel

Bevezeto˝ III

Egy fuzzy rendszer muködéséhez ˝ Szükségünk van: Keretrendszerre, mely a szabályokat értelmezni tudja;


„Fuzzyfikáló” modulra, mely a megfigyeléseket átalakítja a fuzzy logika nyelvére;

Példa D-S logika


Következteto˝ modulra;


„De-fuzzyfikáló” modulra.

Fuzzy szabályok

Eszköz Fuzzy halmazelmélet; Fuzzy logika. 187/364

Történelmi visszatekinto˝ Mesterséges Intelligencia

8

Fuzzy: homályos, zavaros, bizonytalan, kócos


Fuzzy rendszerek

’65 – Zadeh: „Fuzzy Sets”; ’70 – Fuzzy elmélet robotikai alkalmazása;


’75 – Japán . . . ’80–’95 – Empirikus vizsgálatok és széles köru˝ alkalmazások; ’00–’05 – Technológiai standard,

Lotfi A. Zadeh

Felhasználás: ˝ Ha magas a homérséklet, akkor a nyomás is magas; 188/364

Történelmi visszatekinto˝ Mesterséges Intelligencia

8

Fuzzy: homályos, zavaros, bizonytalan, kócos


Fuzzy rendszerek

’65 – Zadeh: „Fuzzy Sets”; ’70 – Fuzzy elmélet robotikai alkalmazása;


’75 – Japán . . . ’80–’95 – Empirikus vizsgálatok és széles köru˝ alkalmazások; ’00–’05 – Technológiai standard,

Lotfi A. Zadeh

Felhasználás: ˝ Ha magas a homérséklet, akkor a nyomás is magas; 188/364

Fuzzy halmazok Mesterséges Intelligencia

8

Fuzzy halmazelmélet Eszköz annak a leírására, hogy egy objektum milyen mértékben illeszkedik egy bizonytalan tényhez;

Csató Lehel D-S modell

Alkalmas bizonytalan kijelentések formalizálására.


Nem valószínuségi ˝ modell.

D-S logika

Fuzzy rendszerek

Döntések hozatala „igazság-értékek” alapján.


Fuzzy halmazok: nem „teljes” hozzátartozás specifikálása.


189/364

I


8 Csató Lehel

II

Klasszikus logika Fuzzy logika Egy kijelentés igaz: – 1; Egy kijelentés vagy hamis – 0. igazságértéke µ(p) ∈ [0, 1]



Egy A halmazra: 1 ha x ∈ A IA (x) = 0 ha x ∈ /A

µA (x) ∈ [0, 1]

∀x ∈ Ω

Egy halmaz= µA

˝ Például: M – magas homérséklet

µM (t)

µ

190/364

50

60

70

80

˝ T - homérséklet


8

A definíciós intervallumot általában felosztjuk több fuzzy halmazra:


III

Alacsony

Magas

Közepes

1



T


30

40

50

60

70

80

90

100

110

Egy fuzzy halmaz tehát függvény, µK : Ω → [0, 1]:   1 ha x ∈ [50, 70]    (x − 40)/10 ha x ∈ [40, 50] µK (x) =  (90 − x)/20 ha x ∈ [70, 90]    0 ha x ≤ 40 vagy x ≥ 90 191/364

Fuzzy logika Mesterséges Intelligencia

0

˝ A logikai muveletek ˝ halmaz–muveletekre ˝ vezethetok vissza:

8 Csató Lehel

a logikai vagy az egyesítés: A ∨ B def = A∪B

D-S modell

a logikai és a metszet:


A ∧ B def = A∩B

D-S logika

a logikai negáció a komplementer:

Fuzzy rendszerek

A def = Ω\A


A fuzzy logikai muveletek ˝ fuzzy halmazok egyesítése, metszete, illetve komplementere. A három logikai muvelet ˝ redundáns: A∨B=A∧B

⇒

A∨B=A∧B

Csak a konjunkciót és a negációt kell specifikálnunk. 192/364


I

A fuzzy rendszerekben a konjunkciót és a negációt specifikáljuk.

8

A konjunkció egy T-norma:

Csató Lehel

T : [0, 1] × [0, 1] → [0, 1] A T (1, 1) = 1 kivételével minden sarokpontban az értéke 0 kell, hogy legyen (hogy kapjuk vissza a klasszikus logikát). A negáció egy-argumentumú függvény: C : [0, 1] → [0, 1] A sarokfeltételek: C(0) = 1, illetve C(1) = 0.



A diszjunkciót a De-Morgan reláció alapján számoljuk ki (S-konormának nevezzük): S : [0, 1] × [0, 1] → [0, 1]

S(a, b) = C ( T (C(a), C(b)) ) 193/364


8

II

Példa: A konjunkciónak megfelelo˝ T-norma: T (a, b) = min(a, b) T (0, 0) = T (0, 1) = T (1, 0) = 0, illetve T (1, 1) = 1.

Csató Lehel D-S modell D-S definíció Példa

A negáció legyen:

D-S logika

Fuzzy rendszerek

C(x) = 1 − x

Tört. visszatekintés

C(1) = 0, illetve C(0) = 1.


A diszjunkció meghatározása: S(a, b) = 1 − T (1 − a, 1 − b) S(a, b) = 1 − T (1 − a, 1 − b) = 1 − min(1 − a, 1 − b) = 1 + max(−1 + a, −1 + b) = max(1 − 1 + a, 1 − 1 + b) = max(a, b)

194/364


8

Logikai szabályok: µA∧B (x) = min [µA (x), µB (x)]

Csató Lehel

µA∨B (x) = max [µA (x), µB (x)]


µA (x) = 1 − µA (x)

Példa D-S logika


195/364

III


8 Csató Lehel D-S modell

IV

Logikai szabályok: a, b ∈ {0, 1} ÉS = 1 csak ha a = 1 és b = 1 VAGY = 0 csak ha a = 0 és b = 0 Alternatív formák:


µA∧B (x) = µA (x) · µB (x) ,

D-S logika

Fuzzy rendszerek

µA (x) = 1 − µA (x)

µA∨B (x) = µA (x) + µB (x) − µA (x) · µB (x)


196/364


8 Csató Lehel D-S modell D-S definíció Példa D-S logika


-!-

Fuzzy logika inkonzisztens x vagy A-nak vagy A-nak eleme, azaz µA∩A = 1.   1 µA∨A (x) = max [µA (x), 1 − µA (x)]   1 − µA (x) [1 − µA (x)]

klasszikusan fuzzy logika 1 def. fuzzy logika 2 def.


Ugyanígy: szeretnénk, hogy µA∧A = 0. Helyette:   0 µA∧A (x) = min [µA (x), 1 − µA (x)]   µA (x) [1 − µA (x)]

klasszikusan fuzzy logika 1 def. fuzzy logika 2 def.

vizsga feladattípus: határozzuk meg a „modus ponens” szabály fuzzy változatát. 197/364


8

Feladat I

A negációt szeretnénk úgy meghatározni, hogy legyen folytonos, bijektív;

Csató Lehel

teljesüljön a negált negáltja önmaga, azaz C(C(x)) = x

D-S modell D-S definíció Példa

legyen C(0) = 1 és C(1) = 0

D-S logika

Fuzzy rendszerek Tört. visszatekintés Fuzzy halmazok Fuzzy logika

A C(x) bijektív, alkalmazva a z = C(x) ⇔ x = C−1 (x):

Fuzzy szabályok

C(z) = C−1 (z) ˝ azaz a C(·) függvény a foátló szerint szimmetrikus. A C(x) = 1 − x egy megoldás. Egy megoldás-család – pozitív q értékekre – a Cq (x) = 198/364

√ q

1 − xq


8

A Cq (x) = értékekre:

√ q

Feladat II

1 − xq grafikus képei a q = {1/3, 1/2, 1, 2, 3}

Csató Lehel D-S modell D-S definíció

C(x)

Példa D-S logika


.8


.6 .4 .2 x .2 199/364

.4

.6

.8

Fuzzy szabályok Mesterséges Intelligencia

Értheto˝ formában írják le egy rendszer muködését: ˝

8 Csató Lehel

Könnyu˝ megfogalmazni;

D-S modell

˝ ˝ Könnyen ellenorizhet o;


Módosításokhoz nem kell az egész rendszert átírni.


Használják a fuzzy logika következtetési mechanizmusait;


Logikai szabályok alapján; Fuzzy változók értékeit számolják; De-fuzzyfikálás után az eredmény jó kontroll-változó.

200/364

0


8

I

Példa: ˝ Ha magas a homérséklet, akkor a nyomás is magas;


Fuzzy rendszerek

Fuzzy h szabályok: i HA X alacsony ÉS Y magas AKKOR Z közepes


Definiáljuk az alacsony, magas és közepes halmazokat: µ

µalacsony

50 201/364

µkozepes

60

70

µmagas




Fuzzy rendszerek

Fuzzy szabályok: X Alacsony Alacsony – Közepes – Magas Közepes


II

Y Közepes Magas Közepes Alacsony Magas Közepes Magas Alacsony – nem megengedett állapot


Szabályok alkalmazása: Megfigyelt értékek:

x = 50, y = 78.75

Fuzzyfikálás – fuzzy halmazokra való áttérés: X szerint csak az Alacsony csoportot kell vizsgálni. Y szerint a Közepes és Magas csoportokat. 202/364

Fuzzy szabályok

III


8 µmag (y) = 0.75;

Csató Lehel

µal (x) = 1 illetve

µkoz (y) = 0.25;



Kombinálás: VAGY= max

µ


µz 50

60

70

Kontroll esetén Egy érték kiírása: súlyozott közép Z = 53. 203/364


Fuzzy rendszer Mesterséges Intelligencia

8 Csató Lehel

–I–

Alkalmazás

Mitsubishi légkondicionáló rendszer Ipari légkondicionáló mely rugalmasan reagál a környezeti változásokra.


Megvalósítás:

Fuzzy rendszerek

50 fuzzy szabály


6 nyelvi változó, közöttük a szoba és a fal ˝ ˝ homérséklete, illetve ezek idobeli változásai;

Fuzzy szabályok

4 nap – prototípus; 20 nap – teszt/integrálás; 80 nap – tesztelés; ⇒ mikrokontroller implementálás. ˝ Elonyök: kevesebb szenzor, változó környezet, 24%-kal kisebb fogyasztás; 204/364

Fuzzy rendszer Mesterséges Intelligencia



– II –

Alkalmazás

Alkalmazások: ˝ uvek Erom ˝ kontrollja (Tokio); Egyszerusített ˝ robot-kontroll (Fuji, Toshiba, Omron); ˝ Fényképezogép automata irányítása (Omron); Motor-fogyasztás, irányítás (Nissan,Subaru);


Gyártósorok szilícium-lapkáinak vágása (Canon); Rák diagnózis (Kawasaki Med. School); Jogi eljárások szimulációja (Meihi Gakuin Univ, Nagoya Univ.) . . . Matsushita, Sony, Canon, Minolta, Sanyo, Hitachi, Ricoh, Fujitech, Toshiba, . . . . http://www.esru.strath.ac.uk/Reference/concepts/fuzzy/fuzzy_appl.00.htm 205/364


8

Összefoglaló

Fuzzy rendszerek: ˝ Foként kontroll feladatokra használjuk. Ajánlottak ha:


komplex rendszerek esetén, nincs matematikai modell; nemlineáris modellek esetén; ˝ tudás bevitelére. szakértoi



Nem ajánlottak ha:


˝ hagyományos kontroll megfelelo; létezo˝ – egyszeru˝ – matematikai modell; nincs megoldás.

Más alkalmazások: Sony PalmTop – „fuzzy” döntési fa implementálása karakterfelismerésre (Kanji). 206/364



9


Csató Lehel


Grafikus modellek


GM feladatok

Irányítatlan GM-ek


Matlab feladat


Admin ...



9 Csató Lehel Grafikus modellek

... trívia


GM feladatok


Laborgyakorlatok:

Matlab feladat

1


18%

2

Játékelmélet

10%

3


12%

4



sok%

˝ Fellendüloben az MI Mesterséges Intelligencia

9 Csató Lehel Grafikus modellek GM feladatok


Újabb MI-divat?

2007.09.12.

Az MI célja, hogy a gépek emberre jellemzo˝ tulajdonságokkal rendelkezzenek: nyelvhasználat, fogalomalkotás, elvonatkoztatás, nem triviális problémák megoldása, öntökéletesítés. (McCarthy, Minsky, Shannon)

Matlab feladat

MI a mindennapokban „A kifejezetten mérnöki munka és alkalmazott tudományok terén elért eredményeket figyelembe véve, a gépi tanulás technikáinak különbözo˝ problémákra (webes keresés, pénzügyek, molekuláris rendszerek megértése) történt alkalmazása a legsikeresebb MI–részterület.” – Terry Winograd szerint. „Ezek az eredmények, és más területek, ˝ például a robotika fejlodése intelligensebb gépekhez vezetnek.” http://www.agent.ai 209/364

Winograd home

Grafikus modellek Mesterséges Intelligencia

9

Grafikus modellek (probabilistic graphical models - PGM)

I

Kevin Murphy

Csató Lehel Grafikus modellek

A gráfelmélet és a valószínuségszámítás ˝ ötvözése.

GM feladatok


˝ gráf, mely egy rendszer függoségeit ábrázolja;

Matlab feladat

csúcsokhoz rendelt függvények, melyek a változók közötti kapcsolatot írják le; „Minden grafikus modell”

szemléletmód 5

Bayes–háló – irányított aciklikus gráfú PGM; Markov modell – irányítatlan PGM. 5 210/364

„minden feladat szeg”, ha egy kalapácsot tartunk a kezünkben . . .

Grafikus modellek (GM) Mesterséges Intelligencia

Irányított GM

II

Irányítatlan GM

9 X

Csató Lehel

Y

W X

Grafikus modellek

Y

GM feladatok


Z

Matlab feladat

feltételes függetlenség;

feltételes függetlenség;

kauzális relációk;

szimmetrikus;

X⊥Y (láttuk) 211/364

Z

X ⊥ Y | {W, Z} W ⊥ Z | {X, Y}

GM feladattípusok Mesterséges Intelligencia

Feladatok – adott GM struktúrára:

9

események (felt.) val.-nek kiszámítása;

Csató Lehel

állapítsuk meg két csúcs (feltételes) függetlenségét;

Grafikus modellek

adatok alapján építsünk optimális gráfot (indukció).

GM feladatok


I

Inferencia P(X13 |X7 , X8 , X9 , X16 ) X1

Matlab feladat

X2

X5

X3

X6

X11

X14

X7

X12

Optimális struktúra keresése

X4

X8

X9

X10

X13

X15

X16 X17

212/364

X18

GM feladattípusok Mesterséges Intelligencia

Feladatok – adott GM struktúrára:

9

események (felt.) val.-nek kiszámítása;

Csató Lehel

állapítsuk meg két csúcs (feltételes) függetlenségét;

Grafikus modellek

adatok alapján építsünk optimális gráfot (indukció).

GM feladatok


I

Inferencia P(X13 |X7 , X8 , X9 , X16 ) X1

Matlab feladat

X2

X5

X3

X6

X11

X7

X12

Optimális struktúra keresése

X4

X8

X9

X10

X13

Inference X14

X15

D

X16 X17

212/364

X18

Irányított GM Mesterséges Intelligencia

9

I

Bayes–labda algoritmus: feltételes függetlenség–teszt. d-szeparáltság

Csató Lehel Grafikus modellek GM feladatok

Irányítatlan GM-ek Matlab feladat

Egy grafikus modellben X az Y-tól d-szeparált a Z ismeretében, ha minden X-et és Y-t összeköto˝ irányítatlan úton létezik w úgy, hogy: vagy

→ w ← és a w vagy utódai nincsenek a Z-ben;

vagy

w nem → w ← és w ∈ Z. X

213/364

Y

X

Y

Z

Z

X⊥Y

X 6⊥ Y

Irányított GM X1


Példa X2

X3

X4

9 Csató Lehel

X5

X6

X7

X8

X9

X10

Grafikus modellek GM feladatok


X11

X12

X13

Matlab feladat

X14

Kérdések ? X1 ⊥ X10 | {X7 , X8 , X9 } ? X1 ⊥ X10 | ∅ ? X1 ⊥ X15 | {X5 , X6 , X13 } 214/364

X15

nem igen igen

Irányított GM X1


Példa X2

X3

X4

9 Csató Lehel

X5

X6

X7

X8

X9

X10



X11

X12

X13

Matlab feladat

X14


X15

nem igen igen

Irányított GM X1


Példa X2

X3

X4

9 Csató Lehel

X5

X6

X7

X8

X9

X10



X11

X12

X13

Matlab feladat

X14


X15

nem igen igen

Irányított GM X1


Példa X2

X3

X4

9 Csató Lehel

X5

X6

X7

X8

X9

X10



X11

X12

X13

Matlab feladat

X14


X15

nem igen igen

Irányítatlan GM Mesterséges Intelligencia

Különbség:

a gráf éleinek nincs iránya; szimmetrikus kapcsolat–modellezés. ?Paraméterezés:

9 Csató Lehel

X1

I

X2

X3

felt. val.-gek: nem jók;



X5

X6

X7

X8

Matlab feladat

X11

X12

X13

? – Nem konszisztens Y P(Xi |Szomszedi )

Függetlenség: gráfon. Pl:

Helyette Y Φ(Xi , Szomszedi )

{X1 , X2 } ⊥ {X11 , X12 , X13 }|{X5 , X6 }

klikkek jellemzése.

215/364


Különbség:


9 Csató Lehel

X1

I

X2

X3




X5

X6

X7

X8

Matlab feladat

X11

X12

X13




{X1 , X2 } ⊥ {X11 , X12 , X13 }|{X5 , X6 }


215/364


Különbség:


9 Csató Lehel

X1

I

X2

X3




X5

X6

X7

X8

Matlab feladat

X11

X12

X13




{X1 , X2 } ⊥ {X11 , X12 , X13 }|{X5 , X6 }


215/364


Különbség:


9 Csató Lehel

X1

I

X2

X3




X5

X6

X7

X8

Matlab feladat

X11

X12

X13




{X1 , X2 } ⊥ {X11 , X12 , X13 }|{X5 , X6 }


215/364


II

Klikkek: teljesen összekötött csúcsok.

9 Csató Lehel

X) = P(X



1 Z

Y

xc ) φc (x

c∈Klikkek

Z=

X

Y

xc ) φc (x

X c∈Klikkek

ahol xc ) ≥ 0 φc (x

potenciál-függvény

Z

partíciós függvény

Gibbs–eloszlás Egy eloszlás, mely ábrázolható egy H gráffal és {φc }c potenciálfüggvényekkel, H fölötti Gibbs–eloszlásnak nevezünk. 216/364

Irányítatlan GM

III


9

X

Y

Z


A gráf alapján X ⊥ Z|Y


P(X, Y, Z) = P(X|Y)P(Y, Z) = φxy (X, Y)φyz (Y, Z)

Matlab feladat

P(X, Y, Z) = P(Z|Y)P(X, Y) = φyz (Y, Z)φxy (X, Y)

φc – potenciálfüggvények ˝ „kompatibilitást”, „összeférhetoséget” jelölnek; nem eloszlásfüggvények. 217/364


IV

Exponenciális eloszláscsalád:

9 Csató Lehel

X) = P(X Grafikus modellek GM feladatok

1 Z

Y

xc ) φc (x

c∈Klikkek

"


θ) + = exp − log Z(θ

Matlab feladat

X

# x ci ) fi (x

i∈I

ahol fi def = log φci

I – index-halmaz

Példa: Gaussz-eloszlás (teljes kapcsolat) " # d log(2π) + log |Σ| + X T Σ−1X X) = exp − P(X 2 218/364

Irányítatlan GM

Feladat


9

X, Y, Z, W ∈ 0, 1



W Ismerjük: φxw , φyw , φxz , φyz

φxw (X, W)

φyw (Y, W)

X

Y

φxz (X, Z)

φxz (X, Z)

Számítsuk ki: p(Y = 1|W = 1)

Milyen esetekben jók/nem jók a GM-ek ? 219/364

Z

Osztályozás – USPS http://www.cs.ubbcluj.ro/~csatol/mestint/USPS Mesterséges Intelligencia



220/364

I

Osztályozás – USPS http://www.cs.ubbcluj.ro/~csatol/mestint/USPS Mesterséges Intelligencia



USPS adatok United States Postal Service; kézzel írott számjegyek 16 × 16-os bit-térképe; ≈ 7200 tanulási- és ≈ 2000 teszt-adat; Feladat: Bináris osztályozás: válasszuk el a négyeseket (4) a ˝ (7). hetesektol ˝ Írjunk egy osztályozási algoritmust a következok közül: Döntési fa; Neurális háló; SVM; Bayes osztályozó. ˝ szerint: Értékeljük az algoritmust a következok osztályozási hiba tanulási adatokon; osztályozási hiba teszt-adatokon – 10% alatt!; ˝ tanulási ido; vizsgáljuk meg a rosszul osztályozott „pontokat”; 221/364

II

Osztályozás http://www.cs.ubbcluj.ro/~csatol/mestint/USPS Mesterséges Intelligencia



4 7 7 4 4 7 7 4 4 4 4 7 7 7 4 7 −1 +1 +1 −1 −1 +1 +1 −1 −1 −1 −1 +1 +1 +1 −1 +1 222/364

III

Osztályozás Mesterséges Intelligencia

IV

Osztályozó algoritmus:

9 Csató Lehel

θ) Program (θ



Tanulás: θ0 kezdoértékek ˝

tanulási adatok x1 , y1 ), . . . , (x xN , yN ) D = (x

új adatokra:

Becslés: θ 1 → . . . → θ post .

hiba mérése tesztadatokon.

Közben: tanulási hiba mérése. 223/364

Tesztelés: θpost használata;

Dtest = . . .

±1


IV

Osztályozó algoritmus:

9 Csató Lehel

θ) Program (θ



Tanulás: θ0 kezdoértékek ˝

tanulási adatok x1 , y1 ), . . . , (x xN , yN ) D = (x

új adatokra:

Becslés: θ 1 → . . . → θ post .

hiba mérése tesztadatokon.

Közben: tanulási hiba mérése. 223/364

Tesztelés: θpost használata;

Dtest = . . .

±1


Program + dokumentáció:

9

V (dolg...)

Algoritmus kiválasztása; Tanulás – paraméterek becslése;

Csató Lehel Grafikus modellek

tanulási adatok beolvasása; adatok transzformációja – pre–processzálás; algoritmus paramétereinek inicializálása; paraméterek tanulása.

GM feladatok


Tesztelés; teszt-adatok beolvasása – függetlenek a tanulási mintáktól!; adatok transzformációja – pre–processzálás; algoritmus paramétereinek beolvasása – tanulási eredmény; hiba mérése.

Dokumentálás: algoritmus, módszer, statisztika 224/364

Osztályozás

Program binclass.m




clear all; % data generation nTr = 200; nTe = 400; [dX dY] = cl_data(nTr,[],0); ii_1 = find(dY==1); d1 = dX(ii_1,:); d2 = dX(setdiff([1:nTr],ii_1),:); N_1 = size(d1,1); N_2 = size(d2,1); pi1 =N_1/nTr; pi2 = N_2/nTr; mu1 = sum(d1,1)/N_1; % class means mu2 = sum(d2,1)/N_2; d = d1 repmat(mu1,[N_1 1]); sig1 = d'*d/N_1; sig1inv = sig1^(1); d = d2 repmat(mu2,[N_2 1]); sig2 = d'*d/N_2; sig2inv = sig2^(1); % generating nTe test data [dX, dY] = cl_data(nTe,[],0); ii_1 = find(dY==1); data1 = dX(ii_1,:); data2 = dX(setdiff([1:nTe],ii_1),:); N_1 = size(data1,1); N_2 = size(data2,1);

. . . grafikus ábrázolás. . . 225/364

% performing classification log_sig1 = log(det(sig1))log(pi1); log_sig2 = log(det(sig2))log(pi2); % classification for data1 p_1=data1repmat(mu1,[length(data1) 1]); p_1=sum(((p_1*sig1inv).*p_1),2); p_2=data1repmat(mu2,[length(data1) 1]); p_2=sum(((p_2*sig2inv).*p_2),2); class(1,1) = length( ... find(p_1+p_2 > log_sig1log_sig2) ); class(1,2) = N_1 class(1,1); % SIMILARLY for the second dataset p_1=data2repmat(mu2,[length(data2) 1]); p_1=sum(((p_1*sig2inv).*p_1),2); p_2=data2repmat(mu1,[length(data2) 1]); p_2=sum(((p_2*sig1inv).*p_2),2); class(2,2) = length( ... find( p_1+p_2 > log_sig2log_sig1)); class(2,1) = N_2 class(2,2); % the confusion matrix: class

Osztályozás

Eredmény binclass.m


Eredmény: Class−cond. prob. C1

9

Class−cond. prob. C2

Csató Lehel

6

6

Grafikus modellek

4

4

2

2

GM feladatok


0 0

2

4

0 0

Posterior probability

6

6

4

4

2

2

0 0 226/364

2

2

4

Classification boundary

4

0 0

2

4



10


Csató Lehel


Tanulás


Indukció Cross-validation


Döntési Fák


Netlab


Admin ...



10 Csató Lehel Tanulás

... trívia



Laborgyakorlatok:

Döntési Fák 1


18%

2

Játékelmélet

10%

3


12%

4


Netlab


sok%

Olcsóbb gépi fordítás Mesterséges Intelligencia

10 Csató Lehel Tanulás Indukció Cross-validation Döntési Fák Netlab

METIS II

A gépi fordítás – annak ellenére, hogy régóta vizsgált tudományág – nem versenyezhet a tolmácsokkal. Még akkor sem, ha az egyértelmu˝ szókészlettel ˝ kifejezetten formális szövegeket produkáló rendelkezo, ˝ területeken – például a repülogép-gyártásban – figyelemreméltó eredményeket érnek el. Korpusz Nagymennyiségu˝ strukturált, elektronikusan tárolt szövegbázis; Egy adott nyelvet reprezentál, akár több tízmillió szóból is állhat; Általában alterületen használják: statisztikai elemzésekre, illetve nyelvi törvények érvényességének vizsgálatára. A gyujtemény ˝ lehet egyetlen (monolingual) vagy két (több) nyelvu˝ (multilingual). A rendszer így tanulja meg, hogy egy nyelv szavai és kifejezései miként kapcsolódnak egy másik nyelv kifejezéseihez és szavaihoz. Bebizonyosodott, hogy METISII a hosszú évtizedek fejlesztésének eredményeként létrejött piacvezeto˝ – szabályalapú – rendszerrel is képes felvenni a versenyt. 229/364

„Tanuló” rendszerek Mesterséges Intelligencia

pp. 525 – Russell & Norvig, 1995 Agents that can improve their behaviour through diligent study of their own experiences.

10 Csató Lehel

Algoritmus változtatható állapottérrel, mely muködése ˝ során az újabb – ugyanolyan típusú – feladatokat jobban oldja meg.

Tanulás Indukció Cross-validation Döntési Fák Netlab

Példák: genetikus algoritmus, neurális hálók, stb. „Machine Learning” – „Gépi tanulás”. Induktív rendszerek – inferencia. 230/364

Indukció Mesterséges Intelligencia

Induktív megoldás

–I–

Dedukció

Deduktív megoldás

10 Csató Lehel

Modell feltételezése: f(zz, θ ),

Tanulás Indukció Cross-validation

Adatok halmaza: D = {zz1 , . . . , z N }

Döntési Fák Netlab

Illeszto˝ – hiba – függvény: L (f(zz)) „optimális modell”: θ ∗ Predikció: f(zz, θ ∗ ). 231/364

Nincs modell, Adatok: D = {zz1 , . . . , z N } Illesztési muvelet ˝ egy z új mintára, használunk minden adatot.


– II –

Induktív megoldás

Dedukció

Deduktív megoldás

10 Csató Lehel

D. . . . . . . . . . .

D. . . . . . . . . . .

x∗


^ θ

Döntési Fák

??

Netlab

x|θ^) f(x

x∗

x

x∗ ) g(x ?? x∗ |θ^) f(x 232/364

„Levezetjük” a g függvény x ∗ -hoz tartozó értékét.


– II –

Induktív megoldás

Dedukció

Deduktív megoldás

10 Csató Lehel

D. . . . . . . . . . .

D. . . . . . . . . . .

x∗


^ θ

Döntési Fák

??

Netlab

x|θ^) f(x

x∗

x

x∗ ) g(x ?? x∗ |θ^) f(x 232/364



– II –

Induktív megoldás

Dedukció

Deduktív megoldás

10 Csató Lehel

D. . . . . . . . . . .

D. . . . . . . . . . .

x∗


^ θ

Döntési Fák

??

Netlab

x|θ^) f(x

x∗

x

x∗ ) g(x ?? x∗ |θ^) f(x 232/364



– II –

Induktív megoldás

Dedukció

Deduktív megoldás

10 Csató Lehel

D. . . . . . . . . . .

D. . . . . . . . . . .

x∗


^ θ

Döntési Fák

??

Netlab

x|θ^) f(x

x∗

x

x∗ ) g(x ?? x∗ |θ^) f(x 232/364



– II –

Induktív megoldás

Dedukció

Deduktív megoldás

10 Csató Lehel

D. . . . . . . . . . .

D. . . . . . . . . . .

x∗


^ θ

Döntési Fák

??

Netlab

x|θ^) f(x

x∗

x

x∗ ) g(x ?? x∗ |θ^) f(x 232/364



10

– III –

„Becslés” egy modell ismeretében.

Csató Lehel

Modell-osztály;

Tanulás

Modellek közötti ^ preferencia ⇒ θ;


Predikció a modell alapján;


Pl: lineáris becslések, neurális hálók; Döntési/regressziós fák;

Dedukció

A cél egy ismert adatra egy választ fogalmazni; A válasz: kategoriális, folytonos ... K-nn: K legközelebbi szomszéd alapján történo˝ közelítés; Rezolúció: egy ismert predikátumról eldönteni, hogy igaz vagy hamis.

Rejtett változós modellek A továbbiakban Induktív módszerekkel foglalkozunk. 233/364

Induktív módszerek Mesterséges Intelligencia

adatokból „információt” vonnak ki;6

10 Csató Lehel Tanulás Indukció Cross-validation Döntési Fák Netlab

Inductive learning methods Systematically produce intensional concept descriptions from extensional concept descriptions. I.e, from the specific knowledge provided by domain examples, ∼ obtain general domain knowledge. Információ induktív rendszereknél Egy indukció folyamán az adatokból „nyert” információt a modell paraméterei tárolják. x|θ θ), θ ∈ Ω} modell esetén a D adatokat az Egy F def = {f(x optimális θ^ paraméter helyettesíti. 6 234/364

Hogyan definiáljuk az információ fogalmát?

I

Induktív módszerek Mesterséges Intelligencia

10 Csató Lehel

„Információ” - θ^: x|θ θ) függvényt keresünk. egy f(x ^ θ az optimális függvény „koordinátája”.

Tanulás

Nem ismerjük az adatokat generáló függvényt

Indukció Cross-validation Döntési Fák

Melyik paraméter jobb?

Netlab

Tesztelési módszer: az adatokat kettéosztjuk: tanulási- illetve teszt-adathalmaz; az optimális θ^ meghatározásához csak a tanuló-adatokat használjuk; Tesztelés: hiba mérése a teszt-adathalmazon. 235/364

II

Paraméterek jóságának a mérése Mesterséges Intelligencia

Cross-validation:

10

módszer, mely méri a tanulási folyamat eredményességét;

Csató Lehel

olyan esetekben használatos, ahol nincs modell illetve külön teszt-adat;

Tanulás Indukció Cross-validation Döntési Fák Netlab

Módszer: a teljes adat felosztása: K részre; tanulási-, illetve teszt-adatok definiálása: j-dik rész a teszt-adat; {1..K} \ j tanulási adatok.

minden j-re mérjük a teszt-hibákat. (összegezzük / átlagoljuk) 236/364

I

Paraméterek jóságának a mérése Mesterséges Intelligencia

II

Cross-validation

10 Csató Lehel

˝ Elonye:

Tanulás

˝ illetve az adatok típusától nem függ a hibafüggvénytol (diszkrét, folytonos, strukturált);

Indukció Cross-validation Döntési Fák Netlab

könnyen kódolható. Hátránya: Nagy adathalmazra sokáig fut; Nem alkalmazható paraméterek becslésére. 237/364

Döntési/Regressziós fák Mesterséges Intelligencia


Regresszió: f:Ω→R Osztályozás: f : Ω → {Igen, Nem}

Indukció

Definíció: fa formájában tárol egy függvényt; leszármazottak nélküli csúcs - levél; másképp belso˝ csúcs; minden belso˝ csúcshoz van egy predikátum rendelve; Például:

Cross-validation Döntési Fák

Kor < 20, Fogl ∈ {Diak, Tanar}.

Netlab

szabályok megállapítására szolgál; általánosítások – extrapolálás; Nem fontos az adatok diszkrét/folytonos léte; 238/364

Döntési fák Mesterséges Intelligencia

sorrend-függo˝ az eredmény;

10

szomszédság/topológia meghatározása: modellezési kérdés.

Csató Lehel

Sok adat =⇒ nagy fa, redundáns modellezés.

Tanulás Indukció Cross-validation Döntési Fák

Logikai bemeno˝ adatok esetén:

Netlab

Bináris fa természetes; Folytonos bemeno˝ adatok esetén: El kell dönteni egy-egy ág érvényességét; ⇔ Diszkretizálni kell a teret; ⇔ Modellezési feladat 239/364

I

Döntési fa építése Mesterséges Intelligencia

10 Csató Lehel

Döntési fa építése Rekurzívan: Vizsgáljuk meg az adatokat és állapítsuk meg a legjobb vágást;

Tanulás Indukció

Osszuk ketté az adatokat a vágás szerint;

Cross-validation Döntési Fák Netlab

? Kérdések ? Megállás; Legjobb vágás keresése; ˝ Vágások minosége: CART (Classification and Regression Trees) algoritmus. 240/364

Netlab Mesterséges Intelligencia

Ian T. Nabney: NETLAB Algorithms for Pattern Recognition Springer 2002


I

http://www.ncrg.aston.ac.uk/netlab

Matlab függvény-gyujtemény ˝

Indukció

˝ egyszeruen ˝ Ingyenesen letöltheto; ˝ kezelheto;

Cross-validation

Nagyon sok modell és algoritmus tesztelheto˝ – anélkül, hogy a modelleket implementálni kellene;


Implementált modellek és algoritmusok: (módosítható demó-k) Regresszió Bayes-módszerek

241/364

Osztályozás

Optimalizálás

Klaszterezés

Mintavételezés

Netlab Mesterséges Intelligencia

II

Netlab használata:

10

Installálás: letöltés és:

Csató Lehel Tanulás

addpath('_netlab_path_')

Demók indítása:

demnlab

Programozás a demók módosításával, pl.

demmlp1


Példa:


%data generation. ndata = 20; noise = 0.2; x = {0:1/(ndata - 1):1}’; t = sin(2*pi*x) + noise*randn(ndata, 1); % Set up network parameters. nin = 1; % Number of inputs. nhidden = 3; % Number of hidden units. nout = 1; % Number of outputs. alpha = 0.01;% weight-decay prior. % Initialisation net = mlp(nin, nhidden, nout, ’linear’, alpha);

% Option vector intialisation options = zeros(1,18); options(1) = 1; % display error values. options(14) = 100;% Number of training cycles. % Train using scaled conjugate gradients. {net, options} = netopt(net, options, x, t, ’scg’); % Plot for TEST data plotvals = {0:0.01:1}’; y = mlpfwd(net, plotvals);

A Netlab programmal egyszeruen ˝ megoldható a laborfeladat. 242/364



11


Csató Lehel


Ann. / G.A.


Bevezeto˝ Annealing


G.A. G.P.


Admin ...



11 Csató Lehel Ann. / G.A.

... trívia


Bevezeto˝ Annealing G.A. G.P.

Laborgyakorlatok: 1


18%

2

Játékelmélet

10%

3


12%

4



sok%

Nehéz feladatok Mesterséges Intelligencia

11

Néha NEM lehet a gradiens-szabályokat alkalmazni mert: Túl bonyolult a modellben a paraméter–kimenet kapcsolat. Pl.

Csató Lehel Ann. / G.A. Bevezeto˝ Annealing G.A.

A paraméterek nem numerikusak. Pl. szemantikus hálók vagy Bayes-hálók tanulása.

G.P.

Azonban: képesek vagyunk a θ paraméter jóságának a mérésére, Van egy „szomszédság-reláció” a paraméterek között, 245/364

Szimulált kifutés ˝ Mesterséges Intelligencia

11 Csató Lehel Ann. / G.A. Bevezeto˝ Annealing G.A.

I

Hibafüggvény: x|θ θ) Méri az F modellcsalád egy elemének – az f(x függvénynek – a „jóságát”. Például - négyzetes hiba: X θ), F ) = xn |θ θ))2 (yn − f(x L(D, f(·|θ n

G.P.

Egy D adathalmaz hibája – empirikus hiba Szomszédság: A θ ∈ Ω paraméterek (pl. fák) esetén: θ) θ 0 ∈ δ (θ

θ, θ 0 ) < ha d(θ

A paraméter–tér bejárására szolgál → összekötött halmazoknál jó. 246/364


II

Eloszlás:

1 θ|β) ∝ exp − L(D, f(·|θ θ), F ) p(θ β

11 Csató Lehel

Ann. / G.A.

h i θ), F ) exp − β1 L(D, f(·|θ h i θ|β) = P p(θ 1 θ), F ) θ∈Ω exp − β L(D, f(·|θ


p(x) 3

x, θ^) modell optimális a Az f(x legnagyobb p(θ^)–nál;

β = 1/9 2

˝ β – „homérséklet” paraméter;

247/364

˝ β kezdoértéke nagy ⇒ nincsenek nagy különbségek;

β=1

β & 0 - egy állapot választódik ki.

−3 −2 −1

1

x 1

2

3


11

III

˝ mert: Gyakorlatban nehezen kivitelezheto,

Csató Lehel

Nem lehet felsorolni az Ω összes elemét;

Ann. / G.A. Bevezeto˝

Nem könnyu˝ egy modell hibájának a kiszámítása – ˝ van szó; =⇒ gyakran muszeres ˝ mérésekrol

Annealing G.A. G.P.

Közelíto˝ módszerek alkalmazása – a „szomszédság” felhasználásával: θ0

→

θ1

→

···

→

θT

ahol az iterációk alatt „javul” a θ illeszkedése az adatokhoz. 248/364


11 Csató Lehel

Általában a „hutést” ˝ szabályozzuk: {βt }∞ 1 . Algoritmus: 1

Ann. / G.A. Bevezeto˝ Annealing

Adat-beolvasás: D; t = 0; x|θ θt )); Inicializálás: θ 0 ; Számítjuk: L(D, f(x

G.A. G.P.

2

3

249/364

θt ) Választunk a szomszédság alapján: θ 0 ∈ δ (θ 0 0 x|θ θ )) → p(θ θ |βt ); Számítjuk: L(D, f(x θ 0 |βt ) > p(θ θt |βt ), akkor θ t+1 = θ 0 , Ha p(θ

4

ellenkezo˝ esetben – a ∈ [0, 1] véletlen szám – ha θ 0 |βt )/p(θ θt |βt ) akkor θ t+1 = θ 0 a ≤ p(θ másképp θ t+1 = θ t

5

t=t+1

Goto 2

IV


Összefoglaló

Használható esetekben, ahol

11 van hibafüggvény;

Csató Lehel Ann. / G.A.

nem folytonos a paraméterhalmaz;

Bevezeto˝ Annealing G.A.

nincs gradiens információ – vagy nem használható;

G.P.

Például: VLSI-design. ∼

használata könnyu˝ – nem igényel sok kódolást vagy tanulmányozást; nem hatékony – a futási ido˝ nagyon nagy – egyszeru˝ feladatoknál is.

250/364

Genetikus algoritmusok Mesterséges Intelligencia

11 Csató Lehel Ann. / G.A. Bevezeto˝ Annealing G.A. G.P.

John R. Koza - Stanford University http://www.geneticprogramming.com/coursemainpage.html

251/364

0


I

A szimulált kifutés ˝ továbbfejlesztése:

11 Csató Lehel

1

Nem egyetlen paramétert optimizál; K θ(t) populáció ∀t{θ k }k=1

2

Definiálja a genetikus operátorokat. (t) (t+1) θ(t) ˝ keresztezodés cr(θ k , θl ) = θm (t+1) θ(t) mutáció m(θ k ) = θm az operátorok az egyedek szintjén muködnek. ˝

Ann. / G.A. Bevezeto˝ Annealing G.A. G.P.

Az iterációs séma hasonló K θ(0) {θ k }k=1

252/364

→

K θ(1) {θ k }k=1

→

···

→

) K θ(T {θ k }k=1


11 Csató Lehel

Genetikus algoritmusok muködése ˝ „természetes” szelekció; genetikus operátorok a paraméter-tér bejárására.


˝ Algoritmus: (minden t idopontban) 1 (t) K (t) (T ) θk }k=1 ⇔ fk = exp − L(D, f(·|θ θk )) {θ β Következo˝ generáció létrehozása:

253/364

(t)

1

Az [fk ]k „fitnessz” faktorral arányosan (t) (t) ˝ választunk szüloket: θl , θl

2

Bemásoljuk azokat a populációba vagy

3

alkalmazzuk a genetikus operátorokat: ˝ keresztezodés, mutáció;

II

G.A. Mesterséges Intelligencia

„Fitnessz”

„Fitnessz”-függvény

11

méri az egyedek megfelelését – jóságát

Csató Lehel

Fordítottan arányos az L(·) hibával 1 (T ) (t) K (t) θk )) θk }k=1 ⇔ fk = exp − L(D, f(·|θ {θ β


a cél, hogy minél több egyed legyen, melynek nagy a „fitnessz”-értéke; ˝ β - homérséklet-paraméter 1 2 3

254/364

a relatív érzékenységet modulálja; ˝ ˝ nagy homérséklet = különbségek nem jelentosek; ˝ kis homérséklet β & 0 – a leg-„fittebb” egyed sokkal jobb, mint bármely más;


Szelekció

Szelekció

11

garantálja a következo˝ populáció optimalitását;

Csató Lehel

csak a kiválasztott – szelektált – egyedek részei a következo˝ generációnak;

Ann. / G.A. Bevezeto˝ Annealing

véletlen, de súlyozott választás;

G.A. G.P.

Szelekciós algoritmus:

P

(t) k fk

1

Számoljuk ki: F(t) =

2

generáljuk a = rand(0, 1)

3

l=0,s=0 amíg s < a · F(t)

4

l=l+1 (t) s = s + fl 255/364

miért maradnak csak a jobb egyedek?


Operátorok

Operátorok

11

˝ keresztezodés és mutáció

˝ Keresztezodés

Csató Lehel

˝ „tulajdonságait” kombinálja; a szülok ˝ a gyerekek „közel” lesznek a szülokhöz;


˝ Keresztezodés „születnek” egyedek, melyek halmozzák a jó tulajdonságokat;

Mutáció szelekció nyomán csak a jó egyedek maradnak fent; ez a genetikus operátor biztosítja a változatosságot; olyan értékek is kiválasztódnak, melyek nem voltak a korábbi generációkban; Mutáció „radikális” változás, mely esetenként jobb eredményhez vezet; 256/364

I


Operátorok

II

Genetikus operátorok: – folyamatos paramétertér

11

5 0. 3

Csató Lehel

0.7

0.5 0.5

Ann. / G.A. 0.7


0.3

0

0.5 0.7

0.7

0.

5

0.3

0.3

mutacio keresztezodes

−5 −5

Mutáció: ha θ ∈ Rm ˝ Keresztezodés: 257/364

0

5

θ) def m(θ =θ+δ θ1 , θ 2 ) def θ1 + θ 2 ) /2 cr(θ = (θ

G.A.

III

˝ Keresztezodés / mutáció : ! heurisztikák ! 5

0.7

0.7

0.3

Csató Lehel

0.5

11

0.5

0.3

Ann. / G.A.

0.3

0.5

Bevezeto˝

0. 7


Operátorok

0.7

G.A.

0. 5

0.7

0.5

0.7

0.5

0.7

0.3 −5 −5

Heurisztika:

7

0.5

0.5

0.

0.3

keresztezodes

0

5

Nem mindig muködik; ˝

Jobb eredményeket remélünk, garancia nélkül. 258/364

0.7

0

G.P.

0. 3

Annealing


TSP

Genetikus algoritmusok definíciója;

11

⇔

I az operátorok

Numerikus esetek kevésbé érdekesek;

Csató Lehel Ann. / G.A. Bevezeto˝ Annealing G.A.

Példa: Utazóügynök (Travelling SalesPerson – TSP)

G.P.

Városokat bejárni úgy, hogy a megtett út minimális legyen. ˝ Egzakt megoldás: nagyon idoigényes; NP-teljes feladat. Genetikus algoritmus: nem garantálja a legrövidebb út megtalálását; azonban egy közel-optimális utat gyorsan megtalál; 259/364


11 Csató Lehel Ann. / G.A.

TSP

II 5

G.A. G.P.

7 4

8

3

Pl. [1, 2, 5, 3, 4, 6, 7, 8, 10, 9, 11, 12]

2

11 10 12

1

Bevezeto˝ Annealing

6

Kódolás: az utak egy permutációja.

Genetikus operátorok: Mutáció: 5

6

˝ Keresztezodés: 5

7

8

3 2

1

9

5

6

2

1

6

8

3

10

11 10

12

12 1

260/364

9

1

9

7 4

2

10

12

9

5

11

11

10

8

3 2

7

8

3

11

7 4

6 4

8

12

10 12

5

7

3 2

11

1

6 4

4

9

9

Genetikus programozás Mesterséges Intelligencia

a populáció egyedei programok;

11

programok egy függvényt implementálnak;

Csató Lehel

genetikus operátorok a programok terén értelmezettek;


program = függvény.

Annealing G.A. G.P.

+ /

sin

* x

* +

y x

−

+

sin y

exp

y x

1

sqr y

261/364

x

Genetikus Mesterséges Intelligencia

Összefoglaló

Genetikus algoritmusok

11

populációkkal operálnak;

Csató Lehel

szelekciós és reprodukciós operátorok használata;


genetikus operátorok gyorsítják a keresést; szükséges a program-/paraméter-tér ismerete.

Annealing G.A. G.P.

a „fitnessz”-érték irányadó ⇔ optimizálás; „Genetikus” Algoritmus általános optimum-keresési módszerek, „szomszédság”-ismerete elégséges; ha a fitnessz-függvény differenciálható, numerikus módszerek használata ajánlott; 262/364



12


Csató Lehel


NHk


Történelem Perceptron


Lin.szep Konv.Tétel


Matlab Összefoglaló


Admin ...



12 Csató Lehel NHk

... trívia


Történelem Perceptron Lin.szep Konv.Tétel

Laborgyakorlatok:


1


18%

2

Játékelmélet

10%

3


12%

4



sok%

ET look and disposition Mesterséges Intelligencia

12 Csató Lehel NHk Történelem Perceptron Lin.szep Konv.Tétel Matlab Összefoglaló

I

Robotika

„Twendy-One”, a „Wendy” robot 21.-edik századi reinkarnációja. A robot képes törékeny tárgyak hordozására valamint emberek segítésére a leülés illetve felállás muveleteiben. ˝ ˝ keresztül válaszol Érzékeloin az emberi érintésekre.

Képes egy szelet kenyér megfogására, ugyanakkor képes embereket kisegíteni az ágyukból. „Az elso˝ ennyire nagyfokú integrációval rendelkezo˝ robot.” – mondta Shigeki Sugano, a Waseda Egyetem tanára, a Twendy-One projekt ˝ vezetoje. pcWorld hír 265/364

ABCnews hír

Történeti áttekinto˝ Mesterséges Intelligencia

12 Csató Lehel NHk Történelem Perceptron Lin.szep Konv.Tétel Matlab

Ramon y Cajal

Összefoglaló

˝ 1894 − 1900 közötti idoszakban; idegrendszer vizsgálata; ˝ építoegység azonosítása: neuron;

266/364

idegsejt – mint az idegrendszer ˝ építoeleme

IdegSejt

Történeti áttekinto˝

I

Neuron


Ramon y Cajal Nobel díj 1906


The cerebellar cortex (a kitten cerebellum).

The letter A marks the Purkinje cells with dendritic ramifications.

http://nobelprize.org/medicine/articles/cajal/ 267/364


Idegsejt fényképe:


268/364

II

Neuron


III

Neuron



Neuron alkotóelemei Szóma (sejtmag) – az információ feldolgozása; Dendrit – az információ összegyujtése; ˝ Axon – az információ terjesztése; mi az információ? http://www.ship.edu/~cgboeree 269/364

http://en.wikipedia.org/wiki/Neuron


12 Csató Lehel NHk

x2

w2 w3

Perceptron

Konv.Tétel

Modell

„Mesterséges” Neuron x1 w1

Történelem

Lin.szep

IV

x3

PN i=1

w i xi

z

f(z)

y


wN xi – bemeneti értékek;

xN P Ahol:

wi – súlyok (dendritek); · · · – összegzo˝ (szóma);

f(z) – átalakító; – kapcsolatok (axonok); 270/364


V w


w

12

w w

Csató Lehel

w NHk

w

Perceptron

Konv.Tétel

w

w

Történelem

Lin.szep

Modell

w

X

Matlab

w

Összefoglaló

w w w w

aszinkron muködés; ˝ nagyon sok kapcsolat; ?hogyan? kreáljunk/töröljünk kapcsolatokat; 271/364

Y


VI

Modell


12 Csató Lehel

w NHk

w

w

Történelem

w

Perceptron Lin.szep

X

w

Konv.Tétel

w

Matlab

w

Összefoglaló

w

w

w

w w

szinkron – ciklusos – muködés; ˝ rétegek ⇒ korlátolt számú kapcsolat;

272/364

Y


Összefoglaló

Idegrendszer = információ-feldolgozó egység. ˝ Kérdések (nincsenek kelloen tisztázva):

12

Mi az információ, Hogyan történik a feldolgozás.

Csató Lehel NHk Történelem Perceptron Lin.szep Konv.Tétel Matlab

biológiai neuronok aszinkron-muködés ˝ uek: ˝ miért jó a mesterséges neuron szinkronizált jellege.

Összefoglaló

mesterséges neuronok egymáshoz kapcsolódása csekély: a biológiai rendszerek nagyságrendekkel több kapcsolatot kezelnek.

273/364

Perceptron Mesterséges Intelligencia

12 Csató Lehel NHk Történelem Perceptron Lin.szep

I

Egyszerusített ˝ természetes neuron-modell: x1 x0 = 1 w1 w0 = b x2 w2 x3 w3 PN z i=1

Konv.Tétel

wi x i

y

wN


xN Korai neuron-modell: McCullogh-Pitts ∼ 1958; xi és y értékek binárisak; ˝ Aktivációs függvény a lépcsofüggvény: −1 ha z < 0 H(z) = +1 ha z ≥ 0 274/364


II

Perceptron

12

ON/OFF neuron állapotok A neuronok vagy aktívak vagy nem, mint a bináris logikában

Csató Lehel

rezolució-szeru˝ muködés ˝

NHk Történelem Perceptron

x(n) , y (n) )-en hiba történt, akkor Tanulási szabály: ha (x

Lin.szep Konv.Tétel Matlab Összefoglaló

(n)

wi (t + 1) W wi (t) + xi y(n) ahol wij súly, x (n) bemeneti minta, y(n) a minta osztálya.

Konvergencia-tétel: Ha a tanulási minták elválaszthatóak,

def

akkor a perceptron konvergál. 275/364

(n) (n) N x , y ) n=1 (x (osztályozási feladat)

Elválaszthatóság

I


12 Csató Lehel NHk Történelem Perceptron

kék osztály kódja legyen +1; piros osztály kódja legyen −1;

Lin.szep Konv.Tétel Matlab Összefoglaló

wT x + b Szeparáló hipersík w, b} vektorral illetve valós szám által meghatározott a {w felület, ha wT xi + b > 0 wT xi + b < 0 276/364

∀i

; yi > 0.

∀i

; yi < 0.

Elválaszthatóság

II



wT x + b Szeparáló hipersík: yi w T x i + b > 0

∀i = 1, N.

ahol x i - i-edik mintavektor és yi az ahhoz tartozó osztály kódja. vissza 277/364


12 Csató Lehel

Konvergenciatétel

Konvergenciatétel A tanulási szabály alkalmazásával a perceptron véges ido˝ alatt konvergál.

NHk Történelem Perceptron Lin.szep Konv.Tétel Matlab Összefoglaló

Biz: Módszer: találjunk – felso˝ és alsó – korlátot a lépések számának. 1 Újradefiniáljuk a bemeneti adatokat: xi , 1]T ∈ Rd+1 x^i def = [x x i def = yix^i

278/364

⇒

w, b]T ∈ Rd+1 w def = [w

Konvergenciatétel Mesterséges Intelligencia

II

2 Újradefiniált feladat Találjunk egy (1) w ∈ Rd+1 értéket úgy, hogy

12 Csató Lehel

∀i ; w T x i > 0

NHk Történelem

minden xi -re (már tartalmazzák a címkéket is).

Perceptron Lin.szep Konv.Tétel

3 Tanítási szabály Ha hiba történt, akkor módosítjuk a perceptron súlyait: (n) wi (t + 1) W wi (t) + xi


(rekurzívan visszafejtve: w (t + 1) = x 1 + · · · + x t ) x(n) < 0. 4 Hiba ⇔ w T (t)x (1) Amennyiben van egy érték, akkor nagyon sok elfogadható érték létezik. 279/364

Konvergenciatétel Mesterséges Intelligencia

III

5 Feltételezzük, hogy létezik szeparáló hipersík:

12

∃ w 0 ∈ Rd+1 ∀i ; w T0 x (n) ≥ α > 0

Csató Lehel NHk

6 Vizsgáljuk a w T0 w (t + 1) skaláris szorzatot:

Történelem Perceptron Lin.szep

wT0 w(t + 1) = wT0 x1 + · · · + wT0 xt ≥ tα

Konv.Tétel Matlab Összefoglaló

2 ˝ 7 Cauchy-Schwartz egyenlotlenség kak2 kbk2 ≥ aT b alkalmazzuk: 2 w0 k2 kw w(t + 1)k2 ≥ w T0 w (t) ≥ (tα)2 kw vagyis w(t + 1)k2 ≥ kw 280/364

(tα)2 w 0 k2 kw

Konvergenciatétel

IV


Másrészt - minden tanuló lépésnél:

12

8 w (t + 1) = w (t) + x (t) , tehát:

Csató Lehel

w(t + 1)k2 = kw w(t) + x (t) k2 kw

NHk

w(t)k2 + 2w w(t)x x(t) + kx x(t) k2 = kw


w(t)k2 + kx x(t) k2 = tβ2 ≤ kw


(n) 2 x k ; n = 1..N Ahol β2 = max kx ˝ ˝ kiszámítható a 9 Van tehát két egyenlotlenség, melybol t maximális értéke: tmax x ≤ Tehát a perceptron konvergál 281/364

w0 k2 β2 kw α2

Matlab Demó Mesterséges Intelligencia

Kódoljuk a perceptron algoritmust:

12

generáljuk az adatokat. Specifikáljuk:

Csató Lehel

az adatok dimenzióját, számát; az elválasztó hipersíkot; generáljuk a bemeneti mintákat illetve az azokhoz tartozó kimeneti osztálykódokat.

NHk Történelem Perceptron Lin.szep Konv.Tétel Matlab Összefoglaló

Transzformálunk a konvergenciatétel szerint. Inicializáljuk a perceptront zeró értékekkel. Futtatjuk az algoritmust: mérjük a hibajavító lépéseket; mérjük a ciklusok számát. 282/364

I



Matlab kód: % ADATOK parameterei dim = 9; N = 200; % az elvalaszto hipersik w_0 = [1;3; 4;1; 2;6;5; 5; 3]; 6 b = 2; % adatgeneralas X = sign(rand(N,dim) 0.5); % cimkek generalasa Y = sign(X*w_0 + b); 11 % hatarmintak szurese idx = find(~Y); idx = setdiff([1:N],idx); X = X(idx,:); Y=Y(idx); N = length(Y); 1

283/364

II



%% Perceptron tanulas %%%%%% % 1 mintak atalakitasa X = [ X ones(N,1)]; % 2 5 XX= diag(Y) * X; %% Tanulas lokalis valtozok beallitasa w = zeros(dim+1,1); Term = 0; steps = 0; sweeps = 0;

284/364

III


12

1

while ~Term; Term = 1;

Csató Lehel NHk Történelem Perceptron Lin.szep Konv.Tétel Matlab Összefoglaló

for ii=1:N; if XX(ii,:) * w <= 0 6 w = w + XX(ii,:)'; steps = steps + 1; fprintf('%d:',steps); % megj. fprintf('%4d',w);fprintf('\n'); Term = 0; 11 end; end; sweeps = sweeps +1; end;

285/364

IV


12 Csató Lehel NHk Történelem Perceptron Lin.szep

Kiíratjuk a statisztikákat: 1

fprintf('\nTeljes bejarasok szama: %d\n',sweeps); fprintf('Eredmeny: '); fprintf('%4d ',w); fprintf('\n'); fprintf('Kezdo hipersik:'); fprintf('%4d',[w_0;b]); fprintf('\n');


286/364

V

Összefoglaló Mesterséges Intelligencia

’60-as évek tanulási paradigmája;

12

Logikai függvényeket keres – bemenet és kimenet binárisak;

Csató Lehel NHk

Cél a gondolkodás modellezése


Nem tudja szeparálni az XOR muvelet ˝ kimeneteit (Minsky és Papert ’62)


Feladat: találjunk konfigurációt, mely az XOR-t helyesen osztályozza.

b1 w11 w x1 12 w21 w22

x2 287/364

h1 b2

h2

v1 v2

b3

y


Kitekinto˝

A perceptron egy black-box – fekete doboz – módszer;

12 Csató Lehel

˝ vett feladatok megoldására lehet Valós életbol használni:

NHk Történelem Perceptron

1

Lin.szep Konv.Tétel

2


3 4

Gyujtünk ˝ adatokat, Építünk modellt, Tanítjuk a modellt, Paraméterek = modell kiválasztása.

˝ A késobbi neurális háló modellek jó példái a fenti automatizált feladatmegoldási paradigmának. A neurális hálózat modelleket nagyon sokáig – ma is – használ(j)ták modellezésre. 288/364



13


Csató Lehel


M.L.P


B.P.

Játékok modellezése Bizonytalanság kezelése Fuzzy rendszerek Grafikus modellek Tanuló rendszerek Szimulált kifutés, ˝ Genetikus algoritmusok A perceptron modell ˝ Neurális hálók, önszervezodés Gépi tanulás 289/364

Admin ...



13 Csató Lehel M.L.P

... trívia


B.P.

Laborgyakorlatok: 1


18%

2

Játékelmélet

10%

3


12%

4



sok%

Robotasszisztens a Stanfordról

STAIR


13 Csató Lehel M.L.P B.P.

˝ A robotok programozásánál nem volt lehetséges speciális eloprogramozás nélkül összeszedni a mosatlant vagy megetetni a cicákat. ˝ Erre általában két kamerát A robotok hagyományosan 3D-s modellt készítenek környezetükrol. ˝ és számítási kapacitás-igényes munkával, az adott tárgy pontjainak használtak, a távolságokat ido– tömege alapján határozták meg. A STAIR alternatív megoldást kínál: pontok sokasága helyett az algoritmus az adott tárgy megfogható részének a középpontját azonosítja. Élek hosszúságát számolja ki, majd az eredményt az adatbázisban levo˝ statisztikailag hasonló tárgyakkal veti össze. A szoftver ezek alapján hozza létre a háromdimenziós modelleket; lényegesen gyorsabban és kevesebb munkával, mint a régi megközelítésben.

Stanford STAIR 291/364

agens.ai

Többrétegu˝ Hálók

I


13

Az információ – számok – a ˝ a bemeneti X rétegbol kimeneti Y réteg fele halad.

Csató Lehel M.L.P

X

Egy mintára kiszámítjuk a kimeneti értéket, minden neuron értékét kiszámítva.

B.P.

Feltételezzük, hogy minden – adat és súly – folytonos.

MLP NEM Bayes-háló A neurális hálók kapcsolatai kommunikációt, a ˝ Bayes-hálók kapcsolatai függoséget jelentenek. 292/364

Y

Többrétegu˝ Hálók Mesterséges Intelligencia

x1

13

x2

x3

x4

Csató Lehel

W

II „Formálisan”: A neuronháló csúcsai az információt feldolgozzák.

M.L.P

xbe ) yki def = fakt (x

B.P.

h1

h2

h3

h4

h5

V

Az élek: a csúcsok közötti kapcsolatok. X (j) (i) xbe 0 def wij xki = j

A fenti lépések ˝ ismétlodnek.

Y MI az információ? 293/364

definíció szerint x ki

∈ Rk


x1

13

x2

x3

x4

Csató Lehel

W


M.L.P


B.P.

h1

h2

h3

h4

h5

V





∈ Rk


x1

13

x2

x3

x4

Csató Lehel

W


M.L.P


B.P.

h1

h2

h3

h4

h5

V





∈ Rk


x1

13

x2

x3

x4

Csató Lehel

W


M.L.P


B.P.

h1

h2

h3

h4

h5

V





∈ Rk


13

III

˝ A bemen P o aktivitás: yj = i wij xi + bj .

1 f(z − b)

Csató Lehel M.L.P B.P.

A perceptron tanulási algoritmushoz hasonlóan: ˝ elobb: x i0 = [x1 , . . . , xd , 1]T ⇒ w ·j0 = [w1 , . . . , wd , b]T

0

b 1 2 f(z) = sgn(z)

Univerzális approximáció A következo˝ rendszer: w, b ) = fM (z|w

M X

wm f(z − bm )

m=1

univerzális approximátor, azaz ∀δ > 0 ∀g ∈ L2 (Rd ) w, b )kL2 ≤ δ ∃M, w , b ú.h. kg − fM (z|w 294/364


IV

Univerzális approximátor: bizonyítás a szint-halmazokon alapszik (lásd Lebesgue integrálás).

13 Csató Lehel

Vizualizálás: Mintavételezés a

M.L.P B.P.

5

10

15

20

w és b értékekbol ˝

MATLAB kód: %Generatorfuggvenyek f = inline('((x>0)0.5).*2'); g = inline('2./(1+exp(2*x))1'); % komponensek szama mComp = 10; % fv.nyek szama nF = 6; % X tengely xx=10:0.05:10; xd=repmat(xx,[mComp,1]); % plot init clf; hf = subplot(1,2,1); set(gca, ... 'Position',[0.05 0.1 0.42 0.85],... 'YTick',[],'XTick',[]); hold on; box on; ylim([25,25]); set(gca,... 'Position',[0.55 0.1 0.42 0.85],... 'YTick',[],'XTick',[]); hold on; box on; ylim([25,25]);

295/364

hg = subplot(1,2,2); % megjelenitesi stilus style = {'b','r','k','m','c','g'}; % F.v.nyek generalasa 5 for ii=1:nF; % egyutthatok ss=(2*rand(mComp,1) 1)*6; ww=(2*rand(mComp,1) 1)*6; bb=(2*rand(mComp,1) 1)*10;

10

bd=diag(bb)*ones(size(xd)); y_f = sum(diag(ww) * f(diag(ss)*xd + bd)); y_g = sum(diag(ww) * g(diag(ss)*xd + bd)); % megjelenites 15 plot(hf,xx,y_f,style{ii},'LineWidth',3); plot(hg,xx,y_g,style{ii},'LineWidth',3); end; % nyomtatas print depsc2 rand_fn.eps

Aktivációs függvények Mesterséges Intelligencia

13

1

1 Aktivacios fugveny F. Derivaltja

0.6

0.5

Aktivacios fuggveny F. Derivaltja

0.2

Csató Lehel 0

−0.2

M.L.P B.P.

−0.5

−1 −10

−0.6

−5

0

5

10

−1 −10

−5

0

Véletlen függvények a függvényosztályokból:

296/364

5

10

Backpropagation Mesterséges Intelligencia

I

Nem bináris függvényt közelít.

13

A bemeneti/kimeneti értékek folytonosak.

Csató Lehel

fNN : Rd → R

M.L.P B.P.

Folytonos esetben használható a négyzetes hibafüggvény: wNN ) = E(w

N 2 1X xn ) yn − fNN (x 2 n=1

ahol w NN a neuronháló paraméterei. Differenciálható akt. függvényeknél a gradiens szabály alkalmazható ⇒ backpropagation szabály. 297/364


II

Error back-propagation ⇔ négyzetes hiba visszaterjesztése

13 Csató Lehel

Egy adott tanulási halmazhoz és egy w NN neurális hálóhoz rendelt négyzetes hiba

M.L.P B.P.

N 2 1X xn ) wNN ) = yn − fNN (x E(w 2 n=1

akkor zéró, ha a neurális háló minden adatot jól közelít. (0)

Egy adott w NN hálónál jobban közelíto˝ hálót kapunk ha egy kis lépést végzünk a negatív gradiens irányába. 298/364


III

„Képletesen”

13 (t+1) (t) w NN ⇐ w NN − α

Csató Lehel

w(t) ∂E(w NN )

M.L.P

w(t) ∂w NN

(t) w(t) ⇐ wNN − α ∂w E(w NN )

B.P.

ahol α – tanulási együttható; – a hiba gradiense (vektorok!).

w(t) ∂w E(w NN )

Kérdés: milyen α ˝ értékek megfeleloek? Kis lépések ⇒ hosszú konvergencia. Nagy lépések ⇒ nem konvergál. 299/364

Local optimum

w2 w1

w0


IV

Differenciálás szabálya:

13

∂f(g1 (wi ), . . . , gk (wi )) X ∂f(g1 , . . . , gk ) ∂gj = ∂wi ∂gj ∂wi g

Csató Lehel

j

M.L.P B.P.

Neuronháló függvénye: y = · · · · · · , fj

X

h1 wi1 !

hi wij

! ,···

h2 wi2

fj (

wiN

i

hN

∂wij E(·) =

X j

300/364

∂fj E(·) ∂wij fj

X i

! wij hi

P i

hi wij )


(folyt)

13 Csató Lehel

V

X N ∂wij E(·) = ∂fj E(· · · ) ∂wij fj w h n=1 ij i X N = hi fj0 n=1 wij hi ∂fj E(·)

M.L.P B.P.

A bemeneti érték és a kimeneti hiba szorzódnak. P És ∂fj E(·) = ∂fj E . . . , gk v f , . . . jk j j Lánc-deriválás szerint: X ∂fj E(·) = vjk ∂gk E(·)gk0 (·)

vj1 fj (·)

...

k

vjK Az egyéni hibák súlyozottan összeadódnak. 301/364


13 Csató Lehel M.L.P B.P.

VI

(folyt) ˝ terjed, a tanulás Tehát: amíg a muködésnél ˝ a jel elore ˝ a háló folyamán a hiba visszafele; a kimeneti réteg felol bemenete felé „terjed”. Hiba-visszaterjesztés (BP) P

·

=⇒ ˝ alakulnak; azaz az osztópontok összegzové P

·

=⇒ azaz az összegzo˝ csomópontok meg hiba-elosztóvá. 302/364

Backpropagation

Összefoglaló


M.L.P

A BP algoritmus a gradiens szabály alkalmazása a neuronhálókra;

B.P.

Az alap a négyzetes hiba;

13 Csató Lehel

Egyszeruen ˝ implementálható;

Local optimum

w2 w1

Nagyon sok alkalmazás; Hátrányok: Mivel gradiens, lassú ⇒ nagyon sokáig tarthat a tanulás. Más módszerekkel állítani be a súlyokat: Newton, Konjugált gradiens. Nincs a becsült mennyiségre konfidencia ⇒ Rosenbrock valószínuségi ˝ módszerek szükségesek. 303/364

w0


13

` ´2 Feladat: keressük a h(x1 , x2 ) = 100 x2 − x21 + (1 − x1 )2 függvény minimumát a gradiens szabály használatával.

Csató Lehel M.L.P 2

B.P.

Példa I

∂1 h(·) = 400(x2 − x1 )x1 + 2(x1 − 1) 2

∂2 h(·) = 200(x2 − x1 ) A második egyenlet ↔ x2 = x1 Behelyettesítve x1 = 1.

Induljunk a (−1, 1) pontból.

304/364


Példa II

BP szabály = gradiens – általában nagyon lassú.

13

Rosenbrock fv. optimizálás

Csató Lehel

2

Gradient Descent Scaled Conjugate Gradients Quasi Newton Conjugate Gradients

M.L.P B.P.

1.5

1

0.5

0

−0.5 −1.5 305/364

−1

−0.5

0

0.5

1

1.5

M.L.P. Mesterséges Intelligencia

Összefoglaló

Neurális hálók fekete-doboz módszerek:

13

1

minden feladat megoldására potenciálisan alkalmazhatóak;

2

jó eredményekhez (majdnem mindig) kell egy kis igazítás a módszeren;

3

siker függ a tapasztalattól;7

Csató Lehel M.L.P B.P.

BackPropagation = gradiens tanulás

7 306/364

1

általában nagyon lassú;

2

fejlett módszerek: konjugált gradiens módszerek, quasi-Newton, etc. gyorsítanak a konvergencián.

3

lokális optimumok elkerülésére többszálú optimizálás, ˝ pl. mintavételezéssel kijelölni a kezdoértékeket.

Érdemes tehát tovább tanulni.



14


Csató Lehel


Hebb


Self. Org. Hebb-hálók


S.O.M.


Admin ...



14 Csató Lehel Hebb

... trívia



Laborgyakorlatok:

S.O.M. 1


18%

2

Játékelmélet

10%

3


12%

4



sok%

D.O. Hebb

I


D.O. Hebb The organization of behavior

14 Csató Lehel Hebb Self. Org. Hebb-hálók S.O.M.

A neurális moduláció alapelvei: ˝ Két neuron között a kapcsolat erossége arányos a neuronok pre-, illetve poszt-szinaptikus tevékenységével; Azon neuron–csoportok, melyek általában egyszerre tüzelnek, egy egységet alkotnak; (modularitás) A gondolkodás folyamata ezen sejt-csoportok szekvenciális aktivációja; 309/364

D.O. Hebb Mesterséges Intelligencia


II

Organization of Behavior: When an axon of cell A is near enough to excite B and repeatedly or persistently takes part in firing it, some growth process or metabolic change takes place in one or both cells such that A’s efficiency, as one of the cells firing B, is increased. (p. 62)

Self. Org. Hebb-hálók S.O.M.

Neuroscience ⇔ „Hebb synapse” „Hebb szabály”

∆wij = αai aj Ahol ai , aj – neuronok aktivitásai; ˝ wij – az összeköto˝ szinapszis erossége; α – tanulási együttható. 310/364

Önszervezo˝ Hálók Mesterséges Intelligencia

Haykin: Neural Networks A comprehensive foundation, IEEE press, 1994


Cél:


Struktúrák felfedezése az adatokban;

S.O.M.

„Felügyelet” nélküli muködés ˝ ⇒ önszervezés. Tanulási szabályok: lokális szabályok, melyek – sok neuronra alkalmazva – egy globális függvényt határoznak meg. Alapja (Turing 1952): „Global order can arise from local interactions.” 311/364

I


II

Önszervezo˝ rendszerek alapelvei (von der Malsburg):

14

˝ oek ˝ A szinapszisok önmegerosít

Csató Lehel

A pre-, illetve posztszinaptikus neuronok egyideju˝ aktivációja ˝ erosíti a szinapszist (lásd Hebb).

Hebb Self. Org. Hebb-hálók S.O.M.

˝ A szinapszisok versengenek az eroforrásokért ˝ A legerosebb szinapszis biztos, hogy túléli. Ez a többi rovására történik (winner-takes-all).

A szinapszisok változásai koordináltak Egy szinapszis nem kódol robusztusan, ezért egy régió neuronjai – majdnem – azonos bemenet–kimenet kapcsolatot kódolnak. 312/364


Önszervezo˝ tanulás

14

III ≡

Struktúra-felismerés

˝ A vizuális rendszer önszervezo:

Csató Lehel

˝ fejlodésének elején csak a felismerésre való képesség van jelen; a muködés ˝ során egyes kép-csoportok – klaszterek – együttesen lesznek ábrázolva;

Hebb Self. Org. Hebb-hálók

A származtatott fogalmak ábrázolása a hierarchia ˝ szintjén történik. egy felsobb

S.O.M.

Példa: neurális rendszer pixelcsoportokat keres.

Y

X 313/364

némely pixelcsoport gyakori; ezen csoportok rözgülnek a rendszerben. a felso˝ szinten a rendszer címkézést végez.

Hebb-féle tanulás Mesterséges Intelligencia

I

Hebb tanulás - auto-asszociatív rendszerek

14 A rendszer bemenete egy minta - nincs kimeneti jel.

Csató Lehel

A „kimeneten” vagy:

Hebb Self. Org.

az eredeti mintát; vagy egy csoportosítást, „surített” ˝ ábrázolást

Hebb-hálók S.O.M.

szeretnénk visszakapni. csoportosításkor a kimeneti neuronok versengenek: X y ^j = xi wij i

1 yl = 0 314/364

l=k l 6= k

ahol k = argmax y ^j j


1 yl = 0

14 Csató Lehel

II

l=k l 6= k


Hebb Self. Org.

Végleges kimeneti érték az argmax muvelet ˝ után.

Hebb-hálók

Versengés a bemeneti mintákért.

S.O.M.

y1

y2

y3

y4

y5

W x1 x2 x3 x4 x5 x6 x7 x8 x9 v1 v2 v3 v4 v5 v6 v7 v8 v9 315/364

Feltételezve egy kezdo˝ W – véletlen – súlyvektort, a v minta bemutatása után csak a w·4 súlyok változnak a kompetitív tanulás során.


1 yl = 0

14 Csató Lehel

II

l=k l 6= k


Hebb Self. Org.

Végleges kimeneti érték az argmax muvelet ˝ után.

Hebb-hálók

Versengés a bemeneti mintákért.

S.O.M.

y1

y2

y3

y4

y5

W x1 x2 x3 x4 x5 x6 x7 x8 x9 v1 v2 v3 v4 v5 v6 v7 v8 v9 315/364

Feltételezve egy kezdo˝ W – véletlen – súlyvektort, a v minta bemutatása után csak a w·4 súlyok változnak a kompetitív tanulás során.


III

∆wij = αxi yj

14 Csató Lehel

minden yk neuron attraktorként muködik. ˝

Hebb Self. Org.

Y1

Y2

˝ alakulnak ki receptív mezok

Hebb-hálók

α → 0 tanulási mód, pl.

S.O.M.

K αt = t az asszociatív háló konvergál (lásd).

Y3

Y5

Y4 X2 X1

ami nincs: kapcsolatok a kimeneti neuronok között: Kohonen-hálók 316/364

Kohonen hálók Mesterséges Intelligencia

14 Csató Lehel Hebb Self. Org. Hebb-hálók S.O.M.

I

Teuvo Kohonen Since the 1960’s, ∼ introduced several new concepts to neural computing: theories of distributed associative memory and optimal associative mappings, the self-organizing feature maps (SOMs), the learning vector quantization (LVQ), . . . the Adaptive-Subspace SOM (ASSOM) in which invariant-feature filters emerge . . . A new SOM architecture WEBSOM has been developed in his laboratory for exploratory textual data mining. http://websom.hut.fi/websom/

317/364

Wikipedia link


II

˝ Jellemzok:

14 Csató Lehel

kétrétegu˝ háló, egy bemeneti és egy kimeneti réteggel;

Hebb Self. Org.

˝ (mint elobb)

Hebb-hálók S.O.M.

kompetitív háló: csak egy neuron lesz aktív; ˝ (mint elobb)

a kimeneti rétegen topológia van értelmezve (ÚJ) 318/364


Topológia

Topológia – szomszédságot jelent


segít a tanulásban:

Self. Org.

a szomszédok is tanulnak –

Hebb-hálók

n14

n24

n34

n44

n13

n23

n33

n43

n12

n22

n32

n42

n11

n21

n31

n41

kevésbé ...

S.O.M.

értelmezheto˝ eredmény: a szomszédok aktivitása is aktivitása alapján pontosabb rekonstrukció

a kimeneti nij neuronok ˝ megcímkézhetoek: Kohonen: ... fonéma annotáció 319/364


Tanulás I

Az algoritmus iteratív:

14

1

˝ minták egyenként; a t-edik idopontban legyen x t

2

kiszámtítjuk a kimeneti neuronok aktivitását: X yj = wij xi (t) = W x (t)

Csató Lehel Hebb Self. Org. Hebb-hálók

i

S.O.M.

3

megkeressük a nyertes kimeneti neuront: k def = argmax yj j

4

Az összes szomszédos neuron súlyát módosítjuk: wij (t + 1) = wij (t) + α η(j, k)xi (t) Normáljuk a súlyokat w·j ⇐ w·j /kw·j k

5 320/364

GOTO 1

Kohonen hálók

Tanulás II



Szavakban: a nyertes neuron „aktivizálódik”;

· ·

A nyertes neuront és szomszédait „közelebb” hozzuk a bemenethez;


Mindegyik neuron specializálódik a mintákra: arra lesz a legnagyobb a kimenete;

321/364

· ·

· · · ·

·

· ·

·

· · · ·

Kohonen hálók

Tanulás II




xt · ·




321/364

· ·

· · · ·

·

· ·

·

· · · ·

Kohonen hálók

Tanulás II




xt · ·




321/364

· ·

· · · ·

·

· ·

·

· · · ·

Kohonen hálók

Tanulás III


14

xt

Csató Lehel

· ·

Hebb Self. Org.

·

Hebb-hálók

· · ·

· · ·

·

·

·

S.O.M.

·

· ·

·

Eredmény: a neuronok elhelyezkedését a bemeneti minták sur ˝ uségfüggvénye ˝ határozza meg – több neuron kerül a sur ˝ ubb ˝ régiókba. 322/364

Kohonen hálók

Tanulás III


14

xt

Csató Lehel

· ·

Hebb Self. Org.

·

Hebb-hálók

· · ·

· · ·

·

·

·

S.O.M.

·

· ·

·

Eredmény: a neuronok elhelyezkedését a bemeneti minták sur ˝ uségfüggvénye ˝ határozza meg – több neuron kerül a sur ˝ ubb ˝ régiókba. 322/364

Önszervezo˝ rendszerek Mesterséges Intelligencia

Összefoglaló

Az adatokhoz nincs kimeneti érték rendelve;

14 Csató Lehel

A rendszer általában az adatok egy csoportosítását valósítja meg;

Hebb Self. Org. Hebb-hálók S.O.M.

Ez implicit módon a bemeneti adatok terének a felosztását jelenti;

Zajszurés/S ˝ urítés: ˝ a teljes bemeneti adatok helyett a hozzá tartozó osztály kódját küldjük.

323/364

Példa Mesterséges Intelligencia

14

–

Térképészgép

Walter Bischof, Jun Zhou (U. Alberta) és Terry Caelli (Australian N.U) a kartográfiát (részben) automatizáló ˝ programmal álltak elo.

Csató Lehel Hebb Self. Org. Hebb-hálók S.O.M.

˝ tanulja, A program embertol miként fedezzen fel és azonosítson légi felvételeken korábban nem szereplo˝ vagy megváltozott elemeket: utakat, vasutakat, épületeket.

Ágens portál

Walter Bischof projektek

Muködése: ˝ Egyre többet tud meg – „okosabb” lesz. Kello˝ mennyiségu˝ gyakorlás után az operátor rábízza a munkát. Bayes-féle következtetést használ: korábbi mérések alapján végez új becsléseket. A legjobbakból állapítja meg az adott országút soron következo˝ pontjait, és ezt mindaddig folytatja, amíg az új elemek pozíciója megfelel az elvárásoknak. 324/364



15


Csató Lehel


Gépi Tanulás


Adatmodellezés Rejtett változók


Becslések


ML

Fuzzy rendszerek

MAP Bayes

Grafikus modellek

Grafikus modellek

Tanuló rendszerek Szimulált kifutés, ˝ Genetikus algoritmusok A perceptron modell ˝ Neurális hálók, önszervezodés Gépi tanulás 325/364

Admin ...



15 Csató Lehel Gépi Tanulás

... trívia



Laborgyakorlatok:

Becslések ML

1


18%

2

Játékelmélet

10%

3


12%

4


MAP Bayes

Grafikus modellek


sok%

Példa Mesterséges Intelligencia

15 Csató Lehel Gépi Tanulás Adatmodellezés Rejtett változók Becslések

Ágensek filmvásznon

A Massive céggel a Gyurük ˝ Ura trilógiában találkozhattunk 2001-ben.

Az összes csatajelenet az o˝ programjukkal készült. Nem véletlen, hogy a tavalyi (2005) King Kong-ban statiszták helyett a Massive ágenseit használták.

ML MAP Bayes

Ágens portál

Grafikus modellek

Aitia 327/364

Walter Bischof projektek

Hangya-kolónia szimuláció egy kedvelt M.I. téma. A „buta” hangya-ágensek feromon nyomokat hagynak maguk után; ezek alapján mozognak. Nincs ˝ globális információ a környezetrol: csak a feromon-nyomot követik. A kolónia intelligens viselkedést mutat: megtalálja a legrövidebb utat a fészek és az élelemforrás között.

Gépi tanulás Mesterséges Intelligencia

Történelmi háttér / Motiváció:

15 Csató Lehel

nagyon nagy mennyiségu˝ adat, melyet szeretnénk automatikusan feldolgozni;

Gépi Tanulás Adatmodellezés Rejtett változók Becslések ML

A matematikai modellek általánosak – nem egy adott feladatra vannak kiélezve,

MAP Bayes

Grafikus modellek

Szükség van esetenkénti tanulmányozására egy-egy feladattípusnak ⇒ „tudomány–ág”, mely a modelleket a feladatokhoz „idomítja”. 328/364

Gépi tanulás Mesterséges Intelligencia

15 Csató Lehel

Meghatározás

Gépi tanulás Módszerek – statisztikai, valószínuségi ˝ – gyujteménye ˝ valós feladatok megoldására.

Gépi Tanulás Adatmodellezés

Például:

Rejtett változók

Zajszurés: ˝ (nem–)lineáris regresszió és (nem–)normális zajt feltételezve;

Becslések ML MAP

Osztályozás: bináris, több–osztályos, illetve

Bayes

Grafikus modellek

Részlegesen címkézett adatokra; Klaszterezés – adatok csoportosítása, Függvényinverzió, Sur ˝ uségbecslés, ˝ „Kakukktojások” felfedezése – novelty detection. Szükséges az adatok modellezése.

329/364

Gépi tanulás

T. Mitchell: Machine Learning (ML), textbook


15 Csató Lehel Gépi Tanulás Adatmodellezés Rejtett változók

Mitchell

. . . is concerned with the question of how to construct programs that automatically improve with experience. In recent years (1997) successful ML algorithms have been developed in data-mining – fraud detection,

Becslések ML

filtering for user’s preferences,

MAP Bayes

vehicles that learn to drive on highways;

Grafikus modellek

advances in the theory and algorithms that form the foundations of tis field.

Thomas Mitchell

Tanuló rendszer olyan számítógépes program, melyek képességei a muködés ˝ során javulnak. 330/364

Adatmodellezés Mesterséges Intelligencia

x) f(x

15

Megfigyelés xi , yi ) (x

Csató Lehel Gépi Tanulás

x1 , y1 ) (x x2 , y2 ) (x ·· · x1 , y1 ) (x

Adatmodellezés Rejtett változók Becslések ML MAP Bayes

Feltételezzük, hogy: „Valahol”: létezik a t = f(x) függvény, mely generál adatokat;

Grafikus modellek

x)-et A megfigyelt értékek zajosak: nem y = f(x kapunk, hanem például: yn = t n + additív zaj yn = h(tn , )

h módosító függvény

Feladat: találjuk meg az y = f(x) függvényt. 331/364

Rejtett változós modellek Mesterséges Intelligencia

^ x) f(x

15

Inferencia

f∈F


I x1 , y1 ) (x x2 , y2 ) (x ·· · x1 , y1 ) (x

Adatmodellezés Rejtett változók Becslések ML MAP

Szükséges: Adatok halmaza – megfigyelés során gyujtjük. ˝

Bayes

Függvény osztály feltételezése. Lehet:

Grafikus modellek

K-ad fokú polinomok, Fourier polinomok, Wavelet-ek;

A megfigyelési folyamat ismerete – a zaj kódolása; ˝ függvény kiválasztására. Algoritmus a legmegfelelobb 332/364


II

Adottak:

15

x1 , y1 ), . . . , (x xN , yN )}. Adathalmaz D = {(x Függvényosztály (feltételezzük, hogy a megoldász ˝ megfelelo): w ∈ Rd , b ∈ R (1) F = w T x + b|w

Csató Lehel Gépi Tanulás Adatmodellezés Rejtett változók Becslések

K K X X (2) F = a0 + ak sin(2πkx) + bk cos(2πkx)

ML MAP Bayes

k=1

Grafikus modellek

a, b ∈ R , a0 ∈ R |a K

k=1

A megfigyelési folyamat egy modellje: xn ) + with ∼ N(0, σ2 ). yn = f(x 333/364


III

Általánosan:

15

1

x1 , y1 ), . . . , (x xN , yN )}. Adatok: D = {(x

2

Függvényosztály:


x, θ )|θ θ ∈ Rp F = f(x


Grafikus modellek 3

Megfigyelés – definiáljuk a hibafüggvényt: xn , θ )) L (yn , f(x Gauss-zaj esetén: xn , θ )) = (yn − f(x xn , θ ))2 . L(yn , f(x

334/364

Bevezeto˝

Paraméterbecslés Mesterséges Intelligencia


Paraméterbecslés Találjuk meg a θ paraméter-vektor optimális értékét. Optimalitás: θ ∗ = arg min L(D, θ ) θ ∈Ω


ahol

Becslések

Ω a paraméterek értelmezési tartománya. L(D, θ ) az adatokhoz rendelt hibafüggvény.

ML MAP Bayes

Grafikus modellek

Példa a hibafüggvényre Független megfigyelések esetén: N X xn , θ )) L(D, θ ) = L(yn , f(x n=1 335/364

miért független?

Paraméterbecslés Mesterséges Intelligencia

15

M.L.

L(D, θ ) – (log)likelihood függvény. M.L. = maximum likelihood értéku˝ θ :


θ∗ = arg min L(D, θ)

Adatmodellezés

θ ∈Ω

Rejtett változók Becslések ML

Példa – legkisebb négyzetes hibával történo˝ becslés:

MAP Bayes

Grafikus modellek

L(D, θ ) = θ ∗ = arg min

θ ∈Ω

N X n=1 N X

xn , θ ))2 (yn − f(x xn , θ ))2 (yn − f(x

n=1

Hátrány: Túl pontos illeszkedés – over-fitting. 336/364

M.L. becslés

Over-fitting


15

Training set Poly 4 Poly 3 Test set

10

Csató Lehel Gépi Tanulás Adatmodellezés Rejtett változók

5

Becslések ML MAP Bayes

Grafikus modellek

0

−5 −10

337/364

−5

0

5

10

Maximum a–posteriori becslés Mesterséges Intelligencia

MAP becsléshez szükségünk van valószínuségekre: ˝

15 Csató Lehel

A D adathalmaz valószínusége ˝ (log–lik). θ paraméterhez – az adatok által – rendelt fgv:


xn , θ , F ) ∝ exp [−L(yn , f(x xn , θ ))] P(yn |x

Rejtett változók Becslések

∝ – normálni is kell.

ML MAP Bayes

Grafikus modellek

˝ A-priori – elozetes – valószínuség ˝ Milyen θ értékek a legvalószínubbek ˝ θ k2 kθ θ) ∝ exp − p0 (θ 2 ˝ specifikáljuk. az adatok ismerete elott 338/364

MAP

Maximum a–posteriori becslés Mesterséges Intelligencia

MAP becsléshez szükségünk van valószínuségekre: ˝

15 Csató Lehel

A D adathalmaz valószínusége ˝ (log–lik). θ paraméterhez – az adatok által – rendelt fgv:


xn , θ , F ) ∝ exp [−L(yn , f(x xn , θ ))] P(yn |x


∝ – normálni is kell.

ML MAP Bayes

Grafikus modellek

˝ A-priori – elozetes – valószínuség ˝ Milyen θ értékek a legvalószínubbek ˝ θ k2 kθ θ) ∝ exp − p0 (θ 2 ˝ specifikáljuk. az adatok ismerete elott 338/364

MAP

MAP Mesterséges Intelligencia

15

II

A becslés a fenti valószínuségek ˝ – lik. & prior – kombinálása.


Bayes-szabály alkalmazása a θ és Dváltozókra:

Adatmodellezés

θ)p0 (θ θ) P(D|θ F) p(D|F Z F) = θ P(D|θ θ)p0 (θ θ) p(D|F dθ

θ|D, F ) = p(θ

Rejtett változók Becslések ML MAP Bayes

Grafikus modellek

Ω

F ) – az adatok teljes valószínusége ahol p(D|F ˝ az adott F modellre. θ|D, F ) minden θ értékhez egy valószínuség P(θ ˝ ⇒ egyszerusítés ˝ szükséges. 339/364

MAP Mesterséges Intelligencia

15

III

M.A.P. becslés – a legvalószínubb ˝ θ megtalálása: ∗ θ|D, F ) θ MAP = arg max p(θ θ ∈Ω

Csató Lehel Gépi Tanulás Adatmodellezés

Példa:

Rejtett változók Becslések ML MAP

xn , θ )) hibafüggvényt és Gauss-féle Az általános L(yn , f(x a-priori valószínuségre. ˝

Bayes

Grafikus modellek

A θ ∗MAP kiszámítása (exp-ben levo˝ tagok): X θk2 kθ xn , θ )) − θ ∗MAP = arg max K − L(yn , f(x 2σ2o θ ∈Ω n Ha σ2o → ∞ a maximum likelihood módszer. . 340/364

˝ egy elojelcsere és max → min helyettesítés után.

MAP

Példa


6−odfoku polinom

15

12

Csató Lehel

10

Gépi Tanulás Adatmodellezés Rejtett változók

Zaj var. =10−3 Zajmentes fgv. Tanulo adatok Zaj var. = 10−2

8 6

Becslések ML MAP

4

Bayes

Grafikus modellek

2 0 −2 −4 −6 −10

341/364

−5

0

5

10

Paraméter–becslések Mesterséges Intelligencia

Bayes – feltételes valószínuség ˝ – szabálya:

15

θ)p0 (θ θ) P(D|θ F) p(D|F Z F) = θ P(D|θ θ)p0 (θ θ) p(D|F dθ

θ|D, F ) = p(θ


Ω

Rejtett változók Becslések ML

Bayes

és megpróbáljuk a teljes eloszlást tárolni.

MAP

Miért?

Bayes

Grafikus modellek

Mivel nincs mindig képlet a poszt. eloszlásra, a θ|D, F ) ppost (θ sur ˝ uségfüggvényt ˝ közelítjük. 342/364

Statisztikák Mesterséges Intelligencia

. . . szünet . . .

Apróbetu: ˝ A statisztikák szerepe: Az adatok helyettesítése

15

Feltételezzük, hogy létezik egy generátor, mely az adatokat létrehozta;


xi , yi ) = Γ (zzi |θ1 , . . . , θk ). Ismerjük a generátor alakját: (x

Rejtett változók

z i – paraméterek, változók.

Becslések

θ = [θ1 , . . . , θk ]T – a modell paraméterei.

ML MAP Bayes

Az elemzéshez

Grafikus modellek

a teljes adathalmazt helyettesítjük a megfelelo˝ paraméterekkel. A predikcióhoz nem használjuk az adatokat, „csak” a kinyert paramétereket és a modellt. 343/364

Bayes–becslés Mesterséges Intelligencia

15 Csató Lehel

II

Bayes–becslés folyamán Foglalkozunk a poszterior-eloszlás közelítésével:

Gépi Tanulás

θ) ≈ ppost (θ θ|D, F ) p ^ (θ


egy új adat valószínuségével ˝ – predikció: Z x∗ ) ≈ θ p θ)P(y ∗ |x x∗ , θ ) p ^ (y∗ |x dθ ^ (θ


Ω

Grafikus modellek

Teljes valószínuségnek ˝ a közelítésével:

F |D) = p(D|F F )p0 (F F) p(F F |D) használható – elvileg – két különbözo˝ A p(F modell összehasonlítására. 344/364


közelítés

θ) ≈ ppost (θ θ|D, F ) p ^ (θ

15 Csató Lehel Gépi Tanulás Adatmodellezés Rejtett változók Becslések ML

A közelítés alapja egy divergencia: méri, hogy a közelíto˝ ˝ eloszlás minoségét: θ) = argmin d ppost (θ θ|D, F ), p(θ θ) p ^ (θ θ)∈Ω p(θ

MAP Bayes

Grafikus modellek

A Bayes-becslések során fontos: milyen családban keressük az optimális eloszlást, milyen divergenciát használunk a „távolságok” mérésére. Gyakori a Kullback-Leibler divergencia. 345/364

Kullback–Leibler Mesterséges Intelligencia

. . . szünet . . .

Gyakori a Kullback-Leibler divergencia:

Z

15

θ)|p2 (θ θ)) = dKL (p1 (θ


θ p1 (θ θ) log dθ Ωθ

θ) p1 (θ θ) p2 (θ

Tulajdonságok:

Adatmodellezés

dKL (p1 |p2 ) ≥ 0

Rejtett változók

0 = log

Becslések ML

`R

” “R ´ θ) p2 (θ θp2 (θ θ) = log dθ θp1 (θ θ) p dθ θ (θ ) 1

alkalmazzuk a

MAP Bayes

Grafikus modellek

dKL (p1 |p2 ) = 0

⇔

˝ Regyenlotlenséget: θ) p2 (θ θp1 (θ θ) log p 0 > dθ θ) 1 (θ 0 > −dKL (p1 |p2 )

Jensen

θ) = p2 (θ θ) p1 (θ kivéve egy nulla-mértéku˝ halmazt...

dKL (p1 |p2 ) 6= dKL (p2 |p1 ) ˝ Nem teljesül a háromszög-egyenlotlenség. dKL (p1 |p2 ) dKL (p1 |p3 ) + dKL (p3 |p2 ) 346/364

következo˝

˝ Jensen egyenlotlenség Mesterséges Intelligencia


. . . szünet II. . .

˝ Jensen egyenlotlenség x) egy konvex függvény az Legyen f(x [a, b] intervallumon. Ekkor ∀λ ∈ [0, 1]

x2 + bx x+c ax

f(λa + (1 − λ)b) ≤ λf(a) + (1 − λ)f(b)

Adatmodellezés

A logaritmus: függvény konkáv, tehát:

MAP Bayes

b = 2.5

ML

λ = 0.4

Becslések

a=0

Rejtett változók

log(λa + (1 − λ)b) ≥ λ log(a) + (1 − λ) log(b)

Grafikus modellek

Sok együtthatóra: ! X log πi ai

≥

i

„Z log

Z

« θp(θ θ) f(θ θ) dθ

X

≥

πi log(ai )

ahol

ahol a, b > 0. X

πi = 1 és πi ≥ 0.

i

i

θp(θ θ) log (f(θ θ)) dθ

θ) > 0. ahol f(θ vissza

347/364


Példa közelítésre:

15

Ω=


közelítés

» –

1 θ − µθ )T Σθ−1 (θ θ − µ θ ) | µ θ ∈ Rd , Σ ∈ Rd exp − (θ 2

ahol Σ egy pozitív-definit mátrix.


Paraméter–optimizálás lépései: θ|D, F ) a-posteriori eloszlás és az Ω A ppost (θ eloszláscsalád meghatározása;


Grafikus modellek

θ)|p(θ θ|µ µ, Σ) kiszámítása – (µ µ, Σ) vált.; dKL ppost (θ ^ meghatározása: (^ µ , Σ) ^ ⇒ argmin dKL ppost (θ θ)|p(θ θ|µ µ, Σ) (^ µ , Σ) p∈Ω 348/364


predikció

Feltételezzük, hogy

15

θ) eloszlást. meghatároztuk a legjobban közelíto˝ p ^ (θ

Csató Lehel

ismerjük a bemenet–kimenet összefüggéseket: a

Gépi Tanulás

x, θ ) felt. valószínuséget. P(y|x ˝


Grafikus modellek

Predikció: Adott bemenetre mi lesz a kimeneti értékek eloszlása?

x, θ ) eloszlás az y szerint, akkor a prediktív Ha P(y|x disztribúció: Z x∗ , D) = p(y∗ |x

θp θ|D) P(y∗ |x x∗ , θ ) dθ ^ (θ Ωθ

349/364

Bayes–predikció Mesterséges Intelligencia

15

predikció II

Prediktív disztribúció: Z θp θ|D) P(y∗ |x x∗ , θ ) x∗ , D) = dθ ^ (θ p(y∗ |x Ωθ

Csató Lehel Gépi Tanulás Adatmodellezés Rejtett változók

A Gyakorlatban: fontos a modell választása: ha M a modell-család, ˝ akkor minden valószínuség ˝ függ az M-tol:


θ|D) p ^ (θ

Grafikus modellek

def

=

θ|D, M) p ^ (θ

θ)-hoz hasonlóan a prediktív eloszlás sem A ppost (θ írható fel analitikusan: közelítések szükségesek. θ)-hoz hasonló A prediktív eloszlást általában a p ^ (θ módszerekkel keressük. 350/364

Bayes–modellek Mesterséges Intelligencia


Példa

Függvénycsalád: legyen az s 6 X 6 def k x) = F = f(x θk α k x | θk ∼ N(0, 1), αk = k k=0

Adatmodellezés Rejtett változók Becslések ML

ahol θ = [θ1 , . . . , θ6 ]T a függvény paraméterei. Ekkor átlagban:

MAP Bayes

Grafikus modellek

x)iθ0 ,...,θ6 = hf(x

* 6 X

+ θk αkx

k

k=0

=

6 X k=0

illetve . . .

351/364

0 αkx k = 0

= θ0 ,...,θ6

Bayes–modellek Mesterséges Intelligencia


Példa

Függvénycsalád: legyen az s 6 X 6 def k x) = F = f(x θk α k x | θk ∼ N(0, 1), αk = k k=0

Adatmodellezés Rejtett változók Becslések ML

ahol θ = [θ1 , . . . , θ6 ]T a függvény paraméterei. Ekkor átlagban:

MAP Bayes

Grafikus modellek

x)iθ0 ,...,θ6 = hf(x

* 6 X

+ θk αkx

k

k=0

=

6 X k=0

illetve . . .

351/364

0 αkx k = 0

= θ0 ,...,θ6

Bayes–modellek

Példa II


15 Csató Lehel

* x1 )f(x x2 )ia0 ,...,a6 = hf(x

6 X

! θk αkx k1

k=0


=


6 X

1α2kx k1x k2 =

= (1 + x 1x 2 )

MAP Bayes

!+ θk αkx k2

k=0

k=0

ML

6 X

...

6 X k=0

6 x1x 2 )k (x k

6

Grafikus modellek

F tehát egy függvényosztály, melynek átlaga 0 és szórása fent látható. Feladat: Közelítsünk a Bayes–modell segítségével. 352/364

Bayes–modellek

Példa II


15 Csató Lehel

* x1 )f(x x2 )ia0 ,...,a6 = hf(x

6 X

! θk αkx k1

k=0


=


6 X

1α2kx k1x k2 =

= (1 + x 1x 2 )

MAP Bayes

!+ θk αkx k2

k=0

k=0

ML

6 X

...

6 X k=0

6 x1x 2 )k (x k

6

Grafikus modellek


Bayes–modellek

Példa II


15 Csató Lehel

* x1 )f(x x2 )ia0 ,...,a6 = hf(x

6 X

! θk αkx k1

k=0


=


6 X

1α2kx k1x k2 =

= (1 + x 1x 2 )

MAP Bayes

!+ θk αkx k2

k=0

k=0

ML

6 X

...

6 X k=0

6 x1x 2 )k (x k

6

Grafikus modellek


Bayes–modellek

Példa II


15 Csató Lehel

* x1 )f(x x2 )ia0 ,...,a6 = hf(x

6 X

! θk αkx k1

k=0


=


6 X

1α2kx k1x k2 =

= (1 + x 1x 2 )

MAP Bayes

!+ θk αkx k2

k=0

k=0

ML

6 X

...

6 X k=0

6 x1x 2 )k (x k

6

Grafikus modellek


Bayes–példa Mesterséges Intelligencia

15 Csató Lehel Gépi Tanulás Adatmodellezés Rejtett változók Becslések

Zaj

Szükséges a zaj ismerete; Feltételezzük, hogy az Gauss eloszlású, tehát: x))2 1 (y − f(x x, θ ), σo ) = √ exp − P(y|f(x 2σ2o 2π ahol σn a zaj (noise) szórása.

ML MAP Bayes

x1 , y1 ), . . . , (x xN , yN )} Az adatok: D = {(x

Grafikus modellek

Feltételes valószínuségük: ˝ θ, σo ) = P(D|θ

N Y n=1

353/364

xn , θ ), σn ) P(yn |f(x


15

A–posteriori eloszlás:

θ|D, σo ) = R ppost (θ

Csató Lehel Gépi Tanulás Adatmodellezés Rejtett változók Becslések ML MAP

a–post I

θ, σo ) p0 (θ θ) P(D|θ θ P(D|θ θ, σo )p0 (θ θ) dθ

θ) a változók feltételezett – a–priori – eloszlása. ahol p0 (θ Megjegyzések: Normál a–priori eloszlás esetén:

Bayes

Grafikus modellek

θ) ∝ − log p0 (θ

354/364

θ k2 kθ 2σ2p

azaz regularizációs megkötés a paramétereken. A modell a paraméterekben lineáris ⇒ gaussz-eloszlás lesz az eredmény is. a jobb oldalon eloszlás van, a nevezo˝ normalizáló ⇒ annak értékét nem kell kiszámítani.

Bayes–példa

a–post II


15

θ|D, σo ) = log p(D|M) + −2 log ppost (θ


N X θ k2 xn |θ θ))2 kθ (yn − f(x + 2 2 σn σp n=1

ahol log p(D|M) a normalizáló konstans. Jelölések:

x0 , x 1 , . . . , x 6 ]T . x^ def = [x

Rejtett változók

θ k2 = θ T θ xn |θ θ) def θ T x n |θ f(x 2 3= 2 3 y1 x1 0 . . . x61 6 7 6 .. 7 .. y = 4 ... 5 X = 4 ... . . 5 yN x0N . . . x6N


Grafikus modellek

A fenti jelölésekkel az összeg szorzattá alakul. Csoportosítva: „ T « X X I7 θT + θ − y T Xθ + K1 σ2n σ2p

355/364

Bayes–példa

a–post III


15

θT


„

I7 XT X + 2 2 σn σp

« θ

yT Xθ −y

+K1

θ T Aθ

bT Aθ −b

+K1


ahol


Grafikus modellek

A def =

XT X σ2 n

+

I7 σ2 p

;

−1 T b def =A X y

θ|D, σo ) tehát tartalmaz egy teljes négyzetet és egy A log pp ost(θ konstanst. Mivel a teljes négyzet Gaussz-eloszlást jelent, a konstans értékét ismerjük. Az eredmény: “ ” θ|D, σo ) = N θ |b b, A −1 log pp ost(θ

356/364


Rajz 2

Pol. 6 − N.var σ = 1

15 Csató Lehel Gépi Tanulás Adatmodellezés

10


5

Grafikus modellek

0

−5 −10 357/364

−5

0

5

10

Becslések Mesterséges Intelligencia

Összefoglaló

Max–Lik. becslésnél: nincs a–priori eloszlás, a becslés esetenként rossz.

15 Csató Lehel Gépi Tanulás Adatmodellezés

M.A.P. becslésnél: eloszlásokról beszélünk, azonban a becslés eredménye nem valószínuségi, ˝ hanem egy érték.


Grafikus modellek

Bayes–becslésnél: a becslés eredménye egy valószínuségi ˝ eloszlás.

358/364

Grafikus Modellek Mesterséges Intelligencia

15 Csató Lehel Gépi Tanulás Adatmodellezés Rejtett változók

˝ A paraméterek függoségi gráfja a regressziós példánál.

Példa

µ

Lényeges, hogy a nem a θ paramétert becsüljük; θ) eloszlás paramétereit, hanem a p(θ =⇒ jelen esetben ezek µ és σ.

σ θ

Becslések ML

yn

MAP Bayes

xn

Grafikus modellek

D Grafikus modelleket akkor használunk, ha egy modell egyes paramétereit megfigyeljük – pl. (xn , yn ) – másokra meg következtetni kell. A következtetés alapja a megfigyelések és a modell. 359/364

Grafikus Modellek

.


15 Csató Lehel

h11 h1d1

hl1

hldl

hiperparaméterek

Gépi Tanulás Adatmodellezés Rejtett változók

θ1

Becslések ML

θl

paraméterek

MAP Bayes

Grafikus modellek

yn

D 360/364

xn

adatok

Admin ...



V Csató Lehel Vizsgatematika

... trívia

Vizsga Szóbeli (60%) + Gyakorlat (40%) Laborgyakorlatok: 1


18%

2

Játékelmélet

10%

3


12%

4



sok%

Vizsgatematika Mesterséges Intelligencia

M.I – racionális vs. imitáló ˝ illetve cselekvo/gondolkodó.

V Csató Lehel

Tudásreprezentáció – állapottér, feladat definíció.

Vizsgatematika

Megoldás-keresések az állapottérben: hegymászó, backtracking. Gráfkeresés – kapcsolata a M.I. rendszerekkel. Dekompozíciós módszer. Predikátumkalkulus, rezolúció. Gráfok, utak, irányított gráfok, /Sigma/delta/ tulajdonságok.

363/364

I

ÉS/VAGY gráfok, hiperutak és-vagy gráfokban. ÉS/VAGY gráfok átalakítása irányított gráffá. Játékok gráfjai, puzzle, 4 ˝ királyno. Gráfkereso˝ alapalgoritmus. Gráfkereso˝ algoritmus tulajdonságai. Keresési algoritmusok: mélységi, szélességi, ˝ ˝ egyenletes, eloretekint o. A-* algoritmus család, tulajdonságok. Szemantikus hálók, tulajdonságok, operációk.

Vizsgatematika Mesterséges Intelligencia

Játékok: keresés, kétszemélyes játékok, stratégia.

V Csató Lehel

NIM játék: leírás, nyero˝ stratégia (b).

Vizsgatematika

Nyero˝ stratégia teljes információs játékoknál (b).

364/364

II

Dempster-Shafer modell, Bel, Pl és m függvények. Fuzzy logika, ∼ rendszerek. Tanulás: induktív és/vagy deduktív rendszerek. Tanuló rendszerek típusai.

Minimax algoritmus, minimax tétel (b).

Exploration vs. exploitation – visszacsatolásos tanulás.

Minimax, negamax algoritmusok.

Genetikus algoritmusok, hamiltoni rendszerek,

Alfa-béta vágás. Bizonyt.ság: Bayes-modell.

Neurális hálózatok, topológiák.

Bayes-hálók, grafikus modellek.

Neurális hálózatok tanítási szabályai, optimizálás.

364

Recommend Documents