Mesterséges intelligencia kérdéses és válaszok vizsga PDF

Preview

Summary

MestInt elméleti kérdések, és válaszok➢ Melyek voltak az MI jellemző időszakai? - 1943 McCulloch és Pitts – agy modellje elektromos áramkörként - 1950 Turing – Computing machinery and Intelligence - 1952- 69 Nézd mama, kéz nélkül! - 1950- kezdeti AI szoftverek - Samuel dáma-program, - Nevell és Simo...

Description

MestI MestInt nt elmé elméleti leti kérd kérdések, ések, és válaszok ➢ Melyek voltak az MI jellemző időszakai? • • • •

1943 McCulloch és Pitts – agy modellje elektromos áramkörként 1950 Turing – Computing machinery and Intelligence 1952-69 Nézd mama, kéz nélkül! 1950kezdeti AI szoftverek • Samuel dáma-program, • Nevell és Simon Logic theorist • Gelernter Geometry Engine

• 1956

Dartmouthi találkozó – MI elnevezés

• 1965

Robinson algoritmusa (rezolúció - teljes algoritmus)

• 1966-74 winter is coming • az MI felfedezi a számítási komplexitást (kombinatorikus robbanás) • a neurális hálózatok háttérbe szorulnak • A szellem készséges, de a test gyenge → A vodka jó, de a hús romlott • 1969-79 tudásalapú rendszerek megjelentése • 1980-88 szakértői rendszerek forradalma • 1980 néhány millió $ • 1988 2 milliárd $ • 1988-93 a szakértői rendszerek piaca kifullad (winter again) • 1985-95 a neurális hálók újra divatba jönnek • 1988• • 1995-

a valószínűség feltámadása, számítási kapacitások növekedése új irányzatok: ALife, genetikus algoritmusok, soft computing ágensek mindenfele

Ágens megközelítés ➢ Mi a racionális ágens (és mi nem)? A racionális ágens (rational agent) definíciója: Az ideális racionális ágens minden egyes észlelési sorozathoz a benne található tények és a beépített tudása alapján minden elvárható dolgot megtesz a teljesítménymérték maximalizálásáért. Egy racionális ágens (rational agent) olyan, amely helyesen cselekszik – elméletileg megfogalmazva az ágensfüggvény táblázatában minden bejegyzés helyesen van kitöltve. Első közelítésben azt mondjuk, hogy a helyes cselekedet az, amely az ágenst a legsikeresebbé teszi. Fontos: A racionális ágens azt a műveletet választja, mely maximalizálja a várható teljesítménymértéket adott érzékeléssorozathoz Annak megfigyelése, hogy egyes ágensek jobban viselkednek, mint mások, a racionális ágens ötletéhez vezet majd – olyan ágenshez, amelyik olyan jól viselkedik, amennyire csak

lehet. Az, hogy mennyire viselkedhet jól egy ágens, a környezet természetén múlik; bizonyos környezetek sokkal nehezebbek, mint mások. ➢ Mitől függ egy ágens racionalitása (adott pillanatban)? Négy dolgon múlik az, hogy egy adott pillanatban mi racionális. Ezek: •

A siker fokát mérő teljesítménymérték.

•

Az ágens eddigi tudása a környezetről.

•

A cselekvések, amiket az ágens képes végrehajtani.

•

Az ágens érzékelési sorozata az adott pillanatig. vagy | Racionális – szükséges feltételek

• felfedezés • tanulás • autonómia ➢ Mi a különbség és a hasonlóság az ágensprogram és ágensfüggvény között? •

az ágens függvény az érzékeléssorozatot cselekvésre képezi le: f: P*→A

•

az ágens program fizikai architektúrán fut, hogy az f-t megvalósítsa

