363

Mesterséges Intelligencia Csató Lehel

Mesterséges Intelligencia Csató Lehel Matematika-Informatika Tanszék Babe¸s–Bolyai Tudományegyetem, Kolozsvár

2010/2011

1/363

˝ Az Eloadások Témái Mesterséges Intelligencia

˝ mi a mesterséges intelligencia ... Bevezeto:

8

„Tudás”–reprezentáció

Csató Lehel

Gráfkeresési stratégiák

D-S modell

Szemantikus hálók / Keretrendszerek

D-S definíció Példa D-S logika

Játékok modellezése

Fuzzy rendszerek

Bizonytalanság kezelése

Tört. visszatekintés Fuzzy halmazok Fuzzy logika

Fuzzy rendszerek

Fuzzy szabályok

Grafikus modellek Tanuló rendszerek Szimulált kifutés, ˝ Genetikus algoritmusok A perceptron modell ˝ Neurális hálók, önszervezodés Gépi tanulás 169/363

Admin ...

... trívia

http://www.cs.ubbcluj.ro/~csatol/mestint

Mesterséges Intelligencia

8 Csató Lehel D-S modell D-S definíció

Vizsga Szóbeli (60%) + Gyakorlat (40%)

Példa D-S logika

Fuzzy rendszerek

Laborgyakorlatok:

Tört. visszatekintés Fuzzy halmazok

1

Gráfok ábrázolása - dedukciós algoritmus

18%

2

Játékelmélet

10%

3

Matlab - tanulási algoritmus

12%

4

Opcionális feladatok - max. 3/személy

Fuzzy logika Fuzzy szabályok

Bemutatók (5–20 pont) Alkalmazások bemutatása, melyek adaptív, gépi tanulásos vagy mestint módszereket alkalmaznak. 170/363

sok%

Dempster–Schafer modell Mesterséges Intelligencia

8

Bevezeto˝ I

Motiváció: szeretnénk döntéseket hozni akkor is, ha az események valószínuségeit ˝ nem ismerjük.

Csató Lehel D-S modell D-S definíció Példa D-S logika

˝ Például: Pacino-t meggyilkoltatta a maffia. A rendorség a következo˝ tényeket gyujtötte ˝ össze:

Fuzzy rendszerek

három bérgyilkos van: Tom, John, illetve Angie;


a gyilkos kiválasztása a következo˝ volt: ha egy dobás fej, akkor Tom, ellenkezo˝ esetben John vagy Angie;


DNS-vizsgálatok eredménye 80%-ban férfit valószínusít. ˝ Kérdés: Mekkora az egyes személyek bunösségének ˝ a valószínusége? ˝ 171/363


8

Bevezeto˝ II

Nincs megfelelo˝ valószínuségi ˝ modell, mely egyesíteni tudná a két állítást.


Bizonytalanság: A tények ismeretében nem tudunk személyt azonosítani.

Fuzzy rendszerek Tört. visszatekintés Fuzzy halmazok Fuzzy logika Fuzzy szabályok

Ábrázolás: a két tényhalmazt ábrázoljuk mértékekkel (e1 és e2 arányban megbízható információ) : ˝ e1 – m(T ) = e1 · 50% és m(J, A) = e1 · 50% Elso: Második: e2 – m(T, J) = e2 · 80% és m(A) = e2 · 20% Ismerethiány: nem tudunk valószínuségi ˝ modellt építeni, melyben ábrázolhatjuk mindkét forrást. 172/363


8 Csató Lehel

Bevezeto˝ III

Dempster-Schafer modell Egy módja a többféle információ–forrás összetételének.

D-S modell D-S definíció Példa D-S logika

Fuzzy rendszerek Tört. visszatekintés

Amennyiben e1 + e2 = 1 m(T ) + m(J, A) + m(T, J) + m(A) = 1

Fuzzy halmazok Fuzzy logika Fuzzy szabályok

Ha e1 = e2 = 50%, tudjuk a halmazok valószínuségét. ˝ Nem tudjuk a személyek valószínuségeit. ˝ Szeretnénk a fenti információkkal muveleteket ˝ végezni. 173/363


