Mesterséges Intelligencia I

Mesterséges intelligencia I. elıadás

Mesterséges Intelligencia I. 10. elıadás (2008. november 10.)

Készítette: Romhányi Anita (ROANAAT.SZE)

-1-

Mesterséges intelligencia I. elıadás

Statisztikai tanulás (Megfigyelések alapján történı bizonytalan következetésnek tekintjük a tanulást.)

- Alapfogalmak: o adatok (tények (evidence):
a területet leíró valószínőségi változók egy részének vagy mindegyikének egy konkrét megvalósulása o hipotézisek:
valamilyen valószínőségi elmélet arról, hogy a világ adott területe hogyan is mőködik - Szemléltetı példa: (meggy és citrom) o meggy- és citromízesítéső cukor: 1) ugyanolyan csomagolás 2) 5 féle zacskó (hipotézisek): • h1: 100 % meggy • h2: 75 % meggy + 25 % citrom • h3: 50 % meggy + 50 % citrom • h4: 25 % meggy + 75 % citrom • h5: 100 % citrom o ágens feladata:
D1… DN példából következtetni a következı cukorka ízére -2-

Mesterséges intelligencia I. elıadás (Di értéke meggy vagy citrom, és feltesszük, hogy Di független minták) - Bayes tanulás: o kiszámítjuk minden egyes hipotézis valószínőségét az adatokra támaszkodva. o reprezentálja D az összes adatot; d pedig legyen a megfigyelt értékek vektora, ekkor az egyes hipotézisek valószínősége:
P (hi|d) = α P(d|hi)P(hi) o Ha egy X változó értékét akarjuk számolni:
P (X|d) = ∑i P (X|d, hi)P (hi|d) = ∑i P (X |hi)P (hi|d), ahol feltettünk, hogy P (X | hi) ismert és X független d-tıl. o Elnevezések:
prior: P (hi) = hipotézisek priori valószínősége
likelihood: 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, általában 2 prior … ismertek vagy rögzítettek o Példa:
h1, … , h5 – höz legyen (0.1, 0.2, 0.4, 0.2, 0.1) az eloszlás, ha az adatok (D1, …, DN) függetlenek és azonos eloszlásúak, akkor az adatok valószínőségének kiszámítása: • P(d|hi) = ∏j P(dj|hi);
például:

-3-

Mesterséges intelligencia I. elıadás • ha h5 áll fenn (csak citrom) → elsı 10 minta csak citrom → P (d|h3) = (1\2)10, mivel a h3 típusú zsákokban a cukorkák fele citrom o megjegyzés: 1. minél több minta van, annál biztosabb a döntés: az „igazi” hipotézis posterior összege → 1, a többié → 0

A hipotézis a posteriori valószínősége

Annak a valószínősége, hogy a következı cukorka citromíző

2. 0 db mintánál a döntés a prior alapján

A minták száma d-ben

A minták száma d-ben

o A Bayes perdikció optimális; a rendelkezésre álló tudás alapján nem lehet valószínőségi értelemben jobban dönteni → épp ezért gyakran túl drága → egyszerősíteni kell.

MAP és ML - Maximum posteriori (MAP) tanulás o prior-okkal súlyozott összeg helyett a maximális P (hi |d) – hez tartozó hi - t egyedül használjuk → „veszélyesebb” de gyakran olcsóbb. Sok adatnál -4-

Mesterséges intelligencia I. elıadás ugyanoda konvergál, mint a Bayes - prior valószínőségek: Bayes és MAP prior-okat használ. o 1. láttuk: … itt: komplex h – hoz kisebb priort rendelünk o 2. maximális P(hi | d) = maximális P (d | hi)P(hi) → minimális - log P (d | hi) - log P(hi) → ez épp a tömörítést fejezi ki: a bitek számát minimalizáljuk a hi+d reprezentációja ez a minimális adat hossza [a minimális leírás elvét is használhatjuk tanulásra]

- Maximum likelihood tanulás: o további egyszerősítés: feltesszük, hogy minden prior valószínősége egyenlı (pl. ugyanolyan komplex hipotézisek). ekkor P(hi | d) ~ P (d | hi) . vegyük a maximális P (d | hi) – hez tartozó hi – t. o Megjegyzés: nagyon sok adatnál ugyanoda konvergál, mint a Bayes és a MAP, de kevés adattal problémás (majd látjuk)

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 o 1. példa: meggy\ citrom, de most Θ a megy aránya, Θ ismeretlen.
hΘ hipotézis: a meggy arány Θ -5-

