Mintázatok felismerése (Pattern recognition) Kiváltott agyi jelek informatikai feldolgozása

Mintázatok felismerése (Pattern recognition) Kiváltott agyi jelek informatikai feldolgozása

1

Bevezetés • Egy ötéves gyerek már felismer karaktereket, akár elforgatva, kézzel írva, géppel nyomtatva, összegyűrt lapon, foltos háttérrel, stb. • Ugyanezt a feladatot gépnek megtanítani nehéz • Mintázatok felismerésre (pattern recognition) • Gépi felismerés, osztályozás, minta csoportosítás, automatikus címkézés • Biológia, pszichológia, orvostudományok, piackutatás, vizuális és audió feldolgozás, mesterséges intelligencia 2

Példák mintafelismerést használó alkalmazásokra

3

Bevezetés Feladatok • A mintafelismerés tervezésének három fő feladata • adat kinyerés és előfeldolgozás • szenzorok/mért adatok kiválasztása • előfeldolgozó technika

• adat reprezentáció • Milyen séma szerint reprezentáljuk az adatokat

• döntéshozatal • döntéshozatal modellje

• A felismerés legismertebb megközelítései • • • •

sablonillesztés statisztikai osztályozás szintaktikus vagy szerkezeti illesztés neurális hálózatok

• Ezek a modellek átfednek, és nem létezik „optimális” megoldás • a legjobb megoldás mindig feladat specifikus

4

Bevezetés Sablonillesztés • Az egyik legegyszerűbb és legkorábbi mintafelismerés • Az illesztés („matching”) a mintafelismerés egy elemi művelete • Két entitás (pont, görbe, alakzat) hasonlóságának megállapítása

• A felismerni kívánt mintázatra egy sablonkészletből sablonokat illeszt • Különböző transzformációk (forgatás, nagyítás) alkalmazásával

• A sablonokat egy tanító halmaz alapján, vagy szabály alapon állapítjuk meg • Alapvetően számításigényes feldolgozást igényel • Nagy osztályon-belüli variáltság esetén nem hatékony 5

Bevezetés Szintaktikai megközelítés • A szintaktikai megközelítésben egy mintázat sorozatos almintázatok egymásra épülése • A legegyszerűbb almintát primitívnek nevezzük, a komplex mintát pedig ezen primitívek közötti kölcsönös kapcsolattal jellemezzük • Nyelvtani analógia: • Minták – mondatok • Primitívek – ábécé • Kapcsolatok – nyelvtan

• Előnye, hogy intuitív, az osztályozás mellett megadja a mintázat primitívekből való felépítését is • Hasznos, amikor a mintázatok szerkezetéről előzetes, szabály-alapú tudásunk van

6

Bevezetés Statisztikai megközelítés • A statisztikai megközelítés esetén minden minta d db jellemzővel reprezentált • d-dimenziós jellemzővektor

• A cél, hogy olyan jellemzőket válasszunk, hogy a kategóriák a ddimenziós térben a legkompaktabb és diszjunkt régiókat foglalják el • A tanítás során a mintahalmaz alapján olyan határvonalakat (hipersíkokat), döntési határokat keresünk, amelyek elkülönítik az egyes kategóriákat

7

Statisztikai mintafelismerés Működési vázlat • d-dimenziós jellemzővektor • Az előfeldolgozó az adatokon végez zajszűrő, kiemelő, normalizáló és kompakt reprezentációs műveleteket • A tanulási módban a jellemző kiválasztás megállapítja a tanulás szempontjából legalapvetőbb jellemzőket • Az osztályozás során a bemenő mintát beosztjuk egy adott kategóriába

8

Statisztikai mintafelismerés Osztályozás • Az osztályozás során a cél, hogy egy adott d jellemzővel leírt 𝒙 = 𝑥1 , 𝑥2 , … , 𝑥𝑑 mintát beosszunk c darab 𝜔1 , 𝜔2 , … , 𝜔𝑐 kategória közül egybe. • Feltételezzük, hogy a jellemzőknek van egy eloszlása a mintaosztályokon. • A 𝜔𝑖 osztályhoz tartozó x jellemzővektor a 𝒑 𝒙 𝜔𝑖 valószínűségi függvényből nyert véletlen megfigyelés

Bayes-szabály alkalmazása: 𝒑 𝒙 𝜔𝑖 ∙ 𝒑 𝜔𝑖 𝒑 𝜔𝑖 𝒙 = 𝒑 𝒙

9

Statisztikai mintafelismerés Bayes döntés Az optimális Bayes döntés szerint a hiba (= egy veszteségfüggvény értéke) minimalizálása a következők szerint írható fel: • Rendeljük hozzá a bemenő x jellemzővektorunkat a 𝜔𝑖 osztályhoz úgy, hogy a következő feltételes hiba minimális legyen: 𝑐

𝑅 𝜔𝑖 𝒙 = ෍ 𝐿 𝜔𝑖 , 𝜔𝑗 ∙ 𝑃 𝜔𝑗 𝒙 𝑗=1

• ahol 𝐿 𝜔𝑖 , 𝜔𝑗 a 𝜔𝑖 osztályra való döntés veszteségfüggvénye abban az esetben, amikor a valódi osztályunk 𝜔𝑗 , 𝑃 𝜔𝑗 𝒙 pedig az aposteriori valószínűség.

A következő veszteségfüggvény esetén

0, ℎ𝑎 𝑖 = 𝑗 1, ℎ𝑎 𝑖 ≠ 𝑗 a feltételes hiba a rossz döntés feltételes valószínűségére egyszerűsödik. Ekkor a Bayes döntés a következő egyszerű formában fogalmazható meg (Maximum aposteriori (MAP) döntés): Rendeljük hozzá a bemenő x jellemzővektorunkat a 𝜔𝑖 osztályhoz akkor, ha 𝑃 𝜔𝑖 𝒙 > 𝑃 𝜔𝑗 𝒙 minden 𝑗 ≠ 𝑖−re 𝐿 𝜔𝑖 , 𝜔𝑗 = ቊ

10

