Skrytý Markovův model - Hidden Markov model

Skrytý Markovův model ( HMM ) je statistický Markovův model, ve kterém se předpokládá, že se modelovaný systém chová jako Markovův proces s nepozorovatelnými („ skrytými “) stavy. Jako součást definice HMM předpokládá, že existuje pozorovatelný proces, jehož chování je známým způsobem „ovlivněno“ . Cílem je dozvědět se o tom pozorováním . HMM vyžaduje, aby v každém okamžiku musel být výsledek „ovlivněn“ výhradně výsledkem a tím, že historie a předchozí výsledky nesmí mít žádný vliv na výsledek

Skryté Markovovy modely jsou známé pro své aplikace v termodynamice , statistické mechanice , fyzice , chemii , ekonomii , financích , zpracování signálu , teorii informací , rozpoznávání vzorů -jako je řeč , rukopis , rozpoznávání gest , označování části řeči , sledování hudby , částečné výboje a bioinformatika .

Definice

Nechme a buďme stochastické procesy v diskrétním čase a . Dvojice je skrytý Markovův model, pokud

  • je Markovův proces, jehož chování není přímo pozorovatelné („skryté“);
Pro každý a každý Borel set .

Nechť a stochastické procesy jsou spojitý čas. Dvojice je skrytý Markovův model, pokud

  • je Markovův proces, jehož chování není přímo pozorovatelné („skryté“);
  • ,
pro každou borelskou sadu a každou rodinu borelských sad

Terminologie

