1. AZ MI FOGALMA. I. Bevezetés. Tulajdonságok. Kezdet ELIZA. Első szakasz (60-as évek)

1. AZ MI FOGALMA Nincs pontos definíció  Emberi gondolkodás számítógépes reprodukálása ‒ Intelligens viselkedésű programok  Az ember számára is nehéz problémák számítógépes megoldása – Intellektuálisan nehéz feladatok megoldása  Az informatika mozgató ereje: érdekes, újszerű problémák felvetése és számítógépes megoldása.

I. Bevezetés

Gregorics Tibor

Mesterséges intelligencia

Gregorics Tibor

1

Tulajdonságok Megoldandó feladatai: nehezek. – Hatalmas a lehetséges válaszok tere (problématér) – Helyes válasz megtalálása intuíciót, kreativitást igényel  Megoldási módszerek: intelligensek. ‒ Olyan, mintha ember oldaná meg (Turing teszt) ‒ Működése közben tanul. ‒ Szisztematikus , előre rögzített stratégiájú keresés helyett irányított keresés (heurisztika) Mesterséges intelligencia

1956 nyár. Darthmouth College-i konferencia Kezdeti cél:

Az emberi gondolkodás számítógép segítségével történő reprodukálása.

Gregorics Tibor

3

Első szakasz (60-as évek)

4

Illesztési szabályok – ön engem . • Úgy érzem, hogy ön mostanában engem un. – Miért gondolja, hogy ön én ? • Miért gondolja, hogy ön úgy érzi, hogy én mostanában unom?  Emlékezési szabályok  Folytatási szabályok

Eredmények: kétszemélyes játékok (dáma, sakk), beszélgető program (ELIZA,1966)  Módszerek, eszközök: GPS, rezolúció (1966), LISP(1958), mesterséges neuronhálózatok (1969), evolúciós algoritmusok (1959)  Kudarcok: DOCTOR-PARRY, nyelvi fordítók, kombinatorikus robbanás



ELIZA 



Gregorics Tibor

2

Kezdet



Gregorics Tibor


5

Gregorics Tibor


6

1

Második szakasz (70-es évek)

Harmadik szakasz (80-as évek) Eredmények: DENDRAL (1969-78), MYCIN(1976), PROSPECTOR(1979), XCON (1982)  Módszerek, eszközök: tudásalapú szakértő rendszerek, shell-ek, módszertanok, nem klasszikus logikák, bizonytalanság kezelése  Kudarcok: rendszerek elkészítése lassabb, mint a gyorsan változó programozási környezet 

Eredmények: SHRDLU (1972), BACON, AM, EURISKO  Módszerek, eszközök: Prolog, heurisztikus keresési technikák, tudásábrázolási módszerek (kognitív modellek)  Kudarcok: MI fejlődési trendje, meseíró program 

Gregorics Tibor


Gregorics Tibor

7

Eredmények: logisztika, űrkutatás, Deep Blue, döntés támogató rendszerek, nyelvi fordítók, robotika (beszélgetés, gépi látás, tervgenerálás, gépi tanulás)  Módszerek, eszközök: elosztott tudás reprezentálása (mesterséges neuron háló, evolúciós algoritmus, ágens szemlélet), döntéselmélet (valószínűségi hálók), beszédfelismerés (rejtett Markov modellek) 






Az emberi gondolkodás számítógépes reprodukálása szempontjából hasznos elveket, módszereket, technikákat kutatja, rendszerezi, fejleszti Nem az emberi gondolkodás számítógépes modelljét, hanem egy-egy feladat minél jobb minőségű számítógépes megoldását keresi Az MI az informatikának a gondolkodási-tudományos előőrse. Vámos Tibor Gregorics Tibor

9

2. PROBLÉMA MODELLEZÉS Problématér: egy problémára adható összes lehetséges válasz , valamint azok esetleges (szomszédsági) kapcsolatai  Cél: a problémára adható egyik helyes válasz megtalálása (a probléma megoldása) . Ehhez sokszor egy kiinduló pontból (kiinduló válaszból) indulunk.  Megoldást segítő ötletek: problématér szűkítése hasznos válaszok kijelölésével Adott lépésben választható válaszok rangsorolása

Gregorics Tibor



10

Probléma reprezentációs modellek



-

8

A gyengeMI nézőpontja

Negyedik szakasz (90-as évektől)

Gregorics Tibor


11



Problématér és a cél számítógépes ábrázolása – Állapottér-reprezentáció –

–

Probléma redukció, dekompozíció Logikai reprezentáció

Strukturált objektum alapú reprezentáció – Elosztott reprezentáció  Sok esetben a probléma reprezentációja leképezhető egy irányított gráfbeli útkeresési feladattá –

Gregorics Tibor


12

2

Útkeresési feladat Általános eset: az irányított gráf csúcsai problémára adható lehetséges válaszok (közülük csak néhány helyes), az élek az ezek közötti szomszédsági kapcsolatok. Ebben a gráfban egy kezdeti válasznak megfelelő csúcstól indulva egy helyes választ reprezentáló csúcsot keresünk.  Speciális eset: amikor a lehetséges válaszokat elemi lépések sorozataként adhatjuk meg, akkor ezek egy közös kezdő csúcsból induló utakkal ábrázolhatók. Az így elképzelt irányított gráfban kell olyan utat keresünk, amelyik egy helyes választ reprezentál. 

