Znalezienie top - k Viterbi'ego ścieżki w HMM

Question

Muszę napisać algorytm, który wyszukuje ścieżki Viterbi'ego top-K w HMM (za pomocą zwykłego algorytmu Viterbiego, aby znaleźć najlepszą drogę).

Myślę, że prawdopodobnie muszę zapisać listę V_t, N rozmiaru k dla każdego stanu N zawierającego najwyższe ścieżki K, które kończą się stanem N, ale nie jestem pewien, jak śledzić tę listę. . jakieś pomysły? Dzięki

Answer 1

Możemy rozwiązać ten problem z jakąś opieką. Najłatwiej jest zobaczyć patrząc na strukturę krata z hmm:

W tym przykładzie ukryte stany są 00, 01, 10, 11, oznacza zbiór tych czterech jak S. obserwacje nie pokazano, ale przyjmijmy, że są 0,1.

Załóżmy, że mamy prawidłowe przejście matrix:

transition[4][4] 

prawdopodobieństw emisji:

emissions[4][2] 

i wstępne prawdopodobieństw:

p[2] 

Więc każda kolumna reprezentuje ukryte stany, i celem Viterbi jest obliczyć najbardziej prawdopodobną sekwencję stanów ukrytych podaną t obserwacje. Teraz alfa (i, t) = największe prawdopodobieństwo, że ukryta sekwencja stanu jest w stanie l (i jest jednym z 00, 01, 10, 11), w chwili t, gdzie obserwacji w czasie t jest o_t (o_t jest jedna 0, 1). Niech pierwsza obserwacja będzie oznaczona jako o_1. To może być skutecznie obliczane jako:

alpha(i, 1) = p[i] * emissions[i][o_1] 
alpha(i, t) = emissions[i][o_t] * max_{k in states} (alpha(k, t-1) * transition[k][i]) 

W celu znalezienia najlepszej ścieżki, trzymamy wskazówek do tyłu w alfa (i, t) etapie, do stanu, który zmaksymalizowane funkcję Max powyżej. W końcu sprawdzamy wszystkie stany alfa (i, T) i i w stanach i ustalamy, który z nich jest największy, a następnie śledzimy go, aby uzyskać najbardziej prawdopodobną sekwencję stanów.

Teraz musimy rozszerzyć ten przechowywać najlepszymi k-ścieżek. Obecnie na każdej alfa (i, t) przechowujemy tylko jednego rodzica. Załóżmy jednak, że przechowujemy najlepsze poprzedniki k. Zatem każda alfa (i, t) odpowiada nie tylko najbardziej prawdopodobnej wartości i węzłowi, z którego się przerzuciła, ale także liście najwyższych k węzłów, z których mogła przejść, oraz ich wartości w posortowanej kolejności.

To jest łatwe do zrobienia, że ​​zamiast robić max i wziąć tylko jeden poprzedni węzeł bierzemy górną k poprzedzających węzłów i przechowywać je. Teraz w przypadku podstawowym nie ma poprzedzającego węzła, więc alfa (i, 1) nadal jest tylko pojedynczą wartością. Kiedy docieramy do dowolnej kolumny (słownie t) i chcą znaleźć ścieżki top-K kończąc na węźle (I), w tej kolumnie, musimy znaleźć najlepsze k poprzedników pochodzić z a górna ścieżki do podjęcia z nimi.

to jest tak, że ma następujący problem, matrycę, m, o wymiarach 4 przez K, przy czym rząd reprezentuje poprzedniego stanu i M [stanu] reprezentuje górną prawdopodobieństwa K dla torów kończących się tam. Zatem każdy rząd m jest posortowana według największego do najmniejszego, problem staje się teraz znaleźć:

Best_K_Values(t, i) = Top K over all i,preceding_state,k (emissions[i][o_t] * m[preceding_state][k] * transition[preceding_state][i]) 

Teraz wygląda to trudne, ale trochę czasu, aby to zrozumieć, możemy rozwiązać górną k od posortowanej problemu macierzy za pomocą sterty w O (4 log k) lub O (numStates log k) w ogóle.

Zobacz tę niewielką odmianę Kth smallest element in sorted matrix, zauważmy, że w naszym przypadku kolumny nie są posortowane, ale idea nadal obowiązuje.

Jeśli nadal czytasz, zwróć uwagę, że ogólna złożoność tej metody to O ((numer dziennika) * numStates * t) = O (numStates^2 * t * log k) (Uważam, że jest to poprawna złożoność).

To może być trudne do naśladowania, ale proszę dać mi znać, jeśli masz jakiekolwiek pytania, czy mam coś zrobić niepoprawnie.

Answer 2

Istnieje obszerna literatura na ten temat. Minęło trochę kopania, ale znalazłem to.

listy dekoderze Viterbi'ego Algorytmy z aplikacjami

http://www.ensc.sfu.ca/people/faculty/cavers/ENSC805/readings/42comm02-seshadri.pdf