Ukryte modele Markowa 📖 Wikipedia

Ukryte modele Markowa (ang. hidden Markov models, HMM) – klasa modeli probabilistycznych służących do opisu danych sekwencyjnych, w których obserwowana sekwencja powstaje pod wpływem nieobserwowanego procesu Markowa. Model zakłada, że układ przechodzi między ukrytymi stanami zgodnie z łańcuchem Markowa, a w każdym stanie generuje obserwację według rozkładu emisji zależnego od tego stanu^[1][2].

Ukryte modele Markowa są stosowane między innymi w rozpoznawaniu mowy, przetwarzaniu języka naturalnego, bioinformatyce, analizie sygnałów, segmentacji szeregów czasowych, rozpoznawaniu gestów, ekonomii i finansach oraz modelowaniu reżimów ukrytych^[1][3][4].

W zwykłym łańcuchu Markowa obserwuje się stan układu. W ukrytym modelu Markowa stan nie jest obserwowany bezpośrednio; widoczna jest tylko sekwencja symboli, pomiarów albo wektorów cech emitowanych przez układ. Dlatego model rozdziela dwie warstwy:

• warstwę ukrytą, czyli sekwencję stanów;
• warstwę obserwowaną, czyli sekwencję emisji.

Typowym przykładem jest nieuczciwe kasyno. Kasyno używa raz uczciwej, a raz obciążonej kostki, ale obserwator widzi jedynie kolejne wyniki rzutów, nie zaś to, której kostki użyto. Ukrytymi stanami są więc rodzaje kostki, a obserwacjami – wyniki rzutów^[2]. Podobna idea występuje w bioinformatyce przy rozpoznawaniu wysp CpG: obserwuje się sekwencję nukleotydów, natomiast ukrytym stanem może być informacja, czy aktualna pozycja należy do wyspy CpG, czy do regionu poza nią^[2][3].

W najczęściej spotykanej dyskretnej wersji ukryty model Markowa jest zadany przez:

• skończony zbiór stanów ukrytych ${\displaystyle Q=\{1,\dots ,N\};}$
• alfabet lub przestrzeń obserwacji ${\displaystyle \Sigma ;}$
• rozkład początkowy ${\displaystyle \pi _{i}=P(X_{1}=i);}$
• macierz przejścia ${\displaystyle A=(a_{ij}),}$ gdzie

${\displaystyle a_{ij}=P(X_{t+1}=j\mid X_{t}=i);}$

• rozkłady emisji ${\displaystyle b_{i}(y)=P(Y_{t}=y\mid X_{t}=i)}$ w przypadku obserwacji dyskretnych albo gęstości emisji w przypadku obserwacji ciągłych.

Zmienna ${\displaystyle X_{t}}$ oznacza ukryty stan w chwili ${\displaystyle t,}$ natomiast ${\displaystyle Y_{t}}$ oznacza obserwację w tej chwili. Parametry modelu zapisuje się często jako

${\displaystyle \lambda =(A,B,\pi ),}$

gdzie ${\displaystyle B}$ oznacza rodzinę rozkładów emisji^[1][2].

Model opiera się na dwóch podstawowych założeniach. Pierwszym jest własność Markowa dla stanów ukrytych:

${\displaystyle P(X_{t+1}\mid X_{1},\dots ,X_{t})=P(X_{t+1}\mid X_{t}).}$

Drugim jest warunkowa niezależność obserwacji od przeszłości i przyszłości przy znanym stanie bieżącym:

${\displaystyle P(Y_{t}\mid X_{1},\dots ,X_{t},Y_{1},\dots ,Y_{t-1})=P(Y_{t}\mid X_{t}).}$^[1]

Dla sekwencji ukrytych stanów

${\displaystyle x_{1:T}=(x_{1},\dots ,x_{T})}$

oraz obserwacji

${\displaystyle y_{1:T}=(y_{1},\dots ,y_{T})}$

prawdopodobieństwo łączne ma postać

${\displaystyle P(x_{1:T},y_{1:T})=\pi _{x_{1}}b_{x_{1}}(y_{1})\prod _{t=2}^{T}a_{x_{t-1}x_{t}}b_{x_{t}}(y_{t}).}$

Prawdopodobieństwo samej obserwowanej sekwencji otrzymuje się przez zsumowanie po wszystkich możliwych sekwencjach stanów:

${\displaystyle P(y_{1:T})=\sum _{x_{1:T}}\pi _{x_{1}}b_{x_{1}}(y_{1})\prod _{t=2}^{T}a_{x_{t-1}x_{t}}b_{x_{t}}(y_{t}).}$

Bezpośrednie sumowanie jest zwykle obliczeniowo niepraktyczne, ponieważ liczba ścieżek stanów rośnie wykładniczo z długością sekwencji. Dlatego używa się algorytmów programowania dynamicznego^[1][2].