Stavy procesu (resp. Se nazývají skryté stavy a (resp. Se nazývá emisní pravděpodobnost nebo výstupní pravděpodobnost) .

Příklady

Kreslení koulí ze skrytých uren

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

Ve své diskrétní podobě lze skrytý Markovův proces vizualizovat jako zobecnění problému s urnou s výměnou (kde je každá položka z urny před dalším krokem vrácena na původní urnu). Zvažte tento příklad: v místnosti, která není pro pozorovatele viditelná, je džin. Místnost obsahuje urny X1, X2, X3, ... z nichž každá obsahuje známou směs koulí, každá koule je označena y1, y2, y3, .... Džin si v té místnosti vybere urnu a náhodně z této urny vytáhne míč. Poté umístí míč na dopravní pás, kde může pozorovatel sledovat posloupnost míčků, ale nikoli sled uren, ze kterých byly vytaženy. Džin má nějaký postup, jak si vybrat urny; volba urny pro n -tý míč závisí pouze na náhodném čísle a výběru urny pro ( n  -1) -tý míč. Volba urny nezávisí přímo na urnách vybraných před touto jedinou předchozí urnou; proto se tomu říká Markovův proces . Lze to popsat v horní části obrázku 1.

Nelze pozorovat samotný Markovův proces, pouze sled označených koulí, proto se tomuto uspořádání říká „skrytý Markovův proces“. To je znázorněno na spodní části diagramu zobrazeného na obrázku 1, kde je vidět, že koule y1, y2, y3, y4 lze kreslit v každém stavu. I když pozorovatel zná složení uren a právě pozoroval na dopravníkovém pásu sled tří koulí, např. Y1, y2 a y3, pozorovatel si stále nemůže být jistý, kterou urnu ( tj . V jakém stavu) džin nakreslil třetí míč od. Pozorovatel však může zpracovat další informace, například pravděpodobnost, že třetí míč pochází z každé z uren.

Hádání počasí

Uvažujme o dvou kamarádech, Alice a Bobovi, kteří žijí daleko od sebe a kteří spolu denně telefonují o tom, co ten den dělali. Boba zajímají jen tři aktivity: procházky v parku, nakupování a úklid bytu. Volba, co dělat, je určena výhradně počasím v daný den. Alice nemá žádné konkrétní informace o počasí, ale zná obecné trendy. Na základě toho, co jí Bob říká, že to dělal každý den, se Alice snaží uhodnout, jaké muselo být počasí.

Alice věří, že počasí funguje jako diskrétní markovský řetězec . Existují dva stavy, „Rainy“ a „Sunny“, ale ona je nemůže přímo pozorovat, to znamená, že jsou jí skryty . Každý den existuje určitá šance, že Bob bude v závislosti na počasí provádět jednu z následujících činností: „procházka“, „obchod“ nebo „úklid“. Jelikož Bob říká Alici o svých aktivitách, toto jsou postřehy . Celý systém je skrytý Markovův model (HMM).

Alice zná obecné trendy počasí v této oblasti a to, co Bob v průměru rád dělá. Jinými slovy, parametry HMM jsou známy. V Pythonu mohou být zastoupeny následovně :

states = ('Rainy', 'Sunny')
 
observations = ('walk', 'shop', 'clean')
 
start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
 
transition_probability = {
   'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
   'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
   }
 
emission_probability = {
   'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
   'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
   }

V tomto kousku kódu start_probabilitypředstavuje Alicinu víru, v jakém stavu je HMM, když jí Bob poprvé zavolá (ví jen, že v průměru bývá deštivo). Zde použité konkrétní rozdělení pravděpodobnosti není rovnovážné, což je (vzhledem k pravděpodobnostem přechodu) přibližně {'Rainy': 0.57, 'Sunny': 0.43}. transition_probabilityPředstavuje změnu počasí v podkladových Markov řetězce. V tomto případě je jen 30% šance, že zítra bude slunečno, pokud bude dnes deštivo. emission_probabilityReprezentuje jak pravděpodobně Bob je vykonávat určitou činnost na každý den. Pokud prší, je 50% šance, že si uklízí byt; pokud je slunečno, je 60% šance, že je venku na procházce.

Grafické znázornění daného HMM

Podobný příklad je dále rozpracován na stránce algoritmu Viterbi .

Strukturální architektura

Níže uvedený diagram ukazuje obecnou architekturu instance HMM. Každý oválný tvar představuje náhodnou proměnnou, která může přijmout libovolnou z řady hodnot. Náhodná veličina x ( t ) je skrytý stav v čase t (u modelu z výše uvedeného diagramu x ( t ) ∈ {  x 1x 2x 3  }). Náhodná veličina y ( t ) je pozorování v čase t (s y ( t ) ∈ {  y 1y 2y 3y 4  }). Šipky v diagramu (často nazývané mřížkový diagram ) označují podmíněné závislosti.

Z diagramu je zřejmé, že podmíněné rozdělení pravděpodobnosti skryté proměnné x ( t ) v čase t , vzhledem k hodnotám skryté proměnné x vždy, závisí pouze na hodnotě skryté proměnné x ( t  - 1 ); hodnoty v čase t  - 2 a dříve nemají žádný vliv. Tomu se říká vlastnost Markov . Podobně hodnota pozorované proměnné y ( t ) závisí pouze na hodnotě skryté proměnné x ( t ) (obojí v čase t ).

Ve zde uvažovaném standardním typu skrytého Markovova modelu je stavový prostor skrytých proměnných diskrétní, zatímco samotná pozorování mohou být diskrétní (typicky generovaná z kategorické distribuce ) nebo spojitá (typicky z Gaussova rozdělení ). Parametry skrytého Markovova modelu jsou dvou typů, přechodové pravděpodobnosti a emisní pravděpodobnosti (také známé jako výstupní pravděpodobnosti ). Pravděpodobnosti přechodu řídí způsob, jakým je zvolen skrytý stav v čase t vzhledem k skrytému stavu v čase .

Předpokládá se, že skrytý stavový prostor sestává z jedné z N možných hodnot, modelovaných jako kategorické rozdělení. (Další možnosti viz níže uvedená část o rozšířeních.) To znamená, že pro každý z N možných stavů, ve kterých může být skrytá proměnná v čase t , existuje pravděpodobnost přechodu z tohoto stavu do každého z N možných stavů skrytá proměnná v čase , pro celkem pravděpodobnosti přechodu. Všimněte si, že množina pravděpodobností přechodu pro přechody z jakéhokoli daného stavu musí být součet 1. Matice přechodových pravděpodobností je tedy Markovova matice . Protože jakoukoli pravděpodobnost přechodu lze určit, jakmile jsou známy ostatní, existuje celkem několik přechodových parametrů.

Navíc pro každý z N možných stavů existuje sada emisních pravděpodobností, které řídí rozdělení pozorované proměnné v určitém čase vzhledem ke stavu skryté proměnné v té době. Velikost této sady závisí na povaze pozorované proměnné. Pokud je například sledovaná proměnná diskrétní s M možnými hodnotami, řízenými kategorickým rozdělením , budou existovat samostatné parametry, pro součet emisních parametrů ve všech skrytých stavech. Na druhou stranu, pokud je pozorovanou proměnnou M -rozměrný vektor distribuovaný podle libovolného vícerozměrného Gaussova rozdělení , budou M parametry ovládající prostředky a parametry řídící kovarianční matici , celkem pro emisní parametry. (V takovém případě, pokud není hodnota M malá, může být praktičtější omezit povahu kovariantství mezi jednotlivými prvky vektoru pozorování, např. Za předpokladu, že prvky jsou na sobě nezávislé nebo méně restriktivně, jsou nezávislé na všech kromě pevného počtu sousedních prvků.)

Časová evoluce skrytého Markovova modelu

Odvození

Pravděpodobnosti přechodu stavu a výstupu HMM jsou indikovány neprůhledností čar v horní části diagramu. Vzhledem k tomu, že jsme pozorovali výstupní sekvenci ve spodní části diagramu, může nás zajímat nejpravděpodobnější posloupnost stavů, které ji mohly vytvořit. Na základě šipek, které jsou přítomny v diagramu, jsou kandidáty následující stavové sekvence:
5 3 2 5 3 2
4 3 2 5 3 2
3 1 2 5 3 2
Nejpravděpodobnější sekvenci můžeme najít vyhodnocením společné pravděpodobnosti obou sled stavů a ​​pozorování pro každý případ (jednoduše vynásobením hodnot pravděpodobnosti, které zde odpovídají neprůhlednosti příslušných šipek). Obecně lze tento typ problému (tj. Nalezení nejpravděpodobnějšího vysvětlení pozorovací sekvence) efektivně vyřešit pomocí Viterbiho algoritmu .

Se skrytými Markovovými modely je spojeno několik inferenčních problémů, jak je uvedeno níže.

Pravděpodobnost pozorované sekvence

Úkolem je co nejlépe vypočítat, vzhledem k parametrům modelu, pravděpodobnost konkrétní výstupní sekvence. To vyžaduje součet všech možných stavových sekvencí:

Pravděpodobnost pozorování sekvence

délky L je dána vztahem

kde součet běží přes všechny možné sekvence skrytých uzlů

S využitím principu dynamického programování lze i tento problém efektivně zvládnout pomocí dopředného algoritmu .

Pravděpodobnost latentních proměnných

Řada souvisejících úkolů se ptá na pravděpodobnost jedné nebo více latentních proměnných vzhledem k parametrům modelu a posloupnosti pozorování

Filtrování

Úkolem je spočítat, vzhledem k parametrům modelu a posloupnosti pozorování, rozdělení na skryté stavy poslední latentní proměnné na konci sekvence, tj . Spočítat . Tento úkol se obvykle používá, když je sekvence latentních proměnných považována za základní stavy, kterými se proces pohybuje v posloupnosti časových bodů, s odpovídajícími pozorováními v každém časovém bodě. Potom je přirozené zeptat se na stav procesu na konci.

Tento problém lze efektivně vyřešit pomocí dopředného algoritmu .

Vyhlazování

To je podobné filtrování, ale ptá se na distribuci latentní proměnné někde uprostřed sekvence, tj. Pro některé vypočítat . Z výše popsané perspektivy to lze považovat za rozdělení pravděpodobnosti přes skryté stavy pro časový bod k v minulosti, vztaženo k času t .

Dopředu dozadu algoritmus je dobrá metoda pro výpočet vyhlazené hodnoty pro všechny skryté stavových proměnných.

Nejpravděpodobnější vysvětlení

Úkol, na rozdíl od předchozích dvou, žádá o společné pravděpodobnosti na celé posloupnosti skrytých stavů, který generoval určitý sled pozorování (viz obrázek vpravo). Tento úkol je obecně použitelný, když jsou HMM aplikovány na různé druhy problémů od těch, pro které jsou použitelné úlohy filtrování a vyhlazování. Příkladem je označování části řeči , kde skryté stavy představují základní části řeči odpovídající pozorované posloupnosti slov. V tomto případě je zajímavá celá posloupnost částí řeči, nikoli pouze část řeči pro jedno slovo, jak by se počítalo filtrování nebo vyhlazování.

Tento úkol vyžaduje nalezení maxima ve všech možných stavových sekvencích a lze jej efektivně vyřešit pomocí Viterbiho algoritmu .

Statistický význam

U některých výše uvedených problémů může být také zajímavé zeptat se na statistickou významnost . Jaká je pravděpodobnost, že sekvence získaná z nějaké nulové distribuce bude mít pravděpodobnost HMM (v případě dopředného algoritmu) nebo maximální pravděpodobnost posloupnosti stavu (v případě Viterbiho algoritmu) alespoň tak velkou, jako je pravděpodobnost konkrétního výstupní sekvence? Když se k vyhodnocení relevance hypotézy pro konkrétní výstupní sekvenci použije HMM, statistická významnost udává falešně pozitivní míru spojenou s tím, že se hypotéza pro výstupní sekvenci neodmítne.

Učení se

Úkolem učení parametrů v HMM je najít vzhledem k výstupní sekvenci nebo sadě takových sekvencí nejlepší sadu pravděpodobností přechodu stavu a emisí. Úkolem je obvykle odvodit odhad maximální pravděpodobnosti parametrů HMM daný množinou výstupních sekvencí. Není znám žádný traktovatelný algoritmus pro přesné řešení tohoto problému, ale lokální maximální pravděpodobnost lze efektivně odvodit pomocí Baum -Welchova algoritmu nebo Baldiho -Chauvinova algoritmu. Algoritmus Baum-Welch je zvláštní případ algoritmu očekávání-zvětšení .

Pokud jsou HMM použity pro predikci časových řad, sofistikovanější Bayesovské inferenční metody, jako je vzorkování Markovova řetězce Monte Carlo (MCMC), se ukázaly jako příznivé oproti nalezení jediného modelu maximální pravděpodobnosti jak z hlediska přesnosti, tak stability. Vzhledem k tomu, že MCMC přináší značnou výpočetní zátěž, v případech, kdy je zajímavá také výpočetní škálovatelnost, je možné se alternativně uchýlit k variačním aproximacím k Bayesovskému závěru, např. Skutečně, přibližný variační odvození nabízí výpočetní účinnost srovnatelnou s maximalizací očekávání, přičemž profil přesnosti poskytuje jen mírně nižší než přesná Bayesovská dedukce typu MCMC.

Aplikace

Profilová HMM modelování vícenásobného zarovnání

HMM lze použít v mnoha polích, kde je cílem obnovit sekvenci dat, která není bezprostředně pozorovatelná (ale jiná data, která na sekvenci závisí) jsou. Aplikace zahrnují:

Dějiny

Skryté Markovovy modely byly popsány v sérii statistických prací Leonarda E. Bauma a dalších autorů ve druhé polovině 60. let. Jednou z prvních aplikací HMM bylo rozpoznávání řeči , které začalo v polovině 70. let minulého století.

Ve druhé polovině 80. let se HMM začaly aplikovat na analýzu biologických sekvencí, zejména DNA . Od té doby se staly všudypřítomnými v oblasti bioinformatiky .

Rozšíření

Ve výše uvedených skrytých Markovových modelech je stavový prostor skrytých proměnných diskrétní, zatímco samotná pozorování mohou být buď diskrétní (obvykle generovaná z kategorické distribuce ), nebo spojitá (typicky z Gaussova rozdělení ). Skryté Markovovy modely lze také zobecnit, aby umožňovaly spojité stavové mezery. Příklady takových modelů jsou ty, kde Markovův proces nad skrytými proměnnými je lineární dynamický systém s lineárním vztahem mezi příbuznými proměnnými a kde všechny skryté a pozorované proměnné sledují gaussovské rozdělení . V jednoduchých případech, jako je právě zmíněný lineární dynamický systém, je přesný závěr odvozitelný (v tomto případě pomocí Kalmanova filtru ); obecně je však přesný závěr v HMM s kontinuálními latentními proměnnými neproveditelný a musí být použity přibližné metody, jako je rozšířený Kalmanův filtr nebo částicový filtr .

Skryté Markovovy modely jsou generativní modely , ve kterých je modelována společná distribuce pozorování a skrytých stavů, nebo ekvivalentně jak předchozí distribuce skrytých stavů ( pravděpodobnosti přechodu ), tak podmíněné rozložení pozorovaných daných stavů ( emisní pravděpodobnosti ). Výše uvedené algoritmy implicitně předpokládají jednotné předchozí rozdělení podle pravděpodobností přechodu. Je však také možné vytvořit skryté Markovovy modely s jinými typy předchozích distribucí. Zjevným kandidátem, vzhledem ke kategorickému rozdělení pravděpodobností přechodu, je Dirichletova distribuce , což je konjugovaná předchozí distribuce kategorické distribuce. Obvykle je vybrána symetrická Dirichletova distribuce, která odráží neznalost stavů, které jsou ze své podstaty pravděpodobnější než ostatní. Jediný parametr této distribuce (nazývaný parametr koncentrace ) řídí relativní hustotu nebo řídkost výsledné přechodové matice. Volba 1 poskytuje rovnoměrné rozdělení. Hodnoty větší než 1 vytvářejí hustou matici, ve které je pravděpodobnost přechodu mezi dvojicemi stavů pravděpodobně téměř stejná. Hodnoty menší než 1 vedou k řídké matici, ve které má pro každý daný zdrojový stav nezanedbatelné pravděpodobnosti přechodu pouze malý počet cílových stavů. Je také možné použít dvouúrovňovou předchozí Dirichletovu distribuci, ve které jedna Dirichletova distribuce (horní distribuce) řídí parametry jiné Dirichletovy distribuce (nižší distribuce), která zase řídí pravděpodobnosti přechodu. Horní rozdělení určuje celkovou distribuci stavů a ​​určuje, jak pravděpodobné je, že každý stav nastane; jeho parametr koncentrace určuje hustotu nebo řídkost stavů. Taková dvouúrovňová předchozí distribuce, kde jsou oba parametry koncentrace nastaveny tak, aby vytvářely řídké distribuce, by mohla být užitečná například při značkování části řeči bez dozoru , kde se některé části řeči vyskytují mnohem častěji než jiné; učební algoritmy, které předpokládají jednotnou předchozí distribuci, si s tímto úkolem obvykle vedou špatně. Parametry modelů tohoto druhu s nejednotnými předchozími distribucemi lze zjistit pomocí Gibbsova vzorkování nebo rozšířených verzí algoritmu maximalizace očekávání .

Rozšíření dříve popsaných skrytých Markovových modelů o Dirichletovy předchozí používá namísto Dirichletovy distribuce Dirichletův proces . Tento typ modelu umožňuje neznámý a potenciálně nekonečný počet stavů. Je běžné používat dvouúrovňový Dirichletův proces, podobný dříve popsanému modelu se dvěma úrovněmi Dirichletových distribucí. Takový model se nazývá hierarchický skrytý Markovův model Dirichletova procesu nebo zkráceně HDP-HMM . Původně byl popsán pod názvem „Nekonečný skrytý Markovův model“ a byl dále formalizován v.

Jiný typ rozšíření používá místo generativního modelu standardních HMM diskriminační model . Tento typ modelu spíše modeluje podmíněné rozložení skrytých stavů vzhledem k pozorování než modelování společného rozdělení. Příkladem tohoto modelu je takzvaný Markovův model maximální entropie (MEMM), který modeluje podmíněné rozložení stavů pomocí logistické regrese (známý také jako „ model maximální entropie “). Výhodou tohoto typu modelu je, že lze modelovat libovolné rysy (tj. Funkce) pozorování, což umožňuje vnést do modelu znalosti specifické pro danou doménu. Modely tohoto druhu nejsou omezeny na modelování přímých závislostí mezi skrytým stavem a jeho přidruženým pozorováním; spíše lze do procesu použitého ke stanovení hodnoty skrytého stavu zahrnout rysy blízkých pozorování, kombinací souvisejících pozorování a blízkých pozorování nebo ve skutečnosti libovolných pozorování v jakékoli vzdálenosti od daného skrytého stavu. Kromě toho není nutné, aby tyto funkce byly na sobě statisticky nezávislé , jako by tomu bylo v případě, kdyby byly tyto vlastnosti použity v generativním modelu. Nakonec lze použít spíše libovolné funkce přes páry sousedních skrytých stavů než jednoduché pravděpodobnosti přechodu. Nevýhody takových modelů jsou: (1) Typy předchozích distribucí, které lze umístit do skrytých stavů, jsou velmi omezené; (2) Není možné předpovědět pravděpodobnost vidění libovolného pozorování. Toto druhé omezení v praxi často nepředstavuje problém, protože mnoho běžných použití HMM takové prediktivní pravděpodobnosti nevyžaduje.

Varianta dříve popsaného diskriminačního modelu je podmíněné náhodné pole s lineárním řetězcem . Toto používá spíše neorientovaný grafický model (alias Markovovo náhodné pole ) než směrované grafické modely MEMM a podobných modelů. Výhodou tohoto typu modelu je, že netrpí takzvaným problémem předpětí štítků u MEMM, a proto může provádět přesnější předpovědi. Nevýhodou je, že trénink může být pomalejší než u MEMM.

Ještě další variantou je faktoriální skrytý Markovův model , který umožňuje, aby bylo jediné pozorování podmíněno odpovídajícími skrytými proměnnými sady nezávislých Markovových řetězců, nikoli jediným Markovovým řetězcem. Je ekvivalentní jedinému HMM se stavy (za předpokladu, že existují stavy pro každý řetězec), a proto je učení v takovém modelu obtížné: pro sekvenci délky má přímý Viterbiho algoritmus složitost . K nalezení přesného řešení by mohl být použit algoritmus spojovacího stromu, který však vede ke složitosti. V praxi by mohly být použity přibližné techniky, jako jsou variační přístupy.

Všechny výše uvedené modely lze rozšířit tak, aby umožňovaly vzdálenější závislosti mezi skrytými stavy, např. Umožňovaly, aby byl daný stav závislý spíše na předchozích dvou nebo třech stavech než na jednom předchozím stavu; tj. pravděpodobnosti přechodu jsou rozšířeny tak, aby zahrnovaly sady tří nebo čtyř sousedních stavů (nebo obecně sousedních stavů). Nevýhodou takových modelů je, že algoritmy dynamického programování pro jejich trénink mají dobu běhu, pro sousední stavy a celková pozorování (tj. Markovův řetězec s délkou).

Dalším nedávným rozšířením je Markovův tripletový model , ve kterém je přidán pomocný základní proces k modelování některých datových specifik. Bylo navrženo mnoho variant tohoto modelu. Je třeba také zmínit zajímavé spojení, které bylo vytvořeno mezi teorií důkazů a tripletovými Markovovými modely a které umožňuje sloučit data v Markovianském kontextu a modelovat nestacionární data. Všimněte si toho, že v nedávné literatuře byly také navrženy alternativní víceproudové strategie fúze dat, např

Nakonec bylo v roce 2012 navrženo jiné odůvodnění k řešení problému modelování nestacionárních dat pomocí skrytých Markovových modelů. Spočívá v použití malé rekurentní neuronové sítě (RNN), konkrétně rezervoárové sítě, k zachycení vývoje časové dynamiky v pozorovaných datech. Tyto informace, zakódované ve formě vysoce dimenzionálního vektoru, se používají jako kondicionující proměnná pravděpodobností přechodu stavu HMM. Při takovém nastavení nakonec získáme nestacionární HMM, jehož pravděpodobnost přechodu se v průběhu času vyvíjí způsobem, který je odvozen ze samotných dat, na rozdíl od nějakého nerealistického ad-hoc modelu časové evoluce.

Model vhodný v kontextu podélných dat se nazývá latentní Markovův model. Základní verze tohoto modelu byla rozšířena o jednotlivé kovariáty, náhodné efekty a modelování složitějších datových struktur, jako jsou víceúrovňová data. Úplný přehled latentních Markovových modelů se zvláštním zřetelem na předpoklady modelu a na jejich praktické využití je uveden v

Viz také

Reference

externí odkazy

Pojmy