I

Cél: megkülönböztetni

8

a bizonytalanságot (uncertainty) az ismerethiánytól (ignorance).


Egy atomi B esemény valószínuségét ˝ nem ismerjük;


A valószínuség-tábla: ˝ m(T ) 25%

m(J, A) 25%

m(T, J) 40%

m(A) 10%

Például: a fentiek alapján tudjuk, hogy p(T ) ≥ 25%, ugyanakkor p(T ) ≤ 65%. 174/363


8

II

Nyilvántartjuk azt, hogy mennyire támogatunk egy állítást Bel(F);

Csató Lehel

mennyire „esélyes” az állítás Pl(F);

D-S modell

(belief)

(plausibility)



˝ Példa: egy érme szabályossága a vizsgálat elott:

Fuzzy halmazok Fuzzy logika

Bel(F) = 0

Fuzzy szabályok

illetve

Bel(F) = 0

de ha 90%-ban megállapítottuk, hogy szabályos, akkor Bel(F) = 0.5 · 0.9

illetve

Bel(F) = 0.5 · 0.9

A „fennmaradó” 10% a bizonytalanságot tükrözi. 175/363


8

Példa folyt.:

III intervallum-logika

˝ p(F) ∈ [0, 1]; vizsgálat elott:

Csató Lehel

vizsgálat után: p(F) ∈ [0.45, 0.55];


Fuzzy rendszerek

Dempster-Shafer modell: intervallumok kombinálása.

Tört. visszatekintés Fuzzy halmazok Fuzzy logika Fuzzy szabályok

Bayes analógia: alsó- illetve felso˝ korlátai egy esemény valószínuségének. ˝ Segédfüggvények bevezetése: Bel(Ai ) – alsó korlát; Pl(Ai ) – felso˝ korlát; 176/363

Belief Plausibility


8

„Belief” Bel (A1 ∪ A2 ) ≥

Csató Lehel

2 X

D-S modell D-S definíció

Bel(Ai ) − Bel(A1 ∩ A2 )

IV

„Plausibility” Pl (A1 ∩ A2 ) ≤ 2 X

i=1

Példa

Pl(Ai ) − Pl(A1 ∪ A2 )

i=1

D-S logika


A Bel és Pl függvények jellemzése: Egy m : 2Ω → [0, 1] függvény segítségével, melyre X m(∅) = 0 , m(A) = 1 Bel(A) =

X B⊂A

177/363

A∈Ω

m(B) ,

Pl(A) =

X B∩A6=∅

m(B)


Bel(A) =

8

X

m(B) ,

Tulajdonságok X

Pl(A) =

m(B)

B∩A6=∅

B⊂A

Csató Lehel

bármely A halmazra Bel(A) ≤ Pl(A)


B ⊂ A ⇒ B ∩ A 6= ∅

Példa D-S logika

Fuzzy rendszerek

bármely A halmazra Bel(A) = 1 − Pl(A)


B ⊂ A ⇔ B ∩ A 6= ∅


B⊂A ⇔ B∩A=∅

a Bel függvény szubadditív: Bel(A ∪ B) ≤ Bel(A) + Bel(B) C⊂A∧C⊂B ⇒ C⊂A∪B

a Pl függvény szuperadditív: Pl(A ∪ B) ≥ Pl(A) + Pl(B) 178/363

Dempster–Schafer Mesterséges Intelligencia

8

Példa

˝ Jellemezzük az érménket megfigyelés elott: legyen m({F, I}) = 1 és minden másra m(B) = 0;

Csató Lehel

ekkor Bel(F) = m({F}) = 0 és Pl(F) = m({F}) + m({F, I}) = 1.


Fuzzy rendszerek Tört. visszatekintés Fuzzy halmazok

Megfigyelések után:

Fuzzy logika

m({F}) = m({I}) = 0.45 és m({F, I}) = 0.1; – az összeg 1; ezért:

Fuzzy szabályok

1 2

