Ágens

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

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

[TODO: elágazási tényezők]

MIVizsgaOsszefWikizalva

• Az intelligens rendszer fogalma Egy intelligens rendszer az, melynek teljesítőképessége az azonos számítási korlátokkal rendelkező informatikai rendszerek közül a legmagasabb.

• Ágens fogalma Az ágens "folyamatosan intelligens rendszer, mely környezetét folyamatosan figyeli, és átformálja céljai érdekében. (Egy ágens a környezetéből kiemelve nem ágens)

• Mi alapján lehet eldönteni hogy mi racionális (a célhoz közelebb vivő) egy adott pillanatban
  • a siker fokát mérő teljesítmény mérőszám
  • az ágens által megfigyelt észlelések sorozata
  • amit az ágens a környezetéről tud
  • cselekvések, amit az ágens képes végrehajtani

• Ideális racionális ágens Minden észlelési sorozathoz a bennük található tények és a beépített tudás alapján mindent megtesz, hogy a teljesítmény mérőszámot maximalizálja.(mert így lett tervezve)

• Az ágens architektúrájának szerepe
  • elérhetővé teszi az észleléseket az ágens programja számára
  • futtatja a programot
  • a cselekvéseket a beavatkozók felé továbbítja, amint azok létrejönnek.

• Az ágensek fajtái
  • Egyszerű, reflex szerű ágens
    • Egy feltétel-cselekvés táblázatot használ
    • problémái:
      • a táblaméret óriási
      • nehéz a táblát kitölteni a tervezőnek
      • rugalmatlan
      • még ha tanul is új bejegyzédseket, ez nagyon lassú
  • Ágens, ami nyomon követi a világot
    • belső állapottal rendelkezik, így meg tudja különböztetni a környezet azonos bemeneteit generáló, de lényegében különböző állapotait.Ehhez két fajta tudást kell beépíteni:
      • hogyan változik a környezet az ágenstől függetlenül
      • az ágens cselekvései hogyan befolyásolják a környezetet.
  • Cél-orientált ágens
    • összeveti a lehetséges cselekvések eredményeit, így meghatározza a céljához legközelebb eső cselekvést
    • a cselekvéssel befolyásolja a környezetét a cél irányába.
    • keresést és tervkészítést használ
  • Hasznosság-orientált ágens
    • A cél felé törekvés nem elég kifinomult, pl. ha
      • egymásnak ellentmondó célok vannak
      • több cél van ,melyre az ágens törekedhet
    • Az ágens egy hasznosság függvény segítségével minden állapothoz kiszámítja a hasznosságot. A célját a magas hasznosságú állapotok mentén éri el.
  • (Hibrid ágens) a különböző típusú ágensek ötvözése egy előnyösebb tulajdonságú ágens érdekében

A környezet

A környezetek jellemzésére az alábbi tulajdosnágok szolgálnak:

• Hozzáférhető vagy nem hozzáférhető
• Determinisztikus vagy nem determinisztikus
• Epizódszerű vagy nem epizódszerű
• Statikus vagy dinamikus
• Diszkrét vagy folytonos

A problémamegoldó ágens

A problémamegoldó ágens a cél-orientált ágens egy típusa. Ugyanúgy célt határoz meg és próbálja elérni azt mint minden cél-orientált ágens,ezen kívül ismeri a "problémát"(lentebb részletezve) is. A probléma állapotterében kereséssel találja meg a megoldást.

Összefoglalva, problémamegoldás lépései

• cél meghatározása
• probléma meghatározása
• keresés
• megoldás
• végrehajtás

A probléma

A probléma információk gyűjtőhelye, az ágens arra használja, hogy meghatározza, mit tegyen.

Pl A jól ismert országjáró ágens. A környezet Románia, a cél ,hogy eljusson Bukarestbe az ágens. A probléma itt lehet pl. egy egyszerű Románia térkép, az ágens ebben kereséssel találhat megoldást. De belevehetjük a problémába az idő múlását, az időjárást stb stb...

• A problémákat az alábbi jelzőkkel tudjuk jellemezni
  • Egy állapotú Az ágens pontosan tudja, melyik állapotban van és egyes cselekvései melyik állapotba viszik át.
  • Több állapotú Ismeri minden cselekvésének hatását, de a környezethez csak korlátozott mértékben fér hozzá (előfordulhat, hogy érzékelője sincs). Tudhatja, hogy a kiinduló állapota az állapotok mely halmazában van és ki tudja számítani ,hogy egyes cselekvéseivel mely állapot-halmazba kerül.
  • Eshetőségi Ahelyett, hogy a végrehajtás során minden eshetőséget előre figyelembe venne, elkezdi a végrehajtást és közben figyeli a környezetét, hogy valójában mely eshetőségek következtek be, ennek függvényében módosíthatja a további cselekvéssorozatot.
  • Felfedezési Az ágens nem ismeri a cselekvései hatását, kísérleteznie kell.
