Algorytm forward – backward - Forward–backward algorithm

Algorytm przód-tył jest wnioskowanie algorytm dla ukrytych modeli Markowa , który oblicza tylne marginesowymi wszystkich ukrytych zmiennych stanu danej sekwencji obserwacji / emisji , czyli oblicza, dla wszystkich ukrytych zmiennych stanu , dystrybucji . To zadanie wnioskowania jest zwykle nazywane wygładzaniem . Algorytm wykorzystuje zasadę programowania dynamicznego do wydajnego obliczania wartości wymaganych do uzyskania późniejszych rozkładów krańcowych w dwóch przejściach. Pierwszy przebieg idzie do przodu w czasie, podczas gdy drugi cofa się w czasie; stąd nazwa algorytm naprzód – wstecz . ${\ Displaystyle o_ {1: T}: = o_ {1}, \ kropki, o_ {T}}$${\ Displaystyle X_ {t} \ in \ {X_ {1}, \ kropki, X_ {T} \}}$${\ Displaystyle P (X_ {t} \ | \ o_ {1: T})}$

Termin algorytm naprzód – wstecz jest również używany w odniesieniu do dowolnego algorytmu należącego do ogólnej klasy algorytmów, które działają na modelach sekwencji w sposób „przód – tył”. W tym sensie opisy w pozostałej części tego artykułu odnoszą się tylko do jednego konkretnego przypadku tej klasy.

Przegląd

W pierwszym przebiegu algorytm forward – backward oblicza zbiór prawdopodobieństw „forward”, które zapewniają wszystkim prawdopodobieństwo znalezienia się w jakimkolwiek określonym stanie, biorąc pod uwagę pierwsze obserwacje w sekwencji, tj . W drugim przebiegu algorytm oblicza zbiór prawdopodobieństw wstecznych, które zapewniają prawdopodobieństwo obserwacji pozostałych obserwacji w dowolnym punkcie początkowym , tj . Te dwa zestawy rozkładów prawdopodobieństwa można następnie połączyć, aby uzyskać rozkład na stanach w dowolnym określonym momencie, biorąc pod uwagę całą sekwencję obserwacji: ${\ displaystyle t \ in \ {1, \ kropki, T \}}$${\ displaystyle t}$${\ Displaystyle P (X_ {t} \ | \ o_ {1: t})}$${\ displaystyle t}$${\ Displaystyle P (o_ {t + 1: T} \ | \ X_ {t})}$

${\ Displaystyle P (X_ {t} \ | \ o_ {1: T}) = P (X_ {t} \ | \ o_ {1: t}, o_ {t + 1: T}) \ propto P (o_ {t + 1: T} \ | \ X_ {t}) P (X_ {t} | o_ {1: t})}$

Ostatnim krokiem wynika z zastosowania reguły Bayesa i warunkowej niezależności od i podane . ${\ Displaystyle o_ {t + 1: T}}$${\ Displaystyle o_ {1: t}}$${\ displaystyle X_ {t}}$

Jak opisano powyżej, algorytm obejmuje trzy kroki:

1. obliczanie prawdopodobieństw wyprzedzających
2. obliczanie prawdopodobieństw wstecz
3. obliczanie wygładzonych wartości.

Kroki do przodu i do tyłu mogą być również nazywane „przekazywaniem wiadomości do przodu” i „przekazywaniem wiadomości do tyłu” - terminy te wynikają z przekazywania wiadomości stosowanego w podejściach do propagacji ogólnych przekonań . Przy każdej pojedynczej obserwacji w sekwencji obliczane są prawdopodobieństwa, które mają być użyte do obliczeń przy następnej obserwacji. Krok wygładzania można obliczyć jednocześnie podczas przejścia wstecz. Ten krok umożliwia algorytmowi uwzględnienie wszelkich wcześniejszych obserwacji danych wyjściowych w celu obliczenia dokładniejszych wyników.

Algorytm naprzód – wstecz może być użyty do znalezienia najbardziej prawdopodobnego stanu w dowolnym momencie. Nie można go jednak użyć do znalezienia najbardziej prawdopodobnej sekwencji stanów (patrz algorytm Viterbiego ).

Prawdopodobieństwa w przód

Poniższy opis będzie używał macierzy wartości prawdopodobieństwa, a nie rozkładów prawdopodobieństwa, chociaż ogólnie algorytm naprzód-wstecz może być stosowany zarówno do ciągłych, jak i dyskretnych modeli prawdopodobieństwa.

Przekształcamy rozkłady prawdopodobieństwa związane z danym ukrytym modelem Markowa na notację macierzową w następujący sposób. Prawdopodobieństwa przejścia danej zmiennej losowej reprezentującej wszystkie możliwe stany w ukrytym modelu Markowa będą reprezentowane przez macierz, w której indeks kolumny będzie reprezentował stan docelowy, a indeks wiersza reprezentował stan początkowy. Przejście od stanu wiersz-wektor do przyrostowego stanu wektor-wiersz jest zapisywane jako . Poniższy przykład przedstawia system, w którym prawdopodobieństwo pozostania w tym samym stanie po każdym kroku wynosi 70%, a prawdopodobieństwo przejścia do innego stanu wynosi 30%. Macierz przejść jest zatem: ${\ Displaystyle \ mathbf {P} (X_ {t} \ mid X_ {t-1})}$${\ displaystyle X_ {t}}$${\ displaystyle \ mathbf {T}}$${\ displaystyle j}$${\ displaystyle i}$${\ displaystyle \ mathbf {\ pi _ {t}}}$${\ displaystyle \ mathbf {\ pi _ {t + 1}}}$${\ Displaystyle \ mathbf {\ pi _ {t + 1}} = \ mathbf {\ pi _ {t}} \ mathbf {T}}$