Statisztikai mintafelismerés Paraméteres/nem paraméteres probléma • Ha minden osztályfüggő eloszlás teljesen ismert, akkor a Bayes döntési szabály alkalmas (optimális) osztályozó létrehozására • Ám az eloszlások általában nem, vagy csak részben ismertek  ezeket tanítómintákból határozzuk meg

• Ha az eloszlások formája (pl. normál eloszlás) ismert, de egyes paraméterei (átlag, szórás) nem, akkor paraméteres döntési problémáról beszélünk • Az ismeretlen paramétereket a tanító minták alapján becsüljük meg

• Ha az eloszlások formája nem ismert, akkor nem paraméteres problémáról beszélünk • Ilyenkor vagy magát az eloszlást becsüljük meg, vagy közvetlen döntési határokat alkotunk

11

Statisztikai mintafelismerés Tanítás módja, döntéshozatal módja • Tanítás módja • Felügyelt tanításnak nevezzük, ha a tanító mintáink előre meghatározott osztályokba tartoznak, és ezek megkülönböztetéséhez alkotunk szabályokat, döntéseket • Nem felügyelt a tanítás akkor, ha a mintáink nincsenek előre ismert osztályok szerint címkézve • Előfordulhat, hogy még az osztályok számát sem ismerjük

• Döntéshozatal • Geometriai megközelítés • Közvetlen döntési határok alkalmazása

• Valószínűségi megközelítés • Közvetett döntéshozatal, eloszlások ismerete alapján 12

Statisztikai mintafelismerés Probléma megoldási megközelítések (balról jobbra egyre kevesebb a rendelkezésre álló információ)

13

Statisztikai mintafelismerés Tanulási hibák • Egy adott probléma megoldását tanító minták alapján készítjük el • A későbbi tesztelni kívánt minták a tanító mintáktól nagy valószínűséggel eltérnek • Annál jobb az osztályozó, minél jobb az általánosító képessége

• Az osztályozó rossz általánosító képessége a következőkből eredhet i.

ii. iii.

Az jellemzővektor dimenziója túl nagy a tanító minták számához képest („a dimenzionalitás átka”, curse of dimensionality) Az osztályozó ismeretlen paramétereinek száma túl nagy (pl. neurális hálózat mérete) Az osztályozó túlságosan rátanul a tanító mintákra („overfitting”) 14

Statisztikai mintafelismerés Curse of dimensionality • Az osztályozó teljesítménye függ a minták száma, a jellemzők száma és az osztályozó bonyolultságának kapcsolatától • A naiv táblázat-keresési eljárás esetén a tanító minták száma a jellemzők számának hatványával arányos • Elnevezés: Curse of dimensionality • „Peaking phenomenon”

• Habár a fenti tényezők összefüggését nehéz egzaktul megadni, vannak általános irányelvek • n/d > 10 (n: tanító minták száma, d: jellemzők száma) • Bonyolultabb osztályozónál (sok neuronos hálónál) az arány nagyobb 15

Peaking phenomenon Példa Legyen adott egy két osztályos probléma, ahol a minták ddimenziós Gauss eloszlásúak egységmátrixú kovarianciamátrixszal, valamint a következő átlagvektorokkal 1 1 1 1 𝒎𝟏 = 1, ,…, , 𝒎𝟐 = −1, − ,…,− 2 2 𝑑 𝑑 • A jellemzők folyamatosan egyre csökkenő megkülönböztető erővel bírnak.

Ha minden eloszlást ismerünk, akkor az osztályozási hiba egy mintára: lim 𝑃𝑒 𝑑 = 0 𝑑→∞

Ha a paramétereket n darab tanító mintákból becsüljük, akkor az 1 osztályozási hiba lim 𝑃𝑒 𝑛, 𝑑 = 𝑑→∞

2

16

Statisztikai mintafelismerés Trunk’s example

17

Dimenzió csökkentés Feature selection/extraction • Jellemző kiválasztás (selection) • A bemeneti jellemző halmazból a legjobb részhalmaz kiválasztása • Csökkenti a mérési költséget • Nem módosítja a jellemzőket • Az osztályozás megértésében fontos lehet

• Jellemző kinyerés (extraction) • A meglévő jellemzőkből (lineáris vagy nem lineáris) transzformáció útján újakat állít elő • Az új jellemzők és az eredetiek fizikai jelentése nem egyezik meg

• Az új jellemzők nagyobb megkülönböztető erővel bírnak

• A két kifejezést sajnos keverve használják 18

Dimenzió csökkentés A jellemzők vizuális megjelenítése • A minták megjelenítése számos esetben jó kiindulási alap a feladat megoldásához • A d-dimenziós tér 2D vagy 3D-s térbe vetítése

Példa: arcok

19

Dimenzió csökkentés Intrinsic (belső) dimension • A dimenziócsökkentés egyik fő kérdése olyan kritérium megállapítása, ami megmondja, hogy melyik kiválasztott jellemző részhalmaz a legjobb • Lehet az osztályozási hiba (kis mintaszám esetén nem robosztus)

• Intrinsic dimensionality: egy többváltozós jel azon dimenziószáma, amely elegendő a jel leírásához 𝑓 = 𝑓 𝒙 , ahol 𝒙 = 𝑥1 , 𝑥2 , … , 𝑥𝑁 Ha van olyan m-változós g függvény és m x n-es A mátrix, amely esetén minden x-re 𝑓 𝒙 = 𝑔 𝑨𝒙 és m a legkisebb olyan érték, amelyre a fenti egyenlet fennáll, akkor f() belső (intrinsic) dimenziója m • Habár léteznek eljárások az m megállapítására, az azokba vezető transzformációt nem adják meg.

20

Jellemző kinyerés PCA • Az ismert egyik legjobb lineáris jellemző kinyerő a Főkomponens elemzés (Prinicipal component analysis, PCA) • Ortogonális transzformáció, amely az adatokat egy új koordinátarendszerbe transzformálja úgy, hogy a koordináták az eredeti adatok egyre kevesebb varianciájú irányát adják. • első koordináta: legnagyobb variancia • második: második legnagyobb variancia • …