• A jól definiált problémák az alábbi tulajdonságokkal rendelkeznek
  • Kezdőállapot
  • Cél állapot(ok)
  • Cél teszt azért, hogy az ágens eldönthesse, hogy célhoz ért-e
  • Útköltség-függvény mely segítségével az egyes cselekvés-sorozatok (utak) költsége meghatározható, összehasonlítható
  • Operátorok: Az ágens rendelkezésére álló cselekvések halmaza.

A keresésről általában

A keresés az a folyamat, ami során az ágens előállítja a kezdő állapotból a cél-állapotba vezető cselekvéssorozatot(utat) azaz a megoldást.

A kereséseket két csoportra lehet osztani:

• nem informált keresések: az eljárás semmilyen információval nem rendelkezik a kezdőállapotból a cél-állapotba vezető útról.
• informált keresések: Van az eljárásnak információja arról, hogy egy adott esetben melyik alternatíva viszi közelebb a cél-állapothoz.

A kereséseket az alábbi tulajdonságokkal lehet jellemezni:

• teljesség garantáltan megtalálja-e a megoldást, ha az létezik
• időigény
• tárigény
• optimalitás ha több megoldás is létezik a legjobbat találja-e meg?

A keresési eljárások keresési fákat használnak, melyek kifejtendő ill. kifejtett csomópontokat tartalmaznak. Ezek a csomópontok nem azonosak a probléma állapottereinek állapotaival, több információt tartalmaznak. Egy csomópont adatszerkezete:

• a csomóponthoz tartozó állapottér állapot
• a keresési fa azon csomópontja, amely ezen csomópontot generálta (szülő csomópont)
• a csomópontot generáló operátor
• a gyökér csomóponttól eddig a csomópontig vezető út csomópontjainak a száma (a csomópont mélysége)
• a kiinduló állapottól a csomópontig számított út költség.

Összefoglalva: a csomópont nem az állapot, a csomópont egy adatszerkezet, egy állapot a világ egy konfigurációja. A csomópont rendelkezik mélységgel és szülővel, míg az állapot nem.

Nem informált keresések

• *szélességi_ keresés*: (BFS)
  • teljes és optimális (feltéve hogy az útköltség a csomópont mélységének nemcsökkenő függvénye)
    • amennyiben a megoldás egy d hosszú út, a csomópontok száma O(b^d)
    • A tárigény nagyobb probléma, mint időigény
• *egyenletes költségű keresés (uniform cost search)*:A szélességi keresés egy módosítása.A hullámfront legkisebb költségű csomópontját fejti ki.A szélességi keresés is egyenletes költségű, ha a költség a csomópont mélysége.
• mélységi_ keresés (DFS)
  • lineáris tárigénnyel rendelkezik O(b*m), időigénye O(b^m)
  • rossz útra keveredve elakadhat, végtelen mély ág esetén előfordulhat, hogy végtelen ciklusba ugrik és talál az optimálisnál rosszabb megoldást.
  • nem teljes és nem optimális
• mélységkorlátozott keresés (Depth Limited Search)
  • a mélységi keresés során mélységi korlátot alkalmaz
  • jól megválasztott korlát esetén teljes, de nem optimális
  • Az állapottér átmérője igen jó mélységi korlátot ad (bármely pont elérhető legfeljebb az átmérő hosszú úttal minden pontból), ám ez leggyakrabban nem ismert
• iteratívan mélyülő keresés (Iterative Deepening Search - IDS)
  • mélységkorlátozott kereséseket hajt végre egymás után, egyre növekvő mélységgel.
  • optimális, teljes, lineáris tárigénnyel rendelkezik.
  • hátránya hogy többször fejti ki ugyanazon csomópontokat, de ez nem számottevő veszteség, mivel az elágazási tényező növelésével csökken a redundancia.
  • általánosságban nagy keresési tér esetén, ha a megoldás mélysége nem ismert az IDS a javasolt alkalmazás
• kétirányú keresés a start és cél állapotból egyszerre indítja el a keresést, ezáltal a gyorsabb lesz.
  • Felmerülő problémák: elődcsomópontok megtalálása, ha az összes operátor reverzibilis, több célállapot esetén - állapothalmaz fogalma. A frissen generált állapot már nem létezik-e a másik irányú fában. A két irányban akár különböző keresési mód is választható, melyiket érdemesebb.
    • tárigénye csak fele a szélességi keresés tárigényének

A keresési stratégiák összehasonlítása:

*Kritérium *	*Szélességi*	*Egyenletes költségű*	*Mélységi*	*Mélység-korlátozott*	*Iteratívan mélyülő*	*Kétirányú (amennyiben alkalmazható)*
*Idő igény*	Bd	bd	bm	bl	bd	bd/2
*Tár igény*	Bd	bd	bm	bl	bd	bd/2
*Optimális?*	Igen	Igen	Nem	Nem	Igen	Igen
*Teljes?*	Igen	Igen	Nem	Igen, ha l >= d	Igen	Igen

A keresési stratégiák értékelése:

• b az elágazási tényező: minden egyes új állapotot kifejtve b darab új állapot jelenik meg.
• d a megoldás mélysége
• m a keresési fa maximális mélysége
• l a mélység korlát.

Informált keresési stratégiák

Informált keresés esetén rendelkezünk egy kiértékelő függvénnyel, mely az egyes csomópontokra meghatározza. hogy mennyire visz a közelebb a cél-állapothoz. Ez a függvény gyakran csak becslés, így pontatlan lehet.

• A heurisztika fogalma: Olyan, nem bizonyítható ötlet, amely a gyakorlati esetek többségében drasztikusan csökkenti a problémamegoldás erőforrásigényét, de általánosságban, kivétel nélkül nem érvényes.
• A heurisztikus függvény (h) megadja egy adott csomópontból a cél-állapotba vezető út legolcsóbb becsült költségét. h tetszőleges lehet,de h=0 -nak teljesülnie kell ha egy cél-csomópontban vagyunk.
• Az elfogadható heurisztikus függvény sohasem becsüli felül a cél eléréséhez szükséges tényleges költséget.
• b* effektív elágazási tényező a heurisztikus függvényt minősíti:

Ha a keresés által kifejtett összes cs-pont száma N, a megoldás mélysége d, akkor b* annak a d mélységű kiegyensúlyozott fának az elágazási tényezője, amely N cs-pontot tartalmazna:
N = 1 + b* + (b*)^2 + … + (b*)^d
Egy jól megtervezett heurisztikus függvény effektív elágazási tényezője 1 körüli érték.

• A legjobbat először (Best-First) keresés Elindul egy jónak tűnő úton és csak akkor lép vissza, ha zsákutcába jutott. Ez egy mohó keresési eljárás, nem teljes nem optimális.A legrosszabb esetben időigénye és tárigénye is O(b^m)
• Az A* keresés Ebben az eljárásban figyelembe vesszük a megtett út költségét (g) és a becsült hátralevő költséget(h) is.Az n csomópont költsége így f(n)=h(n)+g(n) . Ezek közül mindig a minimálisat választjuk ki.
  • Elfogadható heurisztikát használva az A* teljes.
  • Az A* optimális lokálisan véges gráfokon (az elágazási tényező véges), feltéve, ha létezik egy pozitív konstans, melynél semelyik operátor költsége sem kisebb.
• IMA* Az iteratívan mélyülő keresés, ahol a mélységkorlát helyett költségkorlátot használunk. Teljes és optimális, de csak a leghosszabb felderített úttal arányos memóriát igényel.
• EMA* (Egyszerűsített Memóriakorlátozott A*) Hasonló az A*-hoz, de korlátozza a sor méretét, hogy az beleférjen a rendelkezésre álló memóriába. Az összes memóriát felhasználja, megjegyezve az egyes csomópontokat (pl. ezzel ellenben IMA* az iterációk között felejt). Csak akkor teljes, ha a legsekélyebb megoldási út belefér a memóriába. Ebben az esetben optimális.Ha a teljes keresési fa tárolására elegendő memória áll rendelkezésre akkor optimálisan hatékony.
  • elfelejtett csomópont:
    

Ha elfogy a memória, a nem ígéretes – vagyis a nagy f-költségű – csomópontokat törli a sorból. Az algoritmus a szülő csomópontokban információt tárol az elfelejtett részfa legjobb útjáról, ha már az összes megmaradó út rosszabbnak tűnik az elfelejtettnél, újragenerálja a az elfejetett részfát.

• Iteratívan javító algoritmusok: Az állapotteret egy felületnek felel meg, az egyes pontok magassága a felületen arányos a jóságukkal.
  • hegymászó algoritmus (gradiens módszer) Mindig azt a lehetőséget választja, amely kedvezőbb.Problémái:
    • lokális maximumok: megáll benne
    • síkság: véletlen séta, mert ha több legjobb lépést talál, random válasz közülük
    • hegygerinc: könnyen eljut a gerincre, de lehet hogy a gerinc csak lassan emelkedik a csúcs felé
  • A lokális maximumok ellen véletlen újraindítással vagy szimulált lehűtéssel lehet védekezni: Megengedünk az algoritmusnak néhány lefelé vezető lépést. A legjobb lépés helyett véletlen lépést alkalmazunk. Ha a lépés javít, mindenképp végrehajtjuk, ellenkező esetben csak 1-nél kisebb valószínűséggel. Ez a valószínűség (P) = exp(-deltaE/T). deltaE a lefelé haladás mértéke, T a hűtési karakterisztika, mely a 0-hoz tart.

