II. Szabályalapú következtetés

Szabályalapú következtetés lényege 

II. Szabályalapú következtetés

felhasználható ismeretek



Gregorics Tibor

Ismeretalapú modellezés

Szabályalapú technikáknál az ismereteket vagy ha-akkor szerkezetű szabályokkal, vagy feltétel nélküli tényállításokkal a feladat megoldásához írják le.

általános

–



–



speciális

–





MI általános megoldó sémája ha feltétel akkor hatás A szabály lehet a megoldás beégetett procedurális eleme is.

o

–

•

o

ha feltétel akkor állítás Tételbizonyító módszer A szabályok implikációt tartalmazó logikai állítások.



(∀x)(∀y)(holding(x)  ontable(y)  clear(y) → on(x, y)) (∀x)(∀y)(holding(x)  ontable(y)  clear(y) → on(x, y))

Tananyagra vonatkozó állítás: ha nehézség=„közepes” és jegyzeteltség=„rossz” akkor tanulási_idő=„hosszú”

Procedurális (végrehajtható programok formájában) o

ha holding(x) és ontable(y) és clear(y) akkor stack(x, y)

A logika nyelve egy programozási nyelv A szabályok speciális logikai állítások: Horn klózok

Gregorics Tibor


Gregorics Tibor

3


Szabály alkalmazása: láncolás 





Ha a szabály feltétele illeszkedik az aktuális állapothoz, akkor a szabály következményének megfelelően módosítható az aktuális állapot vagy a továbbiakban feltételezhető a rákövetkező állapot.

•




hő = 105 ha hő > 80 akkor Riasztás

Sztringek adott hibahatárú illesztése •

Ha a szabály következménye illeszkedik az éppen vizsgált részcélhoz, akkor ezen részcél eléréséhez elegendő a továbbiakban a szabály feltételét igazolni, a részcélt ezzel visszavezetjük a szabály feltételére.

Gregorics Tibor

Illesztés egyszerű program változókkal •

Visszafelé láncolás 

4

Illesztés

Előre láncolás 

2

Kockavilágra vonatkozó állítás: ha holding(x) és ontable(y) és clear(y) akkor on(x, y) •

ha feltétel akkor következmény IR egyik markáns fajtája A szabályokat szimbolikus formában, elkülönítve tárolja.

Logikai programozásban (Prolog) –


Deklaratív (logikai állítás)

Szabályalapú logikai következtetésnél –

általános, szabály formájú ismeretek

Szabályok leírásának módjai

Szabályalapú rendszerekben –

konkrét, tényszerű ismeretek

Gregorics Tibor

1

Produkciós rendszerekben (Kereső rendszer) –

általános szakterületi ismeretek

Egy feladat-megoldási helyzetben meg kell határozni az alkalmazható szabályokat, kiválasztani közülük egyet és azt végrehajtani, aminek következtében módosul a feladatmegoldási helyzet.

Szabályalapú következtetés különböző megközelítései 

konkrét feladattal kapcsolatos ismeretek

„Makko Szeged utca 3.”

token-attribútumok: státusz, érték, javított érték, stb. •

5

Pl: Makó ha tokeni.státusz:=nem_ismert és távolság(tokeni.érték, név) < limit ahol név∊településnévtár akkor tokeni.javérték:=név és tokeni.státusz:=településnév

Gregorics Tibor


6

1

Illesztés 

Elsőrendű logikai állítások illesztése P(a)Q(a) P(a)Q(a)

• •



Megoldható feladatok fajtái Egy kezdeti állapotból (illetve az azt jellemző tényekből) kiindulva el kell jutni egy célállapotba vagy meg kell konstruálni egy célállapotot.

1.

x helyébe a

(x) (P(x)Q(x) → R(x) ) (x) ((P(x)  Q(x)) → R(x) )

o

a 45%-ban nehéz, 31%-osan jegyzetelt tananyag ha nehézség= „közepes” és jegyzeteltség= „rossz” akkor tanulási_idő= „hosszú”