• A PCA felügyelet nélküli jellemzőkinyerő eljárás

21

Jellemző kinyerés PCA

22

Jellemző kinyerés Multidimensional Scaling, MDS Az MDS a sokdimenziós adathalmaz 2-3 dimenziós ábrázolását célozza meg. Legyen I darab objektumunk, és definiáljuk a közöttük lévő 𝛿𝑖,𝑗 mértéket, mint a i. és j. objektum közötti távolságot. Alkossuk meg a következő távolság mátrixot: 𝛿1,1 ⋯ 𝛿1,𝐼 ⋮ ⋱ ⋮ Δ≔ 𝛿𝐼,1 ⋯ 𝛿𝐼,𝐼 Az MDS célja adott Δ mellett olyan 𝑥1 , … , 𝑥𝐼 ∈ 𝑅𝑁 vektorok megalkotása, hogy 𝑥𝑖 − 𝑥𝑗 ≈ 𝛿𝑖,𝑗 minden 𝑖, 𝑗 ∈ 1, … 𝐼−re ahol ∙ a vektor norma, klasszikus esetben Euklideszi távolság. Ha N=2 vagy 3, akkor az adathalmazt vizuálisan is tudjuk ábrázolni. Az MDS megoldását általában optimalizációs problémaként írják fel, ahol az 𝑥1 , … , 𝑥𝐼 -t valamilyen költségfüggvény minimalizálásával kapjuk meg, pl: min ෍ 𝑥𝑖 − 𝑥𝑗 − 𝛿𝑖,𝑗

𝑥1 ,…,𝑥𝐼

𝑖<𝑗

2

23

Jellemző kinyerés Neurális Hálózat Lásd a NN-os slide-ot!

24

Jellemző kinyerés Önszerveződő háló, self-organizing Map (SOM, Kohonnen-háló) A hálóban a neuronok m-dimenziós rácsszerkezetben helyezkednek el (általában m=1,2 vagy 3). Minden neuron össze van kötve a minden d bemenettel. A neuronok d kapcsolata egy d dimenziós súlyvektort ír le. A mintákat sorban bemutatjuk a hálónak, és a súlyokat úgy módosítjuk, hogy a nyertes neuron (amelynek a súlyvektora a legközelebb esik a bemenő vektorhoz) környezetének súlyvektorai a nyertes neuron súlyvektora felé tolódjon. A tanítás után a szomszédos neuronok olyan bemeneti mintázatokat reprezentálnak, amelyek közel vannak egymáshoz az eredeti térben • Topológia megőrző térkép

𝑊𝑣 𝑠 + 1 = 𝑊𝑣 𝑠 + 𝜃 𝑢, 𝑣, 𝑠 𝛼 𝑠 𝐷 𝑡 − 𝑊𝑣 𝑠

𝑣: neuron 𝑤𝑣 : v. neuron súlyvektora 𝜃 𝑢, 𝑣, 𝑠 : v. és u. neuron távolsága (u: nyertes neuron) 𝛼 𝑠 : tanító korlátozó szorzó 𝐷 𝑡 : bemenő t. minta

25

Jellemző kinyerés Kohonnen-háló példa

26

Jellemző kinyerés Kohonnen-háló vs PCA

27 Szürke: adatpontok

Kék: PCA első főkomponense Piros: 20 csomópontos Kohonnen-háló

Jellemző kiválasztás Feladat megfogalmazása • Legyen Y a jellemzők halmaza, d elemmel. Jelölje m a jellemzők kívánt számát a kiválasztott X (𝑋 ⊆ 𝑌) részhalmazban • Legyen 𝐽 𝑋 az X kiválasztási kritériuma. J() magasabb értéke jobb jellemző részhalmazt jelöl. • Lehetséges alapvető ilyen függvény az osztályozási hiba: 𝐽 = 1 − 𝑃𝑒

• Kimerítő keresés: • Minden lehetséges X részhalmazra kiszámoljuk J-t, és a legmagasabb értékkel rendelkező részhalmazt választjuk ki. • Csak ez garantál optimális megoldást

• Ha 𝐽 ⋅ monoton úgy, hogy 𝑋1 ⊂ 𝑋2 esetén 𝐽 𝑋1 < 𝐽 𝑋2 , akkor a „branch and bound” algoritmus is optimális eredményt ad kimerítő keresés nélkül • Ez a feltétel azonban általában nem teljesül

28

Eljárás

Tulajdonság

Kimerítő keresés

Minden

Branch-and-bound keresés

Csupán az összes lehetséges részhalmaz egy részének kiértékelése szükséges

Monoton kritériumfüggvény esetén optimális megoldást ad.

Legjobb különálló jellemzők

Minden m jellemző kiértékelése; a legjobbak kiválasztása

Egyszerűen számítható, nem valószínű, hogy optimális megoldást ad.

Sequential Forward Selection (SFS)

A legjobb jellemző kiválasztása, majd egyesével azon jellemzők hozzáadása, amelyek maximalizálják a kritérium függvényt.

Egy hozzáadott jellemzőt már nem lehet eltávolítani. Alacsony számításigényű (pl. 2 elemű halmaz kiválasztásához d-1 elemet kell kiértékelni)

Sequential Backward Selection (SBS)

d jellemzővel kiindulva folyamatosan vegyünk el egyet.

Egy törölt jellemzőt már nem lehet újra hozzáadni. Nagyon számításigényű, mint az SFS.

„Plus l-take away r” kiválasztás

Vegyünk fel l jellemzőt SFS-sel, majd vegyünk el r jellemzőt SBS-sel.

Kiküszöböli a SFS és SBS azon hibáját, hogy a rejtett belső jobb részhalmazokat („nesting”) azok nem találják meg. Szükséges az l és r helyes megválasztása.

Sequential Forward Floating Search (SFFS) and Sequential Backward Floating Search (SBFS)

A „plus l-take away r” általánosítása; l és r értékei automatikusan, dinamikus módon kerülnek meghatározásra

Optimálishoz közeli megoldást ad elfogadható számításigénnyel.

𝑑 𝑚

Megjegyzés

részhalmaz kiértékelése

Optimális megoldást ad. Nagyon számításigényes.

29

Jellemző kiválasztás eljárások

30

Példa osztályozási hibára a jellemzők számának függvényében (SFFS)

Osztályozók • Három alapvető kategória • Hasonlóság alapú • Valószínűségi alapú • Döntési határ alapú (geometriai)

31

Gépi osztályozók Hasonlóságon alapuló osztályozók • Azok a minták, amelyek közel esnek egymáshoz, egy osztályba tartoznak • Kell egy hasonlósági metrika (pl. euklideszi távolság)

• Sablon alapú, minimális távolság alapú osztályozó • Nearest mean classifier • Minden osztályhoz egy átlagvektor prototípus

• Vektorkvantálás • k nearest neighbour decision rule (k-NN) • A legközelebbi tanító minták többségi döntése • Jó hasonlítási alapot ad más osztályozók teljesítményének értékeléséhez 32

Gépi osztályozók Valószínűségi alapú osztályozók Bayes döntés: az ismert vagy becsült feltételes sűrűségfüggvények alapján a legvalószínűbb osztály kiválasztása Rendeljük hozzá a bemenő x jellemzővektorunkat a 𝜔𝑖 osztályhoz akkor, ha 𝑃 𝜔𝑖 𝒙 ∙ 𝑃 𝑤𝑖 > 𝑃 𝜔𝑗 𝒙 ∙ 𝑃 𝑤𝑗 minden 𝑗 ≠ 𝑖−re

Logistic regression Legyen két kimeneti esetünk: 0 és 1.

Logisztikus függvény:

33 t=-4.0777+1.5046x

Gépi osztályozók Geometriai alapú osztályozók Döntési határok (síkok, hipersíkok) meghatározása hibakritériumok alapján Linear Discriminant Analysis (LDA) Ismertek a következő normál eloszlású feltételes valószínűségek: 𝑝 𝑥|𝑦 = 0 és 𝑝 𝑥|𝑦 = 1 Döntsünk 0-ra, ha

𝑝 𝑥|𝑦=0 𝑝 𝑥|𝑦=1

>𝑇

𝑥 − 𝜇0 𝑇 Σ0−1 𝑥 − 𝜇0 +ln Σ0 − 𝑥 − 𝜇1 𝑇 Σ1−1 𝑥 − 𝜇1 − ln Σ1 Ha Σ0 = Σ1 = Σ, akkor a képlet a következőre egyszerűsödik: 𝑤∙𝑥 >𝑐 1 𝑤 = Σ −1 𝜇1 − 𝜇0 és 𝑐 = 𝑇 − 𝜇0𝑇 Σ −1 𝜇0 + 𝜇1𝑇 Σ−1 𝜇1 2

>𝑇

34

Gépi osztályozók Fisher’s linear discriminant „scatter” mátrix:

𝑆𝑖 = ෍ 𝑥 − 𝑥ഥ𝑖 𝑥 − 𝑥ഥ𝑖

𝑇

𝑥ഥ𝑖 : az i. osztály átlaga

𝑥∈𝑐𝑖

intra-”scatter” mátrix: ∑𝑤 = 𝑆1 + 𝑆2 = ෍ ෍ 𝑥 − 𝑥ഥ𝑖 𝑥 − 𝑥ഥ𝑖

𝑇

𝑖 𝑥∈𝑐𝑖

inter-”scatter” mátrix: ∑𝑏 = 𝑥1 − 𝑥2 𝑥1 − 𝑥2

𝑇

Olyan 𝑤 transzformációt keresünk, amely a következő kifejezést maximalizálja: 𝑤 𝑇 ∑𝑏 𝑤 𝐽 𝑤 = 𝑇 𝑤 ∑𝑤 𝑤 ∑

A 𝑤-t a ∑ 𝑏 mátrix sajátvektorai adják. 𝑤

Többosztályos LDA: 35

𝑛

∑𝑤 = ෍ 𝑆𝑖 𝑖

∑𝑏 = ෍ 𝑥ഥ𝑖 − 𝑥ҧ 𝑥ഥ𝑖 − 𝑥ҧ 𝑖=1

𝑇

36

Gépi osztályozók Szupport Vektor Gépek • Az eljárás fő célja az osztályok közötti szeparálási margó maximalizálása • A margót az un. szupport vektorok definiálják • A margó széleihez tartozó tanító minták

37 Két osztály, amely egy hipersíkkal elkülöníthető

Gépi osztályozók Neurális hálózat Gépi tanulást megvalósító mesterséges neuronok hálózata 𝑥0 = 1

𝑤0

𝑥1

𝑤1

𝑥2

𝑤2

𝑥𝑁

𝑤𝑁

∑

𝑠

𝑓

𝑦

Aktiváló bemenet

Egyenrangú bemenetekkel rendelkező memória nélküli neuron felépítése

𝑠 = ෍ 𝑤𝑖 𝑥𝑖 = 𝑤 𝑇 𝑥 𝑖=0

𝑦=𝑠=

𝑦 = 𝑓 𝑠 = 𝑓 𝑥𝑇𝑤

1.5 1 0.5 0

y(s)

𝑁

𝑤𝑇𝑥

-3

-1

1 s

Szigmoid függvény

3

38

Neurális hálózatok • A neurális hálózatokat tekinthetjük masszív párhuzamos feldolgozást megvalósító rendszereknek, rendkívül nagy számú egyszerű feldolgozó egységgel és azok kereszt-kapcsolataival • Egy súlyozott irányított gráf különböző szerkezeti alapelvekkel • A csomópontok a mesterséges neuronok • A közöttük lévő súlyozott élek a neuronok közötti kapcsolatok

• A fő tulajdonságok • Képesek összetett, nem-lineáris bemenet-kimenet kapcsolat megtanulására • Szekvenciális tanulási eljárással rendelkeznek • Képesek magukat adaptálni az adatokhoz • Elrejtik a feladat megoldásának mikéntjét • Nem igényel tudást (vagy csak keveset) a problémáról

