Jakie są różnice między algorytmem Baum-Welcha a treningiem Viterbi?

Obecnie używam szkolenia Viterbi do problemu segmentacji obrazu. Chciałem wiedzieć, jakie są zalety / wady korzystania z algorytmu Baum-Welch zamiast treningu Viterbi.

— Digital Gal
źródło

Co dokładnie rozumiesz przez „trening Viterbi”?

— bmargulies

W moim problemie mam szereg danych o wartościach rzeczywistych, które modeluję jako HMM (w szczególności mieszanina funkcji wielu gęstości o nieznanych parametrach). Na razie zakładam, że znam probability przejścia stanu. Przez Viterbi Trainig rozumiem następujący algorytm. 1) Arbitralnie przypisz stan do każdego punktu danych (inicjalizacja) 2) Wykonaj MLE parametrów funkcji gęstości. 3) Ponownie oszacuj stan dla każdego punktu (można to zrobić za pomocą Viterbi Alg). 4) Przejdź do kroku 2 i powtórz, chyba że zostaną spełnione kryteria zatrzymania.

— Cyfrowy Gal

To samo pytanie zostało zadane przy przepełnieniu stosu: trening viterbi vs algorytm baum-

— welch

Algorytm Bauma-Welcha i algorytm Viterbiego obliczają różne rzeczy.

Jeśli znasz prawdopodobieństwa przejścia dla ukrytej części modelu i prawdopodobieństwa emisji dla widocznych wyników twojego modelu, algorytm Viterbi daje najbardziej prawdopodobną kompletną sekwencję ukrytych stanów, zależną zarówno od twoich wyników, jak i specyfikacji modelu.

Algorytm Bauma-Welcha daje zarówno najbardziej prawdopodobne ukryte prawdopodobieństwa przejścia, jak i najbardziej prawdopodobny zbiór prawdopodobieństw emisji, biorąc pod uwagę tylko obserwowane stany modelu (i zwykle górną granicę liczby stanów ukrytych). Otrzymujesz również „punktowe” najwyższe prawdopodobieństwo w stanach ukrytych, które często nieznacznie różnią się od pojedynczej ukrytej sekwencji, która jest ogólnie najbardziej prawdopodobna.

Jeśli znasz swój model i chcesz po prostu ukrytych stanów, nie ma powodu, aby używać algorytmu Baum-Welch. Jeśli nie znasz swojego modelu, nie możesz używać algorytmu Viterbi.

Edytowano, aby dodać: Zobacz komentarz Petera Smita; w nomenklaturze występuje pewne nakładanie się / niejasności. Niektóre grzebanie wokół doprowadziło mnie do rozdziału Luisa Javiera Rodrıgueza i Ines Torres w „Rozpoznawaniu wzorów i analizie obrazu” (ISBN 978-3-540-40217-6, str. 845-857), w którym omawia się kompromisy między szybkością a dokładnością dwa algorytmy.

W skrócie, algorytm Baum-Welch jest zasadniczo algorytmem Expectation-Maximization (EM) stosowanym do HMM; jako ścisły algorytm typu EM masz gwarancję, że zbiegniesz się do co najmniej lokalnego maksimum, więc w przypadku nietypowych problemów znajdź MLE. Wymaga to jednak dwóch przejść dla danych dla każdego kroku, a złożoność staje się bardzo duża w zakresie długości danych i liczby próbek treningowych. Jednak otrzymujesz pełne prawdopodobieństwo warunkowe dla swoich ukrytych parametrów.

Algorytm treningowy Viterbi (w przeciwieństwie do „algorytmu Viterbi”) aproksymuje MLE, aby osiągnąć przyrost prędkości kosztem dokładności. Segmentuje dane, a następnie stosuje algorytm Viterbi (tak jak to rozumiem), aby uzyskać najbardziej prawdopodobną sekwencję stanów w segmencie, a następnie wykorzystuje tę najbardziej prawdopodobną sekwencję stanów do ponownego oszacowania ukrytych parametrów. W przeciwieństwie do algorytmu Baum-Welcha nie daje to pełnego warunkowego prawdopodobieństwa ukrytych parametrów, a zatem zmniejsza dokładność, oszczędzając przy tym znaczący (rozdział opisuje 1 do 2 rzędów wielkości) czas obliczeniowy.

— Bogaty
źródło

Jeśli mam rację, miksujesz trening Viterbi i dekodowanie Viterbi.

— Peter Smit

Masz rację. Nie wiedziałem, że istniała procedura wykorzystująca tylko algorytm Viterbiego do obliczenia prawdopodobieństw przejścia. Wygląda - przy dalszym czytaniu - jakby pewne nakładanie się nomenklatury między analizą HMM czasu dyskretnego / stanu dyskretnego, a analizą dyskretną czasu / stanu ciągłego z wykorzystaniem rozkładów mieszaniny Gaussa. Moja odpowiedź dotyczy konfiguracji DTDS HMM, a nie konfiguracji modelu mieszanki.

— Bogaty

@Rich: Czy możesz wskazać mi jakiś dostępny materiał (na przykład oryginalny samouczek HMM Rabinera) na temat szkolenia Viterbi?

— Jakub

Szkolenie Jacoba Viterbiego nosi również nazwę Segmental K-Means, patrz ten artykuł Juanga i Rabinera.

— alt

@Anoldmaninthesea. Patrzenie na prawdopodobieństwo między epokami jest normalnym sposobem oceny konwergencji (prawdopodobieństwo powinno zawsze wzrastać w każdej epoce, a następnie przestać, gdy osiągniesz lokalne maksima). Inną rzeczą, którą możesz zrobić, to wczesne zatrzymanie poprzez monitorowanie prawdopodobieństwa danych nieużywanych podczas EM.

— alt

Naprzód-wstecz jest używany, gdy chcesz policzyć „rzeczy niewidzialne”. Na przykład, gdy używasz EM do ulepszenia modelu za pomocą danych bez nadzoru. Myślę, że artykuł Pietrowa jest przykładem. W technice, o której myślę, najpierw trenujesz model z danymi z adnotacjami i dość gruboziarnistymi adnotacjami (np. Tag dla „Czasownika”). Następnie arbitralnie dzielisz masę prawdopodobieństwa dla tego stanu na dwie nieznacznie nierówne wielkości i ponownie trenujesz, biegając do przodu i do tyłu, aby zmaksymalizować prawdopodobieństwo poprzez redystrybucję masy między dwoma stanami.

— bmargulies
źródło