Dr Mikó Balázs Mesterséges intelligencia Szakértői rendszerek 3.1 ( :38)

BUDAPESTI MŰSZAKI ÉS GAZDASÁGTUDOMÁNYI EGYETEM GÉPGYÁRTÁSTECHNOLÓGIA TANSZÉK

Dr Mikó Balázs

Mesterséges intelligencia Szakértői rendszerek Oktatási segédlet a Technológiai tervező rendszerek Tárgyhoz

3.1 (2002.02.26. 17:38)

2002.

Mesterséges intelligencia, Szakértői rendszerek

Tartalom 1. 2. 3. 4. 5. 6. 7. 8.

1.

Mesterséges intelligencia Szakértői rendszerek Tudásreprezentációs módszerek Mesterséges neurális hálók Kereső eljárások Felkészülést segítő kérdések Függelék Irodalom

Mesterséges intelligencia

2 3 4 8 12 17 18 20

2 91] egy probléma jobb megoldásának előállítására helyezi a hangsúlyt a kutatás céljának definiálásakor: a mesterséges intelligencia annak a kutatása, hogyan oldhatják meg a számítógépek hatékonyabban azokat a problémákat, melyeket jelenleg az emberek oldanak meg jobban. Természetesen itt is megfigyelhetők biológiai analógiák, de a cél nem a biológiai rendszer modellezése, megértése, hanem más területeken felmerülő problémák hatékonyabb megoldása. Ily módon az analógia már csak igen nehezen fedezhető fel az alkalmazott módszer, algoritmus mögött. Műszaki problémák megoldására ez a megközelítés alkalmazható. [Sharples 91] három pontban foglalta össze a mesterséges intelligencia kutatások célját, ötvözve a fenti két megközelítést: • meglévő intelligens rendszerek empirikus tanulmányozása és modellezése, • intelligens rendszerekben alkalmazható módszerek elméleti kutatása, • gyakorlati problémák megoldása ezen módszerek segítségével. A célunk tehát az intelligens problémamegoldás. A kérdés az, mit jelent az intelligens viselkedés. Az intelligencia az értelmi működés fokmérője, elsősorban új körülményekhez való alkalmazkodó képességben mutatkozik meg, amely szorosan összefügg az előzőleg szerzett tapasztalati anyag alkalmazásával, a helyzet mozzanatainak széleskörű figyelembevételével és a gondolkodóképességgel ([Berei 62]). Ezen definició igen tág teret ad az intelligens viselkedés értelmezésére. [Russel 94] szerint egy rendszer intelligensen viselkedik, ha a rendelkezésre álló ismeretek, vélekedések alapján a lehető legjobb döntést hozza egy adott cél elérése érdekében. [Leigh 86], [Wolfgram 87] és [Schalkoff 90] az emberi problémamegoldás mintáján történő önálló döntéshozatalt emeli ki. [Partridge 86] szintén alkalmazás orientált definíciót ad a mesterséges intelligencia fogalmára: szerinte a mesterséges intelligencia olyan algoritmusok gyűjteménye, melyek tanulási képességgel rendelkeznek és egy probléma elegendően jó megoldását adják. [Sharples 91] három kulcs jellemző meglétével