• Leggyakoribb neurális hálózat családok • Előrecsatolt neurális hálózat (feed-forward neural network) • Önszerveződő háló (Self-organizing Map SOM, Kohonnen-háló)

39

Jellemző kinyerés Neurális Hálózat A hálózat megfelelő szerkezetével jellemzőkinyerést érhetünk el • A rejtett rétegek kimenetei új jellemzőkként is interpretálhatóak

3-dimenziós altér keresése NN-val (a) lineáris (b) nem lineáris

40

Method

Property

Comments

Template matching

A mintát a leghasonlóbb sablonhoz rendeljük

A sablont és a metrikát a felhasználó adja meg

Nearest Mean Classifier

A mintát a legközelebbi átlagú osztályhoz rendeljük

Majdnem semmi tanítást nem igényel; gyors tesztelés; metrika és skálázás függő

1-Nearest Neighbor Rule

A mintát a legközelebbi tanító minta osztályához rendeljük

Nem kell tanítás; robosztus teljesítmény; lassú tesztelés; skála és metrika függő

k-Nearest Neighbor Rule

A mintát ahhoz az osztályhoz Aszimptotikusan optimális; rendeljük, amelyből a legtöbb van skála és metrika függő; lassú a minta közelében k környezetben tesztelés (k optimalizálva)

Bayes plug-in

A mintát ahhoz az osztályhoz rendeljük, amely a maximális becsült poszterior valószínűséggel rendelkezik

Egyszerű normális eloszlású osztályozók; érzékeny a sűrűségfüggvény becslési hibákra

Logistic Classifier

Maximum likelihood szabály a logisztikus (szigmoid) poszterior valószínűséghez

Lineáris osztályozó; iteratív eljárás; eltérő eloszlásokra optimális; vegyes adattípusokhoz is jó

41

Eljárás

Tulajdonság

Megjegyzés

Parzen classifier

Bayes plug-in szabály Parzen sűrűség becslésre; a k-NN általánosítása

Aszimptotikusan optimális; skála és metrika függő; lassú tesztelés

Fisher Linear Discriminant

Lineáris osztályozó MSE optimalizálással

Egyszerű és gyors; hasonló a Bayes plug-in osztályozóhoz normáls eloszlásokra azonos kovariancia mátrixszal

Binary Decision Tree Meghatározott jellemző sorozat és küszöbértékek keresése

Iteratív tanuló eljárás; túltanulás érzékeny; metszés szükséges; gyors tesztelés

Perceptron

Iteratív optimalizációs lineáris osztályozó

Érzékeny a tanító paraméterekre; konfidencia értékeket képes adni

Neural Network (Feed-forward)

Iteratív MSE optimalizációs eljárás

Érzékeny a tanító paraméterekre; konfidencia értékeket képes adni; lassú tanulás; nemlineáris osztályozás; túltanulás érzékeny

Radial Basis Network (NN altípus)

Iteratív MSE optimalizációs eljárás egy nem lineáris transzformációt végző rejtett réteggel

Érzékeny a tanító paraméterekre; konfidencia értékeket képes adni; lassú tanulás; nemlineáris osztályozás; túltanulás érzékeny; robosztus a kilógó értékekkel szemben

Szupport vektor gépek

Osztályok közötti szeparálási margó maximalizálása

Skála és metrika függő; iteratív; lassú tanulás; nemlineáris; túltanulás érzéketlen; jó optimalizációs teljesítmény

42

Gépi osztályozók kombinálása • Érvek, amikor a külön-külön megvalósított osztályozók kombinálása eredményes lehet: • Több különféle típusú osztályozó megvalósítás • Azonos feladatra különböző szempontból tanított osztályozók • Személyfelismerésre: arc, beszéd, kézírás

• Több tanító halmaz érhető el, esetleg különböző jellemzőkészlettel • Az olyan osztályozók esetén, amelyek érzékenyek a kezdeti paraméterekre (pl. neurális hálózatok) a paramétertétbeli keresés helyett több kezdő paraméterrel rendelkező osztályozót kombinálhatunk

43

Gépi osztályozók kombinálása Példák • Stacking: több osztályozó kimenetét használjuk egy különálló osztályozó bemeneteként • Bagging: a meglévő tanító adatbázisból véletlen mintavétellel (visszatevéssel) halmazokat képezünk és ezekkel tanítjuk a különálló osztályozókat • Boosting: egymás után kötött súlyozott gyenge osztályozók (gyenge: alig jobb, mint véletlenszerű döntés) • Schapire: „korrelálatlan, gyenge osztályozók kombinációja által elért hiba tetszőlegesen kicsi lehet a tanító adatokon” • Intuitív értelmezés: a problémát egyre komplexebb területenként osztályozzuk • Pl: AdaBoost

44

Regresszió Eddigi feladat: minták diszkrét kategóriákba sorolása • osztályozás

Regresszió: folytonos kimenetű függvény becslése Bemenő vektor: 𝑿 = 𝑋1 , 𝑋2 , … , 𝑋𝑛 Kimenet: 𝑌 (valós érték) Cél: 𝑓 𝑋 → 𝑌 függvény becslése

• • • •

Lineáris regresszió Nem-lineáris regresszió Logisztikus regresszió (osztályozó) Support Vector Regression

45

Lineáris regresszió Egyszerű lineáris egyenes illesztése az adatpontokra meredekség

kimenet

𝑦 = 𝛽𝑥 + 𝛼

kezdeti eltolás

bemeneti vektor

∑𝑛𝑖=1 𝑥𝑖 − 𝑥ҧ 𝑦𝑖 − 𝑦ത 𝐶𝑜𝑣 𝑥 𝑦 𝛽መ = = ∑𝑛𝑖=1 𝑥𝑖 − 𝑥ҧ 2 𝑉𝑎𝑟 𝑥 𝛼 = 𝑦ത − 𝛽መ 𝑥ҧ

46

Adathalmaz felosztása • Gyakorlatban alkalmazott adatbázis felosztás tanító eljárásoknál: • Tanító halmaz • Az osztályozó tanítása