W klasycznym ujęciu ukrytych modeli Markowa wyróżnia się trzy podstawowe problemy obliczeniowe^[1]:

• ocena – obliczenie prawdopodobieństwa obserwowanej sekwencji przy znanych parametrach modelu;
• dekodowanie – znalezienie najbardziej prawdopodobnej sekwencji stanów ukrytych, która mogła wygenerować obserwacje;
• uczenie – estymacja parametrów modelu na podstawie obserwowanych sekwencji.

Odpowiadają im odpowiednio algorytm w przód, algorytm Viterbiego oraz algorytm Bauma-Welcha, będący szczególnym przypadkiem algorytmu EM^[1][2].

Algorytm w przód służy do obliczania prawdopodobieństwa obserwowanej sekwencji ${\displaystyle y_{1:T}.}$ Definiuje się zmienne

${\displaystyle \alpha _{t}(i)=P(y_{1},\dots ,y_{t},X_{t}=i\mid \lambda ),}$

czyli prawdopodobieństwo wygenerowania prefiksu obserwacji i zakończenia w stanie ${\displaystyle i}$ w chwili ${\displaystyle t.}$

Inicjalizacja ma postać

${\displaystyle \alpha _{1}(i)=\pi _{i}b_{i}(y_{1}).}$

Rekurencja:

${\displaystyle \alpha _{t+1}(j)=b_{j}(y_{t+1})\sum _{i=1}^{N}\alpha _{t}(i)a_{ij}.}$

Na końcu

${\displaystyle P(y_{1:T}\mid \lambda )=\sum _{i=1}^{N}\alpha _{T}(i).}$^[1][2]

Algorytm działa w czasie ${\displaystyle O(TN^{2}),}$ gdzie ${\displaystyle T}$ jest długością sekwencji, a ${\displaystyle N}$ liczbą stanów^[1].

Algorytm wstecz jest komplementarny do algorytmu w przód. Definiuje się zmienne

${\displaystyle \beta _{t}(i)=P(y_{t+1},\dots ,y_{T}\mid X_{t}=i,\lambda ),}$

czyli prawdopodobieństwo wygenerowania sufiksu obserwacji przy założeniu, że w chwili ${\displaystyle t}$ model znajduje się w stanie ${\displaystyle i.}$

Inicjalizacja:

${\displaystyle \beta _{T}(i)=1.}$

Rekurencja:

${\displaystyle \beta _{t}(i)=\sum _{j=1}^{N}a_{ij}b_{j}(y_{t+1})\beta _{t+1}(j).}$^[1][2]

Algorytmy w przód i wstecz są używane wspólnie w procedurze Bauma-Welcha oraz do obliczania prawdopodobieństw posteriori stanów ukrytych.

Algorytm Viterbiego służy do znalezienia najbardziej prawdopodobnej ścieżki stanów ukrytych dla danej sekwencji obserwacji. Szuka się więc

${\displaystyle {\widehat {x}}_{1:T}=\operatorname {*} {arg\,max}_{x_{1:T}}P(x_{1:T}\mid y_{1:T},\lambda ).}$

Definiuje się

${\displaystyle \delta _{t}(j)=\max _{x_{1:t-1}}P(x_{1:t-1},X_{t}=j,y_{1:t}\mid \lambda ).}$

Rekurencja ma postać

${\displaystyle \delta _{t+1}(j)=b_{j}(y_{t+1})\max _{i}\delta _{t}(i)a_{ij}.}$

Aby odtworzyć całą ścieżkę, przechowuje się także wskaźniki stanów, dla których maksimum zostało osiągnięte^[1][2].

Algorytm Viterbiego został wprowadzony przez Andrew Viterbiego w kontekście dekodowania kodów splotowych, a następnie stał się podstawowym narzędziem dekodowania w ukrytych modelach Markowa^[5][1].

Algorytm Bauma-Welcha służy do estymacji parametrów ukrytego modelu Markowa, gdy znane są obserwacje, ale nieznane są odpowiadające im ścieżki stanów ukrytych. Jest szczególnym przypadkiem algorytmu EM.^[1][6]

W kroku E oblicza się wartości oczekiwane liczby przebywań w stanach oraz przejść między stanami, korzystając z algorytmów w przód i wstecz. W kroku M aktualizuje się prawdopodobieństwa przejść i emisji tak, aby zmaksymalizować oczekiwaną logarytmiczną wiarygodność^[1][2].

Typowe wielkości pomocnicze to

${\displaystyle \gamma _{t}(i)=P(X_{t}=i\mid y_{1:T},\lambda )}$

oraz

${\displaystyle \xi _{t}(i,j)=P(X_{t}=i,X_{t+1}=j\mid y_{1:T},\lambda ).}$

