Ukryty model Markowa - Hidden Markov model

Ukryty model Markowa ( HMM ) to statystyczny model Markowa, w którym zakłada się, że modelowany system zachowuje się jak proces Markowa z nieobserwowalnymi („ ukrytymi ”) stanami. W ramach definicji HMM zakłada, że ​​istnieje obserwowalny proces, na którego zachowanie „wpływa” w znany sposób. Celem jest poznanie poprzez obserwację . HMM wymaga, aby w każdym przypadku na wynik „wpływał” wyłącznie wynik historii i wcześniejszych wyników, nie mogą one mieć żadnego wpływu na wynik${\ Displaystyle Y_ {n}}$${\ Displaystyle X}$${\ Displaystyle X}$${\ Displaystyle Y}$${\displaystyle t=n_{0},}$${\displaystyle Y_{n_{0}}}$${\displaystyle X_{n_{0}},}$${\ Displaystyle \ {X_ {n} \} _ {n < n_ {0}}}$${\ Displaystyle \ {Y_ {n} \} _ {n < n_ {0}},}$${\displaystyle Y_{n_{0}}.}$

Ukryte modele Markowa są znane ze swoich zastosowań w termodynamice , mechanice statystycznej , fizyce , chemii , ekonomii , finansach , przetwarzaniu sygnałów , teorii informacji , rozpoznawaniu wzorców - takich jak mowa , pismo ręczne , rozpoznawanie gestów , znakowanie części mowy , śledzenie partytury , wyładowania niezupełne i bioinformatyka .

Definicja

Pozwól i bądź procesami stochastycznymi w czasie dyskretnym i . Para jest ukrytym modelem Markowa, jeśli ${\ Displaystyle X_ {n}}$${\ Displaystyle Y_ {n}}$${\displaystyle n\geq 1}$${\ Displaystyle (X_ {n}, Y_ {n})}$

• ${\ Displaystyle X_ {n}}$jest procesem Markowa, którego zachowanie nie jest bezpośrednio obserwowalne („ukryte”);
• ${\ Displaystyle \ operatorname {\ mathbf {P} } {\ bigl (} Y_ {n} \ w A \ {\ bigl |} \ X_ {1} = x_ {1}, \ ldots, X_ {n} = x_ {n}{\bigr )}=\operatorname {\mathbf {P} } {\bigl (}Y_{n}\in A\ {\bigl |}\ X_{n}=x_{n}{\bigr ) },}$

dla każdego i każdej Borel zestawu .${\displaystyle n\geq 1,}$ ${\displaystyle x_{1},\ldots,x_{n}}$${\ Displaystyle A}$

Pozwól i bądź ciągłymi procesami stochastycznymi. Para jest ukrytym modelem Markowa, jeśli ${\ Displaystyle X_ {t}}$${\ Displaystyle Y_ {t}}$${\ Displaystyle (X_ {t}, Y_ {t})}$

• ${\ Displaystyle X_ {t}}$ jest procesem Markowa, którego zachowanie nie jest bezpośrednio obserwowalne („ukryte”);
• ${\ Displaystyle \ operatorname {\ mathbf {P} } (Y_ {t_{0}} \ w A \ mid \ {X_ {t} \ w B_ {t} \} _ {t \ równa t_ {0}}) =\nazwa operatora {\mathbf {P} } (Y_{t_{0}}\w A\mid X_{t_{0}}\w B_{t_{0}})}$,

za każdy zestaw Borel i każdą rodzinę zestawów Borel${\displaystyle t_{0},}$${\displaystyle A}$${\ Displaystyle \ {B_ {t} \} _ {t \ równa t_ {0}}.}$

Terminologia

Stany procesu (odpowiednio nazywane są stanami ukrytymi i (odpowiednio nazywane są prawdopodobieństwem emisji lub prawdopodobieństwem wyjściowym) . ${\ Displaystyle X_ {n}}$${\ Displaystyle X_ {t})}$${\ Displaystyle \ operatorname {\ mathbf {P} } {\ bigl (} Y_ {n} \ w A \ mid X_ {n} = x_ {n} {\ duży )}}$${\ Displaystyle \ operatorname {\ mathbf {P} } {\ Bigl (} Y_ {t} \ w A \ mid X_ {t} \ w B_ {t} {\ Bigr}})}$