• Developement halmaz • Az osztályozó paramétereinek beállítása

• Tesztelő halmaz • Az osztályozó teljesítményének, hiba-valószínűségének megállapítása

• A különböző halmazoknak elegendően nagynak és függetlennek kell lenniük

47

48

Adathalmazok felosztásának módszerei

49

Hiba becslés • Cél: metrika, amely segítségével az osztályozó eljárások összehasonlíthatóak • „Osztályozási hiba”, „hiba arány”, „Pe” • Hibázási valószínűség • Jellemzők mérésének költsége, döntés számításigénye

• A Pe zárt formában való megadása nehéz  feltételes valószínűségekkel való felírása könnyebb • Konzisztens tanító szabályokkal és megfelelő méretű adathalmazzal Pe megközelíti a Bayes-i hibát

50

Pe meghatározása • Az osztályozó hibájának becslése véletlen valószínűségi változó • Legyen τ azon minták száma a teszt halmazon, amelyet hibásan osztályoztunk (összesen n mintából) • τ sűrűségfüggvénye binomiális eloszlású • 𝑃෡𝑒 a 𝑃𝑒 maximum-likelihood becslése) a következő 𝜏 𝑃 𝑃෡𝑒 = , E 𝑃෡𝑒 = 𝑃𝑒 , Var 𝑃෡𝑒 = 𝑒 𝑛

• Konfidencia intervallum:

1−𝑃𝑒 𝑛 1

𝑧 = 1 − 2 𝛼: a normál eloszlás z kvantilise

• Példa: 𝑛 = 250, 𝜏 = 50 → 𝑃෡𝑒 = 0 2, 95%-os konfidencia intervallum: (0.15, 0.25) • C1: 𝜏 = 10, 𝑛 = 100, C2: 𝜏 = 13, 𝑛 = 100. Jobb-e C1, mint C2?

51

Osztályozók teljesítményének egyéb mértékei ℎ𝑖𝑏á𝑠𝑎𝑛 𝑗ó𝑛𝑎𝑘 𝑜𝑠𝑧𝑡á𝑙𝑦𝑜𝑧𝑜𝑡𝑡 𝑚𝑖𝑛𝑡á𝑘 𝑠𝑧á𝑚𝑎 ö𝑠𝑠𝑧𝑒𝑠 𝑗ó𝑛𝑎𝑘 𝑏𝑒𝑠𝑜𝑟𝑜𝑙𝑡 𝑚𝑖𝑛𝑡á𝑘 𝑠𝑧á𝑚𝑎

False Acceptance Rate (FAR) =

ℎ𝑖𝑏á𝑠𝑎𝑛 𝑟𝑜𝑠𝑠𝑧𝑛𝑎𝑘 𝑜𝑠𝑧𝑡á𝑙𝑦𝑜𝑧𝑜𝑡𝑡 𝑚𝑖𝑛𝑡á𝑘 𝑠𝑧á𝑚𝑎 ö𝑠𝑠𝑧𝑒𝑠 𝑟𝑜𝑠𝑠𝑧𝑛𝑎𝑘 𝑏𝑒𝑠𝑜𝑟𝑜𝑙𝑡 𝑚𝑖𝑛𝑡á𝑘 𝑠𝑧á𝑚𝑎 ℎ𝑒𝑙𝑦𝑒𝑠𝑒𝑛 𝑗ó𝑛𝑎𝑘 𝑜𝑠𝑧𝑡á𝑙𝑦𝑜𝑧𝑜𝑡𝑡 𝑚𝑖𝑛𝑡á𝑘 𝑠𝑧á𝑚𝑎 = ö𝑠𝑠𝑧𝑒𝑠 𝑗ó𝑛𝑎𝑘 𝑏𝑒𝑠𝑜𝑟𝑜𝑙𝑡 𝑚𝑖𝑛𝑡á𝑘 𝑠𝑧á𝑚𝑎

False Reject Rate (FRR) =

True positive Rate (TPR)

False positive Rate (FPR) =

ℎ𝑖𝑏á𝑠𝑎𝑛 𝑗ó𝑛𝑎𝑘 𝑜𝑠𝑧𝑡á𝑙𝑦𝑜𝑧𝑜𝑡𝑡 𝑚𝑖𝑛𝑡á𝑘 ö𝑠𝑠𝑧𝑒𝑠 𝑟𝑜𝑠𝑠𝑧𝑛𝑎𝑘 𝑏𝑒𝑠𝑜𝑟𝑜𝑙𝑡 𝑚𝑖𝑛𝑡á𝑘 𝑠𝑧á𝑚𝑎

Receiver Operating Characteristic • TPR és FPR együttes ábrázolása • Görbe alatti terület, mint mérőszám • • • • •

.90-1 - kiváló (A) .80-.90 - jó (B) .70-.80 - közepes (C) .60-.70 - rossz (D) .50-.60 - bukó (F)

52

Osztályozók teljesítményének egyéb mértékei – Reject Rate Reject Rate • Ha egy minta közel esik az elválasztó határhoz, jobb, ha elutasítjuk (az osztályozás alacsony konfidenciájú) • RR: elutasított minták aránya • Mikor utasítsuk el? • Bayes-i aposzterior max. valószínűség • Osztályozó hibájának ábrázolása RR függvényében

53

True condition

Total population

Predicted condition positive

Condition positive

True positive

Condition negative

Prevalence= Σ Cond ition positive/Σ Total population

False positive (Type I error)

Positive predictive False discovery value(PPV), Precision rate (FDR)= Σ False = Σ True positive/Σ Test out positive/Σ Test out come positive come positive

True negative

False omission Negative predictive rate (FOR)= Σ False value(NPV)= Σ True negative/Σ Test out negative/Σ Test out come negative come negative

Predicted condition Predicted condition negative

Accuracy (ACC) = Σ True positive + Σ True negative/Σ Total population

False negative (Type II error)

