hmm (2).pdf

Wst¦pdoukrytychmodeliMarkowaimetody

Bauma–Welcha.

PiotrWiktorZwiernik

5stycznia2005

Streszczenie

Wartykuleprzedstawimyszerok¡klas¦modeli,jak¡s¡ukrytemo-

deleMarkowa.Pomy±lanyjestonjakosamodzielnewprowadzeniedo

teorii.Zaprezentowanazostaniedeﬁnicjaprocesuoraznajpopularniej-

szametodaestymacjijegoparametrów.Zeszczególnymuwzgl¦dnie-

niempotraktujemyprzypadek,gdymodelposiadadwuelementow¡prze-

strze«stanów.Opisanezostan¡procesyowarunkowychprawdopodo-

bie«stwachemisjizrozkłademwykładniczym,Poissonaoraznormal-

nym.

Spistre±ci

1UkrytemodeleMarkowa 3

1.1Wprowadzenie.......................... 3

1.2DeﬁnicjaukrytychmodeliMarkowa............... 4

1.2.1Zało»eniawst¦pne.................... 4

1.2.2Ła«cuchyMarkowa.................... 5

1.2.3Uwagidotycz¡ceprzypadkudwustanowego...... 7

1.2.4UkrytemodeleMarkowa................. 8

1.3EstymacjaparametrówHMM..................12

1.3.1WprowadzeniedoalgorytmuBauma–Welcha.....12

1.3.2Algorytmpreﬁksowy–suﬁksowy.............14

1.3.3AlgorytmBauma–Welcha................16

2UkrytemodeleMarkowarozkładówdyskretnych 19

2.1Przeł¡czanierozkładówPoissona................19

2.1.1Wprowadzenie......................19

2.1.2Podstawowestatystykiprocesu.............20

2.1.3Modelowanieliczbyatakówpadaczki..........22

2.2Przeł¡czanierozkładówwielomianowych............24

2.2.1Wprowadzenie......................24

2.2.2Podstawowestatystykiprocesu.............25

2.2.3Modelowanieryzykanarynkuobligacji ........26

2.2.4Modelowanieerupcjigejzera„OldFaithful”......28

3UkrytemodeleMarkowarozkładówci¡głych 31

3.1Markowowskieprzeł¡czanierozkładównormalnych......31

3.1.1Wprowadzenie......................31

3.1.2StabilnaalternatywametodyBauma–Welcha.....31

3.2Modelanalizycyklugospodarczego...............33

3.2.1Wprowadzenie......................33

3.2.2Posta¢modelukoniunktury...............35

3.2.3Modelowaniezwrotówkoniunktury...........36

4Zako«czenie 41

1UkrytemodeleMarkowa

1.1Wprowadzenie

UkrytemodeleMarkowa(ang. HiddenMarkovModels ,HMM)topoj¦ciedo-

skonaleznanewzastosowaniachin»ynieryjnychodprawiepółwieku.Pierw-

szepowa»nezastosowanieznalazłyonew1967rokuwlaboratoriachIBM,

gdziewykorzystanojedorozpoznawanieznaków.Jakdot¡dnajszerzejko-

rzystasi¦znichtworz¡cmodeleakustycznewrozpoznawaniumowy[26].

Istniej¡znacz¡cepublikacjezbiorczetraktuj¡ceometodologiiizastosowa-

niuukrytychmodeliMarkowa.Zadobryprzykładmo»esłu»y¢niedawna

publikacjaautorstwaR.Elliota,L.AggounaorazJ.Moore[16],artykułY.

EphraimaiN.Merhava[17]orazlicznepublikacjewtakichczasopismachna-

ukowychjak IEEETransactionsonSignalProcessing , IEEETransactions

onSpeechandAudioProcessing oraz Biometrics .

Zbiegiemlatzacz¦toodkrywa¢,»etesamemodelesprawdzaj¡si¦tak-

»edoopisuinnychzjawiskwprzyrodzie.Podobnerozwi¡zaniateoretyczne

wykorzystywanowgenetyceibiochemii,patrznaprzykładpraceThompso-

na 1 .Churchilla 23 ,Baldiego[4].ZucchiniiGuthorp 4 u»ywaliukrytychmodeli

Markowadomodelowaniasekwencjidnisuchychiwilgotnychwniektórych

miejscachnaszegoglobu.Albert[1]orazLe,LerouxiPuterman[25][24]sto-

sowalinatomiastwswoichpublikacjachukrytemodeleMarkowadomode-

lowaniaszeregówczasowychliczbyatakówepilepsji.Hamilton[18]stworzył

szerokoupowszechnionywekonomiimodelcyklikoniunkturalnych.

Tonajbardziejistotneobszarywykorzystaniatychmetodwmodelowa-

niuprocesówwotaczaj¡cejnasrzeczywisto±ci.Listazastosowa«jestjednak

jeszczedalekaodwyczerpania.Istniejewieledo±¢egzotycznychpróbmode-

lowaniazu»yciemukrytychmodeliMarkowa,jaknaprzykładszacowanie

czasumi¦dzykolejnymierupcjamigejzeraOldFaithfulczysystemyrozpo-

znawaniatwarzy.UkrytemodeleMarkowaznalazłyrównie»zastosowaniew

naukachspołecznych.Pojawilisi¦naukowcy,którzypróbowaliprzyichpo-

1 [30]cyt.w:[27]

2 [13]cyt.w:[27]

3 [14]cyt.w:[27]

4 [32]cyt.w:[27]

1UKRYTEMODELEMARKOWA 4

mocyprzewidywa¢wydarzeniapolityczne.P.Schrodtnaprzykładzbudował

model,którymi¦dzyinnyminapodstawiedepeszzagencjiReutersszacował

