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.
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.
Intuicja 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. 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ą.
Definicja W najczęściej spotykanej dyskretnej wersji ukryty model Markowa jest zadany przez: skończony zbiór stanów ukrytych alfabet lub przestrzeń obserwacji rozkład początkowy macierz przejścia gdzie
rozkłady emisji w przypadku obserwacji dyskretnych albo gęstości emisji w przypadku obserwacji ciągłych.
Zmienna oznacza ukryty stan w chwili natomiast oznacza obserwację w tej chwili. Parametry modelu zapisuje się często jako
gdzie oznacza rodzinę rozkładów emisji.
Model opiera się na dwóch podstawowych założeniach. Pierwszym jest własność Markowa dla stanów ukrytych:
Drugim jest warunkowa niezależność obserwacji od przeszłości i przyszłości przy znanym stanie bieżącym:
Prawdopodobieństwo sekwencji Dla sekwencji ukrytych stanów
oraz obserwacji
prawdopodobieństwo łączne ma postać
Prawdopodobieństwo samej obserwowanej sekwencji otrzymuje się przez zsumowanie po wszystkich możliwych sekwencjach stanów:
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.
Trzy podstawowe problemy W klasycznym ujęciu ukrytych modeli Markowa wyróżnia się trzy podstawowe problemy obliczeniowe: 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.
Algorytm w przód Algorytm w przód służy do obliczania prawdopodobieństwa obserwowanej sekwencji Definiuje się zmienne
czyli prawdopodobieństwo wygenerowania prefiksu obserwacji i zakończenia w stanie w chwili
Inicjalizacja ma postać
Rekurencja:
Na końcu
Algorytm działa w czasie gdzie jest długością sekwencji, a liczbą stanów.
Algorytm wstecz Algorytm wstecz jest komplementarny do algorytmu w przód. Definiuje się zmienne
czyli prawdopodobieństwo wygenerowania sufiksu obserwacji przy założeniu, że w chwili model znajduje się w stanie
Inicjalizacja:
Rekurencja:
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 Algorytm Viterbiego służy do znalezienia najbardziej prawdopodobnej ścieżki stanów ukrytych dla danej sekwencji obserwacji. Szuka się więc
Definiuje się
Rekurencja ma postać
Aby odtworzyć całą ścieżkę, przechowuje się także wskaźniki stanów, dla których maksimum zostało osiągnięte.
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.
Algorytm Bauma-Welcha 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.
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ść.
Typowe wielkości pomocnicze to
oraz
Następnie parametry przejść aktualizuje się w przybliżeniu jako oczekiwany udział przejść wśród wszystkich przejść wychodzących ze stanu
Dla emisji dyskretnych analogicznie zlicza się oczekiwaną liczbę emisji danego symbolu w danym stanie.
Algorytm Bauma-Welcha zwiększa wiarygodność w kolejnych iteracjach, ale nie gwarantuje znalezienia globalnego maksimum. Wynik zależy od inicjalizacji parametrów.
Historia 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. 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.
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.
Rodzaje emisji 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.
Wybór liczby stanów 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.
Zastosowania Rozpoznawanie mowy 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.
Przetwarzanie języka naturalnego 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.
Bioinformatyka 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.
Szeregi czasowe i reżimy ukryte 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.
Uogólnienia i modele pokrewne 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.
Ograniczenia 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.
Pakiety i oprogramowanie R 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. 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.
Python 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. Inną biblioteką probabilistyczną jest pomegranate, która zawiera implementację HMM-ów jako modeli sekwencyjnych z rozkładami emisji i macierzą przejść.
Przykład: nieuczciwe kasyno Rozważmy model z dwoma ukrytymi stanami: – używana jest uczciwa kostka; – używana jest kostka obciążona.
Obserwacjami są wyniki rzutów W stanie każdy wynik ma prawdopodobieństwo W stanie wynik 6 może mieć prawdopodobieństwo a pozostałe wyniki po 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.
Literatura 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.