A mesterséges intelligencia kutatások kezdetét a korai ötvenes évekre tehetjük, amikor John McCarthy egy konferenciát szervezett a Dartmouth College-ba, melynek témája az emberi gondolkodás folyamatát modellezni képes gép megalkotásának lehetősége volt ([Chien 92]). Az azóta eltelt időben a mesterséges intelligencia kutatás önálló tudománnyá vált, így a kezdeti célok is sokrétűbbé váltak, számos területe alakult ki a kutatásoknak, jól elkülöníthető irányzatok jöttek létre. Ebből következik, hogy a mesterséges intelligencia szó jelentését is másként értelmezik a különböző kutatók. A mesterséges intelligencia (MI) olyan kutatási terület, amely arra törekszik, hogy a számítógépek intelligensnek tekinthető tevékenységeket tudjanak végezni ([Erdélyi 97]). A kutatásoknak két fő irányuk van, egy kognitív és egy számítástudományi irány. A kognitív pszichológiával kapcsolatos kutatások a számítógépet eszközként használják az emberi gondolkodás, problémamegoldás stb megértésére, modellezésére ([Beardon 89], [Turing 88], [Searle 88], [Newell 88]). Ezen irányzaton belül is több modellezési módszer létezik ([Érdi 98]). Az úgynevezett "felülről-lefelé" megközelítés a viselkedési adatokból indul ki és megpróbál olyan modellt illetve algoritmust alkotni, amelyek visszaadják ezen jelenségeket. Az Mesterséges intelligencia "alulról-felfelé" modellezési stratégia Számítástudományi az anatómiai ismeretek alapján próbál Kognitív kutatások kutatások modellt alkotni, ügyelve a konkrét fizikai hasonlóságra és így előállítani a MI módszerek MI alkalmazások megfigyelhető jelenségeket. Ezen Keresés megközelítés sajátosságai jól Szakértői rendszerek megfigyelhetők [Albert 98] által Tudásreprezentáció Cselekvéstervezés ismertetett idegrendszeri modellen. Szimbolikus következtető módszerek Beszédfeldolgozás Ezzel szemben a számítástudományi megközelítés azt Szubszimbolikus következtető módszerek Képfeldolgozás tűzte ki célul, hogy intelligensebbé ... Tanulás és adaptáció tegye a számítógépek "viselkedését" ... ([Bahrami 88], [Gottinger 90]). [Rich Ábra 1. MI kutatási területek Mikó Balázs - [email protected]

Mesterséges intelligencia, Szakértői rendszerek definiálja az intelligenciát, melyek a céltudatosság, a rugalmasság és az általa "eredményes lustaság"-nak nevezett tulajdonság, ami arra utal, hogy a cél elérése érdekében csak a szükséges és elégséges tevékenységet végezze a rendszer. Mint az eddigiekből is kiderült, a mesterséges intelligencia kutatások roppant szerteágazóak és sokrétűek (Ábra 1). A továbbiakban a szakértői rendszerekkel, illetve a szakértői rendszerekben alkalmazható mesterséges intelligencia módszerekkel foglalkozom.

2.

Szakértői rendszerek

A mesterséges intelligencia kutatások egyik legismertebb és legelterjedtebb alkalmazása a szakértői rendszerek. A szakértői rendszerek fogalmát definiálhatjuk szűkebb és tágabb értelemben ([Harmon 90]). Szűkebb értelemben a szakértői rendszer-technika olyan eszköz, amely könnyebbé és hatékonyabbá teszi a programfejlesztést. Tágabb értelemben az első lépést jelenti abban a folyamatban, amely arra irányul, hogy a programozás a direkt, numerikus programozásnál magasabb szintre kerüljön. A szakértői rendszer egy számítástechnikai hátterű probléma-megoldó rendszer, amely alapvetően különböző mesterséges intelligencia módszerekre épül ([Savory 90]), egy szűkebb problématerület (domain) ismereteit tartalmazza ([Bounet 88], [Parsage 88]), segít nagy méretű, komplex problémák analizálásában illetve megoldásában ([Harmon 88]) figyelembe véve a humán szakértők probléma-megoldási folyamatát ([Ignizio 91]). Íly módon kiterjesztik a számítógép lehetőségeit a szokásos matematikai és statisztikai függvényeken túl és megkönnyítik a számítógép programok készítését. A tudás kódolásával és a humán szakértők következtetési képességével a szakértői rendszerek feltárják az adott problémát és javaslatokat készítenek a megoldására ([Harmon 88]). Szakértői rendszereket ma már számos területen használnak. Alkalmazásuk közös vonása a következőkben foglalható össze ([Harmon 85], [Bielawski 91], [Durkin 94]): • a probléma megoldása gyakorlati tudást igényel, • a problématerület jól körülhatárolható, • a kiinduló adatok objektív módon leírhatók, • kevés az emberi szakértő, • fontos a probléma gyors megoldása. A szakértői rendszerenek alapvetően két típusuk van: a döntéstámogató és a döntéshozó szakértői rendszer. A döntéstámogató szakértői rendszerek Mikó Balázs - [email protected]

3 emlékeztetik a humán szakértőt a megfontolandó következményekre, a felderítendő alternatívákra stb., amelyek felett a szakértő esetleg elsiklana a döntéshozatal során. A döntéshozó szakértői rendszerek a probléma megoldásának megtalálásában segítik a problématerületen járatlan vagy kevéssé jártas felhasználót. A szakértői rendszereknek természetesen hátrányai is vannak: • nehéz új, vagy a szokásostól eltérő helyzetekre felkészíteni, • nem kreatív, • a fejlesztés drága és időigényes. Összehasonlítva egy humán szakértő és egy szakértői rendszer tulajdonságait, a következők állapíthatók meg: Humán szakértő Szakértői rendszer 1. A képességek és a A tudás állandó. tudás idővel változik. 2. Felkészítése hosszú és Fejlesztése drága, de költséges folyamat. sokszorosítani könnyű és olcsó. 3. Érzelmi állaponta Állandó és befolyásolja a megismételhető döntéshozatalt. eredményt biztosít. 4. Ritka és drága. Használata és karbantartása viszonylag olcsó. Az alapvető szakértői problématípusok következők lehetnek ([Harmon 90], [Sántáné 98]): • procedurális problémák, • diadnosztizáló problémák, • monitorozó / örző problémák, • konfiguráló / objektum tervező problémák, • tevékenységtervező / ütemező problémák.

a

Az egyes feladattípusok jellemzői a következők. Amikor az adott tárgyköri anyag leírható valamilyen egyszerű eljárással, procedurális problémával állunk szemben. Ilyenkor a feladat megoldása egymás utámi lépések sorozatával leírható, vagy döntési fába szervezhető. Diadnosztizáló problémát kell megoldanunk, ha megfigyelések halmazán következtetünk egy vagy több lehetséges megoldási javaslatra. A lehetséges okok (megoldások) felsorolása eleve adott és számuk az okozatok (megfigyelések) számához képest kevés. Monitorozó / örző problémáról beszélunk, ha jelek folyamatos figyelése során a rendszer beavatkozása szükséges, ha a kívánttól eltérő szituáció áll elő. A konfiguráló / objektum tervező problémák esetén nincsenek előre megadva a lehetséges megoldások, hanem a megfigyelések és felhasználói igények alapján a rendszer dolgozza ki azokat, az objektumok kapcsolatára vonatkozó megszorítások figyelembevételével.

Mesterséges intelligencia, Szakértői rendszerek A tevékenységtervező / ütemező feladatok az eléjük kitűzött célok érdekében tevékenységek olyan sorozatát határozzák meg, melyek adott körülmények között történő végrehajtása célhoz vezet. Megvizsgálva azon problématerületek, melyek szakértői rendszer segítségével hatékonyan támogathatók, öt jellegzetes tulajdonságuk emelhető ki ([Mérő 2001]): • A problématerület elég szűk ahhoz, hogy olyan tudást lehessen benne megragadni, amely nem mindenki számára kézenfekvő, ugyanakkor elég bonyolult ahhoz, hogy ilyen szakértelemre igény legyen. • Az adott területnek rendelkeznie kell emberi szakértőkkel, akiknek a tudásából ki lehet indulni a rendszer elkészítéséhez. • A humán szakértők között a szakterület alapkérdéseiben nagyfokú egyetértésnek kell lennie. • Szükséges, hogy az adott szakterületen számos tanpélda, alapadat is rendelkezésre álljon, mert csak így lehet a szakértői rendszert megbízhatóan tesztelni és tudásának korlátait meghatározni. • Általában annál jobb szakértői rendszert lehet építeni egy adott területen, minél jobban felosztható az illető terület olyan részproblémákra, amelyek egymással csak nagyon kevéssé interferálnak.

4 munka memóriába kerül, majd a megoldás során a következtető mechanizmus, felhasználva a tudásbázis adatait, megpróbál választ adni. A következtetés folyamatát a nyomkövető rendszer segítségével tudjuk figyelemmel kisérni. Léteznek úgynevezett szakértői keretrendszerek, amelyek a szakértő rendszer vázát tartalmazzák (az ábrán szaggatott vonallal határolva), így a fejlesztés idő- és munkaszükséglete jóval kisebb. Egy szakértői keretrendszer a következtetőmechanizmuson kívül tartalmazza azokat az eszközöket is, melyek lehetőséget nyújtanak a felhasználói felület és a tudásbázis létrehozására.

3.

A szakértői rendszerek problémamegoldó módszerét alapvetően meghatározza a tudásreprezentáció folmája. A legfontosabb reprezentációs formák a következők: • Frame-ek • Szabályok • Esetek • Heurisztikák 3.1

Egy szakértői rendszer általános felépítését mutatja az Ábra 2.

Tudásreprezentációs módszerek

Frame-ek

A frame-ek fogalmát Marvin Minsky vezette be és a következőképpen definiálta: a frame sztereotip helyzetek leírására alkalmas adastruktúra Tudásgyűjtő és ([Minsky 81]). Az egyes frameTudásmérnök TUDÁSBÁZIS karbantartó rendszer ekhez különböző típusú információk rendelhetők és köztük kapcsolatok Következtető definiálhatók. Munka memória mechanizmus A frame-ek csomópontok és kapcsolatok hierarchikusan szervezett hálózata, ahol a Felhasználói Nyomkövetö rendszer magasabb szinten lévő felület csomópontok általános, míg az alacsonyabban lévő Felhasználó csomópontok speciálisabb ismereteket tartalmaznak az adott fogalomról. Ábra 2. Egy szakértői rendszer felépítése Az ábrázolni kívánt fogalmakat osztályokba A rendszer tudását a tudásbázis tartalmazza, amit a tudásmérnök állít össze és tart karban. A tudásmérnök soroljuk, amiknek további alosztályai létezhetnek. a problématerület ismerője, aki átlátja a Mind az osztályoknak, mind az alosztályoknak problématerülethez kapcsolódó ismereteket és képes létezhetnek tulajdonságai, amelyek az adott osztályba azt rendszerezni. A felhasználó a felhasználói felületen tartozó fogalmak jellemzőit írják le (Ábra 3.). keresztül tud kommunikálni a rendszerrel, itt tudja Amennyiben ezen tulajdonságokhoz konkrét értéket leírni a problémát és ezen keresztül kapja meg a rendelünk, az osztály egy pédányát hozzuk létre. megoldást is. A felhasználó által leírt probléma a Mikó Balázs - [email protected]

Mesterséges intelligencia, Szakértői rendszerek A tulajdonságok értékei megadhatók a konkrét értékkel, egy eljárással, amely a tulajdonság értékét egyéb információkból határozza meg, vagy öröklödéssel, ami azt jelenti, hogy a tulajdonság értéke egy magasabb szinten megadott értékkkel egyezik meg. Egyéb eljárások is hozzárendelhetrők egy-egy tulajdonsághoz, amelyek akkor hajtódnak végre, ha valamilyen egyéb feltétel teljesül, például, az érték megváltozik, vagy a frissítése szükséges. Osztály X

Példány ...

Alosztály k

Példány 2

Alosztály l

Példány 1 Osztály X - Alosztály m

Alosztály m Tulajdonság 1

Tulajdonság 1

=

Érték 1

Tulajdonság 2

Tulajdonság 2

=

Érték 2

Tulajdonság 3

Tulajdonság 3

=

Érték 3

Ábra 3. Frame 3.2

Szabály alapú következtetés

A szabály-alapú következtetés (rule-based reasoning) nagyon közel áll az emberi gondolkodás bizonyos formáihoz. Gyakran döntünk ha - akkor típusú szabályok alapján. Ezt a gondolkodási folyamatot modellezi a szabály-alapú következtetés. A szabály-alapú rendszerek tudásbázisa részben tényekből, részben szabályokból áll. A tények az általunk vizsgálni kívánt világ zárt leírására szolgálnak. A szabályok ezen világmodell elemeire vonatkoznak. A szabályok feltétel-akció párosok, ami azt jelenti: ha a feltétel kielégül akkor az akciót végre lehet hajtani. A feltétel azon körülmények kifejezésére szolgál, melyek között a szabály egyáltalán aktivizálódhat. Az akció oldal adja meg, hogy mi történjen a szabály aktivizálódása nyomán. A szabálynak kétféle hatása lehet: részben módosíthatja a tényeket, részben input/output tevékenységet generálhat. A következtetési ciklusnak három fő lépése van (Ábra 4). Mintaillesztés

Adatbázis

Szabály bázis

Kiválasztás

Tüzelés

Ábra 4. Szabály-alapú következtetési ciklus A mintaillesztés kijelöli mindazon szabályokat, melyek feltételei illeszkednek a tényekre. Ekkor nem pusztán a feltételek logikai ellenőrzése, hanem a feltételek közt szereplő változók minden lehetséges módon való lekötése történik. Egy szabály többféle

Mikó Balázs - [email protected]

5 módon is illeszkedhet az adatbázisra, ezért valójában nem a szabályok tüzelnek, hanem azok példányai. Választáskor el kell dönteni, hogy a mintaillesztés során kijelölt szabálypéldányok közül melyik tüzeljen. A feladat megoldására többféle vezérlési stratégiát alkalmazhatunk. A leggyakrabban alkalmazott stratégiák a következők: • a legfrisebb tényekre illeszkedő; • a legspecifikusabb, azaz a legtöbb feltételt alkalmazó; • a legnagyobb prioritású, ha a szabályokhoz prioritás rendelhető, vagy • egy véletlenszerűen kiválasztott szabály tűzel. Egy szabály, lekötött, konkrét értékkel rendelkező változók mellett történő, végrehajtását tüzelésnek nevezzük. A tüzelés során módosulnak a tények, vagy input/output tevékenységek aktivizálódnak. A szabályok feldolgozása a következtető mechanizmusok alapján történheti: Szabály-alapú rendszerekben az alapvető következtetési mód az előreláncolás vagy adatvezérelt következtetés, melynek lényege a következő: ha a következtető mechanizmus talál olyan szabályt, melynek feltételeit a tények kielégítik, akkor végrehajthatja a szabályt, aminek hatására a tények módosulnak. Mindez ciklikusan addig folytatódik, míg van olyan szabály, amely "tüzelhet". A következtetés másik, gyakran alkalmazott módja az ún. hátraláncolt vagy célvezérelt következtetés. A következtetés egy célból indul ki és megvizsgálja, hogy a rendelkezésre álló tények alapján a cél igazolható-e. A mechanizmus előszőr a cél alapján kiválaszt egy szabályt, melynek akció oldalán a cél állítása szerepel. Ezután ellenőrzi, hogy a tények kielégítik-e ezen szabály feltételeit. Ha egy feltételre nincs illeszthető tényállítás, akkor azt az igazolandó célokhoz csatolja. Ez a folyamat mindaddig tart, míg előáll egy megoldás, vagy kiderül, hogy az adott cél az adott tények esetén nem teljesíthető. A gyakorlatban gyakran alkalmazzák a vegyes, mind előre-, mind hátraláncoló következtetési módot. Ekkor, ha a mintaillesztés egy bizonyos tény hiánya miatt nem sikerül, akkor ezt a tényt célként lehet kitűzni és hátraláncoló szabályok segítségével meg lehet próbálni a többi tényből levezetni. 3.3

Eset-alapú következtetés

Az eset-alapú következtetés (case-based reasoning) a probléma megoldás és gépi tanulás egyik legfrissebb megközelítési módja a mesterséges intelligencia módszerek között, amely nagy figyelmet kapott az elmúlt években. Az eset-alapú következtetés az emberi megismerés élettani elméletére épül, amely - egyes kutatások szerint - a megérzésre alapszik, vagyis az emberi tudás nem szabályoktól vagy egyéb formalizálható szerkezettől függ, hanem tapasztalatoktól. Az emberi

Mesterséges intelligencia, Szakértői rendszerek szakértők, ellentétben az adott szakterületen járatlan vagy kezdő emberekkel, képesek összekapcsolni egy példát egy előzővel, következtetni tudnak analógiák alapján az aktuális és a régebbi problémák között, használva a régi esetből következő megoldásokat, képesek felismerni és elkerülni a régi hibákat és hiányosságokat. Az eset-alapú tervezés tehát egy problémamegoldási minta, amely számos tekintetben alapvetően eltér minden más mesterséges intelligencia módszertől. Ahelyett, hogy kizárólag a problématerületből generált tudásra építene, vagy a problémaleírás és a következmény közötti összefüggéseket állítaná elő, az eset-alapú következtetés képes kihasználni a korábbi tapasztalatokban rejlő speciális tudást egy konkrét probléma megoldása során. Egy új probléma megoldása egy hasonló, régi eset visszakeresésével és annak az új helyzetben való alkalmazásával történik. A másik lényeges különbség az, hogy az eset-alapú következtetés hosszantartó, folyamatos tanulást valósít meg, mivel az új tapasztalat beépül a rendszerbe, így azonnal felhasználható a következő problémák megoldása során ([Kolodner 93]). Ez alapján az eset-alapú következtetés meghatározására a következő definíciót adhatjuk ([Aamodt 96]): Egy új probléma megoldása azáltal, hogy felidézünk egy korábbi, hasonló problémát, és felhasználjuk ennek megoldásából származó tudást és tapasztalatot. Az eset-alapú tervezés szóhasználatban az eset általában egy probléma helyzetet jelent. Egy olyan korábban tapasztalt helyzetet, amelyet megfigyeltünk és megtanultunk oly módon, hogy egy jövőben jelentkező probléma megoldására újra fel tudjuk használni. Erre hivatkozhatunk mint múltbeli eset, előző eset, tárolt eset vagy elfogadott eset. Teljesen hasonló módon az új vagy más elnevezéssel megoldatlan eset, az új, megoldásra váró probléma leírása. Az eset-alapú következtetés valójában egy probléma megoldásának és ebből a tapasztalatból való tanulásnak a ciklikus és integrált folyamata ([Aamodt 96]). Itt kell megjegyeznünk, hogy a probléma megoldás kifejezést szélesebb értelemben használjuk, a tudásbázisú rendszerek területén általánosan használt gyakorlattal összhangban. Ez azt jelenti, hogy a probléma megoldás nem feltétlenül az aktuális problémára választ adó konkrét megoldás automatikus keresését jeleni, elképzelhető, hogy bizonyos feladatokat a felhasználó old meg. Például a probléma értélmezését, a lehetséges megoldások generálását vagy a javasolt megoldás helyességének vizsgálatát stb. Egy eset jellemzően a következőket tartalmazza ([Watson 96]): • a problémát, amely leírja azt a világállapotot, amelyben az eset érvényes,


6 • a megoldást, amely kifejti a problémára adott megoldást és/vagy • a következményt, amely a világ állapotát írja le, miután az eset bekövetkezett. Egy eset leírására sokféle típusú adatot tárolhatunk, amelyeket a hagyományos adatbáziskezelés során már megszoktunk, sőt egyes rendszerek kihasználják a multimédia adta lehetőségeket is. A kérdés az, hogy milyen és mennyi adatot tároljunk. Erre vonatkozóan két szabály mondható ([Watson 96]): olyan adatokat kell tárolni, amelyek funkcionálisan szükségesek és könnyű beszerezni őket. Az Ábra 5. az eset-alapú következtetés folyamatát mutatja. Új probléma

Indexelés

Visszakeresés

Esetbázis

Hasonló esetek

Választás

Javasolt megoldás

Adaptálás Tanulás Ellenörzés

Megoldás

Ábra 5. Eset-alapú következtetés folyamata A legtöbb adatbáziskezelő rendszer indexeket használ az adatok visszakeresésének meggyorsítása érdekében. Az index a számítógépes adat struktúra része, amely lehetővé teszi az egyszerű nyilvántartást és a gyors visszakeresést. Ez az jelenti, hogy a számítógépnek nem kell a rekordok összes mezőjét végignézni keresés során, ami sokkal lassabb lenne. Eset-alapú következtető rendszerek is indexeket használnak a visszakeresés meggyorsítására. Az indexelés során ezt a kódot állítjuk elő. Az indexelés célja az eset jellegzetességeinek leírása, valamint az információ rendszerezése és tömörítése. Egy eset kétféle információt tartalmaz: • indexelt információt, amelyet a visszakeresés során használunk, és • nem indexelt információt, amely az esthez kapcsolódó információkat tartalmaz, de a visszakeresés folyamatában nem használjuk őket.

Mesterséges intelligencia, Szakértői rendszerek A jó index a következő tulajdonságokkal rendelkezik ([Watson 96]): • Egyértelmű kapcsolatban van a megoldással, vagyis a megoldást befolyásoló körülményeket írja le. • Leírja azokat a célokat, melyekhez az eset használható. • Elég abstrakt ahhoz, hogy tekintetbe vegye az esetbázis széleskörű jövőbeni használatát. • Elég konkrét ahhoz, hogy később is értelmezhető legyen. Az est-alapú rendszereknél az emlékezés a esetek memóriából történő visszakeresését jelenti. Általában ez két alfeladatból áll ([Kolodner 93]). Korábbi esetek felidézésének célja az, hogy kikeressen olyan ‘jó’ eseteket, amelyek megalapozzák a következtetés folyamatát, ami a következő lépésben történik. A visszakeresés az új eset tulajdonságainak felhasználásával történik. Ezeket indexként használva végigvizsgáljuk az esetbázist. A legjobb eset kiválasztása során kiválasztjuk a legigéretesebb esetet vagy eseteket az előző lépésben generált információk felhasználásával. Az eljárás célja, hogy megrostáljuk a szóbajöhető eseteket, így kiválasztva egy vagy néhány további feldolgozásra alkalmas esetet. Számos probléma merül fel, melyeket a visszakeresés során meg kell oldani ([Kolodner 96]). Az első az, hogy a számítógépnek meg kell adnunk, hogyan ismerheti fel, hogy egy eset alkalmazható egy új helyzetben. Ezt illesztési vagy hasonlóság-becslési problémának nevezzük. Amikor két eset nyilvánvalóan egyforma, ez nem túl nehéz, de gyakran azok az esetek, amelyek a leginkább használhatók, első ránézésre nem tűnnek túl hasonlónak, mélyebb elemzés szükséges, hogy nyilvánvalóvá váljon, hogy ezek valóban egyformák. Ez át is vezet bennünket az indexelés problémájára, melyről már szóltam korábban. Mivel az indexelés egy absztrakt szinten írja le az esetet, el kell tudni dönteni, az elvonatkoztatás milyen szintje alkalmas arra, hogy összehasonlítsuk az eseteket. A számítógépet képessé kell tenni arra, hogy kidolgozza egy eset részleteit. Gyakran elég kevés információ áll rendelkezésre az új szituációról, így ez csak kevés bázist biztosít más helyzetekkel való összehasonlítás során. Más esetben amit tudunk, az túl nyers ahhoz, hogy az összehasonlítást elvégezzük. Ezt a problémát helyzet-becslésnek nevezzük (situationassessment). Az utolsó nehézség egy hatékony keresési algoritmus elkészítése. A nehézséget az jelenti, hogy egy nagy eset könyvtárban kell megtalálni az alkalmas eseteket. Meg kell oldanunk azt a problémát, hogy a lehető legkisebb részét vizsgáljuk meg az esetbázisnak.


7 Miután az eset-alapú rendszer visszakereste a megfelelő eseteket, azok megoldását adaptálni kell az új eset sajátosságainak megfelelően ([Watson 96]). Az adaptáció során eltéréseket keresünk a kiválasztott és az aktuális eset között és ezután változtatásokat hajtunk végre a javasolt megoldásban. Az adaptációnak alapvetően két formája létezik: • szerkezeti adaptáció (structural adaptation), amely során a szabályokat és/vagy képleteket közvetlenül a visszakeresett megoldásra alkalmazzuk, • származtatási adaptáció (derivational adaptation) során az új esetre alkalmazzuk azokat a szabályokat és/vagy képleteket, melyekkel a régi megoldást is előállítottuk. Az eset-alapú rendszerek számos különböző technikát alkalmaznak, melyek bonyolultsága igen eltérő. A legfontosabbak a következők ([Watson 96]): Null adaptáció (null adaptation) a legegyszerübb adaptációs technika, melyet akkor alkalmazunk, ha a visszakeresett megoldás változtatás nélkül használható. Paraméter beállítás (parameter adjustment) egy szerkezeti adaptációs technika, amely összehasonlítja a visszakeresett és az aktuális esetek meghatározott paramétereit, hogy azokon keresztül módosítsa helyes irányba a megoldást. Reinstantiation alkalmazása során a régi megoldás bizonyos elemeit új elemekre cseréljük ki. Származtatási újrajátszás (derivational replay) során azokat az eljárásokat alkalmazzuk az új megoldás előállítására, amelyekkel a régi esethez tartozó megoldást előállítottuk. Ez a technika a probléma terület (domain) alapos ismeretét igényli. Modell-vezette javítás (model-giuded repair) kauzális modellt használ az adaptáció irányításához. Ez a technika is igényli a domain alapos ismeretét. A legtöbb kereskedelmi rendszer egyáltalán nem végez adaptációt. Egyszerűen felkínálja a legjobban illeszkedő esethez tartozó megoldást (null adaptáció) vagy lehetőséget biztosít a felhasználónak a kézi adaptálásra. Az esetek adaptálása, bármilyen módon történik is, az eset-alapú következtetés megvalósításának gyenge pontja. Az ellenőrzés során azt vizsgáljuk, hogy az adaptálás után előállt megoldás megfelelő-e. A megoldás tesztelésére számos, tárgykörtől függő technikát fejlesztettek ki. Bizonyos tárgykörök lehetőséget biztosítnak elemzési technikák alkalmazására, mások megkövetelhetik szimuláció végrehajtását, megint mások a megoldás helyességét meghatározó formális szabályoknak adnak helyet. Akármilyen eszközzel történik az ellenörzés, ezután ki kell értékelni az eredményeit. Ha a megoldás, bizonyos tárgykörtől függő kritériumok alapján elfogadható, a CBR rendszer elkészült a következtetéssel. Más esetben a megoldást újból

Mesterséges intelligencia, Szakértői rendszerek módosítani kell. Ekkor a módosítást a megoldás kiértékelésének eredménye vezérli. Az utolsó lépés a tanulás. Ha a megoldás nem volt megfelelő, meg kell keresni a hiba okát és meg kell tanítani, hogyan kerülheti el a következő alkalommal. Ha a megoldás megfelel, csatoljuk az eset-bázishoz mint sikeres megoldást. A eset-alapú rendszernek el kell döntenie, hogy megtanulja-e és ha igen milyen formában az elfogadott megoldást. Ez azt jelenti, hogy meg kell vizsgálni, vajon az új, sikeres megoldás elegendő mértékben különbözik-e a már ismert megoldásoktól. Ha a megtanulás mellett dönt, a következő kérdés, hogyan indexelje az új esetet, az absztrakció mely szintjén legyen megfogalmazva az új probléma. 3.4

Heurisztikák

A szakértői rendszerek a problémamegoldás során alkalmazhatnak úgynevezett heurisztikákat is. A heurisztikák tulajdonképpen ökölszabályok, amelyek nagyban leegyszerűsítik a problémamegoldás folyamatát az által, hogy korlátozzák a megoldás keresési terét. A heurisztika olyan algoritmizált feladatmegoldó módszer, mellyel ismert megoldási módszerekből kiindulva adott problémák újszerűen, automatikusan oldhatók meg. A heurisztikus módszerek bonyolult feladatok megoldására igyekeznek nem minden lehetséges utat kipróbálni, hanem hasonlósági alapon bizonyos feladatmegoldási típusok alapulvételével elindulnak egy-egy plauzibilis, tehát nem biztos, de valószínű megoldás felé ([Polinszky 72]). Más megközelítés szerint valamely probléma megoldásának olyan gyakorlatias, de matematikailag nem egzakt módszere, amelyben közelítő megoldások sorozatának segítségével nyerhető a megoldás egy elfogadható közelítése ([Kovács 95]). Tehát heurisztikának nevezünk minden olyan szabályt, következtetést, értékelést, elvet, amely egy bizonyos fajta szituációban többnyire érvényes, illetve működik, de nem mindig ([Mérő 2001]). A heurisztikák alkalmazásával elért eredmények jogosan töltik el az embert örömmel, hiszen éppe az a dolog lényege, hogy a megoldás sikere nem eleve biztos. Az ember lépten nyomon szinte mindegyik gondolatmenetében heurisztikus eljárásokat alkalmaz, mivel csak így tud a lehetőségek sokaságának, azok minden következményének végiggondolása nélkül, belátható idő alatt elfogadható módon cselekedni. A mesterséges intelligencia sem tud meglenni heurisztikák nélkül, mert a következtetésláncok összes ágának végiggondolása többnyire a leggyorsabb számítógépekkel is lehetetlen.


8 4.

Mesterséges neurális hálók

A tudásalapú rendszerekkel párhuzamosan megjelent egy új tudományága a mesterséges intelligencia kutatásokban, amely az emberi idegrendszert, az emberi agyat próbálta modellezni. A biológiai neurális hálók analógiájára mesterséges neurális hálókat hoztak létre és próbáltak vele különböző feladatokat megoldani. Jellemzőjük volt, hogy a problémát nem algoritmikusan oldották meg, hanem a természethez hasonlóan, mintákból tanulva. A mesterséges neurális hálók olyan, számítási feladatok megoldására létrehozott párhuzamos adatfeldolgozást végző adaptív eszközök, melyek eredete az emberi agy működésének modellezésére vezethető vissza (Ábra 6.) ([Anderson 83], [Shepanski 92]). Felépítésüket tekintve egyszerű, általában adaptív elemek sűrűn összekapcsolt hálózata illetve hierarchikus szervezete ([Hinton 92], [Camp 92]). A neurális hálókat a hálók topológiája, csomópontjaik karakterisztikája illetve az alkalmazott tanulási algoritmus határozzák meg.

Ábra 6. Neuronok 4.1

Történeti áttekintés

A mesterséges neurális hálózatok kialakulása egy igen régi tétel bizonyításával kezdődött. Ez a tétel egy híres német matematikustól, Hilbert-től (1862-1943) ered. Ő vetett fel 1900-ban 23 olyan matematikai problémát, amelyek megoldása szerinte a XX. Század matematikusainak fontos feladata lesz. Ezek közül az

Mesterséges intelligencia, Szakértői rendszerek egyik

így hangzott:

„Bizonyítsuk be,

x 7 + ax 3 + bx 2 + cx + 1 = 0

hogy a

hetedfokú egyenlet nem oldható meg pusztán kétváltozós függvények segítségével.” Ez a mondat látszólag nem kapcsolódik a neurális hálókhoz. Évek során rengetegen dolgoztak a probléma megoldásán, sokan megcáfolták Hilbert állítását, azonban 1957-ben egy Kolmogorov nevű matematikus bebizonyította, hogy nem csak kétváltozós függvényekkel oldható meg a feladat. Tétele szerint tetszőleges N-változós függvény felírható egyváltozós függvények segítségével. Ezen tétel szerint képesek a neurális hálók például folytonos, négyzetesen integrálható függvényeket approximálni![6] Így a mesterséges neurális hálózatokat ma már a tudomány majd minden ágában felhasználják különböző bonyolultságú feladatok megoldására, ahol a kimenet és bemenetek közti bonyolult összefüggések, függvények megalkotása nehéz és hosszadalmas feladat, vagy egyszerűen más módszerekkel megoldhatatlan. A természetes neuronok kutatásának hatására 1943-ban jelent meg McCulloch és Pitts neuronmodellje, ezt követte 1949-ben Hebb tanulással kapcsolatos eredményei. Természetesen ezután még jó néhány évet kellett várni az első mesterséges neuronokig, de az alapokat ez adta. Az egyszerű neuron modell nem volt más, mint többdimenziós bemenet komponenseinek súlyozott összegét meghatározó elem, melyet egy nem lineáris leképezés követ. Itt nem is a neuron felépítése volt az érdekes, hanem az a mód, ahogy eredményeket mutat fel. A tanulás itt azt jelenti, hogy a neuron a tudást reprezentáló minták alapján valamilyen átvitelt alakít ki. Ennek a modellnek az alapján alkotta meg 1958ban Rosenblatt a perceptront, ami egyszerű osztályozási feladatokat már meg tudott oldani. Ezt hamarosan követte 1960-ban Widrow és munkatársainak eredményei, ahol a neuronokat már hálózatba rendezték. Az ígéretes kezdet után hosszú megtorpanás következett mikor Marvin Minsky kimutatta, ezek a hálózatok csak lineárisan szeparálható osztályozási feladatok megoldására alkalmasak, ami a problémák csak egy kis százaléka. Bár megmutatta, hogy ha rétegekbe szervezzük a neuronokat, akkor képesek nem lineáris feladatok megoldására is, de nem volt tanítási algoritmus amivel a háló tanítható lett volna. Mivel Minsky a MIT professzora volt, eredményeit fenntartás nélkül elfogadta az akkori tudóstársadalom, a kutatások szinte teljesen leálltak. Mintegy 20 évet kellett várni arra, hogy a neurális hálók újra az érdeklődés körébe kerüljenek. Ezt a lökést 1982-ben Hopfield hálózata adta meg, amely képes volt NP-teljes feladatok megoldására (olyan feladatok, melyek megoldásainak száma a bonyolultság függvényében exponenciálisan nő, lásd utazó ügynök probléma). A következő jelentős Mikó Balázs - [email protected]

9 eredmény a hiba-visszaterjesztéses (backpropagation) algoritmus felfedezése volt, amit 1986-ban Rumelhart, Hinton és Williams publikált. A nyolcvanas évek második fele óta a neurális hálózatok reneszánszukat élik. Rengeteg publikáció jelenik meg, egyre több helyen alkalmazzák őket. Ebből jön egy probléma: az emberek hajlamosak túlértékelni, és olyan helyeken is alkalmazni akarják, ahol a hagyományos megoldás jobb. A természetes neurális hálók számos dologban sokkal jobbak, mint a számítógépes algoritmusok. Léteznek olyan feladatok, melyek az ember számára nagyon egyszerűek, algoritmust írni rá viszont szinte lehetetlen, hatékonysága, teljesítménye messze elmarad az ember teljesítményétől. Jó példa erre a karakterfelismerés. A biológiai neurális hálókat a nagy párhuzamosság és a tanulási képesség jellemzi, ez különbözteti meg őket a hagyományos számítástechnikai algoritmusoktól. Ezért vetődött fel az ötlet, hogy a természetet modellezni lehetne, és így olyan feladatokat, mint a mintafelismerés nagy hatékonysággal meg lehetne oldani. A felismerési feladatokon kívül más problémák is megoldhatók ezzel a módszerrel. Egyik tipikus alkalmazási terület olyan feladatok megoldása, ahol az algoritmus rendkívül bonyolult, vagy olyan számításigényes, hogy az eredményt reális időn belül nem tudja szolgáltatni. További előnyei a párhuzamos felépítésből adódik: egy robosztus rendszert kapunk, ami zajos, hiányos bemenetek esetén is képes jó megoldást adni. Neurális háló segítségével megoldható feladatok általában két típusra bonthatók: 1. Nem rendelkezünk azzal a tudással, amellyel a feladat algoritmikusan megoldható, mivel a rendszert befolyásoló összes paramétert és összefüggést ismernünk kellene, hogy a rendszer kimeneteit meghatározhassuk. Rendelkezünk viszont az adott problémáról véges számú adattal, amelyek alapján a mesterséges neurális háló képes az általánosításra, olyan szituációkban jó választ tud adni, ami a tanító adatok közt nem volt megtalálható. Létezik algoritmikus megoldása egy problémának, de a számítások mennyisége a feladat nagyságával exponenciálisan nő, kombinatorikai robbanás jön létre. Ezeknél a feladatoknál ezért megelégszünk inkább egy jó megoldással, amit gyorsan meg tudunk szerezni, mint a legjobbal, amit esetlegesen nem lehet reális időn belül meghatározni (NP-teljes probléma). A mesterséges neurális hálók alkalmasak optimalizálási feladatok elvégzésére, nem garantálható az optimális megoldás, de egy ahhoz közeli igen.

Mesterséges intelligencia, Szakértői rendszerek 4.2

10

Neurális hálók típusai

A neurális hálókat több szempontból vizsgálhatjuk. Az Ábra 7. egyfajta osztályozását és a legismertebb fajtáit mutatja ([Lippmann 87]). További példákat ismertet [Hecht-Nielsen 88], melyből kitűnik, hogy a kotatások e területen is igen szerteágazóak.

pozícióban álló, de különböző bitek számával egyezik meg ez a távolság ([Horváth 96]).

Neurális H álók Binális bemenet Nem felügyelt tanítás

Felügyelt tanítás

Hopfield háló

Folytonos és bináris bemenet

Carpenter/ Grossberg háló

Hanning háló

Nem felügyelt tanítás

Felügyelt tanítás

egy rétegû perceptron

több rétegû perceptron

Kohenen háló

Ábra 8. Neurális hálók osztályozása A Hopfield háló a legegyszerübb neurális háló, amely asszociatív memóriát valósít meg. Az egyrétegű visszacsatolt struktúrát John Hopfield amerikai biológus publikálta először ([Hopfield 82], [Hopfield 86]). A hálózatot leggyakrabban autoasszociatív feladatok megoldására használják ([Abu-Mostafa 85], [McEliece 87], [Horváth 95]). A Hopfield háló szerkezetét az Ábra 7. mutatja. Az alapmodell esetén a háló bemenetei binárisak. Az egyrétegű modellben a neuronok kimenetei minden neuron bemenetére súlyozott összeköttetéseken keresztül vannak visszacsatolva. A hálózat bemenetének a neuronok kezdeti állapotai tekinthetők, míg kimenetei ugyanezen neuronok állapotai a működés során. A megfelelően beállított súlyokkal rendelkező hálózattól azt várjuk, hogy az adott kezdeti konfigurációból kiindulva az ehhez legközelebbi stabil állapothoz tartozó pontban stabilizálódik ([Khanna 90]). X' o

X' 1

X'n-2

X'

n-1

X' o

X' 1

X'n-2

...

...

Xo

...

X1

Xm-2

X1

X n-2

X

Xm-1

Ábra 9. Hamming háló A Carpenter/Grossberg háló bináris értékekkel dolgozó, nem felügyelt tanulásra képes struktúra ([Lippmann 87]), melynek alap elemét az Ábra 10. mutatja. A háló bináris bemenetei az X értékek, kimenetei az Y értékek. Mint látható a csomópontok visszacsatolással rendelkeznek. Y0

Xo

X' n-1

Y

1

n-1

Ábra 7. Hopfield háló A Hamming háló a Hopfield háló továbbfejlesztése. A kiegészítés célja (Ábra 9.), hogy a zajjal terhelt bináris bemenetet megszűrje, így segítve a háló működését ([Lippmann 87]). A szűrést a Hamming távolság felhasználásával végzi a háló. A Hamming távolság két bináris kód eltérését, mint két térbeli pont geometriai távolságát értelmezi. Két azonos hosszúságú bitsorozat esetén az azonos


X

0

X

1

X

2

Ábra 10. Carpenter/Grossberg háló A Kohenen háló ([Kohenen 84]) az emberi agy azon tulajdonságát modellezi, hogy az agykéreg nagyrésze egymással összekötött, egy síkban elhelyezkedő neuronokból áll, mégis képes arra, hogy több dimenziós fogalmakkal is foglalkozzon. A Kohenen háló alapeleme a lineáris összegző funkciót

Mesterséges intelligencia, Szakértői rendszerek megvalósító processzáló elem. A processzáló elemek e hálóban nem rétegekben vannak elrendezve, hanem egy sík rácspontjaiban helyezkednek el. A hálózatban az előrecsatolás mellett visszacsatolás is be van építve, ez azonban csak a közvetlen szomszédos csomópontokra korlátozódik. A háló másik sajátossága, hogy nincs különálló kimeneti réteg: a rács minden csomópontja egyben kimeneti csomópont is. A háló egyes kimenetei a bemeneti komponensek súlyozott összegei, vagyis a háló a bemenetek és a kimenetek között lineáris kapcsolatot valósít meg. Az oldalirányú kapcsolatok rögzítettek, jellegük gerjesztő, ha egy processzáló elem önmagára való visszacsatolásáról van szó és gátló a többi esetben. Az Ábra 11. a Kohenen háló szerkezetét mutatja. X1 X

2

1

Y1

2

Y2

11 f(S) nemlineáris függvényként leggyakrabban az Ábra 13-n látható függvényeket alkalmazzák ([Vemuri 92], [Nelson 90]). +1 s > 0 Y= −1 s ≤ 0

a,

s>1  +1  Y =  S −1 ≤ S ≤ +1  −1 s<1 

b, X

n

Yn

k

Y=

1 − e − K⋅S ; K>0 1 + e − K ⋅S

Y=

1 ; K>0 1 + e − K ⋅S

Ábra 11. Kohenen háló 4.3

Perceptron háló

A legelterjedtebb hálótípus az egyenrangú bemenetekkel rendelkező memória nélküli neuronokból, úgynevezett perceptronokból ([Rosenblatt 59], [Minsky 69]) álló egy illetve többrétegű háló. Egy perceptron felépítését az Ábra 12. mutatja. Működése során a csomópont súlyozva összegzi a bemenetein jelentkező értékeket (xi), majd a súlyozott összeget (S) egy f(S) nemlineáris függvény segítségével transzformálja. Ily módon egy csomópont kimenete a következőképpen határozható meg:

S = ∑ xi wi ; n

Y = f(S) ahol: xi: wi: Y: X1 X2

a csomópont bemenetei; a bemenetek súlyai; a csomópont kimenete. w1 w2 S

Xn

wn

Ábra 12. Perceptron


f( . )

Y

c,

d, Ábra 13. Nemlinearitások a, lépcsőfüggvény; b, telítéses lineáris függvény; c, tangens hiperbolikusz függvény; d, szigmoid függvény A perceptron alapú háló ilyen egyforma elemekből épül fel. A háló, legegyszerűbb esetben három rétegből áll (Ábra 14.). A bemeneti réteg, amely értelem szerüen a bemeneti adatokat tartalmazza, össze van kötve a közbenső vagy más néven rejtett réteg minden csomópontjával. Ez a réteg szintén össze van kötve a kimeneti réteg összes elemével ([Monostori 96], [Knight 90], [Lippmann 87]). Több tétegű hálómodell esetén több rejtett rétegből áll a háló.


12 5.

S1 S2 S

S3 S4

Ábra 14. Perceptron háló A neurális hálók legfontosabb tulajdonsága az a tanulási képesség, amely az adaptivitásukat biztosítja, vagyis a bemeneti és kimeneti paraméterek közötti kapcsolat változtathatóságát. A tanítási folyamat lehet felügyelt, megerősített vagy felügyelet nélküli ([Diedrich 90], [Hinton 89]). Perceptron alapú hálók esetén a back-propagation eljárás a legelterjedtebb tanítási mód ([Hinton 92], [Freeman 92]). Ekkor a háló működését meghatározó súlyokat oly módon kell változtatnunk, hogy a várt és a mért értékek közötti hiba a legkisebbre csökkenjen. Egy tanítási ciklusban egy súlytényező értékét a következő képlet szerint módosítjuk: ∂E ( w) + α * ∆wi , j (n − 1) ∆wi , j (n) = −η * ∂wi , j , ahol ∆wi,j(n)

: az n-edik lépésben a wi,j súly változtatása, ∆wi,j(n-1) : az (n-1)-edik lépésben a wi,j súly változtatása, η : tanulási ráta, 0 < η< 1, konstans, α : momentum, 0 <= α < 1, konstans, E(w) : hiba, 2 1 E ( w ) = * ∑ t − o( w ) , 2 k t : megkivánt kimeneti érték, o : aktuális kimeneti érték, k : a tanítási minta elemszáma. A tanításhoz mintákat használunk, vagyis olyan példa bemeneti és kimeneti paramétereket, melyek közötti kapcsolatot szeretnénk meghatározni a háló segítségével. A tanítási folyamat addig tart, míg a háló a kivánt pontossággal elő nem tudja állítani a tanítási mintához hasonló teszt minta értékeit.

(


)

Kereső eljárások

A különféle kereső algoritmusok a megoldás felkutatásában, a keresés struktúrájában térnek el egymástól. Az algoritmusok keresési taktikájuk szerint lehetnek véletlenszerűek (vak keresők) és informáltak (heurisztikusak), az utóbbi azt jelenti, valamilyen tudatosság van a keresési irány megválasztásában. A közös minden kereső eljárásnál, hogy a keresési teret alkotó diszkrét pontok egyike (több jó megoldás esetén ez több pont is lehet) a megoldás. ([Sántáné 98]) A kereső eljárások lényege, hogy megpróbál eljutni egy kezdeti állapotból a megoldáshoz, ami az állapot teret alkotó pontok érintésével történik. A keresés folyamán az aktuális állapotból a következőre az algoritmus operátorait használva tudunk eljutni. Az új paraméter kombinációt kiértékelve kapunk információt az új állapot helyzetéről. Vak kereső eljárások 5.1

Szélességben-először kereső

Az egyik legegyszerűbb algoritmus az un. szélességben-először, ahol a kezdeti állapotból kiindulva az első szinten az összes lehetséges állapotot kiértékeljük és csak utána (ha nincs megoldás) veszi a következő szintet, amit az előző pontokból leszármaztatható összes lehetséges megoldás alkot. Működés vázlata: Kezdeti állapot generálása. - Ha ez a keresési tartományon kívülre esik, leállás, a keresés sikertelen; - Egyebkent: létrehozza a kezdeti állapot ágait, - y legyen a lehetséges ágak közül egy. Ciklus kezdete Ha y egy cél állapot, akkor leállás, és y értékét valamint a hozzávezető utat visszaadja eredményként. Egyébként - létrehozza y leágazásait; - eltárolja a hozzájuk vezető utat; - hozzáadja az ágazatokat a kezdeti állapothoz; - törli y-t; - y legyen a lehetséges ágazatok közül egy; Ciklus vége (ismétel) A szélességben-először kedvező tulajdonsága, hogy a keresési fa adott szintjét teljes részletességgel kielemzi és csak azután lép a következőre; így biztosan megtalálja a megoldást. Csomópontok számától függően a számítási igénye és a memória szükséglete óriási. Minden csomópontban 2n elágazást feltételezve mielőtt a célt a k-adik szinten megtalálnánk a legrosszabb esetben a csomópontok száma: 1+(2n)+(2n)2+(2n)3+…+(2n)k ≈ (2n)k. A memória igénye is ekkora mennyiségű csomóponthoz

Mesterséges intelligencia, Szakértői rendszerek kell, hiszen minden állapot jellemzőit le kell tárolni. Ezért ez az algoritmus csak a kisebb terjedelmű problémák megoldására alkalmas. A keresés részletes, de a memória igénye óriási. 5.2

Mélységben-először való keresés

Az un. mélységben-először keresés nem vizsgálja meg az összes lehetséges megoldást, hanem minden szinten kiválaszt egy pontot, és azt terjeszti ki. Ha elakadna egy holtágon, akkor addig megy vissza, míg nem talál egy olyan csomópontot, ahol van más keresési irány is. Működés vázlata: Kezdeti állapot generálása. - Ha ez a keresési tartományon kívülre esik, leállás, a keresés sikertelen; - Egyebkent: kezdeti állapotból kiválaszt egy paramétert, és létrehozza az ágazatait. - y legyen a lehetséges ágazatok közül egy. ciklus kezdete Ha y egy cél állapot, akkor leállás és y értékét valamint a hozzá vezető utat visszaadja eredményként. Egyébként - kiválaszt egy paramétert y-ból, és létrehozza a gyermekeit; - választ a két utód közül, és eltárolja a hozzá vezető utat; - törli y-t; - hozzáadja a választott gyermeket a kezdeti állapothoz, és ez legyen y; Ciklus vége (ismétel) A keresés memória igénye csekély, számítási igénye a mélységgel lineárisan nő. Az egyes szinteket nem vizsgálja meg teljes részletességgel, hanem valamennyi szinten kiválaszt egy paramétert és azt terjeszti ki, így az optimális megoldást szinte biztosan nem találja meg. 5.3

Korlátozott mélységű keresés

A korlátozott mélységű keresés teljes, feltéve, hogy a megoldás adott mélységen belül van. Az egyes csomópontokat addig terjeszti ki amíg az az adott mélységi korlát felett van. A korlát mélységéig teljes szélességben megvizsgálja a tartományt, és ha a megoldás nincs mélyebben, mint a korlát, akkor biztosítva van, hogy megtalálja a megoldást. Ebből jól látszik, hogy a mélységi korlát megválasztása döntő fontosságú a eredmény feltárásában. Általában célszerű a feladat sajátosságából kiindulni, és ez alapján felvenni egy értéket. 5.4

Iteratív mélyítés

Az iteratív mélyítés lényege, hogy az adott mélységig teljes szélességben keresi a kedvező pontot, és ha ezen a részen nem akad rá, akkor kitolja a Mikó Balázs - [email protected]

13 keresés határát, addig folytatva a kutatást, és a mélyítést, míg meg nem találja az optimumot. Az így megalkotott algoritmus az eddigiek tulajdonságait összegzi; kis memória igény, számítási igény exponenciálisan nő a mélységgel. A keresés teljes, biztosan megtalálja az optimumot, és nem tárja fel jobban a megoldási teret, mint azt szükséges lenne. Heurisztikus kereső eljárások A másik keresési eljárás típus a heurisztikus keresés, amely annyiban különbözik a korábbiaktól, hogy a keresés során egy kevés információt is felhasznál a pillanatnyi helyzetének kiértékeléséből, így javítható a keresési idő, csökkenthető a szükséges tárolókapacitás. A heurisztikát a még fel nem derített csomópontok kiértékelésére használjuk, és ebből következtetünk a pillanatnyi helyzetünk és a cél távolságára. Ez a kiértékelés, mivel csak becslés, lehet félrevezető is, de a kockázat megéri, mivel már kevés egyszerűsítő körülmény figyelembevétele is nagy mértékben csökkentheti a keresési teret (számítási igényt és a tárolási kapacitást). A heurisztikus kiértékelő függvények egy mérőszámmal jellemzik az optimális pont távolságát a keresés pillanatnyi helyétől. A jó kiértékelő függvény a valós eredményt mindig alulról közelíti. Ez nagyon fontos az algoritmus megfelelő működéséhez. Ilyen, heurisztikus kiértékelő függvényeket a legegyszerűbben a gyakorlati példa egyszerűsítésével származtathatunk. 5.5

Legjobbat-először keresés

Egyik fajtája a heurisztikus keresőknek a legjobbat-először keresés, mely az adott pontban a választási lehetőségek közül azt választja, amelyik a legközelebb van a célhoz. Alkalmazásbeli hátrány, hogy nem biztos, hogy megtalálja az optimumot. Egy korábbi elágazásnál a jobbnak látszó csomópont választása után már nincs mód a korrigálásra. Ha esetleg kiderülne, hogy egy másik ág, mely távolabbinak tűnt, tartalmazza az optimumot, nincs lehetőség a javításra. Működés vázlata: Kezdeti állapot generálása. - Ha ez a keresési tartományon kívülre esik, leállás, a keresés sikertelen; -Egyebkent: A lehetséges ágazatok kiértékelése, - legyen a legkedvezőbb ág y. ciklus kezdete Ha y egy cél állapot, akkor leállás és y értékét illetve a hozzá vezető utat visszaadja eredményként. Egyébként - létrehozza y gyermekeit; - legkedvezőbb ágazatot kiválasztása; - a hozzá vezető út eltárolása; - törli y-t;

Mesterséges intelligencia, Szakértői rendszerek - a választott ág legyen y; Ciklus vége (ismétel) A memória szükséglete nem nagy, a számítási igénye a mélységgel exponenciálisan nő. Ezt az algoritmust egy kicsit tovább fejlesztve kapunk egy olyan eljárást, ami már képes megtalálni az egyetlen megoldást. 5.6

A*

Az A* algoritmus lényege, hogy a keresés pillanatnyi állapotának célfüggvény értéke (g), és a keresés adott pillanatában az előrebecsült optimális pontig bekövetkező célfüggvény érték változás (k) összege (f) minimális legyen.

f (n ) = g (n ) + k (n ) → min Ennak következtében a keresés hatékonyságát jelentősen befolyásolja, hogy a becsült költség mennyire fedi a valóságot. Ha nagyon eltér attól, akkor a keresés szélesebb területet érint és a memória igénye, számítási ideje nagyon megnő. Működés vázlata: Kezdeti állapot generálása. Ha ez a keresési tartományon kívülre esik, leállás, a keresés sikertelen. ciklus kezdete - f meghatározása a választható csomópont-okban, választás az f min függvény figyelembe vételével, legyen y a választott ágazat. Ha y egy cél állapot, akkor leállás és y értékét és a hozzá vezető utat visszaadja eredményként. Egyébként - létrehozza y gyermekeit; - eltárolja a hozzájuk vezető utat; - hozzáadja a gyermekeket a kezdeti állapothoz; - törli y-t; Ciklus vége (ismétel) Az algoritmus hibája, hogy keresés közben a tárolandó adatmennyiség óriási méretet ölthet, míg az idő szükséglet elfogadható mértékű marad. A vak keresésnél is felmerülő hasonló problémára a mélységi korlátozást alkalmazták, és iteratív mélyítéssel sikeresen oldották meg a problémát. Ezért itt is ezt a módot választották, a teljesség és az optimalitás megtartása mellett, azonban ebben az esetben nem a mélységet korlátozták le, hanem az f (n ) értékét. 5.7

IDA* (iterative deepening)

Az IDA* a mélységben először kereséssel azon pontokat vizsgálja meg, melyek költségei, f (n ) kisebbek, mint a megadott korlát. Ha nem talál


14 megoldást, akkor növeli a korlátot, és újra indítja a keresést. Az IDA* ugyanolyan feltételek mellett optimális és teljes, mint az A*. Működés vázlata: Kezdeti állapot generálása. Ha ez a keresési tartományon kívülre esik, leállás, a keresés sikertelen. ciklus kezdete -f meghatározása a választható leágazásokban. Ha túlléptük a korlátot, akkor ciklus vége. Ha nem, akkor választás az f min függvény figyelembe vételével, legyen y a választott ágazat. Ha y egy cél állapot, akkor leállás, és y értékét és a hozzá vezető utat visszaadja eredményként. Egyébként - létrehozza y lehetséges ágazatait; - törli y-t; Ciklus vége (ismétel) Ha f min > f , korlát növelése, és utána újra indítjuk a ciklust. A memóriaigénye csak lineárisan nő a tartomány mélységével, a keresés ideje pedig exponenciálisan (ahogy az eddigi algoritmusok mindegyikénél volt). Az időt jelentősen befolyásolja a becslés pontossága. Ha becslés pontatlan, akkor az algoritmus szélesebb területen vizsgálja át teret. Ez a keresési időt és a memória igényt is megnöveli. Azoknál a feladatoknál, melyek esetében csak a megoldás a fontos, és a hozzá vezető út lényegtelen, illetve a keresési tartomány diszkrét pontokból áll, és egy hálóként fedi le azt, akkor használhatók az iteratív javító algoritmusok. Iteratív javító algoritmusok Bizonyos feladattípusoknál a keresési térben a csomópontok által létrehozott tartomány egy domborzati térképhez hasonlítható a legjobban, ahol a magaslati mérőszámok a pontok jósági foka. A célfüggvénytől függően kétféle helyzet alakulhat ki, az egyik esetben minél magasabban van egy pont annál jobb a megoldás, itt maximumot keresünk, a másik esetben minél alacsonyabban van a pont, annál jobb a megoldás, itt minimumot keresünk. Az algoritmusok működése is eltérő az előzőektől, hiszen most egy háló jellegű felületen kell mozogni, míg az előző esetekben egy fa struktúrán. Egy adott pontból a továbbjutás oly módon történik, hogy a szomszédos pontokat kiértékeli, és azok közül választ egyet az algoritmusra jellemző módon. 5.8

Csúcsra-mászás

A csúcsra-mászás algoritmus az összes szomszédos pontot kiértékeli, és a célfüggvényérték szempontjából a legkedvezőbbet választja ki. Az algoritmus hátránya, hogy sok lokális szélsőértékkel rendelkező keresési tér

Mesterséges intelligencia, Szakértői rendszerek esetén elakad, és nem tud tovább lépni egy megmászott helyi csúcs esetén, de hasonlóképpen elakad, ha egy plató jellegű felületre téved, a keresés sikere tehát függ a felület alakjától. Működés vázlata: Kezdeti állapot generálása, legyen ez y. Ha ez a keresési tartományon kívülre esik, leállás, a keresés sikertelen. ciklus kezdete Ha y egy cél állapot, akkor leállás és y értékét adja vissza eredményként; Egyébként - létrehozza y gyermekeit (közvetlen szomszédjait). - Az utódok kiértékelése, n legyen a lehetséges ágazatok közül a legjobb. - törli y-t, és y := n . Ciklus vége (ismétel); Az algoritmus nem tárolja a keresési fát, csak a pillanatnyi helyzetének adatait, így a memóriaszükséglete igen kicsi. A számítási idő lineárisan nő az érintett csomópontok számával. Olyan terepen, ahol elakadhat, mert helyi maximumok is vannak, egy másik algoritmust érdemes használni, ami ezt a problémát meg tudja oldani. 5.9

Tabu keresés

A tabu keresés az első lokális csúcsig csúcsramászás algoritmusa szerint működik, majd onnét a kiértékelés után elfogad rosszabb megoldásokat is, de ezen pontok koordinátáit mindig eltárolja egy tabu listában, hogy az a veszély ne álljon fent, hogy a következő lépésben oda kerül vissza. Működés vázlata: Kezdeti állapot generálása, legyen ez y. Ha ez a keresési tartományon kívülre esik, leállás, a keresés sikertelen. ciklus kezdete Ha y egy cél állapot, akkor leállás és y értékét adja vissza eredményként; egyébként - létrehozza y gyermekeit (közvetlen szomszédjait). - az utódok kiértékelése, n legyen a lehetséges ágazatok közül a legjobb. Ha n rosszabb, mint y, akkor legyen n a szomszédos pontok közül valamelyik, és y-t tárolja a tabu listában. Ha nem rosszabb, törli y-t, és y:=n. Ciklus vége (ismétel); A memória igénye nagyobb, mint a csúcsra-mászás algoritmusé. Az idő igénye az érintett pontokkal lineárisan nő. A tabu keresés gyenge pontja, hogy miután felmászott a csúcsra, és elakadt, csak akkor enged meg egyéb stratégiát.


15 5.10

Szimulált hűtés

A szimulált hűtés a tabu keresés továbbfejlesztett változata, előnye az egyenetlen felületű térben mutatkozik meg, ahol egy csúcsra-mászás tehetetlen a sok helyi szélsőértékekkel. A stratégiabeli különbség, hogy a keresés első pillanatától kezdve megengedi a rontó lépéseket. A környező pontokból véletlenszerűen kiválaszt egyet, és ha az javít a jelenlegi helyzeten, akkor megteszi azt a lépést, ha nem, akkor a rontás mértékétől, és egy valószínűségi paramétert figyelembe véve dönti el, hogy mit tegyen, elfogadja, vagy válasszon egy másik irányt. Ez a valószínűségi paraméter egy un. hőmérsékletváltozó, mely a keresés során csökken, és így a rossz döntések elfogadásának valószínűsége is csökken a megoldás felé haladva. Végül csúcsra mászássá egyszerűsödik. Működés vázlata: Kezdeti állapot generálása, legyen ez y. Ha ez a keresési tartományon kívülre esik, leállás, a keresés sikertelen. ciklus kezdete Ha y egy cél állapot, akkor leállás és y értékét adja vissza eredményként; Egyébként - létrehozza y gyermekeit (közvetlen szomszédjait). - választ egyet a lehetséges ágazatok közül, ez legyen n. Ha n rosszabb, mint y, akkor döntse el választhatóe: nem: ugorjon a 4-es ponthoz; igen: ugorjon a következő pontra; Ha n jobb, mint y - törli y-t, és y :=n. Ciklus vége (ismétel); A memória igénye nem nagyobb, mint a csúcsra mászásé. A számítási idő lineárisan nő az érintett pontok számával. Az eljárás roppant nagy előnye, hogy ha a hőmérséklet paramétere lassan csökken, megtalálja az optimális megoldást. 5.11

Genetikus algoritmusok

A genetikus algoritmusok, melyek alapjait John H. Holland alkotta meg ([Holland 75]), olyan numerikus szélsőérték kereső eljárások, amelyek biológiai párhuzamra, az evolúció mechanizmusára épülnek. Az élőlény-populációk zöme két alapvető folyamat, a természetes szelekció és az ivaros szaporodás révén fejlődik. A természetes szelekció dönti el, hogy a populáció mely tagjai maradnak fenn és szaporodnak, az ivaros szaporodás pedig az utódok génjeinek keveredését és rekombinációját biztosítja. E génkeveredés révén a populációk sokkal gyorsabban fejlődhetnek, mint ha az utódok pusztán valamelyik szülőjük génjeinek egy-egy másolatát hordoznák és e gének csak elvétve, mutációkkal változnának meg. A természetes szelekció alapelve igen egyszerű: ha egy

Mesterséges intelligencia, Szakértői rendszerek élő szervezet bizonyos „alkalmassági vizsgákon” elbukik, például egy mutáció során megváltozott a színe nem rejti el a környezetben az ellenségei felismerik és hamar elpusztul. A genetikus algoritmusok ezt a folyamatot modellezik és alkalmazzák keresési problémák megoldására. A genetikus algoritmusok sztochasztikus keresési algoritmusoknak tekinthetők, ahol a paramétertér feltérképezése és az iterációnként egyre jobb megoldások előállítása az eddigi kereső eljárásoktól eltérő módon történik. Más szélsőérték-keresési eljárások - akár a gradiens módszer, akár a véletlen keresés - a paramétertérben egy pontot mozgatnak és a pont minden egyes állapotában - ami egy lehetséges megoldásnak felelt meg kiértékelik a kritériumfüggvényt, majd ennek eredményétől függően folytatják az eljárást. A genetikus algoritmusok ezzel szemben nem különálló pontokban vizsgálják a kritériumfelületet, hanem egyszerre több ponton értékelik ki, tehát egy lépésben a megoldások egész halmazával dolgoznak. A halmaz elemei különböző sikerrel oldják meg a feladatot, ami szélsőértékkeresésnél azt jelenti, hogy a populáció elemei a kritériumfüggvény különböző pontjait határozzák meg. E pontok között lesznek olyanok, amelyek a globális szélsőértékhez közelebb esnek és lesznek e megoldástól távolabb eső pontok is. A populáció elemei tehát a feladat szempontjából eltérő tulajdonságúak. A genetikus algoritmusoktól azt várjuk, hogy a természetes szelekció mintájára egy látszólag spontán fejlődés során egy adott populációból olyan újabb populációt, ill. olyan újabb és újabb populációkat hozzanak létre, amelyekben a jó megoldáshoz közeli megoldások egyre nagyobb számban lesznek megtalálhatók és amelyekben a gyenge eredményt szolgáltató elemek egyre ritkulnak. Bizonyos szempontokból tehát a genetikus algoritmusok a véletlen kereséssel rokonítható, hiszen itt is a teljes keresési tér valamilyen feltérképezéséről van szó. A genetikus algoritmus azonban - szemben a véletlen kereséssel - nem vakon keres. A keresés az egymást követő lépésekben egyre inkább a kritériumfüggvény szélsőérték helyei környezetére koncentrálódik. A genetikus algoritmusok a megoldások egy halmazával dolgoznak, amit populációnak nevezünk. A populáció egyes elemei az egyedek, amelyek kromoszómákból álló genetikai kóddal vannak reprezentálva. Ezen genetikai kód általában bináris, tehát 0 vagy 1 értékkel rendelkezik, de léteznek ettől eltérő megoldások is. Ez az egyed genotípusa. Az egyedekkel kapcsolatban két fogalmat kell még megemlíteni. Életképes az az egyed, amely megfelel az összes környezeti feltételnek, vagyis az egyed által reprezentált megoldás kielégíti a feladatban megfogalmazott korlátozásokat. Az egyed tulajdonságait fenotípusnak nevezzük. Az egyed jóságát a rátermettség határozza meg, ami a megoldáshoz tartozó célfüggvény értéket jelenti. Mikó Balázs - [email protected]

16 Egy populáció fejlődése alapvetően kétfajta eljárás, úgynevezett genetikai operátor ismételt alkalmazásával történik. Az első genetikus operátor az úgynevezett keresztezés, amely során két egyedből két újabb egyedet hozunk létre. Ez oly módon történik, hogy az egyedeket reprezentáló karakterlánc mentén véletlenszerűen keresztezési pontokat jelölünk ki, és az így létrejött kódszegmenseket kicseréljük a szülők között (Ábra 15). 011011000101101 100111101100100

01101100

0101101

10011110

1100100

01101100

1100100

10011110

0101101

Ábra 15. Keresztezés A másik genetikus operátor az úgynevezett mutáció. Ennek során egyetlen egyed kódját módosítjuk oly módon, hogy ugyancsak véletlenszerűen mutációs pontokat jelölünk ki és ezen pontoknál található kromoszómák értékét megváltoztatjuk (Ábra 16.). 011011000101101

011011010101101

Ábra 16. Mutáció A genetikus algoritmusok általában a következő működésűek (Ábra 17.). Először véletlenszerűen létrehozunk egy életképes egyedekből álló kezdeti populációt, majd meghatározzuk az egyedek életképességét és e szerint sorbarendezzük őket. Ezt követően létrehozzuk az új életképes egyedeket a kiválasztás, keresztezés és mutáció eljárások segítségével. Az új egyedek rátermettségének meghatározása és újabb sorbarendezés után a populáció méretét az eredeti méretre csökkentjük, eltávolítva a kevésbé jó tulajdonságokat mutató egyedeket. A populáció fejlődése addig tart, amíg a populáció nem homogenizálódik, vagyis valamennyi egyed egyenértékűvé nem válik.


17 • mutációval létrehozott egyedek aránya, az úgynevezett mutációs ráta, • a keresztezési pontok száma, • a mutációs pontok száma.

Paraméterek beállítása

Kezdeti populáció generálása

Kiértékelés, Sorbarendezés

Kiválasztás

Keresztezés

Mutáció

Kiértékelés, Sorbarendezés

6.

Felkészülést segítő kérdések

1. 2.

Mi a mesterséges intelligencia? Milyen irányzatai vannak a mesterséges intelligencia kutatásoknak? Mi a mesterséges intelligencia kutatások célja? Mi az intelligencia? Mi a szakértői rendszer? Mi a szakértői rendszerek alkalmazásának közös vonásai? Ismertesse a szakértői rendszerek alkalmazásának előnyeit és hátrányait! Ismertesse a szakértői rendszerek két típusát! Milyen jellemzői vannak egy szakértői rendszerrel támogatható problématerületnek? Ismertesse a szakértői rendszer általános felépítését! Mi a szakértői keretrendszer? Ismertesse az alapvető szakértői rendszer problématípusokat! Ismertesse a frame fogalmát! Ismertesse a szabály alapú rendszerek jellemzőit! Ismertesse a szabály alapú következtetési ciklust! Mi a különbség az adat és a célvezérelt következtetés között? Mi az eset alapú következtetés? Ismertesse az eset alapú következtetés folyamatát! Mi a mesterséges neurális háló? Osztályozza a neurális hálókat, írjon példákat! Ismertesse a perceptron felépítését és működését! Milyen feladatok megoldására alkalmasak a neurális hálók? Mi a kereső eljárások két fő csoportja? Írjon példákat! Ismertesse a genetikus algoritmusok alapfogalmait! Ismertesse a genetikus algoritmus működési folyamatát! Milyen paraméterek befolyásolják a genetikus algoritmus működését?

3. 4. 5. 6.

Leállási feltétel

7. STOP

Ábra 17. Genetikus algoritmus felépítése Ezen algoritmus tömören a következő módon írható le: program genetikus algoritmus; begin Állítsd be a folyamat fő paramétereit; Töltsd fel a kiindulási populációt; Értékeld ki a populáció egyedeinek rátermettségét; Rendezd sorba az egyedeket csökkenő rátermettség szerint; while leállási feltétel nincs kielégítve do begin Válaszd ki az átkereszteződésre szánt egyedeket; Végezd el az átkereszteződést; Válaszd ki a mutációra szánt egyedeket; Végezd el a mutációt; Értékeld ki az új egyedek rátermettségét; Rendezd az új és régi egyedeket csökkenő rátermettség szerint; A legkisebb rátermettségű egyedek eltávolításával csökkentsd a populációt eredeti méretére; end; end. A genetikus algoritmus működését a következő paraméterek határozzák meg: • a populáció mérete, • a kiválasztás stratégiája, • keresztezéssel létrehozott egyedek aránya, az úgynevezett keresztezési ráta,


8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26.


7.

18

Függelék

7.1

Neurális háló A csomópontok kimeneti értéke: Jj

w i,j

o

Oj

w j,k

p

Oj =

Jk

Si

1 1+ e

Pk

Pk =

− ( J oj − J 0o j )

1 1+ e

− ( J kp − J 0pk )

,

J oj = ∑ S i ⋅ wi , j i

,

J kp = ∑ O j ⋅ w j , k j

A neurális háló tanítása - back propagation

7.2

A tanítási folyamat során meghatározzuk az egyes súlyok értékét. A háló tanításához többek között a back propagation eljárást alkalmazhatjuk. 7.2.1

Back propagation

A tanítás során mintákat mutatunk a hálónak, amelyek tartalmazzák a bemenõ és kimenõ adatokat. A súlyok kezdeti értékeit oly módon változtatjuk, hogy az aktuális kimenet és a minta alapján megkívánt kimenet eltérése a lehetõ legkisebb legyen. Ez alapján a következõképpen kell módosítani a súlyokat:

∂E + α * ∆wi , j (n − 1) ∂wi , j ∂E ∆w j , k ( n) = −η * + α * ∆w j , k ( n − 1) ∂w j , k ∂E ∆J ojo (n) = −η * o + α * ∆J ojo (n − 1) ∂J oj ∂E ∆J okp ( n) = −η * p + α * ∆J okp ( n − 1) ∂J ok ∆wi , j (n) = −η *

, ahol (n) (n-1) η α E

: hiba,

: az n-edik lépésben a paraméter változtatása : az (n-1)-edik lépésben a paraméter változtatása : tanulási ráta, 0 < η< 1, konstans (0.9) : momentum, 0 <= α < 1, konstans (0.4)

E=

1 2 * ∑ (tk − Pk ) 2 k tk : megkivánt érték Pk : aktuális érték



19

∂E   = ∑ (tk − Pk ) ⋅ Pk ⋅ (1 − Pk ) ⋅ w j , k  ⋅ O j ⋅ (1 − O j ) ⋅ Si ∂wi , j  k  ∂E = (tk − Pk ) ⋅ Pk ⋅ (1 − Pk ) ⋅ O j ∂w j , k ∂E   = ∑ (tk − Pk ) ⋅ Pk ⋅ (1 − Pk ) ⋅ w j , k  ⋅ O j ⋅ (1 − O j ) o ∂J oj  k  ∂E = (tk − Pk ) ⋅ Pk ⋅ ( Pk − 1) ∂J okp 7.2.2

A tanítási folyamat algoritmusa

A háló tanítása során a következõ algoritmust használjuk: 1. Véletlenszerűen felvesszük a súlyok értékét. 2. Meghatározzuk a háló hibáját (összhiba és/vagy legnagyobb egyedi hiba). 3. Beolvasunk egy tanítási mintát. 4. Elvégzünk egy iterációt a mintán. 5. Ha nincs vége a fájlnak ⇒ 3. 6. Meghatározzuk az összhibát és/vagy a legnagyobb egyedi hibát a teszt mintára. 7. Ha a hiba nagyobb a megengedettnél ⇒ 3. 8. Ellenõrizzük az eredményeket a tesztmintákon. 9. Meghatározzuk a háló hibáját (összhiba és/vagy legnagyobb egyedi hiba). 10. Ha a hiba nagyobb a megengedettnél felveszünk egy újabb csomópontot a rejtett szinten ⇒ 1. 11. Vége. 7.3

Jellemző válogatás - Feature selection

Adott egy n elemű tanítási minta, melynek jellemzőit egy D elemű Y halmaz írja le. A feladat: kiválasztani Yból egy olyan d elemszámú X halmazt, amelyre a J(.) kritériumfüggvény értéke maximális ([Devijver 82]). X={xi | i = 1,2, ..., d; xiεY};

Y={yj | j = 1,2, ..., D};

D>d

Generalized Sequential Forward Selection Algorithm (GSFS) 1. X halmaz üres 2. n=0 3. Létrehozunk (D-n) számú, X'k=X+yj halmazt (k=1...(D-n)). 4. Meghatározzuk Jk=J(X'k), k=1...D-n. 5. X=X'k ha Jk=MAX 6. n=n+1 7. ⇒ 3. Az algoritmus futása során ciklusonként felírandó a kiválasztott jellemző sorszáma illetve a kritériumfüggvény értéke.

