Informatika | Mesterséges intelligencia » Hermann Gyula - Mesterséges Intelligencia

1. Bevezetés Az informatika kevés területét kísérte akkora figyelem és várakozás mint a mesterséges intelligencia területét. A várakozás mellett természetesen nagy számban megjelentek a szkeptikus hangok is, tegyük hozzá, hogy nem alaptalanul. Azonban visszatekintve meg kell, hogy állapítsuk, hogy a mesterséges intelligencián belül igazi sikettörténetként könyvelhetjük el az ún. ismeretalapú rendszerek és ezen belül a szakértői rendszerek területén elért eredményeket. Hosszú és rögös út vezetett annak felismeréséig, hogy jelenleg rendelkezésre álló eszközök és ismereteink mellett melyik absztrakciós szint alkalmas igazán az intelligens emberi döntéssel összemérhető számítógépes döntések meghozatalára. A mesterséges intelligencia tárgykörét alkalmazások szerint osztályozva következő felosztáshoz jutunk: tételbizonyítás, játékok, robotika, látás, természetes nyelvek feldolgozása, tudástechnológia, stb.

Az alkalmazott alapvető módszerek: a probléma reprezentáció, a keresések, következtetési technikák, a mesterséges intelligencia nyelvei, ismeretreprezentáció, a tanulás, stb. Jegyzetünkben a mesterséges intelligencia egyik legfontosabb és egyben legsikeresebb területének, az ismeretalapú rendszereknek az alapvető fogalmaival és eljárásaival foglalkozunk. A jegyzet két részből áll: az első a hagyományos ismeretalapú rendszerekkel és ezen belül a szakértői rendszerekkel foglalkozik, a második a mesterséges neurális hálózatok területén elért eredményeket foglalja össze. A hagyományosnak tekinthető ismeretalapú rendszerekkel foglalkozó részben áttekintjük a különböző keresési technikákat és ismeretreprezentációs módszereket, a bizonytalanság kezelésének különböző technikáit, az ismeretalapú rendszerek felépítését, valamint röviden bemutatjuk e rendszerek fejlesztésénél használt módszereket. A második

részben ismertetjük a természetes és mesterséges neurális hálózatok felépítését és működését, néhány tipikus hálózati struktúrát. Bevezetjük az olvasót a gépi tanulás rejtelmeibe. Ezt a részt a mesterséges neurális hálózatok alkalmazási területeinek összefoglalásával zárjuk le. 2. Szakértői rendszerek 2.1 Ismeretalapú technológia története A mesterséges intelligencia k utatások és ez en bel ül az i smeret l apú r endszerek fejlődését három jól elkülönülő szakaszra lehet bontani: 1955 - 1970 A hős kor amikor a kutatások megindultak és alapvetően tapogatóztak abba az i rányba, hog y hog yan l ehet az ember problémamegoldó képességét modellezni. Ebben az időszakban különböző játékprogramok születtek és ekkor élte kezdeti f énykorát ( s ikertelensége el lenére) a vizuális alakfelismerés. A korszak legjelentősebb és maradandó eredményei a következők voltak: • John McCarthy megalkotta a LISP-t

• Newell és Simon elkészítették a Logic Theorist nevű automatikus tételbizonyító programot, majd a General Problem Solver nevű általános problémamegoldó rendszert • Rosenblatt kidolgozta a perceptront és egyrétegű neuron hálózattal modellezte a szem retináját • az MIT Dertuozus kidolgozza az ún. t hreshold l ogika m atematikáját, am ely későbbiekben a neurális hálózatok elméleti megalapozása lesz 1971 - 1980 közötti időszakban a kutatások elsősorban az emberi problémamegoldó tevékenység egy m agasabb s zintjére k oncentrálnak és a k or di vatos k ifejezései a szakértői illetve ismeretalapú rendszerek lesznek. Ekkor születnek meg a: • DENDRAL, a MYCIN és az X CON v alamint a P ROSPECTOR az első sikeres mai értelemben vett szakértői rendszerek • a logikai programozás új nyelve a PROLOG • megszületik a fuzzy elmélet Ekkor kristályosodik ki az a f elismerés, am ely az i smeretek és a pr oblémamegoldó mechanizmusok

szétválasztásához vezet. 1980-1990 közötti időszakot a szakértő keretrendszerek kialakulás és széleskörű elterjedése valamint az alaptechnológiák rohamos fejlődése jellemzi. A kutatásoknak különösen nagy lökést adott a j apán 5. G enerációs s zámítógép pr ojekt E zek eredményeként ebben a periódusban: megjelennek és elterjednek a keretrendszerek • széles körben elkezdik elsősorban japán hatásra használni a PROLOG-t, amelynek különböző változatai születnek meg • megkezdődik a szakértői rendszerek ipari alkalmazása • megjelennek az első fuzzy vezérlő és szabályozó rendszerek Napjainkban a k utatások s úlypontjában az i ntegrált k eretrendszerek ( shell + adatbázis + m ultimédia f elület) ál lnak. Ú j él etre k elt a neur ális hál ózatok i ránti érdeklődés és elsősorban a műszaki diagnosztika és a vizuális alakfelismerés területéről számtalan kecsegtető eredményről számolhatunk be. 2.11

Ellenőrző kérdések 1, Hány szakaszra os ztható a m esterséges i ntelligencia és ez en bel ül az ismeretalapú rendszerek fejlődése és mi jellemezte ezeket az idő szakokat? 2, Mi alapozta meg a neurális hálózatok matematikai elméletét? 3, Mik a mesterséges intelligencia fejlődésének fő irányi napjainkban? 2.2 Ismeretalapú rendszerek alapjai Ebben a f ejezetben ol yan pr oblémákkal f oglalkozunk, am elyeknek a megoldásakor valamiféle k eresési el járást k ell al kalmazni. N em f oglalkozunk ol yan f eladatokkal, mint például az elsőrendű, többismeretlenes egyenletrendszer megoldásával. A dott cél elérésére irányuló különböző döntési helyzetekben legtöbbször nem egyértelmű és nem világos, hogy a feladat megoldása érdekében éppen milyen döntést érdemes hozni, milyen lépést célszerű végrehajtani. Ilyen helyzetekben figyelembe kell venni azon döntések különféle sorozatait, am elyek el vezetnek a k ívánt c

élhoz. E bben a fejezetben áttekintjük az állapottérnek illetve a m egoldás el éréséhez s zükséges eszközöknek az operátoroknak a fogalmát, ismertetjük a különböző keresési és ismeret-reprezentációs módszereket. 2.21 Állapottér, keresési problémák megfogalmazása A keresési problémák megfogalmazásának első és egyben legfontosabb lépése az elérendő cél definiálása. Ezt általában elegendő elvárt tulajdonságaival jellemezni, azaz m egadni eg y ol yan v izsgálatot, am elynek s egítségével k épesek v agyunk eldönteni, hogy az adott állapot célnak tekinthető-e vagy nem [18]. Bármely keresési probléma következő összetevőkből áll össze: • kiinduló vagy kezdeti állapot • azon operátorok halmaza, amelyek átvezetnek az egyes állapotokból más állapotokba • célállapot vagy célvizsgálat • a megoldás költségének meghatározására alkalmas költségfüggvény Maga a megoldás az, az út, vagy

döntések sorozata, amely a kiinduló állapotból egy célállapotba v ezet. A k öltségek az egyes oper átorok al kalmazásával j árnak, í gy a megoldás költsége a hozzávezető úton felhalmozott költségekkel egyenlő. Az eredeti feladat igénye szabja meg, hogy a kereséskor beérjük-e egyetlen megoldással, vagy több, es etleg az ös szes l ehetséges m egoldást elő kell állítanunk, avagy a megoldások k özül a l meghatározni. egkisebb k öltséggel j áró ún. optimális megoldást kell 2.22 Példák állapottér reprezentációkra Útkeresés labirintusban Tekintsünk elsőként egy egyszerű labirintus problémát. A labirintus térképe a 2 21 ábrán látható, a feladat pedig a bejárattól a kijáratig vezető útvonal megtalálása. Cél Kiindulási pont 2.21 ábra Labirintus A labirintust ábrázoló gráfot a 2. 22 ábrán láthatjuk Az utakon mozgó embert X-vel jelölve a kezdeti- és célállapot a 2.23 ábrán látható módon

definiálható 4 3 2 1 1 2 3 4 2.22 ábra A labirintus gráfja Az ember szabadon mozoghat a gráf élei, az utak mentén és a kereszteződésekben bármely v álasztott irányba t ovábbhaladhat. A z új poz íciót a 2 22 ábr án l átható koordinátákkal adhatjuk meg. A kezdőpontból kiindulva az elsőként elért kereszteződés a (2,3) pont. Az (1,4) pont zsákutcának bizonyul Bár az ember helyzete f olyamatosan v áltozik m iközben az utak m entén hal ad l ényeges ( döntési) pontok csak a kezdőpont, a kereszteződések, a zsákutcák és a célpont. A probléma állapotát az ember helyzete határozza meg. A probléma megoldó eljárás a célállapot elérését foglalja magában a különböző közbenső állapotokon keresztül. Kezdeti állapot Célállapot 2.23 ábra Kezdeti állapot és célállapot A feladatban a c élt az ember mozgatásával érjük el: amely egy adott pozícióból egy olyan másik pozícióba történő elmozdulást j

elent, am ely út tal k apcsolódik az előzőhöz. A mozgás tehát az egyik állapotból a másikba történő átmenetet jelenti Ezt a mozgást pr oblémamegoldó oper átoroknak nev ezzük. A pr obléma m egoldása tehát az oper átorok eg y ol yan s orozatával í rható l e, am elynek segítségével a c él elérhető. Állapotok halmaza: az ember lehetséges elhelyezkedései az elágazási pontokon Operátorok: az egyik elágazási pontról a szomszédos elágazási pontba való lépés Kezdőállapot: az ember a labirintus bejáratánál van Célállapot: az ember a labirintus kijáratánál van 8-as játék A m ásik s okszor em legetett pél da az ún. 8 -as j áték A dott eg y 3x 3-as t áblán 8 számozott elem, amelyeket a t áblán tologatunk. Szándékunk a k ezdeti állapotból az elemek m ozgatásával a c élállapot el érése, am ikor is az egyes elemek emelkedő sorban gyűrűbe vannak rendezve. Az üres mező alatt, felett, tőle balra illetve jobbra levő elem

tolható az üres helyre. A probléma állapota minden alkalommal megváltozik, am ikor eg y el emet el mozdítunk. A pr obléma oper átora az elemek elmozdítása. Állapotok halmaza: tábla összes lehetséges kitöltése (9!=362 880) Operátorok: az üres hely mozgatása jobbra, balra, le illetve fel Kezdőállapotok halmaza: bármely állapot Célállapot: csak egy van 8 3 2 6 4 1 7 5 1 => 2 8 7 3 4 6 5 2.24 ábra 8-as játék Hanoi tornyai probléma Egy asztallapon adott három rúd (1,2,3) és négy különböző méretű korong (A,B,C), amelyek nagyság szerint csökkenő sorrendben az egyik rúdon vannak. A feladat: a korongokat úgy kell egy másik rúdra áthelyezni, hogy ott ugyanebben a s orrendben legyenek. A kezdő és cél állapotot a 225 ábra mutatja Egyszerre csak egy korong mozdítható és egy korong nem helyezhető egy nála kisebb tetejére. => 2.25 ábra Hanoi tornyai játék Állapotok halmaza: az összes megengedett el helyezések,

ahol t ehát az eg yes rudakon a korongok alulról felfelé csökkenő méretűek Operátorok: az i-edik rúdról a j-dik rúdra helyezzük át a legfelső korongot Kezdőállapotok halmaza: mindegyik korong az 1-es rúdon Célállapot: mindegyik korong a 3-as rúdon Tik-tak-to Ebben a játékban két játékos felváltva rajzol X és O jeleket egy 3x3-as táblára. Az a játékos győz, amelyik három jelet tett folytonosan vízszintes, függőleges vagy átlós irányban. A játékra a 2 26 ábrán látható egy példa A kezdeti állapot az üres tábla Célállapot sok van és nem ábrázolhatóak egyszerű rajzzal. A játék akkor ért véget, ha az egyik fél már győzött, illetve ha már minden mező ki van töltve: ez döntetlen. X X X X X O O X X O X X O O X X O O X X O X X X O O O O O 2.26 ábra Példa a tik-tak-to játékra Állapotok halmaza: a t ábla összes lehetséges kitöltése, oly módon, hogy az X és O jelek száma maximum eggyel tér el

egymástól és tetszőleges számú hely marad üres Operátorok: üres mező kitöltése a soron következő játékos által Kezdőállapot: az üres tábla Célállapotok halmaza: azok az állapotok, amikor az egyik játékosnak három jele van vízszintesen, függőlegesen vagy ferdén egy sorban Legrövidebb útvonal keresése gráfon vagy térképen A feladat az, hogy a lehető legrövidebb úton jussunk el a kiindulási városból a cél városba. A 2 27 ábr a m utatja, hog y az ér intett k örzetben az egyes helységek hogyan és milyen hosszú utakkal v annak ös szekötve. E kkor a k ezdeti ál lapotnak megfelel az hogy Lajosmizsén vagyunk és még nem jártunk sehol. Az operátorok az utazások a s zomszédos v árosok k özött. A c élvizsgálatnak m egfelel az a kérdés, hogy „Szentesen vagyunk-e?” A megoldás költsége a megtett út teljes hossza, és az a megoldás tekinthető optimálisnak, amelynek a költsége a lehető legkisebb. A gráfot nem kell előre

ismerni, lehetséges, hogy csak a keresés során tárjuk fel. Lajosmizse Nagykőrös Tiszakécske Kecskemét Kunszentmárton Kiskunfélegyháza Csongrád Szentes 2.27 ábra Térképvázlat a Lajosmizséről Szentesre vezető út megkereséséhez Állapotok halmaza: az elágazási pontokban való tartózkodás Operátorok: az egyik elágazási pontról a szomszédos elágazási pontba való lépés Kezdőállapot: az utazás kezdetének városában való tartózkodás Célállapot: az utazás céljának elérése 2.23 Keresési eljárások A keresés technikai szempontból úgy tekinthető, mint egy ún. keresési fa felépítése az állapottér felett, ahol a f a c somópontjai az eg yes ál lapotoknak, m íg az él ek azoknak az operátoroknak f elelnek m eg, am elyek az eg yes ál lapotokból átvezethetnek más állapotokba [3]. A fa gyökere a k ezdeti állapot Maga a keresési fa a csomópontok kiterjesztése révén épül fel, amikor is előállítunk olyan

állapotokat, amelyek az adott állapotból az éppen ak kor al kalmazható oper átorok r évén közvetlenül elérhetők. Az í gy k eletkezett c somópontokat nev ezzük a k iterjesztett csomópont gyermekeinek. kezdeti állapot a kezdeti állapot kiterjesztése után Lajosmizse Kecskemét Nagykőrös egy újabb csomópont Kiskunfélegyháza Tiszakécske kiterjesztése után 2.28 ábra a keresési fa kibontása Ha m ár adot t a k ezdeti ál lapot, al kalmazható oper átorok, a c élvizsgálat és a költségfüggvény, akkor a keresés az alábbi általános algoritmus szerint történik: Általános keresés: 1) Legyen L a kezdeti állapotokat tartalmazó lista 2) Ha L üres, akkor állj le a keresés sikertelen, egyébként legyen n egy csomópont L-ből 3) Ha n egy célállapot, akkor állj le és add vissza a (hozzá vezető úttal együtt) eredményként 4) Egyébként: • töröld n-et L-ből • állítsd elő n gyermekeit • jegyezd fel a hozzájuk

vezető utat • add a gyermekeket L-hez • menj vissza az algoritmus 2. pontjára A keresési algoritmusok túlnyomó többsége alapjában véve a fenti módon működik. Az egyes stratégiák közötti döntő különbség az, hogy miként választják ki azt a csomópontot, amelyet a legközelebb ki fognak terjeszteni. Az ú n. va k keresési algoritmusok ebben a döntés során kizárólag a már előállított csomópontoknak a k eresési f án bel ül el foglalt hel yzetét v eszik f igyelembe. E zzel szemben a heur isztikus el járások m inden m ás a konkrét, megoldandó problémával kapcsolatos információt felhasználnak a választáskor. 2.231 Vak keresési módszerek A legegyszerűbb módszerek közé tartozik az ún. szélességben először való keresés[3], am ely a k eresési f ában m indig a gyökérhez legközelebbi csomópontok egyikét terjeszti ki. Először tehát végigvizsgálja a d szinten lévő valamennyi csomópontot és csak ezután veszi

sorra a d+1 szinten lévő csomópontokat. Az általános keresési algoritmuson belül ez a következő módosításokat vonja maga után: 2) Legyen n az első csomópont L-ből 4) Add n gyermekeit L végéhez Az eljárás kedvező tulajdonsága, hogy teljesen módszeresen, szintről szintre, végigjárja a keresési fát és így a legalacsonyabb szinten lévő, megoldást találja meg, Ebből adódóan a megoldás abban az esetben, ha minden operátor alkalmazása azonos költséggel jár, optimális. Kedvezőtlen tulajdonsága viszont, hogy mind a számítási idő, mind a kereséshez szükséges memória felhasználás exponenciálisan nő a keresési fa mélységével. Az utóbbi miatt a szélességben először kereső algoritmust c sak k imondottan kisméretű (állapotterű) feladatok megoldásánál használják. A másik legegyszerűbb eljárás a mélységben először való keresés [3], amely a keresési fában mindig a legmélyebben fekvő csomópontok valamelyikét

terjeszti ki. Általában az ut oljára k iterjesztett csomópont g yermekei k özül v álaszt és ha erre nincsen mód, akkor visszatér az ezt megelőző olyan szintre, ahol még van választási lehetősége. Ehhez az általános keresési algoritmust a következőképpen kell megváltoztatni: 2) Legyen n az első csomópont L-ből 4) Add n gyermekeit L elejéhez A mélységben először keresés memóriaigénye szerény, mindössze a fa maximális mélységével egyenesen arányos. A számítási időigénye viszont, hasonlóan a szélességben először kereséshez, exponenciálisan nő a fa mélységével. Leghátrányosabb t ulajdonsága, az onban az , hog y el akadhat egy rossz ágon, amelyről, ha az végtelen nem tud letérni, mivel nincs lehetőség a korai rossz döntések megváltoztatására. A mélység korlátozásával elkerülhető a mélységben először keresésnek ez a kedvezőtlen t ulajdonsága. E z az t j elenti, hog y az ún korlátozott