Przykłady

Rysowanie kulek z ukrytych urn

Rysunek 1. Parametry probabilistyczne ukrytego modelu Markowa (przykład)
X — stany
y — możliwe obserwacje
a — prawdopodobieństwa przejścia stanów
b — prawdopodobieństwa wyjściowe

W swojej dyskretnej formie ukryty proces Markowa można zwizualizować jako uogólnienie problemu urny z wymianą (gdzie każdy przedmiot z urny jest zwracany do oryginalnej urny przed następnym krokiem). Rozważmy ten przykład: w pokoju, który nie jest widoczny dla obserwatora, znajduje się dżin. W pokoju znajdują się urny X1, X2, X3, ... z których każda zawiera znaną mieszankę kul, każda kula jest oznaczona jako y1, y2, y3, ... . Dżin wybiera urnę w tym pokoju i losowo dobiera z niej kulę. Następnie umieszcza kulę na przenośniku taśmowym, gdzie obserwator może obserwować kolejność piłek, ale nie kolejność urn, z których zostały wyciągnięte. Dżin ma jakąś procedurę wyboru urn; wybór urny dla n- tej kuli zależy tylko od liczby losowej i wyboru urny dla ( n  − 1)-tej kuli. Wybór urny nie zależy bezpośrednio od urn wybranych przed tą pojedynczą poprzednią urną; dlatego nazywa się to procesem Markowa . Można to opisać w górnej części rysunku 1.

Samego procesu Markowa nie można zaobserwować, a jedynie sekwencję oznaczonych kulek, stąd ten układ nazywany jest „ukrytym procesem Markowa”. Ilustruje to dolna część diagramu pokazanego na rysunku 1, gdzie widać, że kulki y1, y2, y3, y4 można narysować w każdym stanie. Nawet jeśli obserwator zna skład urn i właśnie zaobserwował sekwencję trzech kulek, np. y1, y2 i y3 na taśmociągu, nadal nie może być pewien, którą urnę ( tj. w jakim stanie) narysował dżin trzecia piłka z. Jednak obserwator może wypracować inne informacje, takie jak prawdopodobieństwo, że trzecia kula pochodzi z każdej urny.

Gra w zgadywanie pogody

Weźmy pod uwagę dwóch przyjaciół, Alice i Boba, którzy mieszkają daleko od siebie i codziennie rozmawiają przez telefon o tym, co robili tego dnia. Boba interesują tylko trzy czynności: spacery po parku, zakupy i sprzątanie swojego mieszkania. O tym, co robić, decyduje wyłącznie pogoda w danym dniu. Alicja nie ma konkretnych informacji o pogodzie, ale zna ogólne trendy. Bazując na tym, co Bob mówi jej, że robił każdego dnia, Alice próbuje odgadnąć, jaka musiała być pogoda.

Alicja uważa, że ​​pogoda działa jak dyskretny łańcuch Markowa . Istnieją dwa stany, „Deszczowy” i „Słoneczny”, ale nie może ich bezpośrednio obserwować, to znaczy są przed nią ukryte . Każdego dnia istnieje pewna szansa, że ​​Bob wykona jedną z następujących czynności, w zależności od pogody: „spacer”, „sklep” lub „sprzątanie”. Ponieważ Bob opowiada Alicji o swoich działaniach, to są obserwacje . Cały system to ukryty model Markowa (HMM).

Alicja zna ogólne trendy pogodowe w okolicy i wie, co średnio lubi robić Bob. Innymi słowy, parametry HMM są znane. W Pythonie mogą być reprezentowane w następujący sposób :

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},
   }

W tym fragmencie kodu start_probabilityreprezentuje przekonanie Alicji o tym, w jakim stanie znajduje się HMM, kiedy Bob dzwoni do niej po raz pierwszy (wie tylko, że średnio jest deszczowo). Zastosowany tu szczególny rozkład prawdopodobieństwa nie jest rozkładem równowagi, który jest (biorąc pod uwagę prawdopodobieństwa przejścia) w przybliżeniu {'Rainy': 0.57, 'Sunny': 0.43}. transition_probabilityReprezentuje zmianę pogody w instrumencie bazowym łańcucha Markowa. W tym przykładzie istnieje tylko 30% szans, że jutro będzie słonecznie, jeśli dzisiaj będzie deszcz. emission_probabilityReprezentuje ile prawdopodobne Bob jest do wykonywania określonej działalności na każdy dzień. Jeśli pada deszcz, jest 50% szans, że sprząta swoje mieszkanie; jeśli jest słonecznie, istnieje 60% szansa, że ​​wyjdzie na spacer.

