1. Tétel Racionális ágens Definíció: Komponensek: Feladatkörnyezet és fajtái: Ágenstípusok: 2. Tétel Informálatlan keresés definíciója: Fa keresés:

1. Tétel Racionális ágens Definíció: 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ényérték maximalizálásáért. Komponensek: - a siker fokát mérő teljesítményértékek - 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 Feladatkörnyezet és fajtái: A feladatkörnyezetet a TKBÉ (Teljesítmény, Környezet, Beavatkozók, Érzékelők) leírásának hívjuk. Fajtái: - teljesen megfigyelhető vagy részlegesen megfigyelhető - determinisztikus vagy sztochasztikus - epizódszerű vagy sorozatszerű - statikus vagy dinamikus - diszkrét vagy folytonos - egyágenses vagy többágenses Ágenstípusok: - egyszerű reflexszerű ágensek - modellalapú reflexszerű ágensek - célorientált ágensek - hasznosságorientált ágensek - tanuló ágensek

2. Tétel Informálatlan keresés definíciója: 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. Fa keresés: egy FIFO sor, mellyel biztosítja, hogy a korábban meglátogatott csomópontokat az algoritmus korábban fejti ki. Azaz a Fa-keresés szélességi keresést eredményez, mivel az összes újonnan legenerált követőt a sor végére teszi, azaz a sekélyebb csomópontok korábban kerülnek kifejtésre, mint a mélyebben fekvők. Szélességi keresés jellemzése: teljesség: Ha a legsekélyebb célcsomópont valamilyen véges d mélységben fekszik, a szélességi keresés eljut hozzá az összes nála sekélyebben fekvő csomópontot kifejtve. optimalitás: A szélességi keresés optimális, ha az útköltség a csomópont mélységének nem csökkenő függvénye. komplexitás: Az exponenciális komplexitású keresési problémák közül csak a legkisebb problémapéldányok oldhatók meg.

3. Tétel Egyenletes költségű keresés: mindig a legkisebb költségű n csomópontot fejti ki először, nem pedig a legkisebb mélységű csomópontot. teljesség: csak úgy garantálható, hogy minden lépés költsége egy kis pozitív ε konstansnál nagyobb vagy azzal egyenlő optimalitás: megegyezik a teljesség feltételével, ami azt jelenti, hogy egy út költsége az út mentén mindig növekszik. Így az első kifejtésre kiválasztott célcsomópont egyben az optimális megoldás is. komplexitás: legrosszabb esetben O(b1+[C*/ε]) Mélységi keresés: mindig a keresési fa aktuális peremében a legmélyebben fekvő csomópontot fejti ki. Kifejtésüket követően kikerülnek a peremből és a keresés „visszalép” ahhoz a következő legmélyebben fekvő csomóponthoz, amelynek vannak még ki nem fejtett követői. teljesség: igaz, ha a fa véges mélységű optimalitás: nem optimális komplexitás: O(bm), ahol b az elágazási tényező és m a csomópontok maximális mélysége Iteratívan mélyülő keresés fában: egy általános stratégia, amit sokszor a mélységi kereséssel együtt alkalmaznak a legjobb mélységkorlát megtalálására. Az algoritmus képes erre, mert fokozatosan növeli a mélységkorlátot, amíg a célt meg nem találja. Amikor az megvan, a mélységkorlát elérte a d-t, a legsekélyebben fekvő célcsomópont mélységét. teljesség: teljes, ha elágazási tényezője véges optimalitás: optimális, ha az útköltség a csomópontok mélységének nem csökkenő függvénye komplexitás: O(bd), ahol b az elágazási tényező és d a mélység

4. Tétel Gráf keresés: A Fa-keresés algoritmust egészítjük ki egy nyitott- és zárt listának nevezett adatszerkezettel, mely tartalmazza a kifejtésre váró és a már kifejtett csomópontokat. Ha az aktuális állapot egybeesik a zárt listán lévő állapotok egyikével, akkor eldobható, ahelyett hogy a kifejtésével kellene foglalkozni. Egyenletes költségű keresés optimális gráfban: két állításból épül fel. Állítás: A fa-keresés elfogadható g-vel és egyenletes költségű kereséssel optimális. Bizonyítás: G az első célállapot, amit kiterjesztünk és g(G)> C* (C* az optimum). Tehát találtunk egy célállapotot, amely nem optimális. Ekkor a peremben van egy optimális út, melynek x eleme is. Ekkor igaz az, hogy van egy optimális út is, ami különbözik attól, amit találtunk. Ennek az útnak biztosan van legalább egy pontja a peremben, mivel minden utat kiterjesztettünk. A peremben ennek a másik útnak a pontja, aminek optimális a költsége mindenképpen kisebb vagy egyenlő, mint az optimum, mivel ez egy részút és nem az egész út. Ezért biztos az, hogy a peremben lévő pont ami része az optimális útnak - költsége biztosan kisebb, mint az, amit éppen kiterjesztünk. Tehát ellentmondásra jutottunk. Azaz g(x)< g(G), mert g(x) ≤ C* (⇐g elfogadható) → ellentmondás, mert mégis G-t választottuk. Állítás: A gráf-keresés konzisztens g-vel és egyenletes költségű kereséssel optimális.

5. Tétel Informált keresés: amely a probléma definícióján túlmenően problémaspecifikus tudást is felhasznál, azaz hogyan képes hatékonyabban megtalálni a megoldást. A* algoritmus és tulajdonságai: A csomópontokat úgy értékeli ki, hogy összekombinálja a g(n) értéket – az aktuális csomópontig megtett út költsége – és a h(n) értéket – vagyis az adott csomóponttól a célhoz vezető út költségének becslőjét. Így kapjuk a f(n) = g(n) + h(n) összefüggést. f(n) a legolcsóbb, az n csomóponton át vezető megoldás becsült költsége teljesség: optimalitás: a Gráf-keresést használó A* algoritmus optimális, ha h(n) konzisztens, azaz az f(n) akármilyen út mentén nem csökken komplexitás: optimális hatékonyság: Azt jelenti, hogy egyetlen más optimális algoritmus sem fejt ki garantáltan kevesebb csomópontot, mint az A*. Ez azért van, mert az összes olyan algoritmus, amelyik nem fejti ki az összes csomópontot, melyre f(n)
6. Tétel Heurisztikák előállításának módszerei: Relaxálás: a probléma egy, egyszerűbb változatának a költségének a megadása. Az így kapott költséget felhasználhatjuk heurisztikának az eredeti feladat megoldásához, mivel ez a költség kisebb lesz, mint az eredeti feladat költsége. Relaxált probléma optimális megoldásának költsége a h() egy elfogadható heurisztika az eredeti problémára. relaxáció = a feltételek elhagyása. Relaxált probléma optimális költsége mindig kisebb, vagy egyenlő mint az eredeti. Ezt egy elfogadható heurisztikának tekintjük az eredeti problémára. Mivel a számított heurisztika a relaxált problémára egy pontos költség, teljesítenie kell a háromszög egyenlőtlenséget is, és ebből kifolyólag konzisztens is. Automatizált relaxálás: ha a feltételek formális nyelven is adottak, akkor a relaxált problémákat automatikusan is előállíthatjuk. Heurisztikák kombinálása: h(n) = max {h1(n), …, hm(n)} Az így megkonstruált összetett heurisztikus függvény mindig azt a függvényt használja, amelyik az adott csúcspontra a legpontosabb. Mivel az alkotóelemként felhasznált heurisztikus függvények mind elfogadhatóak, ezért h is elfogadható. Továbbá h konzisztens és dominálja az összes, benne alkotóelemként felhasznált heurisztikus függvényt. Mintaadatbázisok: tároljuk az egyes részprobléma esetekhez tartozó pontos megoldási költségeket. Független részproblémák: a költségek összeadhatóak. Elfogadhatóság: kifejtve a relaxálásnál Konzisztencia: kifejtve a relaxálásnál

