Intelligens Rendszerek I. Szabályalapú tudásábrázolás

Intelligens Rendszerek I. Szabályalapú tudásábrázolás 2007/2008. tanév, I. félév Dr. Kovács Szilveszter E-mail: [email protected] Miskolci Egyetem Informatikai Intézet 106. sz. szoba Tel: (46) 565-111 / 21-06 mellék

Ágens Szűkebb értelmezés: Az ágens olyan rendszer, amely • környezetbe ágyazott, • reaktív: érzékel és reagál, • racionális: helyesen cselekszik. • Lehet autonóm: saját tapasztalatai alapján, emberi beavatkozás nélkül működik. • Lehet reflexszerű, cél, vagy hasznosságvezérelt.

Dr. Kovács Szilveszter ©

M.I. 8. / 2.

Tudásbázisú ágens • • • •

Ismeri környezetét Kikövetkezteti cselekvéseit Képes új feladatok elfogadására Autonóm ⇒ alkalmazkodik a környezetváltozásokhoz • Ismeri cselekvései eredményeit


M.I. 8. / 3.

A tudásábrázolás elvárt jellemzői Patrick Winston szerint 1. A fontos dolgokat világosan adja meg. 2. Fedje fel a természetes korlátokat, megkönnyítve a számítások néhány fajtáját. 3. Legyen teljes. 4. Legyen tömör. 5. Legyen átlátható számunkra. 6. Legyen alkalmas gyors feldolgozásra. 7. Rejtse el a részleteket, de tegye elérhetővé azokat szükség esetén. 8. Létezzen rá számítógépi eljárás. A jó tudásábrázolás az MI feladatok megoldásánál fél siker. Dr. Kovács Szilveszter ©

M.I. 8. / 4.

Tudástípusok • Deklaratív • Strukturált • Procedurális


M.I. 8. / 5.

Deklaratív tudás • Csak ismeretek, összefüggések és alkalmazási utasítások nélkül • Leírása: – logikai kifejezések – fogalmak – objektumok • Technikák: – formális logika – O-T-É hármas


M.I. 8. / 6.

Strukturált tudás • Fogalmak, objektumok közötti kapcsolatok • Leírás: – grafikusan – szabálycsoportok • Technikák: – szemantikus háló – keret (frame) – forgatókönyv, táblázat – szabálycsoport


M.I. 8. / 7.

Procedurális tudás • Megadja, hogyan kell a problémát megoldani • Leírása: – szabályok – eljárások – függvények – célok • Technikák: – szabály – eljárás, függvény – agenda – stratégia Dr. Kovács Szilveszter ©

M.I. 8. / 8.

Tudásábrázolási módszerek • Szimbolikus (formális) logika (ítéletkalkulus, elsőrendű logika) • Szabályalapú rendszerek • Szemantikus hálók • Keretek, script-ek • Neurális hálózatok • Modellalapú • Hibrid Dr. Kovács Szilveszter ©

Deklaratív Strukturált Procedurális

M.I. 8. / 9.

Tudásábrázolási technikák Tudástípus

Technika

Deklaratív

előállító szabály szimbolikus logika O-T-É hármas szemantikus háló keret (frame) forgatókönyv, táblázat szabálycsoport

Strukturált

Procedurális

szabály eljárás, függvény agenda stratégia


M.I. 8. / 10.

Előállító szabályok, szabályalapú tudásszemléltetés • Előállító szabály (production rule): egy IF-THEN, feltétel-következmény szerkezet, melyet egyaránt alkalmaznak a problémák megoldásához szükséges deklaratív (leíró) és procedurális (eljárásokon alapuló) tudás ábrázolására. • A logikában neve: implikáció, modus ponens: α → β, α Ha α → β igaz és α igaz, akkor β igaz β • Deklaratív következmény: kikövetkeztetett tény • Procedurális következmény: akció. Dr. Kovács Szilveszter ©

M.I. 8. / 11.

A szabályok E.g. • IF THEN • IF THEN

the ‘traffic light’ is ‘green’ the action is go the ‘traffic light’ is ‘red’ the action is stop

• IF

THEN


M.I. 8. / 12.

A szabályok lehetséges értelmezései • Reláció: IF the ‘fuel tank’ is empty THEN the car is dead • Ajánlás: IF the season is autumn AND the sky is cloudy AND the forecast is drizzle THEN the advice is ‘take an umbrella’ • Utasítás: IF the car is dead AND the ‘fuel tank’ is empty THEN the action is ‘refuel the car’ • Stratégia leírása: IF the car is dead THEN the action is ‘check the fuel tank’; step1 is complete IF step1 is complete AND the ‘fuel tank’ is full THEN the action is ‘check the battery’; step2 is complete • Heurisztika: IF the spill is liquid AND the ‘spill pH’ < 6 AND the ‘spill smell’ is vinegar THEN the ‘spill material’ is ‘acetic acid’ Dr. Kovács Szilveszter ©

