Įžanga į Paslėptą Markovo modelį (skaidrės)

Šį kart trumpa prezentacija apie Paslėptą Markovo modelį, su trupučiu matematikos.

Skaidrėse pristatomi mašininio apmokymo tipai, parodyta pavyzdinė savybių erdvė, aptariamas Markovo procesas, Markovo grandinė, apibūdinti Paslėpto Markovo modelio parametrai, apžvelgiamas Viterbi kelio radimo algoritmas.

Viskas paruošta nėra super-idealiai, dėl didelio akademinio užimtumo. Skaidrės yra daugiau kaip špargalkė kalbai, negu kaip mokomoji priemonė. Mokomajai priemonei reikia knygas rašyti. Skaidres galite peržiūrėti slideshare, arba atsisiųsti pdf formatu.

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.

Paslėptas Markovo modelis: Diskretinis Markovo procesas

Paimkime sistemą, kurią galima apibūdinti bet kokiu laiko momentu tam tikra būsenų seka N, kur galimos sistemos būsenos yra S_1, S_2, .., S_N, kaip pavaizduota iliustracijoje.

Markovo graindinė su 5 būsenomis ir perėjimo tikimybėmis

Markovo graindinė su 5 būsenomis ir perėjimo tikimybėmis

Per tam tikrą, periodinį laiko tarpą, sistema pakeičia savo būseną, priklausomai nuo ankščiau numatytų tikimybių. Mes nustatome laiko konstantas, susietas su būsenų kitimu, t = 1, 2, ... ir nustatome sistemos būseną q_t, esant t laikui. Pilnas probleminis sistemos apibūdinimas reikalauja žinoti sistemos būseną kiekvienu laiko momentu. Specialaus diskretinio, pirmojo tipo Markovo grandinei, toks probleminis sistemos apibūdinimas yra išskaidytas į dabartinę ir spėjamą būseną, pavyzdžiui:

Kur P yra skaičiuojamoji tikimybė; q_t yra t laiko momentu sistemos būsena S_N.

Mes orientuojamės tik į procesus, kurioje aukščiau nurodytos lygties dešinėje dalyje, kuri yra nepriklausoma nuo laiko. Tai veda prie galimybės suformuoti tarpinių būsenų, sudarytų iš dabartinės ir spėjamos, tikimybes a_{ij}:

su tarpinės būsenos koeficientų apibrėžimais:

kadangi jos pilnai patenkina standartinio stochastinio proceso konstantas.

Aukščiau nurodytas stochastinis procesas gali būti vadinamas galimas Markovo modelis, kadangi proceso išėjimas yra sistemos būsena tam tikru laiko momentu, kur kiekviena būsena nusako fizikinį įvykį. Tam, kad įtvirtinti aptartas idėjas, paimkime trijų lygių Markovo oro modelį. Galima pasakyti, kad galimas pusiaudienį oras lauke gali būti trijų fazių:

  • Būsena 1: lietus
  • Būsena 2: debesuota
  • Būsena 3: saulėta

Mes teigiame, kad oras, esant dienai t, yra charakterizuojamas pagal aukščiau nurodytas būsenas, o galimybių a_{ij} matrica A atrodytų taip:

Padarykime prielaidą, kad pirmą dieną (t=1) šviečia saulė. Ir paklauskime klausimo: kokia tikimybė, kad per sekančias septynias dienas oras bus “saulė-saulė-lietus-lietus-saulė-debesuota-saulė-..” ? Tikimybių seką O mes galime aprašyti kaip O = \{S_3, S_3, S_3, S_1, S_1, S_3, S_2, S_3\}, kuri sudaryta iš t =1, 2, ..., 8 laiko momentu atliktais stebėjimais. Mes norime nustatyti šio modelio tikimybę O. Tokia tikimybė gali būti išreiškiama taip:

panaudojome pažymėjimą

norėdami pažymėti pradinio įvykio tikimybę.

Taip pat galime paklausti dar vieno įdomaus klausimo (į kurį atsakyti galime pasitelkti modelį): Kokia tikimybė, kad modelis liks vienoje būsenoje tiksliai d dienų?

Tokia tikimybė yra randama stebėjimų seka:

modeliui, kuris yra:

Dydis p_i(d) yra diskretinis dydis, kuris žymi funkcijos tankio tikimybę, kurios trukmė yra d, i būsenoje. Šitas eksponentinis tikimybės tankio dydis yra Markovo grandinės tikimybės būsenos ilgis. Remiantis p_i(d), mes galime apskaičiuoti tikėtiną vienos būsenos stebėjimų skaičių