mélységű keresés mindig a legmélyebben fekvő csomópontok valamelyikét terjeszti ki, de csak akkor, ha az nincsen egy előre megadott mélységi korlát alatt. A korlát eredhet a feladat természetéből, példánk es etében a v árosok száma egy al kalmas k orlát. A k orlát önk ényes m egadásának pr oblémáját i teratív mélyítés segítségével kerülhetjük meg, ahol korlátozott mélységű keresést végzünk egyre növekvő mélységi korlát mellett. Célszerű alkalmazni olyan esetekben, amikor a keresési tér mérete nagy és a megoldás mélysége ismeretlen. 2.232 Heurisztikus keresés A heur isztika eg yrészt bár mely t anácsot, ök ölszabályt j elent, am ely gyakran hatékony, de nem minden esetben érvényes, másrészt egy kiértékelő függvényt, amely a pr obléma eg y ál lapotához eg y s zámot r endel hoz zá. K eresésnél a heurisztikát arra használjuk, hogy a még ki nem terjesztett csomópontról eldöntsük, hogy az

mennyire l ehet k özel a c élhoz. E z l ehet i gen k öltséges, és m ivel c sak becslésen al apul, ak ár tévútra vezető is. A legjobb csomópont kiválasztása elvben nem könnyebb feladat, mint magának a keresési problémának a m egoldása. Ennek ellenére alkalmazása célszerű, már kevés alkalmazásfüggő ismeret is nagymértékben s egíti a f eladat m egoldásával j áró s zámításigény c sökkentését, illetve korlátozott erőforrások mellett az optimális megoldás megtalálását. A heurisztikus kiértékelő függvény általában azt a költséget becsli, amely a legközelebbi célállapotnak a pi llanatnyi állapotból való elérésével jár. A jó kiértékelő függvény hat ékonyan s zámítható és opt imista bec slést ad, az az nem bec sli túl a tényleges költséget. Ez utóbbi tulajdonság a heurisztikus algoritmusok kedvező viselkedésének előfeltétele. A továbbiakban a heurisztikus algoritmusok két fő osztályával

foglalkozunk: a legjobbat-először, valamint az iteratív javító eljárásokkal. A l egjobbat-először kereső algoritmusok úgy működnek, hogy egy f(n) heurisztikus függvény segítségével kiértékelik a még ki nem terjesztett csomópontokat és minden helyzetben, az éppen l egjobbat v álasztják, pél dául a k eresési f a az on ág át választják, ahol következő lépés a legkevesebb költséggel jár. Ez az általános keresési algoritmus következő módosítását vonja maga után: 2, Legyen n az a csomópont L-ből, amelyre f(n) minimális A legegyszerűbb ilyen módszer az ún. mohó keresés, amely egyedül a cél lehető leggyorsabb m egtalálására t örekszik. E zért a k iértékelés al apja k izárólag a c éltól való távolság: a m ohó k eresés t ehát m indig éppen az t a c somópontot t erjeszti k i, amelynek a céltól becsült távolsága a legkisebb. A legrövidebbnek tűnő út azonban nem mindig az. A mohó keresés tehát

elvétheti az optimális megoldást A m inimális k öltséggel j áró m egoldást i s k épes m egtalálni az ún. A∗ algoritmus A kiértékelés al apja i tt, a már megtett út tényleges és az előttünk álló út várható költségének összege. Az általános keresési algoritmus tehát a következők szerint módosul: 2, Legyen n az a csomópont L-ből, amelyre f(n) = g(n)+h(n) minimális Az A* algoritmus kedvező tulajdonsága, hog y m inden oper átor al kalmazása poz itív költséggel jár, valamint optimális, ha h( n) pont osan bec süli a c él t ávolságát, ak kor ugyanis f(n) nem változik az optimális út mentén, így az algoritmus sem tér le arról. Az optimális úton amennyivel nő g(n) annyival csökken h(n). Ha a cél távolságát nem tudjuk ilyen jól bec sülni, ak kor az al goritmusnak j obban f el k ell der ítenie az állapotteret, am inek nag y ár a v an. Á ltalános es etben az A* algoritmusnak mind időbeli, mind memóriaigénye

exponenciálisan nő a megoldandó feladat méretével. Ha például a céltávolságra a lehető legóvatosabb becslést adjuk, azaz h(n) = 0 minden n -re, akkor az A* algoritmust a szélességben először való keresésre redukáljuk. A memóriaigény radikálisan csökkenthető iteratív módon mélyítő A* (IDA*) kereséssel. E nnek al apötlete ug yanaz, m int a v ak k eresés es etén, ahol az iteratív mélyítés c sökkentette a m emóriaigényt. H eurisztikus k eresés es etén az onban az iteratív módon növekvő korlátot nem a mélységre, hanem f(n)-re al kalmazzuk. A z IDA* a lgoritmus c iklusonként m élységben-először keresést alkalmaz azokra a csomópontokra, amelyekre f(n) kisebb, mint a megadott korlát. Sikertelenség esetén növeli a korlátot és újraindítja a keresést. A mélységi korlátot nem célszerű egyenként l éptetni, hanem m indig az előző ciklusban legkevésbé meghaladó csomópont értékéhez célszerű igazítani. A

feladatok egy jelentős része oly módon fogalmazható meg keresési problémaként, hogy megoldásaik a célállapotoknak megfelelő csomópontokban találhatók meg. Ilyen f eladat lehet például eg y ár amkör v agy eg y g yártórendszer el rendezésének kialakítása, és általánosságban m egfogalmazva az ún. k orlátozás k ielégítési problémák megoldása. Ha egyedül a megoldásoknak megfelelő csomópontokat akarjuk m egtalálni és ér dektelen a hoz zájuk vezető út, akkor az iteratív javító algoritmusok használhatók. Az iteratív javító algoritmusok működése jól szemléltethető terepen való tájékozódás, mozgás segítségével. A z eg yes f elületpontok m agassága m egfelel a c somópontok jóságának, am it pont os v agy heurisztikus k iértékelés r évén k apunk m eg. A csúcspontok az optimális m egoldások. A t ájékozódás pedi g eg y adot t pont ban az onnan elérhető, szomszédos pontok kiértékelésével történik meg. A

heg ymászás ( hill-climbing) al goritmus a k eresés s orán a csomópont közvetlen leszármazottait vizsgálja és ezek közül mindig a legjobbat választja. Az algoritmus a következő lépésekből áll: 1, Legyen n a kezdeti állapot 2, Ha n egy célállapot, akkor állj le és add vissza eredményként 3, Egyébként állítsd elő n valamennyi leszármazottját, legyen n = a legjobb a leszármazottak közül lépj vissza 2, -re Az algoritmus nem tárolja a k eresési fát, csak a pi llanatnyilag vizsgált csomópontot, igy memóriaigénye minimális, ám sikere nagyban függ a f elület alakjától. A felületen való t ájékozódás anal ógiájával él ve az al goritmus el akadhat, ha l okális magaslatra, vagy kiterjedt sík vidékre jut, vagy olyan helyre ahonnan gerinctúrát lenne jó tenni, de a gerincre éppen nem vezet út. A m egtett út v égére em lékezik az ún. t abu k eresés E z m indaddig úg y v iselkedik mint a heg ymászó al goritmus, am íg l

okális m aximumra nem j ut. Ekkor azonban olyan döntést is hoz, amelyik ront a hel yzeten. A c iklikus m ódosítások el kerülése érdekében az utoljára előállított n állapotot, ahová nem szabad visszalépni, egy ún. tabu listán tartja nyilván. 2.24 Ismeretreprezentációs módszerek Az ismeretreprezentáció és a hozzá elválaszthatatlanul kapcsolódó következtetés a mesterséges intelligencia egyik alapkérdése: miként modellezhető a világ úgy, hogy a m odell el égséges al apot adj on az intelligens cselekvéshez[6]? Egy intelligens cselekvő több szinten is leírható. A legfelső, ún ismeret szinten a cselekvőt annak révén def iniáljuk am ire k épes, amilyen feladatok el végzésére al kalmas. A logikai szinten adhatjuk meg, hogy ismeretei miként vannak kódolva: milyen reprezentációs nyelven és m ilyen m ondatokban v an a t udása megfogalmazva. Végül az implementáció szintjén adható meg az a k onkrét ny elv, adat struktúrák, v

ezérlés, stb. amelyek révén az adott hardware és software környezetben működőképes Az implementációs szint az ismeretreprezentáció szempontjából általában lényegtelen. A reprezentációs módszerek osztályozása t öbb s zempont s zerint l ehetséges. A z alábbiakban három osztályozást tárgyalunk részletesebben: Aszerint, hogy a probléma megoldását, algoritmusát adjuk-e meg, vagy csak magát a problémát í rjuk l e, bes zélünk procedurális és deklaratív reprezentációról. A z algoritmikus vagy pr ocedurális r eprezentáció es etén m egadjuk a t árolt i smeretek felhasználásának módját, a f eladatmegoldás s tratégiáját. Leí ró v agy dek laratív reprezentáció esetén csak azt, adjuk meg, hogy milyen feladatot kell megoldani és a szituációfüggő megoldás kidolgozását egy általános célú következtető rendszerre bízzuk. Ez a reprezentáció logikai alapú leírásoknál valósítható meg tisztán Ismeretalapú

rendszereknél alapvetően deklaratív reprezentációról van szó, amelyet a hatékonyság növelésének érdekében legtöbbször algoritmikus elemekkel bővítünk ki. Ilyen algoritmikus elemek lehetnek például: a megoldás módját előíró deklarációk, az eseményvezérelt démonok, a következtető algoritmus beépített stratégiáját módosító ún. meta-szabályok Aszerint, hogy a probléma leírását egyszerű, vagy struktúrával rendelkező, más szóval ös szetett obj ektumokkal adj uk-e meg, megkülönböztetünk egyszerű és strukturált reprezentációt. Az elemi vagy egyszerű reprezentációk egyszerű, struktúra nélküli világok leírására alkalmasak. Ezek az adott problématerületet elemi szintű, osztatlan objektumok, atomok, valamint azok kapcsolatai, a rajtuk végezhető műveletek és a róluk szóló állítások halmazával írják le. A strukturált reprezentációk belső struktúrával, egymástól megkülönböztethető

tulajdonságokkal, attributumokkal rendelkező objektumok világát ábrázolják. Az objektumok kapcsolata lehet taxonomikus (osztályozó jellegű) vagy egy objektum összetevődhet több más objektumból mint alkotórészből. E kapcsolatok révén az objektumok tulajdonságainak (attributumainak) öröklődése is megoldható. Az előző szempontokat és a leíró eszközt együttesen figyelembevevő osztályozás procedurális, l ogikai al apú, s trukturált v agy k eret al apú és hibrid reprezentációkat különböztet meg: Procedurális reprezentáció: Valamely pr ocedurális programozási ny elv el járásai, v agy t ágabb ér telemben v éve akármilyen nyelven megírt vezérlést módosító leírások. Logikai-alapú reprezentáció A logika olyan leíró nyelv, mely lehetővé teszi, hogy a világ tényeire vonatkozó állításokat m ondatok f ormájában f ogalmazzuk m eg [ 13]. A mondatokból azután mechanikus eljárások segítségével új abb m

ondatok s zármaztathatók. E zt a folyamatot nev ezzük k övetkeztetésnek. A t ények, am elyek a v ilág r észei, l ehetnek igazak és hamisak. Mivel a világ tényei nem vihetők be a g épbe, a t ényeket reprezentálni kell, azaz v alamilyen ny elven k i k ell az okat f ejezni. A l ogikai reprezentációban a tényekre vonatkozó állításokat mondatok f ejezik k i. A v ilág és reprezentációja az interpretáció réven kapcsolódik egymáshoz, amely megfeleltetést biztosít a t ények és m ondatok k özött. Á ltalános es etben t öbb i nterpretáció is lehetséges. A l ogika el emei a szintaxis, amely megadja a ny elv s zimbólumait és az okat a szabályokat am elyek s egítségével az okból m ondatokat l ehet f ormálni és a szemantika, amely megszabja, hogy a mondatok a világ mely tényeire vonatkoznak. A szemantika ad j elentést a m ondatoknak, amelyek anélkül nem többek mint a fenti szabályok szerint összefűzött szimbólumok sorozatai. A

következtetés nem más mint adott szintaxis és szemantika mellett új mondatok származtatása a már ismert mondatokból. A következtetéstől elvárjuk, hogy ugyanazon interpretációban az új mondatok is a világ ugyanazon tényeire utaljanak. Egy mondat igaz, ha olyan tényre utal, amely valóban előfordul a világban, azaz a mondat igazsága függ a v ilág ál lapotától és az i nterpretációtól. V annak ol yan, ún érvényes mondatok, amelyek i gazsága s em a v ilág ál lapotától, s em az interpretációtól nem függ. Ezeket nevezzük tautológiának Ilyen például a H olnap is lesz nap. Bizonyos mondatok k ielégíthetetlenek, az az ol yannak í rják l e a v ilágot, amilyen sohasem lehet. következik Reprezentáció: mondatok mondatok Világ: tények tények együtt jár 2.29 ábra A logikai következtetés általános sémája A k övetkeztetéskor olyan mondatot akarunk előállítani, amely igaz, ha ismeretbázisunkban az eredeti

mondatok igazak. Úgy tűnhet, hogy az érvényes és kielégíthetetlen mondatok feleslegesek, hiszen csak ny ilvánvalóan i gaz i lletve ham is dol gokat f ejeznek k i, ám éppen létüknek köszönhető, hogy a számítógépekkel logikai következtetéseket tudunk végrehajtani. A következmények gépi kiszámításakor ugyanis a világról csak annyi tudható, ami az ismeretbázisban van, de az már nem hogy, miként feleltethetők meg egymásnak a reprezentációs nyelv elemei és a világ tényei. Ahhoz, hogy automatikusan eldönthető legyen, hogy egy konkluzió következik-e a tudásbázisból, ki kell mutatni, hogy a „ ha a tudásbázis igaz, akkor a konkluzió i gaz” ös szetett ál lítás ér vényes, az az m inden interpretációban igaz. Következtetéskor m echanikus s zabályokat - ún. k övetkeztetési el járásokat alkalmazunk annak megállapítására, hogy mi következik a m ár ismert mondatokból A következtető eljárás a premisszák halmazából egy

konklúziót állít elő. A l egegyszerűbb formális logika az ún ítéletkalkulus, amelynek szintaxisa csak ítéletváltozókat és k ét í téletkonstanst ( TRUE,FALSE) eng ed m eg, amelyek a szokásos logikai műveletekkel fűzhetők mondatokba. Ezen műveletek halmaza a logikai és ^, a logikai vagy v, a tagadás ¬, az implikáció => és az ekvivalencia <=>. A műveleti jelek és zárójelek segítségével természetesen összetett mondatok is konstruálhatók. A z í téletkalkulus s zemantikájának al apja, hog y az i nterpretáció eg y mondat ítéletváltozóihoz a logikai igaz (T) vagy a l ogikai hamis (F) értékeket rendeli minden l ehetséges m ódon. A T RUE í téletkonstanshoz c sak T , a F ALSE-hoz pedi g csak F rendelhető. Egy mondatnak tehát több interpretációja lehet A mondatok igazságértékének megállapítása a műveleti jelek jelentése alapján t örténik, amelyeket az alábbi igazságtáblában foglaltunk össze: A B ¬A

A^B AvB A=>B A<=>B T T F T T T T T F F T F F F T F T T F F F F F T T T Ezek közül a műveletek közül az implikáció szorul némi magyarázatra: ez állítás B értékéről ha A igaz. H a A ham is, akkor A=>B igaz, függetlenül B értékétől Megjegyezzük, hog y A és B k özött nem feltételezünk semmilyen ok-okozati kapcsolatot! Az, hog y eg y ál lítás k övetkezik-e a m ár i smert ál lítások halmazából, az ítéletkalkulusban igazságtábla s egítségével ellenőrizhetjük. Ha adott a premisszák halmaza (P) és egy konklúzió (Q), akkor k észíteni k ell eg y i gazságtáblát a P =>Q mondat ellenőrzésére, ahol P a premisszák konjunkciója. Ha a tábla minden sora igaz, akkor a P=>Q mondat érvényes, ami azt jelenti, hogy Q következik P-ből. Ilyen eljárás mutat példát a következő táblázat, ahol a premisszák halmaza {P1vP2,¬P2}, a konklúzió pedig P1. P1 P2 P1vP2 ¬P2 (P1VP2)^¬P2

(P1VP2)^¬P2=>P1 T T T F F T T F T T T T F T T F F T F F F T F T Az i gazságtábla s egítségével való következtetés teljesen mechanikussá tehető, hiszen nem kell mást tenni, mint minden lehetséges módon T és F értékeket rendelni a premisszák ítéletváltozóihoz és kiértékelni az ilyen módon kapott immár interpretált mondatokat a műveleti jelek jelentése alapján. Ehhez tehát nem kell semmit tudni a mondatok jelentéséről, arról, hogy a világ mely tényeit írtuk le velük. A gond csupán az, hogy az eljárás idő és helyigénye exponenciálisan nő az ítéletváltozók számával, az az ha az i gazolandó m ondat n s zimbólumot t artalmaz n akkor f el k ell s orolni az igazságtábla 2 sorát. K ötött f ormájú m ondatokból ál ló premisszák esetén létezik ennél sokkal hatékonyabb ellenőrzési módszer. Ilyen például a Horn klózokra korlátozott l ogika, ahol a m ondatok f ormája A1^A2^.^An^B, ahol

valamennyi Ai pozitív (nem tagadott) ítéletváltozó Az igazságtáblán végezhető műveletek bizonyos minták szerint összefoghatók. Ezeket a mintákat fejezik ki a már említett következtetési szabályok avagy eljárások. Az elsőrendű logika (avagy elsőrendű predikátumkalkulus) az a logikai nyelv, amely megalapozza a j elenleg has ználatos i smeretreprezentációs módszerek többségét. Az elsőrendű logika megengedi, hogy a világot objektumokra, azok tulajdonságaira és az objektumok közötti kapcsolatokra tagoljuk. Ahhoz, hogy elsőrendű logikát használni tudjuk, az szükséges, hogy legyen a következtetési szabályoknak egy olyan halmaza, amelyekkel a k övetkeztetés biztos, és ha l ehet, t eljes. E gy k övetkeztetést ak kor nev ezünk bi ztosnak, ha c sak ol yan mondatokat hoz l étre, m elyek i gazak m inden ol yan i nterpretációban, am iben az eredeti mondatok halmaza igaz v olt. A k övetkeztetési el járást ak kor nev ezzük teljesnek, ha