Podobny przykład jest dalej rozwijany na stronie Algorytm Viterbiego .

Architektura strukturalna

Poniższy diagram przedstawia ogólną architekturę instancji HMM. Każdy owalny kształt reprezentuje zmienną losową, która może przyjąć dowolną z wielu wartości. Zmienna losowa x ( t ) jest stanem ukrytym w czasie t (z modelem z powyższego diagramu x ( t ) ∈ {  x ₁ ,  x ₂ ,  x ₃  }). Zmienna losowa y ( t ) jest obserwacją w czasie t (z y ( t ) ∈ {  y ₁ ,  y ₂ ,  y ₃ ,  y ₄  }). Strzałki na diagramie (często nazywane diagramem kratowym ) oznaczają zależności warunkowe.

Z wykresu jasno wynika, że rozkład prawdopodobieństwa warunkowego zmiennej ukrytej x ( t ) w czasie t , biorąc pod uwagę wartości zmiennej ukrytej x przez cały czas, zależy tylko od wartości zmiennej ukrytej x ( t  − 1 ); wartości w czasie t  − 2 i wcześniej nie mają wpływu. Nazywa się to własnością Markowa . Podobnie wartość obserwowanej zmiennej y ( t ) zależy tylko od wartości ukrytej zmiennej x ( t ) (obie w czasie t ).

W rozważanym tutaj standardowym typie ukrytego modelu Markowa przestrzeń stanów ukrytych zmiennych jest dyskretna, podczas gdy same obserwacje mogą być albo dyskretne (zazwyczaj generowane z rozkładu kategorycznego ) albo ciągłe (zazwyczaj z rozkładu Gaussa ). Parametry ukrytego modelu Markowa są dwojakiego rodzaju, prawdopodobieństwa przejścia i prawdopodobieństwa emisji (znane również jako prawdopodobieństwa wyjściowe ). Prawdopodobieństwa przejścia kontrolują sposób, w jaki stan ukryty w czasie t jest wybierany, biorąc pod uwagę stan ukryty w czasie . ${\displaystyle t-1}$

Zakłada się, że ukryta przestrzeń stanów składa się z jednej z N możliwych wartości, modelowanych jako rozkład kategoryczny. (Zobacz sekcję poniżej o rozszerzeniach, aby poznać inne możliwości.) Oznacza to, że dla każdego z N możliwych stanów, w których może znajdować się zmienna ukryta w czasie t , istnieje prawdopodobieństwo przejścia z tego stanu do każdego z N możliwych stanów ukryta zmienna w czasie , dla sumy prawdopodobieństw przejścia. Zauważ, że zbiór prawdopodobieństw przejść dla przejść z dowolnego stanu musi sumować się do 1. Zatem macierz prawdopodobieństw przejścia jest macierzą Markowa . Ponieważ każde prawdopodobieństwo przejścia można określić, gdy znane są inne, istnieje suma parametrów przejścia. ${\displaystyle t+1}$${\ Displaystyle N ^ {2}}$${\ Displaystyle N \ razy N}$${\ Displaystyle N (N-1)}$

Dodatkowo dla każdego z N możliwych stanów istnieje zbiór prawdopodobieństw emisji rządzących rozkładem obserwowanej zmiennej w określonym czasie, biorąc pod uwagę stan ukrytej zmiennej w tym czasie. Wielkość tego zbioru zależy od charakteru obserwowanej zmiennej. Na przykład, jeśli obserwowana zmienna jest dyskretna z M możliwymi wartościami, zarządzanymi przez rozkład kategoryczny , będą oddzielne parametry, dla sumy parametrów emisji we wszystkich ukrytych stanach. Z drugiej strony, jeśli obserwowana zmienna jest M- wymiarowym wektorem rozłożonym zgodnie z dowolnym wielowymiarowym rozkładem Gaussa , będzie M parametrów kontrolujących średnie i parametry kontrolujące macierz kowariancji , dla wszystkich parametrów emisji. (W takim przypadku, o ile wartość M nie jest mała, bardziej praktyczne może być ograniczenie charakteru kowariancji między poszczególnymi elementami wektora obserwacji, np. przez założenie, że elementy są od siebie niezależne lub mniej restrykcyjne, są niezależne od wszystkich elementów poza stałą liczbą sąsiednich elementów.) ${\ Displaystyle M-1}$${\ Displaystyle N (M-1)}$${\ Displaystyle {\ Frac {M (M + 1)} {2}}}$${\ Displaystyle N \ lewo (M + {\ Frac {M (M + 1)} {2}} \ prawej) = {\ Frac {NM (M + 3)} {2}} = O (NM ^ {2} )}$