Mesterséges intelligencia I. elıadás
nevezzünk meg N db cukorkát: • legyen m db meggy, c db citrom, [c=N-m] • ekkor az adathalmaz valószínősége, ha a minták függetlenek: (d|hΘ) = Θm(1-Θ)c


P (d|hΘ) =


Melyik Θ - ra maximális?
Ehhez: L (d|hΘ) = log P (d|hΘ) =

(dj|hΘ)

=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 prior – okat]

P (meggy) = Θ

Íz

Íz

Csomagolás Meggy Citrom

-6-

P (Cs=piros|Íz) Θ1 Θ2

Mesterséges intelligencia I. elıadás

o 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: •

megint természetes eredmény

belátható, hogy diszkrét Bayes-hálóhoz mindig

hasonló eredmény: minden táblázatot egymástól függetlenül becsülünk. - Naiv Bayes tanulás: [naiv Bayes modell: lásd korábban] o itt O(N) táblázat van: adatokból becsülhetıek a paraméterek maximális likelihood szerint (ahogy fent). o O(N) db osztás kell csak, és a P(c | x1, … , xn) = αP(c) o megjegyzés: olcsó, és ehhez képest elég jó - maximum likelihood: folytonos változók -7-

becsülhetı

Mesterséges intelligencia I. elıadás o 1. legyen x1, … , xN N db független minta a µ, Θ paraméterő normális eloszlásúak, ekkor:
P(x)=

, ahol µ, és σ ismeretlen, ekkor a log likelihood: • L (d | hµ,σ) =

, innen a

deriváltakat (µ és σ szerint) 0-nak véve:


ez nem meglepı

o 2. legyen most két változó: X és Y, és P (y | x) =
tudjuk, hogy y normális eloszlású és várható értéke x – tıl lineárisan függ, de Θ1 és Θ2 ismeretlenek.
Az adatok itt (x1, µ 1)… (xn, µ n) formában adottak. Θ1 és Θ2 végül a minimalizálásából adódik, ami éppen a legkisebb négyzetek módszerét használó lineáris regresszió. (ami tehát optimális, ha feltesszük, hogy a hiba normális eloszlású, fix normával)! - Bayes tanulás o 1. cukorkás példa (Θ paraméter, N minta), de most prior is van: P(Θ) = P(O = Θ) [O: hipotézis véletlen változó] o pl. O – nak lehet egyenletes eloszlása ( [0,1] - en) [ likelihood]. gyakorlatban gyakran veszünk béta eloszlást:
béta [a, b] (Θ) = α Θa-1(1 - Θ)b-1 sőrőségfüggvény. -8-

ekkor maximum

Mesterséges intelligencia I. elıadás o paraméterek: a,b α: … konstans
a = 1, b = 1 : egyenletes
a = b: szimmetrikus
a + b nagy: „csúcsos”
E(O) = a/ a +b o 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](Θ) o ez a konjugált prior tulajdonság, azaz a prior eloszlása ugyanaz, mint a posterioré, csak más paraméterekkel. o megjegyzés:
1. a priori tudás itt: virtuális számláló: • P(Θ) = beta[a,b](Θ) jelentése, hogy már ismerek a pozitív és b negatív példát. (az adatok vizsgálata elıtt, azaz a priori)
2. az adatok elıbb utóbb dominálják a posteriori valószínőséget (itt jól látszik) és akkor Bayes ~ Max likelihood o 2. cukorka + csomagolás példa (Θ, Θ1, Θ2 paraméterek)
itt a prior: P(Θ, Θ1, Θ2). Itt gyakran feltesszük, hogy P(Θ, Θ1, Θ2) = P(Θ)P(Θ1)P(Θ2), és pl. lehet mindegyik beta eloszlás.

-9-

Mesterséges intelligencia I. elıadás - Megjegyzés: a Bayes tanulás során ugyanazt a valószínőségi következtetést használjuk (adatok és hipotézisek felett) amit láttunk korábban: itt tehát a modell tanulása ugyanúgy megy, mint a használata. - Bayes háló … tanulása - Egy jó Bayes háló drasztikusan csökkentheti a paraméterek számát (táblázatokat): hogyan építünk?:
1. láttuk: kézzel, szakértıkkel
2. automatikusan keresési probléma:
a. keverési tér: Bayes hálók
b. operátorok: pl. hozzáad/elvesz linket, stb.
c. célfüggvény: pl. ellenırzi, hogy a függetlenségi feltételek teljesülnek (statisztikai … vagy pl. perdikciós képesség) vizsgálata miközben büntetjük a komplex modelleket (prior, stb.)

