A nyomtatható változat már nem támogatott, és hibásan jelenhet meg. Kérjük, frissítsd a böngésződ könyvjelzőit, és használd a böngésző alapértelmezett nyomtatás funkcióját.

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

Erre a szekcióra ráférne egy alapos formázás!

About: Vizsgakérdések és többségükhöz válaszok a 2005 öszi félévig összegyűjtve, tematizálva (amennyire tudtam). Ha egy kérdés alatt „I”-k vannak, azt jelöli, hányszor fordult elő.

III 1. Mi a hozzáférhető illetve a nem hozzáférhető környezet ? _ Egy környezet hozzáférhető, ha az ágens szenzoraival minden olyan információt szerez a környezetről és a környezetre kifejtett hatásáról, amely az adott probléma reprezentálása és megoldása szempontjából feltétlenül szükséges. Következik belőle, hogy a hozzáférhetőség problémafüggő és relatív._

II 1. Mi a nem hozzáférhető környezet, és miért jelent ez nehézséget az ágens számára? Milyen módszerekkel védekezhet egy ilyen környezettel szemben egy intelligens ágens? (3 pont)

II 1. Racionális viselkedés szempontjából mit jelent a cél ? _ A kívánatos, hasznos, stb. környezet + ágens állapotot, amire az ágens a környezetet a cselekvéseivel formálva törekszik._

1. A környezet milyen tulajdonságairól lehet beszélni és mely tulajdonságok problémát jelentenek az ágens számára és miért? (3 pont) Hozzáférhetőség, determinizmus, epizódszerűség, dinamizmus, folytonosság

1. Milyen tulajdonságokkal rendelkezik egy racionális ágens rendszer ? (3 pont)

1. Hogyan működik egy keresőtábla vezérelt ágens (felépítés, működési ciklus)? (3 pont) Érzékelők, Feltételes cselekvési szabályok (tábla), Beavatkozók

2. A reflex ágens egy olyan ágens, amelynek cselekvései mindig a pillanatnyi érzeteinek a függvénye. A Wumpus világban 32 különböző érzet létezik és 6 különböző cselekvés.

Hány különböző reflex ágens definiálható a Wumpus világban?
Hány különböző 4x4-es Wumpus világ létezik? Hány 10x10-es?

a. 32 érzékelés, mindegyik esetben 6 cselekvés alapján: 32 érzékelés úgy jön össze, hogy : 4 x 4 négyzeten lehet bűz és szellő, vagy arany csillogása, azaz: 16 x 2 = 32

(es ha ugy jonne ossze a 32 erzet, hogy buz, szello, utes, sikoly es utes van/nincs, azaz 2^5=32? szerintem igy ertelmesebb. -- yanq - 2006.01.26.)

mindegyik érzékelés esetén lehet: előre, hátra, balra, jobbra, lő, vagy megfog, azaz 6 cselekvés, összesen 6³²kombináció és annyi különböző reflexszerű ágens is.

(szerintem 32^6 db, mert minden egyes erzetre mindig ugyanazt csinalja a hat lehetoseg kozul -- yanq - 2006.01.26.)

b. Egy Wumpus világ azzal jellemezhető, hogy hol van az arany és hol van a Wumpus, azontúl van-e csapda az adott négyzetben (a csapdák száma nincs korlátozva): _ 16 x 16 x 2¹⁶ $\simeq$ 2 x 10^7_ _ 10 x10 Wumpus világ esetén, viszont: 100 x 100 x 2¹⁰⁰ $\simeq$ 10^34_

Keresés

3. Foglalja össze táblázatosan a megismert keresési módszerek tulajdonságait! Azonosítsa a gyakorlatban használható módszereket!

III 2. A keresési stratégiák elemzésénél használt kritériumok közül melyik a legfontosabb (miért)? A teljesség. Mivel egy keresésnél a legfontosabb, hogy biztosan megtaláljuk a megoldást.

1. Mi a mélységi/szélességi keresés alapvetően a legjobb illetve a legrosszabb tulajdonsága? Mélységi keresés esetén legjobb a lineáris tárkomplexitása, a legrosszabb a teljesség hiánya, szélességi keresésnél a teljesség és az exponenciális tár.

III 1. Tegyük fel, hogy egy mohó keresési algoritmust futtatunk h(n) = g(n)-nel. Milyen keresési algoritmust emulál ebben az esetben a mohó keresési algoritmus ? Szélességi, hiszen a mélység mentén ’nő’ legjobban a h. az algoritmus így minden megpróbál mielőtt mélyebbre merészkedne.

1. Tegyük fel, hogy egy mohó keresési algoritmust futtatunk h(n) = -g(n)-nel. Milyen keresési algoritmust emulál ebben az esetben a mohó keresési algoritmus ?

Mivel a g(n) pozitív értékeket vesz fel, az algoritmus mélységi, hiszen a mélységi ág mentén ’fogy’ legjobban a h és a heurisztika tesztje annál inkább fogja ezt az ágat tovább preferálni.

II 3. Hogyan működik az iteratív mélyülő keresés ? Mik a jó tulajdonságai és mivel magyarázhatók meg? (4 pont) Mélységkorlátozott keresésnél a mélységkorlát megválasztása a legnehezebb. Az iteratívan mélyülő keresés megkerüli ezt a problémát mivel vegigprobálgatja az összes megoldást. Valójában ötvözi a szélességi és a mélységi keresés jó tulajdonságait.Szélességi kereséshez hasonlóan optimális és teljes, viszont a mélységi keresés kis memóriaigényével rendelkezik

III 2. Mivé fajul és miért a g=1 és h=0 heurisztikával dolgozó A* keresés ? A szélességi kereséssé, hiszen minden olyan csomópontot fejt ki legelőször, melynek távolsága a gyökértől a legkisebb (a g-k összege itt gyökér-csomópont távolságot fog jelenteni).

1. - 3. Tekintse meg a következő láncot:

_ _mélységi keresés $\Rightarrow$ hegymászó keresés $\Rightarrow$ legjobbat-először keresés $\Rightarrow$ A keresés. Egy-egy nyíl milyen lényegi újításnak felel meg és az algoritmus milyen tulajdonságát befolyásolta a leginkább? (4 pont) 1 – a heurisztika bevezetése, amivel a keresés célszerűbben választja meg (h alapján) a további haladási irányt és szerencsével (szub)optimális megoldáshoz is juthat el. _2 – a visszalépés lehetősége, amitől kivédjük a keresést, hogy a lokális minimum helyén (vagy hasonló rossz helyzetben) megrekedjen. Megjelenik a teljesség._ 3 – Az útköltség figyelembevétele kirekeszti a mohóságot és biztosítja az optimálitást is.

2. Mohó-e az A keresési algoritmus ? A válaszát feltétlenül indokolja meg ! (2 pont) Nem, mert biztosítva van a visszalépés lehetősége.

2. Milyen heurisztikát nevezzünk elfogadhatónak ? (2 pont) _Ha h(n) elfogadható akkor f(n) soha sem becsüli túl az n csomóponton keresztül vezető legjobb megoldás valódi költségét. _

4. Mi az Ún. effektív elágazási tényező? Mire szolgál? (3 pont) Átlagosan egy csomópontból kiindulva hány utat fejt ki. Jól mutatja a heurisztikus függvény használhatóságát. A jó heurisztikus függvény esetén az egyet közelíti.

4. Miért törekszünk az elfogadható heurisztikus függvény használatára? Mert biztosítja az (A) algoritmus kedvező elvi tulajdonságait: teljesség, optimalitás, optimálisan hatékony

II 6. Magyarázza meg, hogyan lehet heurisztikákat kinyerni problémák relaxálásával! Az olyan problémát, amelyben az operátorokra kevesebb megkötést teszünk, mint az eredeti problémában, relaxált problémának nevezzük. Nagyon gyakran teljesül, hogy a relaxált probléma pontos megoldásának költsége jó heurisztikus függvénynek bizonyul az eredeti problémára.

2. Mi az un. keresési/probléma/állapottér és hogyan keletkezik? A probléma olyan absztrakt ábrázolása, ahol közös formalizmusban ábrázoljuk a probléma kezdeti és vég állapotát és minden közbülső megoldást is. Az ilyen ábrázolás lehetőséget nyújt a probléma megoldását a térbeni mozgással – kereséssel – megkísérelni.

5. Hogyan működik az iteratív A^keresés? Mit nyerünk az ilyen megoldáson? Mélységkorlátozott keresés f-költségkorláttal, mélységi jellege miatt csak a leghosszabb felderített út hosszával arányos memóriát igényel.

4. Mi a hegymászó keresés tipikus problémái? (2 pont) _- lokális maximumok a globális maximumhoz viszonyítva olyan csúcs ami alacsonyabb az állapottér legmagasabb csúcsánál. Ha elér ide akkor megáll azt jó megszívja _ _- fennsík egy olyan terület, ahol a kiértékelhető függvény gyakorlatilag lapos. Azt ekkor meg lépked ide oda, vagy leáll _ - hegygerincek oldalai meredekek lehetnek és lehet hogy a keresés oszcillal a hegykerinc két csúcsa között és csak lassan halad előre

1. Mi történik és miért (milyen mechanizmus révén) a memória korlátos A (EMA) keresési algoritmus esetén, ha a legrövidebb megoldási pálya eltárolásához a rendelkezésre álló memória nem bizonyul elegendőnek? _ Az algoritmus addig halad a szokásos medrében (részfák kifejtése, ha elfogy a memória, akkor a pillanatnyilag legrosszabb részfák törlése, a költségük a gyökérnél való feljegyzésével), amíg a memóriakorlátba éppen akkor ütközik, amikor a memóriában a megoldást tartalmazó legjobb részfa van jelen. Tovább kifejteni a fát a helyhiány miatt nem tudja, törölni sem, mert nincs nála rosszabb._

3. Athéni metróval Sepoliától Dafniig utat tervezünk egyenletes költségű kereséssel. Keramikos-Pentagono vonalon egy-egy útszakasz operátor költsége 3, Sepolia-Dafni vonalon 2 és Kifissia- Pireas vonalon 1. Számozza be az állomásokat a kifejtés sorrendjében! Mennyi a keresés hozzávetőleges effektív elágazási tényezője? Elfogadható heurisztika lenne a két állomás között a minimális számú állomást számláló út állomásszáma?

A feladatban minden állomásnak (csomópontnak) van elérési költsége, ami a hozzá vezető legolcsóbb út költsége. Az egyenletes költségű keresés az így minősített csomópontok között mindig az legolcsóbbakat vizsgálja meg először (ha a költésgek mind 1 lennlnek, akkor ez szélességi keresés lenne). A sorrend tehát nagyjából az alábbi, egy-egy megoldásban különbségek lehetnek (elfogadhatók) az azonos érteket felmutató állomások (fennsík) tekintetében

Sepolia 0

Attiki 2 _A.G. Nikolaos 3_ Victoria 3 _Larissa 4_ Kato Patissia 4 _Omonia 4_ _A.G. Eleftherios 5 _ Monastiriki 5 _Deligianni 6_ Ano Patissia 6 _Thissio 6_ Akademia 6 _Perissos 7_ Petralona 7 _Syntagma 8_ Keramikos 8 _Petkala 8_ Tavros 8 _Nea Ionia 9_ Kallithea 9 _Olympion 10_ Iraklio 10 _Moschato 10_ Evangelismos 11 Irini 11 Faliro 11 Neos Kosmos 12 _Maroussi 12_ Pireas 12 _Kat 13_ Megaro Moussikis 14 _Analatos 14_ Kifissia 14 _A.G. Ioannis 16_ Ambelokipi 17 _Dafni 18_ _ _ Megoldás d=10 szinten található, a keresés 3 állomás hián mindenhová ellátogat, azaz N=40-3=37. _Belőle az effetktív elágazási tényező 1 és 2 között van (pontosabban b =1.225). _ Heurisztika tekintetében a válasz igen, hiszen nem létezik a hálózatban olyan út, amely két állomás között kisebb számú állomás éríntésével oldaná meg az áthaladást.

1*.

Egy ágens S-től C-ig keres egy optimális utat iteratív A* algoritmussal, rendre: 11.5, 12.5,  13.5, 14.5 mélységi határokkal, az ábrára nézve balról-jobbra.A heurisztika függvény értékei:

h(S) = 11 h(a) = 13 h(b) = 15 h(c) = 8 h(d) = 11 h(e) = 10 h(f) = 9 h(g) = 9 h(h) = 6 h(i) = 6 h(j) = 3 h(C) = 0

az operátorköltség lépésenként az ábrán látható. Ábrázoljuk a grafban a mélységi határok határvonalát (4 pont)! Hány csomópont *f* értékét számítja ki az algoritmus a megoldás megtalálása előtt? (3 pont) Mennyi a keresés hozzávetőleges b* effetktív elágazási tényezője? (4 pont)

_Az f = 11.5 konturon belül S, c _ f = 12.5 -/- S, c, d, i _f = 13.5 -/- S, c, d, i, e, f, j_ f = 14.5 -/- minden, kivéve b _csomópontok helyezkednek. A keresés konturon belül balról-jobbra haladó mélységi keresés, azaz (a / jel utáni csomópontok már a konturon túl vannak, így tovább foglalkozni velük nem kell):_ az f = 11,5 konturon belül és annak határán a keresés _ S –követői: c d /a , majd_ _ c –követői: /i csomópontokat néz végig (5 csp.)_ az f = 12,5 konturon belül és annak határán a keresés _ S –követőti: c d /a , majd_ _ c –követői: i _ i –követői: /j h _d –követői: /e csomópontokat néz végig (8 csp.)_ az f = 13,5 konturon belül és annak határán a keresés _ S –követőti: c d /a , majd_ _ c –követői: i _ i –követői: j /h _j –követői: /C_ d –követői: e _e –követői: f_ f –követői: /g csomópontokat néz végig (11 csp.) nincs több csomópont, ami f=14 értéknél jobban állna és megoldás lenne, azaz a C az optimális megoldás, nincs mit tovább keresni. _Az algoritmus tehát összesen N = 5 + 8 + 11 = 24 csomópontot nézett meg és a megoldást d = 4 szinten találta meg. A b* effektív elágazási tényező: 1 + b* + (b*)² + (b*)³+ (b*)⁴= N = 24_ Figyelembe véve, hogy: 2⁵-1 = 1 + 2 + 2³ + 2⁴= 31 $\simeq$ 30, a b* effektív elágazási tényező értéke kisebb, mint 2, kb. 1.85.

1*. Egy ágens a szürke csomóponttól az elsőnek elérhető fekete csomópontig keresi az utat, az iteratívan mélyülő algoritmust felhasználva, balról jobbra bejárással. Hány csomópontot számít ki (elvégzi rajta a célállapot tesztet) az első cél megtalálása előtt? (3 pont) Hány csomópontot tudnia kell eltárolni egyszerre a memóriában? (2 pont) Mennyi a keresés hozzávetőleges b* effektív elágazási tényezője? (3 pont)

A 0-ik iterációban: 1 csomópontot vizsgál, _ 1-ik 1 + 4 = 5 - / -,_ _ 2-ik 1 + 4 + 12 = 17 - / -,_ _ 3-ik 1 + 4 + 17 = 22 - / -._ Összesen 45 csomópont, d = 3, 1 + b + b² + b³ = 45. Tekintettel, hogy 1 + 3 + 9 + 27 = 40, a b kissé nagyobb, mint 3. A memóriában egyszerre legfeljebb 10 csomópontot kell eltárolni (a gyökeret, a 4 gyerekét, a baloldali gyerekének 3 gyerekét és még a legbaloldalibb gyerek-gyerekének 2 utódját = 10).

Logika

II 3. Jellemezze röviden a következtetési tudás mindhárom fajtáját, azaz a deduktív, abduktív és induktív következtetést ! (séma, alkalmazhatóság, miért, mire való) _ Az abdukció: ((A $\Rightarrow$ B) $\wedge$ B) $\Rightarrow$ A_ Nem formális, de hasznos, mert kauzális szabályok esetén a diagnosztikai következtetést modellezi. _ A dedukció: pl. Modus Ponens ((A $\Rightarrow$ B) $\wedge$ A) $\Rightarrow$ B_ Formális bizonyítási lépés, tehát minden körülmények között jogosan alkalmazható. _ Az indukció: pl. predikatum(obj1), predikatum(obj2), predikatum(obj3), … alapján_ _ $\forall$ x predikatum(x)_ Nem formális, de komplexitás (tár és idő) redukáló hatású. Indukció a tanulás egyik fajtája is (általánosítás = absztrakció képzés példák alapján).

5. Miért, mikor hasznos a deduktív, az abduktív és az induktív következtetéstési tudás? (5 pont) A világról nem áll mindig rendelkezésre az összes információ, tapasztalat alapján hasznos lehet általánosítani (+ helytakarékosság)

III 3. Mutassa ki igazságtáblával, hogy az abdukció nem egy deduktív eljárás.

_ A B ((A $\Rightarrow$ B) $\wedge$ B) $\Rightarrow$ A

_Hamis_	_Hamis_	_Igaz_
_Hamis_	_Igaz_	_Hamis $\Leftarrow$ itt a bűnős_
_Igaz_	_Hamis_	_Igaz_
_Igaz_	_Igaz_	_Igaz_

III 13. Lássa be az igazságtábla módszerével, hogy az un. Modus Tolens lépés egy formális bizonyító lépés! (4 pont) _A $\Rightarrow$ B _ _ === $\neg$ B=== $\neg$ A_ _ ((A $\Rightarrow$ B) $\wedge$ $\neg$ B) $\Rightarrow$ $\neg$ A_ _A $\neg$ A B $\neg$ B A $\Rightarrow$ B (A $\Rightarrow$ B) $\wedge$ $\neg$ B ((A $\Rightarrow$ B) $\wedge$ $\neg$ B) $\Rightarrow$ $\neg$ A

_0_	_1_	_0_	_1_	_1_	_1_	_1_
_0_	_1_	_1_	_0_	_1_	_0_	_1_
_1_	_0_	_0_	_1_	_0_	_0_	_1_
_1_	_0_	_1_	_0_	_1_	_0_	_1_

7. Mi a teljesség ? Mikor egy következtetési eljárás teljes ? Teljes egy (logikai) rendszer, ha minden igaz állítás bizonyítható benne, és a következtetési eljárás teljes, ha ezt biztosítja.