7. Tétel Lokális keresés: ezek az algoritmusok csak egy aktuális állapotot vesznek figyelembe és általában csak ennek az állapotnak a szomszédjaira lépnek tovább. Két fő előnyük van: - igen kevés memóriát használnak - sokszor nagy vagy végtelen keresési térben is elfogadható megoldást produkálnak Globális optimalizálás: globális maximum: a legmagasabb csúcs, ahol f(x) = maxy (f(y’)) lokális maximum: ahol a szomszédok célfüggvényei kisebbek f(x) ≥ maxy=x f(y) plató: szomszédok értékei ugyanazok váll: szomszédok értékei ugyanazok, majd ezt egy nagyobb célfüggvény követi Hegymászó keresés és javításai: a keresés egy ciklus, ami mindig javuló értékek felé, azaz felfelé lép. Amint elér egy csúcsot (globális vagy lokális) megáll, mivel megtalálta az első optimumot. A siker, hogy a globális maximumot találja meg nem garantált. Javításai: - sztochasztikus hegymászó: a felfelé mutató irányokból véletlen módon választ - elsőnek-választott hegymászó: az első jobb értékű szomszédot választja - véletlen újraindítású hegymászó: ha elakad egy véletlenül választott pontból újraindul Szimulált hűtés: ebben az esetben a cél, hogy a lokális optimumból „kiugorjunk”, de a globális optimumból már ne. Egyes esetekben az aktuálisnál rosszabb megoldásokat is elfogadunk.

8. Tétel Populáció alapú keresés: Nyaláb keresés: az algoritmus nem egy, hanem k állapotot követ nyomon. Az algoritmus k véletlen módon generált állapottal indul, így minden lépésben a k állapot mindegyikének összes követőit kifejti, ha valamelyik a keresett cél az algoritmus leáll. A lokális nyaláb keresési algoritmusban a k parallel keresési szál megosztja az információt, így gyorsabban fókuszál. Egyik változata a sztochasztikus nyaláb keresés, ahol nem a k legjobb követőt választja, hanem k véletlen követőt választ. Evolúciós módszerek: A sztochasztikus nyaláb keresés egy variánsa, és a hegymászó algoritmust általánosítja. Evolúciós algoritmus: a nyaláb keresés általánosításához „szexuális” operátorokat vezetünk be. Genetikus algoritmusok: Állapottér, populáció: véges betűkészletű stringekből áll. Ennek egy adott példánya az egyed. fitness - függvény: a jobb állapotokra magasabb értékeket kell visszaadnia mutáció: az egyed egy értékének megváltoztatása rekombináció: két egyednél keresztezési pontokat adunk meg és ezek alapján keresztezzünk szülő szelekció: válasszunk K/2 darab párt a fitnesszel arányosan, vagy véletlen párosítással túlélő szelekció: válasszuk a K legjobbat, vagy véletlenül a fitnesszel arányosan Differenciális evolúció: populáció: x1 , ….., xk ∈ Rd szülő választás: minden egyed szülő is egyben rekombináció: minden xi {i=1, ..,k}- hoz választunk három véletlen egyedet: xr1, xr2, xr3 Legyen: v = xr1 + F [ xr2 – xr3 ] + λ[ yg – xr1] ahol yg az eddigi legkisebb megoldás amit ismerünk. Megj.: v nem függ xi -től, mutáció: nincs (ill. néha mutációnak hívják a fentit) v-t keresztezzük a xi -vel: (v1 , v2, …. ,vd) } → (u1, u2, …, ud) (xi1 , xi2, …. ,xid) } ahol az uj = xij CR valószínűséggel, vj egyébként

túlélők: u-val helyettesítjük xi-t ha f(u)> f(xi) lényeg: az operátorok automatikusan adaptálódnak a populáció kiterjedéséhez és alakjához

9. Tétel Korlátozott kielégítési feladatok: Definíció: az állapottér: D= D1 x D2 x … x Dn ( Di az i. változó (xi) lehetséges értékei), korlátozások: C1, …, Cm , ahol Ci ⊆ D, konzisztens (megengedett) hozzárendelések: C1 ∩ C2 ∩ …. ∩ Cm. Egy hozzárendelést konzisztensnek nevezünk, ha nem sért meg egyetlen korlátozást sem. A célállapotok a megengedhető állapotok is egyben és néhány korlátozás kielégítési probléma azt is igényli, hogy a megoldás célfüggvényt maximalizáljon. Általában egy Ci, a változók egy részhalmazára tartalmaz megszorítást, gyakran változópárra. Algoritmusok: Kényszergráf: ha Ci párokra vonatkozik, akkor adott, ha nem, akkor segédváltozók bevezetésével átalakítható. A gráf csomópontjai a probléma változóinak, élei pedig a korlátoknak felelnek meg. A keresési teret inkrementálisan is definiálhatjuk: kezdeti állapot: {} (üres halmaz), azaz egyik változónak sincs értéke. szomszédok: valamely hiányzó változóhoz rendeljünk értéket, amely nem okoz konfliktust út költség: konstans költség mindegyik lépésre

10. Tétel Többágenses környezeteket vezetünk be, ahol minden ágensnek számolnia kell a többi ágens cselekvésével, mivel azok hatással vannak rá is (pl, sakk, reversi). Az MI-ben a játékok általában igen specializáltak – amit a játékelméleti szakemberek determinisztikus, váltott lépésű kétszemélyes, zérusösszegű teljes információjú játékoknak neveznek. Vagyis: - Egy determinisztikus, megfigyelhető világban az ágensek cselekvései váltják egymást - A játék végén a hasznosságértékeik mindig azonosak, és ellentétes előjelűek. A játékot formálisan egyfajta keresési problémának is fel lehet fogni az alábbi komponensekkel: - Kiinduló állapot: tábla-állás + ki fog lépni - Állapotátmenet-függvény: megadja a legális lépéseket, és az azokból következő lépéseket - Végteszt: meghatározza, hogy mikor van vége a játéknak, ezek az állapotok a végállapotok - Hasznossági függvény: a játék végeredményéhez egy számértéket rendel hozzá, pl.: -1,0,+1 Optimális stratégia: Egy optimális stratégia olyan kimenetekhez vezet, amelyek legalább olyan jók, mintha egy tévedhetetlen ellenféllel játszanánk. Az optimális stratégia lényege, hogy a kezdőállapotból a lehetséges lépéseken át eljussunk a nyerésig. Természetesen ebbe az ellenfél is beleszól, vagyis a lépéssorozatban figyelembe kell vennünk, hogy az ellenfél is próbál törekedni az optimális stratégiára. MINMAX algoritmus: Alkalmazzuk a minmax fa minden csomópontjára az alábbi függvényt: MINMAX-ÉRTÉK(n)= Hasznosság(n), ha n egy végállapot MAX_s ∈ Követők(n)MINIMAX-ÉRTÉK(s) ha n egy MAX csomópont MIN_s ∈ Követők(n)MINIMAX-ÉRTÉK(s) ha n egy MIN csomópont Az optimális döntést az aktuális állapotból számítja ki, felhasználva az egyes követő állapotok minmax értékeinek kiszámítására a definiáló egyenletekből közvetlenül származtatott, egyszerű rekurzív formulát. A rekurzió egészen a levekig folytatódik, majd a minmax értékeket a fa mentén visszafelé terjesztjük a rekurzió visszalépésekor.

Idő-komplexitása O(bm) és tár-komplexitása O(bm), ahol m a fa maximális mélysége és b a legális lépések száma.