[

R = j , J k , MAX

]

Kritérium függvény:

(

n n 1 ⋅ ∑∑ δ ξ l , ξ m 2 ⋅ n 2 l =1 m =1 ξ l = [x1, l , x2,l ,..., xd ,l ]

Jk =

)

Euclidészi távolság:

δE =

d

∑ (ξ j =1

l, j

− ξ m, j )2



8.

20

Irodalom

[Aamodt 96]

A. Aamodt, E. Plaza: Case-Based Reasoning: Foundational Issues, Methodological Variations and System Approaches; Artificial Intelligence communications, Vol.7. No.1. 1996. Internet dokumentum: http://www.iiia.csic.es/ People/enric/AICom.html#RTFToC1

[Abu-Mostafa 85]

Y.S. Abu-Mostafa, j.StJacques: Information capacity of the Hopfield model; IEEE Transaction on Information Theory, 31(4) July 1985. pp.461-464.

[Albert 98]

Albert János: Az idegrendszer korai evolúciójának számítógépes modellezése; Megismeréstudomány és mesterséges intelligencia, Szerkesztette: Pléh Csaba, Akadémiai kiadó, Budapest, 1998.

[Anderson 83]

J.A. Anderson: Cognitiv and psychological computation with neural models; IEEE Transaction on systems, man and cybernetics, 13(5) September/October, 1983. pp. 799-815.