az képes az összes következményt előállítani. A dedukció problémája, hogy meg lehet-e adni a következtetési szabályok egy olyan készletét, m elyekkel a k övetkeztetés bi ztos és t eljes. I lyenek pél dául az ún. természetes levezetés szabályai, melyek többek között olyan régről ismert, emberi gondolkodás számára természetesnek tartott szabályokat is magukba foglalnak, mint a modus ponens , v agy a r eductio ad abs urdum. A k övetkeztetés az onban em e szabályok s egítségével al igha aut omatizálható. E z ak kor l átható be, ha a következtetést keresési problémaként fogalmazzuk meg, ahol: • a kezdeti állapot az axiómák konjunkciója • a célállapot a bizonyítandó tétel és • az operátorok a következtetési szabályok Mivel sok és s okféle m ódon al kalmazható s zabályunk v an, és r áadásul eg yes szabályok kombinálják a már ismert tényeket, az elágazások száma exponenciálisan nő az i smeretbázisunk

m éretével. R áadásul nehéz t anácsot adni arra nézve, hogy egyes helyzetekben éppen milyen szabályt célszerű alkalmazni. A keresési tér kedvezőbb szerkezetű és a keresés jobban irányítható, ha egyetlen általános következtetési szabályt alkalmazunk. Ilyen szabályok az általános modus ponens és a rezolúció. A rezolúció a modus ponens általánosítása, az elsőrendű logika jól automatizálható következtetési eljárása, ezért itt csak ezt tárgyaljuk. A rezolúciót használó bizonyító eljárás a t agadás cáfolatának elvén alapul. A dott eg y I B i smeretbázis, am ely ellentmondásmentes aximákat tartalmaz és egy Á ál lítás. B izonyítsuk be, hog y Á következménye I B-nek, az az m utassuk k i, hog y az I Bv¬Á hal maz k ielégíthetetlen. Az, hogy a mondatok egy halmaza kielégíthetetlen, a mondatok közötti ellentmondás révén bizonyítható. Ebből következően az eljárás a következő: 1, Tagadd a célállítást és

add azt az ismeretbázishoz 2, Alakítsd át a mondatokat klóz formára 3, Amíg az üres klózt elő nem állítod, alkalmazd ismételten a rezolúciós szabályt A Horn logika, a r ezolúcióval m int k övetkeztetési s zabállyal m egfelel az oknak a követelményeknek, amelyeket a r eprezentációs ny elvekkel s zemben t ámasztunk: kifejező, tömör, egyértelmű és biztosítja a hatékony következtetés lehetőségét. Ezért is válhatott a logikai programozás alapjává, amely a számítógéppel történő feladatmegoldás két aspektusát a f eladatmegoldást és kódolást próbálja egyesíteni. A logikára épít, amely ha nem is minden tekintetben kielégítő módon, de mégis sokkal k özelebb ál l az em beri g ondolkozáshoz, m int bármely programnyelv. A logikai programozás gyökeresen különbözik a hagyományos programnyelvektől abban, hogy egy absztrakt modellből származik és független a számítógépek pillanatnyi műszaki lehetőségeitől. Egy

l ogikai pr ogram ol yan ax iómák hal maza, amelyek objektumok tulajdonságait illetve az azok közötti relációkat határozzák meg. Egy axióma lehet egy egyszerű tényállás, tényállások konjunkciója vagy szabály. A pr ogram m aga a l ehetséges k övetkezmények eg y halmazát rejti m agában - ez a program j elentése. A pr ogram v égrehajtása, av agy a s zámítás nem m ás, m int eg y célállítás k onstruktív bi zonyítása a pr ogramban m egfogalmazott axiómák felhasználásával. A célállítás eg zisztenciálisan k vantált: az az anny it ál lít, hogy létezik olyan egyedi obj ektum, am ely bi zonyos adot t t ulajdonságokkal r endelkezik. Az ax iómák H orn k lózokként adhat ók m eg, í gy a l ogikai pr ogramozás pr ocedurális interpretációja a Horn klózokon alapuló logikának, azaz a feladat értelmezhető úgy is, hogy ahhoz, hogy megoldjuk A-t, meg kell oldani B1,.B2,Bn-t Egy logikai program mindég egy c élállítás s

egítségével bí rható s zóra. H a ez a célállítás változókat tartalmaz, akkor a k onstruktív bizonyítás azontúl, hogy megadja igaz-e az állítás a v áltozók lekötésének révén más eredményeket is tud produkálni. Ezt valósítja meg az ún. absztrakt interpreter: 1, Inicializálás: legyen a rezolválandó célok listája, R = {G} 2, Ha R üres, vizsgáld meg G-t: ha G létezik, add vissza eredményként; egyébként állj le - a bizonyítás sikertelen 3, Egyébként válassz egy A célt R-ből és egy A’:-B1,B2,.,Bn klózt a logikai programból állítsd elő A és A’ legáltalánosabb helyettesítését, Q-t ha nincsen olyan cél-klóz pár, amelyre Q létezik, állj le - a bizonyítás sikertelen töröld A-t R-ből add B1,B2,.Bn alcélokat R-hez alkalmazd a Q helyettesítését R elemeire és G-re menj vissza 2,-re Az előbbiekben vázolt algoritmus nem-determinisztikus, az az nem m ondja m eg, hogy egy adott szituációban melyik célt válasszuk a r

ezolválandók listájáról és hogy melyik klózt a logikai programból. Így itt is különféle stratégiákkal lehet a bi zonyítás és a m egoldás k eresését bef olyásolni. A l ogikai pr ogramozásban t ehát k ettéválik a feladat a megoldáshoz szükséges deklaratív logikai megfogalmazásra és az ezeket az ismereteket manipuláló mechanizmusra, a vezérlésre. A Prolog [10] egy programozási nyelv, amely alapvető konstrukcióit a matematikai logikától kölcsönzi. A P rolog pr ogramok s zámítógépen v aló v égrehajtása s zigorúan kötött előírások szerint t örténik. A pr ogram t ehát v égrehajtandó ut asítások együttesének tekinthető. Ebben a tekintetben egy Prolog program semmiben sem különbözik m ás pr ogramoktól. A l ényeges k ülönbség - és a l ogikai pr ogramozással való r okonság - abban ál l, hog y a s zámítás er edménye a P rolog pr ogramot al kotó axiómák l ogikai k övetkezménye. E zért eg y j ó s tílusban

í rott P rolog pr ogram m indig olvasható úgy, mint logikai állítások egy halmaza. Ez a program deklaratív olvasata A Prolog nyelv három fő ponton tér el a logikai programozás modelljétől: • megköti az absztrakt interpreter által nyitva hagyott döntéseket • a tisztán logikai program kifejező erejét növeli meta-logikai és kiegészítő szolgáltatásokkal • hozzáférést biztosít a s zámítógép bi zonyos s zolgáltatásaihoz, úg ymint aritmetika, input/output A Prolog program rendezett klózok hal maza, ahol m ind a k lózok s orrendje, m ind pedig az eg ye k lózokon bel ül a a f eltételek sorrendje kötött és a végrehajtás mechanizmusa ez eket a m egkötéseket has ználja k i. A P rolog i nterpreter abs ztrakt testvérétől két lényeges ponton különbözik: • tetszőleges cél választása helyett balról jobbra haladva dolgozza fel a c élokat és az új c élokat a r ezolválandó c élok listájának elejére helyezi, tehát

mélységben először keresi a feladat megoldását • a k lózok k özül a sorrendnek megfelelően a legelső olyat választja, amelynek fejrésze egyesíthető az aktuális céllal. Ha nincsen i lyen ak kor v isszalép l egutolsó dönt éséig és ot t egy következő lehetőséget választ A szabályok sorrendje meghatározza, hogy a program milyen sorrendben hozza létre a feladat egyes megoldásait. Rekurzív szabályok esetén előfordul, hogy a program végtelen ciklusba esik és nem áll le. Ez a veszély együtt jár a mélységben először kereséssel. A szabály-alapú reprezentáció [3] korlátozottabb nyelvű mint az elsőrendű logika és következtetési mechanizmusa kötöttebb, mint a rezolúciós előreláncoló tételbizonyító rendszereké. Ennek köszönhetően viszonylag hatékony következtetést tesz lehetővé. Előnye továbbá, hogy közelebb áll az emberi gondolkodás bizonyos formáihoz is. Egy tipikus szabályalapú rendszer ismeretbázisának

egyik főrésze az adatbázis, amely nem más mint az elemi tényállások halmaza. Az adatbázist szokás más néven munkamemóriaként is em legetni. A z adat bázis r ögzíti m indazon t ényeket, amelyeket egy probléma megoldásának adott pillanatában a világról ismerünk. A zárt világ f eltételezése t ermészetesen ér vényben v an: az az m inden állítás ami nincs benne az adatbázisban, hamisnak tekintendő. Az ismeretbázis másik fő része a szabálybázis, mely ha - akkor típusú s zabályok halmaza, amelyek értelmezése kissé eltér a logikai implikáció értelmezésétől: a következmény javaslat egy akció végrehajtására nem pedig egy egyszerű logikai állítás. A s zabály t ehát eg y f eltétel – akció pár os A f eltétel ol dal k ifejezi az okat a körülményeket, melyek között egy szabály eg yáltalán ak tivizálódhat. A f eltétel a minta adj a m eg, am ely adat bázisbeli t ényekre v onatkozik. A mintában, amely változókat

is t artalmazhat, t ények l ogikai k apcsolat def iniálható, i lletve t agadás fogalmazható meg. Az akció oldal adja meg mi történjék a szabály aktivizálódásakor az ún. tüzeléskor Hatására módosulhat az adatbázis, illetve input-output műveleteket hajthat végre a rendszer. A szabályalapú rendszerek alkalmazásának előnyei: • Modularítás: a s zabályok, am elyek az i smeretanyag egy-egy eg ységét képezik egymástól függetlenül hozhatók létre, törölhetők vagy módosíthatók • Univerzális megjelenítés: ismereteinket k izárólag s zabályok f ormájában fogalmazunk meg • Természetesség: a hétköznapi él etben i s igen s ok hel yzetben f eltételes szabályokkal fejezzük ki magunkat • Bizonytalanságkezelési lehetőségekkel a rendszer könnyen kiegészíthető A szabályalapú rendszerek alkalmazásának hátrányai: • Végtelen láncolás: mind adatvezérelt, mind célvezérelt esetben – éppen a modularítás m

iatt – könnyen írhatók olyan szabályok, am elyek es etében a következtető mechanizmus a feladatmegoldás során végtelen szabályláncot generál. • Új, a korábbiakkal ellentmondó ismeret beépítése lehetséges, m ivel nincsen ál talános m ódszer a szabályok es etleges el lentmondásainak ellenőrzésére, így a modularitás adta lehetőség miatt – egy új s zabály könnyen ellentmondásossá teheti a szabályrendszert • Meglévő szabályok módosításánál is fennáll az előző két lehetőség • A stratégiát módosító ún. meta-szabályokkal a beépí tett vezérlési stratégiát módosítani. E zek az onban f ormailag nem k ülönböznek a t árgyterületi ismeretanyagot leíró szabályoktól, ami megtévesztő lehet. Egy szabály jólstrukturáltságát erősen lerontja az, ha feltétel részében keverednek e kétféle ismeretanyagra utaló állítások • Nincs szabványosítva a szabályok nyelve, ez i mplementációnként nagyon

el térhet, am i a s zabálybázisok m ásik rendszerbe való átvitelét megnehezíti. Strukturált vagy keret-alapú reprezentáció A logika nem veszi figyelembe, hogy gondolkodásunk tárgyakhoz, objektumokhoz és főképpen azok közös jellemzőit megragadó fogalmakhoz, ún. osztályokhoz illetve prototípusokhoz k apcsolódik. M indezt k ihasználja az ún k eretalapú ismeretreprezentáció és k övetkeztetés [ 13], am ely l ehetővé teszi osztályok, osztály hierarchiák és adott osztályba tartozó eg yedek def iniálását és ez en obj ektumok hatékony manipulálását. Minsky a 70 -es év ekben f ejlesztette k i a k eret al apú reprezentációs m ódszert. N ála a k eret eg y tipikus, szterotip szituációt ábr ázol: minden át élt s zituáció a hoz zátartozó v iselkedéssel eg yütt eg y g ondolati egységet képez, am elyet ag yunk k eret f ormájában t árol. Ú j s zituációba k erülve a már átélt szituációhoz illesztve alakítjuk ki

viselkedésünket, elvárásainkat, miközben a korábbi keretet esetleg módosítjuk vagy új keretekkel bővítjük. A keret alapú ábrázolás [16] elterjedéséhez jelentős mértékben hozzájárult az objektum orientált programozás, amelynek néhány jellemzőjét felfedezhetjük a keretek között is. A hagyományos programozási technikákban a programok két egymástól független jól elkülönülő részre bonthatók: az algoritmikus részre és adatleíró részre. Az objektum orientált programozás e két r észt eg yesíti: obj ektumokkal dol gozik, am elyek m ind adatokat, m ind m ódszereket tartalmaznak. Az objektumok a s émákhoz has onlóan minden i nformációt, m ódszert t artalmaznak, am i a has ználathoz szükséges és a program működését az objektumok közötti kapcsolatok irányítják. Az obj ektum or ientált pr ogramozásban az obj ektumokat os ztályokba s zervezik. A z osztály nem más mint az objektum absztrakt modellje, amely a hozzá

tartozó tartózó objektumokról minden közös jellemzőt, módszert tartalmaz. Az osztály megvalósításai, az objektum elemek már konkrét, egyedi jellemzőkkel rendelkeznek és az o sztály és elemei között öröklődnek a jellemző adatok, eljárások. Az osztály változók értékei is öröklődnek, az elemi változók pedig az elem egyedi értékeit tartalmazzák. Az objektum orientált programozás főbb jellemzői közül több a keretalapú reprezentációban is megtalálható A k eret ol yan i nformáció-tárolási alapegység, m ely ös szefogja m indazon tulajdonságokat, melyek egyetlen objektumra jellemzők és azokat a relációkat, melyek ezen objektumot m ás objektumokhoz kötik. Mind a tulajdonságokat, mind a relációkat, r ekeszekkel ( slot-okkal) és a hoz zájuk t artozó ér tékek pár osaival l ehet leírni. A keretek mind osztályok, mind egyedek leírására szolgálhatnak Amennyiben a k eret os ztályt hat ároz m eg ak kor, az is-a

reláció s egítségével m egadható, hog y milyen m ás osztály alosztályának tekinthető. Így osztály hierarchia adható meg Ha keret eg y eg yed l eírására s zolgál, ak kor m eg k ell, adni , hog y melyik osztályhoz tartozik. E rre s zolgál az instance-of reláció. A hogy eg y obj ektumot t öbbféle nézőpontból tekinthetünk, ugyanúgy m egadhatjuk, hog y eg y obj ektum eg yszerre több osztály egyede is lehessen. A keret alapú rendszerekben alapvető következtetés az öröklődés: az egyes osztályok megöröklik a hierarchiában felettük elhelyezkedő osztályok rekeszeit és ha vannak ak kor az ok ér tékeit i s. E hhez has onlóan az eg yes eg yedek i s m egöröklik azon osztályok tulajdonságait és értékeit, amelyekhez tartoznak. A több helyről való öröklődés lehetősége konfliktushoz vezethet. Ennek feloldására több lehetőség van: • Ha a k onfliktus egy öröklődés mentén jött létre, akkor a legspecifikusabb osztály

meghatározásából származó értéket szokás elfogadni • Ha a konfliktus forrása több ágról való öröklődés, akkor ennek feloldásához különbséget kell tenni szükséges és tipikus tulajdonságok között. Eddig a pontig a keret alapú reprezentáció is lényegében logikai reprezentáció, csak más, az emberi olvasatot megkönnyítő strukturáltabb formában. Megváltozik a helyzet, ha m egengedjük, hog y az eg yes r ekeszekhez ne c sak ér tékeket, hanem számítási el járásokat is, demonokat vagy m etódusokat l ehessen r endelni. A démonok vagy metódusok akkor lépnek működésbe, ha a keretet manipuláljuk. A metódus típusa határozza meg az aktivizálódás feltételét: • az i f-needed t ípusú ak tivizálódásra ak kor k erül s or, ha eg y r ekesz ér tékére szükség vam, ám az ismeretlen • a when-changed típusú akkor lép működésbe, ha egy rekesz értéke megváltozik. Ebben az esetben a metódus előre meghatározott módon

vagy a régi vagy az új értékkel dolgozik A metódusok ugyanúgy öröklődnek mint a rekeszek és értékeik. A keret alapú reprezentáció alapfogalmainak összefoglalása: • keret vagy i degen s zóval frame névvel ellátott, megkülönböztethető tulajdonságokkal (attributumokkal) rendelkező objektum vagy fogalom ábrázolása • rekesz vagy slot az at tributumok áb rázolására szolgáló név vel, t ípussal, értékkel és alapértelmezéssel rendelkező memóriaterület • öröklődés az attributumok és az ok t ulajdonságainak át adása a hierarchikus kapcsolatok révén • démon vagy függvény az eg y-egy rekesz értékváltozását figyelő és a változáskor aktivizálódó eljárás A keret alapú reprezentáció előnyei: • Eseményvezérelt végrehajtás a dém onok, ol yan el járások, am elyek végrehajtása es eményvezérelt. A dém onok c sak akkor aktivizálják a rendszert ha az adott rekeszben előre specifikált

értékváltozás k övetkezik be. • Az ismeretek szervezése A keretek ismereteinket egy világos, áttekinthető struktúrába szervezik, ahol az eg yes r ekeszek t artalmának el érése közvetlenül történik. • Önvezérlés A keretek úg y v annak s trukturálva, hog y az adot t, pr oblémamegoldó helyzetben képesek meghatározni saját alkalmazhatóságukat. • Dinamikus értékek elhelyezése Az eg yes r ekeszek ér téke a pr oblémamegoldás során dinamikusan, könnyen változtatható • Deklaratív és procedurális ismeretek együttes ábrázolása A dek laratív ismereteket a rekeszek neve és tartalma, míg a pr ocedurális ismereteket az egyes rekeszekhez kapcsolódó démonok testesítik meg. A keret alapú reprezentáció hátrányai: • Prototípusoktól való eltérés: nagyon s ok v alós j elenség el tér a megszokott s émától. H a nem megfelelő absztrakciós szinttől indítottuk a keretek kibontását, a kivételek miatt nagyon elbonyolódhat a