11. Tétel A MINMAX algoritmus bejárja az egész fát, ezért nagy fa esetén sok erőforrást használ. Ezt elkerülendő, bizonyos feltételek alapján a fa ágainak egy részét elnyeshetjük, és ezáltal ki sem kell értékelni azokat. Ha a Játékosnak van az n szülőcsomópontjánál vagy ettől feljebb egy jobb választása, akkor az n csomópontot soha nem fogjuk elérni. Ezek alapján az n csomópontot nyugodtan lenyeshetjük. Az alfa-béta nyesés két paramétertől függ: - α : az út mentén tetszőleges döntési pontban a MAX számára eddig megtalált legjobb(vagyis legmagasabb értékű) választás értéke - β : az út mentén tetszőleges döntési pontban a MIN számára eddig megtalált legjobb(vagyis legalacsonyabb értékű) választás értéke. Az alfa-béta keresés az α és a β értékeit munka közben frissíti, és a csomópontnál a megmaradó ágakat lenyesi. Az algoritmus hatékonysága alapvetően függ a csomópontok vizsgálatának sorrendjétől. Komplexitása: O(b(m/2)). Algoritmus: alphabeta( állapot, alpha, beta ) 1) if állapot = végállapot then return hasznosság( állapot ) 2) for minden s eleme lehetséges következő állapot 3) alpha = max ( alpha, -alphabeta( s, -beta, -alpha )) 4) if beta <= ( kisebb egyenlo ) alpha then return alpha 5) return alpha

12. Tétel Heurisztikus értékelő-függvények és előállításuk: Relaxálás: a probléma egy, egyszerűbb változatának a költségének a megadása. Az így kapott költséget felhasználhatjuk heurisztikának az eredeti feladat megoldásához, mivel ez a költség kisebb lesz, mint az eredeti feladat költsége. Relaxált probléma optimális megoldásának költsége a h() egy elfogadható heurisztika az eredeti problémára. relaxáció = a feltételek elhagyása. Mivel a számított heurisztika a relaxált problémára egy pontos költség, teljesítenie kell a háromszög egyenlőtlenséget is, és ebből kifolyólag konzisztens is. Automatizált relaxálás: ha a feltételek formális nyelven is adottak, akkor a relaxált problémákat automatikusan is előállíthatjuk. Heurisztikák kombinálása: h(n) = max {h1(n), …, hm(n)} Az így megkonstruált összetett heurisztikus függvény mindig azt a függvényt használja, amelyik az adott csúcspontra a legpontosabb. Mivel az alkotóelemként felhasznált heurisztikus függvények mind elfogadhatóak, ezért h is elfogadható. Továbbá h konzisztens és dominálja az összes, benne alkotóelemként felhasznált heurisztikus függvényt. Mintaadatbázisok: tároljuk az egyes részprobléma esetekhez tartozó pontos megoldási költségeket. Független részproblémák: a költségek összeadhatóak. Alfa-béta, minmax esetén - heurisztikus kiértékelő függvények a nem-végállapotokban - csak bizonyos mélységig használható (idő- és számítási igény miatt) - kiértékelés: 1. végállapotok, eredeti értékek 2. gyors, hatékony

3. a nem-végállapotokban a minmaxhoz nagyon közeli értékek (vagy legalább a nyerési esélyeket jól tükrözze)

13. Tétel Ítéletlogika szintaxisa: Az ítéletkalkulus szintaxisa meghatározza az értelmezhető mondatokat. - A szimbólumok: A|B|C|D|…. - Mondatnak nevezünk egy atomot vagy egy komplex mondatot. - Az atom egy tovább már nem bontható szintaktikai elem, amely I|H értékkel rendelkezik, vagy egy szimbólum. - A logikai jelek: ¬| ∧| ∨| → | ↔ (precendencia szerint) - A komplex mondat: ¬mondat | mondat * mondat, ahol * ∈ { ∧, ∨, → , ↔ } A zárójeleket a precendencia szabályok figyelembe vételével elhagyhatjuk. Ítéletlogika szemantikája: A szemantika definiálja a szabályokat ahhoz, hogy meghatározzuk egy mondat igazságértékét. 1. modell: (lehetséges világ): a szimbólumokhoz igazságértékeket rendel. Pl.: Egy három szimbólumot tartalmazó mondat esetén a 23 = 8 db különböző modell lehetséges. 2. mondatok igazságértéke: A mondatok igazságértékét rekurzívan lehet meghatározni. Minden mondat atomokból és logikai jelekből épül fel, emiatt meg kell határoznunk az atomok, majd a komplex mondatok igazságértékét. (a) atomok: I = igaz, H = hamis, a szimbólumok értékét a modell határozza meg. (b) komplex mondat: a logikai műveletek igazságtábláival meghatározható az értékük

14. Tétel Logikai következmény T és f mondatok. Ekkor T |= f akkor és csak akkor, ha minden modellben és minden interpretációban, ahol T igaz értéket vesz fel, f is igaz értéket vesz fel. Kvantorok kiértékelése ∀xf(x) = ⌐∃ x ⌐f(x), stb (csak ∀ vagy ∃ is elég) ∃ x∀y f(x,y) ≠ ∀y∃ x f(x,y) (pl f(x,y) : x vezeti y-t) Logikai következtetés: A kvantoroktól megszabadulunk és a következtetési szabályokat felemeljük (lifting) úgy, hogy a finomszerkezetre figyelünk behelyettesítésekkel. kvantorok : xf(x) => f(c), ahol c skolem konstans szimbólum. Általában a skolemizáció: Ha y ∃ kvantorok között, és az x1,...,xn ∀-el kötött változókhoz tartozó ∀ kvantorok hatáskörében van, akkor helyettesítünk F(x1,...,xn) skolem függvénnyel. Lifting: P1',...,Pn', P1,...,Pn : atomok P1' ,... ,Pn' ,(P1∧…∧ Pn→q) helyettesít (Θ , q) Ahol Θ helyettesítés azon szabad változók helyettesítése olyan termekkel, amelyek más mondatokban előfordulnak. Kielégíthetőség alapú algoritmus: három fő lépésből áll 1. vegyünk (α ∧¬β)-t, és alakítsuk konjuktív normálformára 2. alkalmazzunk mélységi keresést a következő térben: keresési tér: atomok egy részhalmazához igazságértéket rendelünk kezdőállapot: egyik atomhoz sincs érték rendelve operátor: egy nem hozzárendelt atomhoz igazat illetve hamisat rendel hozzá

célállapot: kielégítő modell ⇔ tétel hamis 3. (A ∨ B) ∧ (A ∨ C) igaz, ha A igaz, ezért vágni lehet. Egy szimbólum tiszta szimbólum, ha mindig ugyanazzal az előjellel szerepel minden klózban.

15. Tétel Következtető algoritmusok: logikai ekvivalencia: α és β logikailag ekvivalens, (α ≡ β), ha ugyanazok a modelljeik tautológia: P tautológia, ha minden modellben igaz, jelölése: |= P dedukciós tétel: Minden α és β mondatra teljesül, hogy α |= β, akkor és csak akkor, ha |= α → β kielégíthetőség: Egy mondat kielégíthető, ha van olyan modell, amelyben igaz. - α tautológia ⇔ ¬α kielégíthetetlen - α kielégíthető ⇔ ¬α nem tautológia reductio ad absurdum(indirekt bizonyítás): α |= β ⇔ (α ∧ ¬β) kielégíthetetlen. Itt az α a tudásbázis, a β a tétel amit bizonyítani akarunk α-ból. Rezolúció az ítéletlogikában: Rezolúció során is az a cél, hogy a (α ∧¬β) kielégíthetetlenségét bebizonyítsuk. Iteratívan mélyülő keresés a következő térben: keresési tér: konjuktív normál formulák kezdőállapot: (α ∧¬β) konjuktív normál formája operátorok: a rezolúció és hogy az azonos literálokból csak egy maradjon célállapot: az üres klóz. Az üres klóz azonosan hamis, ekkor a β tétel. Az S klóz rezolúciós lezártja RC (S), az összes olyan klóz halmaza, amely levezethető S-ből rezolúcióval. Ez bizonyítja a rezolúció teljességét. Tétel: Ha klózok egy halmaza kielégíthetetlen, akkor a rezolúciós lezártjuk tartalmazza az üres klózt. Bizonyítás: A tételt a kontrapozíciójával bizonyítjuk: Ha RC (S) nem tartalmazza az üres klózt, akkor S kielégíthető.