8. Mit jelent, hogy egy logika eldönthetõ, és mit az, hogy teljes ? Milyenek ilyen szempontból az elsõrendû logika tulajdonságai ? _Eldönthető: Kimutatható, hogy egy állítás értéke hamis, vagy igaz (az algoritmus mindig lefut) _ Teljes: Minden megoldást megtalál _(elsőrendű log. – teljes, félig eldönthető, azaz a hamis álltásról nem mindig látható be, hogy hamis)_

8. Mi egy érvényes állítás? Mire jók az ilyen állítások? Egy állítás érvényes, ha minden interpretációban, a világ minden állapotában igaz (magyarán, ha igaz attól függetlenül, hogy a benne szereplő szimbólumoknak mi a szándékolt jelentése). _Pl. $\neg$ A $\vee$ A (tautológia)_

8. Mikor mondjuk, hogy egy állítás kielégíthető ? Adjon rá példát. Egy állítás kielégíthető, ha létezik valamely interpretációja, amely valamely világban igaz. Egyébként kielégíthetetlen. _Pl. A $\vee$ B_

8. Mikor kielégíthetetlen egy állítás ? Adjon rá példát. Egy állítás kielégíthetetlen, ha minden interpretációban, a világ minden állapotában hamis, vagyis, ha nem létezik olyan világ, amelyben valamely interpretációja igaz lenne. _Pl. $\neg$ A $\wedge$ A_

Reprezentálja a „Minden magyar azonos nyelvet beszél” mondatot predikátum kalkulusban. Használja a Beszél(x, l) predikátumot, amely jelentése az, hogy _x_ az _l_ nyelvet beszéli. Pl. így: _ $\forall$ x,y,l Magyar(x) $\wedge$ Magyar(y) $\wedge$ Beszél(x,l) $\Rightarrow$ Beszel(y,l)_ hiszen ha páronként, akkor mindenki.

Használjon igazságtáblát annak megmutatására, hogy a következő mondat érvényes-e: (F $\Rightarrow$ T) $\Rightarrow$ ( $\neg$ F $\Rightarrow$ $\neg$ T) Megoldás:

_F T (F $\Rightarrow$ T) ( $\neg$ F $\Rightarrow$ $\neg$ T ) (F $\Rightarrow$ T) $\Rightarrow$ ( $\neg$ F $\Rightarrow$ $\neg$ T))_

H H I I I _H I I H H nem mindenhol I, tehát_ I H H I I nem érvényes _I I I I I_

2. Használjon igazságtáblát annak megmutatására, hogy a következő mondat érvényes-e: (F $\Rightarrow$ T) $\Rightarrow$ ((F $\wedge$ H) $\Rightarrow$ T)

Megoldás:

_F T H (F $\Rightarrow$ T) ((F $\wedge$ H) $\Rightarrow$ T) (F $\Rightarrow$ T) $\Rightarrow$ ((F $\wedge$ H) $\Rightarrow$ T)_

H H H I I I _H H I I I I_ H I H I I I _H I I I I I_ I H H H I I _I H I H H I_ I I H I I I _I I I I I I mindenhol I, tehát érvényes_

7. Fűzzön kommentárt az alábbiakhoz: Szabály: Ha valaki beteg, nem megy előadásra. Tény: Béla nem megy előadásra. Konklúzió: Béla beteg.