Iš čia galime apskaičiuoti, kad tikėtinas vienos būsenos stebėjimas esant saulėtam orui yra \frac{1}{0.2}=5, debesuotumui \frac{1}{0.4}=2.5, o tikimybė stebėti lietų \frac{1}{0.6}=1.67 dienos.

Šaltinis: “A tutorial on Hidden Markov Models and Selected Applications in Speech Recognition”

Paslėptas Markovo modelis: Įžanga

Po truputi ruošiames baigiamąjam darbui, todėl pradėjau versti vieną gerą paslėpto Markovo modelio vadovą “A tutorial on Hidden Markov Models and Selected Applications in Speech Recognition”. Pateikiu Jums išverstą įvadą.

Nors ir buvo pristatyti dar vėlesniais 1960-tais ir ankstyvais 1970-tais metais, statistinis Markovo metodas arba paslėptas Markovo metodas tapo labai populiarūs tik paskutiniais metais. Yra dvi pagrindinės priežastys kodėl taip nutiko. Pirma, modeliai yra stipriai pagrįsti matematiškai ir iš to galima suformuoti teoretinę bazę modelių taikymui. Antra, modeliai, reikiamai pritaikyti, labai gerai dirba praktikoje, svarbiuose įtaisuose. Šiame vadove pabandysime atsargiai ir metodiškai apžvelgti teoretinius šio tipo statistinio modelio aspektus ir parodyti kaip jie yra pritaikomi balso atpažinimo problemoms spręsti.

Realaus pasaulio procesus paprasčiausiai galime apibūdinti signalais. Signalai gamtoje gali būti diskretiniai (raidės iš žodyno) arba nuolatiniai (garsiniai signalai, temperatūros matavimai). Signalo šaltinis gali būti stacionarus (jo statistiniai apibrėžimai nepriklauso nuo laiko), ar nestacionarus (signalo apibrėžimai laikui bėgant kinta). Signalai gali būti gryni (siunčiami tiesiai iš šaltinio), ar pažeisti iš kitų signalų šaltinių (kaip pavyzdžiui triukšmo) arba dėl perdavimo trukdžių, aido, kt.

Fundamentinio tipo svarbi problema yra charakterizuoti tokius, realaus pasaulio, signalus į signalų modelį. Yra keletas priežasčių dėl ko šitą problemą yra būtina spręsti. Pirmiausiai, signalo modelis suteikia mums pradinę informaciją apie signalą, kuria remiantis yra galima apibrėžti reikalingą signalą sistemos išėjime. Pavyzdžiui, mus domina pokalbio, vykstančiu telefonu, signalo sustiprinimas. Signalas yra pažeistas triukšmo ir perdavimo kliūčių. Tokiam uždaviniui atlikti mes galime panaudoti signalų modelį ir suprojektuoti sistemą, kuri pašalins nereikalingą triukšmą ir anuliuos perdavimo iškraipymą. Antra priežastis kodėl signalų modelis yra toks svarbus yra tai, kad jis potencialiai mums gali pasakyti labai daug apie signalo šaltinį, net jeigu mes jo nematome. Ši savybė yra labai svarbi, kai yra būtina gauti tikslų signalą iš šaltinio. Šiuo atveju, su geru signalo modeliu, mes galime simuliuoti signalo šaltinį ir išmokti kuo daugiau iš tokių simuliacijų. Galiausiai, pagrindinė priežastis kodėl signalo modelis yra toks svarbus – jis velniškai gerai veikia praktikoje ir leidžia mums suvokti svarbias praktines sistemas, pavyzdžiui spėjimo sistemos, atpažinimo sistemos, identifikavimo sistemos, kt.

Galima pasirinkti keletą signalo modelio tipų, kuriais galima apibūdinti nagrinėjamo signalo ypatybes. Vienas signalas gali būti išskaidytas į keletas jo sudedamąsias klases: deterministinį modelį ir statistinį modelį. Deterministinis modelis parodo pagrindinę informaciją apie signalą: ar signalas yra sinusinės formos, ar yra eksponentinė suma, kt. Tokiais atvejais, signalo apibūdinimas yra gan paprastas uždavinys. Viskas, kas reikalaujama yra nustatyti signalo modelio parametrų reikšmes (amplitudę, dažnį, fazę, kt.). Antra signalo modelio plati klasė yra statistinis modelis, kuris bando charakterizuoti statistinius signalo parametrus. Tokių statistinių modelių pavyzdžiai yra Gauso procesas, Poisono procesas, Markovo procesas, paslėptas Markovo procesas. Paslėpta prielaida yra ta, kad signalas gali būti gerai charakterizuotas kaip parametrinis atsitiktinis procesas, ir jo stochastinio proceso parametrai gali būni nustatyti tiksliai, gerai apibūdintai.