16. Tétel Elsőrendű logika szintaxisa: mondat → atom | (összekötő mondat) | kvantor változó mondat| ⌐ mondat atom → predikátum (term, …) | term = term term → függvény (term, …) | kvantorok | változó összekötő → ∧| ∨| → | ↔ kvantor → ∀ | ∃ kvantorok → A | B | C (nagybetűk) változók → x | y | z (kisbetűk) Elsőrendű logika szemantikája: Ítéletkalkulus egy lépése : Lehetséges világok közül választunk, ez a modell az elsőrendű logikához, ahol a lehetséges világ a domain, ami a létező objektumok halmaza (D). Ehhez még kell egy interpretáció, ami a következő: Minden kvantorhoz rendel elemet a domainből. Minden függvényhez (n változós) rendel egy Dn → D függvényt. Minden predikátumnévhez (n változós) egy Dn → {igaz / hamis} függvényt. Egy fix domain-en, sok különböző interpretáció is lehet. Kvantorok: Legyen f egy mondat, amelyben szerepel az x változó. x szabad változó, ha - f atomi mondat - <=> ⌐f1 -ben szabad változó

- <=> f összetett (pl f1 ∧f2) és x szabad f1-ben vagy f2-ben - f=∀y f1 (vagy ∃ y f1) és x ≠ y x kötött változó, ha - x szerepel f-ben és nem szabad

17. Tétel Rezolúció az elsőrendű logikában: Két klóz, amelyek standardizálva vannak, tehát nem tartalmaznak azonos változókat, akkor rezolválható, ha tartalmaznak komplemens literálokat. Akkor komplemensek a literálok, ha az egyik egyesül a másik negációjával. egyetlen-szabály : két klózra l1 ∨… ∨l2 , m1 ∨… ∨mn helyettesít(Θ , l1 ∨… ∨li-1 ∨li+1 ∨… ∨l2 ∨m1 ∨… ∨mj-1 ∨mj+1 ∨… ∨mn) (lifting a rezolúció szabályhoz) ahol helyettesít (Θ, li) = helyettesít (Θ, ⌐mj) Lépések: 1. Vegyük fel ⌐β -t : α ∧β -ból indulunk 2. α ∧⌐β konjuktív normálformája kell • ⌐ -t automatikusan bevisszük • csak ∧és ∨marad • konstansoktól megszabadulunk • literálok klózait hozzuk létre (∧-t kivisszük) Bináris rezolúció: A komplemens literál pároknál, olyan helyettesítéseket alkalmazunk, hogy megegyezzenek, majd elimináljuk ezeket. Pontosan két literált old fel. Tétel: A rezolúció cáfolás-teljes, azaz ha β logikai következmény, találunk bizonyítást, de ha nem, akkor nem kell bizonyítani. Bizonyítás: hasonló mint az ítéletkalkulus. Gödel tétele: Minden ellentmondásmentes, a természetes számok elméletét tartalmazó, formális-axiomatikus elméletben megfogalmazható olyan mondat, mely se nem bizonyítható, se nem cáfolható.

18. Tétel Előre láncolás elsőrendű logikában: Horn-hoz hasonló adatbázis formátum. Határozott klóz : f1 ∧f2 ∧...∧fk → fk+1, ahol fi-k atomok (pozitív literálok) Tények: pozitív literál Literálok paraméterei: ha csak konstans vagy változó, akkor DATALOG formátum (függvényt nem engedünk). Kvantorokat továbbra is úgy kezeljük, ahogy eddig: Két módus komponens-t használunk a liftingel → ugyanaz, mint az ítéletkalkulus, de: 1. algoritmus kell, az összes lehetséges helyettesítés megtalálásához 2. akkor van vége, ha egy új formula és a bizonyítandó α közös alakra hozható helyettesítésnek, vagy nincs új formula (ekkor α nem logikai következmény) Mintaillesztés komplexitása: A változók miatt az elsőrendű logikában MP lehetséges alkalmazásaink előállítása NP nehéz. Visszafelé láncolás Ugyanaz, mint az ítéletkalkulus, csak a helyettesítésekre kell figyelni 1. A helyettesítések Θ halmaza kezdetben üres. 2. Mélységi bejárással ezt a halmazt fokozatosan bővítjük, hozzáadva az új helyettesítéseket (amíg lehet).

3. A művelet sikeres, ha eljutunk a tényekig, melyek a levelekben vannak, ebben az esetben megkapjuk a behelyettesítést is. 4. A mélységi keresés miatt nem teljes és ismétlődő állapotok is lehetnek. 19. tétel: valószínűség alapfogalmai: véletlen változók, elemi események, valószínűség, feltételes valószínűség, valószínűség axiómái Véletlen változók: Az ítéletkalkulusban megismert ítéletek szerepét fogják betölteni, logikai operátorokkal, formulák készíthetők velük. A véletlen változók lehetséges értékeit (értéktartományát) nevezzük domaineknek. Jelölés szerint mindig nagybetűvel jelöljük a változó neveket, kisbetűvel az értékeiket. A véletlen változók tipikusan három típusba sorolhatók: 1. Boole - típusú 2. Diszkrét véletlen változók 3. Folytonos véletlen változók Elemi események: Az elemi esemény analógnak tekinthető az ítéletkalkulusbeli modellel (ha csak logikai véletlen változók vannak). Valószínűségi változókkal definiáljuk őket. Az elemi esemény egy olyan kijelentés, ahol minden egyes valószínűségi változóhoz szerepel (értéket kap), és ezeket konjugálom. Az elemi események tulajdonságai: egymást kölcsönösen kizáró események, legfeljebb egy lehet igaz, az összes elemi esemény halmaza kimerítő, tehát legalább az egyiknek igaznak kell lennie, az előző kettőből tehát az következik, hogy a világ aktuális fennállását pontosan egy darab elemi esemény írja le, egy elemi esemény minden lehetséges elemi kijelentéshez igazságértéket rendel, minden kijelentés logikailag ekvivalens a neki nem ellentmondó elemi eseményeket leíró kijelentések halmazával. Valószínűség („a priori” valószínűség): Minden kijelentéshez valószínűséget rendelünk. Egy ’a’ állításhoz tartozó priori (feltétel nélküli) valószínűség az a meggyőződési mérték, amely bármely más információ hiányában az állításhoz kapcsolható. Jele: P(a) Feltételes valószínűség: P(a|b), ahol „a” és „b” kijelentések. Ennek jelentése, hogy „a” valószínűsége ennyi, ha tudom, hogy „b” igaz, és a teljes tudásunk „b”. Technikai definíció: P(a|b) = P(a , b) / P(b). Egyszerűbb definíciója a szorzatszabály, amelyben „a” és „b” szerepe felcserélhető. P(a „és” b) = P(a|b)P(b) = P(b|a)P(a) P(A|B) pedig nem más, mint a P(A=ai | B=bj) értékek táblázata, ahol ai és bj A és B értékei minden párosításban.

1. 2. 3.

A valószínűség tulajdonságai és axiómái: Az eddigiekben szintaxist definiáltunk, most meg kell fogalmaznunk egy szemantikát is. Ezt az axiómákkal kezdjük: A valószínűség mindig [0,1] között van. Azonosan igaz esemény logikai valószínűsége mindig 1, azonosan hamis esemény logikai valószínűsége mindig 0. P(A ∪ B) = P(A) + P(B) – P(A ∪ B)