rendszer. • Új szituációkhoz való alkalmazkodás problémás, ha ol yan új s zituációt vagy obj ektumot k ell r eprezentálni, am elyet nem t udunk a hierarchiába beilleszteni. Ez korlátozza a keret-alapú reprezentáció alkalmazhatóságát • A heurisztikus ismeretek ábrázolása problémás, míg a s zabályalapú rendszereknél k önnyen í rhatunk heur isztikákat i tt nem. Keretekkel például könnyen l e l ehet í rni eg y t ipikus betegséget, eg y ál talánosat, v alamely egyedi bet egség s pecifikus s zimptómáit, az onban az t, hog y az egyes szimptómák hogyan hatnak eg ymásra, í gy hog yan bef olyásolják a diagnózist, inkább szabályok segítségével lehet megadni. Ez az ok a annak , hog y t isztán k eret al apú es zközök hel yett i nkább hi brid rendszereket alkalmaznak, am elyek öt vözik a k eret- és a heur isztikus i smeretek leírására alkalmas szabályalapú reprezentálási módokat. A keret attribútumok közötti

kapcsolatokat, heurisztikus ismereteket lehet szabályokkal leírni. Természetesen egy hibrid rendszer következtető gépében ezért a keret-struktúra feladatmegoldásra való mozgósítását ellátó öröklődési-, dám on és eg yéb m echanizmusok mellett megtalálható a szabályok végrehajtását biztosító mechanizmusok is. 2.35 Ellenőrző kérdések 1, Mit nevezünk állapottérnek, kiinduló és célállapotnak és mik az operátorok? 2, Ismertesse az általános keresési algoritmus működését! 3, Mi(k)nek a módosításával és hogyan származtathatók ebből a különböző a gyakorlatban használt eljárások? 4, Sorolja fel a keresési eljárások legfontosabb jellemzőit! 5, M it nevezünk heur isztikus k eresésnek és az m ilyen m ódon gyorsítja az eljárást? Mondjon erre néhány példát. 6, Sorolja fel különböző szempontok alapján az Ön által ismert ismeretreprezentációs módszereket! 7, Mi az alapvető különbség a

procedurális és a deklaratív ismeretreprezentáció között? 8, I smertesse r öviden a m atematikai l ogika al apú i smeretreprezentációt és hog y hogyan történik ebben az esetben a következtetés? 9, Ismertesse a rezolúció elvét és a Horn klózok alkalmazását! 10, Ismertesse a szabályalapú rendszerek felépítését, legfontosabb jellemzőiket, előnyeiket és hátrányaikat! 11, M i a k eret ( frame), hog yan épül f el, m ik l egfontosabb t ulajdonságaik, alkalmazásuk előnyei és hátrányai? 12, Ismertesse röviden a démonok működési mechanizmusát! 2.3 Bizonytalanság kezelése Tapasztalataink s zerint a l ogika c sak eg yik fajtája az emberi gondolkodásnak. Gondolkodásunk alapja lehet egészen más is, m int am i a l ogika s egítségével formalizálható. K épesek v agyunk bi zonytalan, hi ányos, nehez en f ormalizálható vagy el lentmondásos i smeretek al apján i s r acionális dönt éseket hoz ni. E hhez kapcsolódik ag yunk az on k

épessége, hog y em lékezünk, t ehát hasznosítani tudjuk a korábbi feladatok során szerzett tapasztalatokat és így el tudjuk kerülni korábbi hibáinkat valamint képesek vagyunk hasonlóságok, analógiák alapján is feladatok megoldására. A bizonytalanságnak több forrása van: egyrészt eredhet a világ természetéből, akkor ha az egyes tulajdonságait eleve elrejti, vagy ha az nem-determinisztikus, azaz következő állapotát nem határozza meg egyértelműen a pillanatnyi állapota és az abban végrehajtott akció, másrészt nem gyűjtöttük össze, vagy nem áll rendelkezésre a probléma megoldásakor számba jövő valamennyi ismeret. Újabb ismeretekre szert téve megváltozhat véleményünk korábbi ismereteinkről. Például ha egy műhelyben erősen csikorgó hangot hallunk forgácsolás közben, akkor erős a gyanúnk, hogy az éppen megmunkálást végző szerszám törött. Ha megnéztük magát a szerszámot akkor már bizonyosak lehetünk, hogy az

törött-e vagy sem. Egy új ismeret t ehát bi zonyosságot s zolgáltathat m ás, k orábbi vélekedésünkről. Ezért a bizonytalan következtetés nem monoton, azaz bár mit is vélünk, új ismeretek fényében megváltozhat vélekedésünk. Milyen módszerek alkalmasak a bi zonytalanság k ezelésére? A valószínűségelmélet adja azt az eszközt, amelyek segítségével a mondatokat vélekedéssé alakítjuk (azaz felcímkézzük) és ezekből a vélekedésekből következtetéseket vonunk le. Ez a megközelítés a valószínűségi logika A nemmonoton logikák gyakorlatban is felhasználható elméleti keretet adnak a hiányos ismeretek esetére. Végül a heurisztikus jellegű technikák egyes esetekben jól használhatók, ug yanakkor al kalmazásukkal az el méleti hát tér hi ánya miatt vigyázni kell. 2.31 Bayes módszere A valószínűségi logikában a mondatok valószínűségi értékekkel vannak ellátva, amely azt fejezi ki, hogy mennyire erős az a

vélekedésünk, hogy az állítás igaz. Ha az érték 0 ak kor bizonyosak vagyunk az állítás ham isságában, ha 1 ak kor meg vagyunk győződve annak igazságában. Ha egy véletlen változó, am ely a világ egy állapotának jellemzésére szolgál, akkor a valószínűségi eloszlás adja meg, hogy az egyes értékeket milyen valószínűséggel veheti fel. Ha egy új valószínűségi változó értékét megismerjük, az befolyásolhatja eddigi vélekedéseinket. Ezt fejezi ki a feltételes valószínűség: ha tudjuk, hogy egy B esemény bekövetkezett, ak kor az m ennyire v áltoztatja m eg eg y m ásik A esemény bekövetkezésében való bizalmunkat. A feltételes valószínűséget általában P(A|B)-vel jelöljük és értéke: P(A|B) = P(AB)/P(B) feltéve, hogy P(B) nem 0 Az együttes valószínűségi eloszlás kimerítő módon megadja az összes állítás valószínűségi eloszlásainak kombinációját. Ez n változó esetén egy n dimenziós táblában

foglalható össze. Lássuk ezt egy egyszerű példa kapcsán: Forgácsolás közben fellépő csikorgás a szerszám túlkopására és törésére utal, azonban a két jelenség nem minden es etben j ár eg yütt. A j elenségek valószínűségét összefoglaló táblázat így nézhet ki: törés nincsen törés csikorgás 0.04 0.01 nincs csikorgás 0.06 0.89 Egy valószínűségi változó feltétel nélküli értékét úgy kapjuk meg, hogy összegezzük az értékeket a s orok illetve az oszlopok m entén. P éldául a törés valószínüsége: 0.04+006=01 A feltételes valószínűség értékét pedig a valószínűségszámítás axiómáiból határozhatjuk meg: P(törés|csikorgás) = P(törés^csikorgás) / P(csikorgással) = 0.04 /(004+001) = 08 A fenti táblázat mérete a valószínűségi változók számával exponenciálisan nő; n két értékű logikai változók esetén 2 n cellából áll. E zért a g yakorlatban használhatatlan méretűre dagad.

Új, ismeretlen valószínűségi valószínűségek eloszlással való kiszámításakor számolás, elkerülhető ha közvetlenül az együttes a feltételes valószínűségekkel dolgozunk. Ehhez szükség van Bayes tételére, amely kimondja: P(H|E) = P(E|H) * P(H)/P(E) A tétel segítségével kiszámíthatjuk egy H hipotézis valószínűségét egy bizonyosságot s zolgáltató E t ény j elenlétében. A m ódszer az ért használható, mert s ok es etben a P (H), P (E) és P (E|H) é rtékek k önnyebben meghatározhatóak m int P (H|E) ér téke. K ülönösen ál l ez azokra az esetekre, amikor a v ilág ok -okozati ös szefüggéseit di agnosztikai c élra akarjuk felhasználni. A Bayes módszer alkalmazásának előnyei: • szilárd matematikai alapokon nyugszik • jól definiált jelentéssel bír A Bayes módszer alkalmazásának hátrányai: • nagyon sok valószínűséget kell megadni, és egyetlen egy sem hiányozhat ahhoz, hogy számolni

tudjunk • hogyan adjuk meg az apriori valószínűségeket? Statisztikai mintavétellel vagy szakértői becslés al apján és m ennyire m egbízhatóak ez ek a valószínűségi értékek • a tárgyterület megváltozásakor a teljes korábbi valószínűség-kiosztást f elül kell bírálni, ami a t eljes ismeretbázis módosítását vonja maga után. Tehát a rendszer nem építhető fel lépésről lépésre • a módszerrel meghatározott valószínűségek nem igazán magyarázhatóak, mivel a hipotézisek és a bi zonyítékok k özötti k apcsolatok ál talában összetettek és azok egyszerű számokkal történő ábrázolása mindenképpen információvesztéshez vezet 2.32 Fuzzy rendszerek A fuzzy logika lehetőséget biztosít a modell alapú rendszertervezés intucióval és mérnöki heur isztikákkal v aló t ámogatására. A m indennapi ny elv el emeit használja a rendszer k ívánt v iselkedésének l eírására és í gy bony olult rendszerek

tervezéséhez és optimálásához nyújt hatékony eszközt a s zokásos matematikai modellek használata nélkül. Folytonos változókkal képes dolgozni és a hagyományos kétértékű logikával szemben képes kezelni parciális és többértékű igazságokat is. A fuzzy modellek használata k ülönösen ak kor előnyös, ha az aktuális probléma matematikailag nehezen kezelhető az adatok hiányos v olta, v agy a f olyamatok t úlzott bonyolultsága miatt. Robosztus rendszerek felépítését teszi lehetővé, melyek hiányos és zajos bemeneti adatok alapján is képesek hibamentes működést biztosítani. A valós világ nyelvének használata lehetővé teszi, hogy az emberi logika becslő természetével vértezzük fel a számítógépet. További előnyök nyilvánulnak meg, ha már meglévő szimbolikus tudást akarunk beépíteni a rendszerbe. A ny elvi modellezés has ználata nag yban m egnöveli a r endszer m ódosíthatóságát, ez pedig rövid fejlesztési

ciklusokhoz és könnyű programozhatósághoz vezet. A továbbiakban a fuzzy alapfogalmakat és a műszaki alkalmazásokhoz feltétlenül szükséges technikákat ismertetjük meg. A hal mazelmélet s zerint a hal maz m eghatározott t ulajdonságú objektumok összessége. A hal mazokat el emeik f elsorolásával v agy a definiáló feltételek körülírásával lehet megadni. E z a k örülírás az ún tagsági f üggvény, am ely az objektumokat k ét c soportra, a hal mazhoz t artozó i lletve a halmazhoz nem tartozó el emekre os ztja. A t agsági f üggvény a hag yományos értelemben éles határt v on e k özött a k ét c soport k özött. A f uzzy hal mazelmélet egyfajta bizonytalanság bev ezetésével ez eknek a m erev határoknak az elmosására törekszik. Zadeh [19] ezt a két értékű tagsági függvény általánosításával oldotta meg. A z eg yes obj ektumok hov atartozását [0,1] intervallumbeli s zámmal jellemezte, ahol 1 az t jelenti, hogy benne v an,

a 0 az t, hogy nincs benne, míg egy 0 és 1 közötti szám azt f ejezi ki, hogy m ennyire vagyunk biztosak abban, hogy az adot t obj ektum el eme a hal maznak. Í gy a fuzzy halmazok a hagyományos halmazok általánosításaként is felfoghatók. A fuzzy tagsági függvény matematikai definiciója tehát [4]: µa(x): D >[0,1] úgy, hogy µa(x) = 1 : x definit módon A-hoz tartozik µa(x) = 0 : x definit módon nem tartozik A-hoz µa(x1) > µa(x2) : x1 jobban beletartozik A-ba mint x2 A halmazelméleti műveletek Zadeh által javasolt kiterjesztése a következő [4]: µ[AvB](x) = max{µA(x),µB(x)} unió µ[A^B](x) = min{µA(x),µB(x)} metszet µ~A(x)=1-µA(x) komplementer halmaz A f uzzy hal mazok i nterfészként s zolgálnak az em berek ál tal has znált ny elvi változók és a számítógépeknek megfelelő megközelítés között. A f uzzy r elációk el méletének al apjait s zintén a hagyományos halmazelmélet relációi k épezik. A hag yományos ér

telemben v ett relációk két halmaz elemi között teremtenek kapcsolatot. A fuzzy relációk hasonlóan értelmezhetők azzal a k iegészítéssel, hog y a viszony erősségének jellemzésére tagsági függvényt vezetünk be, amelyek nemcsak a kapcsolat létéről, hanem annak mértékéről is információval szolgál. Ezt mutatja be a következő példa is: Egy patakot folyási sebességével és vizének hőfokával jellemezünk. A folyási sebesség v[m/s] = {2,4,6,8,10}, a vízhőmérséklet pedig T[°C] = { 5,10,15,20,25}. A g yorsat a vgyors {(2;0),(4;0.3),(6;09),(8;1),(10;1)} míg hi deget a T hideg {(5;1),(10;1),(15;0.7),(20;02),(25;0)} fuzzy hal mazok hat ározzák m eg Ezek direkt szorzatát a következő táblázat adja: vT 5 10 15 20 25 2 0 0 0 0 0 4 0.3 0.3 0.3 0.2 0 6 0.9 0.9 0.7 0.2 0 8 1 1 0.7 0.2 0 10 1 1 0.7 0.2 0 A g yakorlati f elhasználásokban k ulcsfontosságú s zerepet j átszik a k ompozició elnevezésű

fuzzy művelet, amely nem más mint a relációk láncolása. A kompozició matematikailag korrekt értelmezését az alábbiakban adjuk meg: Legyen R1(x,y) = {[(x,y);µ1(x,y)]| (x,y) ∈ X x Y} R2(y,z) = {[(y,z);µ2(y,z)]| (y,z) ∈ Y x Z} akkor az R12(x,z) = {((x,z);maxy min[µ1(x,y),µ2(y,z)])| (x,y,z) ∈ X x Y x Z} kifejezés az fuzzy relációk ún. max-min kompozicióját határozza meg Példa: Legyen R1(x,y) és R 2(y,z) két fuzzy reláció, amelyek egyszer az x nagyobb mint illetve az y kb. ugyanakkora mint z összefüggéseket definiálják: 1 2 5 10 1 5 10 20 2 0.9 0.5 0.1 0 1 1 0.1 0 0 5 1 0.9 0.5 0.1 2 0.9 0.2 0 0 10 1 1 0.9 0.5 5 0.1 1 0.5 0.1 10 0 0.2 1 0.3 x nagyobb mint y y körülbelül ugyanakkora mint z A fenti két reláció láncolásának numerikus eredménye a következő táblázatban látható, am elynek ér telmezése: x nag y m int y ugyanakkor körülbelül azonos nagyságú z-vel. xz 2 1 0.9 5 0.2 10 0.1

20 0.1 5 10 1 1 0.5 0.9 0.5 0.5 0.1 0.3 A következtetés nem m ás m int a hal maz-reláció k ompoziciója, am elynek eredménye a következmény tagsági f üggvénye. Leg yen A eg y f uzzy hal maz olyan, hogy abból Következzék B fuzzy halmaz , akkor létezik olyan R relációs következtető mátrix, amely elő tudja állítani a B = A°R következtetést és tagsági függvénye a következőképpen néz ki: µR(x,y) = min{µA(x),µB(y)}, x ∈ X, y ∈ Y Ha több reláció van ugyanazon a hal mazon ér telmezve ak kor l étezik az az R reláció, amely egyszerre tudja előállítani az A1 B1; A2 B2;.An Bn következtetéseket és tagsági függvénye az alábbi: µR(x,y) = max{µR1(x,y),µR2(x,y),., µRn(x,y)}, x ∈ X, y ∈ Y Mint már említettük a fuzzy relációk és az ezzel kapcsolatos műveletek nagy jelentőségűek a gyakorlati élet szempontjából. A fuzzy rendszerek a hagyományos szakértői rendszerekhez hasonlóan szintén szabályalapúak, ahol az i

smereteket a k övetkeztetési s zabályok j elentik, de m ás megközelítést használnak a szabályok nyelvi elemeinek reprezentálására. Az alapvető céljuk is hasonló, vagyis a szakértők tudását HA.AKKOR típusú szabályok formájában j elenítik m eg a r endszerben. H a pél dául eg y x bemeneti és egy y kimeneti változónk van akkor a következő logikai implikáció alapú szabályt alkalmazhatjuk: HA az input x értéke A akkor az out put értéke legyen B, ahol A és B fuzzy halmazok µA és µB tagsági függvénnyel A ny elvi k ifejezésekkel a dott szabályok kiértékelését f uzzy k övetkeztetésnek nevezzük. A legtöbb f uzzy l ogikán al apuló r endszer pr odukció s zabályokat használ a ny elvi v áltozók és az es emények közötti kapcsolatok leírására. A szabályok f eltétel r észe eg y v agy t öbb É S v agy V AGY ny elvi kapcsolattal összekapcsolt feltételből áll. A f uzzy k övetkeztetés f olyamata k ét eg ymástól j ól el

választható r észre: az aggregációra és a k ompozicióra k ülönül el . A z ag gregáció f uzzy oper átorokat és r elációkat al kalmazva hat ározza m eg, hog y m ilyen m értékben t eljesül az adott szabály feltétel oldala. Tegyük fel, hogy adott az alábbi szabályrendszer i szabállyal és j változóval: sz1: HA x1 = A1,1 ÉS xj = Aj,1 AKKOR y = B1, szk: HA x1 = A1,k ÉS xj = Aj,k AKKOR y = Bk, szi: HA x1 = A1,i ÉS xj = Aj,i AKKOR y = Bi, Első lépésként az egyes szabályok információtartalmát és az implikáció definicióját f elhasználva r elációs m átrixot hoz unk l étre, m ajd az így kapott mátrixokat eg yetlen r egyesítésének ös elációs m átrixszá al akítjuk a szefüggését al kalmazva. Ezt a f következtetések olyamatot hí vjuk aggregációnak. A következtetési folyamat második l épése eg y hal mazreláció k ompozició, melynek során az előbb létrehozott mátrix segítségével a feltételek

érvényességéből meghatározzuk a következmények érvényességét. Fuzzy input Fuzy output Fuzzy rendszer A B 2.31 ábra Fuzzy rendszer fuzzy inputtal és outputtal A szokásos MAX-MIN következtetési módszernél a szabály következményének érvényessége megegyezik a feltétel érvényességével. Fejlettebb következtetési módszert jelent a Fuzzy Associative M aps, ahol a s zabályokhoz a fontosságukat jellemző súlyokat rendelünk. Tehát a szabályok maguk is fuzzy-k lehetnek abban az értelemben, hogy érvényességük 0 és 1 között tetszőleges lehet. Vezérlési al kalmazásokban [ 2] a f uzzy l ogikát a vezérlési stratégia köznapi nyelven történő leírására használjuk. Minden vezérlési stratégia célja adott bemenet mellett adott kimenet el érése. M ivel a v ezérelt r endszer nem k épes értelmezni a fuzzy nyelvi el emek ez ért k étirányú f ordítás s zükséges a pont os érték és a nyelvi változók között. A fuzzy

