Modely Markowa ukryte: stany, obserwacje i Viterbi

Nakładka stanów, których nie możesz zobaczyć

Klasyczna łańcuch Markova przechodzi między stanami, które można obserwować bezpośrednio, a prawdopodobieństwa przejść opisują całą historię. Model ukryty Markova dodaje warstwę odrobinę indirekcyjności: stany nadal istnieją i nadal przechodzą zgodnie z macierzą prawdopodobieństw, ale nigdy ich nie obserwujesz. W każdym kroku czasowym bieżący ukryty stan emituje obserwację widzialną, wybraną ze wstępnej rozkładu emisji dla danego stanu, a ta obserwacja jest jedynym, czym dysponujesz. Pogoda jest klasycznym przykładem - nie możesz bezpośrednio zobaczyć, czy podstawowy rząd jest słoneczny lub deszczowy, tylko czy ktoś nosił parasol tamtej dnia, a parasole są tylko zniekształconym wsparciem.

Trzy pytania, trzy algorytmy

Model jest pełnookreślony trzema elementami: macierzą przejść między ukrytymi stanami, rozkładem emisji dla każdego stanu oraz rozkładem początkowego dystrybucji stanów. Dany model pozwala na odpowiedzię trzy klasyczne pytania, każde z nich ma dedykowany algorytm dynamicznego programowania. Ocena - jak prawdopodobne jest ta sekwencja obserwacji pod względem modelu? - jest odpowiadana przez algorytm przód. Odszyfrowywanie - jaki jest najbardziej prawdopodobny ciąg ukrytych stanów, który wygenerował te obserwacje? - jest odpowiadane przez algorytm Viterbi. Nauczanie - dając tylko obserwacje, jakie są parametry modelu? - jest odpowiadane przez procedurę Baum-Welch, która jest formą maksymalizacji oczekiwania.

Algorytm przódowy

Obliczanie całkowitej prawdopodobieństwa szeregu obserwacji metodą siłą zmuszaną polega na sumowaniu nad każdym możliwym szeregiem stanów ukrytych, co powoduje eksponencjalny wzrost z czasem. Algorytm przódowy uniknie tego poprzez budowanie tabeli alpha, gdzie alpha w chwili t i stanie i to prawdopodobieństwo, że znajdujemy się w stanie i na chwili t, mając do dyspozycji wszystkie obserwacje do chwili t. Każdy kolumna zależy tylko od poprzedniej kolumny, więc cała tabela wypełnia się w czasie O(kwadratu stanów razy etapów czasowych) zamiast eksponencjalnego czasu - to samo struktura drzewa, która sprawia, że algorytm Viterbi poniżej jest przyswojemy.

Viterbi: suma staje się maksimum

Viterbi rozwiązuje inny problem na tym samym diagramie zwiastunkowym: zamiast całkowitej prawdopodobieństwa, chce najbardziej prawdopodobnej ścieżki. Każdy sumator w rekurencji w przód jest zastąpiony maksimum, a przy każdym komórce algorytm dodatkowo rejestruje wskaźnik do poprzedniego stanu, który wygenerował to maksimum. Gdy tabela zostanie wypełniona, śledzenie wskaźników od najbardziej prawdopodobnego końcowego stanu z powrotem do chwili zerowej odtwarza najprawdopodobniejszą sekwencję ukrytych stanów w jednym przebiegu.

delta[0][i] = initial[i] * emit[i][obs[0]];
for (let t = 1; t < T; t++)
  for (let i = 0; i < N; i++) {
    let best = -Infinity, arg = -1;
    for (let j = 0; j < N; j++) {
      const score = delta[t-1][j] * trans[j][i];
      if (score > best) { best = score; arg = j; }   // max, not sum
    }
    delta[t][i] = best * emit[i][obs[t]];
    backptr[t][i] = arg;
  }
// trace backptr from argmax(delta[T-1]) back to t=0 for the best state path

Gdzie ukryte modele Markowa wykorzystywane są

Systemy rozpoznawania mowy dawno używaly UKM z fonemami jako ukrytymi stanami i cechach akustycznymi jako obserwacjami. Bioinformatyka wykorzystuje je do znalezienia genów, porównując ciąg base’ów DNA z ukrytymi stanami takimi jak ekon i intron. Tagowanie części mowy traktuje kategorie gramatyczne jako ukryte stany emiting słowa w zdaniu. W każdym przypadku wspólna struktura pozostaje taka sama: łańcuch niezobserwowanych stanów generujący łańcuch zjawisk, które można obserwować, a dekodowanie Viterbi jest tym, co przekształca łańcuch zjawisk znowu w najlepsze odgadywanie ukrytych stanów.

Często zadawane pytania