20. tétel: valószínűségi következtetés diszkrét változókkal, eloszlás reprezentációjának tömörítése: függetlenség Kiindulás a teljes együttes eloszlás, azaz elemi események valószínűségei (véletlen változók bármely értékkombinációja). Tehát a következtetéseinket a teljes valószínűségi eloszlás alapján tesszük fel. Egyszerűsítő jelölésmódot vezethetünk be: P(A) = ∑b P(A,b), ahol A egy változó, vagy változók egy halmaza, és „b” az A-n kívüli változók összes értéke. A szorzatszabállyal ugyanez: P(A)= ∑b P(A|b)P(b). Itt annak a változónak a feltétel feletti eloszlását kapjuk meg, amelyet tartalmazó együttes eloszlásokból kiátlagoljuk az összes többi változót a szorzatszabályban, melyet feltételfeloldásnak nevezünk (conditioning). Általában: P(A|b) = α P(A,b) = α∑x P(A,b,x) , ahol α: normalizálási konstans, b: ismert tények (kijelentések), x: azon változók összes lehetséges értéke, amelyeknek az értéke ismeretlen (ezekből képzett kijelentések), A: változó, érdeklődésük tárgya. A függetlenség: Kétfajta függetlenségről beszélünk: 1. abszolút függetlenség (két véletlen változó független – hatékonyan használható valószínűségi tábla redukálására), 2. feltételes függetlenség (finomabb módszer, további tömörítést tesz lehetővé). Ebből következik a definíciót: - a és b függetlenek akkor és csak akkor, ha P(a „és” b) = P(a)P(b), ahol a és b kijelentések, - A és B változók függetlenek akkor és csak akkor, ha P(A,B) = P(A) P(B). Ezzel ekvivalens definíciók: 1. P(A|B)=P(A) 2. P(B|A)=P(B). Ha változók egy halmaza felbontható független részhalmazokra, akkor csökkenthető a teljes együttes eloszlás tárolási mérete. Ekkor minden részhalmazhoz elég az együttes eloszlás lokálisan, ezáltal sokszor nagy tömörítést érhetünk el.

21. tétel: feltételes függetlenség, Bayes szabály, Bayes háló definíciója Feltételes függetlenségről: Lehet, hogy a és b általában nem függetlenek, viszont létezik c úgy, hogy P(a „és” b|c) = P(a| c)P(b|c). Ekkor a és b kijelentések feltételesen függetlenek (c feltevésével), például akkor, ha a és b közös oka c. Általában A és B változó függetlenek, akkor és csak akkor, ha létezik C úgy, hogy P(A|B,C) = P(A|C)P(B|C). A definícióval ekvivalens két másik definíció: P(A|B,C) = P(A|C) és P(B|A,C) = P(B|C). Bayes - szabály:

P  a∣b  P  b  Pa Bizonyítás: P(a „és” b) = P(a|b)P(b) = P(b|a)P(a) P  A∣B  P  B  Általában is: P(B|A) = , ahol A és B véletlen változók halmaza P  A 1. Feltételes függetlenség kompakt reprezentációja használható. 2. A gyakorlatban sokszor a jobb oldalon lévő példák ismertek, míg a bal oldaliak nem. Másik alakja (α normalizálási konstans használatával): P(B|A) = α P(A|B)P(B), itt α adódik az 1-re normalizálásból, de a teljes eloszlást ki kell hozzá számolni. Állítás: P(b|a) =

Bayes háló: Olyan adatstruktúra, mely a feltételes függetlenségeket ragadja meg, és egy teljes együttes eloszlás tömör reprezentációja. Részei: 1. Csúcsok: véletlen változók 2. Élek: függési reláció ( ha X → Y él, akkor X az Y szülője) 3. Feltételes eloszlás: P(X | X szülői) 4. A háló DAG azaz körmentes irányított gráf A háló nem egyértelmű, az eloszlást több háló is leírhatja! 22. tétel: Bayes háló konstruálása diszkrét változókból, zajos-vagy Belátható: legyenek a változók X1,…, Xn 1. Ha az Xj nem leszármazottja Xi-nek, akkor P(Xi | Szülők(Xi), Xj) = P(Xi | Szülők(Xi)) 2. Ha az Xj tetszőleges változó, akkor P(Xi | Markov-takaró(Xi), Xj) = P(Xi | Markov-takaró(Xi)) Markov - takaró: Szülők ∪ Gyerekek ∪ Gyerekek szülői Tehát Xi csak a Markov - takarótól függ. További tömörítés: Ha „k” szülő van, akkor 2k méretű táblázat kell az adott változóhoz. Ha „k” kicsi, akkor konstans, nem rossz de gyakran még kevesebb információ is elég. Determinisztikus változók: a szülő változók értékeinek függvénye Pl.: Xi = min(Szülők(Xi)) „Zajos-vagy” („noisy-or”): 2k helyett k (ahol pont egy „i” van) a többi ebből számolva (egyszerűsítés de tömör)

23. tétel: valószínűségi következtetés Bayes hálókban: exakt képletek, közvetlen mintavétel, elutasító mintavétel, valószínűségi súlyozás Exakt eset: tudjuk, hogy a teljes együttes eloszlásból kiszámolható, de a Bayes - hálóból kiszámolható a teljes együttes eloszlás. Műveltigény: Kiemelés előtt: O(n2n) Kiemelés után: O(2n) Ezeken lehet javítani: lehetőleg minden részsorozatot csak egyszer számoljunk ki (dinamikus programozás) Közvetlen mintavétel: Célok: 1. Teljes együttes eloszlás szerint generálni változó hozzárendeléseket véletlenszám-generátorral (új mintát könnyebb venni, mint minden lehetséges hozzárendelés valószínűségét megadni) 2. A generált hozzárendelésekben megfigyelt gyakoriságokkal közelíteni a valószínűséget A szülő nélküli változókkal kezdjünk és lefelé haladjunk, majd a mintavételt sokszor ismételjük. Elutasító mintavétel: P(A | b) = α P(A,b) helyett vegyük P(A | b) = lim

N ∞

N  A,b 1 mászóval α ¿ közvetlenül N b N b

kiszámolható. Valószínűségi súlyozás (likelihood weighting): Számolás: minták gyakoriságának számolása helyett a súlyokat adjuk össze m1,…mn mintákra  a , b , c  szerepel mi−ben és w1,…,wn súlyokra. N helyett ∑ wi és N(a,b,c) helyett i ∑ ¿¿¿ ¿

24. tétel: felügyelt tanítás problémája, alapfogalmai, indukció problémája Felügyelt tanulás (induktív tanulás - inductive learning): Egyszerű függvényillesztéstől a fizika tudományáig sok mindent lefed. Adott egy ismeretlen f : A → B függvény és (x1 , (f (x1)) , ... , (xn , f ( xn)) példák. Keresünk egy h : A → B függvényt, ami f-et közelíti. A h függvény a H hipotézistér eleme, H lehet pl. maximum k fokú polinomok, vagy bármi más. Indukció problémája: Az f jó közelítése olyan h, amely ismeretlen x-re is jól becsüli f(x)-et (nem csak az adott példákra) , azaz jól általánosít. f  x  , ha ismert a példa 0, egyébként ¿ Pl.: Ha h(x) = {¿ ¿ ¿ ¿ akkor h egyáltalán nem általánosít, de a tanító példákat tökéletesen tudja. Ebből következik, hogy: 1) Törekszünk tömörebb reprezentációra, mint az adatok: Ockham borotvája (Ockham's razor): a lehető legtömörebb leírás, ami még elég Kolmogorov-komplexitás (algoritmikus komplexitás):

2)

Törekszünk egyszerű reprezentációra a hatékonyság miatt is, mivel egyszerűbb reprezentációban könnyebb keresni.

25. tétel: döntési fák Döntési fák (decision tree): Bemenetként egy attribútumokkal leírt objektumot vagy szituációt kap, és egy döntést ad vissza eredményként – a bemenetre adott válasz jósolt értékét. Mind a bemeneti attribútumok, mind pedig a kimeneti érték lehet diszkrét vagy folytonos. Feltesszük, hogy x ∈ A diszkrét változók értékeinek vektora, és f(x) ∈ B diszkrét változó egy értéke (pl. B = {igen, nem}) Ha a függvény értékkészlete, f(x): - diszkrét, a függvény tanulását osztályozás (classification) tanulásnak, - folytonos, a függvény tanulását regressziónak (regression) nevezzük. Döntési fák kifejezőereje: Várakozás ↔ (A1 ∩ ... ∩ Am) ∪ (B1 ∩ ... ∩ Bn)... Útvonalak „igen” levélbe, Ai, Bi pedig az elágazások. A formulában a diszjunkciós tagok mindegyike azon tesztek konjukciójának felel meg, amelyeket a gyökértől egy pozitív kimenetet jelentő levélig megtett út során végeztünk. Ez éppen egy ítéletkalkulusbeli kifejezés, mivel csak egyetlen változót tartalmaz és minden predikátum unáris. 1.) Ítéletek, pl.: Vendégek = Senki, Vendégek = Néhány, stb. 2.) Az x egy modell. 3.) A döntési fa pedig logikai formula, f(x) a formula kiértékelése. Milyen tömör lehet? Láttuk, hogy ha véletlen, nem tömöríthető. De nem tömöríthető a paritásfüggvény (akkor és csak akkor ad 1-et, ha páros számú bemenet 1 értékű), ekkor egy exponenciálisan nagy döntési fára lesz szükség. Vagy a többségfüggvény (akkor ad 1-et, ha a bemeneteinek több, mint a fele 1 értékű). Az összes változót tudni kell - illetve O(n) - et. Döntési fa építése: Egy logikai döntési fa által kezelhető példa a bemeneti attribútumok X vektorából és egyetlen logikai kimeneti értékből, y-ból áll. Heurisztika: A lehető legjobban szétválogatjuk a pozitív és negatív példákat, így a gyökérbe kerül azaz attribútum, amely a legjobban szeparál. (rekurzív algoritmus): 1.) Válasszuk ki a gyökeret és szeparáljuk a példákat, 2.) Minden ágon a maradék attribútumokra és az oda eső példákra rekurzívan ugyanez. Az esetek, amiket vizsgálni kell a rekurzióban: 1.) Pozitív és negatív példa is van: szeparáljuk őket a legjobban egy attribútumot választva. 2.) Csak pozitív vagy csak negatív példa van: leáll, ez az ág kész. 3.) Nincs példa, de attribútum még van, ekkor „default” érték, és heurisztikát alkalmazunk. 4.) Ha pozitív és negatív példa is van, de nincs több attribútum, azaz hiba (zaj) a példákban. Ekkor heurisztikát alkalmaz, pl. többségi szavazat (ha több volt a pozitív, akkor pozitív lesz.) A legjobban szeparáló attribútum: Adott változó ismerete mennyivel növeli az információt arról, hogy egy példa „igen” vagy „nem”. Információ – információelmélet:

A p valószínűségű esemény információtartalma: −log(p). Ha log2-t használunk, mértékegysége a bit. Véletlen változó átlagos információtartalma (entrópia): Σi −pi log2(pi) ( p1 , ... , pn , valamint az eloszlás: 1=Σ pi ). Döntési fa egy csomópontjának információtartalma: Legyen p a csomópont alatti pozitív, n pedig a negatív példák száma, a csomópont A. −p p n n − I(A) = log2 log2 pn pn pn pn Információ-nyereség A-ban: A gyerek csúcsainak az átlagos információtartalma azt fejezi ki, hogy A - szerint felbontva mennyi „bizonytalanság” marad. Legyenek B1 ,... , Bv A gyerek csúcsai. (A-nak v értéke van, ami v részhalmazra osztja a példákat.). Legyenek E1 , ... , Ev a megfelelő példa részhalmazok, ahol |Ei|=ni+pi . v pi ni I  B i  ,ahol a maximális nyereségű attribútumot választjuk. Nyereség (A) = I  A−∑ i=1 pn 26. tétel: induktív tanuló algoritmusok kiértékelése A tanító halmazon építjük a modellt (pl. döntési fát), a teszt halmazon értékeljük ki. „Kukucskálás” (peeking): Ha a teszteredmények alapján finomhangoljuk az algoritmus paramétereit, akkor a modell függ a teszttől, és a teszthalmazra van optimalizálva. Túlillesztés (overfitting): a „magolás” egy általánosabb formája a túlillesztés, amikor túl messzemenő következtetéseket vonunk le kevés adatból. Kisszámú példák miatt nem igazi minták alakulhatnak ki. Keresztvalidáció (cross-validation): A tanító / teszt felosztás általánosítása, ez a módszer alaposabban szeparál: 1.) Osszuk fel a példákat K egyenlő részre. 2.) Építsünk K modellt a következőképpen: vegyük valamely részhalmazt, mint teszt halmazt és a többi K-1 – et tanítsuk. 3.) Értékeljük ki a K modellt a megfelelő teszthalmazon és vegyük a K értékelés átlagát, ez lesz az értékelés. Megbízhatóbb kiértékelés, hiszen az összes elemet felhasználtuk tesztadatnak. Alkalmazás: Ha van m darab algoritmusunk, mindet kiértékeljük keresztvalidációval, és a legjobb algoritmus segítségével építünk modellt az egész példahalmazon. Ez lesz a végeredmény. Döntési fa specifikus technika (keresztvalidációs algoritmus független): Azért, hogy az irreleváns attribútumokat ne építse be az algoritmusba. Pl. statisztika alkalmazásával. => Valamit tanulni fog, de az biztos tévedés lesz! 27. tétel: hipotézis együttesek, turbózás (boosting), AdaBoost algoritmus Hipotézisegyüttesek (ensemble): Sokszor jó ötlet egy modell (hipotézis) helyett többet gyártani, esetleg más algoritmusokkal, és pl. többségi szavazást alkalmazni. 1.) Modellek hibái nem pont ugyanazok (ideálisan: függetlenek), ezért statisztikailag megbízhatóbb. 2.) Kombinálhatunk is az egyszerűbb modelleket. Turbózás (boosting): Gyenge algoritmusok együttesét állítja elő, amelyek így a tanuló halmazt helyesen osztályozzák. Gyenge algoritmus (weak algorithm): Amely „jobb, mint a találgatás”, azaz 50 % – nál több példát képes helyesen osztályozni a legyártott modell. Jelöljük a gyenge algoritmust Llel.

Ada Boost algoritmus: AdaBoost (példák, L, M) // példák: N darab példa, (xi , yi) , i=1, ... , n // L : tanuló algoritmus (gyenge) // M: hipotézisek száma az együttesben // wi : (xi , yi) súlya, 1/N kezdetben // hi : i-edik hipotézis ( i=1, ... ,M ) if hm(xj) = yj then wj ← wj * error / (1 – error) w ← Normalizál(w) zm ← log[(1 – error) / error] return SúlyozottTöbbség(h, z)

// zi : i-edik hipotézis súlya for m = 1 to M hm ← L(példák, w) error ← 0 for j = 1 to N if hm(xj) ≠ yj then error ← error + wj for j = 1 to N

28. tétel: Bayes tanulás, MAP tanulás, maximum likelihood tanulás (definíciók) A Bayes - tanulás során egyszerűen kiszámoljuk minden egyes hipotézis valószínűségét az adatokra támaszkodva, majd ezek alapján adunk predikciót. Azaz az összes hipotézist használjuk, s valószínűségükkel súlyozzuk őket. A hipotézisek valószínűségét a Bayes szabállyal adjuk meg: P (hi|d) = α P(d|hi)P(hi), ahol α az egy konstans α = 1 / P(d), d a megfigyelt adatok. Ha egy X értékét akarjuk jósolni, akkor ez a képlet: P (X|d) = Σi P (X|d, hi)P (hi|d) = Σi P (X |hi)P (hi|d) Ezek után három nagyon fontos fogalmat kell tisztáznunk: Prior, P(hi): hipotézisek a priori valószínűsége, azaz adott hipotézis fennállása, ha még semmit nem tudunk a világról, Pl.:(komplex hipotézisekhez lehet kisebbet, egyszerűbb hipotézisekhez nagyobbat) Likelihood, (könyvben adatvalószínűségként említik): P(d | hi) : megfigyelések valószínűsége hi mellett Posterior P(hi | d) : hipotézis a posteriori valószínűsége, azaz tapasztalat utáni valószínűség A Maximum a posteriori tanulás (MAP) módszerében a priorokkal súlyozott összeg helyett a legvalószínűbb hipotézis alapján végezzük a predikciót, azaz a maximális P(hi | d)-hez tartozó hi-t használjuk. Tehát vesszük a valószínűségeket, s kiválasztjuk a maximumot. A MAP felhasználja a prior valószínűségeket, s ebből számol posteriort, de a döntést már nem átlagolja, hanem a maximálisat fogja, és a többit figyelmen kívül hagyja. A maximális hipotézist keresi. A MAP hipotézis alapján végzett predikációk közelítőleg Bayes-predikciók. Ám ez sokkal veszélyesebb módszer, mert túl gyorsan következtetünk A Maximum-likelihood tanulás esetén további egyszerűsítéseket teszünk, mégpedig hogy bármely hipotézis a priori valószínűsége egyenlő. (pl.: ugyanolyan komplex hipotézisek). Ekkor vesszük a maximális P(d | hi)-hez tartózó hi -t. Nagyon sok adatnál ugyanoda konvergál, mint a Bayes és a MAP, de kevés adatnál érzékeny, problémák merülhetnek fel az alkalmazásánál.