[Bahrami 88]

A. Bahrami: Design artificial intelligence based software; Halsted Press, New York, 1988.

[Beardon 89]

C. Beardon: Artificial intelligence terminology, Ellis Horwood Ltd., 1989.

[Berei 62]

Új magyar lexikon, Szerkesztette: Berei Andor; Akadémiai Kiadó, 1962.

[Bielawski 91]

L. Bielawski, R. Lewand: Intelligent systems design; John Wiley and Sons, New York, 1991.

[Bounet 88]

A. Bounet, J-P. Haton, J-M. Truoug-Ngoc: Expert systems: principles and practice; Prentice Hall, New York, 1988.

[Camp 92]

D. van Camp: Számítógép-neuronok; Tudomány 1992. November, pp. 116-118.

[Chien 92]

Y-T Chien, J. Liebowitz: Artificial Intelligence, in Enciclopedia of physical science and technology Vol 2., Academic Press, 1992.

[Devijver 82]

P.D. Devijver, J. Kittler: Pattern recognition: a statistical approach; Prentice Hall 1982.

[Diedrich 90]

J. Diederich: Artificial neural networks: concept learning; IEEE Comp. Soc. Press, Washington, 1990.

[Durkin 94]

J. Durkin: Expert systems; Prentice Hall, 1994.