Rejtett változók: - eddig az adatokban minden változó ismert volt. Nem mindig van így - pl. betegség. Amit látunk:
1. Tünetek
2. Orvosi diagnosztika
3. reagálás kezelésre, de maga a betegség nem figyelhetı meg - viszont miért vesszünk bele a modellbe? Mert egyszerősít - 10 -

Mesterséges intelligencia I. elıadás - pl. 2. hiányos adatok is lehetnek - [megjegyzés: hipotézisek is „bevehetık” rejtett változónak…] Dohányzás

Étkezés

Mozgás

Étkezés

Dohányzás

Mozgás

Szívbetegség

Tünet 1

Tünet 2

Tünet 3

Tünet 2

Tünet 1

Tünet 3

- EM algoritmus: o példán keresztül: N példa: x1, … , xN. o Tudjuk: két normális eloszlás keverékébıl …:
P(x) =

, ahol σ rögzített és ismert, de µ 1 és µ 2

ismeretlenek o rejtett változók: Zij: i. példa a j. eloszlásból van (µ j középpel). o teljes adat (x1,Z11,Z12), … , (xN,ZN1,ZN2) lenne. De Z-k nem adottak. o feladat: maximum likelihood: := o [probléma: xi –k eloszlását nem ismerjük (éppen ezt kell megadni)] o ötlet: iteráció („???” helyett)
0: legyen h(0) egy tetszıleges (pl. véletlenül generált) hipotézis
1: h(k) az aktuális hipotézis. h(k) mellett számoljuk ki E(zij)-t: • E(zij) =

(j=1,2, i=1,…,N)


2: tekintsük E(Zij)-t a zij értékével és számoljuk ki a maximum likelihood hipotézist: erre az adódik, hogy •
3. opt 1 o belátható, hogy ez az iteráció a likelihood egy lokális maximumához konvergál (illetve a globális maximumba, hogy csak egy max van) - EM algoritmus általános alakja: - 11 -

Mesterséges intelligencia I. elıadás o valójában nagyon általános módszer:
jelölje X a megfigyelt adatokat, Z a rejtett adatokat.
[Z véletlen változó, X konkrét adat]
ekkor P(x,Z|h) eloszlás várható értékét vesszük és olyan h-t keresünk, ami azt maximalizálja.
tehát E( P (X,z|H))-t vesszük
gyakran könnyebb számolni log-gal: vegyük inkább • E (log P (x,Z,|h))-t (azaz E (L (x,Z,|h))-t)
ehhez kéne tudnunk Z eloszlását. Nem tudjuk: használjuk h(k)-t! A várható értéket számoljuk h(k) és x felvételével: • E(L (x,Z|h)|h(k), x) = ∑Z P(Z | x,h(k))L(x,Z|h)=Q(h|h(k)) o Általános EM:
0:válasszunk bármilyen h(0) hipotézist
1: h(k+1) = argmaxh Q(h| h(k))
2: opt 1 - Példány alapú tanulás: o adott (x1, y1) , … , (xn, yn) példa o ötlet: ismeretlen x kiértékelése „hasonló” ismert példák alapján - legközelebbi szomszéd modellel: o 1. keressük meg x k legközelebbi szomszédját (k5 és 10 között pl.) o 2. h(x) a szomszédok y-jának átlaga (esetleg távolság szerint súlyozott) ha folytonos probléma, v a szomszédok y-jainak többségi szorzata (diszkrét) o ha csak x1, …, xn adott (és y-ok nem), akkor a P(x) sőrőség közelítésére is jó = nézzük meg, hogy a k legközelebbi szomszéd mekkora területen oszlik el? (sőrőség: pontok/terület) o fontos: távolságfüggvény D(x1,x2)
1. folytonos változóknál normalizálni kell a dimenziókat (pl. súly, magasság);
vehetjük pl. minden jellemzı varianciáját, és a jellemzı értékét a másik többszöröseiként fejezzük ki.
2. diszkrét esetben Hamming távolság: különbözı jellemzık száma. pl. H(001, 111) =2

- 12 -