Bel(F) = m({F}) = 0.45, illetve Pl(F) = m({F}) + m({F, I}) = 0.55;

azonosítani tudjuk a „határozatlan” részt: m({F, I}) = 0.1 179/363

Dempster–Schafer modell Logikai muveletek ˝ Mesterséges Intelligencia

8

Logikai muveletek ˝ definíciója: logikai és: Bel(A1 ∧ A2 )

Csató Lehel

X

=

m(B);

B⊂(A1 ∩A2 )

D-S modell

Pl(A1 ∧ A2 )

D-S definíció Példa

X

=

m(B);

B∩(A1 ∩A2 )6=∅

D-S logika

Fuzzy rendszerek

logikai vagy:

Tört. visszatekintés

Bel(A1 ∨ A2 )


X

=

Fuzzy szabályok

m(B);

B⊂(A1 ∪A2 )

Pl(A1 ∨ A2 )

X

=

m(B);

B∩(A1 ∪A2 )6=∅

Általánosított entrópia: AU(Bel) = max − px

180/363

X x∈Ω

! px log px

,

Bel(A) ≤

X x∈A

px


8

Kondicionálás

Feltételes Bel és Pl függvények

Csató Lehel

Amennyiben megfigyelünk egy eseményt, a halmazokhoz rendelt súly változik:


Ha C igaz, akkor csak a C-t tartalmazó halmazok ˝ a C-t töröljük, mint véletlen maradnak, melyekbol eseményt:

Fuzzy rendszerek Tört. visszatekintés Fuzzy halmazok Fuzzy logika

1

Fuzzy szabályok

2

a súlyokat újraszámoljuk; normalizáljuk a rendszert.

Egy más „univerzum” keletkezik. A C nem teljesül, akkor csak C-t nem tartalmazó halmazokat használjuk. 181/363

Dempster–Schafer modell alkalmazása Mesterséges Intelligencia

8

Használják: . . .



www.c3.lanl.gov/~joslyn/ 182/363


Összefoglaló

Konzisztens keretrendszer, mellyel lehet számításokat végezni;


A Bel(·) és Pl(·) függvények definíciója „természetes”;

Példa D-S logika


Könnyu˝ bizonytalanságot rendelni az eseményekhez – ignorancia;


Megfigyelt események kezelése – kondicionálás –nagyon nehéz, újra kell számolni a függvények értelmezési tartományát.

183/363

Fuzzy rendszerek Mesterséges Intelligencia


Bevezeto˝

Döntések bizonytalan helyzetekben – a D.S. rendszerhez hasonlóan akkor, amikor a valószínuség ˝ szabályai nem alkalmazhatóak. Tipikusan:

Példa

„Tények” gyorsan hajtott, magas ember, kb. 180 cm, olajos ruha, . . .

D-S logika


„Szabályok” ha gyorsan hajt és lassan lélegzik akkor lassítson az elektronika . . . Szükség van egy keretrendszerre, mely a fentieket képes programozni:

184/363

1

Szabályokat tudunk megadni;

2

Információt – adatokat – tudunk bevinni;

3

Következtetéseket tudunk levonni ⇒ döntéshozatal;

Bevezeto˝ II


8

Egy fuzzy rendszer építésének logikai sémája:


Megrendelo˝


Fejleszto˝


185/363

Fuzzy Szabályok Fuzzy motor, következtetések

Defuzzyfikálás

XIn

Fuzzyfikálás

Fuzzy szabályok

ZOut

Bevezeto˝ II


8

Egy fuzzy rendszer építésének logikai sémája: ˝ A megrendelo˝ közli a fejlesztovel a

Csató Lehel

változókat szabályokat

D-S modell D-S definíció Példa

a fejleszt o˝ a szabályokat „átírja” a fuzzy logika szerint; Megrendel o˝

D-S logika

Fuzzy rendszerek

˝ ami a a szabályok köré építi a „következtetot”, ˝ Fejleszt o rendszert eredményezi.


185/363

Fuzzy Szabályok Fuzzy motor, következtetések

Defuzzyfikálás

XIn

