363

Mesterséges Intelligencia Csató Lehel

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

2010/2011

1/363

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

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

4

„Tudás”–reprezentáció

Csató Lehel

Gráfkeresési stratégiák

Alapalgoritmus

Szemantikus hálók / Keretrendszerek

Általános algoritmus

Játékok modellezése

Példa Mélységi

Bizonytalanság kezelése

Szélességi Egyenletes

Fuzzy rendszerek

˝ Eloretekint o˝

Grafikus modellek

A alg

Tanuló rendszerek

A* és Ac

Szimulált kifutés, ˝ Genetikus algoritmusok

Opcionális feladatok

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

Admin ...

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

Mesterséges Intelligencia

4 Csató Lehel Alapalgoritmus

... trívia

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


Példa Mélységi

Laborgyakorlatok:


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

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

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

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 71/363

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. 72/363

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:

73/363

5

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

Mesterséges Intelligencia

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. 74/363

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. 75/363

(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) 76/363




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

77/363

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

77/363

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 78/363

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

79/363

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

80/363

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

81/363

– 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


81/363

– nyílt csúcsok

l


4


k


1

4

2

Csató Lehel

3


6

Mélységi

5


81/363

– nyílt csúcsok

l


4


k


1

4

2

Csató Lehel

3


6

Mélységi

5


81/363

– nyílt csúcsok

l


4


k


1

4

2

Csató Lehel

3


6

Mélységi

5


81/363

– 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

81/363

– nyílt csúcsok

l


4


k


1

4

2

Csató Lehel

3


7

Mélységi

6 5

Szélességi

8


81/363

– 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)} 81/363


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. 81/363

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?). 82/363


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

83/363


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

83/363

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. 84/363

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). 85/363

˝ 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.

86/363

„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.

87/363

„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.


88/363

„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. 89/363

„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. 90/363

„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. 91/363

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˝ 92/363

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)


. 93/363

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

363

Recommend Documents