${\ Displaystyle \ mathbf {T} = {\ rozpocząć {pmatrix} 0,7 i 0,3 \\ 0,3 i 0,7 \ koniec {pmatrix}}}$

W typowym modelu Markowa pomnożymy wektor stanu przez tę macierz, aby otrzymać prawdopodobieństwa dla kolejnego stanu. W ukrytym modelu Markowa stan jest nieznany, a zamiast tego obserwujemy zdarzenia związane z możliwymi stanami. Matryca zdarzeń w postaci:

${\ Displaystyle \ mathbf {B} = {\ rozpocząć {pmatrix} 0,9 i 0,1 \\ 0,2 i 0,8 \ koniec {pmatrix}}}$

podaje prawdopodobieństwa obserwacji zdarzeń w określonym stanie. W powyższym przykładzie zdarzenie 1 będzie obserwowane w 90% przypadków, jeśli będziemy w stanie 1, podczas gdy zdarzenie 2 ma 10% prawdopodobieństwo wystąpienia w tym stanie. Natomiast zdarzenie 1 będzie obserwowane tylko w 20% przypadków, jeśli będziemy w stanie 2, a prawdopodobieństwo wystąpienia zdarzenia 2 wynosi 80%. Biorąc pod uwagę dowolny wektor wierszowy opisujący stan układu ( ), prawdopodobieństwo zaobserwowania zdarzenia j wynosi wtedy: ${\ displaystyle \ mathbf {\ pi}}$

${\ Displaystyle \ mathbf {P} (O = j) = \ suma _ {i} \ pi _ {i} B_ {i, j}}$

Prawdopodobieństwo danego stanu prowadzącego do obserwowanego zdarzenia j można przedstawić w postaci macierzy, mnożąc wiersz-wektor stanu ( ) przez macierz obserwacji ( ) zawierającą tylko wpisy po przekątnej. Kontynuując powyższy przykład, macierz obserwacji dla zdarzenia 1 wyglądałaby następująco: ${\ displaystyle \ mathbf {\ pi}}$${\ Displaystyle \ mathbf {O_ {j}} = \ mathrm {diag} (B _ {*, o_ {j}})}$

${\ Displaystyle \ mathbf {O_ {1}} = {\ rozpocząć {pmatrix} 0,9 i 0,0 \\ 0,0 i 0,2 \ koniec {pmatrix}}}$