Fuzzyfikálás

Fuzzy szabályok

ZOut


8 Csató Lehel

Bevezeto˝ III

Egy fuzzy rendszer muködéséhez ˝ Szükségünk van: Keretrendszerre, mely a szabályokat értelmezni tudja;


„Fuzzyfikáló” modulra, mely a megfigyeléseket átalakítja a fuzzy logika nyelvére;

Példa D-S logika


Következteto˝ modulra;


„De-fuzzyfikáló” modulra.

Fuzzy szabályok

Eszköz Fuzzy halmazelmélet; Fuzzy logika. 186/363

Történelmi visszatekinto˝ Mesterséges Intelligencia

8

Fuzzy: homályos, zavaros, bizonytalan, kócos


Fuzzy rendszerek

’65 – Zadeh: „Fuzzy Sets”; ’70 – Fuzzy elmélet robotikai alkalmazása;


’75 – Japán . . . ’80–’95 – Empirikus vizsgálatok és széles köru˝ alkalmazások; ’00–’05 – Technológiai standard,

Lotfi A. Zadeh

Felhasználás: ˝ Ha magas a homérséklet, akkor a nyomás is magas; 187/363

Történelmi visszatekinto˝ Mesterséges Intelligencia

8

Fuzzy: homályos, zavaros, bizonytalan, kócos


Fuzzy rendszerek

’65 – Zadeh: „Fuzzy Sets”; ’70 – Fuzzy elmélet robotikai alkalmazása;


’75 – Japán . . . ’80–’95 – Empirikus vizsgálatok és széles köru˝ alkalmazások; ’00–’05 – Technológiai standard,

Lotfi A. Zadeh

Felhasználás: ˝ Ha magas a homérséklet, akkor a nyomás is magas; 187/363

Fuzzy halmazok Mesterséges Intelligencia

8

Fuzzy halmazelmélet Eszköz annak a leírására, hogy egy objektum milyen mértékben illeszkedik egy bizonytalan tényhez;

Csató Lehel D-S modell

Alkalmas bizonytalan kijelentések formalizálására.


Nem valószínuségi ˝ modell.

D-S logika

Fuzzy rendszerek

Döntések hozatala „igazság-értékek” alapján.


Fuzzy halmazok: nem „teljes” hozzátartozás specifikálása.


188/363

I


8 Csató Lehel

II

Klasszikus logika Fuzzy logika Egy kijelentés igaz: – 1; Egy kijelentés vagy hamis – 0. igazságértéke µ(p) ∈ [0, 1]



Egy A halmazra: 1 ha x ∈ A IA (x) = 0 ha x ∈ /A

µA (x) ∈ [0, 1]

∀x ∈ Ω

Egy halmaz= µA

˝ Például: M – magas homérséklet

µM (t)

µ

189/363

50

60

70

80

˝ T - homérséklet


8

A definíciós intervallumot általában felosztjuk több fuzzy halmazra:


III

Alacsony

Magas

Közepes

1



T


30

40

50

60

70

80

90

100

110

Egy fuzzy halmaz tehát függvény, µK : Ω → [0, 1]:   1 ha x ∈ [50, 70]    (x − 40)/10 ha x ∈ [40, 50] µK (x) =  (90 − x)/20 ha x ∈ [70, 90]    0 ha x ≤ 40 vagy x ≥ 90 190/363

Fuzzy logika Mesterséges Intelligencia

0

˝ A logikai muveletek ˝ halmaz–muveletekre ˝ vezethetok vissza:

8 Csató Lehel

a logikai vagy az egyesítés: A ∨ B def = A∪B

D-S modell

a logikai és a metszet:


A ∧ B def = A∩B

D-S logika

a logikai negáció a komplementer:

Fuzzy rendszerek

A def = Ω\A


A fuzzy logikai muveletek ˝ fuzzy halmazok egyesítése, metszete, illetve komplementere. A három logikai muvelet ˝ redundáns: A∨B=A∧B

⇒

A∨B=A∧B

Csak a konjunkciót és a negációt kell specifikálnunk. 191/363


I

A fuzzy rendszerekben a konjunkciót és a negációt specifikáljuk.

8

A konjunkció egy T-norma:

Csató Lehel

T : [0, 1] × [0, 1] → [0, 1] A T (1, 1) = 1 kivételével minden sarokpontban az értéke 0 kell, hogy legyen (hogy kapjuk vissza a klasszikus logikát). A negáció egy-argumentumú függvény: C : [0, 1] → [0, 1] A sarokfeltételek: C(0) = 1, illetve C(1) = 0.



A diszjunkciót a De-Morgan reláció alapján számoljuk ki (S-konormának nevezzük): S : [0, 1] × [0, 1] → [0, 1]

S(a, b) = C ( T (C(a), C(b)) ) 192/363


8

II

Példa: A konjunkciónak megfelelo˝ T-norma: T (a, b) = min(a, b) T (0, 0) = T (0, 1) = T (1, 0) = 0, illetve T (1, 1) = 1.

Csató Lehel D-S modell D-S definíció Példa

A negáció legyen:

D-S logika

Fuzzy rendszerek

C(x) = 1 − x

Tört. visszatekintés

C(1) = 0, illetve C(0) = 1.


A diszjunkció meghatározása: S(a, b) = 1 − T (1 − a, 1 − b) S(a, b) = 1 − T (1 − a, 1 − b) = 1 − min(1 − a, 1 − b) = 1 + max(−1 + a, −1 + b) = max(1 − 1 + a, 1 − 1 + b) = max(a, b)

193/363


8

Logikai szabályok: µA∧B (x) = min [µA (x), µB (x)]

Csató Lehel

µA∨B (x) = max [µA (x), µB (x)]


µA (x) = 1 − µA (x)

Példa D-S logika


194/363

III


8 Csató Lehel D-S modell

IV

Logikai szabályok: a, b ∈ {0, 1} ÉS = 1 csak ha a = 1 és b = 1 VAGY = 0 csak ha a = 0 és b = 0 Alternatív formák:


µA∧B (x) = µA (x) · µB (x) ,

D-S logika

Fuzzy rendszerek

µA (x) = 1 − µA (x)

µA∨B (x) = µA (x) + µB (x) − µA (x) · µB (x)


195/363


8 Csató Lehel D-S modell D-S definíció Példa D-S logika


-!-

Fuzzy logika inkonzisztens x vagy A-nak vagy A-nak eleme, azaz µA∩A = 1.   1 µA∨A (x) = max [µA (x), 1 − µA (x)]   1 − µA (x) [1 − µA (x)]

klasszikusan fuzzy logika 1 def. fuzzy logika 2 def.


Ugyanígy: szeretnénk, hogy µA∧A = 0. Helyette:   0 µA∧A (x) = min [µA (x), 1 − µA (x)]   µA (x) [1 − µA (x)]

klasszikusan fuzzy logika 1 def. fuzzy logika 2 def.

vizsga feladattípus: határozzuk meg a „modus ponens” szabály fuzzy változatát. 196/363


8

Feladat I

A negációt szeretnénk úgy meghatározni, hogy legyen folytonos, bijektív;

Csató Lehel

teljesüljön a negált negáltja önmaga, azaz C(C(x)) = x

D-S modell D-S definíció Példa

legyen C(0) = 1 és C(1) = 0

D-S logika

Fuzzy rendszerek Tört. visszatekintés Fuzzy halmazok Fuzzy logika

A C(x) bijektív, alkalmazva a z = C(x) ⇔ x = C−1 (x):

Fuzzy szabályok

C(z) = C−1 (z) ˝ azaz a C(·) függvény a foátló szerint szimmetrikus. A C(x) = 1 − x egy megoldás. Egy megoldás-család – pozitív q értékekre – a Cq (x) = 197/363

√ q

1 − xq


8

A Cq (x) = értékekre:

√ q

Feladat II

1 − xq grafikus képei a q = {1/3, 1/2, 1, 2, 3}

Csató Lehel D-S modell D-S definíció

C(x)