M.I. 8. / 13.

A szabályalapú rendszerek általános struktúrája • A produkciós szabályokat a hosszútávú memória míg a probláma-specifikus adatokat vagy tényeket az átmeneti memória tárolja


M.I. 8. / 14.

Előállító szabályok, szabályalapú tudásszemléltetés • Szabályalapú tudásszemléltetést és következtető automatát alkalmazó szakértőrendszer felépítése


M.I. 8. / 15.

Szabályalapú szakértői rendszerek struktúrája


M.I. 8. / 16.

Előállító szabályok, szabályalapú tudásszemléltetés • Szabályláncolás - a következtetési folyamat megvalósulása szabályláncolódás = a szabály következményrésze illeszkedik más szabály feltételrészére • Ha az összes kapcsolódást megvalósítanánk, előállna a szabálybázis által reprezentált összes következtetési fa, melyek egymáshoz rendelnék a leveleiken szereplő tényeket és a fák csúcsán szereplő végkövetkeztetéseket. • A következtetési fa teljes előállítása gyakorlatilag lehetetlen, ezért egy konkrét esetre a következtetési feladat végigvitele a következtető automatára hárul. Dr. Kovács Szilveszter ©

M.I. 8. / 17.

Következtetési lánc • A következtető gép ciklikusan illeszt és tüzel (halad tovább) • The matching of the rule IF parts to the facts produces inference chains. The inference chain indicates how an expert system applies the rules to reach a conclusion. A

X

Database Fact: A is x

B

Y

Fact: B is y

Z E

Match

Fire Knowledge Base

D

Rule 1: IF Y is true AND D is true THEN Z is true Rule 2: IF X is true AND B is true AND E is true THEN Y is true Rule 3: IF A is true THEN X is true

Rule: IF A is x THEN B is y


M.I. 8. / 18.

Előállító szabályok, szabályalapú tudásszemléltetés • Előrehaladó láncolás (forward chaining): a végkonklúzió megtalálása a feladat, a megadott tényekből kiindulva

• Hátrafelé haladó láncolás (backward chaining): az elérendő cél adott és a szükséges előfeltételek megtalálása, ill a megadottak elégséges voltának megállapítása a cél.


M.I. 8. / 19.

Előállító szabályok, szabályalapú tudásszemléltetés Előnyös alkalmazási terület (Christopher Chabris): • Előrehaladó láncolás: ha a megoldandó problémával kapcsolatosan nagyszámú összegyűjtött adattal rendelkezünk, de a megoldást illetően nincs jó elképzelésünk. A szabályalapú rendszer el fogja végezni az összes végrehajtható következtetést és elő fogja állítani a megadott tényekből következő összes szóba jöhető megoldást. • Az előrehaladó láncolást alkalmazó rendszert deduktív rendszernek is szokták nevezni utalva a sorozatban végzett deduktív logikai következtető műveletre (modus ponens). Dr. Kovács Szilveszter ©

M.I. 8. / 20.

Előállító szabályok, szabályalapú tudásszemléltetés • Előrehaladó szabályláncolás


M.I. 8. / 21.

Előállító szabályok, szabályalapú tudásszemléltetés Szabályalapú következtetés működése előrehaladó láncolásnál Feladat: A szabálybázist és az aktuális feladat tényeit felhasználva meg kell próbálni elérni a célállapotot, mely a problémára adott válasz, vagy egy elfogadható választ reprezentáló részcél elérése lehet.


M.I. 8. / 22.

Előállító szabályok, szabályalapú tudásszemléltetés Szabályalapú következtetés működése előrehaladó láncolásnál Lépések: 1. Mintaillesztés: ki kell keresni a szabálybázisból az összes olyan szabályt, melynek a feltételrésze a ténybázisbeli tényekkel igaz. 2. Konfliktusfeloldás: az 1. lépésben megtalált szabályok alkotják a konfliktus-halmazt, mert bármelyik felhasználható, de csak egyet alkalmazhatunk. 3. Szabályalkalmazás: végre kell hajtani a kiválasztott szabály következmény-részében szereplő tevékenységet, ill. fel kell használni az új tényt. (Új tény: az adott feladatra nézve igaz, kikövetkeztetett.) 4. A célállapot tesztelése: meg kell vizsgálni, eljutottunk-e a célállapotba, ha nem, folytatni kell 1.-től. Dr. Kovács Szilveszter ©

M.I. 8. / 23.