• •

Építsük fel az on(A,B) tornyot adott kezdő állásból! Keressük a kockák olyan elrendezését adott kezdő állásból, ahol egy kocka egy másik tetején van! Pl.: on(A,B)  clear(A)  on(B,C)  ontable(C)  handempty()

o

Fuzzy fogalmak illesztése

Egy célállítást kell ki következtetni a kezdetben érvényes tényekre támaszkodva akár úgy is, hogy közben a célállítást is pontosítani kell, annak nem ismert attribútumait fel kell tárni.

2.

Felépíthető-e megadott kockákból egy on(A,B) torony? Teljesülhet-e az on(x,y) célállítás, és vajon milyen x és y értékekre?

o o

Gregorics Tibor


Gregorics Tibor

7


A következtetés iránya 



Adatvezérelt következtetés tények

Előre haladó vagy adatvezérelt

munka memória E

H

betesz mindent

A, B, E, G, H

végrehajt

szabályok A,B then add(D) A then swap(A,C) C,D then add(Z)

Célállítás igazolását a szabályok felhasználásával visszavezeti a tényekre. Minden lépésben egy részcélt vezet vissza egy szabály feltételére, amely a továbbiakban részcéllá válik. Akkor fejeződik be sikeresen, ha minden részcél a tényekre vezetődik vissza.

végrehajt

végrehajt

Szabályalkalmazási lánc:

Z

A, B, E, G, H, D

C, B, E, G, H, D

C, B, E, G, H, D, Z 2.

C

A 1.

cél illeszt?

B

Visszafelé haladó vagy célvezérelt •

A G

Tényekből kiindulva a célállapot felé halad. Egy szabály alkalmazása az aktuális állapotot változtatja meg vagy előállítja a következő állapot által kielégített feltételt. Akkor fejeződik be sikeresen, ha olyan állapotba jut, amelyre a célállítás teljesül.

•

8

D

3.

Z

B Gregorics Tibor


Gregorics Tibor

9

Célvezérelt következtetés munka memória

tények A

E

G

illeszt? H

cél

betesz: Z

Z

szabályok

B

C, D

kivesz: Z; betesz C,D

A, D





kivesz: C; betesz: A

D A, B

Szabályalkalmazási lánc: Z

kivesz: D; betesz A,B

C

2.

1. D

Gregorics Tibor



A 3.

10

Szabályalapú következtetés eredménye

Z

Z if C,D C if A D if A,B


Az eredmény adatvezérelt következtetés esetén a kívánt következmény, célvezérelt esetben egy „Rendben” válasz a cél attribútumainak esetleges pontosítása mellett, de mindkét esetben kiegészül egy magyarázattal is. A magyarázat lényegében az a szabályalkalmazási (vagy következtetési) lánc, amely megmutatja, hogy mely szabályoknak, milyen sorrendben és milyen milyen illesztés mellett végrehajtott alkalmazásával kaptuk az eredményt. A megoldás kereséssel történik. Előnyben részesítjük a heurisztikus módosítható stratégiájú kereséseket; az esetek döntő részében ez egy visszalépéses keresés.

B Ismeretalapú modellezés

11

Gregorics Tibor


12

2

Szabályalapú reprezentáció előnye és hátránya 

Előnyök o o

o



Természetes ábrázolás A szabályok egymástól függetlenül építhetők be az ismeretbázisba. Könnyen kiegészíthető bizonytalanságkezelési lehetőségekkel

Gregorics Tibor

Hátrányok o o

o

Esettanulmány: Cím tisztítás 

Nem objektum alapú Nehéz kivédeni az ellentmondó és redundáns szabályok bekerülését. Nincs szabványosítva a szabályokat leíró nyelv


Probléma – Különböző mértékben részletezett, eltérő sorrendben megadott, hiányos, esetenként hibás, elektronikus formájú, szövegesen megadott postai címek beazonosítása a szabványos országos címadatbázisba. – Több lehetséges válasz esetén a legjobban illeszkedő címet (címeket) adjuk meg. – Rendeljünk a megoldáshoz egy illeszkedési mértéket