[Erdélyi 97]

A technológia management informatika eszközei, információ rendszerek I-II.; Szerkesztette Erdélyi Ferenc, Miskolc, 1997.

[Érdi 98]

Érdi Péter: A kisérleti episztemológia nagy kísérlete: a McCulloch-centenárium elé; Megismeréstudomány és mesterséges intelligencia, szerkesztette: Pléh Csaba, Akadémiai kiadó, Budapest, 1998.

[Freeman 92]

J.A. Freeman, D.M. Skapura: Neural networks: algorithms, applications and programming techniques; Addison-Wesley 1992.

[Gottinger 90]

H.W. Gottinger, H.P. Weimann: Artificial intelligence: a tool for industry and management; Ellis Hornwood Ltd., 1990.

[Harmon 85]

P. Harmon, D. King: Expert systems: artificial intelligence in bussiness; John Wiley and Sons, New York, 1985.

[Harmon 88]

P. Harmon, R. Maus, W. Morrissey: Expert systems: tools and applications; John Wiley and Sons, New York, 1988.

[Harmon 90]

P. Harmon, B. Sawyer: Creating expet systems for business and industry; John Wiley and Sons, New York, 1990.

[Hecht-Nielsen 88]

R. Hecht-Nilsen: Neurocomputing: Picking the human brain; IEEE Spectrum 25(3) 1988. pp.36-41. (in [139])