Logika

Tudás reprezentálása, logikáról általában, ontológia, dedukció szerepe

Következtetési módok:

• dedukció
  • modus ponens
  • rezolúció
• indukció
• abdukció

Elsőrendű logika

• építőelemek
• modell
• következtetési szabályok
• horn-klózok
• monotonitás
• problémák

Predikátum logika

• építőelemek
• következtetési lépések
• tulajdonságok

Bizonytalanság

Valószínűség;Hálók

Infelm vizsga után meg se fog kottyanni ez a rész :) Az egész a feltételes valószínűségek manipulásásáról szól, amit tudni kell nagyon: P(A,B)=P(A|B)P(B). Ezt kétszer egymás után alkalmazva kijön a Bayes tétel: P(B||A)=P(AB)P(B)/P(A) Ezzel az ok-okozati kapcsolatokon "visszafelé lépdelve" is tudunk következtetni.

Felsoroljuk a modellezendő valószínűségi változókat (n db), mindegyiknek van egy esélye. Van együttes eloszlásuk is (igaz-hamis esetben is 2ⁿ db szám), melyből az összes fajta valószínűséget ki tudunk számolni. Ebből mi érdekel minket? Hogy adott események bekövetkezte esetén (ami érzékelővel felfogunk) egy másik adott esemény bekövetkezésének mekkora az esélye (mert az alapján akarunk dönteni). A probléma: az összes együttes eloszlás exponenciálisan sok.

A problémateret szűkíti, ha kihasználjuk feltételes függetlenségeket (Hasonló a Markov tulajdonsághoz), meg persze a sima függetlenségeket. A jegyzet szerinti példa: a betöréstől (B) függ a riasztó megszólalásának (R) esélye, a riasztó megszólalásától függ annak az esélye, hogy Józsi bácsi felhív minket (J), hogy gáz van. Ebből következik, hogy a betöréstől is függ, hogy Józsi hív-e. Az egyszerűsítő feltétel P(J|R,B)=P(J||R) - azaz Józsi bácsi reakcióját nem befolyásolja a betörés ténye, amennyiben szól a riasztó: J és B R-t feltéve függetlenek. Tehát elég P(J||R) és P(R||B) valószínűségeket tudni, P(JB) nem kell.

Ábrázolás: egy DAG-on, ahol a csúcsok események, a feltételesen független csúcsok között nem megy él. Minden csúcshoz van egy Feltételes Valószínűségi Tábla, melyek annyi sora van, ahány lehetséges értékkombinációt felvehetnek az adott csúcsba mutató csúcsok. A táblázat egy sora megadja, hogy az adott kombó esetén mi a csúcs értékének eloszlása (igaz-hamis esetén csak egy oszlop van, a bekövetkezés esélye. n-féle kimenet esetén n-1 szám elég) A DAG forrásaiban csak egyszerűen az adott esemény eloszlását adjuk meg.

Pl: a riasztó (R) megszólalhat betörés (B) miatt, és földrengés (F) miatt is. F-ből és B-ből mutat nyíl R-be, és R FVT-jében megadjuk, hog

B	F	p
I	I	0.99
I	H	0.9
H	I	0.5
H	H	0.01

A valószínűségi hálóból az összes feltételes eloszlást ki lehet olvasni. Az algoritmus nagyon ronda. Ha a DAGban irányítatlan kör sincsen (minden pontpár között csak 1 út van), akkor az algoritmus lineáris a csúcsok számához (hurrá!), de egyébként sajnos np teljes.

A DAG felépítése: tetszőleges sorrendben adjuk hozzá a csúcsokat, mindegyik hozzáadásánál válasszunk ki minimális számú szülőt a csúcsnak, és írjuk meg az FVT-jét. Meglepő módon a gráf mindig minden információt tárolni fog, de az FVT-k száma és mérete nagyban változik, és a függés jelentése nem mindig lesz ember számára kivehető. És a legfontosabb a futási idő szempontjából, hogy ne legyen irányított kör. Ezt a feltételt brute force is teljesíthetjük: ha több csúcsot összevonunk egybe, akkor párhuzamos utakat tudunk egybeolvasztani, de a valószínűségi változók értékkészlete ilyenkor szorzódik (gyerek FVT táblája nő), és a szemléletes jelentést elveszítjük. Ennél sokkal több van a slideokon! Olvassátok azt inkább!

Fuzzy logika

Az IS-en van egy nagyon jó kis segédanyag. Javított link: ezen a zipen belül az mi_fuzzy.zip-ben a fuzzy.pdf az valószínűleg.