logikán alapuló vezérlés működése során alapvetően három lépést különböztetünk meg: • Fuzzyfikálás: a valós ( bemeneti) ér tékek l efordítása ny elvi k ifejezésekre, melyeket fuzzy halmazok reprezentálnak • Fuzzy következtetés: a nyelvi v áltozók k özötti ös szefüggéseket def iniáló szabályhalmaz kiértékelése • Defuzzyfikálás: a fuzzy következtetés er edményeinek v isszafordítása v alós (kimenő) értékekre Ismeretbázis mért értékek beállítandó értékek Fuzzy következtetés Nyelvi szint Fuzzyfikálás Defuzzyfikálás Technikai szint Mért értékek Beállítandó értékek Vezérelt folyamat 2. 32 ábra Fuzzy vezérlés alapvető strukturája A fuzzy logikát a v alós v ilág ny elvének has ználata t eszi i gazán hat ékony eszközzé. A nyelvi változók alkalmazása m eghatározó f ontosságú a f uzzy szakértői és szabályozó rendszerek területén. A nyelvi változók értékei szavak, mondatok, v

agyis hét köznapi ny elvi el emek. A l egtöbb valós helyzetben egy precíz vá lasz nem jelent feltétlenül optimális megoldást a pr oblémára. A fuzzy logika kiterjeszti a szigorú igaz/hamis osztályozás olyan értékekkel mint például a nagyjából igaz és a teljesen rossz. A s ebességet nag yon g yors, g yors, l assú, nag yon l assú k ategóriákba s oroljuk be. A nagyon lassú halmazba 20 km/óra alatti sebességértékek tartalmaznak A lassú k ategóriába a 40 k m/óra k örüli s ebességek tartoznak. Ezeket nyelvi változóknak, m agát a f olyamatot f uzzyfikálásnak nevezzük. Minden egyes értékhez tartozik legalább tagsági fok, ahogy ezt a 2.33 ábra is mutatja Nagyon lassú Nagyon gyors 1.0 0.5 0 2.33 ábra Példa a fuzzyfikálásra A fuzzy szabályok alkalmazásának számos előnye van a hagyományos értelemben vett szakértői rendszerekkel szemben. Míg a hagyományos szakértői rendszerekben a szabályok érvényességét pontosan

definiálni kell és így könnyen el lentmondásba k everedhetünk, a f uzzy r endszerekben a ny elvi változókkal reprezentált mennyiségek lehetővé teszik a részleges igazságot egy vagy több halmazban is. A f uzzy s zabályok k iértékelésével k apott er edmény szintén fuzzy, tehát ezen értékeket valós értékekké kell visszaalakítani. Ezt nevezzük defuzzyfikálásnak, melyre különböző eljárások szolgálnak. Mivel egyidejűleg több kifejezés is érvényes l ehet ezek eg yüttes f igyelembevételével k ell a rendszernek döntését meghoznia. A három legelterjedtebben használt eljárás: • a Center-of-Maximum • a Center-of-Area és • a Mean-of-Maximum A C enter-of-Maximum es etén a t agsági f üggvények m aximumhelyének súlyozott átlagaként számolja ki a kimeneti értéket, ahol a súlyok a megfelelő szabályok kimeneti értékei. A C enter-of-Area módszer talán a l eggyakrabban has znált el járás, num erikus integrálást

használ a tagsági függvények által határolt terület kiszámítására és az így kiszámított terület súlypontja a defuzzyfikálás végeredménye. A M ean-of-Maximum módszer a legnagyobb érvényességi fokkal rendelkező kifejezés maximumaként számolja ki a kimenetet. A 234 ábra a Center of Area defuzzyfikálás f olyamatát m utatja be, ha a r endszer ismeretbázisában a következő két szabály szerepel: HA x = A1 ÉS y = B1 AKKOR z = C1; HA x = A2 ÉS y = B2 AKKOR z = C2 A1 B1 X A2 C1 Y B2 Z C2 Z COA X Y Z 2.34 ábra Defuzzifikálás Center of Area eljárással 2.33 Szimbolikus, nem-numerikus modellek A m odellek ez en os ztályának es etében nem bizonytalansági mértéket használunk, hanem megengedjük, hogy amennyiben kellő információ hiányában helytelen következtetésre jutunk, azt visszavonhassuk. Szemben a hagyományos következtető rendszerekkel, amelyek három fő tulajdonsága. A teljesség, konzisztencia és a monotonitás, a nem

-monoton ún. m odális l ogikák es etén ny elvi es zköz szolgál a bizonytalanság kifejezésére. A nem-monoton következtető rendszereknél az alábbi problémák merülnek fel: • hogyan biztosítható, meglévő és hiányos ismeretek alapján is lehessen következtetéseket levonni • hogyan kell az ismeretbázist módosítani új tények beillesztésekor illetve régiek törlésekor • hogyan has ználjuk f el az i smeretbázisban t ároltakat, olyan konfliktushelyzetekben, am ikor az ok el lentmondó k övetkeztetésre jutunk Egy nem-monoton következtető rendszer két jól elkülönített komponensből áll: • a pr oblémamegoldó k omponens a s zabályalapú r endszerek következtető gépéhez hasonló funkciók mellett további speciális funkciókat nyújt a másik komponensnek • érvényesség karbantartó k omponens, am ely el lentmondás es etén megkeresi az el lentmondást ok ozóját és k iiktatja ez t a feltételezést. Természetesen a k

orábbi k övetkeztetéseken i s végigviszi ennek a visszavonásnak a következményeit. A visszalépés megvalósításához a következőket kell biztosítani: • a végrehajtási fa minden csomópontját kiegészítjük az őt támogató igazolások leírásával • egy mechanizmust, amely a c somópont el lentmondásának észlelésekor kiszűri a nem megfelelő feltételezéseket • egy mechanizmus, amely kiválaszt egy nem megfelelő feltételezést és visszavonja annak minden hatását A nem -monoton rendszerekben al kalmazott i smeretreprezentáció l ényegében szabályalapú, ahol a szabályok feltételrésze kiegészíthető egy ún. UNLESS taggal. 2.34 Heurisztikus módszerek Az ismeretalapú rendszereknél alkalmazták először a bizonytalanság heurisztikus módszereit, melyek a szimbolikus és numerikus formalizmust együttesen használják. Ezeknek a formalizmusoknak az ún. bizonyossági tényezői numerikus értékek, amelyeknek a következtetések

során történő kiszámítása specifikus számítási eljárás alapján történik és a k övetkeztetés v ezérlésének egyik es zköze. A heurisztikus módszerek empirikus úton megerősített értékekkel és eljárásokkal dolgoznak. A feladatok többségénél nem alkalmazható a valószínűségszámítás, mert nem rendelkezünk megfelelő valószínűség értékekkel. A bizonyossági elmélet ezen úgy segít, hogy az események valószínűsége helyett közelítő értékekkel dolgozik. Jó példa er re a M YCIN-nél alkalmazott bizonyossági tényező (BT), ahol ennek értékét egy skála alapján határozzák meg: -1 -0.8 -0.6 -0.2 hamis majdnem valószínűleg 0 0.2 ismeretlen bizonyosan hamis 0.6 0.8 1 BT valószínűleg majdnem igaz igaz bizonyosan hamis igaz Az így meghatározott értékeket tények és s zabályokhoz l ehet k apcsolni és a következtetés során a végeredmény bi zonyossági f oka i s m eghatározható. A bizonyossági

tényező kiszámítása másképpen történik, mint a valószínűségek kiszámítása. Egy szabály BT bizonyossági tényezője a szabályba vetett bizalom és bizalmatlanság mértékének különbsége, azaz: BT = (MB - MD) / (1- min(MB,MD)) Azokban a szakértői rendszerekben, amelyek lehetővé teszik a bizonyossági tényező számítása különböző módszerekkel történik: • ha bi zonytalan t ényekkel dol gozunk, ak kor a hozzájuk rendelt bizonyossági tényezők értéke egy tapasztalati skála alapján becsülhető • ha bi zonytalan s zabályokat has ználunk, ak kor annak bizonyossági tényezője megadja, hogy ha a premissza teljesül, mi lesz a konkluzió bizonyossági tényezőjének értéke. Például: IF P THEN K BT=08 • ha a s zabályban a P bizonyossági pr emissza bi zonytalan, ak kor a k onklúzió tényezőjének értékét a premissza és a szabály bizonyossági tényezőinek szorzat adja. Például IF P THEN K BT=08 és

BT(P)=0.5 akkor BT(P,K)=04 • ha a s zabályban egyszerre több bizonytalan premissza és ezek logikai és kapcsolatban vannak egymással, akkor: BT(K,P1 AND P2 AND . AND PN) = min (BT(Pi)*BT(szabály)) • ha a s zabályban a pr emisszák l ogikai v agy k apcsolatban ál lnak egymással akkor: BT(K,P1 OR P2 OR . OR PN) = max (BT(Pi)*BT(szabály)) Általános megjegyzések: • egy s zabály v égrehajtásakor a k onklúzió bizonyossági tényezője nem lehet nagyobb, mint a szabály premisszái közül a legnagyobb • feladatmegoldás során a bizonyossági szint a következtetés során soha nem nő, inkább csökken • a módszer nem rendelkezik jól megalapozott elmélettel, de jól működik. Sokak szerint csak bizonyos es etekben has ználható ad hoc megoldásról van szó 2.35 Ellenőrző kérdések 1, Miből adódik az ismereteinkkel kapcsolatos bizonytalanság és milyen módszereket ismer a bizonytalanság reprezentálására 2, Fogalmazza meg a valószínűségi

alapon működő következtetés lényegét! 3, Sorolja fel a Bayes módszer előnyeit és hátrányait. 4, Ismertesse a fuzzy halmaz fogalmát és a halmazelméleti műveletek definicióit 5, Foglalja össze fuzzy következtető rendszerek működésének három egymásután következő lépését 6, Adja meg a fuzzy relációk láncolásának definicióját 7, Mik az ún. nyelvi változók? 8, Mi az ún. bizonyossági tényező? 9, Milyen szabályok alapján történik a bizonyossági tényezők kiszámítása? Ismertesse ezeket a szabályokat! 2.4 Ismeretalapú rendszerek felépítése 2.41 Ismeretalapú rendszerek felépítése és főbb moduljai Az ismeretalapú rendszerek alatt olyan újszerű programstruktúrával rendelkező rendszereket értünk, amelyek a pr obléma-területet l eíró i smereteket ex plicit formában, a rendszer többi területétől elkülönítetten ún. ismeretbázisban tárolják [6] Ezen belül pedig az olyan ismeretalapú rendszereket, amelyek

szakértői ismeretek felhasználásával az emberével összevethető teljesítményt nyújtanak egy szűk problémakör kezelésében szakértői rendszereknek nevezünk. Ebből következően jól elkülönül egy m ástól az i smeretbázis v alamint az ál talános pr oblémamegoldó ismereteket tartalmazó ún. következtető gép, amely az ismeretreprezentációtól függő keresési m ódszerrel dol gozik. E zeket eg észítik a rendszer használatát elősegítő további modulok. Ismeretbázis Munkamemória Következtető gép Ismeretszerző alrendszer Magyarázó modul Felhasználói felület 2.41 ábra Ismeretalapú rendszerek felépítése Az ismeretbázis a rendszer hosszú t ávú m emóriája, ál talában k étféle i smeretet tárol: • a szituációkat leíró tényeket • és heur isztikákat, am elyek a pr obléma m egoldásánál használható szabályok, módszerek A következtető gép működésekor következtetések sorozatát hajtja végre és

ennek révén jut el a f eladat m egoldásához. E zt a f olyamatot a k övetkeztetési mechanizmus vezérli. Sorra kijelöli a m unkamemória és az i smeretbázis alapján a f elhasználható s zabályokat és el járásokat. Ha például egy szabály feltétel része teljesül, a k övetkezmény új tényként a m unkamemóriába kerül. A következtető gép alapvetően kétféle stratégiát alkalmazhat: • adatvezérelt ( forward-chaining) k övetkeztetést, am ikor az adatokból kiindulva keres megoldást vagy • célvezérelt következtetést, amely a bi zonyítandó célból indul ki és keresi azokat a tényeket, összefüggéseket, amelyek alapján be tudja bizonyítani a kitűzött célt. A munkamemória a következtető gép munkaterülete, amelyben a konkrét feladat kiinduló adatait, közbülső eredményeit a külvilágból érkező vagy onnan kért információt t ároljuk az i smeretbázisban al kalmazott reprezentációs formában. Ez tehát a rendszer

rövidtávú memóriája és adatai a pr oblémamegoldás befejezésével törlődnek. A munkamemória egy speciális formája az ún blackboard Ezt akkor használjuk, ha egyidejűleg több rendszer működik egymással párhuzamosan és egymás er edményeit v agy r észeredményeit has ználni k ívánják. E bben az esetben ezeket a tényeket egy közösen has znált t erületre a bl ackboard-ra k üldik, am elynek használata külön adminisztrációt, felügyeletet igényel. A magyarázó modul révén betekinthetünk a rendszer működésébe, megtudhatjuk, hogy milyen összefüggések használata r évén j utott el a r endszer az er edményre. Egyes r endszerek a k övetkeztetési f olyamatot g rafikusan m utatják be és lehetővé teszik a mi lenne, ha kérdést egy-egy megoldási változat kidolgozásához. A felhasználó felületnek háromfajta felhasználó kell kiszolgálnia: • a kész rendszer alkalmazóját • az ismeret vagy tudásmérnököt aki fejleszti a

rendszert és • a szakterület szakértőjét, aki az előbbiekben említett mindkét módon viselkedhet A felhasználói felület ezen személyeknek lehetővé teszi az adatok bevitelét a rendszer használat során. Erre a s zokásos s zöveges m egadási m ód m ellett eg yre jobban el terjedt az i konok, m enük és eg yéb k épi i nformáció has ználata, am ely alapjában v éve az adot t oper ációs r endszer s zolgáltatásai épül . J ó pél da er re a Kappa-PC szakértő keretrendszer, amely a Windows valamennyi szolgáltatását egyszerű módon elérhetővé teszi a felhasználó (ebben az esetben a rendszer programozója) számára. 2.42 Adat, információ, tudás és szakértői ismertek Ezeket a fogalmakat még a számítástechnikán belül is sokféleképpen értelmezik. Mi ebben a jegyzetben a számítógépes döntési folyamatban játszott szerepük alapján különböztetjük meg őket: • Az adat egy észlelt, de nem értelmezett szimbólum, tehát

nyers jelentés nélküli szintaktikai fogalom, amely egy értelmezési folyamat bemenetén áll. • Az információ ezzel szemben már értelmezett adat, amely tehát jelentéssel bíró szemantikai fogalom. • Az ismeret vagy tudás pedig nem más mint egy döntési folyamat során felhasznált (megtanult és hasznosított) információ. Adat Ismeret passzív aktív egyszerű érzékelhető, mérhető dolog ökölszabály vagy tény, törvény vagy elv kevés értelmezés vagy elemzés után leírhatók megszerezni, rendszerezni, formalizálni nehéz az adatbázis adatokat tárol megfelelő az ismeretbázis ismeretdarabkákat tárol reprezentációban adatbázis-alkalmazások bemeneti/kimeneti a kommunikáció természetes nyelvű oldalán adatok találhatók egy adatnak az ember ad jelentést a kimenő információnak az ember ad jelentést Jól szemlélteti a fentieket a történet amikor, a hajó kapitánya leszól a fedélzetről a gépházba: Mennyi? 15 hang zik

a v álasz. Mi 15? S zól az újabb kérdés Mi mennyi? Szól erre az újabb választ. A tudás a filozófiai megközelítés szerint a való világ visszatükröződése az emberi tudatban, melynek nem minden része fejezhető ki szavakkal. A tudásnak a közölhető, verbálisan leírható részét nevezzük ismeretnek. Így a számítógépen tehát ismerteket és nem t udást t árolunk. A m agyar s zakirodalom s okszor helytelenül az ismeret helyett a tudás szót használja 2.43 Hagyományos programok és ismeretalapú rendszerek összehasonlítása Az al ábbi t áblázat a hag yományos és az ismeretalapú rendszerek alapját képező adatok és az ismeretek összevetését foglalja össze: Emberi szaktudás Mesterséges szakismeretek Mulandó (elfelejtődik, kihal) Állandó és tartós Nehéz átadni és reprodukálni; oktatással Könnyű átvinni, reprodukálni terjeszthető Nehéz dokumentálni Könnyű dokumentálni Nem mindig következetes, gyakran

emócionális Mindig következetes, de érzéketlen Nagyon meg kell fizetni és nehezen elérhető el Elérhető áron megszerezhető, a helyszínra vihető és sokszorosítható Kreatív, innovatív Ihlettel, lélektelen A körülményekhez alkalmazkodik, tanul Csak azt tudja amit beleépítettek Általában ismeri képességeinek korlátait Nincs tudatában ismeretei korlátozottak Az ember környezetéhez különböző A rendszer felhasználói felülete általában egyféle érzékszerveivel kapcsolódik Gondolkodási folyamatai változatosak, gazdagok A belső feldolgozás szimbólumokkal manipulál Széles látószögből, több aspektusból vizsgálja a Szűk, technikai látószögből tud a problémákkal megoldandó problémát foglalkozni. Jellemzően felszíni tudással operál Van józan esze Nincsen hétköznapi értelemben véve józan esze. Nem lehet vakon hinni benne. Javaslatot, tanácsot ad 2.43 Ellenőrző kérdések 1, Ismertesse a szakértői

rendszerek felépítését és ezen belül az egyes modulok szerepét 2, Sorolja fel milyen következtető rendszereket ismer! 3, Mit tartalmaz az ismeretbázis? 4, Miben különbözik, az adat, az információ és a tudás illetve szakértői ismeretek? 5, Mi a különbség a tudás és az ismeretek között? 6, Hasonlítsa össze az emberi és a mesterséges szakismereteket! 2.5 Alaptechnikák 2.51 Induktív rendszerek Az induktív következtetés egyedi esetekből, példákból jut általános érvényű következtetésre, szemben a logikai r endszerek deduk tiv k övetkeztetéseivel, am ely az általánosból indul ki. Az induktív technikák a gépi tanulás egyik korai eredményén, példák alapján történő tanulás módszerén alapulnak, ahol az ismereteket egy véges példahalmaz tartalmazza és a példákból szabályokat generál a rendszer. Az induktiv rendszert az alábbiak jellemzik: • az ismeretbázis általában t áblázatos f ormában t artalmazza a