prawdopodobie«stwawyst¡pienianapi¦¢,wregionieBałkanów[28].

WrozdzialetymprzedstawimypodstawyteoriiukrytychmodeliMar-

kowa.Punktemwyj±ciawpodrozdziale1.2b¦dziepobie»neprzedstawienie

wynikówzteoriiła«cuchówMarkowa.Nast¦pniezaprezentujemydeﬁnicj¦

ukrytychmodeliMarkowa.Wpodrozdziale1.3zaprezentujemyalgorytmy

wykorzystywanedoefektywnejestymacjiparametrówHMM,czylialgorytm

preﬁksowy–suﬁksowyorazalgorytmBauma–Welcha.

1.2DeﬁnicjaukrytychmodeliMarkowa

1.2.1Zało»eniawst¦pne

Wszystkiezmiennelosoweokre±lones¡nastandardowejprzestrzeniproba-

bilistycznej( , F ,P ).B¦dziemyu»ywa¢wielkichliterbyoznaczy¢zmienne

losowe,małychdlaichrealizacjiorazliter„pisanych”dlaokre±leniazbiorów,

zktórychprzyjmuj¡warto±cizmiennelosowe.Itaknaprzykładmo»emyna-

pisa¢,»ezmienna X przyj¦ławarto±¢ { x } zezbioru X .

Dyskretnyprocesstochastycznyb¦dziemyoznacza¢( X t ) t 2T ,gdzieunas

T = N .Załó»my,»e x t 2X dlaka»dego t 2T .Zprocesemstochastycznym

zwi¡zanajestmierzalnaprzestrze«produktowa( X T , B T X ),gdzie B X oznacza

borelowskie –ciałootwartychpodzbiorówprzestrzeni X wzgl¦demustalo-

nejmiary.Naswszczególno±cib¦dzieinteresowa¢przypadek,gdyproces

stochastycznyzdeﬁniowanyjestprzezrozkładna( X T , B T X ),któryzale»ny

jestodpewnegoparametru.Niech 2 oznaczatenparametr,gdzie

jestzbioremparametrów,któryunasb¦dziepodzbiorem R d dlapewnego

d .Jako P b¦dziemyoznacza¢rozkładprocesuokre±lonyprzezparametr .

Ci¡g n zmiennychlosowych X i ( i =1 , 2 ,...,n )b¦dziemyoznacza¢przez

X ( n ) ,aichrealizacj¦przez x ( n ) .Niech P ( n )

oznacza n –wymiarowyroz-

kład X ( n ) indukowanyprzez P .Dlaka»dego n zakładamy,»erozkład P ( n )

jestabsolutnieci¡gływzgl¦dempewnej –sko«czonejmiary µ ( n ) .G¦sto±¢

wzgl¦demtejmiaryoznaczamy p ( x ( n ) ; ).Warto±¢oczekiwan¡mierzalnej

funkcji g ( X ( n ) )wzgl¦demmiaryprobabilistycznej P ( n )

0 oznaczamyprzez

E 0 g ( X ( n ) ) .Wszczególnieinteresuj¡cymnasprzypadku,gdy g ( X ( n ) )=

1UKRYTEMODELEMARKOWA 5

ln p ( X ( n ) ; ) ,danajestonawzorem:

ln p ( X ( n ) ; )

ln p ( X ( n ) ; ) P 0 ( dx ( n ) ) . (1)

E 0

1.2.2Ła«cuchyMarkowa

Oła«cuchachMarkowa(b¦dziemyczasemoznacza¢skrótowo—ŁM)po-

wstałoszeregpublikacji.Wniniejszejpracyprzedstawionezostan¡jedynie

elementyteoriiniezb¦dnedozgł¦bieniadalszejcz¦±citekstu 5 .

Deﬁnicja1 Ci¡gzmiennychlosowych ( X t ) owarto±ciachwprzeliczalnym

zbiorzeS X (przestrzenistanów)nazywamyła«cuchemMarkowawtedyityl-

kowtedy,gdydlaka»degot 2 N ika»degoci¡gux 1 ,x 2 ,...,x t 2 S X mamy

P ( X t = x t | X t − 1 = x t − 1 ,...,X 2 = x 2 ,X 1 = x 1 )=

= P ( X t = x t | X t − 1 = x t − 1 )

(2)

je±litylkoP ( X t − 1 = x t − 1 ,...,X 2 = x 2 ,X 1 = x 1 ) > 0 .

Nała«cuchMarkowamo»emypatrze¢jakonaprocesstochastyczny.Wa-

runekwdeﬁnicji1mówiwtedytyle,»eewolucjaprocesuzale»yjedynieod

bie»¡cegostanu.Zatemnakształtowaniesi¦zmiennej X t wka»dejchwi-

li t mawpływtylkoiwył¡czniewarto±¢procesuwchwili t − 1(intere-

sujenasprzypadekdyskretny).Je»eliprawdopodobie«stwaprzej±ciami¦-

dzystanaminiezale»¡odchwili,wktórejrozpatrujemyproces,tomówi-

my,»eła«cuchMarkowajestjednorodnywczasie.Prawdopodobie«stwo

przej±ciadostanu j zestanu i b¦dziemywtedyoznacza¢jako p ij

gdzie

p ij = P ( X 2 = j | X 1 = i )= P ( X t +1 = j | X t = i )dlaka»dego t

.Macierz

P =[ p ij ]jednorodnegoŁMb¦dziemynazywa¢macierz¡przej±¢.

Deﬁnicja2 Je±li ( X t ) 1 t =1 jestła«cuchemMarkowa,torozkładzmiennej

losowejX 1 nazywamyrozkładempocz¡tkowym.

5 Podstaw¡tejcz¦±cipracybyłpodr¦cznik[22]

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: