UNIVERZA V LJUBLJANI PEDAGOŠKA FAKULTETA
Poučevanje, Predmetno poučevanje
Domen Brglez
UPORABA STROJNEGA UČENJA NA PODROČJU ŠPORTNE ANALITIKE
Magistrsko delo
Ljubljana, 2019
UNIVERZA V LJUBLJANI PEDAGOŠKA FAKULTETA
Poučevanje, Predmetno poučevanje
Domen Brglez
UPORABA STROJNEGA UČENJA NA PODROČJU ŠPORTNE ANALITIKE
Magistrsko delo
Mentor: prof. dr. LJUPČO TODOROVSKI
Ljubljana, 2019
Iskrena zahvala mentorju, gospodu Ljupču Todorovskemu, da me je vzel pod svoje mentorstvo. S svojim znanjem in razgledanostjo mi je ob pisanju magistrskega dela s koristnimi nasveti in spodbudnimi besedami vedno stal ob strani. Hkrati je s tem še povečal zanimanje za usvajanje znanja s področja strojnega učenja in računalništva. S pristopom in delom je samo potrdil ugled odličnega profesorja in še boljšega človeka.
Hkrati se iz srca zahvaljujem vsem, ki so mi v času študija stali ob strani in verjeli vame.
POVZETEK
Magistrsko delo se ukvarja z uporabo algoritmov strojnega učenja za športno anali- tiko. Športno analitiko lahko definiramo kot upravljanje s strukturiranimi podatki, ki jih zbiramo iz opazovanj športnih dogodkov s ciljem pridobivanja konkurenčne pred- nosti za športno ekipo ali posameznika. V magistrskem delu sem dokumentiral celo- tni postopek analize športnih podatkov, od zbiranja in urejanja podatkov v primerno obliko, preko preverjanja različnih nastavitev parametrov metod za učenje modelov, do izbire najbolj točnih napovednih modelov.
Glavni namen magistrskega dela je bil priprava učnega gradiva za uvod v uporabo metod strojnega učenja, ki bi popolnim začetnikom omogočil spoznavanje različnih metod strojnega učenja skozi konkreten primer njihove uporabe. Zato v prvem delu predstavim različne metode strojnega učenja za gradnjo napovednih modelov iz po- datkov in postopke merjenja točnosti napovedi. V drugem, praktičnem delu, pa se osredotočam na izbiro najbolj ustreznega napovednega modela za napovedovanje izi- dov tekem. Rezultati na podatkih iz lige NBA so pokazali, da so linearni modeli najbolj ustrezni za napovedovanje izidov tekem. Prvo raziskovalno vprašanje se je nanašalo na koristnost metode analize glavnih komponent za predobdelavo podatkov. Po priča- kovanjih, glede na veliko število napovednih spremenljivk, se je izkazalo, da uporaba predobdelave poveča točnost napovednih modelov. Drugo raziskovalno vprašanje se je nanašalo na povezavo med uvrstitvijo ekipe in točnostjo modela za napovedovanje izi- dov njihovih tekem. Rezultati kažejo, da ni povezave med uvrstitvijo ekipe na lestvici NBA ob koncu sezone in točnostjo modela za napovedovanje njihovih tekem.
Ključne besede: športna analitika, strojno učenje, programski jezik R, napovedni modeli, liga NBA.
ABSTRACT
This thesis deals with applying machine learning algorithms in sports analytics.
Sports analytics can be defined as management of structured data collected from sport activities that would allow for getting competitive advantage for a sport team or an individual. More specifically, I am interested in predicting the results of basketball games. I used machine learning algorithms to builds prediction models from data on the outcomes of the games played within the NBA league and data on the league parti- cipants. The thesis documents the whole process of data analysis, from the early phase of data collection and transformation, through selecting optimal settings of the para- meters of the algorithms for learning predictive models, to the final phase of selecting the most accurate predictive models.
The main purpose of the thesis is a preparation of a guide for beginners in the field of machine learning that would familiarize interested students with machine learning algorithms through a show case of their application. To follow the purpose, the first, theoretical part of the thesis introduces different machine learning algorithms for bu- ilding prediction models from data and methods for measuring the models’ accuracy.
The focus of the second, practical part is on building accurate models for predicting the outcomes of NBA games. Results obtained on data from the last three NBA seasons show that linear models are the most accurate ones. First research question was related to the benefit of using principal component analysis for data pre-processing. As expec- ted, due to the large number of predictive variables, the use of principal component analysis leads to more accurate models. The focus of the second research question was on exploring the impact of team’s rank in the standings on the predictive accuracy.
Results show that team’s place in the standings at the end of the season is not related to the accuracy of the model for predicting the outcomes of their games.
Key words: sports analytics, machine learning, R (programming language), prediction models, NBA.
Kazalo
I Teoretični del 1
1 Uvod 2
2 Strojno učenje 5
2.1 Kratka zgodovina strojnega učenja . . . 5
2.2 Tipologija strojnega učenja . . . 6
2.3 Naloge nadzorovanega učenja . . . 6
2.4 Napovedni modeli in njihovo učenje . . . 7
2.5 Strojno učenje napovednih modelov . . . 8
2.6 Primer metode za učenje: linearna regresija . . . 9
2.6.1 Linearna regresija z več napovednimi spremenljivkami . . . 10
2.6.2 Druge oblike regresijskih modelov . . . 12
2.7 Napaka napovednega modela . . . 13
2.8 Ocenjevanje napovedne napake modela . . . 15
2.8.1 Prečno preverjanje (cross-validation) . . . 16
2.8.1.1 Pristop preverjanja množic . . . 17
2.8.1.2 LOOCV . . . 17
2.8.1.3 Prečno preverjanje s k grupami . . . 18
2.8.1.4 Bias-variance trade-off za prečno preverjanje s k grupami 19 2.8.1.5 Prečno preverjanje pri klasifikacijskih problemih . . . . 19
2.8.2 Zankanje . . . 19
2.9 Linearni modeli za klasifikacijo . . . 19
2.9.1 Logistična regresija . . . 20
2.9.1.1 Logistični model . . . 20
2.9.1.2 Ocenjevanje koeficientov regresije . . . 21
2.9.2 Logistična regresija z več napovednimi spremenljivkami . . . 21
2.10 Metoda najbližjih sosedov . . . 21
2.11 Odločitvena drevesa . . . 23
2.11.1 Algoritem za učenje odločitvenih dreves . . . 23
2.11.2 Rezanje dreves . . . 24
2.11.3 Regresijska drevesa . . . 24
2.11.4 Klasifikacijska drevesa . . . 25
2.12 Naključni gozd . . . 27
2.13 Nevronske mreže . . . 27
2.13.1 Zgodovina . . . 28
2.13.2 Uporaba nevronskih mrež . . . 29
2.13.3 Vrste nevronskih mrež . . . 29
2.13.3.1 Preprost nevron . . . 29
2.13.3.2 Kompleksnejši nevron . . . 30
2.13.4 Zgradba nevronskih mrež . . . 30
2.13.5 Plasti v nevronski mreži . . . 31
2.13.6 Perceptroni . . . 31
2.13.7 Proces učenja . . . 31
2.13.8 Uporaba nevronskih mrež v vsakdanjem življenju . . . 32
2.13.8.1 Uporaba v medicini . . . 32
2.13.8.2 Uporaba v marketingu . . . 33
2.13.8.3 Preverjanje kreditnih sposobnosti . . . 33
2.14 Nenadzorovano učenje: analiza glavnih komponent . . . 33
3 Športna analitika in košarkarska liga NBA 35 3.1 Zgodovina športne analitike . . . 36
3.2 Športna analitika in strojno učenje . . . 36
3.3 Liga NBA . . . 37
3.3.1 Zgodovina . . . 37
3.3.1.1 Obdobje 1946–1956 . . . 38
3.3.1.2 Obdobje 1956–1979 . . . 38
3.3.1.3 Obdobje 1979–1998 . . . 38
3.3.1.4 Moderna doba 1998– . . . 39
3.3.2 Struktura lige . . . 39
3.3.3 Sistem tekmovanja v eni sezoni . . . 40
3.4 Znani igralci in ekipe . . . 41
3.5 Priljubljenost in razširjenost lige NBA . . . 42
3.6 Športna analitika v ligi NBA . . . 42
3.6.1 Statistični elementi tekme . . . 42
3.6.2 Statistični elementi v sezoni ekipe . . . 43
3.6.3 Drugi statistični elementi . . . 45
4 Programsko okolje R 47 4.1 Kaj je programski jezik R? . . . 48
4.2 Osnovni ukazi . . . 48
4.2.1 Podatkovni tipi v R . . . 48
4.2.1.1 Vektor . . . 48
4.2.1.2 Seznam . . . 49
4.2.1.3 Matrike . . . 49
4.2.1.4 Array . . . 49
4.2.1.5 Data Frame . . . 50
4.2.1.6 Faktor . . . 50
4.2.2 Osnovne operacije . . . 50
4.2.3 Pogojni stavki . . . 51
4.2.4 Zanke . . . 52
4.3 Uporabni ukazi za lažje delo . . . 52
4.4 Okolje RStudio . . . 53
II Empirični del 55
5 Opis podatkov za napovedovanje izidov tekem lige NBA 56 5.1 Zajem in urejanje podatkov . . . 575.1.1 Prvi tip tabele . . . 57
5.1.2 Drugi tip tabele . . . 57
5.2 Priprava podatkov za napovedovanje izidov tekem . . . 58
5.3 Predobdelava podatkov . . . 59
6 Učenje modelov za napovedovanje izidov tekem lige NBA 61 6.1 Merjenje napovedne točnosti . . . 61
6.2 Metode za učenje napovednih modelov in nastavitve parametrov posa- meznih metod . . . 64
6.2.1 Logistična regresija . . . 64
6.2.2 Metoda najbližjih sosedov . . . 65
6.2.3 Drevesa . . . 67
6.2.4 Naključni gozdovi . . . 69
7 Analiza rezultatov napovedovanja 71 7.1 Izbira najboljših modelov po metodah . . . 72
7.2 Preverjanje veljavnosti hipotez . . . 74
7.2.1 Analiza vpliva predobdelave podatkov z analizo glavnih kompo- nent (PCA) . . . 74
7.2.2 Analiza vpliva uvrstitve moštva in kakovosti napovednega mo- dela tega moštva. . . 77
8 Sklep 80
9 Viri 82
Priloge 85
A Imena stolpcev v tabeli za tekme ekip 85
B Imena stolpcev v tabeli za podatke o sezoni ekipe 87 C Tabela rezultatov najboljših modelov brez predobdelave podatkov 91
D Tabela najboljših modelov s predobdelanimi podatki 93
Slike
2.1 Primer krivulje ROC za ustvarjen model, ki napoveduje izide tekem ene izmed ekip iz lige NBA, Atlanta Hawks. . . 14 2.2 Rdeča krivulja predstavlja povprečno kvadratno napako za testne po-
datke, siva krivulja pa povprečno kvadratno napako za učne podatke (James in drugi, 2013). . . 16 2.3 Primer, na kakšen način deluje metoda najbližjih sosedov. V danem
primeru je parameter k je enak 3. . . 22 3.1 Prikaz delitev moštev na dve konferenci, zahodno (rdeča barva) in vzho-
dno (modra barva). Vsaka konferenca se deli na divizije, katere so v vsaki konferenci 3. V vsaki diviziji je napisano mesto, v kateri ima ekipa iz te divizije sedež. . . 40 3.2 Primer osnovne tabele (box score-a) za ekipo Golden State Warriors
na eni izmed tekem lige NBA. Gre le za enega izmed možnih načinov beleženja podatkov o ekipi. V večini primerov imajo različne televizijske hiše različne načine beleženja podatkov, ki pa so si med seboj podobni. 44 4.1 Logotip programskega jezika R na levi in na desni stran logotip pro-
gramskega okolja RStudio. . . 47 5.1 Primer dela tabele, ki je vključen pri vsaki izmed štirih nastalih tabel,
primer na sliki pa je del tabele moštva Atlanta Hawks. . . 59 5.2 Sliki, ki prikazujeta rezultate analize PCA za tretjo in četrto tabelo,
opisano v poglavju 5.2 za moštvo Atlanta Hawks. Vsaka točka na grafu predstavlja kumulativno vsoto pojasnjene variance. . . 60 6.1 Grafični prikaz poteka zbiranja rezultatov analize v magistrskem delu. . 61 6.2 Podmnožice, ki jih vrne prečno preverjanje, kjer so vidni indeksi vsake
podmnožice. Vsak izmed vrnjenih indeksov v podmožici predstavlja določeno vrstico v originalni matriki, ki je bila s prečnim preverjanjem razdeljena na podmnožice. . . 62 6.3 S pomočjo 5-CV sem dobil vse različne možnosti naborov učnih množic,
ki so zapisani zgoraj na sliki. Množica, ki ni zapisana v posamezni delitvi podmnožic, je uporabljena kot testna množica na danih podatkih. . . . 63
7.1 Škatla z brki za najboljši model podatkov brez analize PCA in z ana- lizo PCA, ki prikazuje razporeditev vrednosti najboljšega (globalnega) modela za vsako ekipo. . . 76 7.2 Škatla z brki, ki prikazuje razporeditev vrednosti AUC za skupine ekip,
kjer so ekipe razdeljene glede na uvrstitev na lestvici ob koncu sezone na najboljših 10 ekip (Top 10), najslabših 10 ekip (Bot10) in na ekipe, ki so bile uvrščene na sredino lestvice (Mid10). . . 78 7.3 Škatla z brki, ki prikazuje razporeditev vrednosti AUC za skupine ekip,
kjer so ekipe razdeljene glede na uvrstitev na l . . . 79
Tabele
7.1 Vrednosti AUC za napovedi izidov tekem po ekipah modelov, zgrajenih z najboljšimi nastavitvami štirih metod (LR, KNN, RF in TREE). Zadnja vrstica poda povprečne range metod za vse ekipe. . . 73 7.2 Tabela z najboljšima modeloma za posamezno vrsto podatkov. V za-
dnji vrstici sta dodana povprečna ranga obeh modelov za primerjavo medsebojnih rezultatov za posamezno ekipo. . . 75 7.3 Povprečni rangi vseh najboljših nastavitev za posamezno metodo, glede
na podatkovno množico. . . 77 C.1 Vrednosti AUC za napovedi izidov tekem po ekipah modelov, zgrajenih
z najboljšimi nastavitvami štirih metod (LR, KNN, RF in TREE). Po- datki, ki so uporabljeni za napovedi izidov, podanih v tabeli, niso bili predobdelani z analizo glavnih komponent (PCA). Zadnja vrstica poda povprečne range metod za vse ekipe. . . 92 D.1 Vrednosti AUC za napovedi izidov tekem po ekipah modelov, zgrajenih
z najboljšimi nastavitvami štirih metod (LR, KNN, RF in TREE). Po- datki, ki so bili uporabljeni za napoved izidov, podanih v tabeli, so bili predobdelani z analizo glavnih komponent (PCA). Zadnja vrstica poda povprečne range metod za vse ekipe. . . 94
Del I
Teoretični del
Poglavje 1 Uvod
Strojno učenje je področje umetne inteligence, ki se danes hitro razvija in je uporabljeno na skoraj vseh področjih našega življenja. Ukvarja se s preučevanjem algoritmov, ki so se sposobni učiti in izboljševati na podlagi podatkov ali pa izkušenj iz preteklih izvajanj.
Ker pa je strojno učenje tematika, ki se lahko uporablja na veliko področjih v našem življenju, se lahko uporablja tudi v športu. Natančneje govorimo o enem izmed možnih načinov uporabe strojnega učenja v športu, osredotočil pa sem se na košarkarsko ligo NBA.
Severnoameriška liga NBA je najbolj priljubljena in najboljša košarkarska liga na svetu. Prav zaradi vse medijske in svetovne prepoznavnosti želijo ekipe dosegati naj- boljše rezultate. Ekipe si želijo poznati svoje slabosti in dobre lastnosti, ki so odraz doseženih statističnih elementov v sezoni ali pa v določenem časovnem obdobju tek- movalne sezone. Seveda je najpomembnejše vprašanje, na katerega želijo dobiti kar se da natančen odgovor, kako naj bi se njihova naslednja tekma razpletla. Gre torej za vprašanje ali bo ekipa zmagala ali ne.
Slednji problem je zbudil moje zanimanje. Ker je napovedovanje izidov tekem zanimivo iz več vidikov, je bila osrednja tema magistrskega dela raziskovanje točnosti različnih modelov za napovedovanje izidov tekem lige NBA. Kot vhodne spremenljivke sem upošteval statistične kazalnike posamezne ekipe, prostor ciljnih spremenljivk pa je binaren, saj z modeli iščem natančne napovedi zmage oz. poraza ekipe. Izenačen rezultat po rednem delu se ne šteje kot poseben rezultat, saj se vsaka tekma konča z zmagovalcem, ne glede na to, koliko podaljškov je potrebno odigrati, da ena ekipa doseže večje število točk kot druga. Da gre za zanimivo temo, lahko sklepam po dejstvu, da v literaturi zasledimo že kar nekaj različnih primerov modelov za napovedovanje izidov tekem, ki pa so si vsi med seboj različni. Hkrati pa je poudarjeno bistvo, da univerzalni model ali pa nek model, ki bi bil najboljši, ne obstaja (Zimmermann, 2016).
Za vsako tekmo v ligi NBA se beleži velika količina podatkov, ki zajemajo vse posamezne košarkarske elemente kot tudi ostale podatke, ki niso najbolj vezani na samo košarkarsko igro, ampak so del celotnega dogajanja na tekmi (število gledalcev na tekmi, povprečna starost ekipe ...). Danes so računalniki napredovali do te mere,
da je mogoče ogromno količino podatkov s premišljenim načinom obdelati tudi doma in s pomočjo tega priti do določenih ugotovitev. Zato je potrebno goro podatkov, ki so nekomu na voljo, treba znati zbrati in urediti v tako obliko, da bodo primerni za obdelavo z algoritmi strojnega učenja.
Sam sem uporabil različne algoritme strojnega učenja, med katerimi sem zajel tiste, ki so bolj prijazni uporabniku, saj so lažje razumljivi ter se jih lahko do neke mere smiselno grafično prikaže. Ostali raziskovalci (Giulidori, 2017; Cheng in drugi, 2016;
Kvam in Sokol 2006) pa uporabljajo različne algoritme in jih z različnimi nastavitvami še dodatno prilagajajo, poleg tega pa poskušajo poiskati tudi kakšno lastnost, ki bi pomembneje vplivala na napovedovanje izidov tekem ter s tem omogočala izdelavo bolj točnih modelov za napovedovanje izidov tekem.
Strojno učenje in športna analitika sta široko odprti področji. Kljub temu pa sta to področji, ki za nekoga, ki se prvič sreča s temi tematikami, nista najbolj razumljivi oz.
sta težko razumljivi tematiki. Za učenje novega znanja, ki ni enostavno razumljivo, je potrebno dobro začetno gradivo. Ker pa ob pregledu virov nekega takšnega gradiva ni, sem se s tem razlogom odločil, da pripravim gradivo, ki bo bralcu omogočalo učenje težje razumljive tematike s pomočjo konkretnega primera na temi, ki je široko poznana.
Tako se bo lahko nekdo opogumil in se poglobil v hitro razvijajoče se področje v današnjem življenju in s tem razširil svoj spekter znanj.
Na začetku dela sem si postavil dve hipotezi. Prva hipoteza se glasi: ”Pred-obdelava podatkov z analizo glavnih komponent (PCA) omogoča učenje bolj točnih napovednih modelov za napovedovanje izidov tekme v ligi NBA.” Pri tej hipotezi sem se osredotočil na dejstvo, da je razpoložljivih podatkov za analizo ogromno. Zato sem preučeval možnost predobdelave podatkov z analizo glavnih komponent (PCA), ki bi znatno zmanjšala količino podatkov, pri tem pa opazoval, kaj se dogaja s točnostjo napovedi izidov tekem v primerjavi s podatki, ki niso obdelani z analizo glavnih komponent.
Druga hipoteza pa se glasi: ”Končna uvrstitev moštva na lestvici vpliva na točnost napovedi izidov njihovih tekem.” Glede na to, da se na koncu sezone pojavlja vzorec ekip, ki so po navadi uvrščene višje, in tudi tistih, ki so uvrščene nižje na lestvici, sem se spraševal, če obstaja kakšna povezava med tema dvema dejstvoma. Zato sem ekipe razdelil v različne tri skupine in preverjal ter opazoval, če je lažje napovedati rezultate za katero izmed skupin ekip glede na uvrstitev na koncu sezone.
Ob pregledu velike količine virov nisem prišel do primernih člankov ali literature, ki bi bila prijazna do nekoga, ki se prvič sreča s to tematiko. Zato je bil namen magistr- skega dela, poleg iskanja čim bolj natančnih modelov za napovedovanje izidov tekem lige NBA z izbranimi algoritmi strojnega učenja, ta, da ustvarim začetno literaturo za učenje strojnega učenja. Predvsem sem se oziral na dejstvo, da bo to literatura, ki bo primerna za nekoga, ki se s to tematiko ni še nikoli srečal. To sem poskušal doseči s prikazom kompleksne tematike na primeru napovedovanja izidov tekem lige NBA, ki je globalno poznana.
Glede na odprtost in kompleksnost teme sem se omejil na dva cilja, in sicer da pri- pravim učne modele za napovedovanje izidov tekme lige NBA in pa na to, da pripravim
problemsko orientirano gradivo za področje strojnega učenja.
Magistrsko delo je sestavljeno iz dveh delov. V prvem, teoretičnem delu, je opisano področje strojnega učenja. Opisana je zgodovina strojnega učenja, kateri sledi topo- logija strojnega učenja, naloge strojnega učenja, napovedni modeli in njihovo učenje, ter strojno učenje napovednih modelov. Na preprostem primeru linearne regresije je opisan potek strojnega učenja. Sledi opis napake napovednega model in ocenjevanje napovedne napake nekega modela, ki je razdeljeno na več podpoglavij. Zadnja pod- poglavja v poglavju strojnega učenja so teoretični opisi metod strojnega učenja, ki so linearni modeli, metoda najbližjih sosedov, odločitvena drevesa, naključni gozd in ne- vronske mreže, ki so dodane kot zanimivost in predlog za nadaljnje delo s teoretičnega vidika, v empiričnem delu pa niso obravnavane.
Sledi poglavje o športni analitiki in košarkarski ligi NBA, kjer v podpoglavjih opisu- jem zgodovino športne analitike, povezavo športne analitike in strojnega učenja, celotno ligo NBA in nekaj njenih zanimivosti, da si bralec lažje predstavlja tematiko, na kateri temelji kasnejša analiza podatkov. Posebej so opisani statistični elementi posamezne tekme, ki so uporabljeni v empiričnem delu, tako da ne pride do nejasnosti, kaj kateri izmed statističnih elementov tekme predstavlja.
Zadnje poglavje teoretičnega dela je namenjeno predstavitvi programskega jezika in okolja R, ki služi kot kratek uvod in povzetek bistvenih značilnosti, ki jih mora bralec usvojiti, da lahko sledi gradivu in sam preizkusi različne metode v okolju RStudio.
Drugi del je empirični del, ki vsebuje poglavja, naravnana na praktično uporabo opisanih poglavij iz teoretičnega dela. Najprej je opisano, kako sem prišel do podatkov, jih uredil in pripravil za nadaljnjo obdelavo z metodami strojnega učenja. Sledi po- glavje, v katerem opisujem, kako sem praktično prišel do rezultatov za vsako metodo posebej, kakšne parametre sem nastavljal in kako se to v programskem okolju RStu- dio tudi izvede. Dobljeni rezultati so opisani v naslednjem poglavju, kjer analiziram rezultate napovednih modelov glede na zastavljene hipoteze in jih na koncu tudi ovre- dnotim. Magistrsko delo zaključim s sklepom. Sledi še navedba virov ter poglavje, kjer pojasnim različne kratice, ki so se pojavile v tabelah, katere sem sestavil ob zbiranju podatkov iz svojega vira. Med prilogami so tudi dodatne tabele, ki služijo kot dodatno pojasnilo k dobljenim rezultatom v poglavju analize hipotez.
Poglavje 2
Strojno učenje
Strojno učenje je področje umetne inteligence, katero preučuje učljive algoritme, to je da izboljšuje svoje delovanje na podlagi podatkov ali izkušenj iz preteklih izvajanj.
Strojno učenje (angl. machine learning, tudi statistical learning), pogosto poteka v obliki algoritmične analize podatkov s ciljem iskanja vzorcev v podanih podatkih ali pa gradnje napovednih modelov iz podatkov. Drugače povedano se lahko računalniki naučijo določenih stvari iz podatkov ali obstoječe znanje na nekem področju celo nad- gradijo, ne da bi bili prej eksplicitno programirani. Vzorci in napovedni modeli so uporabni iz preprostih razlogov, kot so kratka in razumljiva predstavitev večje količine podatkov, njihovo boljše razumevanje, pojasnjevanje obnašanja opazovanega sistema ali pojava, napoved bodočega obnašanja opazovanega sistema ter odločanje o ustrezni kontroli njegovega bodočega obnašanja.
Po načelu umetne inteligence in strojnega učenja deluje na primer samodejno par- kiranje avtomobila. Algoritmi za samodejno parkiranje ne morejo biti vnaprej pro- gramirani, saj se parkirni prostor in njegova lokacija skoraj vedno razlikujeta. Zaradi gradnje novih parkirišč je nerealno pričakovati, da bi si računalnik zapomnil oziroma v ustrezno obliko zapisal vsa parkirišča na Zemlji. Tako se morajo pri vsakem novem parkirnem mestu algoritmi znajti na osnovi prejšnjih izkušenj in sami narediti ustrezen program za parkiranje.
Poglavje 2 in njegova podpoglavja so povzeta po Flach (2012) ter James in drugi (2013). To sta dva učbenika v angleškem jeziku, ki sta mi služila kot podlaga za teoretični del magistrskega dela.
2.1 Kratka zgodovina strojnega učenja
V 40-ih letih prejšnjega stoletja je bil izumljen prvi računalniški sistem, imenovan ENIAC. Že od vsega začetka je bila ideja raziskovalcev in izumiteljev ta, da bi izumili stroj, napravo, ki bi znala posnemati človeško razmišljanje in učenje1. V 50-ih letih 20. stoletja je Frank Rosenblatt2 izumil Perceptron, ki je zelo preprost klasifikacijski
1https://provalisresearch.com/blog/brief-history-machine-learning
2http://csis.pace.edu/ ctappert/srd2011/rosenblatt-contributions.htm
model, a ko ga združimo skupaj z velikimi količinami podatkov v mrežo, postane zelo močan in uporaben.
Sledilo je stagniranje strojnega učenja, ponovno pa se je strojno učenje uveljavilo v 90-ih letih 20. stoletja zahvaljujoč statistiki. Računalništvo in statistika sta skupaj pripeljala do verjetnostnih pristopov v umetni inteligenci. Takrat se je že beležila velika količina podatkov, zato so znanstveniki izumili inteligentne sisteme, ki so bili sposobni zbirati te podatke, se iz njih tudi kaj naučiti ter podati neko informacijo. Med drugim je v tistem času IBM-ov sistem Deep Blue premagal takrat svetovnega prvaka v šahu, velemojstra Garryja Kasparova.
Danes se v večini področij našega življenja kopičijo gore podatkov, za katere je postalo pomembno, da se čim bolj avtomatizirano analizirajo in podajo lastniku teh podatkov neko informacijo, ki bi mu lahko koristila. Preprost primer tega je uporaba kartic zvestobe v trgovini, kjer s pomočjo analize nakupov lahko dobimo informacijo, ali bo lastnik kartice dober kupec za neko trgovino ali pač ne.
2.2 Tipologija strojnega učenja
Glede na to, na kakšen način algoritem za strojno učenje pridobiva in uporablja podatke za učenje, poznamo štiri različne vrste strojnega učenja.
Prva vrsta jenenadzorovano učenje (angl. unsupervised learning), pri katerem gre za učenje vzorcev iz učnih podatkov, ki ne vsebujejo posebnih, eksplicitnih na- vodil ali oznak konceptov za učenje. Nasprotje temu je nadzorovano učenje (angl.
supervised learning). Pri slednjem so učni primeri v podatkovni množici označeni s po- sebnimi izhodnimi spremenljivkami, ki so cilj učenja. Učni primeri so pari tipa (vhod, izhod), tako da je naloga algoritma za stojno učenje iskanje neznane funkcijske povezave med vhodi in izhodom. Mešanica obojega je polnadzorovano učenje (angl. semi- supervised learning), kjer je (običajno manjši) del učnih primerov označenih, ostali pa ne.
Posebna vrsta strojnega učenja jespodbujevalno učenje, kjer ima učeči se agent nalogo sam pridobivati primere z opazovanjem okolja ter interakcijami z okoljem skozi akcije, ki so mu na voljo. Pri učenju agenta vodi funkcija nagrajevanja (spodbujanja), ki pravilnim akcijam dodeli visoke nagrade, nepravilnim pa nizke nagrade oziroma kazni.
2.3 Naloge nadzorovanega učenja
Podatkovna množica za strojno učenje je pogosto zapisana v obliki tabele. Vrstice tabele ustrezajo učnim primerom, posamezni stolpci pa lastnostim teh učnih primerov.
Vsak posamezen stolpec učnega primera predstavlja spremenljivko učne množice. Spre- menljivke v učni množici za nadzorovano učenje delimo na dva dela. V prvi del sodijo vhodne ali napovedne spremenljivke (angl. input, predictive variables), katerim
rečemo tudiatributi (angl. attributes). Vhodne spremenljivke običajno označujemo z Xi, kjer jei indeks spremenljivke iz množice1,2, ..., p. Skrajšano lahko pišemo vhodne spremenljivke tudi kot urejenop-terico X = (X1, X2, ..., Xp).
Ostale spremenljivke učne množice so izhodne ali ciljne spremenljivke (angl.
output, target variables), ki jih običajno označimo z veliko črkoY. Pri običajnem nad- zorovanem učenju je v učni množici le ena ciljna spremenljivka, vse ostale spremenljivke so pa napovedne.
Če pogledamo spremenljivke glede na njihove zaloge vrednosti, pa jih prav tako delimo na dve skupini. Numerične ali kvantitativne spremenljivke zavzemajo nabor številskih, urejenih vrednosti. Za razliko od njih padiskretne alikvalitativne spremenljivkezavzemajo kvalitativne, ne nujno urejene vrednosti (npr. barva oči ali spol).
Na osnovi tipa ciljne (izhodne) spremenljivke delimo naloge nadzorovanega učenja naregresijske inklasifikacijske. Pri regresiji je ciljna spremenljivka numerična, pri klasifikaciji pa diskretna. Preprost primer regresijske naloge je napovedovanje plače zaposlenih glede na njihove lastnosti, primer klasifikacijske naloge je ugotavljanje barve oči posameznika na podlagi njegovih oziroma njenih drugih karakteristik.
V splošnem lahko nalogo nadzorovanega strojnega učenja formalno definiramo na sledeči način. Na vhodu imamo podano učno množico z napovednimi spremenljivkami Xi, i∈1,2, . . . , p in ciljno spremenljivko Y. Naloga je najti neznano povezavo med Y inX = (X1, ..., Xp). Predpostavimo seveda, da taka povezava obstaja, kar lahko bolj formalno, matematično, zapišemo kot Y = f(X) + , kjer je f fiksna, a še neznana funkcija, ki predstavlja sistematično informacijo, katero X poda o Y, in splošna napaka, neodvisna od vrednostiX (običajna dodatna predpostavka je, da je povprečje enako 0).
Preprost primer take naloge je sledeči. Naše napovedne spremenljivkeXiso merljive lastnosti krvi neke osebe, ciljna spremenljivkaY pa je tveganje za nezaželeno reakcijo pacienta na neko cepivo ali zdravilo. Spremenljivke Xi se da preprosto pridobiti z odvzemom vzorca krvi osebe in njegovo laboratorijsko analizo. S pomočjo teh podatkov pa bi želeli napovedovati vrednost Y tudi za osebe, kjer nam tveganje ni znano. Če je naučeni napovedni model dovolj točen, se lahko izognemo neželenim posledicam, ki jih lahko cepivo oziroma zdravilo povzroči (npr. nezavestnemu) pacientu z neznanim tveganjem.
2.4 Napovedni modeli in njihovo učenje
Ker je točno funkcijof pri realnih podatkih oziroma problemih težko ali celo nemogoče dobiti, si zastavimo bolj praktični cilj njenega ocenjevanja z nekim približkom, ki mu bomo reklinapovedni model. Čeprav njegovo ime nakazuje njegov namen, obstajata dva razloga za njegovo učenje.
Prvi razlog je seveda napovedovanje. Tu lahko pri upoštevanju zgornjih predpostavk o f, zapišemo Yˆ = ˆf(X), kjer je fˆnaša ocena za f (napovedni model) in Yˆ napoved
vrednosti Y. V primeru napovedovanja na fˆgledamo kot na nekakšno črno skrinjico (angl. blackbox), saj nas ne zanima točna oblika f, temveč nas zanima čim manjšaˆ napaka napovediYˆ. Napaka napovedi je sestavljena iz dela, ki se ga da zmanjšati (angl.
reducible error) z ustrezno izbiro primerne tehnike za ocenjevanje funkcije oziroma učenja napovednega modela, in iz dela, ki se ga ne da zmanjšati (angl. irreducible error). Tudi v primeru, da bi našli popoln približek za f in bi torej imeli Yˆ = f(x), bi še vedno srečali napako napovedi , katere pa ni mogoče napovedati z uporabo X. Napaka je lahko pogosto posledica neizmerjenih napak, ki so nastale že v fazi pridobivanja podatkov in na katere se v fazi učenja modela ne da več vplivati. Prav ta napaka, ki je ne moremo zmanjšati, pa je tista, ki postavi spodnjo mejo napake naučenega modela.
Na zgornjem primeru je napaka, ki se je ne da zmanjšati, počutje pacienta tisti dan, ko mu odvzamejo vzorec krvi, saj vpliva na sestavo krvi, sestava zdravila in odstopanja od realnih vrednosti ter še kakšne druge stvari. Vse te napake so takšne, na katere ne moremo vplivati, zato lahko posledično zmanjšajo točnost napovednega modela, katerega se želimo naučiti.
Drugi namen ocenjevanja funkcije je sklepanje. Pri tem se oddaljimo od načela napovedi, kjer nas ne zanima toliko, kakšna je napovedna točnost funkcije f, temveč želimo natančno vedeti, kakšna funkcija fˆje. Zanimajo nas odnosi med napovednimi in ciljnimi spremenljivkami, kot so, katere napovedne spremenljivke so povezane s ciljno spremenljivko ter kakšna je povezava med napovednimi in ciljno spremenljivko.
Tako se lahko glede na to, kakšen je naš cilj pri danih podatkih, napoved, sklepanje ali mešanica obojega, odločamo med različnimi metodami za učenje f, ki so različno primerne glede na razpoložljive podatke.
2.5 Strojno učenje napovednih modelov
Metod strojnega učenja je veliko, v grobem pa jih lahko delimo na dve skupini. To so parametrične in neparametrične metode. Te metode se med seboj razlikujejo v nekaterih lastnostih, ki jih tako naredijo bolj primerne za nekatere množice podatkov in spet manj primerne za druge množice podatkov.
Parametrične metode so tiste metode, ki pristopijo k reševanju zastavljenega pro- blema v dveh korakih:
1. Najprej naredimo/postavimo predpostavko o obliki funkcijef (npr. linearni mo- del predvideva funkcijo f(X) =β0+β1X1+...+βpXp),
2. Ko izberemo model, potrebujemo postopek, ki z uporabo učne množice nauči model (npr. za linearni model moramo dobiti vrednosti koeficientov βi ; i = 1,2, ..., p).
Parametrične metode zaradi predpostavke o obliki funkcije f zmanjšajo problem ocenjevanja funkcije f na ocenjevanje množice parametrov, ki se pojavijo v funkciji f.
Po navadi velja, da je lažje (pametno) izbrati parametre, kot pa iskati celotno funkcijo.
To pa je hkrati tudi slaba lastnost parametričnih metod, saj se lahko zgodi, da se izbrani model ne bo ujemal z dejansko f. Če pa bo model preveč različen od prave funkcijef, bo naša ocena slaba.
Iščemo lahko fleksibilne modele, ki lahko ustrezajo različnim formam (oblikam) f. To pa v večini primerov pomeni, da je potrebno upoštevati večje število parametrov.
Posledično to lahko sproži pojav prekomernega prileganja (angl. overfitting), kar pomeni, da bodo modeli preveč sledili napakam v podatkih, se preveč prilagajali učnim podatkom in zato ne bodo univerzalno uporabni.
Nasprotno od parametričnih metod, neparametrične metode ne naredijo eksplicitne domneve o obliki f. Namesto tega se tu išče ocena f, ki se prilega, približa podat- kom kolikor se da, le da ni preohlapna ali pretesna. To pa pomeni, da bo pri tem večja verjetnost za boljšo napoved f. Ker ne postavijo predpostavke o f, se izognejo pomanjkljivosti parametričnih metod, da bi povsem zgrešili napoved funkcije f. Ker pa te metode iščejo funkcijo, ki ni pretesna in preveč ohlapna, pa ni omejitve števila funkcij f, ki jih iščejo, kar pomeni, da je potrebno pogledati ogromno parametrov in posledično to pomeni veliko opazovanj za pravilno oceno funkcije f. To pa je slabost, ki jo je potrebno imeti v mislih, ko se odločamo za neparametrične metode.
2.6 Primer metode za učenje: linearna regresija
Linearna regresija je, kot že ime pove, preprost algoritem strojnega učenja za napo- vedovanje kvantitativne spremenljivke Y na podlagi ene napovedne spremenljivke X.
Predvideva, da je odnos med spremenljivkama približno linearen, kar lahko matema- tično zapišemo kot
Y ≈β0+β1X.
Znak≈ se v tem primeru bereje približno modelirano kot. Konstanti β0 inβ1 sta ne- znani konstanti, ki predstavljata začetno vrednost in naklon grafa linearne funkcije. Ko s pomočjo učne množice dobimo oceniβˆ0 inβˆ1, ju lahko uporabimo pri napovedovanju testnih primerov s pomočjo obrazca
ˆ
y = ˆβ0+ ˆβ1x, kjer yˆpredstavlja napoved Y na podlagiX =x.
Cilj je poiskati oceni koeficientov βˆ0 inβˆ1, da se bo linearni model kar se da dobro prilegal danim podatkom. Drugače povedano iščemo premico, ki bo od danih opazovanj ker se da malo oddaljena. Najpogostejša metoda, ki se uporablja za preverjanje, je metoda najmanjših kvadratov(angl. least squares).
Če je yˆi = ˆβ0 + ˆβ1xi napoved za Y na osnovi i-te vrednosti X-a, potem lahko z ei = yi −fˆi označimo i-ti presežek (angl. residual), ki je razlika med i-to opazovano vrednostjo in i-to opazovano vrednostjo, ki jo je napovedal linearni model. Tako se
lahko definira presežek vsote kvadratov (angl. residual sum of squares - RSS) kot RSS =e21+e22+...+e2n.
Metoda najmanjših kvadratov izbere βˆ0 in βˆ1 tako, da minimalizira preostanek vsote kvadratov.
Da ocenimo točnost ocene koeficientov se je potrebno spomniti, da je pravo razmerje med X in Y lahko povzeto s enačbo Y = f(X) + za neko neznano funkcijo f, kjer je napaka, ki ima povprečno vrednost 0. Tako lahko za linearno odvisnost med spremenljivkama s pomočjo zgornje enačbe zapišemo kot
Y =β0+β1X+.
Kako kakovosten je model linearne regresije, je po navadi ocenjeno s pomočjo dveh povezanih vrednosti, tj. preostankom navadne napake (angl. residual standard error - RSE) in R2. RSE je v grobem povedano povprečna vrednost, za katero bo napoved odstopala od prave regresijske premice. RSE je po navadi znan kot mera, ki pove, kako slabo se model prilega podatkom. Izračuna se po obrazcu
RSE =
s 1
n−2RSS =
v u u t
1 n−2
n
X
i=1
(yi−yˆi)2.
R2 oz. koeficient determinacije je mera, ki vrednoti kakovost regresijskega modela.
Predstavlja delež pojasnjene variance pri linearni regresiji. Kakovost ocene napovedi modela meri z regresijsko premico. Drugače povedano – meri razpršenost točk okoli regresijske premice. Ker ga pri svojem delu ne bom uporabljal, bom podrobnejši opis izpustil.
2.6.1 Linearna regresija z več napovednimi spremenljivkami
Zgoraj opisana linearna regresija je uporaben pristop za napovedovanje, če napove- dujemo z eno napovedno spremenljivko, a imamo običajno več kot eno napovedno spremenljivko. Vse te različne napovedne spremenljivke bi lahko s pomočjo regresije pogledali vsako posebej, vendar pa to ne bi zadovoljilo naših potreb. Namesto tega je boljši pristop ta, da navadno linearno regresijo razširimo na način, da lahko direktno upoštevamo več napovednih spremenljivk.
To pa lahko naredimo tako, da za vsako napovedno spremenljivko izberemo poseben koeficient. V splošnem, če imamo prazličnih napovednih spremenljivk, lahko linearno regresijo z več napovednimi spremenljivkami zapišemo v obliki
Y =β0+β1X1+β2X2+...+βpXp+,
kjer Xj predstavlja j-to napovedno spremenljivko in βj predstavlja povezavo med na- povedno in ciljno spremenljivko. Kot pri navadni linearni regresiji so koeficienti βi
neznani in moramo dobiti njihovo oceno. Z ocenami za βˆi lahko dobimo napovedi s pomočjo
ˆ
y= ˆβ0+ ˆβ1x1 + ˆβ2x2+...+ ˆβpxp.
Parametri so določeni z uporabo istega pristopa najmanjših kvadratov, kot je to pri navadni linearni regresiji. Izbrati moramo βi ; i = 0,1, ..., p, da kar se da zmanjšamo vsoto kvadratov razlike (ostanka) (angl. residual sum of squares – RSS)
RSS =
n
X
i=1
(yi−yˆi)2,
oz. z upoštevanjem zgornje enačbe RSS =
n
X
i=1
(yi−βˆ0−βˆ1xi1−...−βˆpxip)2.
Tiste vrednostiβˆi, za katere je RSS najmanjši, so ocene za koeficiente linearne regresije z več napovednimi spremenljivkami.
Ko je govora o linearni regresiji z več napovednimi spremenljivkami, se postavi nekaj vprašanj, ki zahtevajo odgovore.
1. Ali je vsaj ena izmed napovednih spremenljivkX1, X2, ..., Xp uporabna pri napo- vedovanju?
Ko nas pri linearni regresiji zanima, ali obstaja povezava med napovedno spre- menljivko, moramo preprosto preveriti, če je kateri od koeficientov βi enak 0.
Nato pa s pomočjo F statistike preverimo, če obstaja kakšna povezava med na- povedno in ciljno spremenljivko. Če bo F-statistika vrnila vrednost blizu ena, to pomeni, da med napovedno in ciljno spremenljivko ni nobene povezave, če pa bo vrednost večja od 1, pa lahko sklepamo, da neka povezava obstaja.
2. Ali so potrebne vse napovedne spremenljivke, ki so dane na začetku, da pojasnijo ciljno spremenljivko, ali je dovolj le podmnožica teh napovednih spremenljivk?
Lahko se zgodi, da so vse napovedne spremenljivke povezane s ciljno spremen- ljivko, čeprav je v praksi po navadi tako, da je ciljna spremenljivka povezana le z nekaterimi napovednimi spremenljivkami. Področje izbire spremenljivk je posebej študirano in se ga kasneje v magistrskem delu še dotaknem.
Najlažje bi bilo, da bi naredili modele z vsemi možnimi kombinacijami napovednih spremenljivk (njenimi podmnožicami) in bi tako dobili podmnožico spremenljivk, ki so povezane s ciljno spremenljivko. Sliši se lepo, a če pogledamo številke, vidimo, da je skupaj 2p različnih podmnožic p-spremenljivk. Če je p majhen, se da pregledati toliko podmnožic, čim pa postane pmalce večji, npr. 20, pa dobimo 1048756 podmnožic 20 spremenljivk. Pri p = 30 pa dobimo 1073741824 možnih podmnožic, kar pa ni praktično in uporabno. Zato obstaja nekaj načinov, kako zmanjšati velikost te množice.
Izbira naprej(angl. forward selection) je način, pri katerem začnemo s praznim modelom, ki ne vsebuje spremenljivk. Dodajamo spremenljivko, ki ima najmanjši RSS za model z 1,2, ..., p spremenljivkami. Model se odvija toliko časa, dokler ni izpolnjen nek pogoj za ustavitev. Izbira nazaj (angl. backward selection) je način, pri katerem upoštevamo vse spremenljivke v modelu in odstranjujemo spremenljivko, ki ima največjo p-vrednost. p-vrednost je vrednost, ki pove, kako je neka spremenljivka statistično pomembna. Tudi ta način se odvija, dokler ni izpolnjen nek pogoj za ustavitev. Mešana izbira (angl. mixed selection) je kombinacija izbire naprej in izbire nazaj. Najprej začnemo brez spremenljivk v modelu in z izbiro naprej. Nato dodajamo spremenljivko, ki je najboljša za ta model. Dodajamo spremenljivke eno po eno. Če pa se v katerem koli koraku dodajanja spremenljivkep-vrednost neke spremenljivke dvigne nad neko določeno mejo, se jo odstrani iz modela. Torej se izbira naprej in izbira nazaj dopolnjujeta, dokler niso v modelu vse spremenljivke, ki imajo dovolj nizko p-vrednost.
3. Kako dobro se model prilega podatkom?
Kako dobro se model prilega podatkom najpogosteje merimo z RSE in R2, de- ležema pojasnjene variance. Poleg izračuna teh dveh vrednosti je uporabno, če si podatke narišemo. Grafične upodobitve lahko razkrijejo težave modela, ki jih sicer s pomočjo številskih izračunov ne bi videli.
2.6.2 Druge oblike regresijskih modelov
Do sedaj so bile vse oblike regresijskih modelov obravnavane s predpostavko, da so vse spremenljivke v modelu numerične. V praksi pa ni vedno tako, ker pogosto sreču- jemo tudi kvalitativne napovedne spremenljivke. Za njihovo obravnavo uporabljamo pretvorbo kvalitativne spremenljivke v eno ali več nadomestnih (angl. dummy) nume- ričnih spremenljivk.
• Binarne napovedne spremenljivke
Če ima kvalitativna napovedna spremenljivka le dve možni vrednosti, je pre- nos te napovedne spremenljivke v regresijski model enostaven, saj rabimo le eno nadomestno spremenljivko. Na primer, če imamo spremenljivko spol, ki je kvali- tativna in dve-vrednostna, vrednost za en, naključno izbrani spol (npr. ženski), nadomestimo z vrednostjo 1, vrednost za drugi spol pa nadomestimo z 0. Na- domestno spremenljivko XN potem uporabimo kot napovedno spremenljivko v regresijski enačbi. Dobimo model
Y =β0+β1XN +,
kar lahko zapišemo tudi kot β0+β1 + za osebe izbranega (ženskega) spola in kot β0+ za ostale.
• Več-vrednostne napovedne spremenljivke
Če pa imamo napovedno spremenljivko z več možnimi vrednostmi, ena nado- mestna spremenljivka ne more predstavljati vseh možnih vrednosti. Zato je po- trebno ustvariti več nadomestnih spremenljivk: po eno za vsako možno vrednost kvalitativne napovedne spremenljivke, razen ene vnaprej (in naključno) izbrane vrednosti.
2.7 Napaka napovednega modela
Glede na vrste napovednih spremenljivk ločimo več vrst napak.
Pri regresijskih modelih je bistveno to, da je ciljna spremenljivka kvantitativna.
Najpogosteje uporabljena metoda za merjenje učinkovitosti regresijskih problemov je povprečna kvadratna napaka (angl. Mean Square Error, M SE). Povprečna kva- dratna napaka se izračuna s pomočjo obrazca
M SE = 1 n
n
X
i=1
(yi−fˆ(xi))2,
kjer sta yi in xi vrednosti ciljne in neodvisnih spremenljivk za i-ti primer podane podatkovne množice z n primeri. Vrednost povprečne kvadratne napake bo majhna, če so napovedi blizu pravim odzivom, če pa je razlika med nekaterimi velika, pa bo posledično velika tudi vrednost povprečne kvadratne napake.
Pri klasifikacijskih modelih je ciljna spremenljivka kvalitativna. Veliko konceptov, ki so omenjeni pri vrednotenju regresijskih modelov, se prenese v vrednotenje klasi- fikacijskih modelov, pri tem pa moramo upoštevati, da je ciljna spremenljivka sedaj kvalitativna in ne več numerična. Uporabljan pristop za vrednotenje napake je razmerje napak (angl. error rate), ki ga izračunamo kot
ER = 1 n
n
X
i=1
I(yi 6= ˆyi),
pri čemer je I(yi 6= ˆyi) enak 1, če je yi 6= ˆyi in je I(yi 6= ˆyi) enak 0, če je I(yi = ˆyi).
Z drugimi besedami, če je napoved pravilna, bo vrnil 0, če pa napove napačno, pa bo vrnil 1.
Klasifikacijski modeli pogosto ne napovedujejo le vrednost kvalitativne ciljne spre- menljivke, temveč tudi verjetnost, da ciljna spremenljivka zavzame neko vrednost. V primeru, ko je ciljna spremenljivka binarna, tak model lahko napove le verjetnostpza eno izmed možnih vrednosti ciljne spremenljivke (saj je potem verjetnost druge možne vrednost 1−p). Pri tem klasifikacijskem modelu potem lahko prosto izbiramo prag verjetnostipT, ki odloči ali napovemo eno ali drugo vrednost ciljne spremenljivke. Obi- čajna vrednost praga je pT = 0,5, a za boljše napovedi je v določenih primerih bolje izbrati drugačno vrednost. Če vrednosti praga ne izberemo vnaprej, potem ne moremo napovedovati in zato tudi ne moremo izmeriti napovedne napake po zgornji enačbi.
Za take klasifikacijske modele imamo na voljo še eno mero njegove učinkovitosti, ploščino pod krivuljo ROC. Slednje je okrajšava za reciver operating characte- ristics, izraz iz področja radarske tehnike. Krivulja ROC se uporablja za uprizoritev točnosti podanega klasifikacijskega modela, ki napoveduje verjetnost vrednosti binarne spremenljivke za različne vrednosti odločitvenega praga pT.
Slika 2.1: Primer krivulje ROC za ustvarjen model, ki napoveduje izide tekem ene izmed ekip iz lige NBA, Atlanta Hawks.
Krivulja ROC je znana grafična upodobitev, ki sočasno prikazuje dve vrsti napak za vse možne vrednosti odločitvenih pragov. ROC je okrajšava za Receiver-Operator Characteristics, izraz, ki so ga uporabljali na področju radarske tehnike, kjer opazujejo natančnost radarskih opazovanj (Flach, 2012). Na x-osi prostora ROC nanašamo vre- dnosti (1−specifičnost), na y-osi pa občutljivost klasifikacijskega modela. Specifičnost (angl. specificity) klasifikacijskega modela merimo po enačbi
Specificity = 1− FP N ,
kjer je FP število napačno razvrščenih negativnih primerov, N je pa število vseh primerov v podatkovni množici. Podobno je občutljivost (angl. sensitivity) enaka
Sensitivity = TP P ,
kjer je TP število pravilno razvrščenih pozitivnih primerov, P pa število vseh po- zitivnih primerov v podatkovni množici. Če narišemo točke v prostoru ROC za vse možne vrednosti odločitvenih pragov in točke medsebojno povežemo, dobimo krivuljo ROC. Idealna krivulja ROC bi potekala čez levi zgornji kot, saj večja kot je ploščina pod krivuljo ROC oz. večja kot je vrednost AUC, boljši je model pri napovedovanju.
Najslabša krivulja ROC je diagonala, ki povezuje graf v točkah(0,0)in(1,1). Mogoče
se res zdi, da bi najslabša možna ROC krivulja šla skozi desni spodnji kot, bomo pa v nadaljevanju videli, da temu ni tako.
Za mero točnosti modela, ne glede na vrednost odločitvenega praga, lahko upo- rabimo ploščino pod krivuljo ROC, po angleško Area Under the ROC Curve, AUC.
Najboljša ROC krivulja ima AUC enak 1, najslabša pa AUC enak 0,5, kar pa je enako, kot če bi metali kovanec za napovedovanje, saj si s tem kaj dosti ne moremo pomagati.
Gre torej za naključni napovedni model. Če pa bi krivulja potekala skozi desni spodnji kot, bi bila vrednost AUC enaka 0. Je pa vseeno to ”dober” model, saj lahko v takem primeru napovedujemo ravno nasprotno od napovedi, ki nam jo vrne model.
Kot je že opisano zgoraj, želimo za svojo napoved imeti graf takšne oblike, da se čim bolj približa levemu zgornjemu kotu. Bolj kot se mu približa, boljši je napovedni model. Na sliki 2.1 je vidno, da gre za obliko grafa, ki bolje napove rezultate, kot če bi jih napovedovali naključno. Vrednost ploščine pod ROC krivuljo (AUC) na sliki 2.1 je 0,6339.
2.8 Ocenjevanje napovedne napake modela
Tudi če ima model majhno napako na učni množici, ni nujno, da bo odziv enak na testni množici. Ekstremni primer je npr., da če pride do preprileganja na učnih podatkih (množici), bo vrednost testne povprečne kvadratne napake zelo velika, ker vzorcev, ki jih je metoda našla v učni množici, v testni množici ne bo.
Pomembna lastnost, ki velja ne glede na dane podatke in izbrano metodo strojnega učenja, je značilna za povprečno kvadratno napako. Povprečna kvadratna napaka se na učni množici, ko povečamo fleksibilnost modela, zmanjša. Pri testnih podatkih pa se zgodi situacija, da nekaj časa povprečna kvadratna napaka pada, ko povečujemo fleksibilnost modela, potem pa se v neki točki obrne in začne ponovno naraščati. Tako dobimo, če grafično upodobimo te meritve, graf v obliki črke U (vidno na sliki 2.2).
Na x-osi slike 2.2 se nahajajo modeli različnih kompleksnosti. Za kompleksnejše modele velja, da imajo manjši predsodek in večjo varianco. Ravno nasprotno pa velja za enostavnejše modele, ki imajo večji predsodek in manjšo varianco. Zato temu pojavu rečemo kompromis med predsodkom in varianco (angl. bias-variance trade-off).
Ker vrednosti povprečne kvadratne napake ne poznamo vnaprej, jo lahko ocenimo s pomočjo spodnje enačbe:
E(y0 −fˆ(x0))2 =V ar(ˆ[f](x0)) + [Bias( ˆf(x0))]2+V ar(),
pri čemer je E(y0−f(xˆ 0))2 pričakovana testna povprečna kvadratna napaka. Iz te enačbe lahko vidimo, da če želimo zmanjšati testno povprečno kvadratno napako, mo- ramo izbrati metodo, ki hkrati doseže nizko varianco in nizek predsodek (angl. bias).
Bias pa je predsodek, ki se nanaša na napako, katera nastane pri približku realnega (življenjskega) problema, ki je zelo zapleten, če uporabljamo preprostejši model.
Kot že omenjeno, načeloma velja, da pri uporabi bolj fleksibilnih metod varianca
Slika 2.2: Rdeča krivulja predstavlja povprečno kvadratno napako za testne podatke, siva krivulja pa povprečno kvadratno napako za učne podatke (James in drugi, 2013).
naraste, predsodek pa upade, zato po navadi iščemo metodo, pri kateri sta kvadrat predsodka in varianca zelo majhna.
Zgoraj opisani primer poda jasno sliko, da napake ne moremo oz. ne smemo meriti na učni množici. Meriti jo moramo na množici podatkov, ki jih nismo uporabili za učenje določenega modela in jih imenujemo testni podatki. Njihova množica se imenuje testna množica. Za ločevanje učnih in testnih primerov na področju strojnega učenja uporabljamo metode vzorčenja podane podatkovne množice.
Metode vzorčenja(angl. resampling methods) so nepogrešljivo orodje v moderni statistiki. Vključujejo ponavljajoče se sestavljanje vzorcev iz učne množice in ponovno treniranje modela na vsakem vzorcu z namenom, da bi pridobil dodatne informacije o treniranem modelu.
Metode vzorčenja so lahko računsko potratne, ker zajemajo učenje iste statistične metode večkrat, pri čemer uporabljajo podmnožice učne množice podatkov. Res pa je, da je tehnologija napredovala do te mere, da to ni več velika težava. Najbolj po- gosti metodi vzorčenja sta prečno preverjanje (angl. cross-validation) in zankanje (angl.bootstrap). Obe metodi sta pomembni orodji za veliko statističnih učnih metod.
Prečno preverjanje se lahko uporablja za ocenjevanje testne napake, glede na izbrano metodo strojnega učenja, z namenom da nam vrne oceno napake, kako dobra je, ali pa za primerno izbiro fleksibilnosti modela.
Procesu vrednotenja kakovosti modela rečemoocenjevanje modela (model asses- sment), procesu izbire primerne fleksibilnosti modela pa izbira modela (angl. model selection).
2.8.1 Prečno preverjanje (cross-validation)
Testna napaka je povprečna napaka, ki je posledica uporabe metode strojnega učenja za napoved ciljne spremenljivke na novih opazovanjih . Gre torej za meritev, ki ni bila
uporabljena pri učenju modela. Testna napaka je po navadi težko izmerljiva oz. jo je težko izračunati, saj vnaprej ne poznamo podatkov kot je to pri učni množici, kjer učno napako lahko izračunamo. Da pa to dosežemo, obstaja nekaj pristopov, kateri razpoložljivo množico podatkov razdelijo na dve množici, učno in testno, ter nam tako omogočijo, da izračunamo testno napako na modelu, ki je bil naučen na učni množici podatkov.
2.8.1.1 Pristop preverjanja množic
Pristop preverjanja množic je preprosta strategija, ki naključno razdeli množico raz- položljivih podatkov na dva dela, tj. na učno množico (angl. training set) in testno množico (angl. validation set ali hold-out set). Dan model učimo na učni množici, naučen model pa uporabimo za napoved ciljne spremenljivke za opazovanja v testni množici.
Če postopek delitve na dve množici ponovimo, bomo za dani model dobili različne vrednosti napake, saj bo množica drugače razdeljena kot v prejšnjem primeru. Kon- ceptualno je ta pristop lahko razumljiv in izvedljiv. Vendar pa lahko naletimo na dve težavi, ki sta lahko ključnega pomena za naš model. Prva je ta, da je lahko ocena testne napake močno variabilna, kar pa je odvisno od tega, katera opazovanja so vključena v učno množico in katera v testno množico. Druga je ta, da je le podmnožica opazo- vanj vključena v učenje modela, druga podmnožica pa je prej uporabljena za učenje modela. Glede na to, da metode strojnega učenja po navadi vrnejo slabše rezultate na učni množici (po navadi je ta majhna), to pomeni, da bi lahko dobili preveliko vrednost testne napake, če bi model naučili na celotni učni množici.
2.8.1.2 LOOCV
LOOCV je okrajšava za Leave-One-Out Cross-Validation, ki je tesno povezana s pre- verjanjem množic, le da poskuša rešiti težave tega pristopa.
Prav tako kot pri preverjanju množic LOOCV razdeli množico podatkov na dva dela. Ampak namesto, da ustvari množici, ki sta približno istih velikosti, je pri njem samo eno opazovanje (x1, y1) uporabljeno v testni množici, ostala opazovanja pa so v učni množici. To pomeni, da model učimo na(n−1)podatkih (velikost učne množice je (n−1)), napovedyˆ1 pa je narejena na tistem opazovanju, ki ga ni v učni množici, pri uporabi vrednostix1.
Ker opazovanje (x1, y1) ni bilo uporabljeno v procesu učenja modela, M SE1 = (y1−yˆ1)2 poda oceno testne napake skoraj brez predsodka. Čeprav je M SE1 brez predsodka za testno napako, gre vseeno za slabo oceno, ker ima ta visoko variabilnost, saj je odvisen od opazovanje(x1, y1). Zgornji proces lahko ponavljamo na ta način, da vsakič drugo, različno opazovanje, pustimo za tesno množico. Tako bomo vsakič znova izračunali M SEi za vsako opazovanje podanega n . Tako LOOCV oceni testni MSE
kot povprečje teh ocen napak, ki smo jih izračunali n-krat, CV(n) = 1
n
n
X
i=1
M SEi.
LOOCV ima kar nekaj prednosti pred preverjanjem množic, saj ima manjši pred- sodek (angl. bias). Prav zaradi svojega načina izbiranja učne in testne množice ne vrne previsoke testne napake. Kot drugo pa bo LOOCV vedno vrnil iste rezultate, saj naključnosti delitve množice podatkov tukaj ni. Obstaja pa možnost, da je LOOCV potraten za izvedbo, saj je potrebno model učitin-krat. Težava nastane, ko je vrednost n velika. LOOCV je splošna metoda, ki je lahko uporabljena pri različnih napovednih modelih. Lahko ga uporabimo npr. pri logistični regresiji, linearni diskriminantni analizi in drugih.
2.8.1.3 Prečno preverjanje s k grupami
Prečno preverjanje s k grupami (angl. k-fold cross-validation) je alternativa LOOCV.
Pri tem prečnem preverjanju gre za naključno deljenje množice opazovanj v k grup (angl. groups, folds), ki so približno enake velikosti.
Prva grupa je uporabljena za testno množico, na preostalihk−1 grupah pa model učimo. M SE1 je potem izračunan s pomočjo opazovanj prve, učne grupe. Tako nare- dimo podobno kot pri LOOCV za vsako drugo učno grupo ter s tem dobimo k ocen za testno napako, M SE1, M SE2,. . . ,M SEk. Tako se ocena prečnega preverjanja s k grupami izračuna kot povprečje teh vrednosti
CV(k) = 1 k
k
X
i=1
M SEi.
Brez težav se opazi, da je LOOCV poseben primer prečnega preverjanja skgrupami, kjer je k =n. Po navadi za prečno preverjanje s k grupami izberemo koeficient k = 5 ali k = 10, saj je njegova glavna prednost v tem, da je bolj optimalno za izračun in lažje izvedljivo.
Ko se ukvarjamo z realnimi podatki, ne poznamo prave vrednosti testnega MSE in je zaradi tega težko določiti, kakšna je natančnost ocene prečnega preverjanja. Pri uporabi prečnega preverjanja je naš cilj lahko ta, da vidimo, kako dobro se bo metoda strojnega učenja odzvala na podatkih, torej nas zanima testni MSE.
Spet drugič pa nas lahko zanima, kje je minimum na grafu ocenjenega testnega MSE. To pa s tem razlogom, ker lahko uporabimo prečno preverjanje na več metodah strojnega učenja ali pa na eni sami z različnimi nivoji fleksibilnosti z namenom, da dobimo tisto metodo, ki bo imela najmanjšo testno napako. V tem primeru nas torej ne zanima konkretna vrednost MSE, ampak nas zanima, kje na grafu testnega MSE je minimum.
2.8.1.4 Bias-variance trade-off za prečno preverjanje s k grupami
Prečno preverjanje s k grupami pogosto poda natančnejšo oceno testne napake, kot pa LOOCV. Vzrok pa je bias-variance trade-off. Kot že povedano, LOOCV poda oceno testne napake z zelo majhnim oz. skoraj ničelnim predsodkom, medtem ko jo prečno preverjanje s k grupami poda z zmernim predsodkom (ni zelo velik in ni zelo majhen). S tega vidika je boljša izbira LOOCV. Če pa pogledamo še z druge strani, pa vemo, da ima LOOCV večjo varianco kot pa prečno preverjanje s k grupami, če je k < n. Dokazano je, da je najboljša izbira k = 5 ink = 10, saj ocena testne napake ni pod vplivom previsokega predsodka in previsoke variance.
2.8.1.5 Prečno preverjanje pri klasifikacijskih problemih
Prečno preverjanje je lahko zelo uporabno tudi v klasifikacijskih problemih, kjer je Y kvalitativen. Prečno preverjanje pri klasifikacijskih problemih deluje na isti način, kot je že bilo do sedaj opisano za regresijske probleme, le da namesto MSE v tem primeru uporabimo število napačno napovedanih opazovanj. Tako na primer pri klasifikacijskih problemih LOOCV napako izračunamo kot
CV(n)= 1 n
n
X
i=1
Erri,
kjer je Erri =I(yi 6= ˆyi). Napaki za prečno preverjanje s k grupami in za preverjanje množic sta definirani analogno.
2.8.2 Zankanje
Zankanje (angl. bootstrap) je zelo široko uporabljeno in močno orodje, ki se uporablja za izračun negotovosti, ki je povezan z dano metodo strojnega učenja. Kot primer se lahko zankanje uporablja za ocenjevanje napake koeficientov pri naučenem modelu linearne regresije.
Uporabnost zankanja je skrita v dejstvu, da ga je mogoče uporabiti na veliko me- todah strojnega učenja, vključujoč tiste, za katere je sicer variabilnost težje izračunati.
Zankanje pomaga zmanjšati varianco in igra veliko vlogo pri izogibanju preprileganju.
Po navadi se uporablja na drevesnih metodah strojnega učenja.
2.9 Linearni modeli za klasifikacijo
Model linearne regresije predvideva, da je ciljna spremenljivka Y kvantitativna. Veli- kokrat pa je ciljna spremenljivka kvalitativna. Preprost primer je napovedovanje barve oči, kjer je ciljna spremenljivka (barva oči) kvalitativna. Za kvalitativne spremenljivke se uporablja tudi izraz kategorična spremenljivka.
Pristop za napovedovanje kvalitativnih spremenljivk se imenujeklasifikacija. Naj- pogosteje uporabljeni klasifikatorji sologistična regresija,linearna diskriminantna ana-
liza, k - najbližjih sosedov (kNN). Poleg teh sem se osredotočil še na dve metodi, in sicer drevesa ter naključne gozdove, ki bosta pojasnjeni v samostojnih poglavjih.
Linearna regresija ni primerna v situacijah, ko so ciljne spremenljivke kvalitativne.
Težava nastane pri tem, da ne glede na to, kakšne kvantitativne vrednosti pripišemo kvalitativnim vrednostim, se v splošnem kvalitativnih spremenljivk ne da opisati z kvantitativnimi. Različna kodiranja kvalitativnih spremenljivk bi pomenila povsem različne linearne modele, kar bi posledično vodilo do različnih množic napovedi na te- stnih opazovanjih. Če bi obstajala naravna pot za kodiranje kvalitativnih spremenljivk po neki jakostni lestvici, kar je v praksi skoraj nemogoče, potem bi bilo te spremenljivke smiselno kodirati.
Če imamo ciljno spremenljivko z dvema možnima vrednostma (binarno), se situacija bistveno olajša. Ti dve vrednosti lahko zakodiramo z eno novo spremenljivko in na tak način bi lahko uporabili linearno regresijo, z nekaj dodatnimi pogoji. Ker pa je veliko ciljnih spremenljivk, ki imajo več kot dve možni vrednosti, pa je to težko posplošiti in je v tem primeru potrebno uporabiti klasifikacijske metode.
2.9.1 Logistična regresija
Logistična regresija ne modelira direktno Y samega, pač pa modelira verjetnost, da Y pripada določeni kategoriji.
2.9.1.1 Logistični model
Potrebno je modelirati p(X) z uporabo funkcije, ki vrne vrednosti med 0 in 1 za vse vrednosti X. Pri logistični regresiji se uporablja logistična funkcija
p(X) = eβ0+β1X 1 +eβ0+β1X.
Da model naučimo, uporabimo metodo, ki se ji reče največja okolica (angl. maximum likelihood). Če malce preoblikujemo zgornjo enačbo, vidimo, da velja
p(X)
1−p(X) =eβ0+β1X.
Razmerje p(X)/[1−p(X)]lahko zavzame katero koli vrednost med 0 in ∞. Če loga- ritmiramo obe strani zgornje enačbe, dobimo
log
p(X) 1−p(X)
=β0+β1X,
levi strani enačbe rečemo logaritmična verjetnost (angl. log-odds oz. logit).