[Hinton 89]

G.E. Hinton: Connectionist learning procedures; Artificial Intelligence 40(1) 1989. pp.143150.

[Hinton 92]

G.E. Hinton: Hogyan tanulnak az idegi hálózatok?; Tudomány, 1992. November, pp. 99-106.



21

[Holland 75]

J. H. Holland: Adaption in Neural and Artificial Systems; MIT Press 1975.

[Hopfield 82]

J.J. Hopfield: Neural networks and phisical systems with emerdent collective computational abilities; Proc. Natl. Cad. Csi. USA, Vol.79, April, 1982. pp. 2554-2558.

[Hopfield 86]

J.J. Hopfield, D.W. Tank: Computing with neural circuits: a model; Science, Vol.233, 1986. pp.625-633.

[Horváth 95]

Horváth G.: Neurális hálózatok és műszaki alkalmazásaik; Műegyetemi Kiadó, Budapest, 1995.

[Horváth 96]

Számítástechnikai lexikon; szerk.: Horváth L., Pirkó J.; Kossuth, Bp., 1996.

[Ignizio 91]

J.P. Ignizio: Introduction to expert systems; McGraw-Hill, New York, 1991.

[Khanna 90]

T. Khannan: Foundations of neural networks; Addison-Wesley, 1990.