Wnioskowanie

Przejście stanu i prawdopodobieństwa wyjścia HMM są wskazane przez nieprzezroczystość linii w górnej części diagramu. Biorąc pod uwagę, że zaobserwowaliśmy sekwencję wyjściową w dolnej części diagramu, możemy być zainteresowani najbardziej prawdopodobną sekwencją stanów, które mogły ją wytworzyć. Na podstawie strzałek, które są obecne na diagramie, kandydatami są następujące ciągi stanów:
5 3 2 5 3 2
4 3 2 5 3 2
3 1 2 5 3 2
Możemy znaleźć najbardziej prawdopodobną sekwencję, oceniając wspólne prawdopodobieństwo obu sekwencja stanów i obserwacje dla każdego przypadku (po prostu przez pomnożenie wartości prawdopodobieństwa, które tutaj odpowiadają przezroczystościom zaangażowanych strzałek). Ogólnie rzecz biorąc, tego typu problem (tzn. znalezienie najbardziej prawdopodobnego wyjaśnienia sekwencji obserwacji) można skutecznie rozwiązać za pomocą algorytmu Viterbiego .

Kilka problemów z wnioskowaniem jest związanych z ukrytymi modelami Markowa, jak opisano poniżej.

Prawdopodobieństwo obserwowanej sekwencji

Zadanie polega na tym, aby w najlepszy sposób obliczyć, biorąc pod uwagę parametry modelu, prawdopodobieństwo wystąpienia określonej sekwencji wyjściowej. Wymaga to zsumowania wszystkich możliwych sekwencji stanów:

Prawdopodobieństwo zaobserwowania sekwencji

${\ Displaystyle Y = y (0), y (1), \ kropki, y (L-1) \,}$

długości L jest podane przez

${\ Displaystyle P (Y) = \ suma _ {X} P (Y \ średni X) P (X), \,}$

gdzie suma przebiega przez wszystkie możliwe sekwencje ukrytych węzłów

${\ Displaystyle X = x (0), x (1), \ kropki, x (L-1). \,}$

Stosując zasadę programowania dynamicznego , również ten problem można skutecznie rozwiązać za pomocą algorytmu do przodu .

Prawdopodobieństwo zmiennych latentnych

Szereg powiązanych zadań pyta o prawdopodobieństwo wystąpienia jednej lub więcej zmiennych ukrytych, biorąc pod uwagę parametry modelu i sekwencję obserwacji ${\ Displaystyle y (1), \ kropki, y (t).}$

Filtracja

Zadanie polega na obliczeniu, biorąc pod uwagę parametry modelu i sekwencję obserwacji, rozkład na ukryte stany ostatniej zmiennej latentnej na końcu ciągu, czyli obliczyć . To zadanie jest zwykle używane, gdy sekwencja zmiennych ukrytych jest uważana za stany leżące u podstaw procesu, przez które przechodzi proces w sekwencji punktów w czasie, z odpowiednimi obserwacjami w każdym punkcie w czasie. Wtedy naturalne jest pytanie na końcu o stan procesu. ${\ Displaystyle P (x (t) \ | \ y (1), \ kropki, y (t))}$

Ten problem można skutecznie rozwiązać za pomocą algorytmu forward .

Wygładzanie

Jest to podobne do filtrowania, ale pyta o rozkład zmiennej ukrytej gdzieś w środku sekwencji, tj. o obliczenie dla niektórych . Z perspektywy opisanej powyżej można to traktować jako rozkład prawdopodobieństwa w stanach ukrytych dla punktu w czasie k w przeszłości, względem czasu t . ${\ Displaystyle P (x (k) \ | \ y (1), \ kropki, y (t))}$${\displaystyle k<t}$