Előrehaladó láncolás– p.l. Kérdés: A tudásbázis alapján mi következtethető ki és igaz-e Z ? Database A

B

C

D

Database E

A

X

Match

Fire

Match

Knowledge Base Y&D Z X&B&E Y A X C L L&M N

B

C

Database

D

E

X

L

Fire


Cycle 1

A

B

Database

C

D

E

X

L

Y

Match

Fire

A

B

C

D

E

X

L

Y

Z

Match

Fire



Cycle 2

Cycle 3


M.I. 8. / 24.

Előrehaladó láncolás • Az előrehaladó láncolás egy olyan technika, mely információt gyűjt és abból minden kikövetkeztethetőt kikövetkeztet. • Habár, az előrehaladó láncolás során, sok olyan szabály is végrehajtódik melyeknek nincs közül a kitűzött célhoz. • Ezért, ha az a célunk, hogy egyetlen tény igaz voltát vizsgáljuk, az előrehaladó láncolás nem hatékony.


M.I. 8. / 25.

Előállító szabályok, szabályalapú tudásszemléltetés Előnyös alkalmazási terület (Christopher Chabris): • Hátrafelé haladó láncolás: amikor egy, vagy több hipotézissel rendelkezünk a problémánk megoldására vonatkozóan és azt kívánjuk, hogy a szabályalapú rendszerünk ellenőrizze ezeket. A hipotézistől visszafelé indulva a rendszer bekéri a hipotézis teljesüléséhez szükséges adatokat.


M.I. 8. / 26.

Hátrafelé haladó láncolás 1. Első lépéskény a szabálybázisból olyan szabályokat keres, melyek a bizonyítani kívánt állításra következtetnek. Ezen szabályoknak a THEN (akció) oldala tartalmazza a célt. 2. Ha talál ilyen szabályt, akkor az IF (feltétel) oldalát illeszti a ténybázisra, ha az teljesül, a cél teljesült, az állítás igaz. 3. Ha az IF (feltétel) oldala nincs benne a ténybázisban, akkor a következtető gép félreteszi a vizsgált szabályt (the rule is stacking) és újabb célt állít fel, egy részcélt, hogy bizonyítsa ezen szabály IF (feltétel) oldalát. 4. Ezután újból átvizsgálja a szabálybázist, hogy talál-e olyan szabályokat, melyek az új részcélra következtetnek. 5. A következtető gép mindaddig ismétli ezt a folyamatot az újabb és újabb szabályok stack-elését) míg van olyan szabály, mely az újabb részcélra következtet. Dr. Kovács Szilveszter ©

M.I. 8. / 27.

Hátrafelé haladó láncolás – p.l. A

Kérdés: Bizonyítható-e, hogy Z igaz a tudásbázis alapján?

Pass 1

Pass 2

Pass 3

Database

Database

Database

B

C

D

E

A

B

C

D

E

A

?

Z

A

C

D

X Knowledge Base Y&D Z X&B&E Y A X C L L&M N


Goal: Z

Sub-Goal: Y

Sub-Goal: X

Pass 4

Pass 5

Pass 6

Database

Database

B

C

D

E

A

B

X

Match

Fire


E

?

Y Knowledge Base Y&D Z X&B&E Y A X C L L&M N

B

C

Database

D

E

X

Y

Match

Fire


Sub-Goal: X


Sub-Goal: Y

A

B

C

D

E

X

Y

Z

Match

Fire

Knowledge Base Y&D Z X&B&E Y A X C L L&M N Goal: Z

M.I. 8. / 28.

Előre-, vagy hátrafelé haladó láncolás? Az előre láncolás adat-vezérelt következtetés. • Akkor jó, ha a rendszer először adatokat gyűjt, majd ezekből igyekszik minél több dolgot kikövetkeztetni. A visszafelé láncolás cél-orientált következtetés. • Akkor jó, ha a rendszer egy kezdeti hipotetikus elképzelésből indul és megpróbálja megkeresni a tényeket amelyek igazolják azt.


M.I. 8. / 29.

Előállító szabályok, szabályalapú tudásszemléltetés A következtető automata konfliktusfeloldó működésének vezérlése • Lokális: lokális információkat, speciális, tartománytól függő szabályokat, metaszabályokat alkalmaz. A programozó bizonyos hatások kiváltására közvetlenül megadhat szabályokat. • Globális: globális információkra alapoz, a teljes szabálytartományban egyformán működik. • Globális konfliktus-feloldási módszerek jellemzői: – érzékenység, – stabilitás

• Globális konfliktus-feloldási módszerek fajtái: – Prioritás – Újdonság – Specifikusság. Dr. Kovács Szilveszter ©

M.I. 8. / 30.