True positive False positive rate (TPR),Sensitivity, rate (FPR),FallPositive likelihood Recall= Σ True out= Σ False ratio (LR+)= TPR/FP R positive/Σ Conditio positive/Σ Conditio n positive n negative Diagnostic odds ratio (DOR)= LR+/L R− False negative True negative rate (FNR), rate (TNR),Specificity Negative likelihood Miss rate= Σ False (SPC)= Σ True ratio(LR−) = FNR/T NR negative/Σ Conditi negative/Σ Conditi on positive on negative

54

Felügyelet nélküli osztályozás „Data clustering” • Cél: tanító címkék nélkül osztályok elkülönítése • A mintákat „klaszter”-ekbe osztjuk. • Klaszter definíciója: • (1) Az egy klaszteren belüli minták hasonlóbbak, mint a más osztályokhoz tartozók • (2) a relatíve magasabb pontsűrűséggel rendelkező klasztereket relatív alacsony pontsűrűségű rész választja el

55

Felügyelet nélküli osztályozás „Data clustering”

56

Felügyelet nélküli osztályozás „Data clustering” Két alapvető eljárás • partitional clustering • Partíciók alkotása

• hierarchical clustering • Egymásba ágyazott csoportok, az osztályokat ábrázolhatjuk fa struktúrában

57

Partitional clustering Minden klaszterező eljárás találni fog klasztereket, függetlenül attól, hogy léteznek-e • A kialakított klasztereket ellenőrizni kell

Nincs „legjobb” klaszterező algoritmus • Adott célra, adott feldolgozási szempontból lehet valamely algoritmus optimális • Ajánlott több eljárást alkalmazni egyszerre

A partitional clustering formális definíciója: • Legyen n darab mintánk egy d-dimenziós térben. Határozzuk meg a minták K darab klaszteréből álló partíciót úgy, hogy egy adott metrika szerint a klaszterekben lévő minták jobban hasonlítsanak egymáshoz, mint a más klaszterekben lévő mintákhoz. • K lehet előre meghatározott, vagy dinamikus

58

Square-Error Clustering Cél: adott K klaszter esetén minimalizáljuk a négyzetes hibát Legyen adott n darab d-dimenziós minta, amelyeket már valahogyan partícionáltunk K klaszterbe {C1, C2, …, Ck} úgy, hogy Ck klaszternek nk darab mintája van, és minden minta csak egy klaszterbe tartozhat (∑𝐾 𝑘=1 𝑛𝑘 = 𝑛). Definiáljuk a Ck klaszter átlagvektorát (vagy centroidját): 𝑛𝑘 1 𝑘 𝑚𝑘 = ෍ 𝑥𝑖 , 𝑛𝑘 𝑖=1

𝑘

ahol 𝑥𝑖 a Ck-ba tartozó i. minta. A Ck klaszter négyzetes hibája a Ck-ba tartozó minták és a klaszter középpontjának Euklideszi távolságainak összege: 𝑛𝑘

𝑒𝑘2

= ෍ 𝑥𝑖

𝑘

−𝑚

𝑘

𝑇

𝑥𝑖

𝑘

−𝑚

𝑘

𝑖=1

A teljes partíció négyzetes hibája: 𝐾

𝐸𝑘2

=

෍ 𝑒𝑘2 𝑘=1

59

K-means algoritmus 1) Jelöljünk ki egy kezdeti partíciót. Ismételjük a 2-5 lépéseket amíg a minták klaszterekbe tartozása stabilizálódik 2) Generáljuk egy új partíciót úgy, hogy minden mintát a hozzá legközelebbi középpontú klaszterhez rendeljük 3) Számoljuk ki az új klaszterek középpontjait 4) Ismételjük a 2-3 lépéseket, amíg egy optimális 𝐸𝑘2 értéket el nem érünk 5) Finomhangoljuk a klaszterek számát úgy, hogy összevonunk vagy szétosztunk meglévő klasztereket, vagy eltávolítunk kicsi, kilógó klasztereket. Az eljárás gyors, és meglepően jól működik gömb alakú klaszterek esetén • Nem euklideszi távolság esetén egyéb formákra is jó

60

61

Mixture decomposition Generáljunk a következő módon véletlen mintákat: Legyen K véletlen forrásunk, amelyeket egy valószínűségi sűrűségfüggvény 𝑝𝑚 𝑦 𝜃𝑚 ír le, 𝜃𝑚 paraméterrel (𝑚 = 1, … , 𝐾). Minden minta előállításnál véletlenszerűen veszünk egy mintát valamelyik forrásból 𝛼1 , … , 𝛼𝐾 valószínűséggel. Ezzel a mechanizmussal meghatározott véletlen változót egy véges keverék eloszlással (finite mixture distribution) írhatjuk le: 𝐾

𝑝 𝑦Θ

𝐾

= ෍ 𝛼𝑚 𝑝𝑚 𝑦 𝜃𝑚 , 𝑚=1

ahol 𝑝𝑚 𝑦 𝜃𝑚 -et komponensnek nevezzük, és Θ 𝜃1 , … , 𝜃𝐾 , 𝛼1 , … , 𝛼𝐾 .

𝐾

=

(Általában feltételezzük, hogy minden komponens azonos eloszlású.)

62

EM eljárás Expectation-maximization Tekintsünk y tanító mintára, mint hiányos adatra: jelölje 𝒛

𝑖

= 𝑖

(𝑧𝑚 =

𝑇 𝑖 , … , 𝑧𝐾 azt, hogy 𝑖 1, 𝑧𝑝 = 0, 𝑝 ≠ 𝑚). 𝑖 𝑧1

melyik komponens generálta y(i)-t

y és z esetén a likelihood a következőképpen írható fel: 𝐿 𝜽; 𝑌 = 𝑝 𝑌, 𝜽 = ෍ 𝑝 𝑌, 𝑍 𝜽 𝑍

E-lépés: számoljuk ki a feltételes várható értékét a loglikelihoodnak: 𝑄 𝜽 𝜽 𝑡 = 𝐸𝑍|𝑌,𝜽 𝑡 𝐿 𝜽; 𝑌, 𝑍 M-lépés: frissítsük a paramétereket. 𝜽 𝑡+1 = 𝑎𝑟𝑔 max 𝑄 𝜽 𝜽 𝜽