Példa D-S logika


.8


.6 .4 .2 x .2 198/363

.4

.6

.8

Fuzzy szabályok Mesterséges Intelligencia

Értheto˝ formában írják le egy rendszer muködését: ˝

8 Csató Lehel

Könnyu˝ megfogalmazni;

D-S modell

˝ ˝ Könnyen ellenorizhet o;


Módosításokhoz nem kell az egész rendszert átírni.


Használják a fuzzy logika következtetési mechanizmusait;


Logikai szabályok alapján; Fuzzy változók értékeit számolják; De-fuzzyfikálás után az eredmény jó kontroll-változó.

199/363

0


8

I

Példa: ˝ Ha magas a homérséklet, akkor a nyomás is magas;


Fuzzy rendszerek

Fuzzy h szabályok: i HA X alacsony ÉS Y magas AKKOR Z közepes


Definiáljuk az alacsony, magas és közepes halmazokat: µ

µalacsony

50 200/363

µkozepes

60

70

µmagas




Fuzzy rendszerek

Fuzzy szabályok: X Alacsony Alacsony – Közepes – Magas Közepes


II

Y Közepes Magas Közepes Alacsony Magas Közepes Magas Alacsony – nem megengedett állapot


Szabályok alkalmazása: Megfigyelt értékek:

x = 50, y = 78.75

Fuzzyfikálás – fuzzy halmazokra való áttérés: X szerint csak az Alacsony csoportot kell vizsgálni. Y szerint a Közepes és Magas csoportokat. 201/363

Fuzzy szabályok

III

Mesterséges Intelligencia

8 µmag (y) = 0.75;

Csató Lehel

µal (x) = 1 illetve

µkoz (y) = 0.25;



Kombinálás: VAGY= max

µ


µz 50

60

70

Kontroll esetén Egy érték kiírása: súlyozott közép Z = 53. 202/363


Fuzzy rendszer Mesterséges Intelligencia

8 Csató Lehel

–I–

Alkalmazás

Mitsubishi légkondicionáló rendszer Ipari légkondicionáló mely rugalmasan reagál a környezeti változásokra.


Megvalósítás:

Fuzzy rendszerek

50 fuzzy szabály


6 nyelvi változó, közöttük a szoba és a fal ˝ ˝ homérséklete, illetve ezek idobeli változásai;

Fuzzy szabályok

4 nap – prototípus; 20 nap – teszt/integrálás; 80 nap – tesztelés; ⇒ mikrokontroller implementálás. ˝ Elonyök: kevesebb szenzor, változó környezet, 24%-kal kisebb fogyasztás; 203/363

Fuzzy rendszer Mesterséges Intelligencia



– II –

Alkalmazás

Alkalmazások: ˝ uvek Erom ˝ kontrollja (Tokio); Egyszerusített ˝ robot-kontroll (Fuji, Toshiba, Omron); ˝ Fényképezogép automata irányítása (Omron); Motor-fogyasztás, irányítás (Nissan,Subaru);


Gyártósorok szilícium-lapkáinak vágása (Canon); Rák diagnózis (Kawasaki Med. School); Jogi eljárások szimulációja (Meihi Gakuin Univ, Nagoya Univ.) . . . Matsushita, Sony, Canon, Minolta, Sanyo, Hitachi, Ricoh, Fujitech, Toshiba, . . . . http://www.esru.strath.ac.uk/Reference/concepts/fuzzy/fuzzy_appl.00.htm 204/363


8

Összefoglaló

Fuzzy rendszerek: ˝ Foként kontroll feladatokra használjuk. Ajánlottak ha:


komplex rendszerek esetén, nincs matematikai modell; nemlineáris modellek esetén; ˝ tudás bevitelére. szakértoi



Nem ajánlottak ha:


˝ hagyományos kontroll megfelelo; létezo˝ – egyszeru˝ – matematikai modell; nincs megoldás.

Más alkalmazások: Sony PalmTop – „fuzzy” döntési fa implementálása karakterfelismerésre (Kanji). 205/363

363

Recommend Documents