Informatika | Mesterséges intelligencia » Tejfel Máté - A Rete-algoritmus

Hallgatói Esszék ELTE, MI-sáv Tudásalapú technológia c. tárgy A Rete-algoritmus Egy gyors módszer az előrefelé következtető rendszerek tüzelőképes szabályainak meghatározására Készítette: Tejfel Máté V. éves hallgató Budapest 1999/2000 tanév 1.félév A Rete-algoritmus Az előrefelé következtető rendszereknek minden végrehajtási ciklusban meg kell állapítaniuk, hogy melyek a tüzelőképes szabályok (azaz mely szabályok feltételrészét elégítik ki az eddig kikövetkeztetett, a munkamemóriában található tények). Ehhez a rendszernek minden ciklusban minden szabály minden előfeltételéhez meg kell próbálnia illeszteni az összes lehetséges tényt. Például ha 20 tény van a munkamemóriánkban, 150 szabályunk van, és átlagosan minden szabálynak 4 előfeltétele, akkor minden végrehajtási ciklusban 150*(20^4) = 24000000 illesztést kell elvégezni. Az algoritmus segítségével a fenti időigényes munka elkerülésével is

megállapíthatjuk, melyek a tüzelőképes szabályok. Ugyanis - felismerve, hogy a potenciálisan végrehajtható szabályok ciklusonként nem változnak számottevően - a körönkénti illesztés helyett a tüzelőképes szabályok listáját tartjuk nyilván, és azt módosítjuk a munkamemória változásainak megfelelően. A Rete-algoritmus kétféle hálót készít el minden szabályhoz, a mintahálót és az illesztési hálót, és ezek, ill. a munkamemória alapján állapítja meg melyek a tüzelőképes szabályok Nézzük meg egy konkrét példán keresztül az algoritmus működését. Tekintsük ehhez a következő szabályt, amelynek minden előfeltétele az alábbi formájú: ( állat-típus , szín , méret , szőr-hossz , név) A változóneveket ? vezeti be: IF (( cat ?c small ?h ?n1) (dog ?c ?q medium ?n2) (cat ?c large ?h ?n3) (dog ?c ?q long ?n4) ) THEN ( . ) A mintaháló az előfeltételek alapján létrehozott fákat tartalmaz. Minden fa gyökere a

feltételrész első eleme, a fa csomópontjai pedig a feltételek további tagjai. Így példánk esetén a két első feltételből a következő fák alakulnak ki: 1 1. ábra Két előfeltétel mintahálója Amikor a harmadik előfeltételt adjuk hozzá a hálóhoz, az algoritmus érzékeli, hogy létezik már cat gyökerű fa, és a meglévő hálót felhasználja a lehető legnagyobb mértékben. Hasonló akció hajtódik végre a negyedik előfeltétel kidolgozásakor is. Így a végeredményként kapott mintaháló a következő: 2. ábra A szabály feltételrészének mintahálója A mintaháló elkészülte után az algoritmus felépíti az illesztési hálót. Az illesztési háló a mintaháló fáinak különböző leveleit kapcsolja össze ( abban a sorrendben, ahogy azok a szabály feltételrészében előfordultak ), és összehasonlítja az azonos nevű változókat, így biztosítva, hogy azonos értékeket vegyenek fel. A fenti esetben az alábbi illesztési

háló jön létre: 2 3. ábra A mintahálóhoz rendelt illesztési háló Nézzük, hogyan használja fel a Rete-algoritmus ezeket a hálókat a szabályok tüzelőképességének megállapításához. Legyen a munkamemóriában lévő 9 tény a következő : 1. ( cat yellow large short rebel ) 2. ( cat calico large short rubble ) 3. ( cat calico small short kitty ) 4. ( dog brown medium long charlie ) 5. ( cat brown small medium prince ) 6. ( dog brown small short sam ) 7. ( dog calico medium medium butch ) 8. ( dog brown large medium star ) 9. ( dog calico medium long tramp ) Ezeket a tényeket ráengedjük a mintahálóra megnézve melyik hová (melyik ágra) illeszkedik, ha egyáltalán illeszkedik (pl. a 6 tény nem fog átfolyni a hálón) Az illeszkedések alapján pedig kitöltjük a változók értékeit ( a mintahálóban a változók többszörös értékeket vehetnek fel). Nézzük ezt a konkrét esetben : 3 4. ábra A mintaháló aktualizálása A mintahálón

sikeresen átfolyt szabályokra azután az algoritmus elvégzi az illesztési háló alapján a megfelelő ellenőrzéseket, azaz az azonos változók értékei szerint összekapcsolja a leveleknél megjelenő tényeket, ha lehetséges. Például az előbbi esetet tekintve: 4 5. ábra Az illesztési háló kitöltése Azaz a fenti munkamemóriát feltételezve megkapjuk, hogy a vizsgált szabály tüzelőképes, hiszen a 2.,3,7,9 tények, ebben a sorrendben, kielégítik a szabály előfeltételét Ha az illesztési háló alapján nem kaptunk volna megfelelően összekapcsolható tényeket, akkor azt állapíthatnánk meg, hogy a szabály nem tüzelőképes. 5 Több, illetve összetettebb szabályok esetén az algoritmus - a lehetséges mértékig - felhasználja a meglévő hálórészletet a felépítéskor, ezzel is gyorsítva a végrehajtást. Amikor egy szabályt végrehajtunk, a munkamemória értelemszerűen módosul, így természetesen a két hálón megjelenő

értékek is módosulnak. Ezeket megfelelően karbantartva a Rete-algoritmussal gyorsan megállapítható, hogy egy-egy lépésben melyek a végrehajtható szabályok. Forrásmunka: [Gonazalez, 1993]: Gonzalez, A.J; Dankel, DD, "The Engineering of Knowledge Systems – theory and Practice", Prentice-Hall, Inc., 1993, 127-134 Klasszikus irodalom: Brownston, L., Farrell, R, Kant, E and Martin, N, "Programming Expert Systems in OPS5", Addison Wesley Publishing Co., 1986 Forgy, C. L, "On the Efficient Implementation of Production Systems", Ph Thesis, 1979 Forgy, C. L, "Rete: Just algorithms for the many pattern / many object pattern match problem", Atrificial Intelligence Vol. 19, 1982, pp 17-28 6