Az ágensfüggvény minden lehetséges körülmény esetén megadja az ágens cselekvéseit, az ágensprogram implementálja az ágensfüggvényt (vagy annak egy részét) Az ágensprogram (agent program) megtervezése: egy függvényé, amely megvalósítja az észlelések és a cselekvések közötti leképezést. Az ágensprogramok mindannyian azonos vázzal rendelkeznek: bemenetként fogadják az aktuális észleléseket a szenzoroktól, és visszaküldenek egy cselekvést a beavatkozókhoz.6 Vegyük észre a különbséget az ágensprogram, amely az aktuális észlelést veszi bemenetként, és az ágensfüggvény között, amely a teljes észlelési történetet fogadja. Az ágensprogram azért fogadja csak az aktuális észlelést bemenetként, mert csak ez érkezik a környezettől – ha az ágens cselekedetei a teljes észlelési sorozattól függnek, az ágensnek emlékeznie kell az észlelésekre. ➢ Mi a specialitása az egyszerű reflex ágensek? A legegyszerűbb fajtájú ágens az egyszerű reflexszerű ágens (simple reflex agent). Ezek az ágensek az aktuális észlelés alapján választják ki a cselekvéseket, figyelmen kívül hagyva az észlelési történet többi részét. Az egyszerű reflexszerű ágens csak akkor fog működni, ha a helyes döntés kizárólag az aktuális észlelés alapján meghozható – azaz akkor, ha a környezet teljesen megfigyelhető. Már a megfigyelhetőség legkisebb hiánya is komoly problémát okozhat. A következő példa kapcsolatot feltétel–cselekvés szabálynak (condition–action rule) hívjuk, és ha az-előző-autó-fékez akkor kezdj-fékezni formában írjuk.

2.9. ábra - Egy egyszerű reflexszerű ágens sematikus diagramja

➢ Mi a specialitása a modellalapú reflexszerű ágensek? A részleges megfigyelhetőség kezelésének leghatékonyabb módja, ha az ágens nyomon követi a világ jelenleg nem látható részét. Azaz, az ágensnek nyilván kell tartania valamiféle belső állapotot (internal state), amely az észlelési történeten alapul, és így a jelenlegi állapot nem megfigyelt aspektusainak legalább egy részét tükrözi. 2.11. ábra - Belső állapottal rendelkező reflexszerű ágens

A modellalapú reflexszerű ágens nyomon követi a világ jelenlegi állapotát egy belső modellben. Ezek után a reflexszerű ágenshez hasonlóan választ egy cselekvést.

Kétféle információra van szükségünk: 1. a világ hogyan alakul az ágenstől függetlenül 2. az ágens saját cselekvései hogyan változtatják meg a világot Ezt, a „világ működésének mikéntjéről” szóló tudást – akár egyszerű logikai áramkörökkel, akár teljes tudományos elméletekkel valósítjuk meg – a világ modelljének (model) hívjuk. Egy ilyen modellt használó ágenst pedig modellalapú ágensnek (model-based agent). ➢ Mi a specialitása a célorientált ágensnek? A környezet jelenlegi állapotának ismerete nem mindig elég annak eldöntéséhez, hogy mit tegyünk. Például egy kereszteződésben a taxi mehet egyenesen, de fordulhat jobbra vagy balra is. A helyes döntés attól függ, hogy a taxi hova szeretne eljutni. Más szavakkal, a jelenlegi állapot leírása mellett az ágensnek valamiféle cél- (goal) információval is rendelkeznie kell, amely leírja a kívánatos helyzeteket – például azt, hogy az utas jusson el a célállomásig. Az ágensprogram ezt összevetheti a lehetséges cselekvések eredményeiről szóló információkkal annak érdekében, hogy a céljához vezető cselekvést meghatározza. 2.13. ábra - Egy modellalapú, célorientált ágens. Nyomon követi a világ állapotát és az elérendő célok halmazát is, és kiválaszt egy cselekvést, amely (végső soron) céljainak eléréséhez vezet.