Conflict resolution – e.g.

Rule 1: IF the ‘traffic light’ is green THEN the action is go Rule 2: IF the ‘traffic light’ is red THEN the action is stop Rule 3: IF the ‘traffic light’ is red THEN the action is go

• Conflict set: rules firing in a given cycle having different consequent • Conflict resolution: A method for choosing a rule to fire when more than one rule can be fired in a given cycle . Dr. Kovács Szilveszter ©

M.I. 8. / 31.

Conflict resolution methods - Lokális • Metaszabályok (metaknowledge): „Tudás a tudás(bázis)ról”. The knowledge about the use and control of domain knowledge in an expert system. • In rule-based expert systems, metaknowledge is represented by metarules. • A metarule determines a strategy for the use of task-specific rules in the expert system.


M.I. 8. / 32.

Metaknowledge – Metarules – e.g. Metarule 1: Rules supplied by experts have higher priorities than rules supplied by novices. Metarule 2: Rules governing the rescue of human lives have higher priorities than rules concerned with clearing overloads on power system equipment.


M.I. 8. / 33.

Conflict resolution methods - Globális • Prioritás (priority): A legmagasabb prioritású szabály tüzeljen. In simple applications, the priority can be established by placing the rules in an appropriate order in the knowledge base. • Specifikusság (the most specific rule): A legspecifikusabb – a leghosszabban illeszkedő – szabáy tüzeljen. It is based on the assumption that a specific rule processes more information than a general one. • Újdonság (most recently entered data): Az a szabály tüzeljen, amelyik legutoljára került a szabálybázisba (a legfiatalabb). This method relies on time tags attached to each fact in the database. In the conflict set, the expert system first fires the rule whose antecedent uses the data most recently added to the database. Dr. Kovács Szilveszter ©

M.I. 8. / 34.

Előállító szabályok, szabályalapú tudásszemléltetés A szabályalapú rendszerek előnyei • Modularitás: egyedi előállító szabályok hozzáadhatók, törölhetők, megváltoztathatók • Egyöntetűség: homogén ábrázolás, könnyű megértés, öndokumentáló • Természetesség: emberi problémamegoldáshoz hasonló.


M.I. 8. / 35.

Előállító szabályok, szabályalapú tudásszemléltetés A szabályalapú rendszerek hátrányos tulajdonságai • Merevek: nem nyújtanak különféle absztrakciós szinteket, nem képesek „tapasztalatok alapján” bővíteni szabálybázisukat • Nem hatékonyak: ténybázis-szabálybázis illesztés, kombinatorikus robbanás. • Sok szabály esetén a szabályok szerepe, egymásra hatása nehezen követhető, értékelhető. A szabályalapú tudásszemléltetés rendkívül elterjedt és számtalan szakértőrendszernek és szakértőrendszer-váznak alkotja az alapját. Dr. Kovács Szilveszter ©

M.I. 8. / 36.

Előállító szabályok, szabályalapú tudásszemléltetés Előnyös alkalmazási területek (Barr, Feigenbaum) • Elosztott tudás esetén. Ilyen esetben a tények aránya a szabályokhoz képest jelentős. Példaként a klinikai gyógyászati rendszereket említhetjük. • Olyan esetekben, amikor a szemléltetett tudás és a vezérlő szerkezetek jól elkülöníthetők. Olyan tudásterületeknél áll ez fenn, amelyek könnyen elkülöníthetők a felhasználásukra szolgáló módszerektől, mint például a biológiai osztályozás. • Független tevékenységek esetén. Olyan területek ezek, amelyeknek a folyamatai egymástól elkülönülő tevékenységek halmazaként állnak elő, mint például a gyógyászatban a betegmegfigyelő rendszerek. • Alkalmas nem teljes, vagy bizonytalan tudás ábrázolására. Dr. Kovács Szilveszter ©

M.I. 8. / 37.

Ajánlott irodalom • Jelen előadás fóliái részben az alábbi források alapján készültek: Dr. Dudás László: Mesterséges Intelligencia Módszerek, Miskolci Egyetem, Alkalmazott Informatikai Tanszék, http://www.ait.iit.uni-miskolc.hu/~dudas/MIEAok Michael Negnevitsky: Artificial Intelligence: A Guide to Intelligent Systems, Addison Wesley, Pearson Education Limited, 2002. ISBN 0201-71159-1 Stuart J. Russel – Peter Norvig: Mesterséges Intelligencia modern megközelítésben, Panem-Prentice-Hall, Budapest, 2000, ISBN 963 545 241 1 Dr. Kovács Szilveszter ©

M.I. 8. / 38.

Intelligens Rendszerek I. Szabályalapú tudásábrázolás

Recommend Documents