Algorytm przód-tył jest to dobra metoda na obliczenie wygładzonej wartości dla wszystkich ukrytych zmiennych stanu.

Najbardziej prawdopodobne wyjaśnienie

Zadaniem, w przeciwieństwie do dwóch poprzednich, prosi o wspólnym prawdopodobieństwem w całej sekwencji ukrytych stanów, które wygenerowało konkretny ciąg obserwacji (patrz rysunek po prawej). To zadanie ma ogólne zastosowanie, gdy HMM są stosowane do różnego rodzaju problemów niż te, do których mają zastosowanie zadania filtrowania i wygładzania. Przykładem jest tagowanie części mowy , w którym stany ukryte reprezentują podstawowe części mowy odpowiadające zaobserwowanej sekwencji słów. W tym przypadku interesująca jest cała sekwencja części mowy, a nie tylko część mowy dla pojedynczego słowa, jak oblicza się przy filtrowaniu lub wygładzaniu.

Zadanie to wymaga znalezienia maksimum we wszystkich możliwych sekwencjach stanów i może być skutecznie rozwiązane przez algorytm Viterbiego .

Znaczenie statystyczne

W przypadku niektórych z powyższych problemów interesujące może być również pytanie o istotność statystyczną . Jakie jest prawdopodobieństwo, że ciąg wylosowany z jakiegoś rozkładu zerowego będzie miał prawdopodobieństwo HMM (w przypadku algorytmu forward) lub maksymalne prawdopodobieństwo sekwencji stanów (w przypadku algorytmu Viterbiego) co najmniej tak duże jak dla konkretnego sekwencja wyjściowa? Gdy HMM jest używany do oceny istotności hipotezy dla określonej sekwencji wyjściowej, istotność statystyczna wskazuje na odsetek wyników fałszywie dodatnich związanych z odrzuceniem hipotezy dla sekwencji wyjściowej.

Uczenie się

Zadanie uczenia się parametrów w HMM polega na znalezieniu, przy danej sekwencji wyjściowej lub zbiorze takich sekwencji, najlepszego zestawu prawdopodobieństw przejścia stanu i emisji. Zadanie polega zwykle na wyprowadzeniu oszacowania maksymalnego prawdopodobieństwa parametrów HMM przy danym zestawie sekwencji wyjściowych. Nie jest znany żaden wykonalny algorytm do dokładnego rozwiązania tego problemu, ale lokalne maksymalne prawdopodobieństwo można wydajnie wyprowadzić za pomocą algorytmu Bauma-Welcha lub algorytmu Baldi-Chauvina. Algorytm Baum-Welch jest szczególnym przypadkiem algorytmu oczekiwanie maksymalizacji .

Jeśli HMM są używane do przewidywania szeregów czasowych, bardziej wyrafinowane metody wnioskowania bayesowskiego, takie jak próbkowanie metodą Monte Carlo (MCMC) z łańcuchem Markowa, okazują się bardziej korzystne niż znalezienie pojedynczego modelu największej wiarygodności, zarówno pod względem dokładności, jak i stabilności. Ponieważ MCMC nakłada znaczne obciążenie obliczeniowe, w przypadkach, w których skalowalność obliczeniowa jest również interesująca, można alternatywnie uciec się do przybliżeń wariacyjnych do wnioskowania bayesowskiego, np. przybliżone wnioskowanie wariacyjne zapewnia wydajność obliczeniową porównywalną z maksymalizacją oczekiwań, dając jednocześnie tylko nieznacznie profil dokładności gorsze od dokładnego wnioskowania bayesowskiego typu MCMC.

Aplikacje

Profil HMM modelujący dopasowanie wielu sekwencji

HMM mogą być stosowane w wielu dziedzinach, w których celem jest odzyskanie sekwencji danych, której nie można natychmiast zaobserwować (ale inne dane zależne od sekwencji są). Zastosowania obejmują:

• Finanse obliczeniowe
• Analiza kinetyczna pojedynczych cząsteczek
• Kryptoanaliza
• Rozpoznawanie mowy , w tym Siri
• Synteza mowy
• Oznaczanie części mowy
• Separacja dokumentów w rozwiązaniach do skanowania
• Tłumaczenie maszynowe
• Wyładowanie częściowe
• Przewidywanie genów
• Rozpoznawanie pisma odręcznego
• Dopasowanie biosekwencji
• Analiza szeregów czasowych
• Rozpoznawanie aktywności
• Fałdowanie białek
• Klasyfikacja sekwencji
• Wykrywanie wirusów metamorficznych
• Odkrycie motywu DNA
• Kinetyka hybrydyzacji DNA
• Odkrywanie stanu chromatyny
• Prognozowanie transportu
• Zmienność promieniowania słonecznego

Historia

Ukryte modele Markowa zostały opisane w serii artykułów statystycznych Leonarda E. Bauma i innych autorów w drugiej połowie lat sześćdziesiątych. Jednym z pierwszych zastosowań HMM było rozpoznawanie mowy , które rozpoczęło się w połowie lat 70. XX wieku.

W drugiej połowie lat 80. HMM zaczęto stosować do analizy sekwencji biologicznych, w szczególności DNA . Od tego czasu stały się wszechobecne w dziedzinie bioinformatyki .

Rozszerzenia

W rozważanych powyżej ukrytych modelach Markowa przestrzeń stanów ukrytych zmiennych jest dyskretna, podczas gdy same obserwacje mogą być dyskretne (zazwyczaj generowane z rozkładu kategorycznego ) lub ciągłe (zazwyczaj z rozkładu Gaussa ). Ukryte modele Markowa można również uogólnić, aby umożliwić ciągłe przestrzenie stanów. Przykładami takich modeli są te, w których proces Markowa nad zmiennymi ukrytymi jest liniowym systemem dynamicznym , z liniową relacją między powiązanymi zmiennymi i gdzie wszystkie ukryte i obserwowane zmienne mają rozkład Gaussa . W prostych przypadkach, takich jak wspomniany właśnie liniowy system dynamiczny, dokładne wnioskowanie jest wykonalne (w tym przypadku przy użyciu filtru Kalmana ); jednak na ogół dokładne wnioskowanie w HMM z ciągłymi zmiennymi latentnymi jest niewykonalne i należy zastosować metody przybliżone, takie jak rozszerzony filtr Kalmana lub filtr cząstek .

Ukryte modele Markowa to modele generatywne , w których modelowany jest łączny rozkład obserwacji i stanów ukrytych lub równoważnie zarówno uprzedni rozkład stanów ukrytych ( prawdopodobieństwa przejścia ) jak i warunkowy rozkład obserwacji danych stanów ( prawdopodobieństwo emisji ). Powyższe algorytmy domyślnie zakładają jednorodny rozkład a priori na prawdopodobieństwach przejścia. Jednak możliwe jest również tworzenie ukrytych modeli Markowa z innymi typami wcześniejszych dystrybucji. Oczywistym kandydatem, biorąc pod uwagę rozkład jakościowy prawdopodobieństw przejścia, jest rozkład Dirichleta , który jest sprzężonym rozkładem uprzednim rozkładu jakościowego. Zazwyczaj wybierany jest symetryczny rozkład Dirichleta, odzwierciedlający ignorancję na temat tego, które stany są z natury bardziej prawdopodobne niż inne. Pojedynczy parametr tego rozkładu (nazywany parametrem stężenia ) kontroluje względną gęstość lub rzadkość powstałej macierzy przejścia. Wybór 1 daje równomierny rozkład. Wartości większe niż 1 tworzą gęstą macierz, w której prawdopodobieństwa przejścia między parami stanów są prawdopodobnie prawie równe. Wartości mniejsze niż 1 dają macierz rzadką, w której dla każdego danego stanu źródłowego tylko niewielka liczba stanów docelowych ma niepomijalne prawdopodobieństwa przejścia. Możliwe jest również użycie dwupoziomowego wcześniejszego rozkładu Dirichleta, w którym jeden rozkład Dirichleta (górny rozkład) rządzi parametrami innego rozkładu Dirichleta (dolny rozkład), który z kolei rządzi prawdopodobieństwami przejścia. Górny rozkład reguluje ogólny rozkład stanów, określając prawdopodobieństwo wystąpienia każdego stanu; jego parametr stężenia określa gęstość lub rzadkość stanów. Taki dwupoziomowy rozkład a priori, w którym oba parametry koncentracji są ustawione tak, aby tworzyć rozkłady rzadkie, może być przydatny na przykład w nienadzorowanym znakowaniu części mowy, gdzie niektóre części mowy występują znacznie częściej niż inne; algorytmy uczenia się, które zakładają jednorodną dystrybucję uprzednią, generalnie słabo radzą sobie z tym zadaniem. Parametrów tego typu modeli o niejednorodnych rozkładach a priori można poznać za pomocą próbkowania Gibbsa lub rozszerzonych wersji algorytmu maksymalizacji oczekiwań .