példákat • egy algoritmus a fenti példák alapján szabályokat generál és ezek a szabályok bekerülnek az ismeretbázisba • a következtető rendszer egy új problémánál a legjellemzőbb szempontok al apján k eres has onló pél dát és a példához tartozó megoldás lesz az er edmény. H asonló pél da hi ányában nem ad megoldást. Ismeretreprezentáció Példákat tartalmazó mátrix: attributumok és értékek Következtetés és vezérlés: Algoritmus, amely a példákat tartalmazó (ellentmondás-mentes) mátrixot döntési fává alakítja át és a generált rendszert futtatja 2.51 ábra Induktív rendszerek felépítése 2.51 Szabályalapú rendszerek 2.521 Szabályalapú adatvezérelt következtetés Az adatvezérelt következtetést szokás előre haladó következtetésnek, vagy előreláncolásnak ( forward c haining) i s nev ezni. A s zabály alapú adatvezérelt következtetésnél a szakértői rendszer a felhasználótól először a

kiindulási adatokat kéri és az adat okat a m unkamemóriába hel yezi. További új információ meghatározásához a szabályokat vizsgálja meg. H a eg y s zabály f eltételrésze a munkamemória adatai alapján teljesül, azaz aktivizálódik a szabály, a konklúzió által szolgáltatott adat új t ényként a m unkamemóriába k erül. A z új t ény bev onásával azután további szabályok kerülnek alkalmazásra mindaddig ,amíg egy adott cél mint tény ismertté nem válik, vagy addig amíg a rendszer talál alkalmazható szabályt. A k övetkeztetésI al goritmust eg y s zabályinterpreter v alósítja meg, amire többféle módszer létezik. Az al kalmazható s zabályok k eresését m ás-más m ódszerrel, eg yre gazdaságosabban valósítják meg az algoritmusok. Kiindulási adatok a munkamemóriában Célállapot? Az első szabály vizsgálata Következő szabály vizsgálata A Konkluzió a premissza illeszthető munkamemóriában a

munkamemóriában? Van még vizsgálható szabály? Vége 2.52 ábra Adatvezérelt szabályalapú következtetés A következtetés illusztrálására nézzük az al ábbi 5 s zabályból ál ló pél dát [ 3], amelynek minden változója, az egyszerűség kedvéért legyen logikai változó: Sz1. IF A THEN teljesül = igaz ELSE teljesül = hamis Sz2. IF B and C THEN A = igaz Sz3. IF D or E THEN B = igaz Sz4. IF F or G THEN C = igaz Sz5. IF H THEN g = igaz A szabályinterpreter a következtetés indulásánál kéri a kiindulási adatokat és ezeket a m unkamemóriában hel yezi el . A s zabályok v izsgálata c iklikusan t örténik, ahol minden ciklus egy alkalmazható szabály meghatározásával végződik. Az újabb ciklus minden szabályt ismételten ellenőriz mindaddig, amíg egy célállapot nem kerül a munkamemóriába. Kezdőérték beolvasása 3. Ciklus 1. Ciklus Sz1, Sz2 Premissza ismét ismeretlen Sz1. Premissza: A Sz3. Ismét aktivizálódik Sz2.

Premissza1: B Sz4. Premissza1: F Sz3. Premissza1: D Sz4. Premissza2: G Sz3. Premissza2: E Sz4. Aktivizálódik C Sz3. Aktivizálódik B konklúzió 4. Ciklus 2. Ciklus Sz1 Premissza: Sz1. Premissza: A A Sz2. Premissza1: B Sz2. Premissza1: B Sz2. Premissza2: C Sz2. Premissza2: C Sz2. Aktivizálódik A Sz3. Ismét aktivizálódik Sz4. Premissza1: F 5. ciklus Sz5. Premissza2: H Sz1 Premissza: Sz5. Aktivizálódik G konklúzió Sz1. Aktivizálódik Teljesül A Amikor a m unkamemóriában a c él, a t eljesül v áltozó ér téke ismertté válik, akkor fejeződik be a következtetési sorozat. A pél dában eg y ol yan s zabálysorozatot m utattunk be, ahol a k onklúziók egymástól függetlenül, ak szabályrendszer, ár eg yszerre i amelynél st eljesülhetnek. A dódhat az onban olyan több ol yan s zabály i lleszkedhet eg yszerre a munkamemória adataival, am elyek eg ymást k izáró k onklúziót t artalmaznak és í gy konfliktusok

alakulhatnak ki. Ezek megszüntetésére az adatvezérelt következtetésnél a szabálykiválasztást pontosítani kell: ha egyidejűleg több szabály is aktivizálódhat, akkor különböző stratégiák szerint csak egyet választunk ki közülük [3]: • Az első alkalmazható szabályt vagy • A legnagyobb prioritású szabályt vagy • A legtöbb kifejezést tartalmazó szabályt választjuk 2.522 Szabályalapú célvezérelt következtetés A célvezérelt k övetkeztetésnél vagy m ásképpen visszafelé hal adó k övetkeztetésnél vagy visszafelé láncolásnál az elérendő célból indul ki a rendszer. Ha a cél még nem ismert, olyan szabályt, illetve szabályokat keres a r endszer, amelyek konklúziójában a cél szerepel. Ezek premisszáit vizsgálva ellenőrzi, hogy szerepelnek e már a munkamemóriában a m eghatározáshoz s zükséges par améterek. H a nem , ezek lesznek az új közbülső célok és olyan szabályokat keres, melyek konklúziójában

e közbülső célok szerepelnek. A folyamat mindaddig rekurzívan ismétlődik, amíg egy közbülső cél egyetlen szabályának sem lesz a konklúziója, vagy levezethető valamely szabályból. Ha nem vezethető le, az ismeretlen adatot a felhasználótól kérdezi meg. A kapott értéket azután felhasználja a közbülső célok, vagy az eredeti cél meghatározásához. A célvezérelt következtés algoritmusát s zintén eg y i nterpreter valósítja m eg. E nnek felépítése az onban j óval bony olultabb m int az adat vezérelt k övetkeztetésnél. Az algoritmus k ét eg ymást r ekurzívan hívó el járást al kalmaz: a MEGHATÁROZ eljárás paraméterként kapja meg a cél vagy közbülső célt és a SZABÁLYVIZSGÁLAT segítségével minden ol yan s zabályt m egvizsgál, am ely a c élt k onkluzióként tartalmazza. Mind a c él, m ind az adat vezérelt es etben, a v égrehajtás s orán m aga a r endszer állítja elő azt a műveletsorozatot vagy utat, amely a

szóban forgó kezdő- és célállapotot ös szeköti. A mennyiben i lyen ut at nem t ud g enerálni, v agyis nem talál megoldást, ezt jeleznie kell. CÉLMEGHATÁROZÁS Cél szerepel a Cél megkérdezése konkluzióban? Szabálylista = azon szabályok listája, amelyek konkluziója a cél szabálylista nem üres és SZABÁLYVIZSGÁLAT a cél nem vezethető le a vizsgált szabály törlése a listából SZABÁLYVIZSGÁLAT az első premissza vizsgálata Van benne ismeretlen Következő premissza vizsgálata paraméter? CÉLMEGHATÁROZÁS A premissza igaz? Van még premissza? A szabály nem teljesül A célvezérelt következtetés működését vizsgáljuk A szabály teljesül meg az adatvezérelt következtetésnél használt példa segítségével: 1. Lépés cél ismeretlen 2. Lépés célszabály keresés: Sz2 5. Lépés Sz1 konklúziója a cél 3. Lépés 4. Lépés Sz1 pr emissza v izsgálata: A Sz2 pr emissza v izsgálata: B ismeretlen 6.

Lépés közbülső cél B. ismeretlen Újabb célszabály keresés közbülső cél A. Újabb Sz3 célszabály keresés 7. Lépés Sz3 premissza 1 vizsgálata: D ismeretlen 8. Lépés 14. lépés közbülső cél D. Újabb célszabály keresés célszabály keresés Sz4 Nincs ilyen szabály 9. Lépés 15. lépés D értékét meg kell kérdezni. Kérdés: mennyi D értéke? 10. Lépés 12. lépés F ismeretlen 16. lépés közbülső cél F. Újabb célszabály keresés Sz3 premissza vizsgálata: Nincs ilyen 17. lépés F értékét meg kell kérdezni. közbülső cél E. Újabb Kérdés: mennyi D értéke? célszabály keresés Válasz: igaz Nincs ilyen szabály Sz4 aktivizálódik E értékét meg kell kérdezni 18. lépés Sz2 aktivizálódik konklúzió Újabb célszabály keresés 19. lépés Sz1 aktivizálódik konklúzió Sz3 aktivizálódik konklúzió 13. lépés Sz4 premissza vizsgálat: Válasz: hamis E ismeretlen 11. lépés

közbülső cél C. Újabb Sz2 premissza v izsgálat: Teljesül = igaz 20. lépés A cél értéke ismertté vált. C ismeretlen Az adatvezérelt rendszer főbb jellemzői: • mindig új megoldást állít össze • az ismeretmérnöknek beleszólása van a rendszer vezérlésébe A célvezérelt rendszer főbb jellemzői. • a rendszer választ előre megadott megoldások közül • a következtető gép szigorúan a beépített stratégia szerint működik, a vezérlést az ismeretmérnök csak különböző programozási trükkökkel képes befolyásolni Célvezérelt rendszerek Ismeretmérnök Adatvezérelt rendszerek Heurisztikákat ír le az eleve Heurisztikákat és vezérlési megszabott vezérlés keretei előírásokat egyaránt leír. között Következtető gép A megadott célra illeszthető A szabályokat szabadon keresi, szabályok között előre egyet kiválaszt és azt meghatározott stratégia szerint alkalmazza. keres és a kiválasztott

szabályt Egy végrehajtási ciklusban alkalmazza minden szabálynak van esélye Egy ciklusban az első illeszkedő az aktivításra szabályt kezdi el alkalmazni. Ha ez meghiúsul akkor keres másik illeszkedő szabályt 2.53 Hibrid rendszerek A hi brid r endszer nev ét onnan k apta, hog y az egyidejűleg alkalmaz. különféle technikákat ismeretek reprezentálására Ennek megfelelően felépítésük bonyolultabb és a „tiszta” rendszerektől való eltéréseik az ismeretábrázolás és a következtetési rendszerhez kapcsolódnak. A hibrid rendszerek egy jelentős része grafikus eszközöket nyújt az obj ektumok és s zabályok l étrehozásához, beillesztésükhöz a hierarchiába és a létrejött struktúra szemléltetésére. A h ibrid rendszerek mind keret, mind szabály alapú ismeretábrázolási lehetőséggel rendelkeznek és lehetőséget adnak ezek külön, külön illetve együttes alkalmazására. A keretek és a szabályok

kombinálása kétféleképpen történhet: • szabályok rendelhetők a keretek valamely tulajdonságához és ha az érték ismeretlen az értéket célvezérelt következtetéssel kell meghatározni • a szabályok a keretek tulajdonságaira, metódusaira hivatkoznak Az ismeretbázis összetettségének megfelelően a következtetés vezérlési stratégiája lehet keret vagy szabályalapú és mindkét esetben cél vagy adatvezérelt. A keret és szabály kapcsolat az t a f ormalizmust j elenti, ahog yan eg y k eret tulajdonságaira a szabályokban hivatkozhatunk illetve azt a lehetőséget, ahogyan egy szabály segítségével létrehozhatunk vagy törölhetünk egy keretet. A mintaillesztő szabályok lényege az, hogy segítségükkel ugyanazt az utasításcsoportot egyszerre t öbb k ereten i s v égre l ehet haj tani. M ivel a s zabályt rendszerint c sak bi zonyos eg yedekre ak arjuk al kalmazni ezért k i kell szűrni azokat. Ez az egyedek tulajdonságainak

segítségével történik. Nagyobb méretű problémák kezelése egyszerűbb, ha azokat modulokra bontjuk. Ezt a modularizálást a szakértői rendszerek egy jelentős része támogatja. 2.54 Szimbólum-manipulációs rendszerek A LI SP ny elvet az 1950 -es év ek v égén J ohn M cCarthy irányításával az MIT munkatársai dolgozták ki. Céljuk az „Advice taker” nevű következtetésekre képes program kidolgozása mellett, egy olyan program elkészítése volt, amely matematikai kifejezéseket f ormálisan tud differenciálni. A nyelv elemi építőkövei az atomok, amelyek a f izika at omjaihoz has onlóan „ oszthatatlanok” bár ez eknek i s van „szerkezetük”. A LISP nyelv kétféle atomot ismer, szimbolikus és numerikus atomot A szimbolikus atomok betűkből és számokból álló karaktersorozatak, amelyeknek első karaktere mindég betű. A listák atomokból és elválasztó jelekből (nyitó és záró zárójel, szóköz és sorvégjel) épülnek fel.