[Knight 90]

K. Knight: Connectionist ideas and algorithms; Comm, ACM, 33(11) November 1990. pp. 58-74. (in [140])

[Kohenen 84]

T. Kohenen: Self-organization and associative memory; Springer.Verlag, Berlin, 1984.

[Kolodner 93]

J. Kolodner: Case-Based Reasoning; Morgan Kaufmann, 1993.

[Kovács 95]

Kovács M.: Mikroszámítógépek alkalmazása – értelmező szótár; LSI Budapest, 1995.

[Leigh 86]

W.E Leigh, M.E. Doherty: Decision support and expert systems; South-Western Publishing Co., Cincinnati, 1986.

[Lippmann 87]

R.P. Lippmann: An introduction to computing with neural nets; IEEE ASSP Magazine Vol.4 No.2 April 1987. pp. 4-22.

[McEliece 87]

R.J. McEleice, E.C. Posner, E.R. Rodenich, S.S. Venkatesh: The capacity of the hopfield associative memory; IEEE Transaction on Information theory, 33(4) July 1987. pp. 461-482. (in [140])

[Minsky 2001]

Mérő L.: Új észjárások; Tericum kiadó, 2001.

[Minsky 69]

M. Minsky, S. Papert: Perceptrons: an introduction to computational geomerty; MIT Press, Cambridge, 1969.