29. tétel: log-likelihood technika, illusztrációja két példával Tanulás teljesen specifikált példákból Tegyük fel, hogy: az összes tanítópéldában minden változó értéke adott, ami a terület valószínűségi modelljében szerepel. Maximum likelihood: diszkrét változók 1. példa: meggy\ citrom, de most Θ a megy aránya, Θ ismeretlen. hipotézis: a meggy aránya Θ • nevezzünk meg N db cukorkát: o legyen m db meggy, c db citrom, [c=N-m] o ekkor az adathalmaz valószínűsége, ha a minták függetlenek:  P (d| ) = = m(1- )c  Melyik Θ - ra maximális?  Ehhez: L (d| ) = log P (d| ) = =m*log + c*log (1 - ). [a log P()-nek ugyanott van a maximuma, de gyakran könnyebb kiszámolni] [elég természetes eredmény]. Megint keresési probléma (maximum). Gyakran nem ilyen egyszerű, hanem pl. hegymászó, stb. kellhet. Megjegyzés: kevés adathalmaz esetén, pl. ha N=1, azt mondja, hogy minden cukor citrom (vagy meggy) [nem használ priorokat] 

•

2. példa: most legyen kétféle csomagolás: piros és zöld a fenti Bayes hálóval kifejezett eloszlás szerint. • Három paraméter: Θ, Θ1, Θ2 • pl. P (meggy, zöld | ) = P (zöld | meggy, ) * P (meggy | ) = Θ (1Θ1) • megint van N db példánk: m db megy, c=N - m citrom • legyen Pm + Zm =m a piros és zöld csomagolású meggyek száma, Pc + Zc = c hasonlóan. • Ekkor P (d | )= Megint logaritmust véve tagonként maximalizálhatjuk: o megint természetes eredmény, azaz belátható, hogy diszkrét Bayes - hálóhoz mindig hasonló eredmény, azaz minden táblázatot egymástól függetlenül becsülünk. 30. tétel: naiv Bayes algoritmus Bayes - szabály:

P  a∣b  P  b  Bizonyítás: P(a „és” b) = P(a|b)P(b) = P(b|a)P(a) Pa P  A∣B  P  B  Általában is: P(B|A) = , ahol A és B véletlen változók halmaza P  A Feltételes függetlenség kompakt reprezentációja használható. A Bayes - szabály során az okból az okozatra következtető valószínűséget használjuk fel arra, hogy okozatból okra következtető valószínűséget kapjunk. Másik alakja (α normalizálási konstans használatával): P(B|A) = α P(A|B)P(B), itt α adódik az 1-re normalizálásból, de a teljes eloszlást ki kell hozzá számolni. Naiv Bayes - következtetés: Állítás: P(b|a) =

Adottak: • Y megfigyelési vektor (y1, …, yn) • V osztályok halmaza {v1, …, vk}

Naiv Bayes tanulás: o itt O(N) táblázat van: adatokból becsülhetőek a paraméterek maximális likelihood szerint. o O(N) db osztás kell csak, és a P(c | x1, … , xn) = αP(c) becsülhető o megjegyzés: olcsó, és ehhez képest elég jó 31. tétel: Bayes tanulás a béta eloszlás segítségével, illusztráció egy példával, konjugált prior fogalma Bayes tanulás • cukorkás példa ( paraméter, N minta), de most prior is van: P(O) = P( = O) [O: hipotézis véletlen változó] • pl. O – nak lehet egyenletes eloszlása ( [0,1] - en) [ ekkor maximum likelihood]. gyakorlatban gyakran veszünk béta eloszlást: a-1 o béta [a, b] ( ) = (1 - )b-1 sűrűségfüggvény. •

• •

paraméterek: a,b : … konstans o a = 1, b = 1 : egyenletes o a = b: szimmetrikus o a + b nagy: „csúcsos” o E(O) = a/ a +b legyen a prior beta[a,b]( O), ekkor egy D1 adat után: P( | D1=meggy) = P (D1 = meggy | ) P( ) =

beta[a,b]

)=

a

(1

)b-1

= beta[a+1,b]( ) • ez a konjugált prior tulajdonság, azaz a prior eloszlása ugyanaz, mint a posterioré, csak más paraméterekkel. 32. tétel: példa alapú tanulás: k legközelebbi szomszéd, kerneln A tanulás arról szól, hogy modellt húzunk az adatokra, és a modell alapján a meg nem látott dolgokat szeretnénk általánosítani, megjósolni előre. A példa alapú tanulás is hasonlóról szól. Adott (x1, y1)…(xn, yn) példák. Klaszterezési feladatnál például x alapján kell y-t megmondani. A tanítópéldáknál ezt előre megmondjuk. Ötlet: ismeretlen x kiértékelése „hasonló” ismert példák alapján. Ezekből a tapasztalatokból állítsuk elő y-t. Nincs explicit modell, vagy függvény, hanem úgymond halmazzal tanítunk, de egyáltalán nem „magolásról” van szó.

Legközelebbi szomszéd modellek: 1. Keressük meg x-nek a k legközelebbi szomszédját. Globális heurisztikának tekinthető, nagyon általános érvényű („hasonló dolgok hasonlóképp viselkednek”). Ha ezt a Touring-gépek halmazán tekintjük, ez egy merész heurisztika. 2. h(x) a szomszédok y-jainak átlaga (esetleg távolság szerint súlyozott) ha folytonos a probléma, v a szomszédok y-jainak többségi szavazata (diszkrét). Ha csak x1…xn adott és y-ok nem, akkor a p(x) sűrűség közelítése is jó, azaz milyen valószínűséggel jönnek adott inputok a továbbiakban. Nézzük meg, hogy k legközelebbi szomszéd mekkora területen oszlik el? (sűrűség: pontok / terület) fontos: távolságfüggvény D(x1, x2) 1. folytonos változónál normalizálni kell a dimenziókat (pl, súly, magasság nem ugyanaz a skála, ellipszisként képzelhetjük el a vizsgált területet). Ekkor vehetjük például minden jellemző szórását, és a jellemző értéket a szórás többszöröseiként fejezzük ki. Folytonos esetben érdemes valamilyen euklideszi távolságot venni. 2. diszkrét esetben Hamming távolság: különböző jellemzők száma (hány változóban különbözik), pl. H(001,111) = 2 (2 helyen különbözik) egyszerű, de sokszor jó tanuló algoritmus. Problémái: - érzékeny a távolság-függvényre (holott a módszer egyszerű ötleten alapszik) - nagy adathalmazokon költséges a k szomszédot megtalálni (néha még végigmenni is költséges egy adathalmazon,  internet), ilyenkor a modellépítés célravezetőbb lesz - ha sok jellemző van (sokdimenziós tér) akkor kb. „mindenki közel van mindenkihez”. Kernel módszerek: Módszer: minden példát saját jogán veszek figyelembe (szomszéd nincs). Minden példához hozzárendelek egy saját függvényt (pl. harang-alakú függvényt), ami azt mutatja, milyen súllyal vesszük a példát figyelembe. Minden xi példához veszünk egy K(x,xi) kernel függvényt, pl xi várható értékű, szigma normális eloszlás. Általában a K függvény egy sűrűség-(illetve diszkrét esetben eloszlás-) függvény. - sűrűség közelítése egy x pontra. p(x) = (1/n)ΣK(x,xi) - h(x) közelítése: K-val súlyozott átlag Megjegyzés: itt minden tanítópéldát figyelembe veszünk 33. tétel: perceptron: definíció, kifejező erő, tanuló algoritmus Neuron absztrakt modellje:

Inputok: tipikus a kétértékű input. Minden inputhoz (aj) tartozik súly, wj,i, ahol i a neuron indexe. Összeszorozzuk az inputokat a súlyokkal, aztán az egészet össze szummázzuk. (belső szorzat) wo,i: eltolássúly (bias weight)

a0 lineáris bemenet az eltolás kapcsolaton (-1) fix input, nagy jelentőségű. A lineáris függvények eltolásához hasznos lesz. Inputtól nem függ. (Meghatározza, hol lesz a küszöbérték) g: (0,1) közé képez le. Leggyakoribb, lépcsős vagy szigmoid

Aktivációs függvény: 1. Ha jó input jön, adjon 1-koruli értéket, ha rossz, akkor 0 körülit 2. Nemlineáris legyen  küszöbfüggvény vagy szigmoid függvény (1/(1+e-x)) 3. g(ini) éppen wo,i-nél fog változni 0-bol 1-be 4. szigmoid deriválható  tanuló algoritmusnak jobb Általában osztályozási feladatot adunk a neuronoknak. Nem tipikus használat: logikai kapuk. Következmény: bármilyen logikai függvény modellezhető megfelelő számú neuronnal. A neurális háló általában logikailag nem (vagy nehezen) értelmezhető konstrukció. Teljesítmény szempontjából megfelelő. Gyakran túlszárnyalja a döntési fát. A neuronokból hálózatot szoktunk építeni. Az egyik neuron outputját hozzácsatoljuk a másik neuron inputjához. Tanuló algoritmus: Numerikus optimalizálás: súlyok terében gradiens módszer. Adott pontban megnézzük a függvény deriváltját, megnézzük nő-e vagy csökken, és attól függően, hogy min-t vagy maxot keresünk, ellépünk valamerre. Hasonlít a hegymászóra. A hibafüggvényt akarjuk minimalizálni. Mintapéldától és súlyvektortól függ (1-1 db). A hibának a gradiensét határozzuk meg w függvényében, ezután ellépünk a minimalizálás irányába. Technikai megoldás: hiba négyzetre emelése, hogy mindig pozitív legyen.

Lényeg: - veszünk egy (x,y) tanítópéldát és - erre az egy példára csökkentjük az E hibafüggvényt, és - ezt ismételjük többször az összes példára, amíg w konvergál. 34. tétel: többrétegű előrecsatolt neurális háló, backpropagation algoritmus Többrétegű hálók: Itt van rejtett réteg. Egy rejtett réteggel már bármilyen folytonos függvény felírható. Rejtett réteg: azok a rétegek, amik outputnál nem látszanak. 1 darab nem-rejtett réteg van (output) a többi rejtett réteg. (inputot külön kezeljük). Tanuló algoritmus: Perceptronhoz hasonló, de az output vektorok, nem skalár értékek (több output lehet), és csak az outputot látjuk, a rejtett perceptronokat nem, ebből következik a visszaterjesztés (backpropagation) algoritmus. Úgy lehet felfogni, mintha a felelősséget visszaterjesztenénk a rejtett rétegekre. A hiba ugyanúgy definiálható, a megközelítés is ugyanaz lesz. Kivétel, hogy nem csak az outputban figyelünk súlyokat. A hibának az összes súly függvényében meg lehet határozni a deriváltját. Egy konkrét képletet kell parciálisan deriválni a súly alapján, majd ez alapján elmozdulni.

35. kernel módszer alapötlete (képlet nélkül), kernel trükk, két példa kernel függvényre Hasonlít a perceptronhoz, de bizonyos értelemben elegánsabb annál. Egy függvényközelítő módszer, ami egy lineáris szeparátort próbál a perceptronhoz hasonlóan találni. A neuron csak neurális hálóval tud bonyolultabb „függvényeket” kifejezni. A kernel gépeket nem kötjük egymás után, helyette nemlineáris tereket teszünk a rendszerbe, es a lineáris szeparáció segítségével fogunk nemlineáris osztályozást elvégezni (  kernel trükk). Kernel gépek lineáris modellje Fontos különbség a perceptrontol az optimális szeparátor keresése. Legyenek (x1,y1)…(xn,yn) példák, osztályozási feladat yi {1,-1} xi Rd. Tegyük fel, hogy van egy w-vel es b-vel adott hipersíkunk, ahol w Rd a sík normálisa és |b| / ||w||2 az origótól vett merőleges távolság, es a sík egyenlete wx+b=0 (wx belső szorzat) Jelöljük d+-szal a síkhoz legközelebbi pozitív példák távolságát a síktól. Margó [d++d-] Ezt akarjuk maximalizálni. Kernel trükk Eddig optimális lineáris szeparálás volt, de xi-k csak belső szorzatban szerepelnek LD-ben. Helyettesítjük ezt egy K(xi,xj) kernelfüggvénnyel. Ha K() a belső szorzat: lineáris szeparátor. Ha más, pl:

Ahol  K() kernelfüggvény a példákat modellezi magasabb dimenzióban. Lényeg: a belső szorzatot kicseréljük egy függvényre, és akár egy magasabb dimenzióbeli nemlineáris műveletet tudunk elvégezni az eredeti műveletigénnyel. Nagy dimenzióban könnyebb a lineáris szeparáció, pl N példára N-1 dimenzióban mindig van lineáris szeparáció. A kernelgépek a K() segítségével egy lineáris szeparáció műveletigényével nemlineáris osztályozást végeznek. Két példa kernel függvényre: , így a körlap alakú terület szeparálhatóvá válik , amelyhez olyan F() tartozik, amely d-ben exponenciális számú dimenzióba képez 36. az erős és gyenge mesterséges intelligencia hipotézisei, Turing teszt, kinai szoba Gyenge MI hipotézis: készíthetünk olyan „gépeket” amik látszólag intelligensek, de „valójában” nem feltétlenül van „elméjük” (öntudatuk). Erős MI hipotézis: készíthetünk, olyan „gépeket” amelyeknek „valódi” „elméjük” van. Turing teszt: leginkább „emberi cselekvés” teszt, azaz az ember rájön-e, hogy a másik szobában egy gép van? A gépnek képesnek kell lenni: • a, természetes nyelv feldolgozására • b, tudás reprezentációjára • c, következtetésre • d, tanulásra • stb Ha a gép átmegy a teszten, azt mondjuk intelligens. De attól még öntudata van? Egyáltalán, legközelebb is átmenne? Mik a nehéz kérdések? stb. Érdekes teszt, de az MI nem erre fókuszál elsősorban.

Kínai szoba: egyik legfontosabb gondolatkísérlet 1.) adott egy szoba, benn egy ember, aki nem beszél kínaiul 2.) a szobán van egy ablak, ahol kínaiul írt szövegek (pl. kérdések, válaszok) jönnek 3.) az embernek van egy nagy könyve tele szabállyal: ezek alapján számításokat végez, és legyárt kínai karaktereket, amiket nem ért. [megjegyzés: a szoba nem kell, az ember memorizálhatja a szabályokat] Ekkor: tegyük fel, hogy a „szoba„ átmegy a Turing teszten. Ráadásul az embernek öntudata is van. Akkor ez erős MI? Nem (mondja Searl) Miért ne? (mondják mások). Pl. a szoba, mint egész esetleg „tud” kínaiul, de: vegyük észre: a kínai szoba az univerzális számítógép (Turing gép) megtestesülése ugyanaz a viselkedés megvalósulhat nagyon különböző állapotátmeneteken keresztül (pl. univerzális Turing gép futtat egy univerzális Turing gépet, stb. rekurzión). Mindegyik megvalósulásnak van elméje (azaz itt: ért kínaiul)? Vagy csak néhánynak? Vagy egyiknek sem? Vagy csak egyetlen egynek? [a kínai szoba elsőre nem tűnik jó érvnek, de nem lehet könnyen lesöpörni]