Rozszerzenie wcześniej opisanych ukrytych modeli Markowa z a priori Dirichleta wykorzystuje proces Dirichleta zamiast rozkładu Dirichleta. Ten typ modelu pozwala na nieznaną i potencjalnie nieskończoną liczbę stanów. Powszechnie stosuje się dwupoziomowy proces Dirichleta, podobny do opisanego wcześniej modelu z dwoma poziomami rozkładów Dirichleta. Taki model nazywany jest hierarchicznym procesem Dirichleta ukrytym modelem Markowa lub w skrócie HDP-HMM . Został pierwotnie opisany pod nazwą „Nieskończony ukryty model Markowa” i został dalej sformalizowany.

Inny rodzaj rozszerzenia wykorzystuje model dyskryminacyjny zamiast modelu generatywnego standardowych HMM. Ten typ modelu bezpośrednio modeluje warunkowy rozkład stanów ukrytych na podstawie obserwacji, a nie modeluje rozkład łączny. Przykładem tego modelu jest tzw. model maksymalnej entropii Markowa (MEMM), który modeluje warunkowy rozkład stanów za pomocą regresji logistycznej (znany również jako „ model maksymalnej entropii ”). Zaletą tego typu modelu jest to, że można modelować dowolne cechy (tj. funkcje) obserwacji, co pozwala na wstrzyknięcie do modelu specyficznej dla danej dziedziny wiedzy o danym problemie. Modele tego rodzaju nie ograniczają się do modelowania bezpośrednich zależności między stanem ukrytym a związaną z nim obserwacją; raczej cechy obserwacji pobliskich, kombinacji obserwacji skojarzonych i obserwacji pobliskich, a właściwie dowolnych obserwacji w dowolnej odległości od danego stanu ukrytego mogą być włączone do procesu stosowanego do określenia wartości stanu ukrytego. Ponadto nie ma potrzeby, aby te cechy były statystycznie niezależne od siebie, jak miałoby to miejsce w przypadku wykorzystania takich cech w modelu generatywnym. Wreszcie, zamiast prostych prawdopodobieństw przejścia, można użyć arbitralnych cech w parach sąsiednich stanów ukrytych. Wadami takich modeli są: (1) Typy wcześniejszych dystrybucji, które można umieścić w stanach ukrytych, są poważnie ograniczone; (2) Nie jest możliwe przewidzenie prawdopodobieństwa zobaczenia arbitralnej obserwacji. To drugie ograniczenie często nie stanowi problemu w praktyce, ponieważ wiele powszechnych zastosowań HMM nie wymaga takich prawdopodobieństw predykcyjnych.

Wariantem opisanego wcześniej modelu dyskryminacyjnego jest warunkowe pole losowe o łańcuchu liniowym . Wykorzystuje to nieskierowany model graficzny (znany również jako pole losowe Markowa ) zamiast skierowanych modeli graficznych MEMM i podobnych modeli. Zaletą tego typu modelu jest to, że nie występuje w nim tak zwany problem błędu etykiety MEMM, a zatem może dokonywać dokładniejszych prognoz. Wadą jest to, że trening może być wolniejszy niż w przypadku MEMM.

Jeszcze innym wariantem jest czynnikowy ukryty model Markowa , który pozwala na warunkowanie pojedynczej obserwacji na podstawie odpowiadających jej zmiennych ukrytych zbioru niezależnych łańcuchów Markowa, a nie pojedynczego łańcucha Markowa. Jest to odpowiednik pojedynczego HMM ze stanami (zakładając, że istnieją stany dla każdego łańcucha), dlatego uczenie się w takim modelu jest trudne: dla ciągu długości prosty algorytm Viterbiego ma złożoność . Aby znaleźć dokładne rozwiązanie, można użyć algorytmu drzewa połączeń, ale powoduje to złożoność. W praktyce można zastosować techniki przybliżone, takie jak podejścia wariacyjne. ${\ Displaystyle K}$${\ Displaystyle N ^ {K}}$${\ Displaystyle N}$${\ Displaystyle T}$${\ Displaystyle O (N ^ {2 K} \ T)}$${\ Displaystyle O (N ^ {K + 1} \ K \ T)}$

