Programozási módszertan A gépi tanulás alapmódszerei ´ Werner Agnes ´ oki ¨ es ´ Informaci ´ os ´ Rendszerek Tanszek ´ Villamosmern
e-mail:
[email protected]
SZDT-12 – p. 1/24
´ Agensek • Az új szemléletu, ˝ viselkedésalapú megközelítés szerint: a
mesterséges intelligencia célja az, hogy a feladatmegoldást olyan ágensekkel végeztesse el, amelyek az intelligens viselkedés bizonyos vonásaival rendelkeznek. • Egy ágens lehet bármely dolog, amely érzékeloi ˝
segítségével észleli környezetét, majd megfelelo˝ döntéseket hozva tevékenységével visszahat rá. • Egy ágens realizálásához szükség van a következo˝ képességek bizonyos mértékére: ◦ ◦ ◦ ◦ ◦ ◦ ◦
érzékelés, észlelés, tudásszerzés, döntéshozatal, következtetés, tanulás és tevékenységvégzés. SZDT-12 – p. 2/24
˝ defin´ıcio´ (MI) Eros Az ágens egy olyan rendszer, amely a következo˝ tulajdonságokkal rendelkezik: • Beágyazottság: a környezetbe ágyazottak, abból kiemelve
nem tudnak funkcionálni (pl. egy ágens papírra nyomtatott programja nem ágens, mint ahogy egy vízbe dobott autóhegeszto˝ robot sem az). • Reaktivitás: az ágensek érzékelik környezetüket, valamint
˝ valós idoben reagálnak, az abban bekövetkezett változásokra. • Autonómia: az ágensek önállóan, emberek vagy mások
direkt beavatkozása nélkül muködnek ˝ és meghatározott mértéku˝ kontrolljuk van a saját akcióik és belso˝ állapotuk felett. • Helyzetfüggoség: ˝ az ágensek helyzethez és szerephez
kötötten ágensek csupán. SZDT-12 – p. 3/24
˝ defin´ıcio´ (MI) Eros Az ágens egy olyan rendszer, amely a következo˝ további tulajdonságokkal rendelkezik: • Racionalitás: az ágens a rendelkezésre álló számítási
˝ kapacitás és egyéb eroforrások mellett a leheto˝ legjobb alternatívát választja. • Tanulás: az ágens képes új ismereteket gyujteni ˝
˝ és azt tárolni, felhasználni. A tanultak alapján környezetébol viselkedését megváltoztathatja. • Alkalmazkodás: képes tanulni a cselekedetei hatásából és
a tanultakat felhasználva változtatni tud tervein, annak érdekében, hogy tevékenysége optimálisabb legyen. • Személyiség: Számos alkalmazási területen szükség lehet
mesterséges személyiség létrehozására. A személyiséggel bíró ágens identitással, speciális jegyekkel rendelkezik, ˝ más ágensektol. ˝ melyek megkülönböztetik ot SZDT-12 – p. 4/24
´ ´ anos ´ A tanulo´ agensek altal modellje
Egy algoritmus tanul, ha egy feladat megoldása során olyan ˝ változások következnek be a muködésében, ˝ hogy késobb ugyanazt a feladatot vagy ahhoz hasonló más feladatotokat jobb eredménnyel, ill. hatékonysággal képes megoldani, mint korábban. SZDT-12 – p. 5/24
´ Indukt´ıv tanulas •
Azt mondjuk, hogy egy példa egy (x, f (x)) adatpár, ahol x a bemenete, f (x) a kimenete az x-re alkalmazott leképezésnek.
•
˝ az f -re vonatkozó minták (példák) Az induktív következtetés feladata a következo: egy halmaza alapján, adjon meg egy olyan h leképezést, amelyik közelíti f -et. A h leképezést hipotézisnek nevezzük.
•
Tekintsünk egy geometriai példát:
•
Az igazi f függvény nem ismert, így számos elképzelheto˝ választás van h-ra, ˝ további tudás nélkül nem tudhatjuk, hogy melyiket részesítsük elonyben.
SZDT-12 – p. 6/24
¨ esi ´ fak ´ tanulasa ´ Dont • A döntési fa bemenete egy tulajdonsághalmaz
segítségével leírt objektum vagy szituáció, kimenete pedig egy döntés. • A döntési fák így logikai függvény eket reprezentálnak. • A fa mindegyik belso˝ csomópontja megfelel valamelyik
tulajdonság tesztjének, és mindegyik él a teszt lehetséges értékeivel címkézett. • A fa mindegyik levélcsomópontja megad egy logikai értéket.
SZDT-12 – p. 7/24
¨ esi ´ fak ´ kialak´ıtasa ´ peld ´ ak ´ alapjan ´ Dont • A példát az attribútumok értékeivel és a célpredikátum
értékeivel jellemezzük. • A célpredikátum értékét a példa besorolásának hívjuk. • Ha a célpredikátum értéke egy példára igaz, akkor azt
pozitív példának, egyébként negatív példának tekintjük. • A teljes példahalmazt tanítóhalmaznak nevezzük.
SZDT-12 – p. 8/24
Feladat • Tegyük fel, hogy egy használtautó kereskedo˝ eladási
tapasztalatai alapján szeretné megfogalmazni a jól eladható autók kritériumait. • Lehetséges tulajdonságok és értékeik:
SZDT-12 – p. 9/24
´ keresese ´ Megoldas • Válasszuk a legegyszerubb ˝ alakot, az attribútum-példányok
konjunkcióját lehetséges hipotézisnek. Pl. h = (gyartas helye = nemet & kor = 3 − 6 kozott & motor = diesel & szin = f ekete & cm3 = 1300 − 1800 kozott) • Egyszerubb ˝ vektoros alak:
h = (nemet, 3 − 6 kozott, diesel, f ekete, 1300 − 1800 kozott) • A fogalmi tanulást tekinthetjük egy keresési feladatnak,
mivel az a cél, hogy a hipotézisek terében megkeressük azt a hipotézist, amelyik a legjobban illeszkedik a tanulási példákra. • A vektor komponensei között lehet: ◦ 0 : az attribútum egyetlen értékre sem elfogadható; ◦ ∗ : az attribútum bármely értéke elfogadott a
hipotézisben.
SZDT-12 – p. 10/24
´ keresese ´ Megoldas • Például:
4 ∗ 4 ∗ 2 ∗ 5 ∗ 4 = 640 különbözo˝ egyed lesz Mivel megengedett a 0 és a ∗ jel ezért: 6 ∗ 6 ∗ 4 ∗ 7 ∗ 6 = 6048 hipotézis lehet • Mindazon hipotézisek, amelyek legalább egy 0 szimbólumot
tartalmaznak, az üres példányt reprezentálja, így ezeket nem célszeru˝ megkülönböztetni. A valóban különbözo˝ hipotézisek száma: 1 + (5 ∗ 5 ∗ 3 ∗ 6 ∗ 5) = 2251 • Megállapítás: Mivel a hipotézistér általában nagyméretu, ˝
ezért fontos, hogy hatékony keresési módszerrel tudjuk kiválasztani a legjobban illeszkedo˝ hipotézist.
SZDT-12 – p. 11/24
´ Kiindulas • Az induktív tanulás során olyan h : X → {0, 1} hipotézist
keresünk, amelyre teljesül, hogy h(x) = f (x) minden x ∈ X példányra. • Tekintsük a következo˝ példákat:
SZDT-12 – p. 12/24
´ esei ´ ¨ esi ´ fa felep´ ´ ıtese) ´ Algoritmus lep (dont Kezdetben a fa egy címkézetlen (gyökér) csúcsból áll, amelyhez az összes tanító példát (P ) és attribútumot (A) hozzárendeljük. Adott egy címkézetlen n csúcs: ˝ 1. Ha P = 0, akkor levélcsúcsot kaptunk, amelynek értékét a szülocsúcs példáinak többségi szavazása alapján döntjük el. 2. Ha P csak pozitív (vagy csak negatív) példából áll, akkor egy igen (illetve nem) levélcsúcsnál vagyunk. 3. Ha A = 0, akkor is levélcsúcsot kaptunk, és a csúcs pozitív és negatív példáinak többségi szavazása alapján döntjük el annak értékét. ˝ 4. Egyébként a legnagyobb információs elonnyel járó, még teszteletlen a ∈ A attribútumot rendeljük az n csúcshoz, majd generáljuk az összes (címkézetlen) gyerekét:
• •
Ezekhez az a lehetséges értékeivel címkézett élek vezetnek.
•
Végül minden gyerekre ismételjük meg rekurzív módon az 1 − 4. lépéseket.
Ha az a címkéju˝ n csúcsból az m csúcsba a v címkéju˝ él vezet, akkor az m csúcshoz rendelt ◦ Példák: Pa=v = {p ∈ P |p.a = v} ◦ Attribútumok: A = A − {a}
SZDT-12 – p. 13/24
ID3 algoritmus • A döntési fa konstruálásának legfontosabb kérdése, hogy a
fa adott pontjában melyik attribútum értéke szerint végezzük el a tesztet. • Azt az attribútumot célszeru˝ választani, amelyik a
leghasznosabb a példák osztályozására. • Ezen hasznosság mérésére bevezetheto˝ egy méroszám, ˝ az
˝ ún. információs elony, ami megmutatja, hogy egy adott attribútum szerinti teszt egyedül milyen jól osztályozná az adott tanulási példákat.
SZDT-12 – p. 14/24
´ Entropia defin´ıcio´ • Legyen P pozitív és negatív példák gyujteménye ˝ egy adott
fogalomra vonatkozóan. • A P entrópiája:
E(P ) = E(P + , P − ) = −P + ∗ log2 P + − P − ∗ log2 P − ahol P + a pozitív, P − a negatív példák arányát jelöli P -ben. • Az ID3 algoritmusban használt információs elony ˝
˝ méroszám azt mutatja meg, hogy egy adott attribútum szerinti osztályozás mennyivel csökkenti a P entrópiáját. P a=v | C(P, a) = E(P ) − v∈ertek(a) |P|P | ∗ E(Pa=v )
SZDT-12 – p. 15/24
´ becsles ´ Teljes´ıtmeny ˝ Lehetoségünk van a tanulási algoritmus teljesítményét megbecsülni. ˝ ha jó hipotéziseket szolgáltat azokban az A tanulási algoritmus akkor megfelelo, ˝ esetekben is, amelyeket nem látott elore. A vizsgálatot a példák egy teszthalmazán végezhetjük el, amelyhez a következo˝ lépéseket kell végig követnünk. 1. Gyujtsük ˝ össze a példák egy nagy halmazát. 2. A példahalmazt bontsuk szét két diszjunkt halmazra: egy tanítóhalmazra és egy teszthalmazra. 3. A tanuló algoritmust a tanítóhalmaz példáira alkalmazva állítsuk elo˝ a H hipotézist. 4. Vizsgáljuk meg, hogy H a teszthalmaz példáinak hány százalékát sorolja be helyesen. 5. Ismételjük meg az 1-4 lépéseket különbözo˝ tanítóhalmaz méretekre, és mindegyik mérethez különbözo˝ teszthalmazra. Eredményként kapunk egy adathalmazt, amellyel az átlagos jóslási képesség a tanítóhalmaz méretének a függvényében vizsgálható. ˝ hogy a tanítóhalmaz méretének a Egy ilyen jellegu˝ vizsgálat kapcsán megfigyelheto, ˝ növekedésével a jóslás minosége javulni fog. SZDT-12 – p. 16/24
´ ¨ Agens-k ornyezet ˝ Egyszeruen ˝ fogalmazva: A megerosítéses tanulást és feladatát úgy fogalmazhatjuk meg, mint egy olyan módszert, amely kapcsolatok alapján, bizonyos célokra összpontosítva tanul. ˝ Ágens-környezet modell: Minden t idopillanatban az ágens megkapja a környezetet st ∈ S állapotleírását, ahol S a lehetséges állapotok (state) halmaza. Ennek alapján választ egy at ∈ A(st ) akciót, ahol A(st ) az st állapotban megengedett akciók halmaza. A következo˝ lépésben a választott akció függvényeként kap egy rt+1 ∈ R ⊆ R jutalmat, és egy új st+1 állapotba kerül.
SZDT-12 – p. 17/24
´ ¨ Agens-k ornyezet ˝ Minden egyes idopillanatban az ágens egy leképezést valósít meg az állapotleírások és az egyes akciók választási valószínuségei ˝ között. A leképezést az ágens politikájának (policy) nevezzük, és Πt -vel jelöljük, ahol Πt (s, a) st = s esetén at = a választásának valószínuségét ˝ adja meg. ˝ A megerosítéses tanulás különbözo˝ módszerei azt írják le, hogy az ágens hogyan változtatja a politikáját az ido˝ ˝ elorehaladtával a tapasztalatai függvényében. A cél az, hogy az ágens hosszú távon maximalizálja az
SZDT-12 – p. 18/24
´ Varhat o´ hozam Az ágens feladata a várható hozam (return), Rt maximalizálása, ahol Rt a közvetlen jutalmak sorozatának valamilyen függvénye. Legegyszerubb ˝ esetben: ˝ Rt = rt+1 + rt+2 + . . . + rT , ahol T az utolsó idopillanat Az ágens-környezet interakció részsorozatokra, epizódokra bomlik: pl. kártyajáték, labirintus feladat; itt minden epizód egy terminális állapotban ér végett) Folytatható folyamatok: pl. folyamatszabályozás, robotvezérlés T =∞ ˝ Itt a végtelen sor összegét maximalizálni akarjuk. Elofordulhat, hogy a sor divergens, ilyenkor a maximalizálás értelmét veszti.
SZDT-12 – p. 19/24
´ hozam Diszkontalt Diszkontált hozam: P∞ i 2 Rt = rt+1 + γrt+2 + γ rt+3 + . . . = i=0 γ rt+i+1 0 ≤ γ ≤ 1 a diszkontálási paraméter; Ha γ < 1 a sor konvergens, feltéve, hogy a jutalmak ri sorozata korlátos. Ha γ = 0, akkor az ágens "rövidlátó", azaz csak a közvetlenül következo˝ jutalom maximalizálására törekszik. ˝ Ha γ ≈ 1(γ < 1), a késobbi jutalmak egyre nagyobb súllyal ˝ jelennek meg, az ágens egyre "elorelátóbb" lesz. Egységes hozamfüggvény: PT Rt = i=0 γ i rt+i+1 Ha T véges és γ = 0, akkor az epizódikus, ha T = ∞ és 0 ≤ γ ≤ 1, akkor a folytatható folyamatra megadott definíciót kapjuk.
SZDT-12 – p. 20/24
´ ekel ´ o˝ fuggv ´ Ert eny ¨ Az értékelo˝ függvény leírja, hogy mennyire jó egy adott állapot vagy mennyire jó egy adott állapotban egy adott akciót végrehajtani. Egy s állapot π politika melletti jósága (V π (s)) az állapotból a politika követése mellett gyujthet ˝ o˝ hozam várható értéke. Állapot értékelo˝ függvény: P∞ k π V (s) = Eπ (Rt |st = s) = Eπ ( k=0 γ rt+k+1 |st = s) ˝ ˝ (Eπ jelöli a π politika követése melletti várható értéket, t tetszoleges idopillanat)
Az s állapotban a akció választásának értéke a π politika mellett: Qπ (s, a) = Eπ (Rt |st = s, at = a) = P∞ k = Eπ ( k=0 γ rt+k+1 |st = s, at = a)
SZDT-12 – p. 21/24
Bellman-egyenlet A V π -re vonatkozó Bellman-egyenlet leírja a jelenlegi állapot és a lehetséges rákövetkezo˝ állapotok értéke közötti összefüggést. Optimális politika (π ∗ ) Ugyanaz az optimális állapotot értékelo˝ függvény tartozik hozzá: V ∗ (s) = maxπ (V π (s)), ∀s ∈ S Közös az optimális akciót értékelo˝ függvényük is: Q∗ (s, a) = maxπ (Qπ (s, a)), ∀(s, a) ∈ S × A(s) A V ∗ -ra vonatkozó P Bellman-féle optimalitási egyenlet: a [Ra + γV ∗ (s′ )] V ∗ (s) = maxa∈A(s) s′ Pss ′ ss′ A Q∗ -ra vonatkozó Bellman-féle optimalitási egyenlet: P a [Ra + γmax ′ Q∗ (s′ , a′ )] Q∗ (s, a) = s′ Pss ′ a ss′
SZDT-12 – p. 22/24
˝ ´ modszere ´ Idobeli differenciak (Temporal Difference, TD)
A π politika követése során szerzett tapasztalatait felhasználja a π politikához tartozó V π értékelo˝ függvény V becslésének felülírására. ˝ Ha a t idopillanatban a rendszer az st állapotban van, akkor a módszer rögtön a következo˝ lépésben módosítja a V -t a megfigyelt rt+1 jutalom és V (st+1 ) korábbi becslésének felhasználásával. A legegyszerubb ˝ TD módszer: V (st ) ← V (st ) + α[rt+1 + γV (st+1 ) − V (st )] ˝ + Ez a módszer egy becslés: mintát vesz a várható értékbol felhasználja a V π értékelo˝ függvény V t becslését.
SZDT-12 – p. 23/24
´ ere ´ TD(0) algoritmus V π becsles Input: π policy to be evaluated Initialize: V (s) arbitrarily Repeat for each episode initialise s Repeat for each step of episode ′ take a, r, s V (st ) ← V (st ) + α[rt+1 + γV (st+1 ) − V (st )] ′ s←s until s is terminal
SZDT-12 – p. 24/24