Gregorics Tibor

13


A feladat nehézsége    



Elírások és hibás adatok fordulhatnak elő (4-8. helyett csak 4, Bajcsi-Zsininszki Endre) Adatelemek között inkonzinsztencia léphet fel (település és irányítószám) Rövidítéseket kell kezelni (Bp. Nagy L. kir. u.) Az épület, lépcsőház, emelet besorolás feldolgozása, ami nincs szabványosítva (írásmódja lehet római vagy arab szám, sorrendjük nem rögzített) Településrészek, csatolt települések kezelése (Pl.: "Bükkszentlászló, Fő utca" = "Miskolc, Fő utca", "Agárd" = "Gárdony")

Gregorics Tibor


Megoldás ötlete 

A vizsgált címet szintaktikai egységekre (token) bontjuk.



Fokozatosan válik a kezdeti cím teljesen beazonosított címmé úgy, hogy minden lépésben egy újabb címrészt próbálunk felfedni, azaz egy vagy több szomszédos beazonosítatlan tokenről megmondjuk, hogy melyik címrészhez tartozik és mi az értéke(ha kell, javítjuk).

•

• •



1117 Bp. Pázmány P. u. 1.  <1117><1.>

1117 Budapest Pázmány P. utca 1.  1117 Budapest Pázmány Péter. utca 1. … 1. C ép. (1 ~ házszám)  … 1. C ép. (C ~ épület, ép. ~ )

Minden lépésnek és ezek következtében a címnek is van egy hihetősége (0 és 1 közötti valós szám). A cím hihetősége kezdetben 1, amelyet minden lépés csökkent.

Gregorics Tibor

15

Szabály előfeltétele előfeltétel  következmény 

•



o

 



A szabály egyik következménye, hogy többnyire azonosít egy újabb tokent.



A szabály módosíthatja egy token értékét.

•

<StreetNumber> … 15. C ép. … (ahol a 15 már házszámként azonosított)

• •

Azonosítatlan tokenhez illeszthető: () Azonosított tokenhez illeszthető: <StreetNumber>

•



Az illesztés algoritmusát a tokenséma „Is” mögötti része azonosítja. Az azonosítatlan tokenhez való illeszkedésnek van egy mértéke: o o

16

Szabályalkalmazás hatása

Alapvetően kétféle tokenséma lehet o


előfeltétel  következmény

Az előfeltétel egy token-mintázat, úgynevezett tokensémák sorozata, amelynek illeszkednie kell a cím tokenjeinek egy részsorozatához. •

14

… 15. C ép. …(15 ~ házszám)  … 1. C ép. …(C ~ épület, ép. ~ ) Budapes Pázmány P. u. 1.  Budapest Pázmány Péter. utca 1. Budapest Pázmány P. u. 1.  Budapest Pázmány Péter. utca 1. 1118 Budapest Pázmány Péter. utca 1.  1117 Budapest …

A szabály kiszámolja megváltozott cím új hihetőségét. •

B(cím a szabály után) = B(szabályalkalmazás) * B(cím a szabály előtt) B(szabályalkalmazás) = B(szabály illeszkedés) * B(szabály)

Sztringek közötti távolság: Bp, Budapes, Butapes ~ Budapest Koherencia már azonosított tokenekkel (Pl.: irányítószám és kerület)

Gregorics Tibor


17

Gregorics Tibor


18

3

Szabálybázis 1.

Szabálybázis 2.

szint

előfeltétel

címmező

hit

szint

előfeltétel

címmező

hit

1 2 2 3

település irszám irszám kerület

100 100 50 100

8

<StreetNumber>

épület

100

8

<StreetNumber>

épület

90

8

épület

98

3 3

<Settlement> <Settlement>

kerület kerület

98 100

9

lépcső

90

9

<Building>

lépcső

100

3 4

kerület köz.típus

95 100

9

<Building>

lépcső

90

9

lépcső