A listák kezdőzárójellel kezdődnek és záró zárójellel z árulnak. A l istának nem csak atom, hanem eg y m ásik l ista i s l ehet az eleme: ((ALMA (BARACK MEGGY) (((DINNYE) EPER))) A lista első eleme kitüntetett szerepet játszik, ezért külön nevet is kapott, ez lett a lista feje. A lista fejét elvéve a m egmaradó rész a l ista farka A lista feje lehet atom vagy lista, míg a l ista f arka m indég l ista ( bizonyos es etekben az ún. ür es l ista) A z atomokat és l istákat eg yüttesen s zimbolikus k ifejezéseknek nevezzük. Egy LISP program szimbolikus kifejezések egymásutánja. A program végrehajtása azt jelenti, hogy ez eket a k ifejezéseket eg y s zámítógép r endre k iértékeli. A kiértékelés úgy zajlik le, hogy a programozó egymás ut án beí rja a LI SP pr ogramot al kotó szimbolikus kifejezéseket, amelyeket a számítógép tárjában lévő értelmező program rendre feldolgoz. Az értelmező program sorra beolvassa a programozó

által írt szimbolikus kifejezéseket és ez eket k iértékeli, az az m eghatározza a k ifejezések ér tékét, am ely egy új szimbolikus kifejezés. Hogyan határozza meg egy szimbolikus kifejezés értékét az értelmező program? A szimbolikus kifejezés atom vagy lista lehet. Először vizsgáljuk meg hogy határozza meg egy atom értékét. A z atomok között különleges atomok a s zámok, a T és NIL szimbólumok. Az 5 atom értéke 5, -2 atom értéke -2, a NIL atom értéke pedig NIL A különleges at omok ér tékét a pr ogramozó nem v áltoztathatja m eg, ez ek a rendszer konstansai. Azoknak a szimbolikus at omoknak, am elyek nem k ülönleges s zimbólumok, a programozó adhat értéket, az az ér tékként hoz zájuk r endelhet eg y s zimbolikus kifejezést. A T és N IL k ülönleges szimbólumoktól különböző szimbolikus atomat változóknak is nevezhetjük, mivel a hoz zájuk r endelt ér ték a pr ogram v égrehajtása során többször is változhat.

Ha egy szimbolikus kifejezést azért írtunk fel, hogy az értelmező azt kiértékelje, akkor a kifejezést formának is nevezzük. Ha beírt forma lista, akkor az értelmező program ennek első elemét, azaz a lista fejét egy függvény nevének tekinti, a lista további elemeit pedig, ha v annak ilyenek a f üggvény argumentumainak. A függvény név c sak s zimbólum l ehet, az ar gumentumok pedi g s zimbolikus k ifejezések. A kiértékelés során az értelmező program a függvényt az argumentumok értékére alkalmazza: először tehát kiértékeli az argumentumként megadott kifejezéseket, majd az argumentumok értékére alkalmazza a f üggvényt. A LISP nyelvben beépített függvénynek nev ezzük az okat a f üggvényeket, am elyek a LISP rendszerhez tartoznak és ezeket minden további nélkül használhatjuk. A l egfontosabb l istamanipulációs f üggvények a C AR, C DR és a C ONS. A C AR függvény a l ista f ejét , a C DR f üggvény pedig a l ista f

arkát adja. A CAR és a CDR függvények ismételt alkalmazásával a listákból tetszőleges részeket választhatunk ki. Például a CADR a lista második elemét, a C ADDR a l ista harmadik elemét adja. A CONS függvény segítségével listákat ál líthatunk ös sze. E nnek a f üggvénynek k ét argumentuma van. A CONS függvény értéke az a l ista, amely úgy jön létre, hogy a függvény első argumentumát mint első listaelemet a második argumentumként megadott l ista el ejére i llesztjük. A LI ST f üggvény tetszőleges számú szimbolikus kifejezésekből hoz létre új listát, amelynek elemei az argumentumok értékei. Az ATOM függvény argumentuma tetszőleges szimbolikus kifejezés lehet: a függvény értéke pedig T ha az argumentum értéke atom, minden más esetben NIL. Egy f eltételes k ifejezést a C OND f üggvény s egítségével írhatunk fel. A feltételes kifejezés ér tékét az dönt i el , hog y a t öbb f eltétel k özül melyik

teljesül. A COND függvény tetszőleges számú argumentumú. Mindegyik argumentuma egy kételemű lista, ahol az első listaelem egy feltétel a második listaelem pedig egy tevékenység amelyet a feltétel teljesülése esetén végre kell hajtani. Számtalan alkalmazási lehetősége van az általános listabejáró függvényeknek az ún. MAP függvényeknek Jellegzetességük, hogy rekurzív módon bejárnak egy listát (amely első argumentumuk) és minden vizsgált listarészletre alkalmaznak egy függvényt ( második ar gumentum). E zek k özül a l egfontosabbak a MAPCAR és a MAPLIST. A MAPCAR lista-argumentumának m inden elemére alkalmazza m ásodik argumentumát a függvény argumentumot. Értéke a függvényértékek listája Például: (MAPCAR ‘((A) (B A)(C B A)(D C B A))(FUNCTION CAR)) eredménye (A B C D) A M APLIST nem a l ista el emeire, hanem a l istára, a lista farkára, majd a farok farkára, és így tovább alkalmazza függvényargumentumát.

Például: (MAPLIST ‘(A B C D) (FUNCTION (LAMBDA (FAROK)(LIST (CAR FAROK)(CDR FAROK)))) ((A (B C D)) (B (C D)) (C (D)) (D NIL) Természetesen a programozó maga is definiálhat függvényeket. Például a faktoriális rekurzív definiciója a következő: (DEF FAKTORIÁLIS (N) (COND ((ZEROP N) 1) (T (TIMES N (FAKTORIÁLIS (SUB1 N)))))) Abban az esetben ha ha az argumentum értéke 0 akkor egyszerűen megkapjuk a függvény értékét az 1-t. Ha N értéke nem nulla akkor N faktoriálisának kiszámítását visszavezetjük N-1 faktoriálisának kiszámítására. A LISP s egítségével m atematikai k ifejezéseket s zimbolikusan i s k ezelhetünk. A z alábbiakban ismertetendő program a felírt matematikai kifejezés differenciálhányadosát hat ározza m eg. A m atematikai k ifejezéseket a LI SP-ben szokás formában adjuk meg: x4+x2y2+y4 például (PLUS (EXPT X 4) (TIMES (EXPT X 2) (EXPT Y 2)) (EXPT Y 4)) Ha a kifejezések differenciálásának i smert s zabályaiból i

ndulunk k i, és zrevehetjük, hogy az összeg, szorzat differenciálásának szabályai rekurzív összefüggések; pl. egy összeg differenciálhányadosát úg yk apjuk m eg, hog yat agok differenciálhányadosának összegét képezzük. A DERIV függvény megvizsgálja a di fferenciálandó k ifejezést, és annak t ípusától függően alkalmazza a megfelelő segédfüggvényt, amely az adott típusú kifejezés differenciálását végzi el. A DERIV függvénynek tehát a kifejezés típusától függően más-más s egédfüggvényt k ell al kalmaznia. A z es eteket eg y S ELECTQ kifejezéssel választjuk szét. KIF a di fferenciálandó k ifejezés, X pedi g a s zimbolikus v áltozó, amely szerint differenciálunk: (DEF DERIV (KIF X) (COND ((ATOM KIF) ; Ha a kifejezés atom (COND ((EQ KIF X) 1) (T 0))) (T (SELECTQ (CAR KIF) ;X ; konstans ; ha nem atom (PLUS (DERPLUS KIF X)) ; összeg (DIFFERENCE (DERDIFF KIF X)) ; különbség (TIMES (DERTIMES KIF X)) ;

szorzat (QUOTIENT (DERQUOTIENT KIF X)) ; hányados (MINUS (DERMINUS KIF X)) ; negatív (EXPT (DEREXPT KIF X)) ; hatvány (PROGN (PRIN1 KIF) ; egyébként (PRIN1 „KIFEJEZÉS NEM MEGFELELŐ ALAKÚ”) (TERPRI) A S ELECTQ ut olsó ar gumentumára az ért v an s zükség, hog y ha a D ERIV argumentuma ol yan k ifejezés, am elyre nem adt unk m eg deriválási szabályt, akkor ezt figyelmeztető üzenet kiírásával jelzi és a NIL értéket adja vissza. A segédfüggvények: (DEF DERPLUS (KIF X) (CONS ‘PLUS (MAPCAR (CDR KIF)(FUNCTION (LAMBDA (KIF)(DERIV KIF X)))))) (DEF DERTIMES (KIF X) (COND ((NULL (CDDDR KIF))(DERTIMES2 KIF X)) (T (LIST ‘PLUS (CONS ‘TIMES (CONS (CADR KIF) (DERTIMES (CONS ‘TIMES (CDDR KIF)) X))) (DEF DERTIMES2 (KIF X) (LIST ‘PLUS (LIST ‘TIMES (CADR KIF) (DERIV (CADDR KIF) X)) (LIST ‘TIMES (CADDR KIF) (DERIV (CADR KIF)))) (DEF DERMINUS (KIF X)(LIST ‘MINUS (DERIV (CADR KIF) X))) (DEF DERQUOTIENT (KIF X) (LIST ‘QUOTIENT (LIST ‘DIFFERENCE

(LIST ‘TIMES (DERIV (CADR KIF) X) (CADDR KIF)) (LIST ‘TIMES (CADR KIF) (DERIV (CADDR KIF)X))) (LIST ‘EXPT (CADDR KIF) 2))) (DEF DEREXPT (KIF X) (LIST ‘TIMES (CADDR KIF) (LIST ‘EXPT (CADR KIF)(SUB1 (CADDR KIF))) (DERIV (CADR KIF)))) A P ROLOG [ 10] a pr edikátum kalkuluson al apuló pr oblémamegoldó ny elv. Alapegysége a term. A legegyszerűbb termek a konstansok és a változók Az előbbieket kisbetűvel, az utóbbiakat nagybetűvel jelöljük. A listák a LISP listáihoz hasonlóan v annak def iniálva, c sak a z árójelek s zögletesek és az egyes elemeket vesszővel választjuk el egymástól. A program állítások sorozata, amelyek mindegyike vagy egy fejből vagy egy törzsből, vagy mindkettőből áll. Az alábbi állítás mindkettőt tartalmazza: P:-Q,R,S Ahol P a f ej, Q ,R,S pedi g a t örzs c élja, m íg a „ :-„ j el el választásukra has ználatos. Jelentése: ha mind Q, R és S igaz, akkor P is igaz vagy másképpen fogalmazva a P cél

megvalósításához, meg kell Q, R, S-t is valósítani. Ha csak a fej rész létezi annak jelentése, hogy P igaz, vagyis megvalósított. Ha azonban csak a t örzs létezik, akkor jelentése, hogy hozd létre őket. A fej mindig csak egy termből áll és a vesszők a logikai és kapcsolatot jelölik. Vegyük példaként a következő kifejezést: ahhoz, hogy X Znagyapja legyen, teljesülnie kell, hogy Y, az apja vagy az anyja legyen X-nek, míg Y apja, Z kell, hogy legyen. Ez a PROLG nyelvén az alábbi formában írható fel: nagyapa(X,Z):-anya(X,Y),apa(Y,Z). nagyapa(X,Z):-papa(X,Y),apa(Y,Z). Egy új szülő(X,Y) függvény bevezetésével, ezt a következő módon is kifejezhetjük: nagyapa(X,Z):-szülő(X,Y),apa(Y,Z) szülő(X,Y):- anya(X,Y). szülő(X,Y):- apa(Y,Z). Nézzük meg egy példán a PROLOG működését: leszármazott(X,Y):-gyermek(X,Y). leszármazott(X,Z):- -gyermek(X,Y),leszármazott(Y,Z). Tegyük fel, hogy a bemenő adatok a következőek: gyermek(alan,brian).

gyermek(alan,lucy). gyermek(lucy,clive). gyermek(lucy,jane). A bemenő állítások csak a fejet tartalmazzák és tegyük fel hogy a kérdés a következő: ?-leszármazott(alan,clive) Erre a k érdésre a P ROLOG eg y ol yan ál lítás k eres, am elynek f eje i lleszkedik a kérdéshez és a keresés felülről lefelé hajtódik végre. A példa első állítása mindjárt illeszkedik, m ivel az X = alan és az Y = clive hel yettesítéseket v éve. H a eg y f ej illesztése megtörtént, a következő lépésben az állítások t örzsének i llesztését kíséreljük m eg. M ivel X és Y m eghatározott, a t örzs g yermek(alan,clive) lesz Ez azonban eg yik t örzzsel s em i lleszkedik. A PROLOG ilyen kor automatikusan visszalép, törli a közvetlenül megelőző sikeres illesztést és folytatja a keresést. Ekkor a második állítást találja meg. E bben az X = alan, Z = clive az i llesztés, és a t örzs gyermek(alan,Y) l esz. E z az i llesztés az onban s ikertelen,

ez ért a rendszer ismét visszalép, törli a közvetlenül megelőző sikertelen illesztést és folytatja a keresést most az első termre a gyermek(alan,lucy) illesztést próbálja meg. Ezáltal a második term l eszármazott(lucy,clive)-vé válik, ami illeszkedik az első állítás fejéhez, így az első illesztés törzse pedig gyermek(lucy,clive) lesz. Ez viszont illeszkedik a bemenet egyik állításához, azaz igaz lesz. A keresés tehát mélységben először stratégia szerint történik. Amikor egy célállítás és egy állítás között illeszkedés van a rezolúció elvénél ismert módszerrel változóegyesítést hajtunk végre. Ha most a ? -leszármazott(alan,X) kérdést tesszük fel a rendszer az előhez hasonló módon fog viselkedni. Az első illeszkedés mindjárt az első állításnál meg lesz és ennek törzse gyermek(alan,brian), így X = brian l esz és a r endszer ez zel az eredménnyel tér vissza. A keresés így sikeresnek bizonyult A

fentiekből is látható, hogy a PROLOG az illesztések során betartja a bemenő állítások sorrendjét, a keresést automatikus v isszalépéssel haj tja v égre, m elynek blokkolására is lehetőséget ad. A LISP és a PROLOG összehasonlítását a következő táblázat foglalja össze [15]: LISP Prolog Az USA-ban jött létre az 50-es években Európában jött létre a 70-es években A LISt Processing rövidítése A PROgramming in Logic rövidítése Funkcionális (determinisztikus) szemléletű Reláció (nem-determinisztikus) szemléletű Elméleti alapja: A Church féle λ-kalkulus Elméleti alapja: a matematikai logika Alapelemek: függvények (-kalkulus formalizmusa, Alapelemek: predikátumok (logikai formalizmus, S-kifejezések) objektumok közötti relációk) Procedurális: előírt sorrendű végrehajtás Nem-algoritmikus, hanem leíró, deklaratív Szimbólum-feldolgozás Szimbólum-feldolgozás A végrehajtási mechanizmust a programozónak

Beépített végrehajtási mechanizmus, célvezérelt, kell megépítenie visszalépéses kereséssel Program- és adatstruktúrák azonosak Program- és adatstruktúrák azonosak Az USA-ban számtalan mesterséges intelligencia Európában és Japánban gyakorlati rendszerek kutatási eredmény született LISP-ben, amely a építésére használják. Az USA-ban is kezd mesterséges intelligencia assemly nyelvének elterjedni. Formális leíró nyelvként egyre tekinthető. gyakrabban alkalmazzák 2.55 További technikák Modell-alapú következtetés Am odell-alapú k övetkeztetés l ényege a s összehasonlítva tűnik ki. Míg zabály-alapú k övetkeztetéssel a szabályalapú következtetésnél a szabályok egy szakterületet írnak le, és egy probléma megoldására tűzhető ki feladat. A modell szintén egy szakterületet ír le, de több féle feladat fogalmazható meg segítségével. Míg a szabály-alapú rendszerek felszínes ismeretek

felhasználásával működik, addig a modell alapú következtetés a mélyszintű ismeretek kezelésére alkalmas. Ez a fizikai rendszereket - akár mesterséges, akár természetes - saját szerkezetükben és funkcionalitásukban r agadja m eg. E gy f izikai m odell matematikai eszközökkel szimulálja a működést és lehetőséget ad arra, hogy megfelelő paraméterek beavatkozásával beavatkozzunk a rendszerbe. A m odell-alapú következtetés alkalmazásának előnye, hogy kiiktatható a tudásszerzés és nem k ell az összes hiba t ovaterjedésének hat ását ex plicit m ódon megadni. A hátrányok: nehéz a heurisztikus tudást, és a bizonytalanságot beépíteni A legtöbb rendszer feltételezi, hogy a hibát egyetlen ok okozza. Eset-alapú következtetés Gondolkodásunkra jellemző, hogy feladatok megoldásából tanulunk, az így szerzett tapasztalatokra em lékezünk. A z i gazi t apasztalat nehez en r agadható m eg s tatikus formában, mert azt

valójában állandóan változásban lévő epizodikus ismeretek szövevényes k apcsolata al kotja. A z emberi gondolkodásról al kotott ef féle elképzeléseket veszi alapul az ún. eset-alapú következtetés, amely új problémákat a korábbi feladatmegoldások v isszakeresésével és az er edmények adapt álásával próbál megoldani. Az eset-alapú következtetés sémája rendkívül egyszerű: tároljuk az eseteket - azaz a korábbi f eladatok m egoldásaiból s zármaztatott epi zódokat. E záltal eg y esetbázist hozunk létre. A legegyszerűbb formában az esetek csak konkrét feladatokat és azok megoldásait tartalmazzák, de tárolhatók a megoldás előállításának lépései is, illetve a k onkrét es etek ál talánosított v áltozatai. E gy újabb megoldandó feladattal szembesülve keressük vissza azokat az eseteket, amelyekben a problémafelvetés a lehető legjobban hasonlít az aktuális problémához. Válasszuk ki a leginkább hasonló esetet és

annak megoldását használjuk f el. H a az í gy k apott m egoldás nem kielégítő, akkor próbáljuk meg újra felhasználni más hasonló esetek megoldásait. Ha így sem kapunk kielégítő megoldást, akkor egy korábbi feladat megoldását adaptáljuk az új körülményeknek megfelelően. Az ilyen módon kapott új megoldást természetesen a hozzá tartozó feladatkitűzéssel együtt - tároljuk az esetbázisban A következtetés kritikus pontjaiban komoly szerepet kaphat az ember is. Az eset-alapú következtetés folyamatát mutatja be a 2.54 ábra feladat leírás keresés választás felhasználó módosítás általános esetbázis ismeretbázis tárolás megoldás 2. 54 ábra Az eset-alapú következtetés folyamata Esetek leírása többnyire attribútum-érték párok halmazából áll, ahol az attribútumok típusa szerint az ér ték l ehet ak ár s zabad s zöveg, s zám, s zimbólum, v agy l ogikai érték. Egyszerű rekordokon túl az esetek akár a

keretek-nél m egismert obj ektum hierarchiába is szervezhetők. A hatékony visszakeresést az esetek kiterjedt indexelése teszi lehetővé. Az indexek megadása általában együtt jár az esetek definiálásával, de v an m ód az i ndexek aut omatikus megtanulására is: indukciós algoritmusokkal meghatározhatók azok a jellemzők, amelyek értékei mentén az esetek leginkább szétválaszthatók. Ekkor az esetekhez való hozzáférés döntési fán keresztül is lehetséges. A visszakeresés feladata adott problémához leginkább hasonló esetek kikeresése az esetbázisból. A l eggyakrabban al kalmazott m ódszer a l egközelebbi s zomszéd módszere. Ekkor két eset hasonlóságát a köztük lévő távolság határozza meg, s egy adott esethez leginkább hasonló esetnek a hozzá legközelebb eső számít. A távolságot legegyszerűbben az egyes tulajdonságok ér tékei k özt adódó ( tényleges vagy becsült) különbségek súlyozott összegével lehet

számítani. Az esetekhez való hozzáférést indukció útján előállított döntési fa is biztosíthatja. Végül van olyan visszakeresési módszer is, amelyik a részben specifikált, adatbáziskezelő rendszerekben szokásos lekérdezéseknek eleget tevő esetek halmazát adja eredményül. Ezt a visszakeresést a legközelebbi szomszéd módszer előtt jó alkalmazni, mert jelentősen korlátozza azon esetek halmazát, amelyekre távolságot kell számítani. A távolságfogalom m egkönnyíti a v álasztást is, ám a nag yon hasonló - akár közeli, akár t ávoli - értékekkel rendelkező esetek közül való választást szerencsésebb a következtető rendszer felhasználójára bízni. Az eset-alapú k övetkeztetés legnehezebb lépése a módosítás, az az a r égi m egoldások adapt álása. H a ez t a lépést akárcsak részben automatizálni akarjuk, szükség van a hag yományos logikai következtetési appar átus al kalmazására i s. E gy

új es et t árolásakor annak az esetbázisba v aló i ntegrálását úg y k ell m egoldani, hog y j elentésbeli g azdagsága ne vesszen el, ám egyben könnyen visszakereshető is legyen. Ez az eset-alapú következtetés tanuló komponense. Az eset-alapú következtetések alkalmazásának sok előnyei: • az esetek könyvtára jóval objektívebb mint a szakértői értelmezésre alapozott szabályrendszerek • az ismeretszerzés igen egyszerű • az ismeretszerzés nem egyetlen szakértőre, hanem egy szervezet gyakorlatára épít 2.56 Ellenőrző kérdések 1, Hogyan épülnek fel és hogyan működnek az induktív rendszerek? 2, Mutassa be egy egyszerű példán az adatorientált következtető rendszer működését! 3, Mutassa be egy egyszerű példán a célorientált következtető rendszer működését! 4, Hasonlítsa össze az adat és a célorientált következtetést 5, Mi a hi brid r endszer és ez en bel ül, hog yan k apcsolódnak eg ymáshoz a

szabályok és a keretek? 6, Melyik a két legelterjedtebben használt szimbólum-manipulációs nyelv és melyek ezek legfőbb jellemzői? 7, Készítsen LISP nyelven példaprogramot a F ibonacci f üggvény értékének kiszámítására! 8, Mutassa be egy példa kapcsán a PROLOG következtető rendszerének működését 9, Ismertesse a modell-alapú következtetés lényegét! 10, Vázolja fel az eset-alapú rendszer működését, előnyeit és hátrányait! 2.6 Ismeretalapú rendszerek fejlesztése, ismeretszerzés 2.61 Fejlesztőeszközök A fejlesztő eszközöknek a rendszerfejlesztés meggyorsításának gyakorlati jelentősége mellett fontos szerepe van abban, hogy az ismeretalapú rendszerek új általános érvényű elméleti eredményei a fejlesztés s orán ér vényre j uttatják. A fejlesztő eszközök alapvetően öt csoportra oszthatók [13]: • a mesterséges intelligencia programozási nyelvei • környezeti eszközök • általános

keretrendszerek • problémafüggő keretrendszerek és • szakterületfüggő keretrendszerek A m esterséges i ntelligencia programozási nyelvei alkotják a l egrégebbi fejlesztőeszköz csoportot és ezek a legrugalmasabbak, a legszélesebb körben alkalmazhatóak, ug yanakkor a f ejlesztés v elük a legmunkaigényesebb. Az ismeretalapú rendszerek fejlesztésére a legalkalmasabb nyelvek: • a LISP és a P ROLOG am elyek s zabály-alapú r endszerek f ejlesztését támogatják • az objektum-orientált fejlesztés nyelvek mint például a C++ és Smalltalk A környezeti eszközök olyan software csomagok, amelyek különböző segédprogramok révén támogatják a fejlesztést vagy különböző képességekkel ruházzák fel a rendszert. A szakértői rendszerek nem válhattak tömegárúvá, mivel speciális ismeretek felhasználásával eg y-egy s ajátos f eladatkör el látására k észültek. A mesterséges intelligencia eddigi legnagyobb üzleti

sikere azon alapult, hogy ezekből a rendszerekből kivonták a speciális szakismereteket és az így megmaradt üres vázat, keretet kínált a f elhasználóknak. Ezek a k eretrendszerek azáltal, hogy egy általános célú eszközkészletet és fejlesztői környezetet biztosítanak, lehetővé teszik, hogy a fejlesztők ne az eszközkészítésre, hanem az alkalmazásra koncentráljanak. Az általános keretrendszerek tartalmazzák az ismeretalapú rendszerek mind az öt különálló eg ységét, nev ezetesen az ismeretbázist, a következtető gépet, a magyarázó modult, az ismeretszerző alrendszert és a felhasználói felületet. A korszerű keretrendszerek a következő szolgáltatásokat nyújtják: • integrált s zabály és k eret ( frame) al apú i smeretreprezentációt és következtetési m echanizmust, es etleg az es et-alapú r eprezentáció és következtetés eszközeit • integrált fejlesztő környezetet, amely támogatja az ismeretszerzést,

magyarázatok szolgáltatását és a rendszer karbantartást • grafikus felhasználói felületet • adatbázis interface-t a leggyakrabban használatos adatbázisokhoz • illesztést az elterjedt hardware platformokhoz és operációs rendszerekhez Ez utóbbi két szolgáltatás lehetővé teszi a más rendszerekkel való zökkenőmentes együttműködést, az összetett, esetleg más rendszerekbe is beágyazott ismeretalapú rendszerek fejlesztését. Tipikus példája egy szakértői keretrendszernek az IntelliCorp által forgalmazott Kappa és ennek P C-s v áltozata a K appa P C, am elyek U nix i lletve Windows környezetben működnek. A Kappa PC ún object browser ablakában lehetővé teszi az obj ektumok ( osztályok és eg yedek) g rafikus def inicióját i lletve a már létrehozott struktúra megjelenítését. Következtető gépe lehetővé teszi mind az cél-, mind az adatvezérelt következtetést, magyarázó alrendszere pedi g m egjeleníti a következtetés

s orán eg ymásután v égrehajtott s zabályokat az ok i lleszkedésének módját és a kapcsolódó tényeket, paramétereket. A Kappa PC rendszer kapcsolatot biztosít a járatos adat bázisokhoz, a dB ase-hez és a Lot us 1 -2-3-hoz. F elhasználói felület kialakítására a K appa P C hoz záférést bi ztosít a W indows g rafikus erőforrásaihoz. A rendszernek saját fejlesztői nyelve van Ezen az ún KAL nyelven írott programok és eljárások egy interpreter segítségével ellenőrizhetők. Az elkészült ismeretalapú rendszer azután egy futtatható C kód formájában is előállítható, amely utána a járatos compilerek (Borland vagy Microsoft) valamelyikével lefordítható. A m ásik i gen el terjedt és s ok s zolgáltatást nyújtó keretrendszer az ART*Enterprise szintén obj ektum-orientált al kalmazások f ejlesztésére s zolgál, t ámogatja a keret-, szabály és eset alapú reprezentációt és az ezeken történő következtetést. Kétirányú

kapcsolatot biztosít minden elterjedt adatbázis rendszerhez. Ez az adatintegráció azt jelenti, hogy a következtetések tárgyai a r endszerhez l azán c satolt adat bázisok és dokumentumok is l ehetnek. E set-alapú k övetkeztetéshez has ználatos k eresési mechanizmusa révén struktúrálatlan dok umentumokban i s k épes k eresni. A z ART*Enterprise-nak s aját ny elve v an de k épes C++ kódú pr ogramok és el járások integrálására és f uttatására. A r endszer eg yik i gen f ontos el eme a grafikus felhasználó felület fejlesztését támogatja: lehetővé teszi, hogy bármely objektum reprezentációjának megalkotásával egyidejűleg automatikusan létrejöjjenek azok az eljárások, amelyek az obj ektum pr ezentációját v annak hi vatva k ezelni. Leg újabb változat lehetővé teszi az Internetten keresztül elérhető rendszerek létrehozását is. Az eddi g l egsikeresebbnek bi zonyult es et-alapú következtető eszköz a CBR2 rendszer, am elyben az

es etek at tribútum-érték pár okkal adhat ók m eg. A z attribútumok a s zokásos, numerikus, nominális, logikai típusokon túl szabad szöveg jellegű értékeket is felvehetnek. A felhasználó megszabhatja, hogy az egyes attribútumokhoz milyen súlyokat rendeljünk a has onló es etek v isszakeresésénél. A visszakeresés a legközelebbi szomszéd módszerével t örténik és a r endszer csökkenő távolság szerint rendezve felkínálja a hasonló esetek egész sorát. Egy alternatíva kiválasztásával előkerülnek mindazon releváns kérdések, amelyekre az új probléma leírásában nem v olt v álasz. H a ez ekre a f elhasználó v álaszol, ak kor a rendszer újraindítja a keresést és es etleg m ás t árolt es etekhez k erül k özelebb. A CBR2 a m egtalált es etek adapt álására nem ad es zközt. A C BR2-nek ol yan rendszere van amely szükségtelenné teszi a programozást. A problémafüggő keretrendszerek egy adot t pr oblématípusra k idolgozott

k ulcsra kész r endszerek, am ely i gazodnak az adot t pr oblématípus adot tságaihoz, így nem igénylik valamely pr ogramozási ny elv i smeretét. A l eggyakoribb pr oblématípusok, amelyekre ilyen keretrendszereket kidolgoztak a di agnosztika, konstrukció, irányítás és a s zimuláció. A szakterületfüggő keretrendszerek valamilyen szűk szakterület alapismeretével r endelkeznek és a f ejlesztés c supán a s peciális ismeretek megadásra szorítkozik. A szakértői keretrendszerek piaca igen széles, ahol az olcsós, néhány száz dolláros terméktől kezdve a nagyigényű néhányszor tízezer dolláros termékig minden megtalálható. 2.62 A rendszerek fejlesztéséről általában Az ismeretalapú rendszerek fejlesztési módszereinek alapvetően három követelményt kell kielégíteni: • támogatni kell az ismeretgyűjtést • lehetővé kell tenni az implementálás független ismeretreprezentációt és • egymástól jól

elkülöníthető és dokumentálható lépésekre kell lebontani a fejlesztési folyamatot A Hayes-Roth [7] által kidolgozott modell a folyamatot 5 lépésre bontja fel: A probléma azonosítása igények A megoldás előállításához szükséges fogalmak meghatározása fogalmak Az ismeretek formális reprezentálási módjának és a hozzáillő következtető mechanizmusnak a megválasztása struktúrák Prototípus készítése szabályok Az ismeretek helyességének ellenőrzése 1. lépés A probléma azonosítása A fejlesztésben résztvevők körének és feladatainak tisztázása, a probléma lényeges jellemzőinek feltárása, a fejlesztéshez szükséges erőforrások és ismeretforrások számbavétele 2. lépés A megoldás előállításához szükséges fogalmak meghatározása Az ismeretreprezentációhoz s zükséges fogalmak és a köztük lévő kapcsolatok meghatározása 3. lépés Az ismeretek formális reprezentálási módjának és a hozzáillő

következtető mechanizmusnak a megválasztása 4. lépés P rototípus k észítése A z i smeretbázis t artalmának k ialakítása és a következtető mechanizmus megvalósítása 5. l épés Az i smeretek hel yességének, v alamint a k övetkeztetési f olyamatnak ellenőrzése A fejlesztés többszörösen visszacsatolt folyamat, ami magába foglalja akár a feladat újra definiálásának lehetőségét is. Nagy rendszerek építésekor nem r itka, hog y a fejlesztés során az ismeretreprezentáció formáin v áltoztatni k ell. Lény eges, hog y ismeretalapú rendszerek fejlesztésekor mindig egy feladat megoldását kell nyújtani, nem pedig egyszerűen csak egy új software technológiát. Ezért a fejlesztés nagyobb erőfeszítést igényel a szakértő, mint a mesterséges intelligencia ismereteket szolgáltató ismeretmérnök részéről, akinek a fejlesztés teljes szakaszában a teljes eddigi g yakorlatot f elül k ell v izsgálnia és nem ritkán módosítania, és

akire az elkészült rendszer ellenőrzése hárul. A H ayes-Roth m odell hát ránya, hog y nem t ámogatja ex plicite az i smeretszerzést, nem követeli meg az eg yes l épések dok umentálását és a 2. és 3 Lépés ben az analízis és az ismeretek reprezentálása összemosódik. A következő táblázatban bemutatott m odell a H ayes-Roth m odell eg y k onkretizált v áltozata, ahol az eg yes lépésekhez, végrehajtási módokat és segédeszközöket r endeltünk. E z a v áltozat feltételezi a j ól m egfogalmazott f eladatot ez ért nem tartalmazza a probléma azonosítás lépését. Lépés Leírása Végrehajtás módja Segédeszközök A feladat A probléma megoldásához Szakértőkkel készített Interjú technikák és karakterizálása illeszkedő interjúk (az ismeretmérnök jegyzőkönyvek ismeretreprezentáció és végzi) következtetési mechanizmus kiválasztása A keretrendszer A megfelelő keretrendszer Választás vagy új

Általános rendszer- kidolgozása kidolgozása vagy fejlesztés (az ismeret- fejlesztési eszközök beszerzése mérnök feladata) Az ismeretbázis Szakértői ismeretek Ismeretmérnök által létrehozása formalizálása támogatott szakértők Az ismeretbázis A rendszer finomítása és Szakértő végzi esetleg karbantartása illesztése az új illetve automatikus elemző Keretrendszer Eset gyűjtemény megváltozott viszonyokhoz technikák segítségével A szakértő rendszerek fejlesztése két eltérő hátterű szakember csoport szoros együttműködését igényli: a szakértőét és az ismeretmérnökét. A szakértő az adott területen jártas és képes megoldani az ott felmerülő problémákat, míg az ismeretmérnök bi ztosítja a megfelelő mesterséges intelligencia technikákat. A fejlesztési folyamat a szaktudás ismeretmérnöki megragadása. A fejlesztés során használt ismeretszerzési módszereket a következőképpen

osztályozhatjuk: Közvetlen módszerek: az ismeretanyag emberi segédlettel történő kibontása. Ez történhet di rekt m ódon, am ikor az i smeretmérnök a konkrét kérdések feltevésével igyekszik megszerezni a szakértőtől az ismereteket, vagy indirekt módon, amikor a szakértőt jól átgondolt feladatok elé állítjuk. Közvetett vagy automatikus módszerek az ismeretek esetekből, példákból számítógép segítségével történő kiemelése, általában a gépi tanulás eszközeinek felhasználásával. Az ismeretszerzés t ámogatására s okféle es zközt f ejlesztettek k i: ez ek j obbára általános protokollok, melyek segítségével a területre jellemző fogalmakra és szabályokra lehet rákérdezni. Kérdés azonban, hogy mindaz, ami a tapasztalatokból leszűrhető és szabályok formájában megfogalmazható, az valóban mindent megragad abból amit a szakértő területéről tud? Mivel a szakértő tudása korábbi feladatok m egoldása s orán f

olyamatosan s zerzett tapasztalatokból származik, az epizódikus ismeretek jelentősége legalább akkora, mint az azokból kivonható, szabályszerű, általánosított tudásé. Ezért nő az eset-alapú rendszerek jelentősége, melyek lehetőséget adnak az elsődleges tapasztalatok felhasználására. 2.63 Célvezérelt rendszerek építéséről A kisméretű szabályalapú rendszerek többsége célvezérelt, alkalmazásuk pedig alapvetően diagnosztizáló jellegű. A célvezérelt rendszerek építésének lépései a következők: • a probléma elemzése és definiálása • a probléma szerkezetének meghatározása • az induló szabálykészlet kidolgozása • a szabályok finomítása • a következtetés és a vezérlés testre-szabása A feladat elemzése egy ún. feladat elemzési munkalap kitöltésével történik, aminek segítségével a következő kérdésekre keresünk választ: mi a rendszer célja, felhasználói köre, szakértői köre,

felhasználásának módja és mik lehetnek a felhasználó jellemző igényei. Feltárjuk a feladat megoldásának j elenlegi m ódját és meghatározzuk, hog y r endelkezésre ál lnak-e tárgyköri szakértői ismeretek, tesztesetek és hogy milyen a feladat jellege. A probléma szerkezetének meghatározásánál a probléma belső szerkezetének megismerése a feladat, milyen objektumok és ezek milyen attributumai befolyásolják a döntéseket ezek, hogyan kapcsolódnak egymáshoz. Az induló szabálykészlet meghatározásánál k ét ut at k övethetünk: v agy r ögtön szabályokat fogalmazunk meg, vagy előbb táblázatba foglaljuk a szakértői példákat, majd a döntési tábla elkészülte után indukcióval manuálisan vagy valamilyen eszköz segítségével generáljuk a szabályokat. A generálás során a következő kézenfekvő egyszerűsítéseket lehet megtenni: az azonos példákból(sorokból) csak egyet tartunk meg és az azonos javaslattal rendelkező

sorokat logikai vagy művelettel kapcsoljuk össze. A szabálykészlet finomításánál fejlesztésénél arra törekszünk, hogy: • a rendszer minden esetben adjon javaslatot • kidolgozunk olyan szituációkat, amelyekhez több javaslat tartozik • bevezetjük a bizonytalanság kezelését • összevonjuk az ismétlődő szabályokat • bővítjük az ismeretanyagot A következtetés és a vezérlés testre-szabásához a következő programozási technikák állnak rendelkezésre: • a s zabályok s orrendjének m egváltoztatása ( ez t örténhet vagy a szabályokhoz rendelt prioritásokkal, amennyiben erre van lehetőség, a szabályoknak az ismeretbázisban lévő sorrendjének megváltoztatásával és így időben elvágjuk a gyakran meghiúsuló szabályok lehetőségeit) • bizonytalanság kezelésnél s zabályonként k üszöbszám m egadása ( ezzel befolyásolni t udjuk a s zabályok az on m eghiúsulásait, am elyek egy globális küszöbszám

alkalmazása miatt következnének be • többértékű cél megadása (a megoldás fokozatos megközelítésekor a célokat részcélokra lehet bontani) 2.64 Adatvezérelt rendszerek építéséről Az adatvezérelt rendszerek az adat okból k iindulva k onstruálják a m egoldásokat. Mivel ál talában s ok m egoldás l étezek, nem m indegy, hog y a k eresés m ilyen úton történik. Ezért az ismeretmérnök számára biztosítani kell a beavatkozás lehetőségét a v ezérlés m entébe. A z adat vezérelt r endszerek f ejlesztésének mindenegyes fázisában a szakterületi ismeretek objektumokká illetve szabályokká történő átalakításával pár huzamosan k ell a v égrehajtás v ezérlését i s meghatározni. Ennek hatásos eszköze lehet a szabályokhoz rendelt prioritás Az adatvezérelt rendszerek építésének lépései a következők: • a probléma elemzése és definiálása • az induló adatok megadása • az induló szabálykészlet kidolgozása • a

rendszer megállásának beállítása • a szabályvégrehajtás vezérlése • a rendszer továbbfejlesztése A rendszer f inomítása, t ovábbfejlesztése s orán a c élvezérelt r endszerekhez hasonlóan ügyelni kell egyes szabályok „tüzelésének” összehangolására. 2.65 Hibrid rendszerek építéséről A hibrid eszközök világos felépítésű alkalmazások fejlesztését lehetővé tevő, erőteljes fejlesztő eszközök. Az általános célú tudásalapú eszközök piacán a hibrid eszközök dominálnak. A hibrid rendszerek építésének javasolt lépései a következők: • a probléma meghatározása • keretek és rekeszek megadása • az egyedek megadása • felhasználói felület (képernyő objektumok) megadása • a szabályok megadása • metódusok megadása • az üzenetküldés kidolgozása A hibrid r endszerek épí tésének t echnikai f ogásai és m ódszerei s ok s zempontból megegyeznek az obj ektum-orientált programozás t

echnikai f ogásaival. A z el térés a tudásszerzésben, a heurisztikákat megtestesítő szabályokban és a magyarázatadás területén van. 2.66 Ellenőrző kérdések 1, Sorolja fel az ismeretalapú rendszerek fejlesztésének legfontosabb eszközeit! 2, Ismeretese a keretrendszerek lényegét, és a mai modern keretrendszerek szolgáltatásait. 3, Ismertese a Hayes-Roth féle rendszer fejlesztési modellt és mutassa be részletesen annak egyes lépéseit! 4, Mik a Hayes-Roth modell hátrányai? 5, Kik és milyen jellegű együttműködését kívánja meg az ismeretalapú rendszerek fejlesztése? 6, Ismertesse az ismeretszerzés csoportosítását és eszközrendszerét. 7, Sorolja fel a célvezérelt rendszerek fejlesztésének lépéseit. 8, Mutassa be a probléma elemzésének és belső struktúra meghatározásának céljait. 9, Ismertesse az induló szabálykészlet létrehozásának módjait és a szabálykészlet finomításának célkitűzéseit. 10, Milyen

programozási technikák állnak rendelkezésre a következtetés és a vezérlés testre szabásához? 11, Sorolja fel az adatvezérelt rendszerek fejlesztésének lépéseit. 12, Sorolja fel a hibrid rendszerek javasolt fejlesztési lépéseit. Irodalomjegyzék [1] Blum, A. Neural Networks in C++ John Wiley 1992 [2] Bocklisch, S.F Prozessanalyse mit unscharfen Verfahren VEB Verlag Technik, Berlin 1987 [3] Borgulya István Szakértői rendszerek, technikák és alkalmazások Computer Books, Budapest 1995 [4] Bothe H-H. Fuzzy Logic: Einführung in Theorie und Anwendungen Springer Verlag, Berlin 1993 [5] Dertouzos, M.L Threshold Logic: A Synthesis Approach M.IT Press Cambridge MA 1962 [6] Gábor A. Szakértői rendszerek ’88 Számalk 1988 [7] Hayes-Roth, F. Waterman, DA Lenat, DB Building Expert Systems Addison-Wesley 1983 [8] Kohonen, T. Self-Organization and Associative Memory Springer Verlag New York 1988 [9] Kosko B. Neural Networks and Fuzzy Systems Prentice-Hall, Englewood

Cliffs N.J1992 [10] Márkusz Zs. Prologban programozni könnyű Novotrade Rt. 1988 [11] Masters, T. Signal and Image Processing with Neural Networks John Wiley 1994 [12] Minsky, M. Papert, S Perceptrons: An Introduction to Computational Geometry M.IT Press 1969 [13] Puppe Einführung in Expertensysteme Springer Verlag Berlin 1991 [14] Rojas R. Theorie der neuronalen Netze: Eine systematische Einführung Springer Verlag, Berlin 1993 [15] Sántháné-Tóth Edit Tudásalapú technológia, szakértői rendszerek Dunaújváros, 1997 [16] Winston, P.H Artificial Intelligence Addison-Wesley, Reading, MA 1984 [17] Winston, P.H Horn, BKP LISP Addison-Wesley, Reading, MA 1984 [18] Yoshiaki Shirai-Jun-ichi Tsuji Mesterséges intelligencia Novotrade Rt., Budapest 1987 [19] Zadeh, L.A Fuzzy sets Information and Control 8, 338-353