UNIVERZA V LJUBLJANI
FAKULTETA ZA MATEMATIKO IN FIZIKO Matematika – 2. stopnja
Tine Makovecki
SAMOKODIRNIK Z NAKLJUČNIM GOZDOM
Magistrsko delo
Mentor: prof. dr. Ljupčo Todorovski
Ljubljana, 2021
Zahvala
Zahvaljujem se mentorju, prof. dr. Ljupčotu Todorovskemu, za nasvete, ideje in pomoč pri ustvarjanju magistrskega dela.
Zahvala gre prijateljem za družbo in zabavo, ki je vse olajšala, posebej še dr. Žigi Lukšiču za dodaten pregled magistrskega dela in pogovore o vsebini.
Iz srca pa se zahvaljujem tudi družini in punci Juliji za podporo, skrb in moti- vacijo, brez katerih ne bi šlo.
Kazalo
Program dela vii
1 Uvod 1
2 Strojno učenje 2
2.1 Osnove . . . 2
2.1.1 Nadzorovano učenje . . . 2
2.1.2 Nenadzorovano učenje . . . 5
2.2 Učenje iz množic visoke razsežnosti . . . 6
2.2.1 Prekletstvo razsežnosti . . . 6
2.2.2 Manjšanje razsežnosti množic . . . 10
3 Samokodirnik, zgrajen iz nevronske mreže 11 3.1 Definicija in vrednotenje . . . 11
3.2 Usmerjene nevronske mreže . . . 12
3.3 Usmerjena nevronska mreža kot samokodirnik . . . 15
4 Samokodirnik, zgrajen iz naključnega gozda 16 4.1 Odločitveno drevo . . . 16
4.2 Naključni gozd . . . 17
4.3 Kodirnik . . . 19
4.4 Dekodirnik . . . 21
5 Implementacija samokodirnika z naključnim gozdom 25 5.1 Parametri . . . 26
5.2 Komponente . . . 27
5.3 Različice algoritma . . . 29
5.4 Možne izboljšave . . . 30
6 Vrednotenje implementacije samokodirnika 30 6.1 Metodologija . . . 30
6.2 Podatkovne množice . . . 31
6.3 Rezultati . . . 32
6.3.1 Testiranje parametrov . . . 32
6.3.2 Primerjava samokodirnikov . . . 34
7 Zaključek 35
Literatura 39
Program dela
Magistrska naloga naslavlja zmanjševanje razsežnosti podatkov, ki je zaradi "pre- kletstva razsežnosti"eden od ključnih problemov stojnega učenja [10]. S pojavom globokega učenja, so samokodirniki postali zelo razširjen in tako rekoč standar- den pristop k zmanjševanju razsežnosti podatkov [9]. Samokodirniki slonijo na po- sebni arhitekturi usmerjene nevronske mreže, ki omogoča eleganten prevod problema zmanjševanja razsežnosti podatkov v problem nadzorovanega strojnega učenja iz istih podatkov [2]. V okviru magistrske naloge je treba razviti samokodirnik, ki namesto usmerjene nevronske mreže uporablja metodo naključnega gozda. Naloga naj zastavi konceptualni okvir samokodirnika zasnovanega na naključnem gozdu, okvir implementira in ga ovrednoti na izbranih problemih zmanjševanja razsežnosti podatkov.
Osnovna literatura
[2] D. Charte in dr., A practical tutorial on autoencoders for nonlinear feature fusion: Taxonomy, models, software and guidelines, Information Fusion 44 (2018) 78–96, doi: 10.1016/j.inffus.2017.12.007
[9] I. Goodfellow, Y. Bengio in A. Courville, Deep Learning, Adaptive Computa- tion and Machine Learning series, MIT Press, 2016
[10] T. Hastie, R. Tibshirani in J. Friedman,The Elements of Statistical Learning:
Data Mining, Inference, and Prediction, Second Edition, Springer Series in Statistics, Springer New York, 2009
Podpis mentorja:
Samokodirnik z naključnim gozdom Povzetek
Na področju strojnega učenja se pogosto pojavljajo problemi z množicami viso- kih razsežnosti, ki pa so zaradi “prekletstva razsežnosti” zahtevni za reševanje. Pri reševanju takih problemov pogosto uporabljamo metode za manjšanje razsežnosti množic. Popularna metoda za manjšanje razsežnosti so samokodirniki, ki so pona- vadi zgrajeni iz nevronskih mrež. Slabost nevronskih mrež je, da zahtevajo veliko procesorskega časa in da ima uporabnik zaradi njihove kompleksnosti zelo slab vpo- gled v njihovo delovanje. Zato želimo v magistrskem delu razviti samokodirnik na osnovi naključnega gozda, ki teh slabosti ne bi imel. Za konstrukcijo samokodirnika iz naključnega gozda izberemo nabor listov, ki skupaj čim bolje opišejo podatkovno množico, in jih združimo v kodirni vektor. Samokodirnik nato primer zakodira na osnovi njegove pripadnosti listom konstruiranega kodirnega vektorja. Za postopek dekodiranja imamo na razpolago dve informaciji: poti v odločitvenih drevesih, ki vodijo do listov v kodirnem vektorju in shranjene napovedi naključnega gozda. Da poiščemo čim boljšo rekonstrukcijo zakodiranih primerov, uporabimo oba podatka.
Naš samokodirnik testiramo, da določimo čim boljše nastavitve parametrov, in nje- govo natančnost primerjamo s samokodirniki iz nevronskih mrež. Ugotovimo, da je zaenkrat manj natančen od standardnega pristopa, in premislimo možnosti, kako ga lahko v prihodnosti izboljšamo.
Autoencoder via random forest Abstract
In the field of machine learning, problems with high-dimensional data sets are common, and difficult to solve due to the “curse of dimensionality”. To solve these problems, we usually apply methods for dimensionality reduction. A popular me- thod for this are autoencoders, which are usually built with neural networks. Howe- ver, the downside of neural networks is high computation costs of training and their complexity which obscures the user insight into how they work. To address these issues, we aim at developing an autoencoder that is based on random forests and does not have such problems. To construct an autoencoder from a random forest, we select a set of forest leaves, which describe the data set well, and save them into an encoding vector. We use the encoding vector to encode data samples. There are two types of information we can use to decode the data: the decision tree paths leading to leaves in the encoding vector and the saved predictions from the random forest. We combine the two to get the best possible reconstruction of encoded data.
We test the constructed autoencoder to tune the parameter settings and evaluate its performance in comparison to neural network autoencoders. We establish that at this point our autoencoder is significantly less accurate compared to common autoencoders and consider the possibilities for upgrading it in the future.
Math. Subj. Class. (2010): 68T05, 68T27
Ključne besede: strojno učenje, manjšanje razsežnosti podatkov, samokodirniki, naključni gozdovi, umetne nevronske mreže
Keywords: machine learning, dimensionality reduction, autoencoders, random fo- rests, artificial neural networks
1 Uvod
Strojno učenje je področje umetne inteligence, posvečeno preučevanju algoritmov, ki izboljšujejo svoje delovanje skozi čas. Pogost izziv pri strojnem učenju je delo z množicami visokih razsežnosti, pri katerem pride do pojava, imenovanega “pre- kletstvo razsežnosti”. Rešujemo ga z manjšanjem razsežnosti množic ob čim manjši izgubi informacij. Ena izmed popularnih metod za manjšanje razsežnosti množic je uporaba samokodirnikov.
Samokodirnik je model, ki podatkovno množico preslika v prostor manjše razse- žnosti, nato pa jo ponovno preslika v prvotni prostor. Če je rekonstruirana množica dober približek prvotne množice, sklepamo, da vmesni prostor ohrani večino informa- cij v množici, in ga lahko uporabimo namesto prvotnega. Standardni samokodirniki so zgrajeni iz modela (usmerjene) nevronske mreže. Nevronske mreže, in posledično standardni samokodirniki, imajo nekaj velikih slabosti: so časovno neučinkovite, z vidika uporabnika so “črna škatla”, itd.
V magistrskem delu želimo konstruirati in implementirati samokodirnik, ki se bo izognil slabostim standardnega pristopa. Model naključnega gozda je dobra osnova, saj v splošnem dosega dobro natančnost, ima sorazmerno hiter postopek učenja in uporabniku omogoča jasen vpogled v delovanje.
Model naključnega gozda naučimo napovedovati vrednost svojih vhodnih spre- menljivk, na osnovi tega modela pa želimo zgraditi samokodirnik. Primeri, ki v odločitvenem drevesu iz gozda pripadajo istemu listu, so si v neki lastnosti podobni.
Primere lahko opišemo s pripadnostjo listom, zato želimo izbrati kodirni vektor naj- pomembnejših listov iz gozda, ki skupaj čim bolje opišejo množico. S tem kodirnim vektorjem zakodiramo primere iz podatkovne množice. Pri dekodiranju izkoristimo podatke o poteh do listov kodirnega vektorja in napovedi, ki jih drevesa v gozdu tem listom napovejo.
V poglavju 2 pregledamo osnove strojnega učenja in definiramo standardne pojme, ki jih uporabljamo v preostanku besedila. Najprej opišemo delitev na po- dročji nadzorovanega in nenadzorovanega učenja. Nato obravnavamo problematiko učenja iz podatkovnih množic visokih razsežnosti, kjer se pojavi problem t. i. “pre- kletstva razsežnosti” (ang. curse of dimensionality). Opišemo tudi glavni način so- očanja s to problematiko, tj. manjšanje razsežnosti (ang.dimensionality reduction), ki se mu posvetimo v preostanku magistrske naloge.
V poglavju 3 podrobno definiramo pojem samokodirnika ter na kakšen način ga vrednotimo. Definiramo model usmerjene nevronske mreže, njegovo uporabo ter prednosti in slabosti. Nato opišemo še najbolj razširjeno vrsto samokodirnikov, ki so zgrajeni iz nevronskih mrež, in nekaj različnih podvrst takšnih samokodirnikov.
V poglavju 4 konstruiramo samokodirnik na osnovi naključnega gozda. Naj- prej definiramo modela odločitvenega drevesa in naključnega gozda. Nato vpeljemo pojme kodirnega vektorja, pripadnosti primera listu in mero kvalitete/podobnosti listov, da lahko konstruiramo kodirnik. Pri konstrukciji dekodirnika predstavimo problem SAT in KNO formule. Utemeljimo, da je izziv pri dekodiranju predstavljen v obliki KNO formule in lahko zato pri reševanju uporabimo prirejen algoritem DPLL. Na koncu razdelka še opišemo postopek dekodiranja s pomočjo shranjenih napovedi in prirejenega algoritma DPLL.
Za implementacijo samokodirnika smo izbrali Python [17], pri obdelavi podatkov pa uporabimo tudi R [15]. V poglavju 5, ki je namenjeno implementaciji, opišemo knjižnice, ki smo jih uporabili, in najpomembnejše parametre samokodirnika. Pri- kažemo shemo delovanja implementacije in jo opišemo. Podrobneje predstavimo tudi komponente, iz katerih je samokodirnik sestavljen, in naredimo pregled po- membnejših funkcij. Nato opišemo še alternativne različice algoritma, ki smo jih implementirali, in možne izboljšave implementacije.
V poglavju 6 testiramo delovanje našega samokodirnika. Najprej opišemo meto- dologijo testiranja in predstavimo, na kakšen način generiramo množice za testiranje.
Pri testih se najprej posvetimo iskanju čim boljših privzetih vrednosti parametrov za naš samokodirnik. Nato izvedemo še teste za primerjavo našega samokodirnika s samokodirniki, zgrajenimi iz nevronskih mrež. Magistrsko delo zaključimo z opisom možnih izboljšav za naš samokodirnik.
2 Strojno učenje
2.1 Osnove
Strojno učenje je področje umetne inteligence, posvečeno preučevanju algoritmov, ki izboljšujejo svoje delovanje skozi čas [10]. Uporabljamo ga za avtomatizirano analizo podatkov, pri kateri algoritmi napovedujejo vrednosti izbranega podatkovnega ele- menta, iščejo vzorce v množicah podatkov ali pa prepoznavajo skupine medsebojno podobnih točk/primerov.
Definicija 2.1. Naj bodo D1, D2, . . . , Dp množice. Množico možnih primerov ω definiramo kot skalarni produkt:
ω =D1×D2× · · · ×Dp.
Podatkovno množico S definiramo kot podmnožico množice ω. Atribut Xi, ki ga pogosto imenujemo tudi spremenljivka, je projekcija Xi :ω→Di. Število atributov p imenujemo razsežnost podatkovne množice.
Metode strojnega učenja, ki se ukvarjajo z napovedovanjem vrednosti imenu- jemo metode za nadzorovano učenje (ang. supervised learning). Z uporabo prime- rov, shranjenih v podatkovni množici lahko namreč “nadzorujemo učenje” algoritma – ga prirejamo tako, da dosega čim boljše napovedi. Metode, ki se ne ukvarjajo z napovedovanjem vrednosti, uvrščamo na področje nenadzorovanega učenja (ang.un- supervised learning). Cilj pri nenadzorovanem učenju je poiskati vzorce v podatkih, npr. razpoznati množice medsebojno podobnih primerov ali pa kombinacije vredno- sti atributov, ki se pogosto ponavljajo.
Primeri uporabe strojnega učenja so napovedovanje vrednosti delnic, prepozna- vanje skupin podobnih artiklov v spletnih trgovinah ali podobnih skladb na straneh za poslušanje glasbe in prepoznavanje malignih tvorb v medicini.
2.1.1 Nadzorovano učenje
Nadzorovano učenje se ukvarja z napovedovanjem vrednosti izbranega atributa po- datkovne množice. Ker je atribut za napovedovanje vnaprej določen, lahko vredno-
timo natančnost algoritma tako, da na primerih napoved primerjamo z dejansko vrednostjo. Model prilagodimo tako, da napovedi postanejo bolj točne, in s tem nadzorujemo njegovo učenje. Primeri uporabe nadzorovanega učenja so ocenjeva- nje tveganja v financah, kjer model napove tveganje poslovnega podviga ali pa plačilno sposobnost osebe, priporočanje prilagojene vsebine in oglasov spletnemu uporabniku, napovedovanje vremenskih pojavov in prepoznavanje malignih tvorb pri pacientih v zdravstvu.
Definicija 2.2. Naj bo ω množica možnih primerov inS ⊆ωpodatkovna množica.
Naj bo z Y označen atribut, katerega vrednost želimo napovedati, DY pa njegova zaloga vrednosti. Imenujemo ga ciljna spremenljivka oz. izhodna spremenljivka.
Ostale atribute imenujemo napovedne spremenljivke oz. vhodne spremenljivke.
Ciljna spremenljivka ni nujno število, saj je lahkoDY poljubna množica. Posebej poudarimo, da je lahko DY večdimenzionalna – v tem primeru so vrednosti ciljne spremenljivke Y predstavljene z vektorjem. Spremenljivke bomo delili na dve vrsti glede na njihovo zalogo vrednosti.
Če velja DY ⊆ R in so vrednosti ciljne spremenljivke lahko realna števila, je Y numerična spremenljivka. Če pa jeDY neka diskretna množica, pravimo, da je ciljna spremenljivka Y diskretna spremenljivka. To je lahko podmnožica naravnih števil, množica barv ali pa množica različnih besed. Take množice lahko predstavimo s podmnožico naravnih števil, vendar lahko s tem med primeri ustvarimo “bližino”, ki v prvotni množici ni prisotna. Diskretne spremenljivke zato ponavadi obravnavamo z drugače kot numerične. Podrobnejša delitev spremenljivk in opis, kako različne vrste spremenljivk obravnavamo, se nahaja v [8, pogl. 10].
Predpostavimo, da so točke v podatkovni množici generirane kot rezultati neke preslikave F in so tako povezane med seboj. Pri napovedovanju želimo uporabiti vrednosti napovednih spremenljivk, da bi ocenili vrednost ciljne spremenljivke. Na tak način deluje algoritem, ki ga uporabimo za napovedovanje – podamo mu vek- tor vrednosti napovednih spremenljivk, algoritem pa vrne približek vrednosti ciljne spremenljivke. Cilj pri tem postopku je, da bi vektor, ki vsebuje vrednosti napove- dnih spremenljivk in z njimi izračunan približek vrednosti ciljne spremenljivke, čim bolje aproksimiral rezultat preslikaveF.
Definicija 2.3. Naj bo ω = D1×D2 × · · · ×Dp ×DY množica možnih primerov in S ⊆ ω podatkovna množica. Napovedni model m je funkcija, ki slika iz množice D1×. . .×Dp v množicoDY:
m:
p
∏︂
i=1
Di →DY.
Metoda strojnega učenja A je preslikava oblike:
A:P (︄(︄ p
∏︂
i=1
Di )︄
×DY )︄
→ (︄ p
∏︂
i=1
Di →DY )︄
.
Napovedni model je algoritem, ki ga uporabimo za napovedovanje vrednosti, kon- struiramo pa ga z metodo strojnega učenja. Metoda strojnega učenjaA podatkovni
množici priredi neki napovedni model. Za model, ki ga vrne metoda strojnega učenja pri podatkovni množici S, pravimo, da je bil naučen na podatkovni množici S. V nadaljevanju bomo podrobneje opisali, kako nadzorujemo metode strojnega učenja, da dobimo dober model. Naj bo (x1, . . . , xp, y) ∈ S točka iz podatkovne množice.
Model m vektorju izmerjenih vrednosti napovednih spremenljivk x = (x1, . . . , xp) priredi oceno vrednosti ciljne spremenljivke yˆ = m(x). Ker želimo, da je ocena vrednosti ciljne spremenljivke čim bližje dejanski vrednosti y, potrebujemo način vrednotenja razlike med oceno in izmerjeno vrednostjo.
Definicija 2.4. Funkcija izgube L : DY ×DY → R+ je preslikava, pri kateri za poljuben element y∈DY velja L(y, y) = 0.
Oglejmo si primer dveh različnih funkcij izgube.
Primer 2.5. Denimo, da je zaloga vrednosti ciljne spremenljivke DY = [−1,1] in je Y torej numerična spremenljivka. Kvadratna funkcija izgube (ang. square loss function) za elementa u, v ∈DY je definirana s sledečim predpisom:
L(u, v) = (u−v)2.
V primeru, ko je ciljna spremenljivka diskretna, razlika med dvema elementoma pogosto ni definirana, zato moramo funkcijo izgube osnovati na drugačen način. De- nimo, da je Y diskretna ciljna spremenljivka z zalogo vrednosti DY ={a, b, c, d, e}. Za u, v ∈DY lahko uporabimo funkcijo izgube:
L(u, v) =
{︄0 ; u=v 1 ; sicer .
Vrednost funkcije izgube je 0, če sta argumenta enaka, sicer pa 1. Pri taki definiciji funkcija upošteva zgolj to, ali sta dva elementa enaka.
Vemo torej, da vrednostL(yˆ, y)predstavlja napako napovedi modela, vendar za vrednotenje modela ne uporabimo zgolj enega podatka, temveč t. i. testno mno- žico podatkov. Za vsakega od podatkov izračunamo funkcijo izgube, in dobljene vrednosti združimo v oceno napake.
Definicija 2.6. Naj boS ⊆ωpodatkovna množica, kjer jeω =D1× · · · ×Dp×DY množica možnih primerov. Naj bo L : DY ×DY → R+ funkcija izgube in m :
∏︁p
i=1Di →DY napovedni model. Funkcijo napakeErr : (∏︁p
i=1Di →DY)×P(ω)→ R+ definiramo s predpisom:
Err(m, S) = 1
|S|
∑︂
(x,y)∈S
L(m(x), y).
Funkcija napake kot argumenta prejme modelm in podatkovno množicoS ⊆ω. Argumentoma priredi povprečno vrednost funkcije izgube za model m na primerih iz množice S. Vrednost funkcije napake imenujemo napaka modelamna množiciS. Spomnimo se definicije metode strojnega učenja iz definicije 2.3. Določiti želimo metodo, s katero bi lahko poiskali dober model. Denimo, da imamo podano množico
podatkov, ki jo želimo uporabiti, da zgradimo model, ki bo čim bolje napovedoval vrednosti ciljne spremenljivke. Pri postopku izgradnje modela kot vodilo uporabimo funkcijo napake. Metoda začne z osnovno obliko modela in ga prilagaja s ciljem, da minimizira funkcijo napake modela na podatkovni množici. Podrobnosti metode strojnega učenja so zelo odvisne od vrste napovednega modela, zato obstaja mnogo različnih postopkov, ki jih ne moremo združiti v eno enotno metodo.
Za vrednotenje delovanja modela podatkovno množico razdelimo na dva dela – na učno in testno množico. Pri učenju se lahko model namreč pretirano prilagodi učni množici, kar pomeni, da bo pri novih primerih dosegal mnogo manjšo natančnost kot pri primerih iz učne množice. Zato del primerov iz podatkovne množice izključimo iz učne množice, da lahko testiramo natančnost modela na primerih, ki jih v postopku učenja ni “videl”. Iz primerjave natančnosti na učni in testni množici lahko sklepamo, ali je model morda preveč prilagojen učni množici oziroma ali so njegove napovedi splošno veljavne.
2.1.2 Nenadzorovano učenje
Nenadzorovano učenje se od nadzorovanega razlikuje predvsem v tem, da problemi nimajo ciljne spremenljivke. Množica možnih primerov pri nenadzorovanem učenju je torej ω =D1 × · · · ×Dp. Cilj nenadzorovanega učenja je z algoritmom pridobiti vpogled v podatke, zanimajo nas lahko na primer vzorci v množici, korelacija med primeri, osamelci itd. Pri nadzorovanem učenju problem, ki ga rešujemo, praviloma zastavijo eksperti s področja, s katerega izvirajo podatki, vendar lahko analizo z napovednim modelom izvedemo brez predznanja o ozadju podatkov. V primerjavi s tem pri nenadzorovanem učenju ponavadi ni vnaprej zastavljene naloge, potrebu- jemo zgolj množico podatkov, zato pa je znanje strokovnjaka toliko bolj potrebno pri interpretaciji rezultatov nenadzorovanega učenja.
Pogosta primera sta analiza glavnih komponent (ang. principal component ana- lysis, krajše PCA), ki poišče glavne značilnosti množice, in razvrščanje v skupine (ang. clustering), kjer se množico razdeli na podmnožice med seboj podobnih pri- merov. Nenadzorovano učenje se med drugim uporablja za prepoznavanje podobnih skupin uporabnikov na spletu (npr. v namen oglaševanja), za ocenjevanje glavnih lastnosti finančnega portfelja in za grupiranje spletne vsebine v med seboj podobne skupine, s čimer se lahko uporabniku predlaga povezane artikle.
Pod nenadzorovano učenje spada mnogo pristopov in algoritmov, ki obdelajo množico podatkov in vrnejo rezultat v veliko različnih možnih oblikah. Skupna de- finicija, ki bi opisala vse te postopke, bi bila okorna in preveč splošna, da bi bila uporabna. Namesto tega si bomo raje podrobno ogledali primer postopka razvršča- nja k-voditeljev (ang. k-means clustering), ki spada med metode nenadzorovanega učenja.
Primer 2.7. Naj bo S ⊆ ω podatkovna množica razsežnosti p. Cilj algoritma je elemente množice razvrstiti v k skupin med seboj podobnih elementov. Da lahko postopek izvedemo, morajo biti točke iz podatkovne množice vstavljene v evklidski prostor.
V prostoru naključno izberemo k točk µ1, µ2, . . . , µk. Nato za vsako točko x v podatkovni množici S izračunamo, kateri točki µi leži najbližje. Če x leži najbližje
točki µi, pravimo, da pripada i-ti skupini. Po tem, ko so vse točke razvrščene v skupine, izračunamo nove vrednosti µ1, . . . , µk tako, da za i = 1, . . . , k določimo µi kot povprečje vseh elementov i-te skupine. Nato vse točke množice S ponovno razvrstimo v skupine glede na novo izračunane vrednosti µ1, . . . , µk. Ta postopek nadaljujemo, dokler rezultat ne konvergira.
Slabost takega pristopa je, da zaradi preprostosti ne zajame veliko nians podat- kovne množice. Glede na različne začetne vrednosti µ1, . . . , µk je možno primere razdeliti na več različnih, veljavnih, skupin primerov. Posamezna delitev je lahko pravilna, vendar morda ne prepozna tistih podobnosti, ki smo jih želeli.
Obstaja še precej drugih postopkov in algoritmov, ki spadajo v to vejo strojnega učenja. Metode nenadzorovanega učenja se prav tako uporabljajo tudi pri manjšanju razsežnosti množic. To je pogost izziv strojnega učenja, saj se pri množicah visokih razsežnosti pojavijo ovire, ki jih lahko odpravimo z manjšanjem razsežnosti množice, kar opišemo v naslednjem poglavju.
2.2 Učenje iz množic visoke razsežnosti
Pri večini problemov, za katere se v praksi uporablja strojno učenje, se srečamo z množicami visokih razsežnosti. Pri množicah podatkov s področij financ, medicine, satelitskih posnetkov itd. je število spremenljivk lahko zelo veliko. V tem razdelku bomo podrobno opisali izzive, s katerimi se soočamo pri množicah visoke razsežnosti.
Še posebej se bomo posvetili t. i. prekletstvu razsežnosti, nato pa bomo predstavili še nekaj standardnih pristopov za manjšanje razsežnosti množic.
Množice visokih razsežnosti pri obdelavi potrebujejo veliko pomnilnika in ogro- mno procesorskega časa. Že zaradi omejenih računalniških zmogljivosti je zato pogo- sto potrebno zmanjševanje razsežnosti. Izkaže pa se, da imajo take množice nekatere lastnosti, zaradi katerih je obdelava še posebej težavna, npr. to, da so elementi mno- žice z večanjem razsežnosti med seboj vse bolj oddaljeni. Te lastnosti s skupnim imenom imenujemo prekletstvo razsežnosti [1].
2.2.1 Prekletstvo razsežnosti
Pri večanju razsežnosti prostora se na nek način spremeni položaj elementov v pro- storu. Izkaže se, da so ob večanju razsežnosti primeri vse bolj zbrani blizu roba prostora, saj se njihova razdalja do koordinatnega izhodišča veča (trditev 2.9). Prav tako se veča tudi povprečna razdalja med elementi. S tem, ko se razdalje med ele- menti večajo, potrebujemo tudi vse večje število primerov, če želimo ohraniti enako gosto porazdelitev primerov, kjer se število potrebnih primerov eksponentno veča.
V praksi to pomeni, da pri bolj zahtevnih problemih ne moremo ohraniti enako gostega vzorca.
V nadaljevanju bomo predpostavke nekoliko poenostavili, da bo izpeljava bolj preprosta. Prostor možnih primerov s p dimenzijami pri strojnem učenju pogosto prevedemo v obliko [−1,1]d, kjer se spremenljivke normira za lažjo obdelavo. Doda- tno se bomo omejili na primere znotraj p dimenzionalne enotske krogle. Ta primer bo za naš namen zadoščal, saj obnašanje primerov znotraj krogle nakaže obnašanje primerov v celem prostoru.
Definicija 2.8. Naj bodo X1, X2, . . . , Xn zvezno porazdeljene slučajne spremen- ljivke. Naj bodoY1, Y2, . . . , Yn slučajne spremenljivke, ki jih dobimo, če X1, . . . , Xn uredimo po velikosti, kjerY1 predstavlja najmanjšo izmed Xi,Y2 predstavlja drugo najmanjšo, itd. Za i = 1, . . . , n imenujemo Yi statistika i-tega ranga naključnega vzorca X1, . . . , Xn.
Trditev 2.9. V enotski krogli v prostoruRp enakomerno naključno izberemon točk.
Naj slučajna spremenljivka Ri označuje oddaljenosti-te točke od izhodišča in naj bo Y statistika prvega ranga naključnega vzorca R1, . . . , Rn. Mediana slučajne spre- menljivke Y je:
d(p, n) = (1− 1 2n1)1p.
Dokaz. Volumen krogle s polmerom r v prostoru Rp je [5, enačba 5.19.4]:
rp πp2
Γ(p2 + 1), (2.1)
kjer Γ označuje funkcijo gama [5, enačba 5.4.1].
Naj bo x ∈ (0,1) neko pozitivno število. Zanima nas verjetnost, da je enako- merno naključno izbrana točka od izhodišča oddaljena za x ali manj, oz. da velja Ri ≤ x. To velja v primeru, ko se točka nahaja v krogli Bx s centrom v izhodišču in polmerom x. Ker je bila točka enakomerno naključno izbrana v enotski krogli, je verjetnost, da se nahaja znotraj krogle Bx, enaka razmerju volumna krogle Bx in enotske krogle. Zapišimo kumulativno porazdelitveno funkcijo tega dogodka z uporabo formule 2.1 za volumen krogle v imenovalcu in števcu.
FRi(x) = P(Ri ≤x) = xp(︂
πp2 Γ(p2+1)
)︂
1p(︂
πp2 Γ(p2+1)
)︂ = xp 1 =xp.
Če upoštevamo, da je vrednost Ri nenegativna, dobimo predpis:
FRi(x) =P(Ri ≤x) =
{︄xp ; x≥0
0 ; sicer. (2.2)
Skrajšan zapis kumulativne porazdelitvene funkcije 2.2 nato odvajamo, da dobimo gostoto porazdelitve:
fRi(x) =FR′
i(x) =
{︄pxp−1 ; x≥0
0 ; sicer. (2.3)
Gostoto porazdelitve statistike prvega ranga [11, pogl. 4.6] opiše formula:
fY(y) = n(1−FRi(y))n−1fRi(y).
V to formula vstavimo zvezi 2.2 in 2.3, da dobimo:
fY(y) =
{︄n(1−yp)n−1pyp−1 ; y≥0
0 ; sicer. (2.4)
Gostoto porazdelitve fY integriramo na intervalu (−∞, x], da dobimo kumulativno porazdelitveno funkcijo. Ker je vrednost fY pri negativnih argumentih enaka 0, lahko interval integracije skrčimo na nenegativne vrednosti [0, x].
FY(x) =
∫︂ x
0
n(1−yp)n−1pyp−1dy
=
∫︂ xp
0
n(1−z)n−1dz
=−(1−z)n
⃓
⃓
⃓
xp
0
= 1−(1−xp)n
Da zaključimo dokaz trditve, moramo izračunati vrednost mediane za slučajno spre- menljivko Y. Vemo, da bo vrednost x0 mediana, če velja P(Y ≤x0) =P(Y ≥0) =
1
2. To pa velja za argument, za katerega velja zvezaFY(x0) = 12. V to zvezo vstavimo predpis kumulativne porazdelitvene funkcije in poračunamo vrednost argumenta.
1−(1−xp0)n = 1 2 (1−xp0)n = 1 2 1−xp0 = 1
21n x0 = (1− 1
2n1)1p
Oglejmo si formulo iz trditve 2.9. Z večanjem števila točknse mediana vrednosti slučajne spremenljivke Y manjša, torej se manjša pričakovana oddaljenost izhodišču najbližje točke. Z večanjem dimenzije p pa se mediana veča in narašča proti 1, oddaljenost najbližje točke pa se povečuje. Spomnimo se, da je Y statistika prvega reda naključnega vzorcaR1, . . . , Rn, kar pomeni, da predstavlja razdaljo od izhodišča do najbližje točke iz vzorca. Denimo, da (enakomerno) naključno izberemo vzorec n točk v prostoru visoke razsežnosti. Če je razsežnost prostora dovolj velika, bo celo točka, ki je izhodišču najbližja, verjetno ležala bližje robu prostora kot izhodišču.
Tudi v primeru, ko je število točk v vzorcu (n) zelo veliko, to drži, dokler je razsežnost prostora dovolj velika.
Pokazali smo, da so primeri vse bolj zbrani ob robu prostora, ko se veča razsežnost prostora. Opazimo, da bi lahko v dokazu namesto koordinatnega izhodišča izbrali drugo poljubno točko in z analognim razmislekom pokazali podobno lastnost.
Naj bo x1 točka iz množice n v enotski krogli enakomerno naključno izbranih točk. Zanima nas, koliko bodo od x1 oddaljene ostale točke. Za i= 2,3, . . . , n z R′i označimo slučajno spremenljivke, ki predstavlja razdaljo i-te točke iz vzorca do x1. Naj bo r∈(0,1)neko pozitivno število. VrednostRi′ je manjša ali enaka r natanko tedaj, ko se i-ta točka nahaja v krogli Br(x1)s središčem x1 in polmerom r.
Ta situacija je zelo podobna tisti v dokazu trditve 2.9, vendar kroglaBr(x1)nima središča v izhodišču in možno je, da prvotna enotska krogla ne vsebuje celotne krogle
Br(x1). Zato moramo obravnavati dva primera v odvisnosti od položaja krogle. Če enotska krogla vsebuje celotno kroglo Br(x1), lahko verjetnost P(Y′ ≤ r) tako kot v dokazu trditve 2.9 opišemo z razmerjem volumna dveh krogel.
Če enotski krogli s središčem v izhodišču ne vsebuje celotne krogle Br(x1), pa moramo znova premisliti, kakšna je verjetnost dogodkaR′i ≤r. Zveza R′i ≤r velja, če je točka, ki smo jo enakomerno naključni izbrali v enotski krogli, vsebovana v krogli Br(x1). Točka pa je izbrana znotraj enotske krogle, torej ne more ležati v delu Br(x1), ki ga enotska krogla ne vsebuje. Zveza R′i ≤r torej velja, če točka leži v presekuBr(x1)in enotske krogle, ta presek pa ima manjši volumen kot Br(x1). V tem primeru za verjetnost velja neenakost:
FR′
i(r) =P(R′i ≤r)≤ rp(︂
πp2 Γ(p2+1)
)︂
1p(︂
π
p 2
Γ(p2+1)
)︂ (2.5)
V obeh primerih je torej porazdelitvena funkcija spremenljivke R′i manjša ali enaka porazdelitveni funkciji iz dokaza. To pomeni, da je verjetnost, da je i-ta iz- brana točka od x1 oddaljena manj kot r, manjša od verjetnosti, da je taista točka manj kot r oddaljena od izhodišča. To velja za poljubni r ∈ (0,1) in poljubni i ∈ {2, . . . , n}, torej za vse izbrane točke velja, da so od x1 verjetno oddaljene vsaj toliko kot od izhodišča. Iz tega sklepamo, da je statistika prvega ranga slu- čajnih spremenljivk R′2. . . , R′n večja ali enaka statistiki prvega ranga spremenljivk R2, . . . , Rn, ki je po trditvi 2.9 enaka (1− 1
2n−11
)1p.
Premislili smo, da se razdalja od x1 do najbližje druge izbrane točke veča z razsežnostjo prostora. Podoben razmislek pa velja za poljubno točko v množici, torej se razdalja med vsemi točkami iz nabora izbranih točk z razsežnostjo povečuje.
Slika 1: Graf prikazuje vrednost statistike prvega ranga oz. mediano oddaljenosti od izhodišča pri n= 500.
Primer 2.10. Ogledali si bomo vrednosti mediane iz trditve pri dveh različnih fiksnih vrednostih n, da opazujemo, kako se razdalja spreminja glede na razsežnost
prostora. Najprej fiksiramo vrednostn= 500in si ogledamo graf vrednosti statistike prvega ranga slučajnih spremenljivk R!, . . . , R500 v odvisnosti od razsežnosti. Na sliki 1 vidimo, da vrednost preseže 0,5 pri razsežnosti p = 10, saj za mediano razdalje med izhodiščem in najbližjo naključno izbrano točko v tem primeru velja:
d(10,500)≈0,5178.
Slika 2: Graf prikazuje vrednost statistike prvega ranga oz. mediano oddaljenosti od izhodišča pri n = 50000.
Torej je celo najbližja točka verjetno bližje robu prostora kot izhodišču. Kot smo povedali v razmisleku pred primerom, se analogno povečuje tudi razdalja med točkami. Poglejmo si še primer s številom naključno izbranih točk n = 50000, ki je prikazan na sliki 2. Opazimo, da vrednost mediane preseže 0,5 pri razsežnosti p= 17, kjer velja:
d(17,50000)≈0,5179.
Vidimo, da pri velikem povečanju števila izbranih točk zadošča sorazmerno majhno povečanje razsežnosti, da se vse točke spet zberejo bližje robu prostora. Podobno pa se z večanjem razsežnosti zelo hitro veča tudi razdalja med izbranimi točkami.
S to težavo se soočamo tako, da manjšamo število dimenzij ob čim manjši izgubi informacij.
2.2.2 Manjšanje razsežnosti množic
Zaradi težav z množicami visokih razsežnosti uporabljamo metode za manjšanje razsežnosti množic za boljše delovanje algoritmov strojnega učenja. Pri večini metod za manjšanje razsežnosti domnevamo, da se množica podatkov v prostoru visoke razsežnosti nahaja na oz. blizu neke mnogoterosti manjše razsežnosti, ki se nahaja v prostoru. Elemente množice podatkov nato obravnavamo v tem podprostoru manjše razsežnosti.
Obstaja veliko različnih pristopov za linearno manjšanje razsežnosti, pri katerih se množico podatkov z linearno preslikavo preslika v manj razsežen prostor. Pri
tem želimo, da je predstavitev v manjši razsežnosti optimalna glede na neko merilo, npr. da dosega najmanjšo rekonstrukcijsko napako ali da ima preslikana množica čim večjo varianco. Nekatere znane metode za linearno manjšanje razsežnosti so analiza glavnih komponent (ang.principal component analysis, krajše PCA), analiza kanonične korelacije (ang. canonical correlations analysis, krajše CCA), linearna regresija, analiza faktorjev (ang. factor analysis). Obstajajo pa tudi raziskave, ki stremijo k združitvi in posplošitvi različnih metod linearnega manjšanja razsežnosti.
Pregled in primerjavo različnih pristopov lahko bralec najde v članku [4].
Obstajajo tudi metode za nelinearno manjšanje razsežnosti, ki so pogosto nad- gradnja nekaterih metod za linearno manjšanje razsežnosti. Omogočajo bolj kom- pleksno preslikavo v množico manjše razsežnosti, nekatere izmed teh metod pa so npr. Sammonova projekcija, jedrska analiza glavnih komponent (ang.kernel princi- pal component analysis, krajše kernel PCA) in pa samokodirniki [2], ki so ena izmed najbolj razširjenih in uspešnih metod za manjšanje razsežnosti. V preostanku dela se bomo osredotočili na samokodirnike.
3 Samokodirnik, zgrajen iz nevronske mreže
Samokodirniki so ena izmed najbolj razširjenih in zmogljivih metod za manjšanje razsežnosti podatkovnih množic [2, 9]. V tem poglavju bomo formalno definirali pojem samokodirnika in predstavili standardne samokodirnike, ki so sestavljeni iz usmerjenih nevronskih mrež. Zato bomo tudi formalno definirali model usmerjene nevronske mreže in opisali prednosti in slabosti njihove uporabe. Pregledali bomo še najpogostejše vrste samokodirnikov in v katerem primeru jih je dobro uporabiti.
Večina samokodirnikov ima slabosti, ki jih imajo nevronske mreže, npr. počasen postopek učenja in slab vpogled v delovanje – z vidika uporabnika so namreč “črna škatla”. Zato bomo v naslednjem poglavju nadaljevali s konstrukcijo drugačnega samokodirnika, ki bi to izboljšal.
3.1 Definicija in vrednotenje
Definicija 3.1. Naj bo ωp podatkovna množica razsežnostip. Naj bosta me :ωp → ωkinmd :ωk →ωp modela, kjer jeωk množica razsežnostik, ki jo imenujemozaloga vrednosti kode. Samokodirnik je kompozitum modelov s sledečim predpisom:
msk =md◦me :ωp →ωp.
Podatkovna množica S za učenje samokodirnika je oblike S = {(v, v), v ∈ ωp} ⊆ ωp×ωp. Model me imenujemo kodirnik, model md pa dekodirnik.
Samokodirnik je kompozitum dveh modelov, ki napoveduje lastne vhodne spre- menljivke. Njegovemu delovanju dodamo še določene omejitve ali parametre, da preslikava, ki jo izvede, ne more biti identiteta. Želimo, da bi s transformacijo vho- dnih spremenljivk in njihovo rekonstrukcijo samokodirnik ujel pomembnejše lastno- sti podatkovne množice. Rekonstruirani podatki nas razen za vrednotenje delovanja ne zanimajo – zanimajo nas transformirani podatki (običajno nižje razsežnosti) v vmesni fazi, iz katerih se da prvotno množico dobro rekonstruirati.
Samokodirnike vrednotimo glede na povprečno vrednost funkcije izgube L, ki ji v tem primeru pravimo rekonstrukcijska napaka. Funkcija izgube je določena glede na vrsto podatkovne množice, učenje samokodirnika pa standardno poteka z mini- mizacijo vrednosti funkcije izgube L(x, md(me(x))) na elementih učne podatkovne množice S. Samokodirnik se uči z enim algoritmom, kodirnik in dekodirnik pa nato razberemo iz samokodirnika. Kodirnika in dekodirnika torej ne učimo ločeno.
Rekonstrukcijska napaka bi bila najmanjša v primeru, ko za vsak x ∈ ωp velja x=md(me(x)). To lahko vedno dosežemo s trivialno rešitvijome =md=id, vendar s tem ne izvemo o množici ničesar novega. Da bi se izognili trivialni rešitvi, ponavadi določimo omejitve za vmesno množico, ki to preprečijo. Najpogostejši pogoj je, da omejimo razsežnost k vmesne množice ωk. Samokodirnik, pri katerem je množica ωk manjše razsežnosti kot množicaωp, imenujemo nepopolni samokodirnik. Upamo, da bodo izhodne spremenljivke kodirnika, ki omogočajo dobro rekonstrukcijo, do- bro opisale glavne lastnosti podatkovne množice. V nadaljevanju se osredotočimo predvsem na nepopolne samokodirnike, vendar obstajajo tudi druge možne omejitve.
Nekaj različic omenimo v kasnejšem razdelku, pred tem pa želimo opisati standardni samokodirnik, ki je sestavljen iz nevronskih mrež.
3.2 Usmerjene nevronske mreže
Usmerjene nevronske mreže so sestavljene iz gradnikov imenovanih nevroni, ki jih s sinapsami povežemo v večjo strukturo [13]. Skupine nevronov imenujemo plasti, mreža pa je sestavljena iz vsaj dveh plasti. Posamezen nevron preko sinaps prejme vrednosti od vseh nevronov v prejšnji plasti, jih združi v eno vrednost z aktivacijsko funkcijo in to vrednost posreduje vsem nevronom v naslednji plasti. Usmerjena nevronska mreža kot napoved vrne vrednosti, ki jih izračunajo nevroni v zadnji plasti. Z nevronskimi mrežami lahko dobro napovedujemo kompleksne množice podatkov, zahtevajo pa več procesorske moči kot večina modelov. Uporablja se jih na področjih kot so finančni trgi, medicinsko skeniranje in prepoznavanje pisave ter govora.
Definicija 3.2. Aktivacijska funkcija α : R → R je funkcija na množici realnih števil. Naj bo k ∈ N neko naravno število, b ∈ R neko realno število in naj bo w = (w1, . . . , wk)∈Rk vektor uteži. Funkcijo f : [0,1]k →[0,1] s predpisom oblike f(x) =α(w·x+b) imenujemo nevron, konstanto b pa imenujemo pristranskost.
Uporablja se lahko različne aktivacijske funkcije, najpogostejša pa je sigmoidna funkcijaσ(y) = 1+e1−y. Nevronu s sigmoidno aktivacijsko funkcijo pravimosigmoidni nevron. Če σ vstavimo v definicijo nevrona 3.2, dobimo za nevron fσ predpis:
fσ(x) = 1
1 +e−∑︁ki=1wixi−b.
Povedali smo že, da je usmerjena nevronska mreža sestavljena iz nevronov, ki si med seboj posredujejo vrednosti skozi sinapse, moramo pa še formalno opisati, na kakšen način so nevroni povezani.
Definicija 3.3. Arhitektura usmerjene nevronske mreže Np1,p2,...,pl je usmerjen graf, v katerem vsako vozlišče predstavlja nevron. Vsebuje n = p1 +p2 +· · ·+pl voz- lišč, ki so razdeljena v l neodvisnih, med seboj disjunktnih, množicN1, N2, . . . , Nl. Povezave v grafu definiramo s predpisom, da zai= 1,2, . . . , l−1 velja:
∀v ∈Ni,∀w∈Ni+1, v∼w.
Množici N1 pravimo vhodna plast, množici Nl pa izhodna plast.
izhodna plast vhodna plast
Slika 3: Simbolična slika arhitekture usmerjene nevronske mreže.
V arhitekturi usmerjene nevronske mreže je torej vsako vozlišče povezano z vsemi vozlišči iz predhodne in sledeče plasti. Na sliki 3 je prikazan primer arhitekture usmerjene nevronske mreže Arhitektura opiše strukturo mreže, definirati pa mo- ramo, kako deluje nevronska mreža z določeno arhitekturo.
Definicija 3.4. Naj boNq1,q2,...,ql arhitektura usmerjene nevronske mreže. Pravimo, da arhitekturaNq1,q2,...,ql opiše model m:D1× · · · ×Dp →DY, če vsakemu vozlišču arhitekture pripada en nevron in veljajo sledeča pravila:
1. q1 =p
2. ql=dim(DY), kjer dim(DY) označuje razsežnost množice DY.
3. Za vse nevrone fi ∈N1 velja, da imajo domeno razsežnostip, njihova aktiva- cijska funkcija je identična preslikava, njihova pristranskost je enaka 0, njihov vektor uteži pa je Ii, ki je vektor z vrednostjo 1 na i-tem mestu in 0 na vseh ostalih mestih.
fi ∈N1 ⇒fi(x1, . . . , xp) = id(Ii·(x1, . . . , xp) +b) = id(xi + 0) =xi
4. Za j = 2, . . . , l za vsak nevronfi ∈Nj velja, da ima domeno razsežnosti qj−1
5. Slika modela m je definirana s predpisom m(x) = network_predict(x).
Algorithm 1 Algoritemnetwork_predict napovedovanja nevronske mreže Vhod: arhitektura nevronske mreže Nq1,q2,...,ql, primer x iz podatkovne množice
Izhod: napoved yˆ, ki je približek vrednosti ciljne spremenljivke for fi ∈N1 do
y
ˆi ←fi(x) end for
for j = 2, . . . , l do
former_layer_results ←(yˆ1, . . . , yˆpj−1) for fi ∈Nj do
y
ˆi ←fi(former_layer_results) end for
end for
return(yˆ1, . . . , yˆp
l)
Usmerjena nevronska mreža je modelm :D1× · · · ×Dp →DY, ki ga opiše neka arhitektura nevronske mreže, katere vhodna plast je sestavljena iz p elementov, izhodna plast pa iz dim(DY) elementov.
Definicija 3.4 vsebuje seznam različnih pogojev, ki določajo, kakšna arhitektura opiše usmerjeno nevronsko mrežo. Za lažje razumevanje definicije lahko pogoje za- pišemo tudi v manj formalni obliki. S prvima dvema pogojema zahtevamo, da je velikost vhodne plasti enaka številu vhodnih spremenljivk in velikost izhodne plasti enaka razsežnosti ciljne spremenljivke podatkovne množice. S pogojem 3 določimo lastnosti nevronov vhodne plasti, ki skupaj pomenijo, da bodo nevroni vhodne plasti lahko sprejeli vrednosti vhodnih spremenljivk in jih naprej poslali nespremenjene.
V pogoju 4 zahtevamo, da nevroni vseh ostalih plasti sprejmejo število vrednosti, ki je enako velikosti predhodne plasti. Z zadnjim pogojem definiramo, kako model nevronske mreže (z določeno arhitekturo) izračuna napoved. Nevroni vhodne plasti sprejmejo vrednosti vhodnih spremenljivk, ki jih nato podamo kot argument nevro- nom naslednje plasti, rezultat, ki ga izračunajo, pa je argument nevronov naslednje plasti itd. Vrednosti, ki jih izračunajo nevroni izhodne plasti, so napoved modela.
Omenimo še, da so uteži aktivacijskih funkcij shranjene v povezavah, tj. v si- napsah nevronske mreže. Če je nevronska mreža sestavljena iz sigmoidnih nevronov oz. nevronov z dovolj “lepimi” aktivacijskimi funkcijami, ima lepe lastnosti za učenje.
Če parametre mreže, tj. uteži in pristranskost, minimalno spremenimo, se minimalno spremeni tudi izhodna vrednost spremeni. To velja, ker je nevron zvezen kot funkcija uteži in pristranskosti in je velikost spremembe izhodne vrednosti linearno odvisna od velikosti sprememb uteži in pristranskosti [13, pogl. 1].
Parametre nevronske mreže lahko popravljamo, s čimer postaja rezultat pri iz- branem argumentu bolj točen, s tem pa točnosti napovedi pri drugih argumentih ne pokvarimo preveč. Algoritem torej prilagaja uteži in pristranskost nevronov v mreži, dokler ni razlika med napovedjo in resničnim rezultatom čim manjša. Pri učenju usmerjenih nevronskih mrež za optimizacijo uporabimo gradientni spust [13, pogl.
1]. Računanje gradienta funkcije izgube, ki ga algoritem potrebuje, pa je za nevron- ske mreže zelo zamudno, zato uporabimo postopek vzvratnega razširjanja napake
(ang. backpropagation), ki je bolj učinkovit od direktnega izračuna. Bolj podroben opis nevronskih mrež in postopka, s katerim jih učimo, lahko bralec najde v delu [13, pogl. 2].
Prednosti uporabe nevronskih mrež so, da lahko uspešno dosežejo visok nivo abstrakcije – npr. pri prepoznavanju obrazov, avtomatiziranem branju rokopisa in razpoznavanju govora. Dobro se odrežejo pri kompleksnih podatkovnih množicah z velikim številom vhodnih spremenljivk. Slabost uporabe usmerjenih nevronskih mrež je zamuden postopek učenja in slab vpogled v delovanje končnega modela.
Model je namreč sestavljen iz nabora med seboj poveznih funkcij in zato že pri sorazmerno preprosti arhitekturi težko sledimo dogajanju znotraj mreže.
3.3 Usmerjena nevronska mreža kot samokodirnik
Najpogostejša implementacija samokodirnika je usmerjena nevronska mreža sesta- vljena iz treh ali več plasti. Ključne plasti so vhodna plast, koda in izhodna plast.
Vključuje pa lahko tudi vmesne plasti, ki povečujejo kompleksnost kodiranja. Ko- dirnik in dekodirnik dobimo z izbiro primernih plasti te mreže. Kodirnik vsebuje vhodno plast, kodo ter vmesne plasti med njima, dekodirnik pa vsebuje kodo in izhodno plast ter vmesne plasti. Vhodna in izhodna plast vsebujeta enako število nevronov, razsežnost kode pa je lahko različna. Struktura samokodirnika je prika- zana na sliki 4.
X h X’
koda
vho dna plast izho dna plast
kodirnik
dekodirnik
Slika 4: Shema, ki prikazuje strukturo samokodirnika in kodirnik ter dekodirnik.
Pri nepopolnih samokodirnikih koda vsebuje manj nevronov kot vhodna in iz- hodna plast. Če jih vsebuje več kot vhodna plast, pa rečemo, da je samokodirnik nadpopoln. V tem primeru je možna identična preslikava, ki je ne želimo, zato se taki samokodirniki uporabljajo samo v posebnih primerih. Če kodirnik in dekodirnik ne vsebujeta skritih plasti, je samokodirnikplitev, v nasprotnem primeru pa globok.
Poznamo tudi druge vrste samokodirnikov, pri katerih so prisotne drugačne ome- jitve kot pri nepopolnih. Pri nadpopolnih samokodirnik se lahko omeji število ne- ničelnih elementov v zakodiranih podatkih – zahtevamo, da je srednja plast redka (ang. sparse). Poznamo tudi samokodirnike za odstranjevanje šuma, pri katerih
vhodnim podatkom dodamo šum, da onemogočimo identične preslikave, ne da bi omejili razsežnost kodirne plasti.
4 Samokodirnik, zgrajen iz naključnega gozda
V tem poglavju bomo uvedli nov koncept samokodirnika, ki bo alternativa stan- dardnemu pristopu. Z našo različico samokodirnika želimo odpraviti slabosti večine samokodirnikov. Cilj je kodiranje, ki uporabniku omogoča razumevanje zakodiranih podatkov, kodirni postopek z vpogledom v delovanje in hitrejše procesiranje. Samo- kodirnik je zgrajen na osnovi metode naključnega gozda, ki je nadgradnja modela odločitvenih dreves. V prvem podrazdelku bomo predstavili modele odločitvenih dreves, v drugem pa model naključnega gozda. V nadaljnjih podrazdelkih bomo predstavili postopek kodiranja in dekodiranja na osnovi naključnega gozda ter la- stnosti in prednosti takšnega pristopa.
4.1 Odločitveno drevo
Odločitveno drevo je dvojiško drevo, ki v notranjih vozliščih vsebuje logične pogoje, ki določajo, v kateri list razvrstimo primer, v listih pa vsebuje napovedi vrednosti za pripadajoče primere. Napoved je matematično gledano zlepek konstantnih funkcij.
Njihovo učenje zahteva zelo malo procesorskega časa, njihova struktura pa je razu- mljiva za uporabnika, zato služijo kot dobro izhodišče za izgradnjo samokodirnika.
Definicija 4.1. Odločitveno drevo je model, katerega delovanje opiše graf dvoji- škega drevesa. Notranja vozlišča drevesa vsebujejo oznako spremenljivke in mejno vrednost, listi pa vsebujejo napovedi, v katere model preslika primere. Postopek, s katerim odločitveno drevo določi napoved, je opisan v algoritmu 2.
Algorithm 2 Algoritem napovedovanja odločitvenega drevesa Vhod: odločitveno drevo t, primer x iz podatkovne množice Izhod: napoved yˆ, ki je približek ciljne spremenljivke
vertex_id←1
while not leaf(vertex_id) do v ← t.vertices[vertex_id]
feature_id ← v.feature threshold ← v.threshold
if x[feature_id] > thresholdthen vertex_id← v.right_subbranch else
vertex_id← v.left_subbranch end if
end while y
ˆ← v.prediction returnyˆ
Denimo, da notranje vozlišče vsebuje mejno vrednost ti in fi, ki je indeks atri- buta. Algoritem se v notranjem vozlišču usmerja tako, da vrednost x[fi] primerja z
mejo ti. Če velja x[fi] > ti, postopek nadaljuje v desnem poddrevesu, sicer pa ga nadaljuje v levem. Ko postopek doseže list, primeru napove vrednost, ki je shranjena v listu.
Izgradnja optimalnega odločitvenega drevesa je težek optimizacijski problem, zato v praksi uporabljamo požrešne algoritme. Najpogosteje uporabljen algoritem za gradnjo dreves je “top down induction”. Zapisali smo definicijo odločitvenega dre- vesa, za lažje razumevanje pa opišimo delovanje modela še na preprostem primeru.
Primer 4.2. Na sliki 5 je primer grafa odločitvenega drevesa. Denimo, da to drevo prejme primer x= (1,1), tj. X1 = 1 in X2 = 1. Ker velja f1 = 2, v prvem vozlišču preverimo vrednost druge spremenljivke. Vrednost spremenljivke X2 je 1, in ker je manjša od mejne vrednosti t0 = 1,5, postopek nadaljujemo v levem poddrevesu. S tem prispemo v list in za primer napovemo vrednost0.
r
r r
r r
A A
A A
A A
◁
◁
◁
◁
◁
◁
A A
A A
A A
◁
◁
◁
◁
◁
◁
f1 = 2, t0 = 1.5
f2 = 1, t1 = 0 0
3 4
Slika 5: Primer odločitvenega drevesa
Če bi drevo prejelo primer x = (1,2), tj. X1 = 1 in X2 = 2, pa bi iz korena nadaljevali v desno poddrevo, saj je vrednost druge spremenljivke večja od mejet0 = 1,5. Ker veljaf2 = 1, v naslednjem vozlišču preverimo vrednost prve spremenljivke.
Vrednost prve spremenljivke X1 = 1 je višja od mejne vrednosti t1 = 0. Postopek tako nadaljujemo v desnem poddrevesu, ki je list, in zato za primer napovemo vrednost 4.
Odločitveno drevo je dokaj preprost model, ki v splošnem ne more natančno opi- sati preveč kompleksno porazdeljenih podatkov. V primeru kompleksnih podatkov namreč pogosto pride do preprileganja – globoko, močno razvejano drevo (preveč) podrobno opiše podatke učne množice, s tem pa izgubi natančnost na ostalih pri- merih iz porazdelitve.
4.2 Naključni gozd
Natančnost modelov lahko izboljšamo z združevanjem v ansamble [18]. Za naše potrebe je najprimernejša ansambelska metoda model odločitvenega gozda. V splo- šnem se izkaže za zelo uspešno in bolj natančno kot posamezno odločitveno drevo [12, pogl. 4].
Definicija 4.3. Ansambel dreves je model, ki je sestavljen iz več odločitvenih dre- ves. Če je ciljna spremenljivka numerična, je napoved ansambla dreves povprečje napovedi posameznih dreves. Če je ciljna spremenljivka diskretna, pa je napoved ansambla določena izmed napovedi odločitvenih dreves tako, da se izbere napoved, ki jo napove največje število odločitvenih dreves.
Poudariti je treba, da je ansambel posebna vrsta modela. Poleg ansambla dreves lahko gradimo tudi ansamble drugih vrst modelov. Ansamble bi lahko obravnavali kot celo zvrst modelov, ki jih zgradimo z združevanjem različnih vrst posameznih modelov. S tem želimo izboljšati točnost in zmanjšati preprileganje [18]. Naključni gozd je posebna vrsta ansambla dreves, ki se izkaže za zelo uspešno.
Algorithm 3 Algoritem konstrukcije modela naključnega gozda
Vhod: podatkovna množica S, število odločitvenih dreves q, število analiziranih spremenljivk m
Izhod: model naključnega gozda mrf
Definicija 4.4. mrf ← init_random_forest() for all i∈ {1, . . . , q} do¸
S′ ←[ ]
for all j ∈ {1, . . . , n} do x← random_element(S) S′.append(x)
end for
ti ←train_random_tree(S′, m) mrf.add_tree(ti)
end for
Naj bo S ⊆ ω podatkovna množica razsežnosti p. Naključni gozd je ansambel dreves, ki ga konstruiramo s postopkom, opisanim v algoritmu 3 in za katerega veljata sledeči pravili:
1. Vsako odločitveno drevo se zgradi iz množice naključno izbranih primerov iz podatkovne množice S.
2. Na vsakem koraku gradnje drevesa je za spremenljivko, ki določa vejitev v voz- lišču, določena optimalna spremenljivka izmed množice m različnih naključno izbranih spremenljivk. Algoritem train_random_tree označuje prilagojeno različico standardnega postopka izgradnje dreves, ki upošteva restrikcijo na m izbranih spremenljivk.
Ponavadi veljam < p, če veljam=p, pa ta algoritem imenujemo vrečenje (ang.ba- gging).
Naključni gozd v splošnem dosega dobro natančnost že pri privzetih parametrih, učenje in napovedovanje pa ostajata hitra, saj število dreves q ni zelo visoko, stan- dardno se vzame npr. q = 100. Izračun napovedi ne zahteva veliko časa - potreben je namreč pregled q dreves in združitev njihovih napovedi. Delovanje naključnega gozda uporabnik dobro razume, saj so posamezna odločitvena drevesa preprosta
za razumevanje. Pri delovanju je mogoče pregledati napoved vsakega posameznega drevesa, napovedi pa se združijo na jasen način. Glede na te lastnosti je naključni gozd primeren model za uporabo pri alternativni različici samokodirnika.
4.3 Kodirnik
Naključni gozd lahko naučimo in uporabimo za napovedovanje lastnih vhodnih spre- menljivk. Poudariti je treba, da morajo drevesa v naključnem gozdu napovedovati vektorje vrednosti vseh vhodnih spremenljivk, namesto da bi npr. posamezna dre- vesa napovedovala vrednosti posameznih spremenljivk, ki bi jih potem združili v vektor. To se ne bi ujemalo z našo definicijo ansambla in posledično naključnega gozda. Za razliko od nevronskih mrež, kjer model razdelimo na kodirnik in de- kodirnik, bomo model naključnega gozda raje vzeli za izhodišče in na tej osnovi sestavili nov samokodirnik. Prvi izziv je, kako iz naključnega gozda ustvariti čim boljše kodiranje.
Definicija 4.5. Naj bo T odločitveno drevo zgrajeno na podatkovni množiciS ⊆ω razsežnostipinx= (x1, . . . , xp)∈S. Naj bol list izT, do katerega vodi potqskozi vozliščav1, v2, . . . , vk, vk+1, kjer velja vk+1 =l. Za i= 1,2, . . . , k definiramo logično izjavo qi s sledečim predpisom:
qi(l, x) =
{︄xfvi > tvi ; vi+1 je element desnega poddrevesa od vi xfvi ≤tvi ; vi+1 je element levega poddrevesa od vi .
Definiramo še logično formulo Q(l, x) = q1(l, x)∧q2(l, x)∧ · · · ∧qk(l, x), ki je ko- njunkcija vseh izjavqi. Pravimo, da primerxpripada listul, če velja logična formula Q(l, x).
Vsak list odločitvenega drevesa opiše neko lastnost podatkovne množice. Množico razdeli na dva dela – na primere, ki listu pripadajo, in tiste, ki mu ne. Primeri, ki listu pripadajo, ustrezajo množici pogojev, ki sestavljajo formulo Q(l, x), in so si tako v nekaterih lastnostih podobni. Porodi se ideja za kodiranje: iz gozda izberemo množico “dobrih” listov l1, l2, . . . , lc, za katere želimo, da bi skupaj čim bolje zajeli lastnosti množice podatkov. Poudarimo, da izbiramo liste iz celega gozda in ni nujno, da izbrani listi pripadajo istemu drevesu.
Definicija 4.6. Vektorκ= (l1, . . . , lc), katerega elementi so listi dreves naključnega gozda, imenujemo kodirni vektor. Kodirnik ϕκ : ω → {0,1}c, ki deluje na osnovi kodirnega vektorja κ = (l1, . . . , lc), definiramo s predpisom ϕκ(x) = (b1, b2, . . . , bc), kjer zai= 1,2, . . . , c velja:
bi =
{︄1 ; če je formulaQ(li, x) resnična 0 ; sicer.
Primere torej zakodiramo z dvojiškimi vrednostmi glede na to, katerim listom pripadajo. Dolžina zakodirane predstavitve primerov jec, enako kot število listov.
Z algoritmom 4 konstruiramo kodirni vektor, ki ga nato uporabimo v algoritmu 5, da dobimo kodirnik, kot je opisan v definiciji 4.6. V algoritmu 4 želimo konstruirati
Algorithm 4 Algoritem konstrukcije kodirnega vektorja iz modela naključnega gozda
Vhod: naključni gozd mrf, razsežnost kode dcode, mera kvalitete listov ρ, mera podobnosti listov sim, meja dovoljene podobnosti tsim
Izhod: kodirni vektor κ κ= [ ]
for t in mrf.trees do
for leaf int.leaves() do if length(κ)< dcode then
κ.append(leaf) end if
end for end for
for t in mrf.trees do for lnew in t.leaves() do
if lnew ∈/ κ then
κ.sort_by_quality() llast =κ.pop()
if ρ(lnew)> ρ(llast)then
if ∀l∈κ:sim(l, lnew)< tsim then κ.append(lnew)
else
κ.append(llast) end if
end if end if end for end for returnκ
dober kodirni vektorκtako, da pregledamo vsa drevesa v gozdu. Pri vsakem drevesu pregledamo vse liste in za posamezen list lnew storimo sledeče: če kodirni vektor še ne vsebuje dovolj elementov, list dodamo med kandidate za kodirni vektor, sicer preverimo druge kriterije, da odločimo, ali je lnew dober kandidat za kodirni vektor.
Zmero kvalitete ρ(definirano v nadaljevanju) primerjamo, ali jelnew bolj kvaliteten kandidat od najslabšega trenutno vključenega v kodirni vektor. Če je lnew bolj kvaliteten kot vsaj eden izmed trenutnih kandidatov in ni preveč podoben ostalim že vključenim kandidatom kodirnega vektorja, ga dodamo v kodirni vektor κ namesto najslabšega kandidata.
Pojavi se ključno vprašanje, kako določimo, kateri listi so dobri kandidati. Ne želimo, da bi bili kandidati v kodirnem vektorju κ med seboj preveč podobni. Če dva lista v kodirnem vektorju opišeta podobno (ali enako) lastnost, lahko brez škode odstranimo enega izmed njiju in tako dobimo kodirni vektor manjše razsežnosti.
Ker je razsežnost kodirnega vektorja fiksirana, vpeljemo mero podobnosti sim in podobnost listov preverjamo v algoritmu, preden naredimo zamenjavo. Če je nov kandidat preveč podoben nekemu že vključenemu, ga ne dodamo. Vpeljati moramo
pa tudi mero kvalitete listov, ki za posamezen list opiše, ali je dober kandidat.
Mera podobnosti sim liste primerja glede na primere, ki jim pripadajo. Če listoma l1 in l2 iz množice učnih primerov pripada enaka podmnožica primerov, lahko sklepamo, da lista opišeta zelo podobno ali celo enako lastnost. Definiramo preslikavo σpripadnost :V(G)→ P(S), s katero list predstavimo z množico primerov, ki mu pripadajo. Preslikava list l preslika v podmnožico σpripadnost(l) = {x |x ∈ S, formulaQ(l, x) je resnična}. Mero podobnosti definiramo s sledečim predpisom:
sim(l1, l2) = |σpripadnost(l1)∩σpripadnost(l2)|
|σpripadnost(l1)∪σpripadnost(l2)|.
Kot mero torej vzamemo razmerje med številom primerov, ki pripadajo obema listoma hkrati, in številom vseh primerov, ki pripadajo enemu ali drugemu listu.
Listi, ki vsebujejo večji delež primerov, opišejo pogostejšo lastnost, ki jo lahko zato razumemo kot pomembnejšo. Drugi podatek, ki ga v listih lahko opazujemo, je lokalna natančnost napovedi accuracy. Pove nam, kako natančna je napoved, ki jo drevo priredi primerom, ki pripadajo listu. Mero kvalitete tako v splošnem definiramo kot linearno kombinacijo teh dveh vrednosti:
ργ(l) =γ· |σpripadnost(l)|
|S| + (1−γ)·accuracy(l)
Mera kvalitete je odvisna od parametra γ ∈ [0,1]. V nadaljevanju zaenkrat pri- vzamemoγ = 1 kot privzeto vrednost in kot mero kvalitete upoštevamo zgolj delež primerov, ki pripadajo listu. V poglavju o vrednotenju delovanja samokodirnika bomo preverili, kako dobro deluje samokodirnik pri različnih nastavitvah parametra γ, med drugim tudi zato, da ugotovimo, ali v splošnem obstaja najboljša nastavitev, ki bi jo nato lahko nastavili kot privzeto.
Opisali smo postopek, s katerim določimo kodirni vektor, delovanje kodirnika pa je opisano v algoritmu 5. Kot argument mu podamo kodirni vektor, konstruiran z algoritmom 4. Z zanko gremo čez podatkovno množico in vsakemu primeru pri- redimo vektor vrednosti, ki se ujema z opisom iz definicije 4.6. Za vsak primer iz množice S gremo z zanko čez vse elemente kodiranja. Če primer pripada i-temu listu kodirnega vektorja, za i-ti člen zakodirane predstavitve določimo 1, sicer za i-ti člen zakodirane predstavitve določimo 0. Tako zakodirane primere združimo v zakodirano podatkovno množico S′, ki jo algoritem vrne.
4.4 Dekodirnik
Definicija 4.7. Dekodirnik θ : {0,1}c → ω je preslikava, ki preslika zakodiran primer nazaj v element množice ω.
Če je dekodirnik nenatančen, ne moremo biti prepričani, da smo izbrano kodira- nje dobro ovrednotili, saj so napake lahko krivda dekodirnika, in ne pomanjkljivosti kodiranja. Zato je naš cilj konstruirati čim bolj natančen dekodirnik, ki zakodi- ran primer preslika v dober približek njegove prvotne vrednosti. Pri konstrukciji se bomo opirali na kodirni vektor listov. Na razpolago imamo dva glavna podatka – poti do listov v kodirnem vektorju, ki vsebujejo pogoje o vrednosti primerov, in v listih shranjene napovedi.