Įdomumo dėlei, nusakytas kalbos atpažinimas, abudu deterministiniai ir stochastiniai signalo modeliai turi didelį pasisekimą. Šitame straipsnyje mes orientuosimės į vieną stochastinį signalo modelį, kuris pavadintas paslėptas Markovo modelis (angliškai: hidden Markov model (HMM)). Pirmiausiai mes apžvelgsime Markovo grandinės teoriją ir ją plėsdami prieisime prie paslėpto Markovo modelio, panaudodami kelis pavyzdžius. Tuomet sutelksime savo dėmesį į tris fundamentines problemas, su kuriomis susiduriama projektuojant HMM: stebėjimo eilės tikimybės vertinimas specifiniam HMM; geriausios modelio būsenos eilės nustatymas; modelio parametrų apibrėžimas, siekiant gauti norimą signalo atsakymą. Mes parodysime, kad kai šios tris fundamentinės problemos yra išspręstos, mes galime taikyti HMM nurodytoms problemos spręsti balso atpažinimo sistemose.

Nei paslėpto Markovo modelio, nei balso atpažinimas nėra naujas dalykas. Pagrindinė teorija buvo paskelbta Baumo ir jo kolegų dar vėlyvais 1960, ankstyvais 1970 metais ir pritaikyta balso atpažinimo sprendimams Bakerio CMU ir Jelinek su kolegomis IBM 1970 metais. Tačiau, paplitęs supratimas ir HMM teorijos kalbos atpažinimo sprendimai pasirodė tik prieš kelerius metus. Tai nutiko dėl kelių priežasčių. Pirma, paslėptas Markovo modelis buvo publikuotas matematiniuose žurnaluose, kurie pagrinde nebuvo skaitomi inžinierių, kurie dirbo prie balso atpažinimo. Antra priežastis yra ta, kad pagrindiniai balso atpažinimo sprendimai nebuvo gerai dokumentuoti daugeliams vartotojų, todėl buvo sunku suprasti kokiu principu veikia sprendimas ir inžinieriai negalėjo perkelti modelio į savo tyrimus. Kuomet detalūs vadovai buvo išleisti, inžinieriai perkėlė teoretinį modelį savo laboratorijas. Šitas vadovas yra skirtas suteikti pagrindinės HMM teorijos apžvalgą (kaip ją pateikė Baumas ir jo kolegos), sutekti praktines teorinio metodo diegimo detales ir aptarti keletą nurodytų teoretinių aiškių problemų sprendimų pavyzdžių kalbos atpažinime. Vadovas sudeda iš kelių sudėtų straipsnių ir suteikia vientisą vadovą, kuris suteikia reikiamą užnugarį norint dirbti šios sferos tyrimų srityje.

Šis vadovas susideda iš sekančių sekcijų. Antroje sekcijoje mes apžvelgsime diskrečią Markovo grandinę ir parodysime paslėptos būsenos koncepciją, kur stebėjimas yra problematiška būsenos funkcija, gali būti efektyviai panaudota. Teoriją iliustruosime dvejais pavyzdžiais: monetos supimas, klasikinė kamuoliuko ir urnos sistema. Trečioje sekcijoje mes aptarsime tris fundamentines HMM problemas, ir suteiksime tris praktines technikas jas sprendžiant. Ketvirtoje sekcijoje mes aptarsime skirtinus HMM tipus, kurie buvo išstudijuoti: ergodinis ir kairys-dešinys modelius. Šioje sekcijoje mes taip pat aptarsime skirtingas modelio ypatybes, kaip stebėjimo skaičiaus funkcija, būsenos trukmės skaičius ir optimizavimo kriterijus, pasirenkant teisingas HMM parametrų reikšmes. Penktoje sekcijoje mes aptarsime problemas, kuris kyla diegiant HMM, kaip mastelio keitimas, pradinių parametrų sąmatos, modelio dydis, modelio forma, duomenų praradimas ir daugialypės stebėjimo seką. Šeštoje sekcijoje mes aptarsime izoliuotą žodžių iš balso atpažinimą, kuris yra suprojektuotas, naudojantis HMM idėjomis ir parodysime kaip jis elgiasi, lyginant su kitomis, alternatyviomis sistemomis. Septintoje sekcijoje mes išplėsime idėjas, aptartas šeštoje sekcijoje, ir pritaikysime jas sakinio atpažinimui. Tam mes jungsime atskirus, kiekvieno žodžio HMM modelius. Aštuntoje sekcijoje mes trumpai apžvelgsime didelį balso atpažinimo žodyną ir galiausiai, devintoje sekcijoje mes apibendrinsime visas idėjas, kurias aptarinėjome per visą vadovą.