1. gyakorlat Mesterséges Intelligencia 2.
Elérhetőségek web: www.inf.u-szeged.hu/~gulyasg mail:
[email protected]
Követelmények (nem teljes) •
gyakorlat látogatása kötelező
•
ZH írása a gyakorlaton elhangzott algoritmusokból
•
kötelező program írása (valamely metaheurisztika alkalmazása egy adatbázison)
Gépi tanulás alapfogalmai (a leírás Tóth László - Gépi Tanulási Módszerek jegyzete alapján készült) A gépi tanulás célja A gépi tanulás célja olyan programok készítése, amelyek a működés során szerzett tapasztalatok alapján képesek javítani saját hatékonyságukon. Tanuló-algoritmusok Olyan algoritmusok, melyek képes összefüggések, szabályosságok megtanulására (hipotetizálására) egy példa-halmaz alapján. Induktív tanulás A tanítás során nem látott esetekre is szeretnénk általánosítani a megtanult összefüggéseket. Feltevés: A példák hűen reprezentálják a tanulandó összefüggést. Felügyelet nélküli tanulás Felügyelet nélküli tanulásnak nevezzük, ha a példákhoz nincs „külső segítség”. •
leggyakoribb feladat: klaszterezés: adatok automatikusan kialakított osztályokba sorolása valamilyen hasonlóság alapján.
Felügyelt tanulás Felügyelt tanulásnak nevezzük, ha a tanítópéldákhoz a „helyes válaszok” is adottak •
leggyakoribb: f(x1,...,xN) függvény tanulása {(y1,...,yN);f(y1,...,yN)}(i) , (i=1,...,M) alakú példák alapján általában élesen szétválik a tanulási és tesztelési (felhasználási) fázis
•
pl.: emberek orvosi tesztjei, valamint diagnosztizált betegésük; a cél olyan modell alkotása (tanulás), amely alapján az adott betegséget hatékonyabban lehet felismerni
•
pl.: molekulák adatbázisa (gráfokkal leírva), és bizonyos számú molekula esetén ki van mérve, hogy hogyan reagál az AIDS vírusra; kérdés, hogy a többi, ismeretlen molekuláról mit lehet ezek alapján mondani
Tanuló adatbázis Felügyelt tanulás esetén
Példa Magasság Hajszín Szemszín Osztály 1 alacsony
szőke
kék
+
2
magas
szőke
barna
-
3
magas
vörös
kék
+
4 alacsony
sötét
kék
-
5
magas
sötét
kék
-
6
magas
sötét
barna
-
szőke
barna
-
7 alacsony
Attribútum-halmaz: A={Magasság, Hajszín, Szemszín} Osztálycímkék halmaza: C={+,-} Példa: egy sor az adatbázisban (a valóság egy entitását írja le)
Döntési fák: ID3-algoritmus Az előző példához tartozó döntési fa:
hajszín sötét
szőke vörös
-
+
szem
barna
kék
+
-
Osztályozás a fa alapján: egy új, eddig ismeretlen entitást ({M, H, SZ}) a fa gyökeréből kiindulva, a csúcsokban található attribútumoknak megfelelően haladunk valamely levél felé; a példához tartozó címkét a levél címkéje adja meg
Modellalkotás: tanulási folyamat Algoritmus ID3(S, C, A) S: példahalmaz, C: osztály-címkék, A: attribútum halmaz
• • • • •
készítsünk gyökércsomópontot a fának ha S-ben minden példa pozitív, akkor a gyökér címkéje legyen +, és return gyökér ha S-ben minden példa negatív, akkor a gyökér címkéje legyen -, és return gyökér ha az A attribútum-halmaz üres, akkor a gyökér címkéje legyen az S-ben lévő leggyakoribb címke, és return gyökér különben
o o o
legyen At a legjobban vágó attribútum a gyökér címkéje legyen At At minden lehetséges v értékére
a gyökér alá hozzunk létre új ágat, ami az At attribútum v értékét reprezenztálja
legyen Sv azon példák halmaza S-ből, melyek At értéke v ha Sv üres, akkor az adott ághoz tartozó csúcs (levél) címkéje legyen az Sben lévő leggyakoribb címke
•
ha Sv nem üres, akkor az ághoz csatoljuk be az ID3(Sv, C, A-{At}) által visszaadott csúcsot
return gyökér
Legjobban vágó attribútum Legyenek p+, és p- az S-beli pozitív, és negatív példák aránya Entrópia: halmaz homogenitásának mértéke (rendezetlenség foka, információ..)
E S =− p pos⋅log 2 p pos − p minus⋅log 2 p minus
E(S)
1
0
0,5 p+
1
Egy adott A attribútumhoz tartozó várható nyereség, az entrópia várható csökkenése
Gain S , A=E S −∑ v ∈ A
∣S v∣ E S v ∣S∣
Tehát egy adott csúcsban a legnagyobb Gain(S, A)-val rendelkező A-t választjuk vágó attribútumnak.
Főbb tulajdonságok •
a módszer mohó módon minél kisebb méretű fát épít, ezzel próbál általánosítani
•
a modell (a fán kívül) felfogható konjunciók diszjunkciójaként
•
emberi szemmel értelmezhető, szemléletes
•
nem érzékeny a zajokra (statisztikai alapon dönt)
•
könnyen kiterjeszthető (folytonos attribútumokra, hiányzó értékek kezelésére, ...)
Példa Magasság Hajszín Szemszín Címke 1
alacsony
szőke
kék
+
2
magas
szőke
barna
-
3
magas
vörös
kék
+
4
alacsony
sötét
kék
-
5
magas
sötét
kék
-
6
magas
sötét
barna
-
7
alacsony
szőke
barna
-
S={1,2,3,4,5,6,7} (csak a sorszámokkal azonosítva a példákat, egyszerűsítve) A={Magasság, Hajszín, Szemszín} C=Címke={+,-} (mivel ez menetközben nem változik, ezért csak most írjuk ki) •
ID3(S, C, A)
2 5 , p minus= 7 7
◦
p pos=
◦
2 2 5 5 E S =− p pos⋅log 2 p pos − p minus⋅log 2 p minus=− ⋅log 2 − ⋅log 2 =0.8631 7 7 7 7
◦
Gain S , Magasság ▪ ▪ ▪
◦
1 1 2 2 S alacsony = {1,4,7 } , ∣S alacsony∣=3, E S alacsony =− ⋅log 2 − ⋅log 2 =0.9183 3 3 3 3 1 1 3 3 S magas= { 2,3,5,6 } , ∣S magas∣=4, E S magas =− ⋅log 2 − ⋅log 2 =0.8113 4 4 4 4 ∣S ∣ ∣S ∣ Gain S , Magasság = E S − alacsony ⋅E S alacsony − magas ⋅E S magas =⋯ ∣S∣ ∣S∣ 3 4 ⋯=0.8631− ⋅0.9183− ⋅0.8113=0.0059 7 7
Gain S , Hajszín ▪ ▪
1 1 2 2 S szőke = { 1,2,7 } , ∣S szőke∣=3, E S szőke =− ⋅log 2 − ⋅log 2 =0.9183 3 3 3 3 S vörös= { 3 } , ∣S vörös∣=1, E S vörös =0 definíció alapján , mivel p pos=1
▪ ▪
S sötét = { 4,5,6 } , ∣S sötét∣=3, E S sötét =0
definíció alapján , mivel p pos=0
∣S szőke∣ ∣S ∣ ∣S ∣ ⋅E S szőke − vörös ⋅E S vörös − sötét ⋅E S sötét =⋯ ∣S∣ ∣S∣ ∣S∣ 3 1 3 ⋯=0.8631− ⋅0.9183− ⋅0− ⋅0=0.4696 7 7 7
Gain S , Hajszín= E S −
◦
Gain S , Szemszín ▪ ▪ ▪
2 2 2 2 S kék = { 1,3,4,5 } , ∣S kék∣=4, E S kék =− ⋅log 2 − ⋅log 2 =1 4 4 4 4 S barna= { 1,4,7 } , ∣S barna∣=3, E S barna =definíció alapján , p pos=0=0 ∣S ∣ ∣S ∣ Gain S , Szemszín= E S − kék ⋅E S kék − barna ⋅E S barna =⋯ ∣S∣ ∣S∣ 4 3 ⋯=0.8631− ⋅1− ⋅0=0.4345 7 7
◦ Legjobban vág: Hajszín ▪ felosztás: • S szőke = { 1,2,7 } , S vörös = { 3 } , S sötét= { 4,5,6 } ▪ a vörös, és a sötét esetek egyszerűek: az elsőben csak +, a másodikban csak negatív példák vannak ▪ így rekurzív hívás csak a szőke esetre szükséges ▪ ami eddig megvan tehát:
hajszín sötét
szőke vörös
•
+
?
ID3(Sszőke, C, A-{Hajszín}) Magasság Hajszín Szemszín Címke 1 alacsony
szőke
kék
+
2
szőke
barna
-
szőke
barna
-
magas
7 alacsony
◦ ◦
1 2 , p minus= 3 3 1 1 2 2 E S =− ⋅log 2 − ⋅log 2 =0.9183 3 3 3 3 p pos=
◦
Gain S , Magasság ▪ ▪ ▪
◦
1 1 1 1 S alacsony = {1,7 } , ∣S alacsony∣=2, E S alacsony =− ⋅log 2 − ⋅log 2 =1 2 2 2 2 S magas= { 2,3,5,6 } , ∣S magas∣=4, E S magas =0 definíció szerint 2 1 Gain S , Magasság =0.9183− ⋅1− ⋅0=0.2516 3 3
Gain S , Szemszín ▪ S kék = { 1 } , ∣S kék∣=1, E S kék =0 definíció szerint ▪ S barna= { 2,7 } , ∣S barna∣=2, E S barna=0 definíció szerint 1 2 ▪ Gain S , Szemszín=0.9183− ⋅0− ⋅0=0.9183 3 3
◦ Legjobban vág: Szemszín ▪ és ezzel kész is, hiszen a kék színhez csak pozitív, a barnához csak negatív példák tartoznak ▪ visszakapjuk a fentebb bemutatott fát
