Doktorska disertacija
Kompleksna vozlišča v drevesih za napovedovanje strukturiranih vrednosti
Ogledi: 5 | Prenosi: 3
Povzetek
Tema te disertacije je integracija kompleksnih vozlišč v drevesa za napovedno razvrščanje
(DNR). DNR-ji so uveljavljeni modeli v strojnem učenju, ki jih lahko uporabimo za vrsto
različnih nalog, med drugim napovedovanje strukturiranih vrednosti in polnadzorovano
učenje. Zgrajeni so s požrešnim rekurzivnim algoritmom, ki ima dve šibki točki. Prva
težava je njegova kratkovidnost, ki je posledica požrešnosti in pomeni, da so naučena
drevesa redko optimalna. Druga težava pa je računska zahtevnost učenja testov v delitvenih
vozliščih drevesa, ki hitro narašča s številom izhodnih spremenljivk. To pride še posebej
do izraza pri napovedovanju strukturiranih vrednosti.
Za zmanjšanje kratkovidnosti uporabimo opcijska vozlišča in predlagamo opcijske DNRje.
Ko naletimo na več testov, ki izgledajo podobno dobri kot najboljši med njimi, opcijski
DNR-ji ne izberejo samo najboljšega, ampak združijo vse alternative v opcijsko vozlišče.
Za vsako alternativo se potem drevo normalno gradi naprej. Ko z zgrajenim opcijskim
DNR-jem delamo napovedi, opcijsko vozlišče primere posreduje vsem vsebujočim alternativam.
Vsaka izmed njih pripravi svojo napoved, le-te pa se potem združi v končno
napoved drevesa. Opcijske DNR-je smo evalvirali na več nalogah napovedi strukturiranih
podatkov: večciljni regresiji, večoznačni klasifikaciji in hierarhični večoznačni klasifikaciji.
Cilj empiričnih raziskav je bil raziskati vpliv števila opcijskih vozlišč na napovedno moč
dreves in njihovo velikost, ki ključno vpliva na zmožnost razlage naučenih modelov. Rezultati
kažejo, da imajo opcijski DNR-ji z malo opcijskimi vozlišči boljšo napovedno moč
od navadnih DNR-jev, še vedno pa ostanejo razložljivi. Po drugi strani pa so napovedna
moč, velikost modelov in čas učenja opcijskih DNR-jev z veliko opcijskimi vozlišči podobni
tem od ansamblov DNR-jev.
Da izboljšamo računsko zahtevnost učenja DNR-jev, jih razširimo s poševnimi delitvenimi
vozlišči, ki v svojih testih uporabljajo linearne kombinacije značilk. Takšna drevesa
poimenujemo poševni DNR-ji in predlagamo dve metodi za njihovo konstrukcijo. MPV
različica najprej razvrsti primere v dve skupini na podlagi izhodnih vrednosti in tako
dobi idealno delitev, potem pa s pomočjo linearne metode podpornih vektorjev poišče približek
te delitve na podlagi značilk. Gradientna različica pa definira odvedljiv približek
kriterijske funkcije, ki jo za ocenjevanje delitev uporabljajo navadni DNR-ji, za učinkovito
optimizacijo testa pa uporabi gradientne optimizacijske metode. Predlagani varianti
izboljšata časovno zahtevnost algoritma na problemih z več izhodnimi spremenljivkami,
dodatne računske prihranke pa nudita na redkih podatkih. Računsko prednost najprej potrdimo
s teoretično analizo računske zahtevnosti, nato pa še z empirično študijo. Rezultati
eksperimentov pokažejo tudi to, da poševni DNR-ji ohranijo ali celo izboljšajo vrhunsko
napovedno moč navadnih DNR-jev. Tudi evalvacija v kontekstu polnadzorovanega učenja
prikaže podobno sliko: poševni DNR-ji so hitrejši in imajo pogosto tudi boljšo napovedno
moč. Predstavimo tudi način, kako lahko iz naučenih poševnih DNR-jev pridemo do ocen
pomembnosti značilk, za katere z eksperimenti pokažemo, da so smiselne.