_A feladvány formális átírása: _ $\forall$ x Beteg(x) $\Rightarrow$ NemMegy(x

_ NemMegy(Béla_

Beteg(Béla) _azaz egy abduktív lépés (tehát formálisan nem igaz, de azért hasznos, ha pl. kellően jóhiszeműek vagyunk Béla iránt)._

II 6. Állít-e a következő mondat valamit az aritmetikáról vagy az időjárásról, vagy egyikről sem: „Vagy 2+2=4 és esik, vagy 2+2=4 és nem esik“. Indokolja meg véleményét !

Legyen *A* a „*2+2=4*” és *B* az „*esik*” ítéletállítás, akkor az összetett állítás nem más, mint: _*(A $\wedge$ B) $\vee$ (A $\wedge$ $\neg$ B) = A*_ Azaz a mondanivaló az, hogy 2+2=4, végül is csakis az aritmetikáról nyilatkozunk.

115. Milyen gyakorlati nehézségek vannak a logikai bizonyítás gépi megvalósításával ? Probléma, hogy sok állítás nem konvertálható Horn klóz alakba.

Klóz forma

III 2. Sorolja fel a klóz formára való átalakítás lépéseit. Kísérelje meg elemezni, hogy az első két lépés miért olyan, amilyen? Implikációt eltüntetni: A $\Rightarrow$ B = $\neg$ A $\vee$ B Negálást az atomi formulák szintjére áthelyezni:_ $\neg$ (A $\vee$ B) = $\neg$ A $\wedge$ $\neg$ B_ Egzisztenciális kvantorokat eltüntetni, Skolemizálás $\forall$ x Személy(x)  $\exists$ y Sziv(y) $\wedge$ Birtokol(x,y) _ $\forall$ x Személy(x)  Sziv(H) $\wedge$ Birtokol(x,H)_ $\forall$ x Személy(x)  $\exists$ y Sziv(F(x)) $\wedge$ Birtokol(x,F(x)) Ha szükséges a változókat átnevezni: $\forall$ xP(x) $\vee$ $\forall$ xQ(x)  $\forall$ xP(x) $\vee$ $\forall$ yQ(y) Univerzális kvantorokat balra kihelyezni: …. $\forall$ x… $\forall$ y….= $\forall$ x $\forall$ y….x…..y Diszjunkciókat literál szintjére áthelyezni: (A_ $\wedge$ B) $\vee$ C = (A $\vee$ C) $\wedge$ (B $\vee$ _C) ez a CNF Konjukciókat eltüntetni (bontás diszjunktív klózokra) Ha szükséges változókat átnevezni Univerzális kvantorokat elhagyni CNF formát kapunk

Az első lépés az implikáció átalakítása, hogy az állítás ne tartalmazzon redundáns logikai operátorokat. A másik a negálás atomi szintre való hozása, hogy pontosan tudjuk, hogy melyik kvantor milyen jellegű (egzisztenciális, vagy univerzális) és a ’vagy’ és az ’és’ operátorok mi a kölcsönös viszonya a további átalakításokhoz.

II 4. Mi történik a konjunkcióval a klóz formára történő áttéréskor ? A konjunkciók (azaz az „ÉS” műveletek) az „ÉS eliminálása” deduktív lépéssel „eltűnnek”, és a klóz több kisebb önálló klózzá esik szét (amikben az „ÉS” már nem szerepel). _Megjegyzés: A klózban tehát az „ÉS”-nek nincs helye. Az „ÉS” eltűnése egy szimbólikus átalakítás, mert a keletkező klózhalmaz egyidejű felirása implicit módon tartalmazza az „ÉS”-t._

3. Írjuk át az alábbi mondatokat predikátum kalkulus állításaira, majd klóz formára, és bizonyítsuk be rezolúciós bizonyítással a kérdéses állítást ! Figyelem: ha a predikátumnevek adott megválasztása mellett a bizonyítással gond van, kíséreljék meg a feladatot más, de jellegre helyes predikátumok felhasználásával a logikai szinten átfogalmazni !(8 pont)

_ János csak könnyû tárgyakat kedvel._ _ Matematikai tárgyak nehezek._ _ A Kísérleti Kémia Tanszék tárgyai könnyûek._ _ "A kén vegyületei" a Kísérleti Kémia Tanszék egyik tárgya._ _ Milyen tárgyat kedvelne János ?_

Egy lehetséges átírás: _ $\forall$ x Könnyű(x) $\Rightarrow$ Kedvel(János, x)_ _ $\forall$ x Matematikai(x) $\Rightarrow$ $\neg$ Könnyű(x)_ _ $\forall$ x KísérletiKémiaTanszék(x) $\Rightarrow$ Könnyű(x)_ _ KísérletiKémiaTanszék(A-kén-vegyületei)_ _ $\exists$ x Kedvel(János, x)_ Klózok a. $\neg$ Könnyű(x1) $\vee$ Kedvel(János, x1) _b. $\neg$ Matematikai(x2) $\vee$ $\neg$ Könnyű(x2)_ c. $\neg$ KísérletiKémiaTanszék(x3) $\vee$ Könnyű(x3) _d. KísérletiKémiaTanszék(A-kén-vegyületei)_ e. $\neg$ Kedvel(János, x4) Rezolúció: f. a+e: x1/x4 $\neg$ Könnyű(x4) g. f+c: x3/x4 $\neg$ KísérletiKémiaTanszék(x4) h: g+d: x4/_ A-kén-vegyületei_ 

A válasz a behelyettesítésből: János a _"A kén vegyületei" _tárgyat kedveli.

2. Alakítsa át klózzá (5 pont): * $\forall$ x $\exists$ y $\neg$ ((Piros(x) $\vee$ Zöld(x) $\vee$ Sárga(x)) $\wedge$ Színe(x,y))*

$\forall$ x $\exists$ y $\neg$ ((Piros(x) $\vee$ Zöld(x) $\vee$ Sárga(x)) $\wedge$ Színe(x,y)) _Először a negálás literál szintre való hozása következik:_ _ $\forall$ x $\exists$ y ( $\neg$ (Piros(x) $\vee$ Zöld(x) $\vee$ Sárga(x)) $\vee$ $\neg$ Színe(x,y))_ _ $\forall$ x $\exists$ y (( $\neg$ Piros(x) $\wedge$ $\neg$ Zöld(x) $\wedge$ $\neg$ Sárga(x)) $\vee$ $\neg$ Színe(x,y))_ Most skolemizálunk: _ $\forall$ x (( $\neg$ Piros(x) $\wedge$ $\neg$ Zöld(x) $\wedge$ $\neg$ Sárga(x)) $\vee$ $\neg$ Színe(x,f(x)))_ és elhagyjuk az univerzális kvantort: _( $\neg$ Piros(x) $\wedge$ $\neg$ Zöld(x) $\wedge$ $\neg$ Sárga(x)) $\vee$ $\neg$ Színe(x,f(x))_ Átalakítjuk diszjunkciók konjunkciójává: _( $\neg$ Piros(x) $\vee$ $\neg$ Színe(x,f(x)) $\wedge$ ( $\neg$ Zöld(x) $\vee$ $\neg$ Színe(x,f(x)) $\wedge$ ( $\neg$ Sárga(x) $\vee$ $\neg$ Színe(x,f(x))_ és eltüntetjük a konjunkciókat. A 3 eredményklózban átnevezzük a változókat: _ $\neg$ Piros(x1) $\vee$ $\neg$ Színe(x1,f(x1)_ $\neg$ Zöld(x2) $\vee$ $\neg$ Színe(x2,f(x2) _ $\neg$ Sárga(x3) $\vee$ $\neg$ Színe(x3,f(x3)_

2*. Alakítsa át klózzá (5 pont): $\forall$ x $\exists$ y ( ( A(x,y) $\Rightarrow$ B(x,y) ) $\wedge$ C(y) ) $\Rightarrow$ D(x,y)

$\forall$ x $\exists$ y ( ( A(x,y) $\Rightarrow$ B(x,y) ) $\wedge$ C(y) ) $\Rightarrow$ D(x,y) $\forall$ x $\exists$ y $\neg$ ( ( A(x,y) $\Rightarrow$ B(x,y) ) $\wedge$ C(y) ) $\vee$ D(x,y) $\forall$ x $\exists$ y $\neg$ (A(x,y) $\Rightarrow$ B(x,y)) $\vee$ $\neg$ C(y) $\vee$ D(x,y) $\forall$ x $\exists$ y $\neg$ ( $\neg$ A(x,y) $\vee$ B(x,y)) $\vee$ $\neg$ C(y) $\vee$ D(x,y) $\forall$ x $\exists$ y (A(x,y) $\wedge$ $\neg$ B(x,y)) $\vee$ $\neg$ C(y) $\vee$ D(x,y) $\forall$ x (A(x,f(x)) $\wedge$ $\neg$ B(x, f(x))) $\vee$ $\neg$ C(f(x)) $\vee$ D(x, f(x)) $\forall$ x ( (A(x,f(x)) $\vee$ $\neg$ C(f(x) $\vee$ D(x, f(x)) ) $\wedge$ ( $\neg$ B(x, f(x)) $\vee$ $\neg$ C(f(x) $\vee$ D(x, f(x)) ) $\forall$ x1 A(x1,f(x1)) $\vee$ $\neg$ C(f(x1) $\vee$ D(x1, f(x1)) $\forall$ x2 $\neg$ B(x2, f(x2)) $\vee$ $\neg$ C(f(x2) $\vee$ D(x2, f(x2)) A(x1,f(x1)) $\vee$ $\neg$ C(f(x1) $\vee$ D(x1, f(x1)) $\neg$ B(x2, f(x2)) $\vee$ $\neg$ C(f(x2) $\vee$ D(x2, f(x2))

5. Alakítsa át klóz formára: * $\forall$ x $\exists$ y Piros(x) $\vee$ Zöld(x) $\vee$ Sárga(x) $\Rightarrow$ Megveszi(x,y)* $\forall$ x $\exists$ y Piros(x) $\vee$ Zöld(x) $\vee$ Sárga(x) $\Rightarrow$ Megveszi(x, y) _ $\forall$ x $\exists$ y $\neg$ (Piros(x) $\vee$ Zöld(x) $\vee$ Sárga(x)) $\vee$ Megveszi(x, y)_ $\forall$ x $\exists$ y ( $\neg$ Piros(x) $\wedge$ $\neg$ Zöld(x) $\wedge$ $\neg$ Sárga(x)) $\vee$ Megveszi(x, y) _ $\forall$ x ( $\neg$ Piros(x) $\wedge$ $\neg$ Zöld(x) $\wedge$ $\neg$ Sárga(x)) $\vee$ Megveszi(x, f(x))_ ( $\neg$ Piros(x) $\wedge$ $\neg$ Zöld(x) $\wedge$ $\neg$ Sárga(x)) $\vee$ Megveszi(x, f(x)) _c Piros(x1) $\vee$ Megveszi(x1, f(x1))_ $\neg$ Zöld(x2) $\vee$ Megveszi(x2, f(x2)) $\neg$ Sárga(x3) $\vee$ Megveszi(x3, f(x3))

Rezolúció

8. Foglalja össze a rezoluciós logikai bizonyítás lépéseit! 1. Az F halmaz összes állítását konvertáljuk F ' klóz formába. 2. Negáljuk az S-t és konvertáljuk klóz formába. Adjuk hozzá az F '-hez. _3. Ismételjük az alábbi ciklust, amíg _ _ (a) ellentmondásra rá nem futunk, _ _ (b) AZ ELŐREHALADÁST MÁR NEM TAPASZTALJUK, vagy _ _ (c) AZ ERŐFORRÁSOK ELŐRE MEGHATÁROZOTT MENNYISÉGÉT _ _ KI NEM HASZNÁLJUK:_ _# VÁLASSZUNK MEG két klózt._ _# Alkalmazzunk rezolúciós lépést._ _ Rezolvens = a két szülő klóz összes literáljának diszjunkciója, _ _ megfelelő behelyettesítéssel._ _# Ha a rezolvens egy üres klóz, megvan az ellentmondás. _ _ Ha nincs, adjuk hozza a többi klóz-hoz és folytatjuk tovább. _

64. Hogyan néz ki az általánosított Modus Ponens ? Miben áll a fontossága ? _ E1 P(A)_ _ ===E1 $\Rightarrow$ E2=== === $\forall$ x P(x) $\Rightarrow$ Q(x)_=== _ E2 Q(A) _ Nagyobb lépéseket tesz, hasznos lépéseket tesz(nem próbálgat véletlenül, mint az univerzális-elimináció), és kihasználja a kanonikus formát.

III 5. Tanult definíciók és a rezolúció működése alapján magyarázza meg, hogy egy érvényes állítás érvényes voltát hogyan lehet a rezolúciós bizonyítással kimutatni. Érvelését az alábbi állítás esetén ültesse át gyakorlatba:

a. $\forall$ _x P_(_x_) $\Rightarrow$ $\exists$ _x_ _P_(_x_) _ Az érvényes állítás önmagában igaz, minden más ténytől függetlenül. Ez azt jelenti, hogy a rezolúciós bizonyításban az állításhalmaz üres, csakis a kérdés létezik, amit persze negáltjával kell figyelembe venni és rajta a rezolúciós lépéseket elvégezni._

Az a. állítás negálva: _ $\neg$ ( $\forall$ x P(x) $\Rightarrow$ $\exists$ x P(x))_ és klózzá alakítva: _ $\neg$ ( $\neg$ $\forall$ x P(x) $\vee$ $\exists$ x P(x))_ _ $\neg$ ( $\exists$ x $\neg$ P(x) $\vee$ $\exists$ x P(x))_ _ $\forall$ x P(x) $\wedge$ $\forall$ y $\neg$ P(y)_ _ P(x) $\wedge$ $\neg$ P(y)_ _ a1. P(x)_ _ a2. $\neg$ P(y)_ A rezolúciós lépés az a1. és az a2. klózok egy lépéses rezolválása x/y behelyettesítéssel, üres klózzá.

74. Értelmes stratégia, amikor a kérdés negáltjából indulunk ki és mindig megtartjuk a pillanatnyi rezolvenst ?

Csak abban az esetben értelmes, ha a tudásbázis klóz formában tartalmazza a logikai állításokat (input stratégia).

78. Lássa be, hogy a rezolúciós lépés egy deduktív lépés ! (( $\neg$ A $\vee$ B) $\wedge$ (A $\vee$ B)) $\Rightarrow$ B _ (ezt kell levezetni, vagy igazságtáblával belátni – könnyű)_

(2001.01.17.) Tegyük fel, hogy rendelkezésünkre áll bizonyos mennyiségű MgO, H₂, O₂ és C. Tegyük fel, hogy a következő kémiai reakciókat biztosítani tudjuk: a. MgO + H₂ $\Rightarrow$ Mg + H₂O b. C + O₂ $\Rightarrow$ CO₂ c CO₂ + H₂O $\Rightarrow$ H₂CO₃ A helyzetet logikai apparátussal modellezve mutassuk meg rezolúciós bizonyítással, hogy elő tudunk állítani H₂CO₃-at !

II 7. A relevancia alapú tanulásnál egy általános háttértudásból (hogy egy országban a nép egy nyelvet beszél – a. állítás) és a megfigyelt konkrét esetből (hogy a Fernandó nevű brazil bennszülött portugálul beszél – b. állítás) meg lehet tanulni, hogy Brazília nyelve portugál. (c. állítás).

a. $\forall$ x, y, n, l Nemzetisége(x, n) $\wedge$ Nemzetisége(y, n) $\wedge$ Nyelve(x, l) $\Rightarrow$ Nyelve(y, l) b. Nemzetisége(Fernandó, Brazil) $\wedge$ Nyelve(Fernandó, Portugál) c. $\forall$ x Nemzetisége(x, Brazíl) $\Rightarrow$ Nyelve(x, Portugál)

_Az állításokat alakítsa át klóz formára és rezolúcióval lássa be, hogy a c. állítás következik az a. és b. állításból. _

Megoldás: _a. $\forall$ x, y, n, l N(x,n) $\wedge$ N(y,n) $\wedge$ Ny(x,l)  Ny(y,l) _ b. N(F, B) $\wedge$ Ny(F, P) _c. $\forall$ x N(x,B)  Ny(x,P) igaz-e_

A kérdéses állítást negálni kell: _a. $\forall$ x, y, n, l N(x,n) $\wedge$ N(y,n) $\wedge$ Ny(x,l)  Ny(y,l) _ b. N(F, B) $\wedge$ Ny(F, P) _c. $\neg$ ( $\forall$ x N(x,B)  Ny(x,P) )_

_klózformára való átalakításnál _ az a. állítás a premissza negálása miatt egyetlen egy klózzá alakul át: _ $\neg$ N(x1,n) $\vee$ $\neg$ N(y1,n) $\vee$ $\neg$ Ny(x1,l) $\vee$ Ny(y1,l) _ a b. állításból, konjunkció miatt, két klóz lesz: _N(F, B)_ Ny(F, P) _a c. állításnál a negálás befelé tolása megváltoztatja a kvantor jellegét (egzisztenciális), ami egyrészt skolemizáláshoz vezet, másrészt a konjunkció miatt ez is két klózzá esik szét:_ N(,B) _ $\neg$ Ny( ,P) ahol  egy Skolem konstans_

és most a rezolúció: _ N(F,B) –ből és_ $\neg$ N(x1,n) $\vee$ $\neg$ N(y1,n) $\vee$ $\neg$ Ny(x1,l) $\vee$ Ny(y1,l) -ből _-------- x1/F, n/B behelyettesítéssel_ $\neg$ N(y1,B) $\vee$ $\neg$ Ny(F,l) $\vee$ Ny(y1,l) –ből és _ Ny(F, P) - ből_ --------- l/P behelyettesítéssel _ $\neg$ N(y1,B) $\vee$ Ny(y1,P) –ből és_ _ $\neg$ Ny(, P) -ből_ ---------- y1/ behelyettesítéssel _ $\neg$ N(,B) –ből és_ _ N(,B) -ből_ -------- _[]_

IIII 5. Tekintsük az alábbi példát: “Városban vásárolunk. Vezetni csak Anna és Barbara tud. Anna nem megy Csaba vagy Dávid nélkül. Csaba követeli, hogy Erzsébet és Fanni is jöjjön. Ha Fanni megy, de Dávid marad, akkor Erzsébet is marad vele. És Dávid nem tud menni. Ki fog vezetni ?”

Ítélet szimbólumok: _A_ - Anna megy (azaz vezethet) _B_- Barbara megy _C_ - Csaba megy _D_ - Dávid megy _E_- Erzsébet megy _F_ - Fanni megy

A történet leírása:# _A $\vee$ B _2. _A $\Rightarrow$ (C $\vee$ D) _3. _C $\Rightarrow$ (E $\wedge$ F) _4. (F $\wedge$ $\neg$ D) $\Rightarrow$ $\neg$ E#### $\neg$ D

Lássa be rezolúcióval, hogy Barbara fog vezetni. Milyen rezolúciós stratégiát használt ?

A klózok: 1. A $\vee$ B 2. _ $\neg$ A $\vee$ C $\vee$ D _ 3a. $\neg$ C $\Rightarrow$ E 3b. $\neg$ C $\Rightarrow$ F 4. $\neg$ F $\vee$ D $\vee$ $\neg$ E 5. $\neg$ D 6. $\neg$ B (a kérdés)

7:# + 6. _A _ 8:# + 2. C $\vee$ D 9:# + 5. _C_ 10:# + 3a. _E_ 11: 10. + 3b. _F_ 12: 11. + 4. D $\vee$ $\neg$ E 13: 12. + 10. _D_ 14: 13. + 5. üres rezolvens, itt pl. a stratégia az input rezolúció, de lehetne a bizonyítást másképpen levezetni.

4. Modellezzünk az otthoni vízvezetékrendszer egy részletét az alábbiak szerint: x-csap nyitva: *Csx, nyomás van x-ben: Nyx*, víz folyik x-ben:* Vzx. *Szokásos köznapi tudásunk lehetőséget teremt felírni, hogy: Vz2 $\vee$ Vz3 $\Rightarrow$ Vz1 Ny1 $\Rightarrow$ Ny2 $\wedge$ Ny3 Ny2 $\wedge$ Cs2 $\Rightarrow$ Vz2 Ny3 $\wedge$ Cs3 $\Rightarrow$ Vz3

Legyen a konkrét megfigyelés az, hogy: Ny1 van, a Vz1 nem folyik és* Cs3* le van zárva. Bizonyítsuk be (*===rezolúció*===!), hogy igaz az a sejtés, hogy a Cs2 szelep is zárva van!

(vagy pedig, hogy Cs2 le van zárva és bizonyítsuk be, hogy igaz az a sejtés, hogy a Cs3 szelep is zárva van)

*1. Vz2 $\vee$ Vz3 $\Rightarrow$ Vz1 * _*2. Ny1 $\Rightarrow$ Ny2 $\wedge$ Ny3 *_ *3. Ny2 $\wedge$ Cs2 $\Rightarrow$ Vz2 * _*4. Ny3 $\wedge$ Cs3 $\Rightarrow$ Vz3*_ *5. Ny1* _*6. $\neg$ Vz1*_ *7. $\neg$ Cs3* _*8. $\neg$ Cs2* (a kérdés a Cs2 értéke, a rezolúcióhoz negálva kell felvenni)_

*1a. $\neg$ Vz2 $\vee$ Vz1 * _*1b. $\neg$ Vz3 $\vee$ Vz1 *_ *2a. $\neg$ Ny1 $\vee$ Ny2* _*2b. $\neg$ Ny1 $\vee$ Ny3 *_ *3. $\neg$ Ny2 $\vee$ $\neg$ Cs2 $\vee$ Vz2 * _*4. $\neg$ Ny3 $\vee$ $\neg$ Cs3 $\vee$ Vz3 *_ *5. Ny1* _*6. $\neg$ Vz1*_ *7. $\neg$ Cs3* _*8. $\neg$ Cs2*_

Már egy rápillantás is elég, hogy megállapitsuk, hogy ebből az állításhalmazból soha nem jön ki az üres rezolúció (az állítás halmaz ellentmondásassága nem dönthető el). Azonban a feladat a Cs2 értéke, azaz vagy a Cs2 ítéletállítás logikai értéke, vagy a $\neg$ Cs2 ítéletállítás logikai értéke, hiszen mindegyik változatnak úgyananyi az információ értéke. Ha a kérdés a $\neg$ Cs2, akkor negálva Cs2 és most már a rezolúció menni fog.

*8’. Cs2*

*1a. + 6 = 7: $\neg$ Vz2 * _*1b. + 6 = 8: $\neg$ Vz3*_ *2a. + 5 = 9: Ny2* _*2b. + 5 = 10: Ny3 *_ *3. + 7 + 2a = 11: $\neg$ Cs2* _*8’ + 11 = 12:  *(tehát Cs2 hamis, abból kifolyólag $\neg$ Cs2 igaz, a csap zárva van)_

A feladat másik változatában a helyzet ugyanaz (mert a fizikai rendszer a Cs2, Cs3 csapokra szimmetrikus, így annak a logikai leírása is), csupán a Cs2 és a Cs3 szerepet cserél.

8. Rezolució alkalmazásával lássa be, hogy (nyilvánvalóan igaz) ( $\forall$ x P(x)) $\Rightarrow$ ( $\exists$ x P(x))

állítás tényleg igaz

Ez az állítás egy érvényes állítás, más állítás ismerete nem szükséges. Maga a kérdés, amit negálni kell és egy üres rezolvensre visszavezetni.

klóz $\neg$ * ( ( $\forall$ x P(x)) $\Rightarrow$ ( $\exists$ x P(x)) )* _* $\neg$ ( $\neg$ ( $\forall$ x P(x)) $\vee$ ( $\exists$ x P(x)) )*_ * ( $\forall$ x P(x)) $\wedge$ * $\neg$ * ( $\exists$ x P(x)))* _* ( $\forall$ x P(x)) $\wedge$ ( $\forall$ x * $\neg$ *P(x))*_ * ( $\forall$ x P(x)) $\wedge$ ( $\forall$ y * $\neg$ *P(y))* _* $\forall$ x $\forall$ y P(x) $\wedge$ * $\neg$ *P(y)*_ *P(x) $\wedge$ * $\neg$ *P(y)* _* c1. P(x)*_ *c2. * $\neg$ *P(y)*

_c1,c2: P(x) _ _ === $\neg$ *P(y)*=== x/y_ _ üres rezolvens_ azaz az állítás igaz.

4. Modellezzünk egy egyszerű csőrendszert az alábbiak szerint:

Ha nyomás van, szelep nyítva és lyuk nincs, akkor vízes a padló. Ha nyomás van, szivarog a cső, akkor vízes a padló. Ha a nyomáskijelző nyomást mutat és kijelző nem rossz, akkor nyomás van. Ha a szelepálláskijelző nyított szelepet mutat és a szelepálláskijelző nem rossz, akkor szelep nyítva van.

a. Nyomás $\wedge$ Szelep $\wedge$ $\neg$ Lyuk $\Rightarrow$ Víz b. Nyomás $\wedge$ Lyuk $\Rightarrow$ Víz c. NyomásKijelző $\wedge$ $\neg$ NyomásKijelzőRossz $\Rightarrow$ Nyomás d. SzelepÁllásKijelző $\wedge$ $\neg$ SzelepÁllásKijelzőRossz $\Rightarrow$ Szelep

Legyen a konkrét megfigyelés az, hogy: nyomás van, nyomáskijelző nyomást mutat, szelepálláskijelző nyított szelepet mutat, és a padló nem vízes. e. *Nyomás *f*. NyomásKijelző* g. SzelepÁllásKijelző h. $\neg$ Víz Bizonyítsuk be (*===rezolució*===!), hogy igaz az a sejtés, hogy a szelepálláskijelző rossz! (6 pont)

a. *Nyomás $\wedge$ Szelep $\wedge$ $\neg$ Lyuk $\Rightarrow$ Víz* _b. *Nyomás $\wedge$ Lyuk $\Rightarrow$ Víz*_ c. *NyomásKijelző $\wedge$ $\neg$ NyomásKijelzőRossz $\Rightarrow$ Nyomás* _d. *SzelepÁllásKijelző $\wedge$ $\neg$ SzelepÁllásKijelzőRossz $\Rightarrow$ Szelep*_ _ e. *Nyomás _ _f. NyomásKijelző* _ _g. SzelepÁllásKijelző _ h. * $\neg$ Víz*

a. *N $\wedge$ S $\wedge$ $\neg$ L $\Rightarrow$ V *b. *N $\wedge$ L $\Rightarrow$ V* _c. *NK $\wedge$ $\neg$ NKR $\Rightarrow$ N *d. *SAK $\wedge$ $\neg$ SAKR $\Rightarrow$ S*_ _ e. *N *f*. NK*_ g. SAK h. * $\neg$ V* _A kérdés negálva:_ i. * $\neg$ SAKR* _A klózok:_ a. * $\neg$ N $\vee$ $\neg$ S $\vee$ L $\vee$ V *b. * $\neg$ N $\vee$ $\neg$ L $\vee$ V* _c. * $\neg$ NK $\vee$ NKR $\vee$ N *d. * $\neg$ SAK $\vee$ SAKR $\vee$ S*_ _ e. *N *f*. NK*_ g. SAK h. * $\neg$ V* _A kérdés negálva:_ i. * $\neg$ SAKR* _A rezolúció:_ j. = a. + e. + h. = * $\neg$ S $\vee$ L* _k. = b. + e. + h. = * $\neg$ L*_ l. = j. + k. = * $\neg$ S* _m. = d. + g. + i. = *S*_ _ n. = l. + m. = üres rezolvens_

Modellezzünk a csőrendszer egy részletét az alábbiak szerint: Nyítva(Cs1) $\wedge$ Nyomás(Ny1) $\Rightarrow$ Nyomás(Ny3) Nyítva (Cs3) $\wedge$ Nyomás(Ny3) $\Rightarrow$ Telik(Ms)

Telik(Ms) $\wedge$ $\neg$ Dugó(Ms) $\Rightarrow$ Folyik(Vz3) Folyik(Vz3) $\Rightarrow$ Folyik(Vz1)*

Legyen a konkrét megfigyelés az, hogy: Nyomás1 van, *Mosdó *nincs eldugaszolva, de a Vz1 nem folyik, azaz: *Nyomás(Ny1), $\neg$ Dugó(Ms), $\neg$ Folyik(Vz1). *Bizonyítsuk be (*===rezolúció*===!), hogy igaz az a sejtés, hogy vagy a Cs1, vagy a Cs3 szelepek zárva vannak! (6 pont)

Nyítva(Cs1) $\wedge$ Nyomás(Ny1) $\Rightarrow$ Nyomás(Ny3) _Nyítva (Cs3) $\wedge$ Nyomás(Ny3) $\Rightarrow$ Telik(Ms)_ _Telik(Ms) $\wedge$ $\neg$ Dugó(Ms) $\Rightarrow$ Folyik(Vz3) _ Folyik(Vz3) $\Rightarrow$ Folyik(Vz1) _Nyomás(Ny1)_ $\neg$ Dugó(Ms) _ $\neg$ Folyik(Vz1)_ $\neg$ ( $\neg$ Nyítva(Cs1) $\vee$ $\neg$ Nyítva(Cs3))

Klózok, rövidítésekkel:

$\neg$ C1 $\vee$ $\neg$ N1 $\vee$ N3
$\neg$ C3 $\vee$ $\neg$ N3 $\vee$ T
_ $\neg$ T $\vee$ D $\vee$ F3 _
$\neg$ F3 $\vee$ F1
N1
$\neg$ D
$\neg$ F1
C1
C3

10. 1.+5.+8. = N3 _11. 10.+9.+2. = T_ 12. 11.+6.+3. = F3 _13. 12.+7.+4. = üres rezolvens_

Elsőrendű logika

III 7. Értelmezze az elsőrendű logika körében az alábbi fogalmakat: teljesség, félig eldönthetőség, monotonitás, unifikálás. _ Vázlatosan:_ Teljesség – amikor minden IGAZ állítás be is bizonyítható. _Félig eldönthetőség – amikor a HAMIS állítás hamis volta nem mutatható ki._ Monotonítás – ha az egyszer bebizonyított állítás mindig igaz marad. _Unifikálás = Egyesítés – az általánosított Modus Ponens, ill. rezolúciós bizonyító lépésnek az a része, amikor a két kifejezés bizonyos részliteráljait alkalmas behelyettesítések révén azonos, vagy ellentétes logikai értékre hozzuk._

4. Az elsőrendű logikában, a rezolúciós lépés alkalmazásánál miért ügyelni kell az argumentumok értékére ? Saját példával illusztrálja. _ Mert a sikeres egyesítés csakis a megfelelő behelyettesítések mellett lehetséges. Pl. két konstans nem helyettesíthető egymással, két változó pedig igen._ Példa: _ $\neg$ kutya(János) $\vee$ piros (János)_ _ kutya(Bodri)_ nem megy (az első két literál a negálás ellenére mind igaz !) _ $\neg$ kutya(x) $\vee$ piros (János)_ _ kutya(Bodri)_ megy (x/Bodri behelyettesítéssel, és így az első két literál ellentétes logikai értéket kap !)

92. Milyenek az elsõrendû logika tulajdonságai ? Teljes(minden igaz állítás belátható annak) _ Félig eldönthető(hamis állítás hamis volta nem mutatható ki)_

III 6. Írja le elsőrendű logika formalizmusával: Emberek sûrûn lakják a Földet. Jancsi is ember, arra ügyelve, hogy az alkalmazott logikai átírásból ne következzen, hogy Jancsi is sûrûn lakja a Földet. Lehet pl. _ember(Jancsi)_ $\forall$ x $\forall$ y ember(x) $\wedge$ ember(y) $\Rightarrow$ kozellakik(x,y) _de lehet számtalan más módon is. A lényeg, hogy ne alakuljon a helyzet pl. az alábbi módon:_ $\forall$ x ember (x) $\Rightarrow$ sürûnlakja-a-földet (x) _ember (Jancsi)_ mert a Modus Ponens-bõl következik, hogy: s_ürûnlakja-a-földet (Jancsi)_

121. Az elsõrendû logikában az apparátus milyen elemeibe épül be a világra vonatkozó tudás ? A logikai konstansokba, a függvény- és a predikátumnevekbe.

II 7. Miért nehéz elsőrendű logikában ábrázolni olyan kijelentéseket, hogy az A ágens azt hiszi, hogy a B ágens okos. Mik a lehetséges megoldások ?

Mert nem megy a hiedelem predikátumként való kifejezése, pl.: _A-hiszi(okos(B))_ _hiszen egy predikátumban argumentumként nem állhat egy másik literál (elsőrendű logika szintaktikája). _ Két megoldás lehet: _a. A predikátumon belül a belső állítást „füzéresíteni”, ettől konstássá válik és így a szintaktika megmenthető:_ A-hiszi(„okos(B)”) _Probléma ilyenkor, hogy a ’külső’ és a ’belső’ állításról nem lehet egyszerre következtetni._ b. Predikátum helyett logikai operátort alkalmazni, pl.: _H_A okos(B), ahol H_A p jelentése, hogy az A ágens elhiszi a p-t._ Itt az a probléma, hogy a H_A p-hez nem adható meg az igazságtáblával az állítás értékszámítása (H_A p logikai értéke nem függ a p logikai értékétől !!). Ez az út a modális logika felé vezet, ahol meg kell adni a H_A p számítási módszerét (szemantikát).

Ítéletkalkulus, szituációs kalkulus

7. Milyen az ítéletlogikai következtetés komplexitása és miért? Vonatkozik-e ugyanaz a Predikátum Kalkulus esetére is? Az ítéletlogika eldönthető, mert minden jól definiált mondat igaz-hamis volta belátható véges erőforrások alkalmazásával. A predikátum félig eldönthető. Hamis – hamis volta nem dönthető el.

5. Az ítélet- ill. elsőrendű logikának milyen alapvető tulajdonsága nem teszi azt alkalmassá az alapeseti következtetés megvalósítására? Az, hogy monoton logikák mind.

8. Milyen az ítélet logikai következtetés komplexitása és mivel tudná az állítását megindokolni ? Vonatkozik-e ugyanaz a predikátum kalkulus esetére is ? (2 pont) Az, hogy az ítéletlogika sok állítását pl. egyetlen egy elsőrendű állítással ki lehet fejezni nem jelenti azt, hogy az elsőrendű logikának kisebb a komplexitása. Az elsőrendű állításokban lévő változók konkrét bizonyítások esetén (a sokféle lehetséges behelyettesítések révén) a komplexitást csak tovább fokozzák.

7. “Az egzisztenciális kvantor eltüntetése” deduktív lépés párja “az egzisztenciális kvantor bevezetése”, miért azonban nincs párja “az univerzális kvantor eltüntetése” lépésnek ? _ A predikátum kalkulus, és az ítéletlogika képtelen az általánosításra. (pl.: kutya(A), kutya(B), kutya(C) nem implementálja hogy $\forall$ x kutya(x), mert lehet, hogy $\neg$ kutya(D) )._

7. Milyen axiómákkal ki kell egészíteni a szituáció kalkulust, hogy az ágens világát képes legyen leírni? Hatás-axiómákkal(a cselekvések hatására bekövetkező változások a világ állapotában) és keret-axiómákkal(ellenkezője: a világ változatlansága a cselekvések hatására, pl.:ha nem engedi el, akkor még nála van az arany).

6. Mi a szituáció kalkulus? Mire jó ? Milyen viszonyban áll az elsőrendű logikához ? Fogalmazzon szituációs kalkulusban egy szintaktikailag helyes (!) saját példát. (3 pont)

5*. Mire jó a szituáció kalkulus, mi a viszonya a predikátum kalkulushoz ? Mi a keret axiómák szerepe ? Mit írnak le ? Képzeljünk el egy ágenst és a környezetet (valamilyen cselekvési készlet és a világ leírása) és fogalmazzuk meg az egyik cselekvésére a hatás axiómát (saját példa)? (5 pont)

TMS

127. Mik az un. természetes fajták és milyen problémát jelentenek ? Adjon meg egy saját példát. Nehezen tömören definiálható természetes kategóriák. Tömör töredékes leírás alapján nehéz az egyértelmű következtetés. Tipikus esetek ábrázolása. (előadás példa: paradicsom, nemzetiség)

128. Miért fontos a kategóriák ábrázolása ? A következtetés általában kategóriák szintjén történik. Öröklődésre van lehetőség.

II 8. Miért fontos, hogy egy intelligens rendszer képes legyen az alapeseti következtetésre ? Hogyan változik ilyenkor a következtetés jellege ? Milyen idetartozó módszereket ismer ?

_ Mert ez a tipikus gyakorlati eset (t.i. hogy valamilyen tudásanyag mindig hiányzik), de általában ami hiányzik, az a speciális, ritkán előforduló információ. Ami viszont közismert, feltételezhető, azok a tipikus esetek és tudásformák. Ezek után lehet következtetni megszokott, deduktív módon. A baj csak akkor lesz, amikor a feltételezés helytelennek bizonyul és ezzel az eddig kihozott igazságok halmaza is (nem monoton helyzet). Pontosabban az a lényegi baj, hogy elképzelhető, hogy néhány tény továbbra is igaz marad, azonban a tárolt bizonyítások hiányában nem tudjuk azokat a többitől elkülöníteni. Az elsőrendű logika itt tehetetlen. Ide tartozik a TMS módszerek családja a tárolt bizonyítás = függőségi gráffal, nem eldobott hamissá vált állításokkal és az explicit módon tárolt ellentmondásokkal._

15. Miért lényeges a default ismeretek kezelhetősége ? Mert a hiányos ismereteket ezek tükrében próbáljuk kitalálni, pótolni, ehhez viszont szükség van arra, hogy legalább azt a keveset, amit tudunk, jól tudjuk kezelni.

15. Milyen elvi problémákra lehet számítani a default ismeretek kezelésénél ? _Előfordulhat, hogy a feltételezett érték nem helyes, és új értéket kell tippelnünk. Ez sokáig mehet így, ami problémát okozhat. _ Ha kiterjesztjük a logikát egy új operatorral vagy új következtetési szabállyal, akkor elszáll a félig eldönthetőség.

16. Milyen elemekben tér el a monoton logikától a TMS módszertan? (3 pont)

III 9. A logikai ellentmondást tekintve miben különbözik a TMS rendszer az első rendű logikától ?

_ Az elsőrendű logikában az ellentmondás az egész tudás bázis tulajdonsága (inkonzisztens tudás). Az érte felelős tény akárhol lehet benne. A TMS rendszerben az ellentmondásokat explicit módon, tényként (csomópontként) ábrázoljuk, így pl. több oknál fogva megjelenő ellentmondásokat tudunk külön-külön ábrázolni és kezelni._

III 8. Mik a TMS rendszerben alkalmazott különleges megoldások a nem-monoton következtetés biztosítására ? _ Alapvetően a TMS rendszer tárolja (a Support List formájában) a bizonyításokat, így a függőségeket képes kinyomozni és a konzisztenciát visszaállítani. A tények mellett (csomópontok) mindkét logikai értéket tárol (a hamissá vált tényeket nem törli a tudásbázisból), hiszen a pillanatnyi hamisság később újra igazzá válhat és az újbóli következtetést megspóroljuk. Az utolsó megoldás az ellentmondás (több is lehet) explicit ábrázolása (ellentmondás csomópontok) és így lehetőség arra, hogy a logikai ellentmondáshoz vezető különböző helyzeteket lekezelhessük._

II 9. A TMS rendszerben mi felelhetne meg az alábbi állításnak: A $\wedge$ $\neg$ B $\Rightarrow$ C ? C

+ -

A B

5. Mi a Support List típusú bizonyítás információtartalma? (2 pont) A support lista (+) jelű elemeinek IN állapota és a (-) jelű elemek OUT állapota bizonyítja az alátámasztott állítás igazságát (IN), míg ha a (+) OUT vagy a (-) IN akkor az állítás OUT-ba billen.

(A TMS módszerben a Support List struktúrában már nincs negálás. A negált logikai állítás, mivel hamis értékével járul hozzá a bizonyított állítás értékéhez a (-) azaz az Out részlistára kerül, ahol Out értékével támasztja alá a célállítást.)

16. Milyen problémákat orvosol és milyen lényegi új elemeket vezet be a logikai apparátusba a TMS rendszer ? Orvosolja azt a problémát, hogy ha a rendszerben egy változó értéke megváltozik, akkor nem lesz miatta inkonzisztens az egész tudásbázis. Az apparátus tartalmazza az egyes értékek bizonyítását, így az esetleges változások hatását az egész rendszerben ki lehet értékelni.

15. Milyen lényegi különbséget tapasztal a JTMS és az ATMS működésében ?

_ Az ATMS a kontextus háló alapján dolgozik, ahol az összes lehetséges kontextus között keres. A rossz ágakat levágja. A JTMS logikai értékekkel dogozik és ellentmondás esetén újraszámítja a megfelelő ágakat._

Bizonytalan tudás

15. A valószinűségi számításhoz képest milyen furcsaságokat tapasztalt a Dempster-Shaffer elmélet esetén ? a. Egy evidencia nem egy hipotézishez, hanem egy hipotézishalmazhoz rendel probabilisztikus súlyt _b. A probabilisztikus súly nem pontszerű, hanem egy intervallum, amely nővekvő evidenciával pontszerű jellemző felé zsugoródik._

17. Mi a Dempster-Schafer elméletben alkalmazott 'tömegeloszlás' különlegessége ? Tömegeloszlás (mass distribution): m(p) _p - a hipotézisek részhalmaza, új evidencia - új m(p), megoldandó probléma az m(p)-k kumulalasa_ Belief függvény - m összegzése p összes részhalmaza felett:

_ Be(p) =  m(q)_ _ q  p_

174. Hasonlítsa össze a valószínűség alapú és a Dempster-Schafer féle bizonytalanságábrázolást ! A valószínűség alapú rendszerekkel szemben a Demszter Schafer elmélet megkülönböztethetővé teszi a bizonytalanságot és az ismerethiányt. Egy állítás valószínűsége helyett egy valószínűségi intervallumot definál, amely annál inkább pontszerű, minél nagyobb a hiedelem mértéke.

15. Milyen jellegű bizonytalan tudást lehet mesterséges intelligencia eszközeivel modellezni ? _ - 'lazaság/lustaság': a részletes szabályok megfogalmazása túl nehéz, használatuk szintén _ nehézkes (véges erőforrások miatt).

_elméleti tudatlanság: adott problématerületnek az elméleti feltárása még nem zárult le, _

vagy soha lezárni nem lehet _ - gyakorlati tudatlanság:_ _ nem minden, a szabályokban hivatkozott, feltétel ismert a szabályok_

11. Mutassa meg az alapelvek segítségével, hogy P(A / A $\wedge$ B) = 1 P(A  A $\wedge$ B) = P(A $\wedge$ A $\wedge$ B) / P(A $\wedge$ B) = P(A $\wedge$ B) / P(A $\wedge$ B) = 1

IIII 9. Írja fel a Bayes-tételt, értelmezze a benne szereplő mennyiségeket és magyarázza meg, miért hasznos ez a tétel a bizonytalan tudás ábrázolása szempontjából ?

P(H|E) = P(EH) P(H)/ P(E), ahol H a hipotézis, az E pedig az evidencia A hasznosság abból adódik, hogy a probléma leírásánál általában könnyűszerrel megadható kauzális P(E|H) a priori valószínűségből kiszámítható a diagnosztikai feladat megoldásához szükséges, nehezen megadható anti-kauzális P(HE) a posteriori valószínűség.

17. Foglalja össze, hogy a valószínûségbõl eredõ 'egyéb' módszerek milyen, a Bayes-tétel hátterében húzódó, elvi szinten rögzített feltételezéseket szeretnének feloldani ? - a priori feltételes és együttes valószínűségek begyűjtése nehéz és költséges (frekvencionista megközelites esetén), _ - emberek általában rossz valószínűségbecslők (szubjektív megközelítés esetén),_ _ - túl sok adatról lehet szó, a begyűjtése nem tud lépést tartani az elavulásával (pl. a mikróbák reakciója a gyógyszerekre igen gyorsan változik),_ _ - Bayes rendszer módosítása körülményes (az interakciók nagy száma miatt)_ _ (pl. Sum{p}=1, mi lesz, ha egyetlenegy valószínűség értéket módosítunk ?),_ _ - Bayes szabály nagyon sok számítást igényel (az összes valószínűséget kell figyelembe venni (elpazarolt erőforrások),_ _ - ha a valószínűségek nem pontosak, mi a végleges pontosság ?_ _ - kizáró események (kettő vagy több egyszerre nem fordulhat elő),_ _ - Bayes képlet pontossága, ha az elvi feltételei nem teljesülnek ?_

Valószínűségi hálók

IIIIII 10. Mit ábrázol egy valószínűségi háló ?

A valószínűségi háló az adott problémát leíró együttes valószínűségi eloszlás tömör ábrázolása (a véletlen változók, közvetlen hatások és a feltételes valószínűségi táblák segítségével)(a tömörség forrása a feladatban rejlő függőségek kihasználása – feltételes függetlenség). Magyarázza meg, hogyan lehet következtetni és tanulni valószínűségű hálókban. A valószínűségi hálóban a kérdéses változók és az evidencia változók akárhol helyezkedhetnek a hálóban (tipikus elhelyezések az un. kauzális, diagnosztikai, okok közötti és vegyes következtetéshez vezetnek). Ha a háló egyszeresen összefüggő, megadható egy rekurzív számítási eljárás, amely a kérdéses változókra nézve keresi ki a hálóban az evidencia hatását (a szülő csomópontok felül és a gyerek csomópontok felül). Ha a háló nem egyszeresen összefüggő, akkor zárt számítási módszer nincs, többféle közelítő módszer létezik. Tanulást a neurális háló mintájára meg lehet oldani úgy, hogy a FVT elemei a súlyok és a gradiens kiszámításához alkalmazott kritérium a P(adatok|FVT-k) valószínűség.

Rajzolja fel azt a valószínűségi hálót, melynek topológiája felel meg az alábbi függőségeknek és töltse ki annak FVT tábláit:

A B

C D E

_A felsoroltakon kívül kell-e még valamilyen valószínűséget specifikálni ? _Nem.

III 5. Mik a háló építésének a lépései ?

A valószínűségi változók megválasztása, sorbarendezése, egyenkénti behelyezése a hálóba, a közvetlen hatások figyelembevétele, a FVT-k kitöltése. _1. Határozzuk meg a tárgytartományt leíró változók halmazát._ 2. Határozzunk meg egy sorrendet. _3. Ameddig maradt még érintetlen változó:_

Válasszuk a következő Xi változót és adjunk egy csomópontot a hálóhoz.
Legyen a Szülők(Xi) a csomópontok azon minimális halmaza, amik már szerepelnek a hálóban és a feltételes függetlenség korábban meghatározott (15.2) tulajdonságát teljesítik.

_Definiáljuk Xi feltételes valószínűségi tábláját._ A háló építésénél mi múlik a véletlen változók rendezésén? A valós problémák lokális strukturáltsága miatt (Egy valószínűségi változó általában nem függ a tárgytartomány összes többi változójától) egy valószínűségi háló általában sokkal tömörebb, mint egy együttes val. eloszlásfüggvény ( ami exponenciális bonyolultságú). Ellenben a változók sorrendjének szerencsétlen megválasztása esetén a valószínűségi háló is ugyanilyen bonyolult lehet. _Ami még rosszabb, ilyenkor olyan feltételes valószínűségek megadása lehet szükséges, amelyek nagyon nehezen értelmezhetők. Hogy mindezt elkerüljük, a val. változókat olyan sorrendben kell megadni, hogy először az alapvető okokat adjuk a hálóhoz, majd a változókat, amiket befolyásolnak, és ezt addig folytatjuk, amíg el nem érjük a leveleket._ A valószínűségi háló milyen módon csökkenti a valószínűségi tudásábrázolás komplexitását ? A háló topológiája meghatározza, hogy mely val. változók közt van közvatlen függőség és melyek függetlenek (vagy csak elhanyagolható mértékben függenek egymástól). A tudásábrázolás komplexitását ezen függetlenségeket kihasználva lehet jelentősen csökkenteni. A Valós problémák nagy részének lokális strukturáltsága miatt ez az egyszerűsítés általában jelentős.

15. Mi a valószínűségi háló az ún. szülői feltétele? Egy saját példával illusztrálja ! (4 pont)

12. Tegyük fel, hogy v₁, v₂, ..., v_N N db véletlen változó kétféle rendezésével az alábbi két valószínűségi hálót kapjuk eredményül:

_ v₁ v₂ v₃ v_N-1 v_N _ _{_a.) -------> --------> ........... -->_} _{_ _}

_*b.* v₁ v₂ v₃ v_{N-1_} _{_ *. . . . . . .*_}

_{_}

v_{N_}

Legyen M(i) az i-edik háló specifikálásához szükséges valószínűségek számát. Adja meg az M(a)/M(b) általános képletét és számítsa ki ennek az aránynak közelítő értékét _N_=11 esetén. _a. eset: _ _ Minden változónak csak egy szülője van, tehát a FVT-ja két elemet tartalmaz. Ennek alapján:_ _ _M(a) = 2(N-1)+1 b. eset: _ v_N –nek _N_-1 szülője van, azaz a FVT-ja 2^N-1 elemet tartalmaz. Ennek alapján:_ _ M(b) = 2^N-1 + (_N_-1)_

N_=11 esetén az arány:_ _ (2*10+1) / (2¹⁰ + 10) = 21/1034 $\simeq$ 1/50_

II 5. Élre álló N db dominó kockából építsünk egy sort. A k-adik kocka állapota, mint véletlen változó, legyen d_k (az első meglökendő kocka a d₁). A kockák csakis egy irányba dőlhetnek (1-től N-felé) és azonos egységnyi erővel dőlhetnek neki a sorban következőnek. Egy valószínűségi háló építéséhez rendezzünk kockákat d₁, d₂, d₃, ..., d_N-1, d_N(azaz kauzális sorrendben), a felépített háló az ábrán látható.

d₁ d₂ d₃ d_N-1 d_N

****** . . . . .

Milyen háló keletkezne, ha a változókat fordított (antikauzális d_N, d_N-1, d_N-2, ..., d₂, d₁) sorrendben használnánk fel a háló építéséhez ? A két háló esetére adja meg a P(d₁ d₂ d₃ ... d_N-1 d_N) együttes valószínűség képletét és alkalmas átalakítással lássa be, hogy a két érték azonos.

Megoldás: _ Kauzális esetben (ábra alapján):_ _ P(d₁ d₂ d₃ ... d_N-1 d_N) = P(d₁| d₂ d₃ ... d_N-1 d_N) P(d₂ d₃ ... d_N-1 d_N) =_ = P(d₁| d₂) P(d₂ d₃ ... d_N-1 d_N) = P(d₁|| d₂) P(d₂ d₃ ... d_N-1 d_N) P(d₃ ... d_N-1 d_N) _= P(d₁| d₂) P(d₂ d₃) P(d₃ ... d_N-1 d_N)_ = P(d₁| d₂) P(d₂|| d₃) P(d₃ ... d_N-1 d_N) P(d₄ ... d_N-1 d_N) _= P(d₁| d₂) P(d₂|| d₃) P(d₃ d₄) P(d₄ ... d_N-1 d_N)_ = .... _= P(d₁| d₂) P(d₂|| d₃) ... P(d_N-1 d_N) P(d_N)_

_ Anti-kauzális esetben:_

_Ha a véletlen változókat fordított sorrendben dolgozzuk fel, akkor hasonló hálót kapunk, hiszen _ ha tudjuk a k-adik kocka állapotát, ez meghatározza teljes egészében a (k-1)-ik kocka állapotának a valószínűségét, függetlenül attól, hogy a k-adik kocka utáni kockákkal mi is valójában történt (figyelem: NEM a fizikai állapot meghatározásáról van szó, hiszen anti-kauzális a gondolkodás, hanem az állapot valószínűség meghatározásáról beszélünk). Fordított irányban tehát is egy csomópontnak egyetlen egy szülője van (az időben az ő utána következő kocka). Az eredményháló:

_ d_N d_N-1 d_N-2 d₂ d₁ _ _ _ * ****** . . . . .

A kérdéses valószínűség: _ P(d₁ d₂ d₃ ... d_N-1 d_N) = P(d_N d_N-1 d_N-2 ... d₂ d₁) =_ = P(d_N| d_N-1 d_N-2 ... d₂ d₁) P(d_N-1 d_N-2 ... d₂ d₁) = _= P(d_N| d_N-1) P(d_N-1 d_N-2 ... d₂ d₁) =_ = P(d_N| d_N-1) P(d_N-1 d_N-2 ... d_N-1 d_N) P(d_N-2 ... d₂ d₁) = _= P(d_N| d_N-1) P(d_N-1 d_N-2) P(d_N-2 ... d₂ d₁) =_ = P(d_N| d_N-1) P(d_N-1|| d_N-2) P(d_N-2 d_N-3) P(d_N-3 ... d₂ d₁) _= ...._ = P(d_N| d_N-1) P(d_N-1|| d_N-2) ... P(d₂ d₁) P(d₁)

_ Felhasználva a Bayes-tételt:_ P(d_N| d_N-1) P(d_N-1|| d_N-2) ... P(d₂ d₁) P(d₁) = _= P(d_N-1| d_N) P(d_N) /P(d_N-1) * P(d_N-2|| d_N-1) P(d_N-1)/P(d_N-2) * ... * P(d₁ d₂) P(d₂)/P(d₁) * P(d₁) =_ = P(d_N-1| d_N) P(d_N) * P(d_N-2|| d_N-1) * ... * P(d₁ d₂) = _= P(d₁| d₂) P(d₂|| d₃) ... P(d_N-1 d_N) P(d_N)_

II 10. Mit ábrázol egy valószínűségi háló ? Magyarázza meg, hogyan lehet következtetni és tanulni valószínűségű hálókban. A valószínűségi háló az adott problémát leíró együttes valószínűségi eloszlás tömör ábrázolása (a véletlen változók, közvetlen hatások és a feltételes valószínűségi táblák segítségével)(a tömörség forrása a feladatban rejlő függőségek kihasználása – feltételes függetlenség). _A valószínűségi hálóban a kérdéses változók és az evidencia változók akárhol helyezkedhetnek a hálóban (tipikus elhelyezések az un. kauzális, diagnosztikai, okok közötti és vegyes következtetéshez vezetnek). Ha a háló egyszeresen összefüggő, megadható egy rekurzív számítási eljárás, amely a kérdéses változókra nézve keresi ki a hálóban az evidencia hatását (a szülő csomópontok felül és a gyerek csomópontok felül). Ha a háló nem egyszeresen összefüggő, akkor zárt számítási módszer nincs, többféle közelítő módszer létezik. Tanulást a neurális háló mintájára meg lehet oldani úgy, hogy a FVT elemei a súlyok és a gradiens kiszámításához alkalmazott kritérium a P(adatok|FVT-k) valószínűség._

Rajzolja fel azt a valószínűségi hálót, melynek topológiája felel meg az alábbi függőségeknek és töltse ki annak FVT tábláit:

A B

C D E

_A felsoroltakon kívül kell-e még valamilyen valószínűséget specifikálni ? _Nem.

A felépített háló alapján adja meg a P(E D $\neg$ C $\neg$ A $\neg$ B) értékét. Milyen elvet használt a számítás megvalósításához ? Fogalmazza meg ezt az elvet a lehetőleg legáltalánosabb formában. _P(E D $\neg$ C $\neg$ A $\neg$ B) = P(E__ D $\neg$ C $\neg$ A $\neg$ B) P(D__ $\neg$ C $\neg$ A $\neg$ B) P( $\neg$ C__ $\neg$ A $\neg$ B) P( $\neg$ A $\neg$ B) =_ _ = P(E__ $\neg$ B) P(D__ $\neg$ A $\neg$ B) P( $\neg$ C__ $\neg$ A ) P( $\neg$ A) P( $\neg$ B) =_ _ = P(E__ $\neg$ B) P(D__ $\neg$ A $\neg$ B) (1 -P(C__ $\neg$ A )) (1 - P(A)) (1 - P(B)) _ és a megfelelő értékeket az FVT-kból kiolvasva az eredmény 0.

Az alkalmazott elv a feltételes függetlenség, azaz: _ P(x  Szűlők(x), Ősők(x)) = P(x  Szűlők(x)) _

A valószínűségi háló milyen módon csökkenti a valószínűségi tudásábrázolás komplexitását ? A keletkezett háló komplexitása (a hatások száma és a belőle adódó FVT táblák értékhalmaza). Jó (kauzális) rendezéssel az együttes eloszlás exponenciális komplexitását lényegesen le lehet csökkenteni.

9. Hány valószínűség megadása szükséges a fenti valószínűségi háló definiálásához? Ez hányad része a worst-case-ben megadandó valószínűségeknek?

Jelöljük meg a valószínűségi változókat (csomópontokat) valami módon, pl. az ábrán látható módon. _Egy csomópont (feltételes valószínűségi táblájának) megadásához *2 ^szülő* valószínűség kell. Tehát:_ M, H -hoz 1-1 _L, K, J, E, G -hez 2-2_ I, D, F, C, A -hoz 4-4 B -hez 8, összesen 40. Mivel összesen 13 változó van, elvileg a teljes együttes valószínűségi eloszlás megadásához 2¹³-1= 8192 válószínűségre lenne szükség. A nyereség tehát 8191/40 = kb. 204-szeres. Egyszeresen, vagy többszörösen összefüggő ez a háló? Miért? Egy megválasztott hálórészletre írja fel a feltételes függetlenség elvét! _A háló többszörösen összefüggő, mert nem húrokmentes gráf (több csomópontpár között többféle irányitatlan út is vezet). Pl. M-től I-ig egyszer az L-en, másrészt a K-n keresztül (de az ábra hemzseg ilyen esetektől). _ A független valószínűség elve azt mondja ki, hogy: P(x  szülő, őse) = P(x  szülő). Mivel a háló 2-nél több szintű, mindenhol találunk erre példát, pl. P(C  D, H) = P(C  D), vagy P(C  D, M) = P(C  D), stb.

10. Valószínűség számítási azonossággal lássa be, hogy P(A  AB) = 1. P(A  AB) = P(A $\wedge$ AB) / P(AB) = P(AB) / P(AB) = 1

6. Legyenek adva az alábbi feltételes valószínűségek:

P(A) = .9 P(B) = .8 P(C) = .7 P(DABC) = .1 P(D $\neg$ ABC) = .2 P(DA $\neg$ BC) = .3 P(DAB $\neg$ C) = .3 P(D $\neg$ A $\neg$ BC) = .6 P(D $\neg$ AB $\neg$ C) = .9 P(DA $\neg$ B $\neg$ C) = .1 P(D $\neg$ A $\neg$ B $\neg$ C) = .4 P(EC) = .2 P(E $\neg$ C) = .9 P(FDE) = .1 P(F $\neg$ DE) = .5 P(FD $\neg$ E) = .5 P(F $\neg$ D $\neg$ E) = .8

Ábrázolja a valószínűségekkel konzisztens valószínűségi hálót! Kell-e még más való-színűséget specifikálni? Egyszeresen össze-függő-e a háló? Mennyi a P(F) értéke, ha A=1, B=1, D=1, és C=0? (a kiszámításához használja a hálóban rejlő információt és a teljes való-színűség képletét) Mennyivel változik meg a P(F) értéke, ha B 0-ról 1-re változik? (6 pont)

_ _ _Az A, B, C, D csomópontok értéke ismert, így a valószínűségük 1. D = 1 kiválaszt két szülői feltételt az F FVT-jában, az E értéke viszont nem ismert, az F a két szülői feltételből adódó valószínűségét így az E valószínűségével kell súlyozni. Másképpen (a teljes valószínűség képletéből): P(F) = P(FDE)P(DE) + P(F $\neg$ (DE))P( $\neg$ (DE)) = P(FDE)P(E) + P(FD $\neg$ E)P( $\neg$ E) = _ 0.1  0.9 + 0.5  0.1 = 0.14 _mivel D = 1, DE = E, $\neg$ (DE) = $\neg$ E, és P(E) = P(EC) a C = 1 miatt. Mivel B nem szerepel sehol, a P(F) értéke a B értékétől nem függ. A háló többszörösen összefüggő._

Legyenek adva az alábbi feltételes valószínűségek: P(A) = .9, P(B) = .8, P(C) = .7, P(DAB) = .1, P(D $\neg$ AB) = .7, P(DA $\neg$ B) = .3, P(D $\neg$ A $\neg$ B) = .9, P(EC) = .3, P(E $\neg$ C) = .9, P(FDE) = .1, P(F $\neg$ DE) = .4, P(FD $\neg$ E) = .5, P(F $\neg$ D $\neg$ E) = .6

Ábrázolja a valószínűségekkel konzisztens valószínűségi hálót! Kell-e még más valószínűséget specifikálni? Egyszeresen összefüggő-e a háló? (2 pont) Mennyi a P(A $\neg$ BC $\neg$ DE $\neg$ F) együttes valószínű-ség értéke? (3 pont) Egy valószínűségi hálóban hogyan képzelhető el tanulás példák alapján? (3 pont)

_Nem kell. Egyszeresen összefüggő. _ P(A $\neg$ BC $\neg$ DE $\neg$ F) = P( $\neg$ F $\neg$ DE A $\neg$ BC) = P( $\neg$ F  $\neg$ DE A $\neg$ BC) P( $\neg$ DE A $\neg$ BC) = P( $\neg$ F  $\neg$ DE) P( $\neg$ DE A $\neg$ BC) _= P( $\neg$ F  $\neg$ DE) P( $\neg$ D  E A $\neg$ BC) P(E A $\neg$ BC) = P( $\neg$ F  $\neg$ DE) P( $\neg$ D  A $\neg$ B) P(E A $\neg$ BC) =_ P( $\neg$ F  $\neg$ DE) P( $\neg$ D  A $\neg$ B) P(E  A $\neg$ BC) P(A $\neg$ BC) = P( $\neg$ F  $\neg$ DE) P( $\neg$ D  A $\neg$ B) P(E  C) P(A $\neg$ BC) = _P( $\neg$ F  $\neg$ DE) P( $\neg$ D  A $\neg$ B) P(E  C) P(A) P( $\neg$ B) P(C) =_ (1- P(F  $\neg$ DE)) (1 - P(D  A $\neg$ B)) P(E  C) P(A) (1- P(B)) P(C) = (1 – 0.4)  (1 – 0.3)  0.3  0.9  (1 – 0.8)  0.7

Milyen matematikai fogalmat ábrázol a valószínűségi háló ? Rajzolja fel azt a valószínűségi hálót, melynek topológiája felel meg az alábbi függőségeknek és töltse ki annak FVT tábláit

P(B)=0.2 P(R| J ,M,B,F)=0.9 P(R $\neg$ J , $\neg$ M , $\neg$ B,F)=0.07 P(F)=0.4 P(R | J ,M,B, $\neg$ F)=0.8 P(R $\neg$ J , $\neg$ M , $\neg$ B, $\neg$ F)=0.08 P(M|B,F)=0.7 P(R J ,M, $\neg$ B,F)=0.7 P(M| $\neg$ B,F)=0.1 P(R J ,M, $\neg$ B, $\neg$ F)=0.6 P(M|B, $\neg$ F)=0.4 P(R J , $\neg$ M,B,F)=0.5 P(M| $\neg$ B, $\neg$ F)=0.01 P(R J , $\neg$ M,B, $\neg$ F)=0.4 P(J|M,B,F)=0.8 P(R J , $\neg$ M, $\neg$ B,F)=0.3 P(J|M, $\neg$ B,F)=0.2 P(R J , $\neg$ M, $\neg$ B, $\neg$ F)=0.2 P(J|M,B, $\neg$ F)=0.4 P(R $\neg$ J ,M,B,F)=0.01 P(J|M, $\neg$ B, $\neg$ F)=0.1 P(R $\neg$ J ,M,B, $\neg$ F)=0.02 P(J| $\neg$ M,B,F)=0.6 P(R $\neg$ J ,M, $\neg$ B,F)=0.03 P(J| $\neg$ M, $\neg$ B,F)=0.2 P(R $\neg$ J ,M, $\neg$ B, $\neg$ F)=0.04 P(J| $\neg$ M,B, $\neg$ F)=0.4 P(R $\neg$ J , $\neg$ M,B,F)=0.05 P(J| $\neg$ M, $\neg$ B, $\neg$ F)=0.01 P(R $\neg$ J , $\neg$ M,B, $\neg$ F)=0.06

_A felsoroltakon kívül kell-e még valamilyen valószínűséget specifikálni ? Egyszeresen, vagy többszörösen összefüggő ez a háló ? A felépített háló alapján adja meg a P(R $\neg$ J $\neg$ M $\neg$ B $\neg$ F) értékét. Milyen elvet használt a számítás megvalósításához ? Fogalmazza meg ezt az elvet a lehetőleg legáltalánosabb formában. _

_Nem. Többszörösen. _ P(R $\neg$ J $\neg$ M $\neg$ B $\neg$ F) = P(R  $\neg$ J $\neg$ M $\neg$ B $\neg$ F) P( $\neg$ J $\neg$ M $\neg$ B $\neg$ F) ) = _ P(R  $\neg$ J $\neg$ M $\neg$ B $\neg$ F) P( $\neg$ J  $\neg$ M $\neg$ B $\neg$ F) P( $\neg$ M $\neg$ B $\neg$ F) =_ _ P(R  $\neg$ J $\neg$ M $\neg$ B $\neg$ F) P( $\neg$ J  $\neg$ M $\neg$ B $\neg$ F) P( $\neg$ M  $\neg$ B $\neg$ F) P( $\neg$ B $\neg$ F) =_ _ P(R  $\neg$ J $\neg$ M $\neg$ B $\neg$ F) P( $\neg$ J  $\neg$ M $\neg$ B $\neg$ F) P( $\neg$ M  $\neg$ B $\neg$ F) P( $\neg$ B ) P( $\neg$ F) =_ _ P(R  $\neg$ J $\neg$ M $\neg$ B $\neg$ F) (1- P(J  $\neg$ M $\neg$ B $\neg$ F)) (1-P(M  $\neg$ B $\neg$ F)) (1-P(B )) (1-P( F)) =_ _ = … a megadott értékek alapján_ Elv: _ együttes valószínűség felírása feltételes valószínűség segítségével_ _ vigyáz! itt a háló olyan, hogy a feltételes függetlenség egyszerűsítő hatása nem lép fel!_

Fuzzy

III 9. Mi a fuzzy következtetõ rendszer blokkvázlata és milyen rendeltetésűek az egyes elemei ?

Fuzzy szabálybázis, fuzzy következtető gép, fuzzyfikáló, defuzzyfikáló. _(de)fuzzyfikáló: a bemeneti adatokból fuzzy értékeket csinál és vissza. (alfa és a súlypont számítása)_ FKG: a szabálybázis és a fuzzyfikált bemeneti adatok alapján előállít egy kimenetet. _FSZB: a logikai szabályokat tartalmzza a FKG számára._ Mik a fuzzy Modus Ponens (következtetés) alapvető problémái ?

II 11. Igaz-e fuzzy logikában, hogy A $\vee$ $\neg$ A = Igaz és A $\wedge$ $\neg$ A = Hamis ? A válaszát számítással és grafikonnal is illusztrálja ! _ Természetesen nem igaz. Mivel az ÉS a min és a VAGY a max, a diszjunkció ott lesz 1-nél kisebb, ahol az A tagsági függvénye 1-nél kisebb, a konjunkció pedig ott lesz nagyobb 0-nál._ Ha a (x) és az 1- (x) tagsági függvények grafikonján vesszük a maximum és a minimum burkolót, akkor a diszjunkcióban 1 alatti bemélyedést, a konjunkcióban 0 feletti csúcsot fogjuk tapasztalni.

III 11. Mi a Mamdani-féle implikáció definíció és miért lényeges ez a fuzzy következtetésre nézve? Az implikáció tagsági függvényének a min művelettel történő kiszámítása. Nagyban leegyszerűsíti a Modus Ponens-t kiértékelő apparátus bonyolultságát.

II 10.Mi a fuzifikálás és defuzifikálás szerepe a fuzzy következtető rendszerben? Miért hasznos (jó választás) a szingleton fuzzifikálás ? Természetes választás is ez egyben? (4 pont)

A valóság értékeit fuzzy halmazokká kell alakítani, hogy a rendszer értelmezni tudja. Például az autó sebessége kicsi, közepes vagy nagy? Hogy melyik mennyire igaz, azt a kilométeróra állásából és a tagsági függvényekből lehet kitalálni.  = maxx min(A’ (x₀), A (x)) =  (x₀)_ Ez tulajdonképpen a két tagsági függvény ÉS kapcsolatának maximumát jelenti, tehát “Maximálisan igaz lesz az, hogy mind A mind A’ igaz”. Éppen ezért természetes ez a választás.

9. Igaz-e fuzzy logikában, hogy a szokásos műveletdefiníciók mellett (mik azok?) _A _v $\neg$ _A _= _Igaz? A válaszát számítással és grafikonnal is illusztrálja! (3 pont)

12. Ábrázolja grafikusan a max-min fuzzy következtetés menetét: A $\Rightarrow$ B_

_A’_

_ B’_ fuzzy Modus Ponens esetén! (4 pont)

m m m A' A B ^ __ __ ^ __ | / \ / \ a / \ | / \/...........\...................................../________\ m | / /\ \ /xxxxxxxxx\ B'

|___/_____/__\______\____		_____/xxxxxxxxxx\__

12. A MinMax fuzzy következtetési sémában mire utal a Min, és mire a Max kifejezés? (4 pont)

10. Igaz-e fuzzy logikában, hogy az OR és AND idempotens mûveletek, azaz hogy A $\vee$ A=A és A $\wedge$ A=A? A választ grafikusan, vagy képlettel adja meg. (3 pont)

10. Értelmezze grafikusan fuzzy halmazokkal a (0 g ... 20 g) cukor adag folytonos univerzum felett a természetes nyelvben használt megszokott: _"keserű tea", "enyhén édes", "édes", "nagyon édes_" és "_pfuj, de édes_" kifejezéseket. (3 pont)

186. Vázolja rövíden a fuzzy következtetés menetét. _numerikus adat $\Rightarrow$ _ _ fuzifikálás fuzzy halmazzá $\Rightarrow$ _ _ következtetés fuzzy szabályokkal $\Rightarrow$ _ _ defuzifikálás numerikus adattá $\Rightarrow$ _ _ kimeneti adat_

2. Az (a1,a2,a3,a4) jelentése egy olyan fuzzy tagsági függvény, amely a1-tol a2-ig lineárisan 0-től 1-ig nő, a2-től a3-ig 1 értékű, a3-tól a4-ig viszont 1-től 0-ig lineárisan csökken.

Húsüzemben a száraz kolbász minőségét a ketté szeletelt kolbász keresztmetszetének a megtekintése és a szárítási idő alapján határozzák meg. A keresztmetszetben a zsírfoltok kontrasztossága a jobb minőségre utal. Vezessük be a következõ fuzzy halmazokat:

_ Kevésbé kontrasztos: (0 0 0.3 0.7)_ _ Inkább kontrasztos: (0.3 0.7 1 1) 0 ... 1 skála felett_

Sokáig száradt: (6 18 24 24) Nem sokáig száradt: (0 0 6 18) 0 ... 24 óra skála felett

Nem minőségi: (0 0 0.2 0.5) Közepesen minőségi: (0.2 0.4 0.6 0.8) _ Minőségi: (0.5 0.8 1 1) 0 ... 1 skála felett_ _ (elfogadjuk a kolbászt, ha minőségben 0.5-on túl vagyunk)._ Döntési szabályok: _# Ha kevésbé kontrasztos és sokáig száradt, akkor nem minőségi._ _# Ha kevésbé kontrasztos és nem sokáig száradt, akkor közepesen minőségi._ _# Ha inkább kontrasztos és sokáig száradt, akkor közepesen minőségi._ _# Ha inkább kontrasztos és nem sokáig száradt, akkor minőségi._

A keresztmetszet 0.6 mértékig kontrasztos és a kolbász 16 órát száradt. Fogadjuk el ?

_ A 0.6 mértékű mért kontraszt a Kevésbé kontrasztos halmaz tagsági függvényéből 0.25, az Inkább kontrasztosből 0.75 értéket metsz ki. A 16 óra (8 óra) a Sokáig halmazból 5/6 (1/6), a Nem sokáig halmazból pedig 1/6 (5/6) értéket metsz ki. Ezek után a 16 óra (8 óra) esetén a Nem minőségi, Közepesen minőségi és Minőségi kimeneti halmazok vágási szintjei: 0.75, 0.25, 1/6 (1/6, 0.75, 0.25), amiből látszik, hogy a defuzzifikálás az első esetben 0.5-nél kisebb, a másik esetben nagyobb értéket fog szolgáltatni._

12. Jelentsen (a1,a2,a3,a4) egy olyan fuzzy halmazt, melynek tagsági függvénye a1-tol a2-ig lineárisan 0-tõl 1-ig nõ, a2-tõl a3-ig 1 értékû, a3-tól a4-ig viszont 1-tõl 0-ig lineárisan csökken. Döntést fogunk fuzzy következtetéssel modellezni, hogy nézzünk-e TV-ben egy filmet. A döntés alapja a film kezdési ideje és ismert kritikája. Vezessük be a következõ fuzzy halmazokat:

_ Korán: (18h 18h 20h 21h)_ _ Normál_idõben: (20h 21h 23h 24h)_ _ Késõn: (23h 24h 2h 2h) óraskála felett_ _ Rossz_a_kritikája: (0% 0% 25% 50%)_ _ Talán_talán: (25% 50% 50% 75%)_ _ Jó_a_kritikája: (50% 75% 100% 100%) nézettségi index skála felett_ _ Nem_Szabad: (0 0 0.3 0.5)_ _ Lehet: (0.3 0.5 0.5 0.7)_ _ Muszáj: (0.5 0.7 1 1) képzett (0,1) "döntési" intervallum felett _ _ (pozitív a döntés, ha 0.5-on túl vagyunk)._

_ Ha a film korán van és jó a kritikája, akkor muszáj megnézni._ _ Ha a film késõn van és rossz a kritikája, akkor nem szabad nézni._ _ Ha a film normál idõben van és talán jó, akkor meg lehet nézni._

A film 20h30-kor kezdõdik és a nézettségi index 60%. Nézzük meg ? A megadott univerzumok felett rajzoljuk a fuzzy halmazokat és megnézzük (vagy kiszámítjuk), hogy a mért értékek melyik halmaz tagsági függvényét milyen értékszinten határozzák meg. Egy szabály premisszájában szereplő halmazok esetén vesszük az ilyen értékek min-át (maxmin következtetés). Ez lesz az a szint, amivel a konklúzió halmaz tagsági függvényét le kell nyesni. Az összes kiértékelhető szabály ily módon lenyesett konklúzió tagsági függvényét max művelettel másoljuk össze és meghatározzuk az eredő tagsági függvény súlyponti koordinátáját.

12. Jelentsen (a1,a2,a3,a4) egy olyan fuzzy halmazt, melynek tagsági függvénye _a1_-tol _a2_-ig lineárisan 0-tõl 1-ig nõ, _a2_-tõl _a3_-ig 1 értékû, _a3_-tól _a4_-ig viszont 1-tõl 0-ig lineárisan csökken.

Fõzési receptet fogunk fuzzy következtetéssel modellezni, hogy mennyire édesítsük meg az ételt, ha már benne van a só és a paprika. Vezessük be a következõ fuzzy halmazokat:

_ Kevésbé sós: (0 0 0.5 1)_ _ Sós: (0.5 0.75 1.25 1.5)_ _ Nagyon Sós: (1 1.5 2 2) gramm só skála felett_

Kevésbé Paprikás: (0 0 1 5) _ Paprikás: (1 3 6 9)_ _ Erõsen Paprikás: (4 8 10 10) gramm kalocsai paprika skála felett_

Keveset édesíteni: (0 0 20 50) _ Mértékkel: (20 30 40 50)_ _ Jócskán édesíteni: (20 50 80 80) gramm cukor skála felett_

Főzési szabályok: _ 1. Ha az étel nagyon sós, de kevésbé paprikás, akkor jócskán kellene édesíteni._ _ 2. Ha az étel sós és ráadásul paprikás, akkor csak mértékkel._ _ 3. Ha az étel kevésbé sós, de erősen paprikás, akkor jócskán kellene édesíteni._ _ 4. Ha az étel kevésbé sós, ugyanúgy kevésbé paprikás, akkor keveset kell édesíteni._ _ 5. Ha az étel nagyon sós és erősen paprikás, akkor szintén keveset._

Az ételben 1.4 g só és 3 g paprika van. Mennyi cukrot adjunk hozzá ? A megadott univerzumok felett rajzoljuk a fuzzy halmazokat és megnézzük (vagy kiszámítjuk), hogy a mért értékek melyik halmaz tagsági függvényét milyen értékszinten határozzák meg. Egy szabály premisszájában szereplő halmazok esetén vesszük az ilyen értékek min-át (maxmin következtetés). Ez lesz az a szint, amivel a konklúzió halmaz tagsági függvényét le kell nyesni. Az összes kiértékelhető szabály ily módon lenyesett konklúzió tagsági függvényét max művelettel másoljuk össze és meghatározzuk az eredő tagsági függvény súlyponti koordinátáját.

12. Jelentsen (a1,a2,a3,a4) egy olyan fuzzy halmazt, melynek tagsági függvénye _a1_-tol _a2_-ig lineárisan 0-tõl 1-ig nõ, _a2_-tõl _a3_-ig 1 értékû, _a3_-tól _a4_-ig viszont 1-tõl 0-ig lineárisan csökken.

Fõzési receptet fogunk fuzzy következtetéssel modellezni, hogy mennyire édesítsük meg az ételt, ha már benne van a só és a paprika. Vezessük be a következõ fuzzy halmazokat:

_ Kevésbé sós: (0 0 0.5 1)_ _ Sós: (0.5 0.75 1.25 1.5)_ _ Nagyon Sós: (1 1.5 2 2) gramm só skála felett_

Kevésbé Paprikás: (0 0 1 5) _ Paprikás: (1 3 6 9)_ _ Erõsen Paprikás: (4 8 10 10) gramm kalocsai paprika skála felett_

_ Keveset édesíteni: (0 0 20 50)_ _ Mértékkel: (20 30 40 50)_ _ Jócskán édesíteni: (20 50 80 80) gramm cukor skála felett_

Főzési szabályok: _ 1. Ha az étel nagyon sós, de kevésbé paprikás, akkor jócskán kellene édesíteni._ _ 2. Ha az étel sós és ráadásul paprikás, akkor csak mértékkel._ _ 3. Ha az étel kevésbé sós, de erősen paprikás, akkor jócskán kellene édesíteni._ _ 4. Ha az étel kevésbé sós, ugyanúgy kevésbé paprikás, akkor keveset kell édesíteni._ _ 5. Ha az étel nagyon sós és erősen paprikás, akkor szintén keveset._

Az ételben 1.4 g só és 3 g paprika van. Mennyi cukrot adjunk hozzá ? (6 pont)

Tervkészítés

IIII 13. Hogyan néz ki a tervkészítési eljárásnál alkalmazott kezdeti (zérus) terv? A kezdeti terv a Start és a Cél fiktív cselekvésekből áll össze és a rendeltetése a probléma definiálása a tervkészítő algoritmus számára. A Start cselekvésnek csak következményei vannak – ezek írják le a kiinduló állapotot. A Cél cselekvésnek csak előfeltételei vannak – ezek írják le a kívánatos célállapotot. Mi az információtartalma és mi történik vele a tervkészítési eljárás során ? A kezdeti terv folyamatosan bővül (az új cselekvések hozzáadásával) és módosul (a kényszerek és rendezések bevezetésével), úgy, hogy a tervkészítő az eddig még nem teljesített előfeltételekre „vadászik”. Ha az ilyen előfeltételt nem tudja már találni, akkor a terv előállt.

III 14. Feltételes tervkészítésnél mi a kontextus és mi a kontextusok szerepe ? Egy kontextus a hiányzó információ valamely változatával előállt problémaleírás. A tervkészítő mindegyik kontextushoz (minden eshetőségre) készít egy teljes és konzisztens tervet. A kontextus feladata körülhatárolni a valóság azt a változatát, amiben a terv egy jó terv lesz.

Hány kontextus létezik egy olyan feladatnál, ahol 2 literálból álló információ hiányzik a tervkészítésekor?

Az N db bináris értékű literál esetén 2^N érték kombináció képzelhető el és annyi kontextus létezik.

II 13. Mi az un. hierarchikus tervkészítés alapgondolata, miért jónak tűnik az ötlet, milyen problémákra lehet számítani és mi a lehetséges megoldásúk ? Elemezze a hierarchikus tervkészítésben rejlő előnyöket és hátrányokat ! _ A hierarchikus tervezés megkíséri mérsékelni a tervkészítés bonyolultságát úgy, hogy a problémát több absztrakciós szinten ábrázolja. Így nem kell mindjárt a közvetlenül végrehajtható, de nagy számban lévő cselekvésekkel dolgoznunk. Minél absztraktabb a szint, így általánosabbak az cselekvések, kevesebb (általánosított) feltételhez vannak kötve és a tervkészítés egyszerűbb._ _Egy adott szinten bevezetett absztrakt cselekvés az alsó szinten egy egész résztervnek felel meg. A tervkészítés így sokkal egyszerűbb, mert egy absztrakt terv egyfajta ’vázat’ jelent az alsó szinten folyó tervkészítési tevékenység számára és nem kell annyi cselekvési szekvenciaváltozatot előállítani és ellenőrizni. _ _ A probléma nyilvánvalóan az, hogy minden absztrakt cselekvéshez elő kell készíteni annak megfelelő résztervet, ill. terveket. Az is probléma, hogy a bonyolultság igazi letöréséhez biztosítani kellene a terv hierarchiában az un. felfelé és lefelé való megoldhatóságot. _

14. Mi a közelítő hierarchikus tervkészítés gondolata, miért értelmes gondolat ez ? _ Ez egy alkalmas megoldás a teljes kiépítettségű hierarchikus tervkészítés bajaira. Ha a résztervek hierarchiáját megfogalmazni és előre megtervezni nehéz, akkor vezessük be a ’normál’ tervkészítés esetén az előfeltételek hierarchiáját, valamilyen fontosság szerint. Ezek után a tervkészítő csakis az aktuálisan beállított szinthez tartozó feltételeket vizsgálja és a tervhez csatolt cselekvésekkel kezeli le. Ha az adott szinthez a feltételek elfogynak, következő szintre kapcsol át._ _ Értelmes, mert így is érvénysül az, hogy egy általánosabb terv ’vázat’ jelent a későbbi gazdagabb terv számára, így annak előállítása nem 0-ból indul. Előnye, hogy nem kell előre megtervezni a tervhierarchiát, viszont a feltételek hierarchiáját gondosan végig kell fontolni._

II 7. Milyen előnyt jelent a részben rendezett terv a teljesen rendezett tervhez képest? Hogy az utólagos rendezésénél olyan másodlagos szempontok kielégítését is lehet figyelembe venni, amiket formálisan a tervkészítésekor (pl. komplexitás miatt) nem ábrázoltunk.

II 11. A részben rendezett tervkészítésnél mi az üres terv felépítése és az információ tartalma?

12. Mi az un. STRIPS féle operátor modell, milyen elemekből áll? (2 pont) Operátor neve, előfeltételek, következmények

11. Mit fenyegetnek a tervbeli fenyegetések ? Mit jelent a hátramozdítás, ill. előremozdítás a tervbeli fenyegetések feloldásánál? Az egyes cselekvésekhez szükséges, már biztosított logikai előfeltételek további fennállását. A két mozgatás a fenyegető cselekvést a védett előfeltételt előteremtő és felhasználó cselekvések lánca elé, mögé helyezi.

11. Magyarázza meg, hogy (a részben rendezett) tervkészítésekor, mi célt szolgálnak a védett kapcsolatok és milyen módon biztosítani lehet azok sérthetetlenségét.

8. A tervkészítők jellemzésének számos módja van. Fejtsük ki a következő tulajdonságpárokra, hogy mit jelentenek, és a rájuk vonatkozó választás hogyan befolyásolja a tervkészítő hatékonyságát és teljességét! (4 pont) Szituációs tér – tervtér: lehetséges szituációk tere, ill. lehetséges tervek tere (kiinduló áll.: részleges terv; finomító és módosító operátorok) Progresszív – regresszív: _progresszív: előre keresés, regresszív: visszafele keresés (célállapottól) _ Teljesen rendezett - részben rendezett.

Logikai ábrázolásban hogyan lehet megoldani a tervkészítésre jellemző dinamikus robotkörnyezet problémáját és mi az alapvető hátránya ennek a megoldásnak ? _A szituációkalkulus bevezetésével. Baj a komplexitás, félig eldönthetőség, [semmi,terv] is egy jó terv. _ Minden a,s Van(T,Eredm(a,s)) [(a=Vesz(T)ÉSHely(ÉlelmB,s)] V Van(T,s) _Minden s Eredm’([],s)=s_ Minden a,t,s Eredm’([a|t],s)=Eredm’(t,Eredm(a,s))

Mit garantál a formálisan helyes tervkészítési eljárás és mit nem ? Értékelje ennek a módszernek gyakorlati használatát ! A teljes és konzisztens terv megtalálását garantálja.

2. Legyen adva a következő tervkészítési probléma:

Megy: E: hely(itt) K: hely(ott) $\wedge$ $\neg$ hely(itt) Vesz: E: elad(aru, bolt) $\wedge$ hely(bolt) K: van(aru) Kölcsönkér: E: $\neg$ elad(aru, bolt) K: van(aru) Betelefonál: E: hely(Otthon) K: tudja(„elad(Videomagno, Tesco)” logikai értékét) Legyenek továbbá: Kezdeti állapot: hely(Otthon) Célállapot: van(Videomagno) $\wedge$ hely(Otthon)

A tervkészítés melyik esetéről van itt szó? Milyen tervet (tervgráfot) készít el a tervkészítő? (a cselekvéseket a tervhez való hozzáadásuk sorrendjében részletezze)

_Ha a tervkészítő szokás szerint a cél ki nem elégített feltételeivel kezd foglalkozni, akkor a ’Vesz’ beszúrása után rájön, hogy az ’elad’ feltételről nem tud semmit, így a ’Vesz’ csak akkor jó, amennyiben igaz az ’elad’. Ez a feltételes tervkészítés esete. Ezek után az algoritmus úgy halad tovább, hogy az üres tervben a Cél cselekvés mellé ’elad=igaz’ kontextust ír és az ’elad’-ot igaznak feltételezve befejezi a terv erre az esetre vonatkozó ágát (Vesz, Megy(Tesco-ba), Megy(Otthon) cselekvések beszúrásával és esetleges rendezésével). Majd beszúrja a tervbe az információt begyűjtő cselekvést (Betelefonál), amelynek egyik kimeneti ága biztosítja az ’elad’ feltételt. Ezek után kreál egy új (komplemens) kontextust és Célcselekvést az ’elad=hamis’ esetére és kibővíti a tervet ezzel a feltételes ággal (Kölcsönkér). _ _ A szükséges rendezési kényszerekkel a terv:_

_ $\Rightarrow$ Megy(Tesco) $\Rightarrow$ Vesz $\Rightarrow$ Megy(O) $\Rightarrow$ Cél/ elad=igaz_ _ Start $\Rightarrow$ Betelefonál $\Rightarrow$ _ _ $\Rightarrow$ Kölcsönkér $\Rightarrow$ Cél/ elad=hamis_

12. Dolgozzuk át az előző vizsga tervkészítési feladatát, hogy alkalmas legyen a közelítő hierarchikus tervkészítés kipróbálásához, azaz rendeljünk fontossági szinteket az egyes előfeltételeknek ! Legyenek adva a következő cselekvések (előfeltételei és következményei, figyelem a változók kisbetűsek !): Megy: E: (1) hely(itt) K: hely(ott) $\wedge$ $\neg$ hely(itt) Vesz: E: (1) elad(aru,bolt) (2) van(KreditKártya) (3) hely(bolt) K: van(aru) Elhoz: E: (1) otthonvan(x) (2) hely(otthon) K: van(x) Legyenek továbbá: Kezdeti állapot: hely(Otthon) $\wedge$ elad(Videomagno, Tesco) $\wedge$ otthonvan(KreditKártya) Célállapot: (1) van(Videomagno) (2) hely(Otthon)

Mi a számok jelentése és milyen a tervkészítés általános vezérlési sémája ? Magyarázza meg, hogy ebben a konkrét esetben a tervkészítés hogyan fog haladni ? A tervkészítő milyen lépést fűzi be a tervbe elsőnek ? Másodiknak ? Harmadiknak ? Miért ?

A számok a bevezetett hierarchia szinteket jelentik. A tervkészítő beállítja a legmagasabb hierarchia szintet és a többi feltételt figyelmen kívül hagyja. Az így értelmezett célok és cselekvések mellett elkészíti a tervet. Most a következő szint következik a feltételek bővítésével. A korábban „kész” tervben új, ki nem elégített feltételek jelennek meg, és a tervkészítő újra beindul és az azokhoz beilleszti a szükséges cselekvéseket. Az eljárás addig folytatódig, amíg vannak még hierarchia szintek.

Hierarchia szint = 1: _Megy: E: hely(itt)_ _ K: hely(ott) $\wedge$ $\neg$ hely(itt)_ Vesz: E: elad(aru,bolt) _ K: van(aru)_ Elhoz: E: otthonvan(x) _ K: van(x)_ Kezdeti állapot: _ hely(Otthon) $\wedge$ elad(Videomagno, Tesco) $\wedge$ otthonvan(KreditKártya)_ Célállapot: _van(Videomagno) _ Egyetlen előfeltétel van, amivel kell foglalkozni (van) és ehhez a tervbe be kell fűzni a Vesz-t. A StartVeszCel terv készen van, nincs benne semmi határozatlan.

Hierarchia szint = 2: _Megy: E: hely(itt)_ _ K: hely(ott) $\wedge$ $\neg$ hely(itt)_ Vesz: E: elad(aru,bolt) $\wedge$ van(KreditKártya) _ K: van(aru)_ Elhoz: E: otthonvan(x) ) $\wedge$ hely(otthon) _ K: van(x)_ Legyenek továbbá: _Kezdeti állapot:_ _ hely(Otthon) $\wedge$ elad(Videomagno, Tesco) $\wedge$ otthonvan(KreditKártya)_ Célállapot: _ van(Videomagno) $\wedge$ hely(Otthon)_ a teljesítetlen előfeltétel most a van(KreditKartya) (a többi a kezdeti állapotban teljesül) és ehhez a tervbe be kell fűzni az Elhoz-et.

A harmadik hierarchia szinten bejön a „boltban lenni” feltétel, amit a Megy beszúrásával lehet biztosítani (megy a boltba), és mivel ettől elszáll a célbeli hely(Otthon), be kell szúrni egy másik Megy-et is (megy haza).

10. Hogyan lehet figyelembe venni a tervkészítésnél a véges erőforrásokat ? Kísérelje meg kibővíteni ilyen irányba az eredeti tervezési feladatot úgy, hogy a Megy-hez legyen szüksége benzinre és a Vesz-hez viszont pénzre.

Pl. így: _Megy: E: hely(itt) c $\wedge$ (Liter(Benzin)  Fogyasztas  Tav(ott,itt))_ K: hely(ott) $\wedge$ $\neg$ hely(itt) $\wedge$ *(Benzin  Benzin - Fogyasztas  Tav(ott,itt))* _Vesz: E: van(KreditKártya) $\wedge$ elad(aru,bolt) $\wedge$ hely(bolt) _ _ * $\wedge$ Van(Penz) $\wedge$ (Forint (Penz)  Ar(aru))*_ K: van(aru) ) $\wedge$ *(Penz  Penz - Ar(aru))*

_Elhoz: E: otthonvan(x) $\wedge$ hely(Otthon) _ _ K: van(x)_

Kezdeti állapot: _ hely(Otthon) $\wedge$ elad(Videomagno, Tesco) $\wedge$ otthonvan(KreditKártya)* *_

Célállapot: _hely(Otthon) $\wedge$ van(Videomagno) _ ahol Liter, Forint, Tav és Ar alkalmas függvények, Benzin, Penz aritmetikai változók és Fogyasztas egy aritmetikai konstans. Azontúl: _*(Benzin = 100) $\wedge$ (Penz = 200000) $\wedge$ (Fogyasztas = 6)*_

(Igényesebb megoldás, ha a fogyó erőforrások pótlásáról is gondoskodunk további cselekvések definiálásával (pl. ’Felvesz’ pénzt az automatából, ’Befizet’ a számlára, stb., ill. további cselekvésláncok figyelembevételével, pl. ’Megy’ benzinkútra, ’Vesz’ benzint, stb.).)

12. Hogyan lehet figyelembe venni a tervkészítésnél a véges erőforrásokat ? Kísérelje meg kibővíteni ilyen irányba az eredeti tervezési feladatot úgy, hogy a Megy-hez és a Vesz-hez legyen szüksége egy bizonyos időtartamra. Megy: E: hely(itt) K: hely(ott) $\wedge$ $\neg$ hely(itt) Vesz: E: van(KreditKártya) $\wedge$ elad(aru,bolt) $\wedge$ hely(bolt) K: van(aru) Elhoz: E: otthonvan(x) $\wedge$ hely(Otthon) K: van(x) Kezdeti állapot: hely(Otthon) $\wedge$ elad(Videomagno, Tesco) $\wedge$ otthonvan(KreditKártya) Célállapot: hely(Otthon) $\wedge$ van(Videomagno)

Pl. így: Megy: E: hely(itt) c $\wedge$ (VanIdő(t)  Tav(ott, itt) / Sebesség) K: hely(ott) $\wedge$ $\neg$ hely(itt) $\wedge$ (t  t - Tav(ott, itt) / Sebesség)

_Vesz: E: van(KreditKártya) $\wedge$ elad(aru,bolt) $\wedge$ hely(bolt) _ _ * $\wedge$ VanIdő(t) $\wedge$ (VanIdő(t)  VásárlásIdeje(aru, bolt))*_ _ K: van(aru) ) $\wedge$ *(t  t - VásárlásIdeje(aru, bolt))*_

_Elhoz: E: otthonvan(x) $\wedge$ hely(Otthon) _ _ K: van(x)_

Kezdeti állapot: _ hely(Otthon) $\wedge$ elad(Videomagno, Tesco) $\wedge$ otthonvan(KreditKártya)_ * $\wedge$ (t = Óra(2)) * _Célállapot:_ _hely(Otthon) $\wedge$ van(Videomagno) _ ahol VanIdő, Tav, Óra és VásárlásIdeje alkalmas függvények, Sebesség egy aritmetikai konstans.

9. Legyenek adva a következő cselekvések (előfeltételei és következményei): Megy: E: hely(itt) K: hely(ott) $\wedge$ $\neg$ hely(itt) Vesz: E: van(KreditKártya) $\wedge$ elad(áru, bolt) $\wedge$ hely(bolt) K: van(áru) Elhoz: E: otthonvan(x) $\wedge$ hely(Otthon) K: van(x) Legyenek továbbá: Kezdeti állapot: hely(Otthon) $\wedge$ elad(Videomagno, Tesco) $\wedge$ otthonvan(KreditKártya) Célállapot: hely(Otthon) $\wedge$ van(Videomagno)

_Tervkészítésekor milyen lépést próbál ki az algoritmus legelőször ? Fejtse ki részletesen, mi fog történni, ha a tervbe befűzött második lépés a ’Megy’ (Tesco-ba) ? _

Megoldás: _a. Az üres terv (Start és Cél lépések) Start következményeként tartalmazza a probléma kezdeti állapotát:_ hely(Otthon) $\wedge$ elad(Videomagno, Tesco) $\wedge$ otthonvan(KreditKártya) _és a Cél lépés előfeltételeként a probléma célállapotát:_ _ hely(Otthon) $\wedge$ van(Videomagno)_ b. A tervkészítő keresi a ki nem elégített előfeltételeket és talál is egyet (van(Videomagno)). Ehhez megkeresi az azt biztosító cselekvést (Vesz – a van(Videomagno) miatt). _c. Az új cselekvés új ki nem elégített előfeltételeket hoz be a tervbe (hely(Tesco)), amihez a tervkészítő új cselekvést választ be (Megy – a hely(Tesco) miatt)._ d. Következő előfeltétel lehet a van(KreditKártya), amihez kellene az Elhoz, de a tartózkodási hely miatti problémát rendezni kell: _ az Elhoz-ot a Megy-elé kell beszúrni, mert különben a hely(Otthon) feltétellel lesznek gondok._

3. Legyenek adva a következő cselekvések (előfeltételei és következményei): Megy: E: hely(itt) K: hely(ott) $\wedge$ $\neg$ hely(itt) Vesz: E: van(KreditKártya) $\wedge$ elad(áru, bolt) $\wedge$ hely(bolt) K: van(áru) Elhoz: E: otthonvan(x) $\wedge$ hely(Otthon) K: van(x) Legyenek továbbá: Kezdeti állapot: hely(Otthon) $\wedge$ elad(Videomagno, Tesco) $\wedge$ otthonvan(KreditKártya) Célállapot: hely(Otthon) $\wedge$ van(Videomagno)

Tervkészítésekor milyen lépést próbál ki az algoritmus legelőször ? Fejtse ki részletesen, mi fog történni, ha a tervbe befűzött második lépés a ’Megy’ (Tesco-ba) ?

Megoldás: a. Az üres terv (Start és Cél lépések) Start következményeként tartalmazza a probléma kezdeti állapotát: hely(Otthon) $\wedge$ elad(Videomagno, Tesco) $\wedge$ otthonvan(KreditKártya) és a Cél lépés előfeltételeként a probléma célállapotát: hely(Otthon) $\wedge$ van(Videomagno) b. A tervkészítő keresi a ki nem elégített előfeltételeket és talál is egyet (van(Videomagno)). Ehhez megkeresi az azt biztosító cselekvést (Vesz – a van(Videomagno) miatt). c. Az új cselekvés új ki nem elégített előfeltételeket hoz be a tervbe (hely(Tesco)), amihez a tervkészítő új cselekvést választ be (Megy – a hely(Tesco) miatt). d. Következő előfeltétel lehet a van(KreditKártya), amihez kellene az Elhoz, de a tartózkodási hely miatti problémát rendezni kell: az Elhoz-ot a Megy-elé kell beszúrni, mert különben a hely(Otthon) feltétellel lesznek gondok.

13. Lehet-e szituáció kalkulusban terveket készíteni? A gondolatot

$\forall$ x $\neg$ Szoba(x) $\wedge$ $\neg$ Piros(x) $\Rightarrow$ Szoba(Eredményez(Bemegy(x)) *alapján fejtse ki!

Hogyne, volt is előadáson is egy ilyen példa. A fennti állítás egy hatás axióma, amiből egy konkrét, szituáció kalkulussal leírt feladat esetében, többet kell felírni (ugyanúgy a keret axiómákból is). Ezeket az állításokat természetesen át kell írni klóz alakba. Egy konkrét feladat leírásánál megjelenik a kiinduló szituáció jelentő konkrét konstans, mondjuk *S_0*. Rezolúciós bizonyítás során ez a konstans előbb-utóbb be lesz helyettesítve az Eredményez(Bemegy(S₀)) –be, aminek értéke szintén egy szituációs konstans (Eredményez egy funktor, szituációból szituációt számol ki). Ez a konstans is előbb-utóbb behelyettesítődik az Eredményez(Cselekvés(…)) kifejezésekbe és így a bizonyítás során a behelyettesíthető konstansok alakja egyre jobban „kinyúló”

*Eredményez(Cselekvé1 (Eredményez(Cselekvés2 (Eredményez(Cselekvés3 (…))))* alakot kap.

A rezolúciós bizonyítás végeztével az üres rezolúció eléréséhez szükséges behelyettesítés alapja

*S_N = Eredményez(Cselekvé1 (Eredményez(Cselekvés2 (… (Eredményez(Cselekvés-első (S₀)…)))*

lesz, ahol az S_N a véghelyzetre (feladatmegoldása) jellemző szituációs konstans, annak definiciójában szereplő cselekvéslánc pedig a hozzá vezető és a megoldás feltételeit teljesítő cselekvési terv.

5. Hogyan kell kiegészíteni és miért az ábrán látható részleges tervet? Mi a Honnan és Hová változók lehetséges értéke és mik a hiányzó kauzális linkek? (6 pont)

A Hova = Otthon kell, hogy legyen, azaz Honnan csak Bolt lehet. Akkor viszont a Megy (*Bolt* – *Otthon*) veszélyezteti a Megy – Bolt – Vesz kauzális linket. A megoldás a Megy (*Bolt* – *Otthon*) lépés elmozdítása (kényszerű rendezés bevezetése) a Vesz utánra.

Döntési fa

II 7.Rajzoljon fel egy döntési fát annak meghatározására, hogy elinduljunk-e vagy sem az útkereszteződésben, ha a lámpa éppen most váltott zöldre?

Megoldás: fontoljuk meg pl. a következő teszteket, nagyjából az alábbi sorrendben: Sor elején állunk ? _Előttünk a kocsi elindult-e ?_ Keresztbe állnak-e ? _Van-e keresztforgalom ?_ Mennek-e a zebrán gyalogosok ? _Fordulunk-e a kereszteződésben ?_ Van-e szembe forgalom ? _Jön-e biciklista ?_

II 17. Milyen célt szolgál a döntési fa ? _ Lehetőséget teremt, hogy az egy- vagy többértékű attribútumhalmazzal leírt példákból nyerjük ki azok tömör logikai leírását, faszerűen ágyazott logikai tesztek, azaz logikai függvény alakjában._

Egy döntési fa szerkesztésénél a további elágazást az _A_{1_}, ill. _A_{2_} attribútum teszttel lehet folytatni. A + és a – a fa adott helyén értelmezett pozitív és a negatív példát jelenti.

Az _A_{1_} attribútum teszt után Az _A_{2_} attribútum teszt után

+ + + + - - - - + + + + - - - -

+ + - - + + - - + + + - + - - -

Számítsa ki a Nyereség(A₁) és a Nyereség(A₂) értékeit. A számításnál használja I(1/2,1/2)=1 bit, I(0,1)=0 bit és _I(1/4,3/4)=0.8 _bit értékeket. Melyik tesztet építene be a fába és miért ? _ Az attribútum nyeresége a fa információ tartalma az attribútumig, levonva az attribútum teszt utáni fa átlagos információ tartalmát (ld. könyvbeli képlet)._ Itt A₁ esetén: I(1/2,1/2) – (1/4 x I(0,1) + 1-4 x I(1,0) + 1/2 x I(1/2,1/2)) = 0.5 _és_ A₂ esetén: I(1/2,1/2) – (1/2 x I(3/4,1/4) + 1/2 x _I(3/4,1/4)) = 1 – 1/2 x 0.8 – 1/2 x 0.8 = 0.2_ Azaz az A₁ –et kell választani.

17. Milyen célt szolgál a döntési fa ? (2 pont) Egy döntési fa szerkesztésénél a további elágazást az _A_{1_}, ill. _A_{2_} attribútum teszttel lehet folytatni. A + és a – a fa adott helyén értelmezett pozitív és a negatív példát jelenti.

Az _A_{1_} attribútum teszt után Az _A_{2_} attribútum teszt után

+ + + + - - - - + + + + - - - -

+ + - - + + - - + + + - + - - -

Számítsa ki a Nyereség(A₁) és a Nyereség(A₂) értékeit. A számításnál használja I(1/2,1/2)=1 bit, I(0,1)=0 bit és _I(1/4,3/4)=0.8 _bit értékeket. Melyik tesztet építene be a fába és miért ? (4 pont)

10. Egy döntési fa tanulásánál a tanító példahalmaz 5 pléldából áll. A példaattributumok a, b, és c, a d a besorolás oszlopa. Információ mérlegelése alapján döntse el, hogy a fát hogyan építené meg. (6 pont)

a b c d

x1 I I N N x2 N I N I x3 N I I I x4 N N I N x5 I N N N

A részpéldák aránya: _a I p/n 0/2_ _ N p/n 2/1_ b I p/n 2/1 _ N p/n 0/2_ c I p/n 1/1 _ N p/n 1/2_

A teljes fa info tartalma: If = I(2/5, 3/5) = -2/5 lg2(2/5) – 3/5 lg2(3/5) = 0.971 _A nyerességek: Ny(a) = If – (2/5 I(0,1) + 3/5 I(2/3, 1/3))_ _ Ny(b) = If – (3/5 I(2/3,1/3) + 2/5 I(0, 1))_ _ Ny(c) = If – (2/5 I(1/2,1/2) + 3/5 I(1/3, 2/3))_ ahol I(2/3, 1/3) = -2/3 lg2(2/3) – 1/3 lg2(1/3) = 0.9183 _azaz Ny(a) = 0.971 – 3/5 x 0.9183 = .42_ _ Ny(b) = 0.971 – 3/5 x 0.9183 = .42_ _ Ny(c) = 0.971 – 2/5 - 3/5 x 0.9183 = .02 _ a fár a-ból és b-ből kell építeni:

példahalmaz: +(x2 x3) –(x1 x4 x5) _teszt1 = a_ _ a = I +(-) -(x1 x5) NEM_ _ a = N +(x2 x3) -(x4) tovább_ teszt2 = b _ b = I +(x2 x3) -(-) IGEN_ _ b = N +(-) -(x4) NEM_

3. Egy döntési fa tanulásánál a tanító példahalmaz 6 példából áll. A példaattributumok *a* és *b*, és *c* a besorolás oszlopa. Információ mérlegelése alapján döntse el, hogy a fát hogyan építené meg (6 pont)?

=== ===x1=== ===x2=== ===x3=== ===x4=== ===x5=== ===x6

a* 0 1 2 0 1 2
b* 0 0 0 1 1 1
c* N N I I N I

A teljes példahalmaz információtartalma: I = I(3/6,3/6) = 1 _Ny(a) = I – (2/6  I(1/2,1/2) + 2/6  I(0,1) + 2/6  I(1,0)) =_ _ 1 – (1/3  1 + 1/3  0 + 1/3  0 = 2/3 = 0.66_ Ny(b) = I – (3/6  I(2/3,1/3) + 3/6  I(1/3,2/3)) = _ 1 – (1/2  I(2/3,1/3) + 1/2  I(1/3,2/3)) =_ _ 1 –I(2/3,1/3) =_ _ 1 – (-2/3 log₂(2/3) – 1/3 log₂(1/3)) =_ _ 1 + 2/3 log₂(2/3) + 1/3 log₂(1/3)) =_ _ 1 + 2/3 - 2/3 log₂3 - 1/3 log₂3 = 5/3 - log₂3 = 0.0817_ azaz az *a* teszttel kell kezdeni.

Tanulás

Soroljon nehany gepi szimbolikus tanulasi modszert !

Induktív tanulás
- Logikai kifejezések tanulása
  - Döntési fák
  - Verzió tér
- Általános logokai leírás tanulásaű
  - A pillanatnyilag legjobb hipotézis keresése
  - Legkisebb megkötés elvű keresés
  - Döntési listák tanulása
Neurális hálók, Valószínűségi hálók

Vagy:

Felügyelt tanulás
Megerősítéses tanulás

_Felügyelet nélküli tanulás_

IIIII 16. Vesse össze a Pillanatnyi Legjobb Hipotézis tanulás és a Verzió terek módszer előnyeit és hátrányait. _ A PLH tanulás egyetlen egy hipotézissel dolgozik, amit a példáknak megfelelően formál (szűkítés, általánosítás). Egy hipotézismódosító döntés után zsákutcába is kerülhet, pl. úgy, hogy később semmilyen módosítás nem lesz lehetséges, hogy az új példát befogadhassa ÉS a régi példákkal maradjon konzisztens. Ilyenkor a hipotézismódosító fában vissza kell lépni és új lehetőségekkel próbálkozni. A verzió teres tanulás az összes konzisztens hipotézist tartja számon és a példákkal ezt a halmazt folyamatosan szűkíti. Tehát a PLH kevesebbet adminisztrál, viszont tévedhet és visszalépve többet kell keresni, és főleg módosításonként a hipotézist az összes eddigi példával összevetni. A VT többet adminisztrál, de visszalépnie nem kell._

IIIII 2. Magyarázza meg, hogyan lehet szimbolikus (logikai) kifejezéseket tanulni szimbolikus példák alapján (Hamis Pozitív, Hamis Negatív példák szerepe, formáló hatásuk a hipotézisre).

_ A szimbolikus kifejezésekhez is találni lehet az azokat formáló módosító műveleteket. Azok megválasztását pedig az elemzett példákkal lehet vezérelni. A hamis pozitív példa azt jelenti, hogy a hipotézis logikailag ’túl bő’, többet ismer fel, mint kellene, azaz szűkíteni kell (feltételeket hozzáadni). A hamis negatív példa azt jelenti, hogy a hipotézis ’túl szűk’, általánosítani, kiterjeszteni kell (feltételeket levenni, vagy diszjunkciókat hozzáadni). _

5. Megtanulható-e szimbolikus példákból egy általános logikai függvény? Indokolja meg!

Nem, hiszen az általános (ítélet)logikai függvény tanulása esetén a hipotézistér számossága duplán exponenciális, így logaritmusát véve (képlet!!!!) sem kapjuk az exponenciálisnál kisebb szükséges példaszámot.

III 15. Mi az induktív tanulás általános folyamata ? Az induktív tanulás a példák alapján történő tanulás, ahol a tanító halmaz példáit dolgozzuk fel (rekurzív módon, vagy sem), hogy egy hipotézist (függvényközelítést) felállíthassunk (a tanítóhalmaz példáinak egy általánosítása). A hipotézist a teszthalmazhoz tartozó példáival ellenőrizzük.

III Milyen fogalom mondható megtanulhatónak ? _ Amihez a probléma függvényében (a tanult hipotézis hibája, a rossz hipotézis elfogadásának a valószínűsége, stb.) a szükséges példák száma nem éri el az exponenciális szintet._

III Mi a tanulásnál a zaj és az elfogultság ?

A zaj az azonos felépítésű, de nem azonos besorolású példák, amelyek a tanulás folyamatát megzavarják. _Az elfogultság a példákkal konzisztens, több lehetséges felépítésű hipotézis megválasztásának a szempontjai (pl. legyen minél egyszerűbb)._

8. Mi az un. megerősítéses tanulás és miben áll a megvalósításának fő nehézsége? A nehézség a megerősítés/besorolás késői érkezése és így bizonytalanság, hogy melyik cselekvés mit ér. Ehhez a megerősítést időben hátrafelé kell terjeszteni, ami matematikailag nehezen kiértékelhető összefüggésekhez vezet.

9. A megtanult fogalom definícióján túlmenően (ha sikerül), milyen információt szolgáltat még a verziós teres tanulás? (4 pont) A két tér (S és G) végső állapota jelzi a példahalmaz tanításra való alkalmazhatóságát.

15. Foglalja össze a verziós teres tanulás lényegét, előnyeit és hátrányait!

15. Foglalja össze a megerősítéses tanulás lényegét és alapvető módszerét!

9. Mi a megerősítéses tanulás alapgondolata és az alapmódszere ? (4 pont)

10. Miért azt mondják, hogy a logikai függvények teljes általánosságban gyakorlatilag nem tanulhatók meg? (3 pont)

4. Egy megerősítéses módon tanuló ágens a BME épületeit járja és számára a legelőnyösebb utat tanulja. Tegyük fel, hogy minden épületben egyetlenegyszer járt már, kivéve az R-ben, ahol többször fordult meg, valamint, hogy eddig minden épület hasznosságértéke azonos. Most az ágens egy új felfedező körútra indult. D-ből indult ki, majd áthaladt az összes épületen egyszer, végül az E épületben kötött ki, ahol egy egységnyi dicséretben részesült. A szükséges számítások után az R épület hasznosságát az ágens nagyobbnak / kisebbnek fogja látni a többi épületéhez képest? Miért?_ _

_Ha valahol többször volt, a hely (környezeti állapot) hasznossága mégis ugyanannyi, mint azé a helyé, ahol kevesebbszer volt (akár csak egyetlen egyszer), akkor világos, hogy egy olyan tanító szekvencia után, amely az összes helynek azonos megerősítést jelent (ha mindenhol csak egyszer haladt át és csak a végén kapta meg a megerősítést), a frekventált helynek a hasznossága kisebb mértékben nő, mint egy kevésbé frekventált hely esetében. Magyarán az R épület hasznosságát az ágens kisebbnek fogja látni. _ _ Képlettel: _ _új hasznosság = _ régi hasznosság + (adott helyre eső megerősítés – régi hasznosság) / felfrissített frekventáltság

4. Egy ágens megerősítéses tanulással tanul a BME-n járni az épületek között, hogy a számára a legelőnyösebb utat megtanulhassa. Tegyük fel, hogy minden épületben már kétszer volt, kivéve az R-ben, ahol négyszer. Minden épület hasznosság értéke egységesen 0.6. Most egy új felfedező körútra indult. D-ből indult ki, majd áthaladt az R-en, T-n, H-n is. Végül az E épületben kötött ki, ahol egy egységnyi dicséretben részesült. Hogyan látja ezek után az ágens az egyes egyetemi épületeknek a hasznosságát ?

A példában az épületek a környezetállapotok. Az érintett épületek esetén az ágens a kapott jutalmat a meglátogatott épületekre visszavetíti _U_{i_} = _R_ + _U_{j _} értelmében. Mivel a D-R-T-H-E szekvencia mentén közben jutalmat nem kapott, minden _U_ érték 1 lesz. Most az ágens felfrissíti az épületek látogatottsági számát _N_(_épület_) = _N_(_épület_) + 1 és ezt követően az épületek (állapotok) hasznosságát _c_ szerint. Konkrétan: _hasznosság_{új_}(D) = _hasznosság_{régi_}(D) + (_U_(D) – _hasznosság_{régi_}(D))/_N_(D) = 0.6 + (1 – 0.6)/3 = 0.79 _hasznosság_{új_}(R) = _hasznosság_{régi_}(R) + (_U_(R) – _hasznosság_{régi_}(R))/_N_(R) = 0.6 + (1 – 0.6)/5 = 0.68 _hasznosság_{új_}(T) = _hasznosság_{régi_}(T) + (_U_(T) – _hasznosság_{régi_}(T))/_N_(T) = 0.6 + (1 – 0.6)/3 = 0.79 _hasznosság_{új_}(H) = _hasznosság_{régi_}(H) + (_U_(H) – _hasznosság_{régi_}(H))/_N_(H) = 0.6 + (1 – 0.6)/3 = 0.79 _hasznosság_{új_}(E) = _hasznosság_{régi_}(E) + (_U_(E) – _hasznosság_{régi_}(E))/_N_(E) = 0.6 + (1 – 0.6)/3 = 0.79 _hasznosság_{új_}(más) = _hasznosság_{régi_}(más) + (_U_(más) – _hasznosság_{régi_}(más))/_N_(más) = 0.6 + (0 – 0.6)/N = ... attól függően, hogy ott hányszor volt korábban

13. Megerősítéses tanulásnál tudjuk, hogy a környezet modellje:

===M_ij j= S₁ S₂ S_3 === i= S₁ 0 1/2 1/2 S₂ 1/2 0 1/2 S₃ 1/2 1/2 0 Adja meg az U(S₂) és az U(S₃) értékét, ha az U(S₁) értéke 1. Az R(S₁), R(S₂) és az R(S₃) értéke 0.

Az állandósult állapotban egy környezeti állapot hasznossága: _ U_k = R_k + j M_kj U_{j_}

Az egyenletrendszer tehát: _ U₁ = ½ U₂ + ½ U_{3_} _ U₂ = ½ U₁ + ½ U_{3_} _ U₃ = ½ U₁ + ½ U_{2_} Aminek, adott feltételek mellett, a megoldása: U₁ = 1, U₂ = 1, U₃ = 1

8. Hány példára van szükség a közelitőleg helyes induktív tanulásnál, ha a tanulandó hipotézis hibája kisebb legyen, mint 1%, az a valószínűség, hogy rossz hipotézist tanulunk legyen szintén kisebb, mint 1%, és a hipotézis tér számossága 2¹⁵ ?

Megoldás:  = 0.01,  = 0.01, H = 2¹⁵

alapján: m > 100*(ln100+15) $\simeq$ 2200

8. Hány példára van szükség a közelitőleg helyes induktív tanulásnál, ha a tanulandó hipotézis hibája kisebb legyen, mint 10%, az a valószínűség, hogy rossz hipotézist tanulunk legyen szintén kisebb, mint 10%, és a hipotézis tér számossága 2²⁰ ?

Megoldás:  = 0.1,  = 0.1, H = 2²⁰

alapján: m > 10*(ln10+20) $\simeq$ 250

_ _

16. VKH tanulás esetén a hipotézis tér ezer hipotézisből áll,  = 0.001. 10 példa feldolgozása milyen tanulási pontossághoz () elegendő?

_m  (1/ )(lg(1/)+lg(H) alapján _

_10  (1/ )(lg(1/0.001)+lg(1000) _ _10  6/ _ *  0.6*

16. VKH tanulás esetén a hipotézis tér 10 millió hipotézisből áll,  = 0.01. Ezer példa feldolgozása milyen tanulási pontossághoz () elegendő? (3 pont)

_1000  (1/ )(lg(1/0.01)+lg(10⁷) _ _1000  9/ _ *  0.009*

14. Ágens a pillanatnyi legjobb hipotézis módszerével tanul. Alábbi 6 példát kap. A kiinduló hipotézis az első példa logikai kifejezése. Írja le a tanulás folyamatát, azaz milyen a soron lévő példa (jó, HP, HN), mi a művelet (általánosítás, specializálás) és mi a pillanatnyi legjobb hipotézis alakja?

_ Hörcsög Tengeri Malac Kutya Nagy Példa jellege Művelet hipotézissel Hipotézis_

x1 I N N N + _x2 I N N I -_ x3 N I N I - _x4 N I N N +_ x5 N N I I - _x6 N N I N +_

A kiinduló hipotézis: H1(x) = x1 = Hörcsög(x) $\wedge$ $\neg$ Tengeri Malac(x) $\wedge$ $\neg$ Kutya(x) $\wedge$ $\neg$ Nagy(x)

Az első példa tehát már megvan. _Az x2 példa egy negatív példa és H1(x2) = Hamis, tehát ez is rendben van. _ _Az x3 példa egy negatív példa és H1(x3) = Hamis, tehát ez is rendben van. _ _Az x4 példa egy pozitív példa és H1(x4) = Hamis, tehát ez egy Hamis Negatív és valamit tenni kell a hipotézissel. A hipotézist általánosítani kell konjunkció elhagyásával, de úgy, hogy az új hipotézis az eddigi példákon jól viselkedjen. _ *H2(x) = $\neg$ Kutya(x) $\wedge$ $\neg$ Nagy(x)* _Az x5 példa egy negatív példa és H2(x5) = Hamis, tehát ez is rendben van. _ _Az x6 példa egy pozitív példa és H2(x6) = Hamis, tehát ez egy Hamis Negatív és valamit tenni kell a hipotézissel. A hipotézist általánosítani kell konjunkció elhagyásával, de úgy, hogy az új hipotézis az eddigi példákon jól viselkedjen. _ *H3(x) = $\neg$ Nagy(x)*

9. Ágens a pillanatnyi legjobb hipotézis módszerével tanul. Alábbi 5 példát kap. A kiinduló hipotézis a H1. Írja le a tanulás folyamatát

Fekete Nagy Kerek Milyen példa

x1 I N I + x2 N N N - x3 I I I + x4 N I N - x5 I N N +

A kiinduló hipotézis: H1(x) = x1 = Fekete(x) $\wedge$ $\neg$ Nagy(x) $\wedge$ Kerek(x)

_befutó példa, a tesztelés eredménye és a hipotézis módosítás_

x2 helyes negatív H2(x) = H1(x) = Fekete(x) $\wedge$ $\neg$ Nagy(x) $\wedge$ Kerek(x) _x3 HN általánosítás H3(x) = Fekete(x) $\wedge$ $\neg$ Nagy(x) _ _ nem jó, x3-t nem fogadja_ _ H3(x) = Fekete(x) $\wedge$ Kerek(x)_ x4 helyesen negatív H4(x) = Fekete(x) $\wedge$ Kerek(x) _x5 HN általánosítás H5(x) = Kerek(x)_ _ nem jó, x5-t nem fogadja el_ _ H5(x) = Fekete(x)_ kifogytunk a példákból, H5(x) minden példát jól sorolja be.

10. PAC tanulás esetén legalább hány tanító példára van szükség  = .1,  = .01 hibászintek és H = 10⁶ számosságú hipotézistér esetén? (3 pont)

m  1/ (lg 1/ + lg H ) = 10 (lg 100 + 6) = 80

17. Kik és mivel járultak a tárgy anyagához a fent látható urak?

K. Gödel – az elsőrendű logika teljessége, nemteljességi tétel L. Zadeh – a fuzzy logika megteremtője A. Turing – az első gép, az első MI megfontolások, Turing teszt

J__. Mccarthy – a Mesterséges Intelligencia fogalma, a LISP, az első deduktív módon működő intelligens rendszer gondolata, és sok más__

-- adamo - 2006.01.25.

Bejelentkezés

Keresés

Ágens környezete

Névterek

Több

Lapműveletek

Tartalomjegyzék

Keresés

Sepolia 0

Logika

_F T (F $\Rightarrow$ T) ( $\neg$ F $\Rightarrow$ $\neg$ T ) (F $\Rightarrow$ T) $\Rightarrow$ ( $\neg$ F $\Rightarrow$ $\neg$ T))_

_F T H (F $\Rightarrow$ T) ((F $\wedge$ H) $\Rightarrow$ T) (F $\Rightarrow$ T) $\Rightarrow$ ((F $\wedge$ H) $\Rightarrow$ T)_

_ NemMegy(Béla_

Klóz forma

Rezolúció

Elsőrendű logika

Ítéletkalkulus, szituációs kalkulus

TMS

Bizonytalan tudás

Valószínűségi hálók

Fuzzy

_A’_

Tervkészítés

Döntési fa

a b c d

Tanulás

Fekete Nagy Kerek Milyen példa

_befutó példa, a tesztelés eredménye és a hipotézis módosítás_

Navigáció

Navigáció

Egyetem

Wikieszközök

Wikieszközök

_0_	_1_	_0_	_1_	_1_	_1_	_1_
_0_	_1_	_1_	_0_	_1_	_0_	_1_
_1_	_0_	_0_	_1_	_0_	_0_	_1_
_1_	_0_	_1_	_0_	_1_	_0_	_1_

_0_	_1_	_0_	_1_	_1_	_1_	_1_
_0_	_1_	_1_	_0_	_1_	_0_	_1_
_1_	_0_	_0_	_1_	_0_	_0_	_1_
_1_	_0_	_1_	_0_	_1_	_0_	_1_

Bejelentkezés

Keresés

Ágens környezete

Keresés

Sepolia 0

Logika

_F T (F ⇒ {\displaystyle \Rightarrow } T) ( ¬ {\displaystyle \neg } F ⇒ {\displaystyle \Rightarrow } ¬ {\displaystyle \neg } T ) (F ⇒ {\displaystyle \Rightarrow } T) ⇒ {\displaystyle \Rightarrow } ( ¬ {\displaystyle \neg } F ⇒ {\displaystyle \Rightarrow } ¬ {\displaystyle \neg } T))_

_F T H (F ⇒ {\displaystyle \Rightarrow } T) ((F ∧ {\displaystyle \wedge } H) ⇒ {\displaystyle \Rightarrow } T) (F ⇒ {\displaystyle \Rightarrow } T) ⇒ {\displaystyle \Rightarrow } ((F ∧ {\displaystyle \wedge } H) ⇒ {\displaystyle \Rightarrow } T)_

_ NemMegy(Béla_

Klóz forma

Rezolúció

Elsőrendű logika

Ítéletkalkulus, szituációs kalkulus

TMS

Bizonytalan tudás

Valószínűségi hálók

Fuzzy

_A’_

Tervkészítés

Döntési fa

a b c d

Tanulás

Fekete Nagy Kerek Milyen példa

_befutó példa, a tesztelés eredménye és a hipotézis módosítás_

Navigáció

Wikieszközök

Eszközök

Kategóriák

_F T (F $\Rightarrow$ T) ( $\neg$ F $\Rightarrow$ $\neg$ T ) (F $\Rightarrow$ T) $\Rightarrow$ ( $\neg$ F $\Rightarrow$ $\neg$ T))_

_F T H (F $\Rightarrow$ T) ((F $\wedge$ H) $\Rightarrow$ T) (F $\Rightarrow$ T) $\Rightarrow$ ((F $\wedge$ H) $\Rightarrow$ T)_

_0_	_1_	_0_	_1_	_1_	_1_	_1_
_0_	_1_	_1_	_0_	_1_	_0_	_1_
_1_	_0_	_0_	_1_	_0_	_0_	_1_
_1_	_0_	_1_	_0_	_1_	_0_	_1_