Wszystkie powyższe modele można rozszerzyć, aby uwzględnić bardziej odległe zależności między stanami ukrytymi, np. pozwalając, aby dany stan był zależny od dwóch lub trzech poprzednich stanów, a nie od jednego poprzedniego stanu; tj. prawdopodobieństwa przejścia są rozszerzone tak, aby obejmowały zbiory trzech lub czterech sąsiednich stanów (lub ogólnie sąsiednich stanów). Wadą takich modeli jest to, że algorytmy programowania dynamicznego do ich uczenia mają czas działania dla sąsiednich stanów i obserwacji całkowitych (tj. łańcuch Markowa o długości). ${\ Displaystyle K}$${\ Displaystyle O (N ^ {K} \ T)}$${\ Displaystyle K}$${\ Displaystyle T}$${\ Displaystyle T}$

Innym niedawnym rozszerzeniem jest model trypletowy Markowa , w którym dodatkowy proces bazowy został dodany w celu modelowania pewnych specyfiki danych. Zaproponowano wiele wariantów tego modelu. Należy również wspomnieć o interesującym powiązaniu, jakie powstało między teorią dowodów a trypletowymi modelami Markowa i które pozwala na fuzję danych w kontekście Markowa i modelowanie danych niestacjonarnych. Należy zauważyć, że w najnowszej literaturze zaproponowano również alternatywne strategie wielostrumieniowej fuzji danych, np

Wreszcie w 2012 r. zaproponowano inne uzasadnienie rozwiązania problemu modelowania danych niestacjonarnych za pomocą ukrytych modeli Markowa. Polega ono na wykorzystaniu małej rekurencyjnej sieci neuronowej (RNN), a konkretnie sieci zbiornikowej, do uchwycenia ewolucji dynamiki czasowej w obserwowanych danych. Ta informacja, zakodowana w postaci wysokowymiarowego wektora, jest wykorzystywana jako zmienna warunkująca prawdopodobieństwa przejścia stanów HMM. W takiej konfiguracji ostatecznie otrzymujemy niestacjonarny HMM, którego prawdopodobieństwo przejścia ewoluuje w czasie w sposób, który można wywnioskować z samych danych, w przeciwieństwie do jakiegoś nierealistycznego modelu ewolucji czasowej ad hoc.

Model odpowiedni w kontekście danych podłużnych nazwano utajonym modelem Markowa. Podstawowa wersja tego modelu została rozszerzona o indywidualne współzmienne, efekty losowe oraz modelowanie bardziej złożonych struktur danych, takich jak dane wielopoziomowe. Pełny przegląd ukrytych modeli Markowa, ze szczególnym uwzględnieniem założeń modelu i ich praktycznego wykorzystania, znajduje się w:

Zobacz też

Bibliografia

Zewnętrzne linki

Koncepcje

• Teif, VB; Rippe, K. (2010). „Statystyczno-mechaniczne modele sieci wiązania białka-DNA w chromatynie”. J. Phys.: Kondens. Sprawa . 22 (41): 414105. arXiv : 1004.5514 . Kod bib : 2010JPCM...22O4105T . doi : 10.1088/0953-8984/22/41/414105 . PMID  21386588 . S2CID  103345 .
• Ujawniające wprowadzenie do ukrytych modeli Markowa autorstwa Marka Stampa z Uniwersytetu Stanowego w San Jose.
• Dopasowanie HMM do maksymalizacji oczekiwań – pełne wyprowadzenie
• Samouczek krok po kroku dotyczący HMM (Uniwersytet w Leeds)
• Ukryte modele Markowa (wystawa z wykorzystaniem podstaw matematyki)
• Ukryte modele Markowa (autorstwa Narady Warakagody)
• Ukryte modele Markowa: podstawy i zastosowania część 1 , część 2 (autor: V. Petrushin)
• Wykład Jasona Eisnera na arkuszu kalkulacyjnym , wideo i interaktywny arkusz kalkulacyjny