Gregorics Tibor


Állapottér-reprezentáció Ez egy széles körben (de nemcsak a MI-ben) használt modell • Állapottér (domináns típusérték-halmaz) – invariáns • Műveletek (elemi lépés az állapottérben) – előfeltétel, hatás • Kezdő állapot(ok) vagy előfeltétel • Célállapot(ok) vagy utófeltétel  Ekkor a leírt feladat mindig leképezhető útkeresési problémává. 

Gregorics Tibor

13


[3,3,3]

Hanoi tornyai probléma [2,3,3]

1

2

3

1

A B C [3,3,3]

2

[1,3,3] [1,2,3]

[2,1,3]

A B C [1,1,1]

[2,2,3]

[1,1,3] [3,1,3] [3,2,3]


[2,2,1]

[1,1,2] [3,1,2]

[2,1,2]

[2,2,2] 15

Egy útkeresési probléma gráfreprezentációja egy (R,s,T) hármas, amelyben – R=(N,A,c) -gráf az un. reprezentációs gráf, – az s N startcsúcs a kiinduló pont, – a T N halmazbeli célcsúcsok.  A feladat megoldása: egy t T cél megtalálása egy s T, esetleg egy s* T optimális út megtalálása 


[3,2,1] [3,1,1] [1,1,1]

Gregorics Tibor

Mesterséges intelligencia [2,1,1] [1,2,2] [1,3,2] [3,3,2] [3,3,1] [2,3,1]

16

Gráf fogalmak 1.   

    

17

[1,2,1]

[2,3,2] [1,3,1]

[3,2,2]

Gráfreprezentáció fogalma

Gregorics Tibor

Állapot gráf

3

Állapottér: Állás=tömb( [A,B,C];{1,2,3}) Művelet: Rak(honnan, hová):Állás Állás (a:Állás) HA a-ban a honnan nem üres, és a hová üres vagy a hová felső korongja nagyobb, mint honnan felső korongja AKKOR a[honnan felső korongja] hová Gregorics Tibor

14

csúcsok, ir. élek él n-ből m-be n utódai, szülei irányított gráf -tulajdonság élköltség -tulajdonság -gráf Gregorics Tibor

N, A N N (számosság) (n,m) A (n,m N) (n), (n), (n) R=(N,A) {(n,m) A m N} < n N c:A R , c(n,m) (n,m) A c(n,m) >0 (n,m) A , -tulajdonságú élsúlyozott irányított gráf Mesterséges intelligencia

18

3

Gráf fogalmak 2. irányított út



n-ből kiinduló utak ir. út hossza ir. út költsége opt. költség opt. költségű út

   

c (n,m):= i c(ni-1,ni) c*(n,m):=min {n m} c (n,m) n* m, n* M

Gregorics Tibor


A keresés egy olyan algoritmus, amely a problématér kezdeti válaszából indulva keres egy helyes választ tárolja az addig feltárt információ egy részét választ az adott pillanatban elvégezhető alternatív lépések közül egy lépés végrehajtásával módosítja a tárolt információt felismeri, ha elérte a célját  Ha a megoldandó feladatot útkeresési problémaként fogjuk fel, akkor a keresés során feltárt információ a reprezentációs gráf egy része. 

=(n,n1),(n1,n2),...,(nk-1,m) (n,n1,n2,...,nk-1,m), n m, n m {n m} , {n M}

19

Gregorics Tibor


Kereső rendszer (KR)

A KR részei globális munkaterület

Procedure KR 1. ADAT kezdeti érték 2. while terminálási feltétel(ADAT) loop 3. select SZ from alkalmazható szabályok 4. ADAT SZ(ADAT) 5. endloop end


globális munkaterületet változtató

kereső rendszer operátorok (procedurális ismeret) szabályai hatás, értelmezési tartomány SZ

vezérlési stratégia 21

Vezérlési vagy keresési stratégia

független a feladattól

Gregorics Tibor

másodlagos független a konkrét feladattól, de annak reprezentációs modelljére támaszkodik

végrehajtható szabályt kiválasztó általános elv + a konkrét feladattól származó vezérlési ismeret (megoldást segítő ötletek)

Gregorics Tibor


22

A heurisztika hatása a KR működésére

vezérlés elsődleges

a keresés során megszerzett és megőrzött (deklaratív) ismeret kezdeti érték, terminálási feltétel

ADAT

select Gregorics Tibor

20

reprezentáció alapján



3. KERESÉS

heurisztika

heurisztika A reprezentációban nem rögzített a konkrét feladat megoldását segítő ötletek


23

eredmény

hatékonyság

futási idő Gregorics Tibor

memóriaigény Mesterséges intelligencia

24

4

A KR futási ideje költség futási idő alkalmazott szabályok száma

szabály kiválasztásának ideje informáltság teljes

Gregorics Tibor


25

5

1. AZ MI FOGALMA. I. Bevezetés. Tulajdonságok. Kezdet ELIZA. Első szakasz (60-as évek)

Recommend Documents