Dr. Jelasity Márk
Mesterséges Intelligencia I. (I602, IB602) kurzus kilencedik előadásának jegyzete (2008. november 3.)
Tanulás (Learning)
Szeged, 2008. december 9.
Készítette:
Szabó Péter
EHA:
SZPNAAT.SZE
Tanulás (learning): Tapasztalati adatok (tények) felhasználása az ágens teljesítményének növelésére. „Tulajdonképpen az ágens különböző komponenseit optimalizálni akarjuk (pl. játék – kiértékelő függvény)”. Ez is keresési feladat. Racionális ágens (rational agent): Egy racionális ágens úgy cselekszik, hogy maximalizálja a teljesítménymérték várható értékét az addigi észlelési sorozat alapján. Durva felbontásban a tanulást két csoportra oszthatjuk: 1) Felügyelt tanulás (supervised learning): „A tanítási példák és ezek eredményei is megvannak.” Egy f : A → B függvényt kell találni példák alapján, amelyek a 1 , b1 , ... , a n , b n alakban adottak. Például: a) A: e-mail-ek halmaza B: {spam, ¬spam}
(összes lehetséges e-mail), (függvény, amit meg akarunk tanulni).
A tanító példák kézzel osztályozott e-mail-ek (spam szűrő tanítása) b) A: részvényindex idősorai, B: {emelkedik, esik}. Tőzsdéző program, stb... 2) Felügyelet nélküli tanulás (unsupervised learning): „Csak a példák vannak meg, vagyis csak az A halmaz adott.” A példák csak a 1 , ... , a n alakúak és nem függvényt kell illeszteni, hanem mintázatot keresni, pl. klasztereket. Számos finomabb felosztás lehet, pl. van "B" (függvényt kell illeszteni) de a tanuló példák csak késleltetve értékelődnek ki (megerősítéses tanulás – reinforcement learning) vagy pl. a példák előre adottak vagy csak fokozatosan gyűlnek. x x
x x
x x
O * * O * * O O O
x
x x
Felügyelt
x
x
x x
x x
x x
Felügyelet nélküli 2
Reprezentáció: A függvényt adott alakban keressük, polinom, ítéletkalkulus (Boole – függvények), stb. Kereshetnénk Turing gépet, de: 1.) Nem lehet hatékonyan, 2.) Túl általános! Ideálisan a reprezentáció se nem túl egyszerű, se nem túl bonyolult. A priori ismeretek fontossága: A "tabula rasa" tanulás lehetetlen! (Ha a tanulás megkezdése előtt semmit nem tudunk, csak a példákat, akkor nem tudunk tanulni.) Pl.: a reprezentáció is a priori ismeret, stb. (később látjuk) 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 x 1 , f x 1 , ... , x n , f x n 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.
K=1 a) ábra
K=7 b) ábra
K=6 c) ábra
sin d) ábra
3
Az a) esetben (K = 1, az elsőfokú polinomok tere) egyenest akarunk illeszteni, a b) esetben pedig (K = 7, hetedfokú polinomok tere) nyolc pontot is tökéletesen tudunk illeszteni, vagyis „be tudjuk magolni a nyolc pontot”, de láthatóan nem feltétlenül jobb a nagyobb hipotézistér. Sőt! „Kis hipotézistérhez előzetes tudás kell, ezért nehezebb konstruálni.” A d) ábrát tekintve, „ha van benne szinusz, jó lesz az eredmény, viszont ha nincs, akkor nagyon rossz”. Észrevételek: a) és b) : Az általánosabb H nem mindig jobb. c) és d) : Nem mindegy, hogy mi a H. Indukció problémája: Az f jó közelítése olyan h, amely ismeretlen x-re is jól becsüli példákra) , azaz jól általánosít. (Ez nehéz! Filozófiai kérdés)
f x – et (nem csak az adott
f x , ha x ismert példa
Pl.: Ha h x = 0
, egyébként
akkor h egyáltalán nem általánosít, de a tanító példákat tökéletesen tudja: magolás! 1) Törekszünk tömörebb reprezentációra, mint az adatok (Ockham borotvája: a lehető legtömörebb leírás, ami még elég.) Ockham borotvája (Ockham's razor): Ez az elv tehát egy lehetséges válasz arra a kérdésre, hogy hogyan válasszunk több konzisztens – valamennyi adatra illeszkedő – hipotézis közül? Részesítsük előnyben a legegyszerűbb olyan hipotézist, amely konzisztens az adatokkal. Ez józan intuíciónak tűnik, mivel azok a hipotézisek, melyek nem egyszerűbbek, mint maguk az adatok, nem nyernek ki semmilyen mintázatot az adatokból. Ha van struktúra, elég jól tömöríthető, viszont van, amikor nem lehet tömöríteni: véletlen adatok, Kolmogorov-komplexitás (Kolmogorov-complexity). Kolmogorov-komplexitás (algoritmikus komplexitás): Formális definíciót próbál adni az Ockham borotvája elvben használt egyszerűségnek. Hogy valahogy kimeneküljenek abból a csapdából, hogy az egyszerűség függ az információ reprezentációjának módjától, azt javasolták, hogy az egyszerűséget annak a legrövidebb programnak a hosszával mérjék, amely egy általános Turing – gépen helyesen adja vissza a megfigyelt adatokat. De ez is csak "ökölszabály", bizonyítani nem lehet és nem is mindig működik. 2) Törekszünk egyszerű reprezentációra a hatékonyság miatt is, mivel egyszerűbb reprezentációban könnyebb keresni. Az induktív tanulás alapfogalmait a következő területen szemléltetjük: 4
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}) f x :
Ha a függvény értékkészlete, – –
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.
Példa: Egy döntési fa annak eldöntésére, hogy várjunk-e asztalra az étteremben? B = {Igen, Nem} A= – Alternatíva: van-e a közelben megfelelő alternatívaként kínálkozó étterem. – Bár: van-e az étteremnek kényelmes bár része, ahol várakozhatunk. – Péntek/Szombat: igaz értéket vesz fel pénteken és szombaton. – Éhes: éhesek vagyunk-e. – Vendégek: hány ember van az étteremben (Senki / Néhány / Tele). – Drága: az étterem mennyire drága. – Konyha: az étterem típusa (francia, olasz, thai vagy burger). – Becsült várakozás: pincér becsülte várakozási idő (0-10, 10-30, 30-60, >60 perc). – Eső: esik-e odakint az eső. – Foglalás: foglaltunk-e asztalt. Vendégek? Senki Nem
BecsültVárakozás?
Igen >60
30-60
Nem
Igen Igen
Bár? Nem
Éhes?
Igen
Nem Nem
Igen Igen
Igen
Igen Igen
Nem
Péntek/Szombat?
Foglalás? Nem
0-10
10-30
Alternatíva?
Nem
Nem
Tele
Néhány
Igen
Alternatíva? Igen
Nem
Eső?
Igen Nem
Igen 5
Nem
Igen Igen
A döntési fa élei a változók lehetséges értékei. Vegyük észre, hogy a fa nem használja a Konyha és a Drága attribútumokat, valójában irrelevánsnak tekinti azokat. 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. –
Visszafelé is igaz:
Az ítéletlogikai nyelvek területén a döntési fák teljes kifejezőképességgel bírnak, ami azt jelenti, hogy tetszőleges logikai (Boole) függvény felírható döntési faként. Pl.: a függvény igazságtáblájában minden „igaz” sorhoz egy utat adunk. (Ennél tömörebben is lehet.) –
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. Pozitív példa: a példa pozitív, ha a VárjunkE értéke igaz. Negatív példa: a példa negatív, ha a VárjunkE értéke hamis. Pl.: Vendégek =Tele, Várakozás = 10-30, [összes attribútum]; VárjunkE = igen. Vendégek = Senki, Várakozás = 0-10, [összes attribútum]; VárjunkE = nem.
6
Pl.: 100 példa adott: x1, … , x100. Bemagolhatnánk (minden pozitív példához egy út), de láttuk, hogy ez nem jó => tömöríteni kell. Heurisztika: A lehető legjobban szétválogatjuk a pozitív és negatív példákat. Ötlet: Gyökérbe az az 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.
Tanítási adathalmaz
i h i h i h i A
i h h h
i h i h i h i
h
i
i i i i
i h i h
B
h i h i
Ideális eset 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: „default” érték, heurisztikát alkalmaz, pl. többség a szülőben. 4.) Ha pozitív és negatív példa is van, de nincs több attribútum: 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: Ötlet: 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 log 2 -t használunk, mértékegysége a bit. Véletlen változó átlagos információtartalma (entrópia):
∑ − p i log 2 p i i
( p 1 , ... , pn , valamint az eloszlás: 1=∑ pi ) 7
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. I A=
−p p n n log 2 − log 2 pn pn pn pn
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
E 1 , ... , E v a megfelelő példa részhalmazok, ahol ∣E i∣=n i pi . v
Nyereség (A) =
I A−∑ i=1
pi n i I Bi pn
Maradék (Reminder) => A maximális nyereségű attribútumot választjuk. Induktív tanuló algoritmusok kiértékelése: Hogyan „buktatjuk le” a magolókat? A példákat két részre osztjuk: 1.) Tanító halmaz (training set) 2.) Teszt halmaz (test set) – nem használjuk fel a tanítás során. A tanító halmazon építjük a modellt (pl. döntési fát), a teszt halmazon értékeljük ki. De: precision, recall, stb: % nem mindig kielégítő mérték, pl. ha sokkal kevesebb a pozitív példa. „Kukucskálás” (peeking): Ha a teszteredmények alapján finomhangoljuk az algoritmus paramétereit. => A modell függ a teszttől. (A teszthalmazra is optimalizálva lett a modell. Ez nem jó!) Túlillesztés (overfitting): Megjegyzés: 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.”
8
Pl.: Ha az egyik paraméter a dobókocka színe, pl. ilyen téves minta alakulhat ki: „csak piros dobókockával jöhet ki hatos”. „Kevés adatnál tehát nem kell nagyon komolyan venni a mintákat.” 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 (pl. teljesen véletlen kockadobásoknál KockaSzíne, DobásIdeje, stb.) ne építse be az algoritmusba. Pl. statisztika alkalmazásával. => Valamit tanulni fog, de az biztos tévedés lesz! Vajon detektáljunk irreleváns attribútumokat? Pl.: Statisztika Egy ∞ mintában az információ-nyereség zérus. Kis mintában ritkán zérus, de megnézhetjük, hogy szignifikánsan nem nulla-e? Például: χ 2 – próba: Legyen a KockaSzíne szerinti felbontáshoz tartozó minták száma
∑ pi= p Ekkor a nullhipotézis az, hogy
és
∑ ni=n
.
p i várható értéke p i : p i= p
pi ni p n és n i=n i i . pn pn 9
p1 , n1 ,
p 2 , n2 , stb.
azaz 0 a nyereség, mert ugyanolyan arányú a pi , mint a p. D=∑ D
χ
2
p i− p i 2 n i−n i 2 , p i n i
eloszlást követ, táblázatból ellenőrizhető D valószínűsége.
Ez az algoritmus a
χ
2
– metszés.
Gyakorlati kérdések (vázlatosan): – – – –
Hiányzó adatok, pl. attribútum értékek: pl. felvenni példákat minden lehetséges értékkel (de súlyozva, n példa esetén 1/n súllyal.) Sokértékű attribútumok: nagy a nyereség egyszerűen azért, mert sok az attribútum: nem jó! Vegyük figyelembe magának az attribútumnak az információtartalmát is: normalizáljunk vele. Folytonos változók : a gain számolásakor megkeressük azt a felosztó pontot, ami maximális nyereséget eredményez. (költséges) Folytonos kimenet: minden levélen egy függvény, nem pedig pl. „igen/nem” érték.
Fontos: A döntési fa gyakran nem a legjobb algoritmus, de értelmezhető (olvasható, visszafejthető) és ez gyakran követelmény. 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. Miért lehet jó? 1.) Modellek hibái nem pont ugyanazok (ideálisan: függetlenek) => statisztikailag (nagy számok törvénye) megbízhatóbb. 2.) Kombinálhatunk is 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 L-lel.
10
Súlyozott példák: Az x i , y i példához w i súlyt rendelünk, L-nek kezelni kell tudni ezt. Pl.: a döntési fák könnyen kezelik.( p i és n i számításánál súllyal vesszük a példákat) Ada Boost algoritmus: AdaBoost (példák, L, M) // példák: N darab példa, x i , y i , i=1, ... , n // L : tanuló algoritmus (gyenge) // M: hipotézisek száma az együttesben // w i : x i , y i súlya, 1/ N kezdetben // h i : i-edik hipotézis ( i=1, ... , M ) // z i : 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 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) – – – –
A nehéz (nem egyértelmű) példák és a jó osztályozók nagyobb súlyt kapnak. Pl.: L lehet döntési tönk (egyváltozós döntési fa, e változó alapján döntünk). Érdekes: túlillesztés nem jelentkezik, ha M nagyon nagy, sőt, ellenkezőleg => nem világos miért és mikor. Sok elméleti eredmény tartozik ide, ezeket nem tárgyaljuk, csak az intuitív megértésre támaszkodunk.
11