𝑡

63

EM eljárás Példa: normális eloszlás Jelölje 𝑥 = 𝑥1 , 𝑥2 , … , 𝑥𝑛 az n véletlen megfigyelésből álló mintát két d-dimenziós normál eloszlásból álló keverékből. Jelölje z = 𝑧1 , 𝑧2 , … , 𝑧𝑛 azt, hogy a megfigyelések melyik komponensből jöttek.

𝑋𝑖 | 𝑍𝑖 = 1 ~𝒩𝑑 𝝁1 , Σ1 és 𝑋𝑖 | 𝑍𝑖 = 2 ~𝒩𝑑 𝝁2 , Σ2 , ahol P 𝑍𝑖 = 1 = 𝜏1 és P 𝑍𝑖 = 2 = 𝜏2 = 1 − 𝜏1 A célunk, hogy megbecsüljük az ismeretlen paramétereket: 𝜃 = 𝝉, 𝝁1 , 𝝁2 , 𝛴1 , Σ2 többdimenziós normális eloszlás sűrűségfüggvénye 𝑛

2

𝐿 𝜃; 𝑥 = ෑ ෍ 𝜏𝑗 𝑓 𝑥𝑖 ; 𝝁𝑗 , 𝛴𝑗 𝑖=1 𝑗=1

indikátor függvény 𝑛

2

𝐿 𝜃; 𝑥, 𝑧 = 𝑝 𝑥, 𝑧 𝜃 = ෑ ෍ 𝕀 𝑧𝑖 = 𝑗 𝑓 𝑥𝑖 ; 𝝁𝑗 , 𝛴𝑗 𝜏𝑗 𝑖=1 𝑗=1

64

E lépés 𝑡

Adott 𝜃 aránya:

paraméterek esetén 𝑍𝑖 feltételes eloszlása a normális sűrűség 𝜏-val súlyozott 𝑡

𝑡

𝑇𝑗,𝑖 = 𝑃 𝑍𝑖 = 𝑗 𝑋𝑖 = 𝑥𝑖 ; 𝜃

𝑡

=

𝑡

𝜏𝑗 𝑓 𝑥𝑖 ; 𝝁𝑗 , Σ𝑗 𝑡

𝑡

𝑡

𝜏1 𝑓 𝑥𝑖 ; 𝝁1 , Σ1

𝑡

𝑡

𝑡

𝑡

+ 𝜏2 𝑓 𝑥𝑖 ; 𝝁2 , Σ2

„tagsági valószínűségek” (membership probabilities) 𝑛

𝑄 𝜃𝜃

𝑡

= 𝐸 log 𝐿 𝜃; 𝑥, 𝑍

𝑛

= 𝐸 log ෑ 𝐿 𝜃; 𝑥𝑖 , 𝒛𝒊 𝑖=1

= 𝐸 ෍ log 𝐿 𝜃; 𝑥𝑖 , 𝒛𝒊 𝑖=1

𝑛

= ෍ 𝐸 log 𝐿 𝜃; 𝑥𝑖 , 𝒛𝒊 𝑖=1

𝑛

2 𝑡

= ෍ ෍ 𝑇𝑗,𝑖 𝑖=1 𝑗=1

1 1 log 𝜏𝑗 − log Σ𝑗 − 𝑥𝑖 − 𝝁𝑗 2 2

𝑇 −1 Σ𝑗

𝑥𝑖 − 𝝁𝑗 −

𝑑 log 2𝜋 2

Nem kell a teljes kifejezést kiszámolni, mivel a M-lépésben csak a 𝜏 vagy 𝝁-től függő tagok szerint kell maximalizálni.

65

M lépés Maximalizáljuk külön 𝜏 és a 𝜇𝑗 , Σ𝑗 tagokat. Binomiális eloszlás MLE

𝑛

𝝉

𝑡+1

𝑡

= arg max 𝑄 𝜃 𝜃 𝝉

𝜏𝑗

𝑡+1

𝑡+1

𝝁1 𝑛

𝑡

= arg max ෍ 𝑇1,𝑖 𝜇1 ,Σ1

𝑡+1

𝝁1

𝑡+1 𝝁2

=

=

𝑖=1

∑𝑛𝑖=1 𝑇1,𝑖𝑡 𝑥𝑖 ∑𝑛𝑖=1 𝑇1,𝑖𝑡 ∑𝑛𝑖=1 𝑇2,𝑖𝑡

𝑥𝑖

∑𝑛𝑖=1 𝑇2,𝑖𝑡

és

és

𝑡

𝑡

= arg max ෍ 𝑇1,𝑖 log 𝜏1 + ෍ 𝑇2,𝑖 log 𝜏2 𝝉

=

𝑛

𝑖=1 𝑛

∑𝑛𝑖=1 𝑇𝑗,𝑖𝑡 ∑𝑛𝑖=1 𝑇1,𝑖𝑡 + 𝑇2,𝑖𝑡 𝑡+1

, Σ1

𝑖=1

1 𝑡 = ෍ 𝑇𝑗,𝑖 𝑛 𝑖=1 𝑡

= Normális eloszlás MLE 1 1 − log Σ1 − 𝑥𝑖 − 𝝁1 𝑇 Σ1−1 𝑥𝑖 − 𝝁1 2 2

𝑡+1 Σ1

𝑡+1 Σ2

= arg max 𝑄 𝜃 𝜃 𝜇1 ,Σ1

=

=

∑𝑛𝑖=1 𝑇1,𝑖𝑡

𝑥𝑖 −

𝑡+1 𝝁1

𝑥𝑖 −

𝑡+1 𝝁1

𝑇

𝑥𝑖 −

𝑡+1 𝝁2

𝑇

∑𝑛𝑖=1 𝑇1,𝑖𝑡 ∑𝑛𝑖=1 𝑇2,𝑖𝑡

𝑥𝑖 −

𝑡+1 𝝁2

∑𝑛𝑖=1 𝑇2,𝑖𝑡

66

67