[Minsky 81]

M. Minsky: A framework for representating knowledge; MIT Press, 1981.

[Monostori 96]

L. Monostori, H.Van Brussel, E. Westkampfer: Machine learning approach to manufacturing; CIRP Annals 45(2) 1996. pp. 675-712.

[Nelson 90]

M.M. Nelson, W.T. Illingworth: A practical guide to neural nets; Addison-Wesly, 1990.

[Newell 88]

A. Newell, H.A. Simon: the theory of human problem solving; Readings in cognitive science, Edited by A. Collins, E.E. Smith, Morgan Kaufmann, San Mateo, 1988.

[Parsage 88]

K. Parsage, M. Chignell: Expert systems for experts; John Wiley and Sons, New York, 1988.

[Partridge 86]

D. Partridge: Artificial intelligence: applications in the future of software engineering; Ellis Horwood Ltd., New York, 1986.

[Polinszky 72]

Műszaki lexikon, szerk.: Polinszky K.; Akadémiai Kiadó, Budapest, 1972.

[Rich 91]

E. Rich, K. Knight: Artificial intelligence; McGraw-Hill, New York, 1991.

[Rosenblatt 59]

R. Rosenblatt: Principles of neurodynamics; Spartau Books, New York, 1959.

[Russel 94]

S. Russel, P. Norvig: Artificial intelligence: a modern approach; Prentice Hall, 1994.

[Sántáné 98]

Sántáné – Tóth E.: Tudásalapú technológia, szakértő rendszerek; Dunaújváros, 1998.

[Savory 90]

S.E. Savory: Expert systems for the professional; Ellis Hoewood, New York, 1990.

[Schalkoff 90]

R.J. Schalkoff: Artificial intelligence: an engineering approach; McGraw and Hill, 1990.

[Searle 88]

J.R. Searle: Minds, brains and programs; Readings in cognitive science, Edited by A. Collins, E.E. Smith, Morgan Kaufmann, San Mateo, 1988.



22

[Sharples 91]

M. Sharples, D. Hogg, C. Hutchinson, S. Torrance, D. Young: Computer and thought: a practical introduction to artificial intelligence; MIT Press, 1991.

[Shepanski 92]

J.F. Shepanski: Artificial neural systems; in Encyclopedia of physical science and technology, Academic Press, 1992.

[Turing 88]

A.M. Turing: Computing machinery and intelligence; Readings in cognitive science, Edited by A. Collins, E.E. Smith, Morgan Kaufmann, San Mateo, 1988.

[Vemuri 92]

V.R. Vemuri: Artificial neural networks: theoretical concepts; IEEE Comp. Soc. Press, 1992.

[Watson 96]

I. Watson: Knowledge-Based Engineering; http://www.salford.ac.uk/survey/igds/mod7/chp00.htm 1996.

[Wolfgram 87]

D.D. Wolfgram, T.J. Dear, C.S. Galbraith: Expert systems for the technical professional; John Wiley and Sons, New York, 1987. Mikó Balázs 1973-ban született. Gépészmérnöki oklevelet 1996-ban szerzett a Budapesti Műszaki Egyetem Gépészmérnöki karán Gépipari technológia szakon. Doktori (PhD) disszertációját 2001ben védte meg. A szerző kutatási területe a technológiai tervezés számítógépes segítése mesterséges intelligencia módszerek alkalmazásával.


Internet

dokumentum

Dr Mikó Balázs Mesterséges intelligencia Szakértői rendszerek 3.1 ( :38)

Recommend Documents