Vektoriaus palaikymo mašina

Kažkodėl nusprendžiau, kad seniai berašiau įrašų, kurių niekas nesuprato. Šiandien su plačia tauta norėčiau pasidalinti maža teorijos ir praktikos samprata apie Support Vector Machine (SVM) (lietuviškai galima versti įvairiai, tačiau, kadangi niekur jokio vertimo nerandu, tai sugalvojau savo variantą – Vektoriaus palaikymo mašina); Labiausiai man patiko Christopher J.C. Burgers parašytas įvadas “A Tutorial on Support Vector Machines for Pattern Recognition“. Nors, aišku, galite bandyti skaityti originalų Vapnik straipsnį “An overview of statistical learning theory“. Ten daugiau matematikos, bet ir aišku mažiau.

Įžanga

SVM sprendžia klasifikavimo problemas. Turim tam tikrą savybių erdvę ir mums reikia toje savybių erdvėje gražiai `padalinti` duomenis. SVM genialumas yra tai, kad jis naudoja pačius `duomenis` duomenų praskyrimo erdvei rasti. Daug žada, ne?

Gražioji pusė

Pavyzdį galima paimti iš wiki.

Grafike X_1 ir X_2 suformuoja dvi dimensijas, kur SVM ieško linijinio jų tarpusavio prasiskyrimo. Ryškiau apibrėžti tuščiaviduriai taškai ir pilkai apvesti juodi taškai yra ne kas kitas kaip palaikymo vektoriai. Tai jie pagrindinė priežastis kodėl įmanomas toks duomenų prasiskyrimas. Labai nesigilinant į SVM matematiką (ribinės klaidos radimas ir kt.), tai mes turime dvi linijines lygtis. Viskas ko mums reikia, tai rasti dvi linijinės funkcijas. Mums šiuo klausimu dar padeda ir ta sąlyga, kad nagrinėjamos lygtis turi būti viena kitai lygiagrečios. Nėra jokio Gauso (NaiveBayes), nėra jokios gausios ir gan sunkios matematikos PMM (HMM) atveju. Juk nuostabu, ne? Iš teigiamų savybių galima paminėti ir išgirtą jo naudojimą izoliuotų raidžių atpažinime. Yra pateikiamas net visas projektas su kodu (.NET) (dėl .NET jo net nežiūrėjau).

Negražioji pusė

Tačiau SVM turi ir blogų savybių. Kas nutiks, jeigu po apmokymo, testavimo fazėje savybių erdvėje koks nors taškas pateks tarp dviejų linijų? SVM neturi jokio Gauso (bent jau originalas), todėl atsakymo paprasčiausiai nebus. Kokia loginė funkcija tai gali paaiškinti? Kur `uncertainty` principas? Sekantis SVM trūkumas – tai jo įvairumas. Jeigu prisiminti mokyklinę matematiką, tai visos matematinės plokštumos ir figūros kaip tik ir prasidėdavo tašku ir tiese. Taip pat ir SVM atveju – galime prigalvoti begalės jo variantu ir ieškoti tinkamo iki kol pati saulė sudegs. Žinoma, yra keli populiarūs, oficialiai naudojami sprendimai. Kita neigiama savybė – SVM sugebėjimas vienu laiko momentu klasifikuoti tik du duomenų debesis savybių danguje. Yra, tiesa, neblogas popierius šia tema. Siūlau pasiskaityti, kada nors. Iš praktikos dar galima paminėti, kad SVM apmokymas yra labai lėtas ir nervų reikalaujantis procesas. Stebuklus su juo galima daryti ir neturint baigtinį dimensijų skaičių, tačiau `gyvai` treniruoti klasifikatoriaus tiesiog neįmanoma.

Išvados

Taip ir nesupratau kodėl SVM tapo toks populiarus. Yra geresnių ir greitesnių klasifikavimo metodų (kad ir stebuklingas PMM (HMM), nors ir reikia turėti baigtinį dimensijų skaičių). Reiks gal kada parašyti įžangą į SVM lietuvių kalba. Tiek, trumpai.

Kas iš tikrųjų yra Paslėptas Markovo modelis

Įžanga

Truputi pamankštinęs rankas prie Paslėpto Markovo modelio, galiu pasidalinti ne teoriniais samprotavimas apie nagrinėjamą modelį, o apie konkretų įrankį, kuris veikia ir veikia pakankamai gerai.

Paslėptas Markovo Modelis ir kiti klasifikatoriai

Jeigu padaryti prielaidą, kad Paslėptas Markovo Modelis (PMM) yra klasifikatorius, tuomet palyginus su kitais klasifikatoriais – mes turime labai galingą įrankį.

Pradėkime nuo NaiveBayes klasifikatoriaus, kuris yra labai paprastas – n dimensijų Gauso pasiskirstymas. Kai gauname tašką erdvėje – tiesiog pažiūrime kiekvieno cluster tikimybes ir išrenkam tą cluster, kuris turi didžiausią tikimybę. Paprasta, greita ir pigu. Tačiau kas nutinka, kai du Gauso pasiskirstymai yra arti vienas kito, o taškai iš šaltinio gaunami tik per delta skirtumą tarp dviejų pasiskirstymų – klasifikatorius mėtysis tarp vieno ir kito cluster. Taip mes gauname labai mažą accuracy ir presition.

Support Vector Machine yra kiek sudėtingesnis variantas. SVM’as ieško papildomų dimensijų duomenims atskirti. Tai ypač pagelbėja, kai duomenis linijiniu būdu atskirti tiesiog nėra įmanoma. Geras pavyzdys – naudojant polynomial kernel trick. Pagrindinis SVM darbo arklys yra radial basis function. Tai tas pats Gausas. Mano praktikos metu, SVM’as tik truputi geriau dirbo, negu NaiveBayes klasifikatorius, o kaikuriais atvėjais – net blogiau. Dirbtinio intelekto sistemose, visgi, daug kas priklauso nuo application. Reikia išnagrinėti kokias savybes signalas turi savyje, ką duoda dimensijų mažinimas.

PMM turi vieną labai didelį pranašumą, palyginus su kitais nagrinėtais klasifikatoriais – jis turi savyje laiko informaciją. Matematiškai šnekant, tai kai mes turime du duomenų cluster, kurių variacijos kertasi – mes virš dviejų variacijų galime aprašyti dar vieną variacija, kuri aprašo įvykių tikimybes, kurias atspindi clusters. Taip galima kontroliuoti sąlygas, kurios aprašo įvykio pasikeitimą.

Jeigu nustatyti, kad perėjimo tikimybė tarp vieno ir kito įvykio yra labai maža, tai nors, jeigu ir naujas duomenų taškas bus ant kito Gauso pasiskirstymo – klasifikatorius vistiek neskubės persijungti prie kito įvykio.

Paprastas klasifikatorius

Pagerintas (PMM) klasifikatorius

Išvados

Paslėptas Markovo Modelis yra fantastiškas matematinis įrankis. Skirtingai nuo kitų klasifikatorių, jame lengvai gali būti saugoma bet kokia euristinė informacija apie nagrinėjamus duomenų clusters.