Disambiguace v´yznamu slov Z´avˇereˇcn´a zpr´ava Petra Baranˇc´ıkov´a 2012/13
1
Popis u ´ lohy
C´ılem projektu je automaticky pˇriˇradit v´ıceznaˇcn´emu slovu jeho v´ yznam na z´akladˇe vˇety, ve kter´e bylo pouˇzito. Konkr´etnˇe se jednalo o tˇri anglick´a slova - podstatn´e jm´eno ”line”, sloveso ”serve”a adjektivum ”hard”. K tomu m´ame k dispozici data - soubory s vˇetami a konkr´etn´ımi v´ yznamy v nich. Spr´avn´e urˇcen´ı v´ yznamu slova m´ a velk´ y v´ yznam v lingvistice a pˇri zpracov´an´ı pˇr´ırozen´eho jazyka. Lze ho aplikovat pˇri ve strojov´em uˇcen´ı, napˇr´ıklad pr´avˇe slovo ”line”m˚ uˇze b´ yt podle sv´eho v´ yznamu pˇrekl´ ad´ ano jako napˇr´ıklad ”ˇc´ara”, ”linka”, ”ˇrada”, ”fronta”, ”ˇr´adek”, ”pozn´amka”, ”ˇsn ˇ˚ ura”, ”kabel”, ”spojen´ı”, ”trasa”, ”obor”, ”rozdˇelen´ı”a mnoh´a dalˇs´ı. V´ yznam m´ a ale i v mnoha jin´ ych odvˇetv´ıch jako napˇr´ıklad pˇri dob´ yv´an´ı informac´ı, odvozov´an´ı z kontextu, diskurzn´ı anal´ yze, odpov´ıd´an´ı na ot´azky a dalˇs´ıch... Prvn´ım krokem pˇri automatick´e disambiguaci je extrahovat z tˇechto vˇet takov´e atributy, kter´e maj´ı vliv na v´ yznam dan´eho slova. To m˚ uˇze b´ yt tˇreba spojen´ı s konkr´etn´ı pˇredloˇzkou, pˇredmˇetem, pozice ve vˇetˇe, nebo tagy okoln´ıch slov. Na z´akladˇe tˇechto atribut˚ u je potom moˇzn´e natr´enovat klasifik´ator, kter´ y by urˇcoval co nejspolehlivˇeji spr´avn´ y v´ yznam slova.
2
Data
K dispozici jsou tˇri soubory s daty hard.devel/serve.devel/line.devel. Kaˇzd´ y z nich obsahuje pˇr´ıklady pro jedno slovo. Pro kaˇzd´ y z pˇr´ıklad˚ u jsou uvedeny tyto informace: • ID - identifikaˇcn´ı ˇc´ıslo dan´e vˇety • SENSE - v´ yznam slova v t´eto vˇetˇe, tj. tˇr´ıda, kterou chceme urˇcit • SENTENCE - upraven´ a vˇeta s vyznaˇcen´ ym c´ılov´ ym slovem, u ´prava spoˇc´ıv´a v pˇreveden´ı vˇsech p´ısmen na mal´e a vloˇzen´ı mezer mezi vˇsechny prvky vˇety, tj. slova i diakritiku • MORPH - automaticky z´ıskan´a morfologick´a anal´ yza vˇety • WLT - automaticky z´ıskan´ a morfologick´a anal´ yza vˇety v alternativn´ım form´atu slovo/lemma/morfologick´ y tag • PARSE - seznam syntaktick´ ych z´avislost´ı, tak´e z´ıskan´ y automaticky pomoc´ı Stanford dependency parseru 1
2.1
Rozdˇ elen´ı dat
N´asleduj´ıc´ı tabulka obsahuje poˇcty pˇr´ıklad˚ u pro kaˇzd´e slovo. Mnoˇzstv´ı pouˇzit´ ych vˇet neodpov´ıd´a celkov´emu poˇctu vˇet, protoˇze nˇekter´e vˇety v datech neobsahovaly poˇzadovan´e slovo a byly proto vynech´ any. slovo
hard
line
serve
pˇr´ıklad˚ u v datech pouˇzit´ ych pˇr´ıklad˚ u
3833 3831
3646 3591
3878 3847
Tabulka 1: Poˇcet pˇr´ıklad˚ u Data jsem nerozdˇelovala na pevnˇe dan´e tr´enovac´ı, v´ yvojov´a a testovac´ı data. M´ısto toho jsem radˇeji pouˇz´ıvala kˇr´ıˇzovou validaci. Pˇri n´ı byla data n´ahodnˇe rozdˇelena na deset stejnˇe velk´ ych podmnoˇzin. Na kaˇzd´e z tˇechto podmnoˇzin jsem pot´e vyhodnocovala mo9 del natr´enovan´ y na komplementu t´eto mnoˇziny, tj. zbyl´ ych 10 dat. Obdobnˇe pˇri ladˇen´ı modelu, kdy ale bylo voleno rozdˇelen´ı pouze na 8 podmnoˇzin, protoˇze ladˇen´ı model˚ u bylo ˇcasovˇe n´ aroˇcn´e.
2.2
Urˇ covan´ e tˇ r´ıdy
Rozdˇelen´ı jednotliv´ ych tˇr´ıd v datech nebylo rovnomˇern´e, vˇetˇsinou jedna tˇr´ıda v´ yraznˇe dominovala, viz. tabulky 2, 3 a 4. v´ yznam HARD1 poˇcet pˇr´ıklad˚ u 3056 pod´ıl ze vˇsech 79.8%
HARD2 447 11.7%
HARD3 328 8.6%
Tabulka 2: Rozdˇelen´ı tˇr´ıd u hard HARD1 oznaˇcuje n´ aroˇcn´e, sloˇzit´e, vyˇzaduj´ıc´ı znaˇcn´e u ´sil´ı, HARD2 znamen´a tvrd´e metaforicky, tˇeˇzk´e (napˇr. ostr´ y pohled, tvrd´a pr´ace) a HARD3 naopak fyzicky tvrd´e, pevn´e, ˇspatnˇe zlomiteln´e ˇci ohnuteln´e. S ohledem na bˇeˇznou mluvu se i zd´a docela pˇrirozen´e, ˇze se HARD1 vyskytuje v datech v´ yraznˇe ˇcastˇeji neˇz ostatn´ı tˇr´ıdy. I pro serve a line je to velmi podobn´e - dominuj´ıc´ı tˇr´ıda je ta v jazyce nejˇcastˇeji pouˇz´ıvan´a. v´ yznam cord poˇcet pˇr´ıklad˚ u 332 pod´ıl 9.2%
division 321 8.9%
formation 295 8.2%
phone 378 10.5%
product 1913 53.3%
text 352 9.8%
Tabulka 3: Rozdˇelen´ı tˇr´ıd u line SERVE10 pˇredstavuje pod´ avat nˇekomu j´ıdlo ˇci pit´ı, SERVE12 vykon´avat urˇcit´e zamˇestn´ an´ı, povinnost ˇci sluˇzbu. SERVE2 znamen´a hr´at urˇcitou roli, m´ıt specifick´e 2
v´ yznam SERVE10 poˇcet pˇr´ıklad˚ u 1586 pod´ıl ze vˇsech 41.2%
SERVE12 1119 29.1%
SERVE2 753 19.6%
SERVE6 389 10.1%
Tabulka 4: Rozdˇelen´ı tˇr´ıd u serve vyuˇzit´ı a v´ yznamem SERVE6 je poskytovat (oblasti ˇci skupinˇe lid´ı) sluˇzbu ˇci produkt.
2.3
V´ ybˇ er atribut˚ u
Dalˇs´ım krokem je v´ ybˇer atribut˚ u. Ty je potˇreba zvolit tak, aby byly relevantn´ı a aby jejich kombinace dok´ azala odhadnout spr´avnou tˇr´ıdu i pro slovo s dosud nezn´am´ ym v´ yznamem. Jedn´ a se proto o velmi podstatnou ˇc´ast cel´eho u ´kolu. hard 27
line 60
serve 45
Tabulka 5: Poˇcet atribut˚ u V´ yznam slova lze urˇcit pouze na z´ akladˇe kontextu.[2] Zamˇeˇrila jsem se proto pˇrev´aˇznˇe na slova, kter´e se v kontextu jednoho v´ yznamu objevovaly v´ yraznˇe ˇcastˇeji neˇz u jin´eho. Konkr´etnˇe jsem si udˇelala frekvenˇcn´ı anal´ yzu slov v bezprostˇredn´ım okol´ı urˇcovan´eho slova a vybrala z nich takov´e, kter´e se pro jednu tˇr´ıdu vyskytovaly v´ yraznˇe ˇcastˇeji neˇz pro ostatn´ı. Na jej´ım z´ akladˇe jsem si pro tuto tˇr´ıdu spoˇc´ıtala pravdˇepodobnost Pdata (tˇr´ıda|mnoˇzina slov). Tu jsem potom posuzovala individu´alnˇe - pokud se mi zd´ala dostateˇcnˇe vysok´a, vytvoˇrila jsem atribut, kter´ y testuje pˇr´ıtomnost slov z mnoˇziny na dan´e pozici. V opaˇcn´em pˇr´ıpadˇe jsem ji nevyuˇzila, nebo zkusila vyˇradit z mnoˇziny ty slova, kter´e hodnotu Pdata (tˇr´ıda|mnoˇzina slov) sniˇzovaly. Obecnˇe plat´ı, ˇze jsem pro m´enˇe ˇcast´e tˇr´ıdy ponech´avala atributy s niˇzˇs´ı hodnotou, neˇz pro tu nejfrekventovanˇejˇs´ı resp. i takov´e atributy, kter´e dobˇre oddˇelovaly v´ıce m´enˇe ˇcast´ ych tˇr´ıd od t´e nejˇcastˇejˇs´ı. Minim´aln´ı velikost mnoˇziny slov, aby mohla tvoˇrit atribut, jsem stanovila na 5 v´ yskyt˚ u v datech. Kromˇe v´ yskytu konkr´etn´ıho slova v nejbliˇzˇs´ım okol´ı jsem stejn´ ym zp˚ usobem vyb´ırala atributy mezi slovn´ımi tvary urˇcovan´eho slova, morfologick´ ymi tagy v jeho okol´ı, slovy, se kter´ ymi se spojovalo v urˇcit´e syntaktick´e z´avislosti, urˇcit´ ymi syntaktick´ ymi funkcemi obecnˇe, pˇredloˇzkami, se kter´ ymi se ˇcasto spojovalo a dalˇs´ımi. Protoˇze kaˇzd´e slovo je jin´eho slovn´ıho druhu, jsou i relevantn´ı atributy pro nˇe velmi odliˇsn´e a vyb´ırala jsem je proto zvl´aˇst’. Jejich celkov´ y poˇcet je v tabulce 5 a kompletn´ı seznam je v souborech hard.pl, line.pl a serve.pl, kter´e slouˇz´ı tak´e k jejich extrakci z dat. Vˇsechny atributy jsou bin´ arn´ı a vybran´e z hladin SENTENCE, MORPH a PARSE. Zde je pˇr´ıklad konkr´etn´ıho atributu pro slovo hard pro kaˇzdou hladinu: • SENTENCE - po hard n´ asleduje abstraktn´ı podstatn´e jm´eno jako look, feeling, evidence, truth, edge, work ; Pdata (HARD2|hard {look, feeling,...}) = 0.93 • MORPH - po hard n´ asleduje tag TO (tj. slovo to); Pdata (HARD1|hard to) = 0.99 3
• PARSE - hard se poj´ı s pˇredloˇzkou for ; Pdata (HARD1|prep for(hard,*)) = 0.99 Po z´ısk´an´ı mnoˇziny atribut˚ u jsem ji jeˇstˇe zkouˇsela redukovat. K tomu existuje nˇekolik d˚ uvod˚ u. Prvn´ı je, ˇze velk´e mnoˇzstv´ı atribut˚ u zpomaluje algoritmy a vyˇzaduje mnoho m´ısta. Tento v m´em pˇr´ıpadˇe nebyl tolik d˚ uleˇzit´ y, protoˇze mnoˇzstv´ı extrahovan´ ych atribut˚ u nebylo nijak z´ avratn´e. Podstatnˇejˇs´ı d˚ uvod je, ˇze pokud jsou mezi nimi nevhodnˇe zvolen´e rysy, mohou vytv´ aˇret ˇsum a v´ ysledky klasifik´ator˚ u jsou potom n´achylnˇejˇs´ı k chyb´am. Ide´ aln´ı je proto menˇs´ı optim´ aln´ı mnoˇzina atribut˚ u.[3] Pˇr´ıliˇs mnoho atribut˚ u tak´e m˚ uˇze zp˚ usobit pˇretr´enov´ an´ı modelu a ten potom nen´ı schopen spr´avnˇe pˇredpov´ıdat pro dosud nevidˇen´ a data. Z mnoha moˇzn´ ych postup˚ u jsem zvolila dvˇe metody pro redukci poˇctu atribut˚ u Borutu a zpˇetn´e vyˇrazov´ an´ı.
2.3.1
Boruta
Jedn´a se o algoritmus pro v´ ybˇer d˚ uleˇzit´ ych atribut˚ u. Je zaloˇzen na klasifikaˇcn´ım algoritmu n´ahodn´eho lesa.1 D˚ uleˇzitost atributu je poˇc´ıt´an´a jako pokles pˇresnosti klasifikace zp˚ usoben´ y n´ ahodnou permutac´ı hodnot atribut˚ u mezi pˇr´ıklady. Ze vˇsech strom˚ u v lese, kter´e pouˇz´ıvaj´ı dan´ y atribut pro klasifikaci, se vypoˇc´ıt´a pr˚ umˇer a standardn´ı deviaci ze ztr´aty pˇresnosti. Z-sk´ ore je potom pr˚ umˇer podˇelen´ y standardn´ı deviac´ı. Boruta konkr´etnˇe funguje tak, ˇze pro kaˇzd´ y atribut se vytvoˇr´ı jeho kopii, tzv. st´ınov´ y atribut, jehoˇz se hodnoty n´ ahodnˇe prom´ıchaj´ı. Na vˇsech atributech se pust´ı algoritmus n´ahodn´eho lesa a pro kaˇzd´ y z nich spoˇc´ıt´a Z-sk´ore. Nalezne se maxim´aln´ı hodnota Z-sk´ore mezi st´ınov´ ymi atributy a ta se porovn´a s kaˇzd´ ym dosud nerozhodnut´ ym atributem. Ty, jejichˇz d˚ uleˇzitost je v´ yznamnˇe niˇzˇs´ı, jsou oznaˇceny jako ned˚ uleˇzit´e a odstranˇeny, zat´ımco ty kter´e maj´ı d˚ uleˇzitost v´ yznamnˇe vyˇsˇs´ı jsou oznaˇceny jako d˚ uleˇzit´e. Pot´e se odstran´ı st´ınov´e atributy a cel´ y proces se opakuje, dokud nemaj´ı vˇsechny atributy pˇriˇrazenou d˚ uleˇzitost.[1] hard 2
line 15
serve 8
Tabulka 6: Poˇcet atribut˚ u vyˇrazen´ ych Borutou Tento algoritmus je souˇc´ ast´ı bal´ıˇcku Boruta pro jazyk R. Konkr´etnˇe jsem ho spouˇstˇela pˇr´ıkazem Boruta(V1 ∼ ., data = a, confidence = 0.95) pro 95% jistotu toho, ˇze je dan´ y atribut lepˇs´ı neˇz n´ ahodn´ a permutace hodnot. Z´akladn´ı nastaven´ı je 99.9%, ale to je velmi ˇcasovˇe n´ aroˇcn´e. Atributy, o kter´ ych se algoritmus nedok´azal rozhodnout, jsem ponechala. Konkr´etn´ı vyˇrazen´e atributy a naopak atributy, kter´e Boruta oznaˇcila jako nejd˚ uleˇzitˇejˇs´ı jsou souˇc´ ast´ı pˇr´ılohy, stejnˇe jako grafy d˚ uleˇzitosti atribut˚ u pro jednotliv´a slova. 1
viz kapitola 3.1.
4
2.3.2
Zpˇ etn´ e vyˇ razov´ an´ı
Tento algoritmus nen´ı zaloˇzen nutnˇe na konkr´etn´ım klasifik´atoru, zde byl konkr´etnˇe pouˇz´ıv´an na k-NN2 a SVM3 pˇri z´ akladn´ım nastaven´ı. Model je nejprve natr´enov´an na vˇsech atributech. Potom se postupnˇe odeb´ır´a po kaˇzd´em atributu a spoˇc´ıt´a se pˇresnost modelu. Atribut, jehoˇz odstranˇen´ım se nejv´ yˇse zv´ yˇsila pˇresnost klasifik´atoru, je odebr´an a cel´ y proces se opakuje do t´e chv´ıle, kdy se odstranˇen´ım atributu pˇresnost klasifik´atoru uˇz nezv´ yˇs´ı. Pokusy se zpˇetn´ ym v´ ybˇerem atribut˚ u jsem nˇekolikr´at opakovala a nakonec odebrala ty atributy, kter´e byly vyˇrazeny ve vˇetˇsinˇe pˇr´ıpad˚ u. Alternativn´ı moˇznost´ı je tak´e obr´ acen´ y algoritmus, kdy se postupnˇe pˇrid´av´a po jednom atributu, kter´ y nejv´ıce zvyˇsuje pˇresnost modelu, dokud se pˇrid´an´ım nov´eho atributu pˇresnost zv´ yˇs´ı. Kaˇzd´ y z tˇechto postup˚ u m´a sv´e v´ yhody a nev´ yhody. Pˇrid´av´an´ı po jedn´e m˚ uˇze opom´ıjet ty atributy, kter´e funguj´ı dobˇre ve spoleˇcn´e kombinaci a naopak odeb´ır´an´ı m˚ uˇze b´ yt velmi v´ ypoˇctovˇe n´ aroˇcn´e, pokud staˇc´ı pouˇz´ıt p´ar atribut˚ u z velk´e mnoˇziny. Zde jsem zvolila zpˇetn´ y postup, protoˇze mnoˇzstv´ı extrahovan´ ych atribut˚ u nen´ı pˇr´ıliˇs vysok´e. V tabulce 7 je poˇcet vyˇrazen´ ych atribut˚ u pomoc´ı zpˇetn´eho vyˇrazov´an´ı pro SVM a kNN. Pro n´ ahodn´ y les se mi zd´ ala dostateˇcn´a Boruta. Konkr´etn´ı vyˇrazen´e atributy jsou souˇc´ast´ı pˇr´ılohy.
k-NN SVM
hard 3 3
line 6 4
serve 4 3
Tabulka 7: poˇcet vyˇrazen´ ych atribut˚ u Je zaj´ımav´e, ˇze shoda mezi algoritmy nebyla vˇetˇsinou pˇr´ıliˇs vysok´a. Napˇr´ıklad pro serve se shodly pouze Boruta a zpˇetn´e vyˇrazov´an´ı pomoc´ı k-NN a to na jedin´em atributu. Naopak u line tvoˇrily atributy vyˇrazen´e zpˇetnˇe pro k-NN podmnoˇzinu vyˇrazen´ ych Borutou. T´ımto zp˚ usobem jsem pro kaˇzd´e slovo z´ıskala ˇctyˇri r˚ uzn´e mnoˇziny atribut˚ u, kter´e jsem d´ale pouˇz´ıvala k tr´enov´ an´ı model˚ u. Nicm´enˇe nejlepˇs´ıch v´ ysledk˚ u bylo vˇetˇsinou dosaˇzeno stejnˇe na p˚ uvodn´ı, neredukovan´e mnoˇzinˇe atribut˚ u.
3
Teoretick´ y popis model˚ u
3.1 3.1.1
N´ ahodn´ y les Rozhodovac´ı stromy
Rozhodovac´ı strom je zakoˇrenˇen´ y strom, tj. graf bez kruˇznic. Kaˇzd´ y z jeho vnitˇrn´ıch uzl˚ u reprezentuje pr´ avˇe jeden atribut a hrany, kter´e z nˇej vedou odpov´ıdaj´ı hodnot´am, kter´e tento atribut nab´ yv´ a. Pˇri klasifikaci pˇr´ıkladu se tedy postupuje shora dol˚ u podle hodnot atribut˚ u a na z´ avˇer je mu pˇriˇrazena hodnota v listu. Rozhodovac´ı strom m˚ uˇzeme tak´e ch´apat jako disjunkci konjunkc´ı, kde vnitˇrn´ı uzly jsou ˇc´asteˇcnˇe ohodnocen´e formule a listy u ´plnˇe ohodnocen´e, maj´ı hodnotou. Strom se stav´ı na z´ akladˇe rozdˇelov´an´ı tr´enovac´ıch dat na co nejjednoznaˇcnˇeji urˇcen´e 2 3
viz kapitola 3.2 viz kapitola 3.3
5
mnoˇziny. V kaˇzd´em kroku se zvol´ı takov´ y atribut, kter´ y jako rozhoduj´ıc´ı krit´erium zp˚ usob´ı nejvˇetˇs´ı pokles neˇcistoty dat, tj. co podaˇr´ı se oddˇelit tˇr´ıdy co nejjednoznaˇcnˇeji. Zp˚ usob˚ uP mˇeˇren´ı neˇcistoty dat je v´ıce, program R jako z´akladn´ı kriterium bere Gini Index = j pj , kde pj je pravdˇepodobnost tˇr´ıdy j.[8] Pˇri stavbˇe stromu je tˇreba d´at si pozor na pˇretr´enov´ an´ı - aby strom dokonale neokop´ıroval rozdˇelen´ı tr´enovac´ıch dat, m´ısto poˇzadovan´e generalizace. Kvalitu stromu je moˇzn´e zlepˇsit proˇrez´av´an´ım. Pˇri nˇem se vˇetve, kter´e pracuj´ı s pˇr´ıliˇs malou podmnoˇzinou tr´enovac´ıch dat nahrad´ı listem s hodnotou nejˇcastˇejˇs´ı tˇr´ıdy v t´eto podmnoˇzinˇe. 3.1.2
N´ ahodn´ y les
N´ahodn´ y les je tvoˇren velk´ ym mnoˇzstv´ım rozhodovac´ıch strom˚ u. Stromy v n´ahodn´em lese jsou tvoˇreny speci´ aln´ım zp˚ usobem. Pokud tr´enovac´ı data Dtrain obsahuj´ı n pˇr´ıklad˚ u, kaˇzd´ y ze strom˚ u roste na mnoˇzinˇe n n´ahodnˇe vybran´ ych pˇr´ıklad˚ u z Dtrain s opakov´an´ım. Pravdˇepodobnost v´ yskytu konkr´etn´ıho pˇr´ıkladu v takto vybran´e mnoˇzinˇe je 1 − (1 − 1 n −1 ≈ 0.63. n) ≈ 1 − e Pokud je m poˇcet atribut˚ u, je zvoleno ˇc´ıslo md ostˇre menˇs´ı neˇz m. Pˇri stavbˇe stromu se potom v kaˇzd´em uzlu vyb´ır´ a mezi md n´ahodnˇe vybran´ ymi atributy. Hodnota md je stejn´a pro vˇsechny stromy v lese. Stromy se neproˇrez´avaj´ı, kaˇzd´ y je pˇestov´an do maxim´aln´ıho rozsahu. Pˇri klasifikaci se testovac´ıho pˇr´ıkladu nejprve vyhodnot´ı na kaˇzd´em ze stromu v lese. Jako v´ ysledn´ a tˇr´ıda je pak zvolena ta, pro kterou hlasuje nejv´ıce strom˚ u. Tento algoritmus m´ a ˇradu v´ yhod, patˇr´ı mezi nejpˇresnˇejˇs´ı mezi souˇcasn´ ymi klasifik´atory, dok´aˇze efektivnˇe zpracov´ avat velk´ a data a nevad´ı mu ani velk´e mnoˇzstv´ı atribut˚ u.[1]
3.2
kNN - k-Nearest Neighbour
Algoritmus k-Nearest Neighbour patˇr´ı mezi tzv. l´ın´e metody, to znamen´a, ˇze si nevytv´aˇr´ı ˇz´ adn´ y model, ale klasifikuje na z´akladˇe podobnosti s tr´enovac´ımi daty, kter´e si uchov´ avaj´ı v pamˇeti. Konkr´etnˇe pˇri metodˇe k-NN se tr´enovac´ı pˇr´ıklady uloˇz´ı podle hodnot sv´ ych atribut˚ u v m-dimenzion´aln´ım prostoru, kde m je poˇcet atribut˚ u. Pˇri klasifikaci nov´eho pˇr´ıkladu algoritmus v tomto prostoru hled´a k jeho nejbliˇzˇs´ıch soused˚ u. Pot´e je mu pˇriˇrazena tˇr´ıda, kterou m´a vˇetˇsina z jeho k nejbliˇzˇs´ıch soused˚ u. Vzd´alenost´ı mezi sousedy je obvykle ch´ap´ana euklidovsk´ a vzd´alenost, tj. pro dva pˇr´ıklady qP (r) (r) 2 (r) m xi a xj je vzd´ alenost definov´ ana d(xi , xj ) = je hodnota r=1 (xi − xj ) , kde xi xi v r-t´e dimenzi. Form´alnˇe, oznaˇc´ıme-li Dtrain jako tr´enovac´ı mnoˇzinu, m˚ uˇzeme klasifikaci nov´eho pˇr´ıkladu xn popsat n´ asledovnˇe. Pokud xn ∈ Dtrain , je mu pˇriˇrazena tˇr´ıda P z tr´enovac´ıch dat, v opaˇcn´em pˇr´ıpadˇe algoritmus hled´ a A ⊆ D takov´e, ˇze | A |= k a xi ,xj ∈A d(xi , xj ) je minim´aln´ı. xn je pˇriˇrazena nejˇcastˇejˇs´ı tˇr´ıda v A.
3.3
SVM - Support vector machines
Tr´enovac´ı pˇr´ıklady je moˇzn´e si pˇredstavit um´ıstˇen´e v prostoru, zkonstruovan´em nad mnoˇzinou vˇsech hodnot atribut˚ u. SVM hled´a separ´ator - nadrovinu, kter´a by prostor s pˇr´ıklady rozdˇelila na dva podprostory obsahuj´ıc´ı pˇr´ıklady jedn´e tˇr´ıdy, tak aby pˇr´ıklady mˇely co nejvˇetˇs´ı vzd´ alenost k separ´ atoru. Vzd´alenost je ch´ap´ana jako d´elka k nejbliˇzˇs´ımu bodu separ´ atoru. Protoˇze dvˇe tˇr´ıdy neb´ yvaj´ı ˇcasto dokonale oddˇeliteln´e a data mohou obsahovat ˇsum, byl tento model d´ ale vylepˇsen zaveden´ım speci´aln´ıch promˇenn´ ych ξ. Ty penalizuj´ı pˇr´ıklady 6
na nespr´ avn´e stranˇe separ´ atoru. Dalˇs´ı v´ yrazn´e zlepˇsen´ı SVM z´ıskalo zaveden´ım kernelov´ ych funkc´ı, kter´e umoˇzn ˇuj´ı i jin´e neˇz line´arn´ı rozdˇelen´ı prostoru. Hled´an´ı separ´ atoru lze form´ P alnˇe popsat P jako hled´an´ı takov´eho α, kter´e maximalizuje P n´asleduj´ıc´ı v´ yraz: L(α) = i αi − 12 i,j αi αj yi yj K(xTi xj ), tak ˇze αi ≥ 0 a i αi yi = 0. K oznaˇcuje kernelovou funkci, mezi nejbˇeˇznˇejˇs´ı patˇr´ı: • line´ arn´ı K(x, z) = xT z • polynomi´ aln´ı K(x, z) = (γxT z + c)d • radi´ aln´ı K(x, z) = exp(−γ(k x − z k))2 • sigmoida K(x, z) = tanh(γxT z + c) Algoritmus SVM je prim´ arnˇe urˇcen pro klasifikaci dvou tˇr´ıd. Je moˇzn´e ho ale rozˇs´ıˇrit i pro klasifikaci v´ıce tˇr´ıd. Nejˇcastˇejˇs´ı zp˚ usob je pomoc´ı hlasovac´ıch sch´emat jako je jedenproti-jednomu a jeden-proti-vˇsem. M´ame-li m tˇr´ıd, je pˇri jednom-proti-vˇsem nacviˇceno m bin´arn´ıch klasifik´ ator˚ u. Kaˇzd´ y z nich je natr´enov´an na rozpozn´an´ı jedn´e tˇr´ıdy proti nov´e tˇr´ıdˇe, kterou tvoˇr´ı pˇr´ıklady vˇsech ostatn´ ıch tˇr´ıd. V programu R se pouˇz´ıv´a jeden proti-jednomu. Pˇri tom natr´enov´ ano k2 klasifik´ator˚ u na datech pr´avˇe ze dvou tˇr´ıd. Nezn´am´emu pˇr´ıkladu je pˇridˇelena vˇzdy ta tˇr´ıda, pro kterou hlasovala vˇetˇsina klasifik´ator˚ u.
4
Praktick´ y popis model˚ u
Vˇsechny experimenty byly prov´ adˇeny v jazyku R [7]. V pˇr´ıloze jsou dokumenty hard.r, line.r a serve.r, ktere obsahuj´ı jak skripty vyuˇzit´e k tr´enov´an´ı, tak v´ ysledn´a nastaven´ı model˚ u. Automatick´e vyhodnocen´ı modelu je moˇzn´e spustit skriptem run.sh, kter´ y potˇrebuje jako prvn´ı argument urˇcovan´e slovo, jako druh´ y tr´enovac´ı mnoˇzinu a jako tˇret´ı testovac´ı mnoˇzinu. V´ ysledky experiment˚ u jsou hodnoceny pomoc´ı pˇresnosti - tj. m´ıry spr´avnˇe klasifikovan´ ych pˇr´ıklad˚ u v˚ uˇci vˇsem pˇr´ıklad˚ um pouˇzit´ ym pˇri klasifikaci. Aby tato m´ıra byla co nejspolehlivˇejˇs´ı, je vˇzdy poˇc´ıt´ ana pomoc´ı kˇr´ıˇzov´e validace. V tabulce 8 je uvedena baseline - pˇresnost naivn´ıho klasifik´atoru, kter´ y klasifikuje vˇsechny pˇriklady nejˇcastˇejˇs´ı tˇr´ıdou v tr´enovac´ıch datech. hard
line
serve
79,9
53.27
41.23
Tabulka 8: baseline
4.1
N´ ahodn´ y les
Pro tr´enovan´ı modelu n´ ahodn´eho lesa jsem pouˇzila knihovnu randomForest. Konkr´etn´ı pˇr´ıkaz pro natr´enov´ an´ı z´ akladn´ıho modelu je randomForest(V1 ∼ ., data = train, method = ”class”), kde V1 je atribut tˇr´ıdy a data je mnoˇzina dat s pˇr´ısluˇsn´ ymi atributy. 7
atributy
hard
line
serve
vˇsechny Boruta
91.19 91.12
75.93 75.55
84.83 83.69
Tabulka 9: N´ahodn´ y les - z´akladn´ı model Vzhledem k tomu, ˇze pro kaˇzd´e slovo se nejl´epe osvˇedˇcily vˇsechny atributy, tr´enovala jsem parametry modelu na nich. Jednalo se konkr´etnˇe o tyto parametry: 1. ntree - poˇcet strom˚ u, kter´e v lese roste, z´akladn´ı nastaven´ı je 500. Zkouˇsela jsem natr´enovat les i s hodnotami 400 a 600, ale rozd´ıly nebyly pˇr´ıliˇs v´ yznamn´e a proto jsem pot´e nech´ avala p˚ uvodn´ıch 500 strom˚ u. 2. mtry - poˇcet atribut˚ u n´ ahodnˇe vybran´ ych pro kaˇzd´ y uzel stromu. Z´akladn´ı nastaven´ı je odmocnina z poˇctu atribut˚ u. Proto jsem j´ı nastavovala u kaˇzd´eho slova individu´ alnˇe v okol´ı z´ akladn´ıho nastaven´ı ± 2,3. 3. nodesize - Minim´ aln´ı velikost pro list. Z´akladn´ı nastaven´ı je 1, pokud se toto ˇc´ıslo zv´ yˇs´ı, stromy jsou menˇs´ı a klasifikace je rychlejˇs´ı. Zkouˇsela jsem interval od 1 do 5. Kv˚ uli zrychlen´ı jsem tak´e omezila kˇr´ıˇzovou validaci na pouze 8 rozdˇelen´ı. Konkr´etn´ı pˇr´ıkaz potom vypadal napˇr´ıklad: tune.randomForest(V1 ˜ ., data = data, mtry = (4:10), nodesize = (1:5), tunecontrol = tune.control(sampling = ”cross”, cross = 8)). slovo
mtry
nodesize
presnost
hard line serve
7 8 11
1 2 5
91.27 75.89 85.91
Tabulka 10: N´ ahodn´ y les - modely na vˇsech atributech s vyladˇen´ ymi parametry
4.2
k-NN
Pro tr´enovan´ı modelu n´ ahodn´eho lesa jsem pouˇzila knihovnu class. Pˇresnost pˇri z´akladn´ım nastaven´ı (tj. pomoc´ı pˇr´ıkazu knn(tr´enovac´ı-data, testovac´ı-atributy, testovac´ı-tˇr´ıdy) je v tabulce 11. Pro k-NN nen´ı mnoho parametr˚ u, kter´e lze upravovat. Jeden z nich je k = poˇcet nejbliˇzˇs´ıch soused˚ u, kter´e algoritmus bere v u ´vahu pˇri vyhodnocov´an´ı. Pˇri pouˇzit´em z´akladn´ım nastaven´ı plat´ı k = 1, zkusila jsem proto poˇcet soused˚ u postupnˇe navyˇsovat. Pro kaˇzdou mnoˇzinu dat jsem vˇzdy jeden´actkr´at nacviˇcila model, kde k = 1..30. Grafy pˇresnosti na z´ akladˇe k jsou v obr´ azc´ıch 1,2 a 3, kter´e jsou souˇc´ast´ı pˇr´ılohy. V´ ysledky jsou zaj´ımav´e. Pro hard se pˇresnost prakticky nemˇenila a st´ale kol´ısala okolo 90-91%. Nejlepˇs´ıho v´ ysledku dosahovala pro zpˇetnˇe odeb´ıran´e, kde dos´ahla maxima u k = 10. S rostouc´ım k potom pˇresnost klesala, zat´ımco pro Borutu a vˇsechny atributy se pˇri vysok´em k naopak pˇresnost zvyˇsovala a pˇredstihla zpˇetnˇe odeb´ır´an´e. Naopak pro 8
atributy vˇsechny Boruta zpˇetnˇe odebran´e
hard
line
serve
90.02 89.95 90.82
73.40 74.72 75.60
83.49 82.57 84.39
Tabulka 11: z´akladn´ı k-NN slovo
atributy
k
pˇresnost
hard line serve
zpˇetnˇe odeb´ıran´e zpˇetnˇe odeb´ıran´e zpˇetnˇe odeb´ıran´e
10 1 1
90.97 75.61 84.39
Tabulka 12: fin´aln´ı nejlepˇs´ı k-NN modely line se pˇresnost od 1 s rostouc´ım k prudce sniˇzovala. U serve ˇsla pˇresnost tak´e od 1 dol˚ u, ale zdaleka ne tak radik´alnˇe jako u line. Nav´ıc se u serve prohodily mnoˇziny atribut˚ u. Jako v jedin´em modelu zde vych´az´ı h˚ uˇr mnoˇzina atribut˚ u vybran´ ych Borutou neˇz mnoˇzina vˇsech atribut˚ u. Nejlepˇs´ı v´ ysledky k-NN pro jednotliv´ a slova jsou v tabulce 12.
4.3
SVM
Pro tr´enovan´ı SVM modelu jsem pouˇzila knihovnu e1071. Z´akladn´ı pˇr´ıkaz potom m˚ uˇze vypadat takto: model = svm(V1 ∼., data = train, type = ’C’), kde V1 ∼. znamen´a, ˇze model bude urˇcovat tˇr´ıdu V1 na z´ akladˇe vˇsech ostatn´ıch v d´ale zadan´ ych datech a type = ’C’ urˇcuje, ˇze se bude jednat o klasifikaci. D´ale je moˇzn´e mˇenit ˇradu parametr˚ u v nastaven´ı funkce svm. Jde pˇredevˇs´ım o kernelovou funkci, kde z´akladn´ı nastaven´ı je radi´aln´ı, ale je moˇzn´e ji nastavit na polynomi´ aln´ı, line´arn´ı, nebo sigmoidu zmˇenou parametru kernel. 4.3.1
Hard
Pro orientaci jsem si nejprve spoˇc´ıtala pr˚ umˇernou pˇresnost r˚ uzn´ ych kernelov´ ych funkc´ı na vˇsech mnoˇzin´ ach parametr˚ u. V´ ysledky jsou v tabulce 13. Nejlepˇs´ıch v´ ysledk˚ u dosahuje pro mnoˇzinu zpˇetnˇe vyb´ıran´ ych atribut˚ u a pro radi´aln´ı a polynomi´ aln´ı kernelovou funkci. Tyto dvˇe jsem proto zvolila k dalˇs´ımu ladˇen´ı atribut˚ u. To jsem dˇelala pomoc´ı funkce tune.svm. U SVM jsem ladila konkr´etnˇe tyto parametry: • degree - urˇcuje se pro polynomi´aln´ı kernelovou funkci - stupeˇ n polynomu. V formul´ıch je znaˇcen d. • gamma - urˇcuje se pro vˇsechny kernelov´e funkce mimo line´arn´ı. Z´akladn´ı nastaven´ı je 1/poˇcet pˇr´ıklad˚ u. V formul´ıch je znaˇcen γ. • cost - postih za pˇr´ıklad na nespr´avn´e stranˇe hranice. Konkr´etnˇe potom lad´ıc´ı pˇr´ıkaz vypadal a = tune.svm(V1 ∼ ., data = data, kernel = ”polynomial”, degree = (1:5), gamma = 2−8..1 , cost = 2−3..4 , tunecontrol = tune.control(sampling = ”cross”, cross = 8)). Ladˇen´ım ale nedoˇslo k ˇz´adn´emu v´ yrazn´emu zlepˇsen´ı (viz tabulka 14). 9
kernel vˇsechny atributy radi´ aln´ı 91.20 polynomi´ aln´ı 90.97 sigmoida 88.54 line´ arn´ı 90.84
Boruta 91.14 91.12 88.36 90.99
zpˇetnˇe vybran´e 91.24 91.25 89.16 90.86
Tabulka 13: hard - pr˚ umˇern´ a pˇresnost z´akladn´ıho modelu SVM podle kernelov´ ych funkc´ı kernel degree radi´ aln´ı polynomi´ aln´ı 2
gamma 0.03125 0.125
cost 1 0.25
pˇresnost 91.28 91.25
Tabulka 14: hard - pr˚ umˇern´a pˇresnost vyladˇen´eho SVM modelu 4.3.2
Line atributy vˇsechny atributy radi´ aln´ı 75.88 polynomi´ aln´ı 75.93 sigmoida 75.85 line´ arn´ı 75.96
Boruta 75.29 75.57 75.34 75.46
zpˇetnˇe vybran´e 75.82 75.85 75.82 75.85
Tabulka 15: line - pr˚ umˇern´ a pˇresnost z´akladn´ıho modelu SVM podle kernelov´ ych funkc´ı Pro line se na z´ akladn´ıch modelech nejv´ıce osvˇedˇcila p˚ uvodn´ı mnoˇzina atribut˚ u a tak jsem d´ale pokraˇcovala s n´ı. Vzhledem k tomu, ˇze rozd´ıly mezi v´ ysledky r˚ uzn´ ych kernelov´e funkc´ı byly minim´ aln´ı, zkusila jsem vyladit vˇsechny. Ladˇen´ı line a serve prob´ıhalo stejnˇe jako u hard. U line ladˇen´ı pomohlo u radi´ aln´ı kernelov´e funkce, pro ostatn´ı se pˇresnost pˇr´ıliˇs nezmˇenila, respektive v nˇekter´ ych pˇr´ıpadech dokonce poklesla. (tabulka 16) 4.3.3
Serve
Pro serve jsou si v´ ysledky velmi podobn´e (viz tabulka 17) stejnˇe jako to bylo u line, tedy jsem zvolila i stejn´ y postup - vyladit vˇsechny kernelov´e funkce. Obˇcas jsem zkouˇsela vyladit urˇcit´ y model nˇekolikr´at. Je zaj´ımav´e, ˇze pro line´arn´ı kernelovou funkci mi vyˇsly velmi rozd´ıln´e hodnoty a obˇe byly hodnocen´e h˚ uˇre neˇz pˇri z´akladn´ım nastaven´ı. Naopak polynomi´ aln´ı a radi´aln´ı kernelov´e funkce si polepˇsily (viz tabulka 18).
5
V´ ysledek
Z´ıskala jsem tedy ˇradu model˚ u s do znaˇcn´e m´ıry podobnou pˇresnost´ı. Pro kaˇzd´e slovo jsem vybrala dva, kter´e d´ avaly ty nejlepˇs´ı v´ ysledky. Pro nˇe jsem zkusila d´ale zkoumat, jakou by mˇeli u ´spˇeˇsnost na odliˇsn´ ych datech a jestli se jejich u ´spˇeˇsnost na r˚ uzn´ ych datech bude liˇsit v´ yraznˇeji, tj. zda-li jsou rozd´ıly mezi modely statisticky v´ yznamn´e. To jsem ˇreˇsila pomoc´ı bootstrappingu. Tato metoda dovoluje z´ıskat velk´e mnoˇzstv´ı r˚ uzn´ ych
10
kernel radial polynomial sigmoid linear
degree 2 -
gamma 0.0078125 0.0625 0.00390625 -
cost 4 0.125 8 0.5
pˇresnost 76.23 76.03 75.24 75.60
Tabulka 16: line - pr˚ umˇern´a pˇresnost vyladˇen´eho SVM modelu atributy vˇsechny radi´ aln´ı 84.69 polynomi´ aln´ı 84.69 sigmoida 84.90 line´ arn´ı 85.05
baruta 83.61 83.83 83.88 83.78
zpˇetnˇe odeb´ıran´e 84.48 84.61 84.74 84.48
Tabulka 17: serve - pr˚ umˇern´a pˇresnost podle kernelov´ ych funkc´ı mnoˇzin dat t´ım, ˇze se opakovanˇe z p˚ uvodn´ıch dat vyb´ır´a n´ahodn´ y vzorek stejn´e velikosti, ve kter´em se ale pˇr´ıklady mohou opakovat. Na kaˇzd´e takto vybran´e mnoˇzinˇe je natr´enov´ an model a ten se ohodnot´ı na mnoˇzinˇe pˇr´ıklad˚ u, kter´e nebyly vybr´any. V tomto pˇr´ıpadˇe jsem tr´enovala kaˇzd´ y model na 1000 takto z´ıskan´ ych mnoˇzin´ach. Pot´e jsem tyto data vyuˇzila k tomu, abych z´ıskala pr˚ umˇernou pˇresnost, konfidenˇcn´ı interval pro pr˚ umˇer na hladinˇe 95% a 95% percentil. Konfidenˇcn´ı interval pro pr˚ umˇer na hladinˇe 95% je spoˇc´ıt´ an jako Y¯ ∓ t(0.975, n − 1) ∗ √sn , kde Y¯ je pr˚ umˇern´a hodnota, s je standardn´ı odchylka, n je velikost dat a t(0.975, n − 1) je 97.5 percentil t distribuce s n-1 stupni volnosti.[6] 95% percentil jsem z´ıskala tak, ˇze jsem z cel´eho vzorku vzala limitn´ı body bez prvn´ıch 2,5% a posledn´ıch 2,5%, tedy konkr´etnˇe bez prvn´ıch a posledn´ıch 25 hodnot uspoˇr´adan´e mnoˇziny. Na tom je dobˇre vidˇet rozptyl hodnot jednotliv´ ych model˚ u. V´ ysledky experiment˚ u s bootstrappingem jsou uvedeny v tabulce 19. Posledn´ım zp˚ usobem, jak jsem vyuˇzila dat z´ıskan´ ych bootstrappingem, bylo porovn´an´ı u ´spˇeˇsnosti dvou nejlepˇs´ıch model˚ u pro dan´e slovo. To jsem dˇelala pomoc´ı Welchova ttestu jako konfidenˇcn´ı interval hodnot na vektorech v´ ysledk˚ u obou model˚ u na stejn´ ych datech z´ıskan´ ych bootstrappingem. Pokud v´ ysledn´ y interval obsahuje 0, znamen´a to, rozd´ıl mezi u ´spˇeˇsnost´ı model˚ u nen´ı statisticky v´ yznamn´ y. V opaˇcn´em pˇr´ıpadˇe je rozd´ıl statisticky v´ yznamn´ y a m˚ uˇzeme s jistotou 95% tvrdit, ˇze je jeden model lepˇs´ı. V´ ysledky tohoto testu jsou v tabulce 20.
kernel degree radi´ aln´ı polynomi´ aln´ı 3 sigmoida line´ arn´ı line´ arn´ı -
gamma 0.0078125 0.0625 0.0078125 -
cost 4 0.25 4 32 0.5
pˇresnost 85.45 85.16 83.95 84.93 84.76
Tabulka 18: serve - pr˚ umˇern´a pˇresnost vyladˇen´eho SVM modelu
11
slovo hard line serve
model radi´ aln´ı SVM n´ ahodn´ y les polynom. SVM radi´ aln´ı SVM radi´ aln´ı SVM n´ ahodn´ y les
kˇr´ıˇzov´ a val. 91.28 91.27 76.03 76.23 85.45 85.91
pr˚ umˇer boots. 91.09 91.07 74.93 75.70 84.86 85.27
95% k.i. pr˚ umˇer (91.05,91.13) (91.03,91.11) (74.70,75.16) (75.61,75.78) (84.81,84.91) (85.22,85.32)
95% percentil (89.84,92.29) (89.99,92.25) (54.82,77.45) (71.28,77.84) (83.18,86.31) (83.72,86.80)
Tabulka 19: dva nejlepˇs´ı modely pro kaˇzd´e slovo, v´ ysledky z´ıskan´e kˇr´ıˇzovou validac´ı a bootstrappingem. Fin´ alnˇe zvolen´e modely pro kaˇzd´e slovo jsou oznaˇceny tuˇcnˇe. slovo hard line serve
metody radi´ aln´ı SVM x n´ahodn´ y les polynom. SVM x radi´aln´ı SVM radi´ aln´ı SVM x n´ahodn´ y les
95% konfidenˇcn´ı interval (-0.00073,0.00034) (-0.010,-0.0053) (-0.0048,-0.0033)
Tabulka 20: konfidenˇcn´ı interval rozd´ıl˚ u v´ ysledk˚ u r˚ uzn´ ych model˚ u pro stejn´e slovo Jedinˇe pro hard nelze prohl´ asit o jednom modelu, ˇze by byl lepˇs´ı. I co se t´ yˇce pr˚ umˇern´e pˇresnosti jsou si aˇz neuvˇeˇritelnˇe podobn´ı. Pˇresto jsem vybrala jako nejlepˇs´ı model n´ahodn´e stromy kv˚ uli lehce vyˇsˇs´ı doln´ı hranici percentilu. Pro klasifikaci line vych´az´ı l´epe SVM s radi´aln´ı kernelovou funkc´ı, a to nejen kv˚ uli v´ ysledku testu, ale pˇredevˇs´ım kv˚ uli v´ yraznˇe niˇzˇs´ı doln´ı hranici percentilu u SVM s polynomi´aln´ım kernelem (viz tabulka 19). Pro serve se uk´ azaly jako nejvhodnˇejˇs´ı model n´ahodn´e stromy. Pokusy uk´ azaly velmi podobn´e v´ ysledky pro vˇsechny klasifik´atory. Nejlepˇs´ıch hodnot dosahovaly n´ ahodn´e stromy a SVM, naopak nejhorˇs´ı v´ ysledky vych´azely pro algoritmus k-NN. To lze pˇripisovat pˇredevˇs´ım nerovnomˇern´emu zastoupen´ı tˇr´ıd v datech, kdy jedna tˇr´ıda nab´ızela v´ yraznˇe v´ yˇse soused˚ u. Tato skuteˇcnost m´a na k-NN vˇetˇs´ı vliv neˇz napˇr´ıklad na n´ ahodn´e stromy. Pro ilustraci uv´ad´ım tabulku 21, kter´a ukazuje zaokrouhlen´e pr˚ umˇern´e ohodnocov´ an´ı k-NN algoritmu (s k = 1) pro slovo line v r´amci kˇr´ıˇzov´e validace.
cord division formation phone product text
cord 12 0 0 1 2 1
division 0 23 0 0 0 0
formation 0 0 16 0 1 0
phone 3 0 0 24 1 0
product 16 8 11 11 185 23
text 0 0 0 0 1 8
Tabulka 21: matice chyb pro klasifikaci line pomoc´ı k-NN, pr˚ umˇer z deseti pokus˚ u Tato tabulka byla velmi podobn´ a i pro vˇsechny ostatn´ı modely. Nejˇcastˇejˇs´ı ˇspatn´a klasifikace byla pˇriˇrazen´ı nejˇcastˇejˇs´ı tˇr´ıdy - product, ostatn´ı tˇr´ıdy se mezi sebou prakticky ”nepraly”. Pokud ale data odpov´ıdaj´ı skuteˇcn´emu v´ yskytu dan´eho slova v bˇeˇzn´em jazyce, nemus´ı b´ yt nutnˇe na ˇskodu pˇriˇradit ˇspatnˇe zaˇraditeln´ y v´ yskyt slova t´e nejˇcastˇejˇs´ı tˇr´ıdˇe. 12
Tak´e by bylo vhodn´e udˇelat jeˇstˇe druhotnou anal´ yzu atribut˚ u, aˇckoli jsem se snaˇzila hledat takov´e atributy, kter´e oddˇelovaly m´alo ˇcast´e tˇr´ıdy od t´e nejˇcastˇejˇs´ı.
6
Z´ avˇ er, shrnut´ı
C´ılem t´eto pr´ ace bylo automatick´e urˇcov´an´ı v´ yznamu slov. Za t´ım u ´ˇcelem byly z dat vybr´any atributy a nich nacviˇcen´e modely pro tˇri r˚ uzn´e klasifik´atory - n´ahodn´e stromy, k-NN a SVM. Uk´ azalo se, ˇze modely dosahovaly na datech velmi podobn´e pˇresnosti, ale i tak byly v´ yraznˇe lepˇs´ı neˇz baseline. Nejv´ıce se osvˇedˇcily n´ahodn´e stromy a SVM. Koneˇcn´e v´ ysledky jsou uveden´e v tabulce 22 vˇcetnˇe pˇresnosti, kter´e modely dos´ahly pˇri testov´an´ı na 500 pˇredem nevidˇen´ ych vˇet´ach.
baseline nejlepˇs´ı model pˇresnost pˇri kˇr´ıˇzov´e validaci pˇresnost na nezn´ am´ ych datech
hard
line
serve
79,8 n´ahodn´ y les 91.1 90.0
53.3 radi´aln´ı SVM 75.7 74.5
41.2 n´ahodn´ y les 85.3 85.0
Tabulka 22: baseline vs. nejlepˇs´ı model
13
Literatura 1 Breiman Leo, Cutler Adele, Random Forests. URL: http://www.stat.berkeley.edu/∼breiman/RandomForests-cc-home.htm 2 Hanks Patrick, Oxford English Dictionaries, Do word meanings exist?, Computers and the Humanities (2000), s. 171-177. 3 Kohavi Ron, John George H., Wrappers for feature subset selection (1996). URL: ai.stanford.edu/ ronnyk/wrappersPrint.pdf 4 Kursa Miron B., Rudnicki Witold R., Feature Selection with the Boruta Package. URL: http://www.jstatsoft.org/v36/i11/paper 5 NIST/SEMATECH e-Handbook of Statistical Methods, (2013). URL: http://www.itl.nist.gov/div898/handbook/ 6 Snedecor, George W. and Cochran, William G. (1989), Statistical Methods, Eighth Edition, Iowa State University Press 7 The R Foundation. The R project for statistical computing. URL: http://www.r-project.org/index.html. 8 Vidov´ a-Hladk´ a, B.Decision Trees. URL: http://ufal.mff.cuni.cz/∼hladka/ML/LECTURES/PFL054-decision-trees.pdf 9 Vidov´ a-Hladk´ a, B. Support Vector Machines. URL: http://ufal.mff.cuni.cz/∼hladka/ML/LECTURES/PFL054-SVM.pdf 10 Wikipedia. Bootstrapping, (2013). URL: http://en.wikipedia.org/wiki/Bootstrapping statistics
14
Obr´ azek 1: hard - d˚ uleˇzitost atribut˚ u pro slovo hard
Pˇ r´ıloha Boruta • hard - pro hard byly vyˇrazeny 2 atributy. Jednalo se o: V18 - tag pˇred hard je JJ V26 - hard funguje jako otvˇren´ y vˇetn´ y doplnˇek - xcomp Naopak jako v´ yraznˇe nejd˚ uleˇzitˇejˇs´ı atribut se uk´azalo: V23 - hard je adjektivn´ı modifik´ator slova z mnoˇziny abstraktn´ıch podstatn´ ych jmen jako time, question, decision... • line - bylo vyˇrazeno 15 atribut˚ u V4, V10, V24, V25, V28, V32, V34, V35, V36, V37, V44, V48, V54, V57, V58. Naopak jako v´ yraznˇe nejd˚ uleˇzitˇejˇs´ı atributy se uk´azaly postupnˇe: V14 - po line n´ asleduje slovo z mnoˇziny slov spojen´ ych s telefonov´an´ım telephone,direct,customer,.. V56 - line se poj´ı s pˇredloˇzkou between V52 - line je nav´ az´ ano pomoc´ı pˇredloˇzky on • serve - pro slovo serve Boruta vyˇradila osm atribut˚ u - V15 V23 V25 V26 V28 V29 V32 V41. Jako ty nejd˚ uleˇzitˇejˇs´ı pro urˇcen´ı spr´avnou klasifikaci oznaˇcila: V5 - vˇeta obsahuje slovo purpose V34 -slovo serve je pouˇzito s nˇekter´ ym pomocn´eho slovesem V3 - vˇeta obsahuje jedno z mnoˇziny slov oznaˇcuj´ıc´ıch vedouc´ı funkce napˇr. chair15
Obr´ azek 2: hard - d˚ uleˇzitost atribut˚ u pro slovo line man, president, chief..
Zpˇ etn´ e vyˇ razov´ an´ı vyˇrazen´e atributy
hard
line
serve
SVM k-NN
V2, V7, V18 V7, V12, V14
V10, V34, V35, V48 V8, V23, V24, V35, V51, V58
V6, V14, V24; V7, V15, V19, V20
Tabulka 23: Zpˇetn´e vyˇrazov´an´ı
k-NN
16
Obr´ azek 3: hard - d˚ uleˇzitost atribut˚ u pro slovo serve
Obr´ azek 4: hard - pˇresnost k-NN na z´akladˇe k
17
Obr´ azek 5: line - pˇresnost k-NN na z´akladˇe k
Obr´ azek 6: serve - pˇresnost k-NN na z´akladˇe k
18
