Skrytý Markovův model

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Skrytý Markovův model (angl. HMM) je statistický Markovův model, který modeluje systém za předpokladu, že jde o Markovův proces se skrytými (nepozorovanými) stavy. HMM může být znázorněn pomocí nejjednodušší dynamické Bayesovy sítě. Matematické základy modelu vyvinul L. E. Baum spolu se svým týmem spolupracovníků.[1][2][3] Problematika velmi úzce souvisí s dřívější prací Ruslana L. Stratonoviche, který pracoval na lineárním problému filtrování[4] a jako první popsal dopředně-zpětný algoritmus.

V jednodušších Markovových modelech (jako je Markovův řetězec), je stav systému viditelný pozorovateli, tudíž pravděpodobnost změny stavu je jediný parametr modelu. Naopak ve skrytých Markovových modelech stav není pozorovateli viditelný, ale výstup, který je na stavu závislý, viditelný je. Každý stav má pravděpodobnostní vliv na výstup systému. Tedy posloupnost výstupů skrytého Markovova modelu vypovídá o posloupnosti vnitřních stavů, která tuto posloupnost vygenerovala. Přívlastek skrytý se tedy vztahuje na posloupnost vnitřních stavů, kterými model prošel, nikoliv na parametry modelu (model se nazývá skrytý, ačkoliv jsou jeho parametry dány přesně a jsou známé).

Skryté Markovovy modely jsou známé zejména na poli rozpoznávání časových vzorů. Mezi ně spadá například rozpoznávání řeči, rukou psaného písma, gest[5] a POS taging. Využití nalézá také v bioinformatice.

Skryté Markovovy modely lze považovat za zobecnění smíšených modelů, ve kterých nejsou skryté proměnné (nebo latentní proměnné) nezávislé jedna na druhé, ale naopak jsou navzájem spojené Markovovým procesem. V poslední době byly skryté Markovovy modely zobecněny na párové Markovovy modely a tripletové Markovovy modely, které umožňují využití modelu i na komplexnější datové struktury[6][7] a modelování nestacionárních dat.[8][9]

Popis pomocí problému uren[editovat | editovat zdroj]

Obrázek 1. Pravděpodobnostní parametry skrytého Markovova modelu (příklad)
X — stavy modelu
y — možná pozorování modelu
a — pravděpodobnost přechodu mezi stavy
b — pravděpodobnosti výstupů

Ve své diskrétní formě lze skrytý Markovův proces znázornit zobecněním problému uren, ve kterém je každý objekt před dalším krokem navrácen do své původní urny.[10] Uvažujeme následující příklad: v místnosti, do které pozorovatel nevidí, je duch. Místnost obsahuje urny X1, X2, X3, ... Každá z uren obsahuje známý počet různých míčků. Míčky jsou označené y1, y2, y3, ... Duch náhodně vybere jednu z uren a vytáhne z ní náhodný míček. Míček následně položí na přepravní pás, který jej vyveze ven. Pozorovatel tedy vidí posloupnost vytažených míčků, ale není mu známa posloupnost uren, ze kterých bylo taženo. Duch k výběru urny využívá následující postup: výběr urny pro vytažení n-tého míčku závisí pouze na náhodném čísle a na výběru urny pro vytažení (n−1)-ho míčku. Výběr míčku tedy přímo nezávisí na sekvenci předešlých uren ze kterých bylo taženo, ale pouze na urně, ze které byl vytažen n-1 míček. A proto se jedná o Markovův proces. Tento proces popisuje horní část obrázku 1.

Samotný Markovův proces nemůže být pozorován (lze pozorovat pouze sekvenci výstupů), a proto se tomu to procesu říká skrytý Markovův proces. Znázorňuje to spodní část obrázku 1, ze kterého je patrné, že v každém stavu může být tažen míček y1, y2, y3 nebo y4. Tedy ačkoliv pozorovatel zná rozmístění uren a právě viděl posloupnost tří vytažených míčků, nemůže si být jistý, ze které urny duch vytáhl třetí míček. Lze pouze určit pravděpodobnosti s jakými byl třetí míček z jednotlivých uren vytažen.

Reference[editovat | editovat zdroj]

  1. Baum, L. E. (1966).  "Statistical Inference for Probabilistic Functions of Finite State Markov Chains". The Annals of Mathematical Statistics 37 (6): 1554–1563. doi:10.1214/aoms/1177699147. 
  2. Baum, L. E. (1968).  "Growth transformations for functions on manifolds". Pacific Journal of Mathematics 27 (2): 211–227. doi:10.2140/pjm.1968.27.211. 
  3. Baum, L.E. (1972).  "An Inequality and Associated Maximization Technique in Statistical Estimation of Probabilistic Functions of a Markov Process". Inequalities 3: 1–8. 
  4. Stratonovich, R.L. (1960).  "Conditional Markov Processes". Theory of Probability and its Applications 5: 156–178. doi:10.1137/1105015. 
  5. Thad Starner, Alex Pentland. Real-Time American Sign Language Visual Recognition From Video Using Hidden Markov Models. Master's Thesis, MIT, Feb 1995, Program in Media Arts
  6. Pr. Pieczynski, W. Pieczynski, Multisensor triplet Markov chains and theory of evidence, International Journal of Approximate Reasoning, Vol. 45, No. 1, pp. 1-16, 2007.
  7. Boudaren et al., M. Y. Boudaren, E. Monfrini, W. Pieczynski, and A. Aissani, Dempster-Shafer fusion of multisensor signals in nonstationary Markovian context, EURASIP Journal on Advances in Signal Processing, No. 134, 2012.
  8. Lanchantin et al., P. Lanchantin and W. Pieczynski, Unsupervised restoration of hidden non stationary Markov chain using evidential priors, IEEE Trans. on Signal Processing, Vol. 53, No. 8, pp. 3091-3098, 2005.
  9. Boudaren et al., M. Y. Boudaren, E. Monfrini, and W. Pieczynski, Unsupervised segmentation of random discrete data hidden with switching noise distributions, IEEE Signal Processing Letters, Vol. 19, No. 10, pp. 619-622, October 2012.
  10. Lawrence R. Rabiner (February 1989).  "A tutorial on Hidden Markov Models and selected applications in speech recognition". Proceedings of the IEEE 77 (2): 257–286. doi:10.1109/5.18626.  [1]