A keresés (search) (lásd 3–6. fejezet) és a tervkészítés (planning) (lásd 11–12. fejezet) a mesterséges intelligencia azon területei, amelyek az ágens céljait elérő cselekvéssorozat megtalálásával foglalkoznak. Egyszerűen egy új cél megadásával a célorientált ágenstől egy új viselkedés megjelenését kaphatjuk. A reflexszerű ágens „mikor fordulj” és „mikor menj egyenesen” szabályai csak egy cél esetében fognak működni: ki kell őket cserélni ahhoz, hogy egy új helyre menjen.

➢ Mi a specialitása a hasznosságorientált ágensnek? A környezetek többségében a célok önmagukban nem elegendőek jó minőségű viselkedés létrehozásához. Például többféle cselekvéssorozat vezet a taxi végállomásának – és így a céljának – eléréséhez, de némelyik gyorsabb, biztonságosabb, megbízhatóbb vagy olcsóbb, mint mások. A célok csak durva különbséget tesznek „boldog” és „boldogtalan” állapotok között, egy általánosabb teljesítménymérték ezzel szemben a világ állapotainak (vagy állapotsorozatainak) megfelelő összehasonlítását tehetné lehetővé, azt megadva, hogy pontosan mennyire tennék boldoggá az ágenst, ha elérné azokat. Mivel a „boldogság” nem hangzik túl tudományosan, ezért a szokásos terminológia azt mondja, hogy a világ egyik állapota előnyösebb egy másikhoz képest, ha nagyobb a hasznossága (utility) az ágens számára. 2.14. ábra - Egy modellalapú, hasznosságalapú ágens. A világ modellje mellett egy hasznosságfüggvényt is alkalmaz, amely a világ állapotaihoz rendelt preferenciáit (boldogság fokát) méri. Ezek után olyan cselekvést választ, amely a legjobb várható hasznossághoz

vezet,

amit

az

összes

lehetséges

végállapot

előfordulási

valószínűségével súlyozott átlagolásával számít ki.

A hasznosságfüggvény (utility function) egy állapotot (vagy állapotok egy sorozatát) egy olyan valós számra képezi le, amelyik a hozzá rendelt boldogság fokát írja le. A hasznosságfüggvény teljes meghatározása kétféle olyan helyzetben tesz lehetővé racionális döntéseket, amikor a célok erre alkalmatlanok. Egyrészt, amikor egymásnak ellentmondó célok vannak, amelyeknek csak egy része érhető el (mint például a biztonságosság és a sebesség), akkor a hasznosságfüggvény meghatározza a helyes kompromisszumot.

Másrészt, amikor több cél van, amelyek elérésére az ágens törekedhet, és egyikük sem érthető el teljes bizonyossággal, a hasznosság olyan módszert ad, amivel a siker valószínűsége a célok fontosságához mérhető. A 16. fejezetben megmutatjuk, hogy minden racionális ágensnek úgy kell működnie, mintha rendelkezne hasznosságfüggvénnyel, amelynek várható értékét maximalizálni akarja. ➢ Mi a specialitása a tanuló ágensnek? A tanulás lehetővé teszi az ágens számára, hogy kezdetben ismeretlen környezetben működjön, és kompetensebbé váljon, mint ahogy azt kezdeti tudása lehetővé tette volna. Egy tanuló ágens négy koncepcionális komponensre bontható fel, ahogy azt a 2.15. ábra mutatja. A legfontosabb különbségtétel a javításokért felelős tanuló elem (learning element) és a külső cselekvések kiválasztásáért felelős végrehajtó elem (performance element) között van. A végrehajtó elem az, amit eddig a teljes ágensnek tekintettünk: ez végzi az észleléseket, és ez dönt a cselekvésekről. A tanuló elem a kritikustól (critic) kapott, az ágens működéséről szóló visszajelzést használja annak megállapítására, hogy a végrehajtó elemet hogyan kell módosítani annak érdekében, hogy a jövőben jobban működjön az ágens. 2.15. ábra - Tanuló ágensek egy általános modellje

A kritikus megmondja a tanuló elemnek, hogy az ágens milyen jól működik egy rögzített teljesítményszabványhoz viszonyítva. Tekinthető úgy, mintha az ágensen teljesen kívül lenne, mivel az ágens nem módosíthatja azt saját viselkedésének megjavítása érdekében. A tanuló ágens utolsó komponense a problémagenerátor (problem generator). Ennek feladata,

hogy

olyan

cselekvéseket

javasoljon,

amelyek

új

és

informatív

tapasztalatokhoz vezetnek. Az a helyzet, hogy ha a végrehajtó elem a saját feje után menne, akkor adott tudása alapján mindig a legjobb cselekvéseket választaná. De ha az

ágens hajlandó egy kis felfedezésre, és rövid távon talán néhány szuboptimális cselekvésre, hosszú távon sokkal jobb cselekvéseket fedezhet fel. A problémagenerátor feladata, hogy ilyen felfedező cselekvéseket javasoljon. Ezt teszik a tudósok is, amikor kísérleteket végeznek. Bizonyos értelemben a teljesítményszabvány a beérkező észlelés egy részét elkülöníti jutalomként (reward) (vagy büntetésként – penalty), amely az ágens viselkedési minőségének direkt visszacsatolása. A rögzített teljesítményszabványok, mint például állatokban a fájdalom vagy éhség, ily módon értelmezhetők. A tanulás az intelligens ágensekben összefoglalható úgy, mint egy folyamat, amely az ágens minden komponensét úgy módosítja, hogy az összhangba kerüljön a rendelkezésre álló visszacsatolt információval, ily módon növelve az ágens általános teljesítményét.

Keresések ➢ Mi a különbség az online és az offline keresések között? Offline problémamegoldás: a megoldás során a szemek csukva vannak. Online problémamegoldás során a teljes tudás hiányában cselekszünk, menetközben új információkat szerzünk. Offline keresés: Egy teljes megoldást számítanak ki mielőtt a valós világba beteszik a lábukat (lásd 3.1. ábra), majd a megoldást az érzékelések megvizsgálása nélkül végrehajtják. Online keresés: az online kereső (online search) ágensek működésében a számítás és a végrehajtás átlapolódik (interleaving): először végrehajtanak egy cselekvést, majd megfigyelik a környezetüket és kiszámítják a következő cselekvést. (felfedezési probléma) 3.1. ábra - Egy egyszerű problémamegoldó ágens. Először a célt és a problémát fogalmazza meg, majd a problémát megoldó cselekvéssorozatot keres, végül a cselekvéseket egyenként végrehajtja. Amikor kész vele, egy másik célt fogalmaz meg, és az egészet újrakezdi. Jegyezzük meg, hogy a cselekvéssorozata végrehajtása alatt az ágens az érzékeléseivel nem foglalkozik. Feltételezi, hogy az általa megtalált megoldás mindig működőképes.

➢ Milyen komponensei vannak egy jól definiált problémának keresési feladatok esetén? •

kezdeti állapot o Aradon van

•

S(x) rákövetkező függvény o cselekvés-állapot párok o S(Arad)={, …}

•

célteszt o explicit (célállapotok halmaza) x=Bukarest o implicit (absztrakt tulajdonsággal definiálva) NoDirt(x)

•

útköltség(additív) o pl. távolságok összege, cselekvések száma, stb. o pl. távolságok összege, cselekvések száma, stb.

Megoldás: cselekvéssorozat, mely a kezdőállapotból egy célállapotba vezet. Egy probléma (problem) formális megragadásához az alábbi négy komponensre van szükség: •

A kiinduló állapot (initial state), amiből az ágens kezdi a cselekvéseit. A romániai ágensünk kezdeti állapotát például Benn(Arad)-ként lehetne leírni.

•

Az ágens rendelkezésére álló lehetséges cselekvések (actions) halmaza. A leginkább használatos leírás ( Egy alternatív megfogalmazás az operátorok (operators)

egy

halmaza,

amelyeket

egy

állapotra

alkalmazva

lehet

az

utódállapotokat generálni. ) az állapotátmenet-függvényt (successor function) alkalmazza. Egy adott x állapot esetén az ÁLLAPOTÁTMENET-FV (x) visszaadja a rendezett 〈cselekvés, utódállapot〉 párok halmazát, ahol minden cselekvés az x állapotban legális cselekvések egyike, és minden utódállapotot egy cselekvésnek az x állapotra való alkalmazásával nyerünk. A kezdeti állapot és az állapotátmenet-függvény együttesen implicit módon definiálják a probléma állapotterét (state space): azon állapotok halmazát, amelyek a kiinduló állapotból elérhetők. Az állapottér egy gráfot alkot, amelynek csomópontjai az állapotok és a csomópontok közötti élek a cselekvések. Az állapottér egy útja (path) az állapotok egy sorozata, amely állapotokat a cselekvések egy sorozata köt össze. •

A célteszt (goal test), amely meghatározza, hogy egy adott állapot célállapot-e. Néha létezik a lehetséges célállapotok egy explicit halmaza, és a teszt egyszerűen megnézi, hogy az ágens elérte-e ezek egyikét. Néha a cél valamilyen absztrakt tulajdonsággal van definiálva, nem pedig explicit módon felsorolt állapothalmazzal. A sakkban például az úgynevezett „sakk-matt” állapot elérése a cél, amelyben az ellenfél királya az őt ért támadás elől nem tud elmenekülni.

•

Egy útköltség- (path cost) függvény, amely minden úthoz hozzárendel egy költséget. A problémamegoldó ágens azt a költségfüggvényt fogja választani, amely a saját hatékonysági mértékének felel meg. lépésköltség (step cost)

➢ Keresési feladat esetén hogyan adjuk meg a cselekvéseket? A keresési algoritmus bemenete egy probléma, kimenete pedig egy cselekvéssorozat formájában előálló megoldás (solution). operátorok, ÁLLAPOTÁTMENET-FV (x) absztrakt cselekvések Az absztrakció hasznos, ha a megoldásbeli cselekvések végrehajtása az eredeti problémánál egyszerűbb. Az élek cselekvéseket jelentenek az állapottér gráfjában, vagy fájában. vagy talán ez a helyes válasz a kérdésre: CSELEKVÉS: a csomópont szülő-csomópontjára alkalmazott cselekvés; ➢ Mi a kapcsolat az állapottér és keresési fa között? keresési fa (search tree): amelyet az állapotteret együttesen definiáló kezdeti állapotból és az állapotátmenet-függvényből generálnak. Fontos megkülönböztetni az állapotteret és a keresési fát. Az útkeresési probléma esetében az állapottér csak 20 állapotból áll, minden egyes városhoz tartozik egy állapot. Ebben az állapottérben azonban végtelen sok út vezet, így a keresési fa végtelen sok csomópontból áll. Például az Arad–Nagyszeben, Arad–Nagyszeben–Arad, Arad– Nagyszeben–Arad– Nagyszeben három út az első három a végtelen számú útszekvenciából. (Egy jó keresési algoritmus nyilvánvalóan elkerüli az ilyen utak követését. A 3.5. alfejezetben megmutatjuk hogyan.) Saját meglátás: A keresési fával meghatározhatók azok az utak, amelyek az állapotteret alkotó egyes állapotokba vezetnek. ➢ Mit kell tárolni a keresési fa egy csúcsában? Aszalós slide: a csúcs egy adatszerkezet, melyből felépül a keresőfa o tartalmaz: szülő, gyerekek, mélység, útköltség AIMA: A csomópontokat sokféle módon lehet reprezentálni, de mi feltételezzük, hogy egy csomópont egy öt komponensből álló adatszerkezet: •