Następnie parametry przejść aktualizuje się w przybliżeniu jako oczekiwany udział przejść ${\displaystyle i\to j}$ wśród wszystkich przejść wychodzących ze stanu ${\displaystyle i{:}}$

${\displaystyle a_{ij}^{\mathrm {new} }={\frac {\sum _{t=1}^{T-1}\xi _{t}(i,j)}{\sum _{t=1}^{T-1}\gamma _{t}(i)}}.}$

Dla emisji dyskretnych analogicznie zlicza się oczekiwaną liczbę emisji danego symbolu w danym stanie^[1].

Algorytm Bauma-Welcha zwiększa wiarygodność w kolejnych iteracjach, ale nie gwarantuje znalezienia globalnego maksimum. Wynik zależy od inicjalizacji parametrów^[1].

Matematyczne podstawy ukrytych modeli Markowa zostały rozwinięte w latach 60. XX wieku w pracach Leonarda E. Bauma i współautorów dotyczących probabilistycznych funkcji skończonych łańcuchów Markowa^[7][8]. W latach 70. i 80. modele te stały się szczególnie ważne w rozpoznawaniu mowy, a klasyczny artykuł przeglądowy Lawrence’a Rabinera z 1989 roku ugruntował ich standardową prezentację przez trzy podstawowe problemy: ocenę, dekodowanie i uczenie^[1].

W bioinformatyce ukryte modele Markowa rozpowszechniły się jako narzędzie analizy sekwencji biologicznych, między innymi w rozpoznawaniu genów, modelowaniu rodzin białek i wykrywaniu motywów sekwencyjnych^[3][9].

W zależności od typu danych stosuje się różne rozkłady emisji:

• emisje dyskretne – obserwacje należą do skończonego alfabetu, np. litery, nukleotydy albo klasy symboli;
• emisje ciągłe – obserwacje są liczbami lub wektorami, a emisje modeluje się np. rozkładami normalnymi;
• emisje mieszane – obserwacje zawierają jednocześnie zmienne dyskretne i ciągłe;
• emisje regresyjne – rozkład obserwacji zależy od dodatkowych zmiennych objaśniających.

W rozpoznawaniu mowy często stosowano HMM-y z emisjami ciągłymi, w szczególności z mieszaninami Gaussowskimi. W bioinformatyce klasyczne modele sekwencyjne często używają emisji dyskretnych nad alfabetem nukleotydów lub aminokwasów^[1][3].

Liczba ukrytych stanów może wynikać z wiedzy dziedzinowej albo być dobierana empirycznie. W prostym przykładzie z nieuczciwym kasynem naturalne są dwa stany: uczciwa i nieuczciwa kostka. W innych zastosowaniach liczba stanów może odpowiadać liczbie reżimów, klas biologicznych, typów aktywności albo ukrytych faz procesu.

Do porównywania modeli o różnych liczbach stanów używa się między innymi walidacji krzyżowej, logarytmicznej wiarygodności na zbiorze testowym, AIC i BIC. Należy jednak uważać, ponieważ większa liczba stanów może poprawiać dopasowanie, ale jednocześnie utrudniać interpretację i zwiększać ryzyko przeuczenia^[10].

Jednym z klasycznych zastosowań HMM-ów jest rozpoznawanie mowy. Ukryte stany mogą odpowiadać fonemom, fragmentom fonemów lub innym jednostkom akustycznym, natomiast obserwacjami są wektory cech wyznaczone z sygnału mowy. Rabiner opisał HMM-y jako jedną z podstawowych metod statystycznego modelowania mowy^[1].

W przetwarzaniu języka naturalnego HMM-y stosowano między innymi do tagowania części mowy. Ukrytymi stanami są wtedy kategorie gramatyczne, a obserwacjami słowa. Model oblicza najbardziej prawdopodobną sekwencję tagów dla danego zdania^[11].

W bioinformatyce HMM-y służą do modelowania sekwencji DNA, RNA i białek. Używa się ich między innymi do wykrywania genów, rozpoznawania wysp CpG, dopasowywania sekwencji i budowy profilowych modeli HMM dla rodzin białek^[2][3][9].

HMM-y są używane do modelowania procesów, które przełączają się między nieobserwowanymi reżimami. Przykładem może być modelowanie okresów wysokiej i niskiej zmienności, stanów aktywności użytkownika, faz urządzenia technicznego albo trybów zachowania zwierzęcia^[10].

Do ważnych uogólnień ukrytych modeli Markowa należą:

• ukryte modele pół-Markowa – pozwalają modelować czas trwania w stanie przez rozkład inny niż geometryczny;
• profilowe HMM-y – używane w bioinformatyce do modelowania rodzin sekwencji biologicznych;
• faktorialne HMM-y – mają kilka równoległych łańcuchów stanów ukrytych;
• hierarchiczne HMM-y – dopuszczają wielopoziomową strukturę stanów;
• HMM-y z emisjami Gaussowskimi i HMM-y z mieszaninami Gaussowskimi – używane dla danych ciągłych;
• modele przełączające Markowa – stosowane w ekonometrii i analizie szeregów czasowych;
• ukryte modele Markowa z wejściem – w których przejścia lub emisje zależą od dodatkowych zmiennych.

Modele pokrewne obejmują dynamiczne sieci bayesowskie, filtr Kalmana, warunkowe pola losowe oraz modele przestrzeni stanów. HMM jest szczególnym przypadkiem modelu przestrzeni stanów, w którym stan ukryty jest dyskretny^[10][12].

Klasyczny HMM jest modelem stosunkowo prostym i opiera się na silnych założeniach. Najważniejsze ograniczenia to:

• założenie, że przyszły stan zależy tylko od obecnego stanu;
• założenie, że obserwacja zależy tylko od aktualnego stanu ukrytego;
• trudność w wyborze liczby stanów;
• zbieżność algorytmu Bauma-Welcha tylko do maksimum lokalnego;
• możliwa trudność interpretacji stanów ukrytych;
• problemy numeryczne wynikające z mnożenia wielu małych prawdopodobieństw.

W praktyce obliczenia prowadzi się często w skali logarytmicznej albo stosuje skalowanie zmiennych w algorytmach w przód i wstecz, aby uniknąć niedomiaru numerycznego^[1][10].

W języku R do ukrytych modeli Markowa używa się między innymi pakietów HiddenMarkov, HMM i depmixS4. Pakiet HiddenMarkov zawiera funkcje do analizy dyskretnych HMM-ów, modeli Markowa modulujących uogólnione modele liniowe oraz procesów Poissona modulowanych Markowowsko; obejmuje symulację, estymację parametrów i algorytm Viterbiego^[13]. Pakiet depmixS4 służy do dopasowywania ukrytych lub latentnych modeli Markowa dla mieszanych danych kategorycznych i ciągłych, w tym modeli z emisjami z rodzin GLM i rozkładów wielowymiarowych normalnych^[14][15].

W języku Python popularną biblioteką do klasycznych HMM-ów jest hmmlearn, która implementuje uczenie nienadzorowane i wnioskowanie w ukrytych modelach Markowa oraz stara się zachować interfejs zbliżony do scikit-learn.^[16] Inną biblioteką probabilistyczną jest pomegranate, która zawiera implementację HMM-ów jako modeli sekwencyjnych z rozkładami emisji i macierzą przejść^[17].

Rozważmy model z dwoma ukrytymi stanami:

• ${\displaystyle F}$ – używana jest uczciwa kostka;
• ${\displaystyle L}$ – używana jest kostka obciążona.

Obserwacjami są wyniki rzutów ${\displaystyle 1,\dots ,6.}$ W stanie ${\displaystyle F}$ każdy wynik ma prawdopodobieństwo ${\displaystyle 1/6.}$ W stanie ${\displaystyle L}$ wynik 6 może mieć prawdopodobieństwo ${\displaystyle 1/2,}$ a pozostałe wyniki po ${\displaystyle 1/10.}$ Macierz przejść określa, jak często kasyno zmienia kostkę. Na podstawie samej sekwencji wyników można próbować odtworzyć najbardziej prawdopodobną sekwencję używanych kostek za pomocą algorytmu Viterbiego albo oszacować parametry modelu algorytmem Bauma-Welcha^[2].

• Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, Proceedings of the IEEE, 1989.
• Lawrence R. Rabiner, Biing-Hwang Juang, Fundamentals of Speech Recognition, Prentice Hall, 1993.
• Richard Durbin, Sean R. Eddy, Anders Krogh, Graeme Mitchison, Biological Sequence Analysis. Probabilistic Models of Proteins and Nucleic Acids, Cambridge University Press, 1998.
• Christopher M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006.
• Walter Zucchini, Iain L. MacDonald, Roland Langrock, Hidden Markov Models for Time Series. An Introduction Using R, CRC Press, 2016.
• Olivier Cappé, Eric Moulines, Tobias Rydén, Inference in Hidden Markov Models, Springer, 2005.
• Jerzy Tiuryn, Ukryte modele Markowa, materiały do wykładu Wstęp do obliczeniowej biologii molekularnej, MIM UW, 2006.

• łańcuch Markowa
• algorytm Viterbiego
• algorytm EM
• model probabilistyczny
• model przestrzeni stanów
• filtr Kalmana
• bioinformatyka
• rozpoznawanie mowy

• Jerzy Tiuryn, Ukryte modele Markowa, MIM UW
• Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition
• Dokumentacja biblioteki hmmlearn
• Pakiet HiddenMarkov dla R