To pozwala nam obliczyć nowy nieznormalizowany wektor stanu prawdopodobieństwa za pomocą reguły Bayesa, ważąc według prawdopodobieństwa, że ​​każdy element wygenerowanego zdarzenia 1 jako: ${\ displaystyle \ mathbf {\ pi '}}$${\ displaystyle \ mathbf {\ pi}}$

${\ displaystyle \ mathbf {\ pi '} = \ mathbf {\ pi} \ mathbf {O_ {1}}}$

Możemy teraz uczynić tę ogólną procedurę specyficzną dla naszej serii obserwacji. Zakładając wektor stanu początkowego (który można zoptymalizować jako parametr poprzez powtórzenia procedury forward-back), zaczynamy od , następnie aktualizujemy rozkład stanu i ważenie według prawdopodobieństwa pierwszej obserwacji: ${\ displaystyle \ mathbf {\ pi} _ {0}}$${\ displaystyle \ mathbf {f_ {0: 0}} = \ mathbf {\ pi} _ {0}}$

${\ Displaystyle \ mathbf {f_ {0: 1}} = \ mathbf {\ pi} _ {0} \ mathbf {T} \ mathbf {O_ {o (1)}}}$

Proces ten można przeprowadzić z dodatkowymi obserwacjami przy użyciu:

${\ Displaystyle \ mathbf {f_ {0: t}} = \ mathbf {f_ {0: t-1}} \ mathbf {T} \ mathbf {O_ {o (t)}}}$

Ta wartość jest przednim nieznormalizowanym wektorem prawdopodobieństwa. I-ta pozycja tego wektora zapewnia:

${\ Displaystyle \ mathbf {f_ {0: t}} (i) = \ mathbf {P} (o_ {1}, o_ {2}, \ kropki, o_ {t}, X_ {t} = x_ {i} | \ mathbf {\ pi} _ {0})}$

Zwykle normalizujemy wektor prawdopodobieństwa na każdym kroku, tak aby jego wpisy sumowały się do 1. W ten sposób na każdym kroku wprowadzany jest współczynnik skalowania, który:

${\ Displaystyle \ mathbf {{\ kapelusz {f}} _ {0: t}} = c_ {t} ^ {- 1} \ \ mathbf {{\ kapelusz {f}} _ {0: t-1}} \ mathbf {T} \ mathbf {O_ {o (t)}}}$

gdzie reprezentuje skalowany wektor z poprzedniego kroku i reprezentuje współczynnik skalujący, który powoduje sumowanie wpisów wynikowego wektora do 1. Iloczyn współczynników skalowania jest całkowitym prawdopodobieństwem zaobserwowania danych zdarzeń niezależnie od stanów końcowych: ${\ displaystyle \ mathbf {{\ hat {f}} _ {0: t-1}}}$${\ displaystyle c_ {t}}$

${\ Displaystyle \ mathbf {P} (o_ {1}, o_ {2}, \ kropki, o_ {t} | \ mathbf {\ pi} _ {0}) = \ prod _ {s = 1} ^ {t } c_ {s}}$

To pozwala nam zinterpretować skalowany wektor prawdopodobieństwa jako:

${\ displaystyle \ mathbf {{\ hat {f}} _ {0: t}} (i) = {\ frac {\ mathbf {f_ {0: t}} (i)} {\ prod _ {s = 1 } ^ {t} c_ {s}}} = {\ frac {\ mathbf {P} (o_ {1}, o_ {2}, \ dots, o_ {t}, X_ {t} = x_ {i} | \ mathbf {\ pi} _ {0})} {\ mathbf {P} (o_ {1}, o_ {2}, \ dots, o_ {t} | \ mathbf {\ pi} _ {0})}} = \ mathbf {P} (X_ {t} = x_ {i} | o_ {1}, o_ {2}, \ dots, o_ {t}, \ mathbf {\ pi} _ {0})}$

W ten sposób stwierdzamy, że iloczyn współczynników skalowania daje nam całkowite prawdopodobieństwo zaobserwowania danej sekwencji do czasu t, a skalowany wektor prawdopodobieństwa daje nam prawdopodobieństwo przebywania w każdym stanie w tym czasie.

Prawdopodobieństwa wsteczne

Podobną procedurę można skonstruować w celu znalezienia prawdopodobieństw wstecz. Mają one na celu zapewnienie prawdopodobieństw:

${\ Displaystyle \ mathbf {b_ {t: T}} (i) = \ mathbf {P} (o_ {t + 1}, o_ {t + 2}, \ kropki, o_ {T} | X_ {t} = x_ {i})}$

Oznacza to, że chcemy teraz założyć, że zaczynamy w określonym stanie ( ), a teraz interesuje nas prawdopodobieństwo zaobserwowania wszystkich przyszłych wydarzeń z tego stanu. Ponieważ przyjmuje się, że stan początkowy jest zadany (tj. Wcześniejsze prawdopodobieństwo tego stanu = 100%), zaczynamy od: ${\ displaystyle X_ {t} = x_ {i}}$

${\ Displaystyle \ mathbf {b_ {T: T}} = [1 \ 1 \ 1 \ \ kropki] ^ {T}}$

Zauważ, że używamy teraz wektora kolumnowego, podczas gdy prawdopodobieństwa do przodu używają wektorów wierszowych. Następnie możemy pracować wstecz, używając:

${\ Displaystyle \ mathbf {b_ {t-1: T}} = \ mathbf {T} \ mathbf {O_ {t}} \ mathbf {b_ {t: T}}}$

Chociaż moglibyśmy również znormalizować ten wektor, aby jego wpisy sumowały się do jednego, zwykle się to nie robi. Zauważając, że każdy wpis zawiera prawdopodobieństwo przyszłej sekwencji zdarzeń przy określonym stanie początkowym, normalizacja tego wektora byłaby równoważna zastosowaniu twierdzenia Bayesa w celu znalezienia prawdopodobieństwa każdego stanu początkowego przy danych przyszłych zdarzeniach (przy założeniu jednakowych wyprzedzeń dla wektora stanu końcowego ). Jednak bardziej powszechne jest skalowanie tego wektora przy użyciu tych samych stałych, które są używane w obliczeniach prawdopodobieństwa w przód. nie jest skalowany, ale kolejne operacje wykorzystują: ${\ displaystyle c_ {t}}$${\ displaystyle \ mathbf {b_ {T: T}}}$

${\ displaystyle \ mathbf {{\ hat {b}} _ {t-1: T}} = c_ {t} ^ {- 1} \ mathbf {T} \ mathbf {O_ {t}} \ mathbf {{\ kapelusz {b}} _ {t: T}}}$

gdzie reprezentuje poprzedni przeskalowany wektor. Wynik jest taki, że skalowany wektor prawdopodobieństwa jest powiązany z prawdopodobieństwami wstecznymi przez: ${\ displaystyle \ mathbf {{\ hat {b}} _ {t: T}}}$

${\ displaystyle \ mathbf {{\ hat {b}} _ {t: T}} (i) = {\ frac {\ mathbf {b_ {t: T}} (i)} {\ prod _ {s = t +1} ^ {T} c_ {s}}}}$

Jest to przydatne, ponieważ pozwala nam znaleźć całkowite prawdopodobieństwo przebywania w każdym stanie w danym czasie t, poprzez pomnożenie tych wartości:

${\ Displaystyle \ mathbf {\ gamma _ {t}} (i) = \ mathbf {P} (X_ {t} = x_ {i} | o_ {1}, o_ {2}, \ kropki, o_ {T} , \ mathbf {\ pi} _ {0}) = {\ frac {\ mathbf {P} (o_ {1}, o_ {2}, \ dots, o_ {T}, X_ {t} = x_ {i} | \ mathbf {\ pi} _ {0})} {\ mathbf {P} (o_ {1}, o_ {2}, \ dots, o_ {T} | \ mathbf {\ pi} _ {0})} } = {\ frac {\ mathbf {f_ {0: t}} (i) \ cdot \ mathbf {b_ {t: T}} (i)} {\ prod _ {s = 1} ^ {T} c_ { s}}} = \ mathbf {{\ hat {f}} _ {0: t}} (i) \ cdot \ mathbf {{\ hat {b}} _ {t: T}} (i)}$

Aby to zrozumieć, zauważamy, że zapewnia prawdopodobieństwo zaobserwowania danych zdarzeń w sposób, który przechodzi przez stan w czasie t. To prawdopodobieństwo obejmuje prawdopodobieństwa przyszłe obejmujące wszystkie zdarzenia do czasu t, jak również prawdopodobieństwa wsteczne, które obejmują wszystkie zdarzenia przyszłe. To jest licznik, którego szukamy w naszym równaniu i dzielimy przez całkowite prawdopodobieństwo sekwencji obserwacji, aby znormalizować tę wartość i wyodrębnić tylko prawdopodobieństwo, że . Te wartości są czasami nazywane „wartościami wygładzonymi”, ponieważ łączą prawdopodobieństwa do przodu i do tyłu w celu obliczenia prawdopodobieństwa końcowego. ${\ Displaystyle \ mathbf {f_ {0: t}} (i) \ cdot \ mathbf {b_ {t: T}} (i)}$${\ displaystyle x_ {i}}$${\ displaystyle X_ {t} = x_ {i}}$

Wartości zapewniają zatem prawdopodobieństwo znalezienia się w każdym stanie w czasie t. Jako takie, są one przydatne do określenia najbardziej prawdopodobnego stanu w dowolnym momencie. Termin „najbardziej prawdopodobny stan” jest nieco niejednoznaczny. Podczas gdy najbardziej prawdopodobny stan jest najbardziej prawdopodobny w danym momencie, sekwencja indywidualnie prawdopodobnych stanów nie jest prawdopodobnie sekwencją najbardziej prawdopodobną. Dzieje się tak, ponieważ prawdopodobieństwa dla każdego punktu są obliczane niezależnie od siebie. Nie uwzględniają one prawdopodobieństw przejścia między stanami, dzięki czemu można uzyskać stany w dwóch momentach (t i t + 1), które są najbardziej prawdopodobne w tych punktach czasowych, ale które mają bardzo małe prawdopodobieństwo wystąpienia razem, tj. . Najbardziej prawdopodobną sekwencję stanów, które utworzyły sekwencję obserwacyjną, można znaleźć za pomocą algorytmu Viterbiego . ${\ Displaystyle \ mathbf {\ gamma _ {t}} (i)}$${\ Displaystyle \ mathbf {P} (X_ {t} = x_ {i}, X_ {t + 1} = x_ {j}) \ neq \ mathbf {P} (X_ {t} = x_ {i}) \ mathbf {P} (X_ {t + 1} = x_ {j})}$

Przykład

W tym przykładzie za podstawę przyjęto parasolowy świat w Russell & Norvig 2010, rozdział 15, s. 567, w którym chcielibyśmy wywnioskować pogodę na podstawie obserwacji innej osoby noszącej lub nie posiadającej parasola. Zakładamy dwa możliwe stany pogody: stan 1 = deszcz, stan 2 = brak deszczu. Zakładamy, że pogoda ma 70% szans na pozostanie bez zmian każdego dnia i 30% na zmianę. Prawdopodobieństwa przejścia są zatem:

${\ Displaystyle \ mathbf {T} = {\ rozpocząć {pmatrix} 0,7 i 0,3 \\ 0,3 i 0,7 \ koniec {pmatrix}}}$

Zakładamy również, że każdy stan generuje jedno z dwóch możliwych zdarzeń: zdarzenie 1 = parasol, zdarzenie 2 = brak parasola. Prawdopodobieństwa warunkowe dla tych występujących w każdym stanie są podane przez macierz prawdopodobieństwa:

${\ Displaystyle \ mathbf {B} = {\ rozpocząć {pmatrix} 0,9 i 0,1 \\ 0,2 i 0,8 \ koniec {pmatrix}}}$

Następnie obserwujemy następującą sekwencję zdarzeń: {parasol, parasol, brak parasola, parasol, parasol}, które w naszych obliczeniach przedstawimy jako:

${\ Displaystyle \ mathbf {O_ {1}} = {\ rozpocząć {pmatrix} 0,9 i 0,0 \\ 0,0 i 0,2 \ koniec {pmatrix}} ~~ \ mathbf {O_ {2}} = {\ rozpocząć {pmatrix } 0,9 i 0,0 \\ 0,0 i 0,2 \ end {pmatrix}} ~~ \ mathbf {O_ {3}} = {\ begin {pmatrix} 0,1 i 0,0 \\ 0,0 i 0,8 \ end {pmatrix}} ~~ \ mathbf {O_ {4}} = {\ begin {pmatrix} 0,9 i 0,0 \\ 0,0 i 0,2 \ end {pmatrix}} ~~ \ mathbf {O_ {5}} = {\ begin {pmatrix} 0,9 i 0,0 \\ 0,0 i 0,2 \ end {pmatrix}}}$

Zauważ, że różni się od innych ze względu na obserwację „bez parasola”. ${\ displaystyle \ mathbf {O_ {3}}}$

Obliczając prawdopodobieństwa w przód, zaczynamy od:

${\ displaystyle \ mathbf {f_ {0: 0}} = {\ początek {pmatrix} 0,5 i 0,5 \ koniec {pmatrix}}}$

który jest naszym poprzednim wektorem stanu wskazującym, że nie wiemy, w jakim stanie jest pogoda przed naszymi obserwacjami. Podczas gdy wektor stanu powinien być podany jako wektor wierszowy, użyjemy transpozycji macierzy, aby poniższe obliczenia były łatwiejsze do odczytania. Nasze obliczenia zapisujemy wtedy w postaci:

${\ displaystyle (\ mathbf {{\ hat {f}} _ {0: t}}) ^ {T} = c_ {t} ^ {- 1} \ mathbf {O_ {t}} (\ mathbf {T} ) ^ {T} (\ mathbf {{\ hat {f}} _ {0: t-1}}) ^ {T}}$

zamiast:

${\ displaystyle \ mathbf {{\ hat {f}} _ {0: t}} = c_ {t} ^ {- 1} \ mathbf {{\ kapelusz {f}} _ {0: t-1}} \ mathbf {T} \ mathbf {O_ {t}}}$

Zauważ, że macierz transformacji również jest transponowana, ale w naszym przykładzie transpozycja jest równa oryginalnej macierzy. Wykonanie tych obliczeń i normalizacja wyników zapewnia:

${\ Displaystyle (\ mathbf {{\ kapelusz {f}} _ {0: 1}}) ^ {T} = c_ {1} ^ {- 1} {\ rozpocząć {pmatrix} 0,9 i 0,0 \\ 0,0 i 0 .2 \ end {pmatrix}} {\ begin {pmatrix} 0,7 i 0,3 \\ 0,3 i 0,7 \ end {pmatrix}} {\ begin {pmatrix} 0,5000 \\ 0,5000 \ end {pmatrix}} = c_ {1 } ^ {- 1} {\ begin {pmatrix} 0,4500 \\ 0.1000 \ end {pmatrix}} = {\ begin {pmatrix} 0.8182 \\ 0.1818 \ end {pmatrix}}}$

${\ Displaystyle (\ mathbf {{\ hat {f}} _ {0: 2}}) ^ {T} = c_ {2} ^ {- 1} {\ rozpocząć {pmatrix} 0,9 i 0,0 \\ 0,0 i 0 .2 \ end {pmatrix}} {\ begin {pmatrix} 0,7 i 0,3 \\ 0,3 i 0,7 \ end {pmatrix}} {\ begin {pmatrix} 0.8182 \\ 0.1818 \ end {pmatrix}} = c_ {2 } ^ {- 1} {\ begin {pmatrix} 0.5645 \\ 0.0745 \ end {pmatrix}} = {\ begin {pmatrix} 0.8834 \\ 0.1166 \ end {pmatrix}}}$

${\ Displaystyle (\ mathbf {{\ kapelusz {f}} _ {0: 3}}) ^ {T} = c_ {3} ^ {- 1} {\ rozpocząć {pmatrix} 0,1 i 0,0 \\ 0,0 i 0 .8 \ end {pmatrix}} {\ begin {pmatrix} 0,7 i 0,3 \\ 0,3 i 0,7 \ end {pmatrix}} {\ begin {pmatrix} 0,8834 \\ 0.1166 \ end {pmatrix}} = c_ {3 } ^ {- 1} {\ begin {pmatrix} 0,0653 \\ 0.2772 \ end {pmatrix}} = {\ begin {pmatrix} 0.1907 \\ 0.8093 \ end {pmatrix}}}$

${\ Displaystyle (\ mathbf {{\ hat {f}} _ {0: 4}}) ^ {T} = c_ {4} ^ {- 1} {\ rozpocząć {pmatrix} 0,9 i 0,0 \\ 0,0 i 0 .2 \ end {pmatrix}} {\ begin {pmatrix} 0,7 i 0,3 \\ 0,3 i 0,7 \ end {pmatrix}} {\ begin {pmatrix} 0,1907 \\ 0.8093 \ end {pmatrix}} = c_ {4 } ^ {- 1} {\ begin {pmatrix} 0.3386 \\ 0.1247 \ end {pmatrix}} = {\ begin {pmatrix} 0.7308 \\ 0.2692 \ end {pmatrix}}}$

${\ Displaystyle (\ mathbf {{\ hat {f}} _ {0: 5}}) ^ {T} = c_ {5} ^ {- 1} {\ rozpocząć {pmatrix} 0,9 i 0,0 \\ 0,0 i 0 .2 \ end {pmatrix}} {\ begin {pmatrix} 0,7 i 0,3 \\ 0,3 i 0,7 \ end {pmatrix}} {\ begin {pmatrix} 0,7308 \\ 0,2692 \ end {pmatrix}} = c_ {5 } ^ {- 1} {\ begin {pmatrix} 0.5331 \\ 0.0815 \ end {pmatrix}} = {\ begin {pmatrix} 0.8673 \\ 0.1327 \ end {pmatrix}}}$

Dla prawdopodobieństw wstecznych zaczynamy od:

${\ Displaystyle \ mathbf {b_ {5: 5}} = {\ początek {pmatrix} 1,0 \\ 1,0 \ koniec {pmatrix}}}$

Następnie jesteśmy w stanie obliczyć (używając obserwacji w odwrotnej kolejności i normalizując z różnymi stałymi):

${\ displaystyle \ mathbf {{\ hat {b}} _ {4: 5}} = \ alpha {\ begin {pmatrix} 0,7 i 0,3 \\ 0,3 i 0,7 \ end {pmatrix}} {\ begin {pmatrix } 0,9 i 0,0 \\ 0,0 i 0,2 \ end {pmatrix}} {\ begin {pmatrix} 1.0000 \\ 1.0000 \ end {pmatrix}} = \ alpha {\ begin {pmatrix} 0,6900 \\ 0,4100 \ end {pmatrix }} = {\ begin {pmatrix} 0.6273 \\ 0.3727 \ end {pmatrix}}}$

${\ displaystyle \ mathbf {{\ hat {b}} _ {3: 5}} = \ alpha {\ begin {pmatrix} 0,7 i 0,3 \\ 0,3 i 0,7 \ end {pmatrix}} {\ begin {pmatrix } 0,9 i 0,0 \\ 0,0 i 0,2 \ end {pmatrix}} {\ begin {pmatrix} 0.6273 \\ 0.3727 \ end {pmatrix}} = \ alpha {\ begin {pmatrix} 0,4175 \\ 0,2215 \ end {pmatrix }} = {\ begin {pmatrix} 0.6533 \\ 0.3467 \ end {pmatrix}}}$

${\ displaystyle \ mathbf {{\ hat {b}} _ {2: 5}} = \ alpha {\ begin {pmatrix} 0,7 i 0,3 \\ 0,3 i 0,7 \ end {pmatrix}} {\ begin {pmatrix } 0,1 i 0,0 \\ 0,0 i 0,8 \ end {pmatrix}} {\ begin {pmatrix} 0,6533 \\ 0,3467 \ end {pmatrix}} = \ alpha {\ begin {pmatrix} 0,1289 \\ 0,2138 \ end {pmatrix }} = {\ begin {pmatrix} 0.3763 ​​\\ 0.6237 \ end {pmatrix}}}$

${\ displaystyle \ mathbf {{\ hat {b}} _ {1: 5}} = \ alpha {\ begin {pmatrix} 0,7 i 0,3 \\ 0,3 i 0,7 \ end {pmatrix}} {\ begin {pmatrix } 0,9 i 0,0 \\ 0,0 i 0,2 \ end {pmatrix}} {\ begin {pmatrix} 0,3763 \\ 0,6237 \ end {pmatrix}} = \ alpha {\ begin {pmatrix} 0,2745 \\ 0,1889 \ end {pmatrix }} = {\ begin {pmatrix} 0,5923 \\ 0,4077 \ end {pmatrix}}}$

${\ displaystyle \ mathbf {{\ hat {b}} _ {0: 5}} = \ alpha {\ begin {pmatrix} 0,7 i 0,3 \\ 0,3 i 0,7 \ end {pmatrix}} {\ begin {pmatrix } 0,9 i 0,0 \\ 0,0 i 0,2 \ end {pmatrix}} {\ begin {pmatrix} 0,5923 \\ 0,4077 \ end {pmatrix}} = \ alpha {\ begin {pmatrix} 0,3976 \\ 0,2170 \ end {pmatrix }} = {\ begin {pmatrix} 0.6469 \\ 0.3531 \ end {pmatrix}}}$

Na koniec obliczymy wygładzone wartości prawdopodobieństwa. Wyniki te należy również przeskalować tak, aby ich wpisy sumowały się do 1, ponieważ nie skalowaliśmy prawdopodobieństw wstecz z wartościami znalezionymi wcześniej. Powyższe wektory prawdopodobieństwa wstecznego reprezentują zatem w rzeczywistości prawdopodobieństwo wystąpienia każdego stanu w czasie t, biorąc pod uwagę przyszłe obserwacje. Ponieważ te wektory są proporcjonalne do rzeczywistych wstecznych prawdopodobieństw, wynik musi zostać dodatkowo przeskalowany. ${\ displaystyle c_ {t}}$

${\ Displaystyle (\ mathbf {\ gamma _ {0}}) ^ {T} = \ alpha {\ begin {pmatrix} 0,5000 \\ 0,5000 \ end {pmatrix}} \ circ {\ begin {pmatrix} 0,6469 \\ 0,3531 \ end {pmatrix}} = \ alpha {\ begin {pmatrix} 0.3235 \\ 0.1765 \ end {pmatrix}} = {\ begin {pmatrix} 0.6469 \\ 0.3531 \ end {pmatrix}}}$

${\ Displaystyle (\ mathbf {\ gamma _ {1}}) ^ {T} = \ alpha {\ begin {pmatrix} 0,8182 \\ 0,1818 \ end {pmatrix}} \ circ {\ begin {pmatrix} 0,5923 \\ 0,4077 \ end {pmatrix}} = \ alpha {\ begin {pmatrix} 0.4846 \\ 0.0741 \ end {pmatrix}} = {\ begin {pmatrix} 0.8673 \\ 0.1327 \ end {pmatrix}}}$

${\ Displaystyle (\ mathbf {\ gamma _ {2}}) ^ {T} = \ alpha {\ begin {pmatrix} 0,8834 \\ 0,1166 \ end {pmatrix}} \ circ {\ begin {pmatrix} 0,3763 \\ 0,6237 \ end {pmatrix}} = \ alpha {\ begin {pmatrix} 0.3324 \\ 0.0728 \ end {pmatrix}} = {\ begin {pmatrix} 0.8204 \\ 0.1796 \ end {pmatrix}}}$

${\ Displaystyle (\ mathbf {\ gamma _ {3}}) ^ {T} = \ alpha {\ begin {pmatrix} 0,1907 \\ 0,8093 \ end {pmatrix}} \ circ {\ begin {pmatrix} 0,6533 \\ 0,3467 \ end {pmatrix}} = \ alpha {\ begin {pmatrix} 0.1246 \\ 0.2806 \ end {pmatrix}} = {\ begin {pmatrix} 0,3075 \\ 0.6925 \ end {pmatrix}}}$

${\ Displaystyle (\ mathbf {\ gamma _ {4}}) ^ {T} = \ alpha {\ begin {pmatrix} 0,7308 \\ 0,2692 \ end {pmatrix}} \ circ {\ begin {pmatrix} 0,6273 \\ 0,3727 \ end {pmatrix}} = \ alpha {\ begin {pmatrix} 0.4584 \\ 0.1003 \ end {pmatrix}} = {\ begin {pmatrix} 0.8204 \\ 0.1796 \ end {pmatrix}}}$

${\ Displaystyle (\ mathbf {\ gamma _ {5}}) ^ {T} = \ alpha {\ begin {pmatrix} 0,8673 \\ 0,1327 \ end {pmatrix}} \ circ {\ begin {pmatrix} 1,0000 \\ 1,0000 \ end {pmatrix}} = \ alpha {\ begin {pmatrix} 0.8673 \\ 0.1327 \ end {pmatrix}} = {\ begin {pmatrix} 0.8673 \\ 0.1327 \ end {pmatrix}}}$

Zauważ, że wartość jest równa i to jest równe . Wynika to naturalnie, ponieważ oba i zaczynają się od jednakowych wyprzedzeń względem wektorów stanu początkowego i końcowego (odpowiednio) i uwzględniają wszystkie obserwacje. Jednak będzie równy tylko wtedy, gdy nasz wektor stanu początkowego reprezentuje jednolity poprzedni (tj. Wszystkie wpisy są równe). Jeśli tak nie jest, należy połączyć go z wektorem stanu początkowego, aby znaleźć najbardziej prawdopodobny stan początkowy. W ten sposób stwierdzamy, że same prawdopodobieństwa wyprzedzające są wystarczające do obliczenia najbardziej prawdopodobnego stanu końcowego. Podobnie, prawdopodobieństwa wsteczne można łączyć z wektorem stanu początkowego, aby zapewnić najbardziej prawdopodobny stan początkowy, biorąc pod uwagę obserwacje. Prawdopodobieństwa do przodu i do tyłu muszą być tylko połączone, aby wywnioskować najbardziej prawdopodobne stany między punktem początkowym i końcowym. ${\ displaystyle \ mathbf {\ gamma _ {0}}}$${\ displaystyle \ mathbf {{\ hat {b}} _ {0: 5}}}$${\ displaystyle \ mathbf {\ gamma _ {5}}}$${\ displaystyle \ mathbf {{\ hat {f}} _ {0: 5}}}$${\ displaystyle \ mathbf {{\ hat {f}} _ {0: 5}}}$${\ displaystyle \ mathbf {{\ hat {b}} _ {0: 5}}}$${\ displaystyle \ mathbf {\ gamma _ {0}}}$${\ displaystyle \ mathbf {{\ hat {b}} _ {0: 5}}}$${\ displaystyle \ mathbf {{\ hat {b}} _ {0: 5}}}$

Z powyższych obliczeń wynika, że ​​najbardziej prawdopodobnym stanem pogodowym każdego dnia oprócz trzeciego był „deszcz”. Mówią nam jednak więcej niż to, ponieważ zapewniają teraz sposób ilościowego określenia prawdopodobieństw każdego stanu w różnym czasie. Być może co najważniejsze, nasza wartość w kwantyfikacji naszej wiedzy o wektorze stanu na końcu sekwencji obserwacji. Możemy następnie wykorzystać to do przewidzenia prawdopodobieństwa wystąpienia różnych stanów pogodowych w przyszłości, a także prawdopodobieństwa zaobserwowania parasola. ${\ displaystyle \ mathbf {\ gamma _ {5}}}$

Występ

Algorytm naprzód – wstecz działa ze złożonością czasową w przestrzeni , gdzie jest długością sekwencji czasowej i liczbą symboli w alfabecie stanu. Algorytm może również działać w stałej przestrzeni ze złożonością czasową poprzez przeliczanie wartości na każdym kroku. Dla porównania, procedura brutalnej siły wygenerowałaby wszystkie możliwe sekwencje stanów i obliczyłaby łączne prawdopodobieństwo każdej sekwencji stanów z obserwowanymi seriami zdarzeń, które miałyby złożoność czasową . Brutalna siła jest trudna do rozwiązania w przypadku realistycznych problemów, ponieważ liczba możliwych sekwencji ukrytych węzłów jest zazwyczaj niezwykle wysoka. ${\ Displaystyle O (S ^ {2} T)}$${\ Displaystyle O (ST)}$${\ displaystyle T}$${\ displaystyle S}$${\ Displaystyle O (S ^ {2} T ^ {2})}$${\ Displaystyle S ^ {T}}$ ${\ Displaystyle O (T \ cdot S ^ {T})}$

Ulepszenie ogólnego algorytmu naprzód-wstecz, zwanego algorytmem wyspowym, zamienia mniejsze zużycie pamięci na dłuższy czas działania, zajmując czas i pamięć. Ponadto możliwe jest odwrócenie modelu procesu w celu uzyskania algorytmu przestrzenno- czasowego, chociaż proces odwrócony może nie istnieć lub być źle uwarunkowany . ${\ Displaystyle O (S ^ {2} T \ log T)}$${\ Displaystyle O (S ^ {2} \ log T)}$${\ Displaystyle O (S)}$${\ Displaystyle O (S ^ {2} T)}$

Ponadto opracowano algorytmy do wydajnego obliczania dzięki wygładzaniu online, takim jak algorytm wygładzania o stałym opóźnieniu (FLS). ${\ displaystyle \ mathbf {f_ {0: t + 1}}}$

Pseudo kod

algorithm forward_backward is
    input: guessState
           int sequenceIndex
    output: result

    if sequenceIndex is past the end of the sequence then
        return 1
    if (guessState, sequenceIndex) has been seen before then
        return saved result

    result := 0

    for each neighboring state n:
        result := result + (transition probability from guessState to 
                            n given observation element at sequenceIndex)
                            × Backward(n, sequenceIndex + 1)

    save result for (guessState, sequenceIndex)

    return result

Przykład Pythona

Biorąc pod uwagę HMM (podobnie jak w algorytmie Viterbiego ) reprezentowany w języku programowania Python :

states = ('Healthy', 'Fever')
end_state = 'E'
 
observations = ('normal', 'cold', 'dizzy')
 
start_probability = {'Healthy': 0.6, 'Fever': 0.4}
 
transition_probability = {
   'Healthy' : {'Healthy': 0.69, 'Fever': 0.3, 'E': 0.01},
   'Fever' : {'Healthy': 0.4, 'Fever': 0.59, 'E': 0.01},
   }
 
emission_probability = {
   'Healthy' : {'normal': 0.5, 'cold': 0.4, 'dizzy': 0.1},
   'Fever' : {'normal': 0.1, 'cold': 0.3, 'dizzy': 0.6},
   }

Implementację algorytmu forward-backward możemy napisać następująco:

def fwd_bkw(observations, states, start_prob, trans_prob, emm_prob, end_st):
    """Forward–backward algorithm."""
    # Forward part of the algorithm
    fwd = []
    for i, observation_i in enumerate(observations):
        f_curr = {}
        for st in states:
            if i == 0:
                # base case for the forward part
                prev_f_sum = start_prob[st]
            else:
                prev_f_sum = sum(f_prev[k] * trans_prob[k][st] for k in states)

            f_curr[st] = emm_prob[st][observation_i] * prev_f_sum

        fwd.append(f_curr)
        f_prev = f_curr

    p_fwd = sum(f_curr[k] * trans_prob[k][end_st] for k in states)

    # Backward part of the algorithm
    bkw = []
    for i, observation_i_plus in enumerate(reversed(observations[1:] + (None,))):
        b_curr = {}
        for st in states:
            if i == 0:
                # base case for backward part
                b_curr[st] = trans_prob[st][end_st]
            else:
                b_curr[st] = sum(trans_prob[st][l] * emm_prob[l][observation_i_plus] * b_prev[l] for l in states)

        bkw.insert(0,b_curr)
        b_prev = b_curr

    p_bkw = sum(start_prob[l] * emm_prob[l][observations[0]] * b_curr[l] for l in states)

    # Merging the two parts
    posterior = []
    for i in range(len(observations)):
        posterior.append({st: fwd[i][st] * bkw[i][st] / p_fwd for st in states})

    assert p_fwd == p_bkw
    return fwd, bkw, posterior

Funkcja fwd_bkw przyjmuje następujące argumenty: x jest sekwencją obserwacji, np ['normal', 'cold', 'dizzy'] .; states jest zbiorem stanów ukrytych; a_0 jest prawdopodobieństwem rozpoczęcia; a są prawdopodobieństwami przejścia; i e są prawdopodobieństwami emisji.

Dla uproszczenia kodu, zakładamy, że sekwencja obserwacji x nie jest pusty i że a[i][j] i e[i][j] jest określona dla wszystkich państw i, j.

W działającym przykładzie algorytm naprzód-wstecz jest używany w następujący sposób:

def example():
    return fwd_bkw(observations,
                   states,
                   start_probability,
                   transition_probability,
                   emission_probability,
                   end_state)

>>> for line in example():
...     print(*line)
... 
{'Healthy': 0.3, 'Fever': 0.04000000000000001} {'Healthy': 0.0892, 'Fever': 0.03408} {'Healthy': 0.007518, 'Fever': 0.028120319999999997}
{'Healthy': 0.0010418399999999998, 'Fever': 0.00109578} {'Healthy': 0.00249, 'Fever': 0.00394} {'Healthy': 0.01, 'Fever': 0.01}
{'Healthy': 0.8770110375573259, 'Fever': 0.1229889624426741} {'Healthy': 0.623228030950954, 'Fever': 0.3767719690490461} {'Healthy': 0.2109527048413057, 'Fever': 0.7890472951586943}

Zobacz też

• Algorytm Bauma – Welcha
• Algorytm Viterbiego
• Algorytm BCJR

Bibliografia

• Lawrence R. Rabiner , Samouczek dotyczący ukrytych modeli Markowa i wybranych zastosowań w rozpoznawaniu mowy. Postępowanie IEEE , 77 (2), s. 257–286, luty 1989. 10.1109 / 5.18626
• Lawrence R. Rabiner, BH Juang (styczeń 1986). „Wprowadzenie do ukrytych modeli Markowa”. Magazyn IEEE ASSP : 4–15.
• Eugene Charniak (1993). Statystyczna nauka języków . Cambridge, Massachusetts: MIT Press. ISBN   978-0-262-53141-2 .
• Stuart Russell i Peter Norvig (2010). Artificial Intelligence A Modern Approach 3rd Edition . Upper Saddle River, New Jersey: Pearson Education / Prentice-Hall. ISBN   978-0-13-604259-4 .

Linki zewnętrzne

• Interaktywny arkusz kalkulacyjny do nauki algorytmu w przód / w tył (arkusz kalkulacyjny i artykuł z przewodnikiem krok po kroku)
• Samouczek dotyczący ukrytych modeli Markowa, w tym algorytm forward – backward
• Zbiór algorytmów AI zaimplementowanych w Javie (w tym HMM i algorytm forward – backward)