ÁLLAPOT: az állapottérnek a csomóponthoz tartozó állapota;

•

SZÜLŐ-CSOMÓPONT: a keresési fa azon csomópontja, amely a kérdéses csomópontot generálta;

•

CSELEKVÉS: a csomópont szülő-csomópontjára alkalmazott cselekvés;

•

ÚT-KÖLTSÉG: a kezdeti állapotból a kérdéses csomópontig vezető út általában g(n)nel jelölt költsége, ahogy ezt a szülőmutatók jelzik;

•

MÉLYSÉG: a kezdeti állapotból vezető út lépéseinek a száma.

➢ Mi a különbség egy állapot és egy keresési fa csúcsa között? az állapot a fizikai konfiguráció (reprezentációja) az állapotnak nincs szülője, gyereke, mélysége, útköltsége A csomópont egy adatnyilvántartásra használt adatszerkezet, amit egy keresési fa leírására használunk. Egy állapot a világ egy konfigurációja. Így a csomópontok a SZÜLŐCSOMÓPONT mutatók által definiált meghatározott úton találhatók, míg az állapotok nem. Továbbá könnyen előfordulhat, hogy két különböző csomópont egyazon állapotot tartalmaz, ha ezt az állapotot két különböző cselekvéssorozattal generálták le. ➢ Adja meg az általános fakeresési algoritmust!

Nem informált keresések

➢ Mit jelent az, hogy vak (nem informált) keresés? A nem informált keresési stratégiák csak a probléma definiálásakor megadott információkat használja fel. Nem informált (vaknak is nevezett) keresés (noninformed (blind) search) : A kifejezés azt jelenti, hogy ezen stratégiáknak semmilyen információjuk nincs az állapotokról a probléma definíciójában megadott információn kívül. Működésük során mást nem tehetnek, mint a következő állapotok generálása és a célállapot megkülönböztetése a nem célállapottól. ➢ Mi a perem? Adott adatszerkezetet peremként használva milyen keresési módszereket kapunk? Valahogy nyilván kell tartanunk a legenerált, kifejtésre váró csomópontokat is – ezt a gyűjteményt, listát peremnek (fringe) nevezik. A perem minden eleme egy levélcsomópont (leaf node), azaz egy olyan csomópont, amelynek a fában nincsenek követői. Szélességi keresés: A perem egy sor adatszerkezet (FIFO), az új rákövetkezők a sor végére kerülnek, a sor első eleme kerül kiterjesztésre. Egyenletes költségű keresés: Perem implementációja: prioritás sor az útköltség szerint (növekvő) Mélységi keresés, Mélységkorlátozott keresés, Iteratívan mélyülő mélységi keresés: Perem implementációja: verem (LIFO), a rákövetkezőket a verem tetejére teszi. ➢ Adja meg a lényeges különbségeket a különféle nem informált keresési módszerek között! Szélességi keresés: A legsekélyebb (legkisebb mélységű) még ki nem terjesztett csúcsot terjeszti ki Egyenletes költségű keresés: A legkisebb költségű még ki nem terjesztett csúcsot terjeszti ki. Ha minden élköltség azonos, egybeesik a szélességi kereséssel Mélységi keresés: a legmélyebb ki nem fejtett csúcsot fejti ki Mélységkorlátozott keresés: •

A mélységi keresés változata.

•

Az l mélységben lévő csúcsoknak nincs rákövetkezőjük.

Iteratívan mélyülő mélységi keresés: Saját: A mélységkorlátozott keresés iteratív változata, azaz a mélységkorlátot jelentő változót egy ciklusban 0-tól elvileg végtelenig iterációként eggyel növeli, és ezzel meghívja a mélységkorlátoz...