98

6 7

köz.név <StreetType>

100 100

10

szint

100

10

szint

100

7

házszám

100

10

szint

99

7 7

<StreetName>

házszám házszám

75 95

10

<Stairs>

szint

99

11

ajtó

95

11

ajtó

100

Gregorics Tibor


Gregorics Tibor

19





1

A problématér elemei a valamilyen mértékben beazonosított és korrigált címek, ahol egyik címből egy másikba egy szabály vezet el. A tér szerkezete egy háló (irányított körmentes gráf). Egy címre sok szabály alkalmazható, ugyanaz a szabály több tokenhez is illeszthető, sőt egy szabály egy tokenre többféle eredményt adhat. A problématér mérete óriási! Problématér szűkítése: csoportosítjuk a szabályokat aszerint, hogy melyik címrészt azonosítja, és a címrészeket kötött sorrendben azonosítjuk. Ekkor a struktúra egy irányítatlan fa lesz.

2483 Gár I. u. 9 0.750

település szabály

Gárdony 2483 I. u. 9 0.750 Gárdony 2483 I. u. 9 0.609

Ennek bevezetése egy igen jelentős lépésnek bizonyult. Ismeretalapú modellezés

0.571

közterülettípus szabályok



Egy jó (lehetőleg a legjobb) megoldást (azaz olyan címet, amire nem lehet már szabályt alkalmazni) keresünk. Ebben o vagy minden tokent beazonosítottunk o vagy nincs több szabályalkalmazási szint, de maradtak azonosítatlan tokenek (ez tovább rontja a hihetőséget) Csak olyan módosítható keresési stratégia jöhet szóba, amely képes optimális megoldást adni. o Iteratívan mélyítő visszalépéses keresés (IDA*) lehetne, de nincs hozzá megengedhető heurisztikánk. o Az A* algoritmushoz is megengedhető heurisztika kellene. o Módosított előre tekintő (best first) gráfkeresést alkalmaztunk. Gregorics Tibor


0.634 Gyál 2360 utca I. 9

közterületnév szabályok házszám szabályok

0.466 Gyál 2360 utca Ilona 9

Gárdony 2483 utca I. 9 Gregorics Tibor

21

Megoldások keresése 

0.780 Gyál 2360 I. u. 9

Gárdony 2483 utca I. 9 0.571

0.821 Gyál 2483 I. u. 9

irányítószám szabályok

Gárdony 2483 utca I. 9

Gregorics Tibor

20

Problématér fájának részlete

Problématér 


22

Előre tekintő gráfkeresés 

 

23


Globális munkaterület (NYÍLT halmaz) a feldolgozásra váró címeket tartalmazza, kezdetben a kiinduló címet. A keresés mindig a leghihetőbb címet veszi ki a NYÍLT halmazból és arra alkalmazza az összes lehetséges szabályt az összes lehetséges módon. Nem áll le a gráfkeresés az első megoldás megtalálásakor, hanem tovább kutat jobb (jobban hihető) megoldások után. A NYÍLT halmazt korlátozzuk: csak a valahány leghihetőbb címet tárolja, de ezek közül is csak az eddig talált legjobb megoldásnál jobb hihetőségű vagy egy adott korlátnál nem rosszabb hihetőségű címeket. (vágó heurisztika) Ezek a módosítások is jelentősen javítottak a rendszeren. Gregorics Tibor


24

4

Futtatási eredmény

Megerősítéses tanulás 

Szabályok hihetősége o

B(szabály) = eredményes használatok száma / összes használat száma

Eredményes használatok o Felügyelő által megjelölt o Legjobb (néhány legjobb) megoldás kiválasztása Stratégiai paraméterek (korlátok, validálási büntetések, hiányzó vagy fel nem ismert elemek büntetése) közül szabályok alkalmazásokhoz köthető az utóbbi kettő, így arra a fenti módszer alkalmazható o



Gregorics Tibor


25

Gregorics Tibor


26

5

II. Szabályalapú következtetés

Recommend Documents