Algorytm do przodu i do tyłu

Algorytm przód-tył jest algorytmem wnioskowania dla ukrytych modeli Markowa , który oblicza tylne brzegi wszystkich ukrytych zmiennych stanu przy danej sekwencji obserwacji / emisji ${\ displaystyle o_ {1: T}: = o_ {1}, \ kropki, o_ {T}}$ , tj. oblicza dla wszystkich ukrytych zmiennych stanu ${\ Displaystyle X_ {t} \ w \ { X_ {1}, \ kropki, X_ {T} \}}$ , rozkład ${\ Displaystyle P (X_ {t} \ |\ o_ {1: T})}$ . To zadanie wnioskowania jest zwykle nazywane wygładzaniem . Algorytm wykorzystuje zasadę programowania dynamicznego do wydajnego obliczania wartości wymaganych do uzyskania tylnych rozkładów brzeżnych w dwóch przebiegach. Pierwsze przejście idzie do przodu w czasie, podczas gdy drugie cofa się w czasie; stąd nazwa algorytm do przodu i do tyłu .

Termin algorytm do przodu i do tyłu 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 do przodu i do tyłu. W tym sensie opisy w dalszej części tego artykułu odnoszą się tylko do jednej konkretnej instancji tej klasy.

Przegląd

$i$ tyłu zestaw prawdopodobieństw do przodu, zakończenia w jakimkolwiek określonym stanie, biorąc pod uwagę pierwsze $\$ w sekwencji, tj. $o_ {1: t} )}$ . ${\ displaystyle P. (o_{t+1:T}\ |\ X_{t})}$ drugim przejściu algorytm oblicza zestaw prawdopodobieństw wstecznych, które zapewniają prawdopodobieństwo zaobserwowania pozostałych obserwacji przy dowolnym punkcie początkowym, $tj$ . . Te dwa zestawy rozkładów prawdopodobieństwa można następnie połączyć, aby uzyskać rozkład stanów w dowolnym określonym momencie, biorąc pod uwagę całą sekwencję obserwacji:

${\ 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})}$

Ostatni krok wynika z zastosowania reguły Bayesa i warunkowej niezależności o ${\ Displaystyle o_ {t + 1: T}}$ i $: t}}$ biorąc pod uwagę ${\ Displaystyle X_ {t}}$ .

Jak opisano powyżej, algorytm obejmuje trzy kroki:

1. obliczanie prawdopodobieństwa naprzód
2. obliczanie prawdopodobieństw wstecznych
3. obliczanie wygładzonych wartości.

Kroki do przodu i do tyłu można również nazwać „przekazywaniem wiadomości do przodu” i „przekazywaniem wiadomości wstecz” - terminy te wynikają z przekazywania wiadomości stosowanego w ogólnych podejściach do propagowania przekonań . Przy każdej pojedynczej obserwacji w sekwencji obliczane są prawdopodobieństwa, które zostaną użyte do obliczeń przy następnej obserwacji. Krok wygładzania można obliczyć jednocześnie podczas przejścia wstecz. Ten krok pozwala algorytmowi wziąć pod uwagę wszelkie wcześniejsze obserwacje danych wyjściowych w celu obliczenia dokładniejszych wyników.

Algorytm do przodu i do tyłu może być użyty do znalezienia najbardziej prawdopodobnego stanu dla dowolnego punktu w czasie. Nie można go jednak użyć do znalezienia najbardziej prawdopodobnej sekwencji stanów (patrz algorytm Viterbiego ).

Prawdopodobieństwa naprzód

Poniższy opis będzie wykorzystywał macierze wartości prawdopodobieństwa, a nie rozkłady prawdopodobieństwa, chociaż ogólnie algorytm naprzód-wstecz można zastosować 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. P. ${\ Displaystyle \ mathbf {P} (X_ {t} \ mid X_ {t-1})}$ danej zmiennej losowej $\ Displaystyle X_ {t} }$ reprezentujące wszystkie możliwe stany w ukrytym modelu Markowa będą reprezentowane przez macierz, ${$$displaystyle$ kolumny będzie reprezentował stan docelowy, a indeks wiersza ja $i }$ reprezentuje stan początkowy. Przejście ze stanu $mathbf {\ pi _ {t + 1}}}$ wierszowego do przyrostowego stanu wektora wierszowego $Displaystyle$${\ Displaystyle \ mathbf {\ pi _ {t + 1}} = \ mathbf {\ pi _ {t}} \ mathbf {T}$ = . Poniższy przykład przedstawia układ, 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ść to wtedy:

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

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

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

zapewnia prawdopodobieństwa zaobserwowania zdarzeń w określonym stanie. W powyższym przykładzie zdarzenie 1 będzie obserwowane przez 90% czasu, jeśli jesteśmy w stanie 1, podczas gdy prawdopodobieństwo wystąpienia zdarzenia 2 w tym stanie wynosi 10%. W przeciwieństwie do tego, zdarzenie 1 będzie obserwowane tylko przez 20% czasu, jeśli jesteśmy w stanie 2, a zdarzenie 2 ma 80% szans na wystąpienie. Biorąc pod uwagę dowolny wektor wierszowy opisujący stan systemu ( ), 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 wektor wierszowy stanu ( $przez$ macierz obserwacji ( ${\ Displaystyle \ mathbf {O_ {j}} = \ operatorname {diag} (B_ {*, o_ {j}})} )$ zawierający tylko wpisy ukośne. Kontynuując powyższy przykład, macierz obserwacji dla zdarzenia 1 wyglądałaby następująco:

${\ 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ństw za pomocą reguły Bayesa, ważąc prawdopodobieństwo, że każdy element wygenerował $Displaystyle$ 1 $\ mathbf {\ pi '}}$ Jak:

${\ 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 ${\ displaystyle \ mathbf {f_{0:0}} =\mathbf {\pi} _{0}}$ , a następnie aktualizujemy rozkład stanu i wagę o prawdopodobieństwo pierwszej obserwacji:

${\ 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 nieznormalizowanym wektorem prawdopodobieństwa w przód. 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})}$

Zazwyczaj będziemy normalizować 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, tak że:

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

gdzie ${\ Displaystyle \ mathbf {{\ kapelusz {f}} _ {0: t-1}}}$ reprezentuje przeskalowany wektor z poprzedniego kroku i reprezentuje przeskalowany wektor ${\ displaystyle c_ {t}}$ współczynnik skalowania, który powoduje, że wpisy wynikowego wektora sumują się do 1. Iloczyn współczynników skalowania jest całkowitym prawdopodobieństwem zaobserwowania danych zdarzeń niezależnie od stanów końcowych:

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

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

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

Stwierdzamy zatem, ż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 wstecznych prawdopodobieństw. Mają one na celu przedstawienie prawdopodobieństw:

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

$) , a$ chcemy teraz założyć, że zaczynamy w określonym stanie ( interesuje nas prawdopodobieństwo zaobserwowania wszystkich ten stan. Ponieważ stan początkowy przyjmujemy jako dany (tj. prawdopodobieństwo a priori tego stanu = 100%), zaczynamy od:

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

Zauważ, że teraz używamy wektora kolumnowego, podczas gdy prawdopodobieństwa naprzód używały 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 znormalizować również ten wektor, tak aby jego wpisy sumowały się do jednego, zwykle się tego nie robi. Zauważając, że każdy wpis zawiera prawdopodobieństwo wystąpienia sekwencji przyszłych zdarzeń przy danym stanie początkowym, normalizacja tego wektora byłaby równoznaczna z zastosowaniem twierdzenia Bayesa w celu znalezienia prawdopodobieństwa wystąpienia każdego stanu początkowego przy danych przyszłych zdarzeniach (przy założeniu jednolitych wartości a priori dla wektora stanu końcowego ). $,$ bardziej powszechne jest skalowanie tego wektora przy użyciu tych samych które są używane w obliczeniach prawdopodobieństwa w przód. ${\ displaystyle \ mathbf {b_ {T: T}}}$ nie jest skalowany, ale kolejne operacje wykorzystują:

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

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

${\ Displaystyle \ mathbf {{\ kapelusz {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, mnożąc te 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},\kropki,o_{T},X_{t}=x_ {i}|\mathbf {\pi} _{0})}{\mathbf {P} (o_{1},o_{2},\kropki,o_{T}|\mathbf {\pi} _{0 })}}={\frac {\mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)}{\prod _{s=1}^{T }c_{s}}}=\mathbf {{\kapelusz {f}}_{0:t}} (i)\cdot \mathbf {{\kapelusz {b}}_{t:T}} (i) }$

Aby to zrozumieć, zauważamy, że $T$$w$ prawdopodobieństwo zaobserwowania danych zdarzeń w sposób przechodzący przez stan t. To prawdopodobieństwo obejmuje prawdopodobieństwa naprzód obejmujące wszystkie zdarzenia do czasu t, jak również prawdopodobieństwa wsteczne, które obejmują wszystkie przyszłe zdarzenia. 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 ${\ Displaystyle X_ {t} = x_ {i} }$ . Wartości te są czasami nazywane „wartościami wygładzonymi”, ponieważ łączą prawdopodobieństwo do przodu i do tyłu w celu obliczenia ostatecznego prawdopodobieństwa.

Wartości $zapewniają$ stanie w czasie t. Jako takie są przydatne do określenia najbardziej prawdopodobnego stanu w dowolnym momencie. Termin „stan najbardziej prawdopodobny” jest nieco niejednoznaczny. Podczas gdy najbardziej prawdopodobny stan jest najbardziej prawdopodobny w danym punkcie, sekwencja indywidualnie prawdopodobnych stanów prawdopodobnie nie będzie najbardziej prawdopodobną sekwencją. 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, a zatem możliwe jest uzyskanie stanów 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. ${\ 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 })}$ . Najbardziej prawdopodobną sekwencję stanów, która wygenerowała sekwencję obserwacji, można znaleźć za pomocą algorytmu Viterbiego .

Przykład

Ten przykład opiera się na świecie parasoli w Russell & Norvig 2010, rozdział 15, s. 567, w którym chcielibyśmy wywnioskować pogodę na podstawie obserwacji innej osoby niosącej lub nie noszącej parasola. Przyjmujemy dwa możliwe stany pogody: stan 1 = deszcz, stan 2 = brak deszczu. Zakładamy, że pogoda ma 70% szans na pozostanie taką samą każdego dnia i 30% szans na zmianę. Prawdopodobieństwa przejścia wynoszą wtedy:

${\ Displaystyle \ mathbf {T} = {\ początek {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ą określone 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órą w naszych obliczeniach będziemy reprezentować jako:

${\ Displaystyle \ ma thbf {O_{1}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{2}} ={\begin{pmatrix}0.9&0.0 \\0.0&0.2\end{pmatrix}}~~\mathbf {O_{3}} ={\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}~~\mathbf { O_{4}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{5}} ={\begin{pmatrix}0.9&0.0\ \0.0&0.2\end{pmacierz}}}$

$,$ że różni się od innych obserwacją „bez parasola”

Przy obliczaniu prawdopodobieństwa naprzód zaczynamy od:

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

który jest naszym wektorem stanu poprzedniego 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 są następnie zapisywane w postaci:

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

zamiast:

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

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

${\ Displaystyle (\ ma thbf {{ \hat {f}}_{0:1}} )^{T}=c_{1}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}} {\begin{pmatrix}0,7&0,3\\0,3&0,7\end{pmatrix}}{\begin{pmatrix}0,5000\\0,5000\end{pmatrix}}=c_{1}^{-1}{\ początek{pmacierz}0,4500\\0,1000\koniec{pmacierz}}={\rozpoczęcie{pmacierz}0,8182\\0,1818\koniec{pmacierz}}}$

$0,8834 \\ 0.1166 \ end {pmatrix}}$

${\ Displaystyle (\ mathbf {{\ kapelusz {f}} _ {0:2}}) ^ {T} =c_{2}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&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$

${\ Displaystyle (\ mathbf {{\ kapelusz {f}} _ {0: 3}}) ^ {T} = c_ {3} ^ {- 1} {\ rozpocząć {pmatrix} 0,1 i 0 .0\\0.0&0.8\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&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 {{{ \kapelusz {f }}_{0:4}} )^{T}=c_{4}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{ pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}=c_{4}^{-1}{\begin{pmatrix} 0,3386\\0,1247\end{pmacierz}}={\begin{pmacierz}0,7308\\0,2692\end{pmacierz}}}$

${\ Displaystyle (\ mathbf {{\ kapelusz {f}} _ {0: 5}}) ^ {T} = c_ {5 }^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&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{pmacierz}}}$

Dla prawdopodobieństw wstecznych zaczynamy od:

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

Jesteśmy wtedy w stanie obliczyć (wykorzystując obserwacje w odwrotnej kolejności i normalizując z różnymi stałymi):

${\ Displaystyle \ mathbf {{\ kapelusz {b} }_{4 :5}} =\alpha {\begin{pmatrix}0,7&0,3\\0,3&0,7\end{pmatrix}}{\begin{pmatrix}0,9&0,0\\0,0&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 {{{ \kapelusz {b} }_{3:5}} =\alpha {\begin{pmatrix}0,7&0,3\\0,3&0,7\end{pmatrix}}{\begin{pmatrix}0,9&0,0\\0,0&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{pmacierz}}}$

${\ styl wyświetlania \mathbf {{\ kapelusz {b}}_{2:5}} =\alpha {\początek{pmatrix}0,7&0,3\\0,3&0,7\koniec{pmatrix}}{\początek{pmatrix}0,1&0,0\\0,0 &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&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0. 0\\0.0&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 {{\ kapelusz {b}} _ {0: 5}} = \ alfa {\ początek {pmatrix} 0,7 i 0,3 \\ 0,3 i 0,7 \ koniec {pmatrix}} {\ początek {pmatrix} 0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}=\alpha {\begin{pmatrix}0.3976\\0.2170\end{pmatrix} }={\begin{pmacierz}0,6469\\0,3531\koniec{pmacierz}}}$

Na koniec obliczymy wygładzone wartości prawdopodobieństwa. Wyniki te muszą być również przeskalowane, aby suma wpisów wynosiła 1, ponieważ nie skalowaliśmy wstecznych prawdopodobieństw $.$ znalezionymi Powyższe wektory wstecznego prawdopodobieństwa reprezentują zatem prawdopodobieństwo każdego stanu w czasie t, biorąc pod uwagę przyszłe obserwacje. Ponieważ te wektory są proporcjonalne do rzeczywistych prawdopodobieństw wstecznych, wynik musi zostać przeskalowany o dodatkowy czas.

${\ Displaystyle (\ mathbf {\ gamma _ {0}}) ^ {T} = \ alfa {\ rozpocząć {pmatrix} 0,5000\\0,5000\koniec {pmatrix}}\circ {\begin{pmatrix}0,6469\\0,3531\end{pmatrix}}=\alpha {\zacząć{pmatrix}0,3235\\0,1765\end{pmatrix} }={\begin{pmacierz}0,6469\\0,3531\end{pmacierz}}}$

${\ 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} = \ alfa {\ rozpocząć {pmatrix} 0,8834 \\ 0,1166 \ koniec {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 \ koniec {pmatrix}}}$

${\ Displaystyle (\ mathbf {\ gamma _ {\ 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{pmacierz}}={\begin{pmacierz}0,3075\\0,6925\end{pmacierz}}} ($

${\ Displaystyle (\ mathbf {\ gamma _ {4}}) ^ {T} = \ alfa {\ rozpocząć {pmatrix} 0,7308 \\ 0,2692 \ koniec {pmatrix}} \ circ {\ rozpocząć { 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} = \ alfa {\ rozpocząć{pmatrix}0,8673\\0,1327\koniec{pmatrix}}\circ {\rozpocząć{pmatrix}1,0000\\1,0000\end{pmatrix}}=\alpha {\zacząć{pmatrix}0,8673\\0,1327\end{pmatrix} }={\begin{pmacierz}0,8673\\0,1327\koniec{pmacierz}}}$

Zauważ , że wartość jest równa $5}}}$$mathbf {{\ kapelusz {b}} _ {0$${\ Displaystyle \ mathbf {\ gamma _ {5}}}$ jest równe ${\ Displaystyle \ mathbf {{\ kapelusz {f}} _ {0: 5}}}$ . Wynika to naturalnie, ponieważ zarówno , $}} _ { 0:5}} }$ b $\ Displaystyle \ mathbf {{\ kapelusz$ rozpocznij od jednakowych priorytetów względem wektorów stanu początkowego i końcowego (odpowiednio) i weź pod uwagę wszystkie obserwacje. Jednak ${\ Displaystyle \ mathbf {{\ kapelusz {b}} _ {0: 5}}}$ będzie równy ${\ Displaystyle \ mathbf {{\ kapelusz {b}} _ {0: 5}}}$ wektor stanu reprezentuje jednolity przeor (tzn. wszystkie wpisy są sobie równe). Gdy $początkowy$ jest, połączyć z wektorem stanu początkowego, aby znaleźć najbardziej prawdopodobny stan Stwierdzamy zatem, że same prawdopodobieństwa naprzód są wystarczające do obliczenia najbardziej prawdopodobnego stanu końcowego. Podobnie, wsteczne prawdopodobieństwa można połączyć z wektorem stanu początkowego, aby uzyskać najbardziej prawdopodobny stan początkowy, biorąc pod uwagę obserwacje. Prawdopodobieństwa do przodu i do tyłu należy tylko połączyć, aby wywnioskować najbardziej prawdopodobne stany między punktami początkowymi i końcowymi.

Z powyższych obliczeń wynika, że ​​najbardziej prawdopodobnym stanem pogody każdego dnia poza trzecim był „deszcz”. Mówią nam jednak więcej, ponieważ teraz zapewniają sposób ilościowego określenia prawdopodobieństw każdego stanu w różnych momentach. Być może najważniejsze, nasza wartość w $określa ilościowo$ wiedzę o wektorze stanu na końcu sekwencji obserwacji Możemy następnie wykorzystać to do przewidywania prawdopodobieństwa wystąpienia różnych stanów pogodowych jutro, a także prawdopodobieństwa zaobserwowania parasola.

Wydajność

Algorytm do przodu i do tyłu działa ze złożonością czasową $)}$ przestrzeni, gdzie $O (S ^ {2}$$Displaystyle$$} to$$to$ sekwencji czasowej, a liczba symboli w alfabecie państwowym. Algorytm może również działać w stałej przestrzeni ze $złożonością$ . Dla porównania, procedura brutalnej ${\ Displaystyle O (T \ cdot S ^ {T})}$ wygenerowałaby wszystkie możliwe sekwencje $prawdopodobieństwo$ każdej sekwencji stanów z obserwowaną serią 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 bardzo wysoka.

Ulepszenie ogólnego algorytmu do przodu i do tyłu, zwane algorytmem wyspy , zamienia mniejsze zużycie pamięci na dłuższy czas działania, biorąc ${\ Displaystyle O (S ^ {2} T \ log T)}$ czas i pamięć ${\ Displaystyle O (S ^ {2} \ log T)} . Ponadto możliwe jest$$^ {2} T)}$ modelu procesu w celu uzyskania S 2 $S$ odwrócony proces może nie istnieć lub być źle uwarunkowany .

Ponadto opracowano algorytmy do wydajnego obliczania $poprzez wygładzanie online$ ze stałym opóźnieniem (FLS

Pseudo kod

    
     

     
        
          wejście  algorytmu  forward_backward  :  zgadnijState int  sekwencjaIndexwyjście  :  wynik  jeśli  sekwencjaIndeks  jest poza końcem sekwencji  następnie  zwróć  1  jeśli  (  zgadnijState  ,  sekwencjaIndex  ) był widziany wcześniej  to  zwróć  zapisany wynik  wynik  := 0  dla każdego  sąsiedniego stanu n:  wynik  := wynik + (prawdopodobieństwo przejścia z  GuessState  do n danego elementu obserwacji w  sekwencjiIndex  ) × Backward(n,  sekwencjaIndex  + 1) zapisz wynik dla (  GuessState  ,  sekwencjaIndex  )  zwróć  wynik 

Przykład Pythona

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

   
  
 
    
 
     
 
  
          
          
   
 
  
          
          
    stany  =  (  'Zdrowy'  ,  'Gorączka'  )  stan_końcowy  =  'E'  obserwacje  =  (  'normalny'  ,  'zimny'  ,  'zawroty głowy'  )  prawdopodobieństwo_początkowe  =  {  'Zdrowy'  :  0,6  ,  'Gorączka'  :  0,4  }  prawdopodobieństwo_przejścia  =  {  ' Zdrowy”  :  {  „Zdrowy”  :  0,69  ,  „Gorączka”  :  0,3  ,  „E”  :  0,01  },  „Gorączka”  :  {  „Zdrowy”  :  0,4  ,  „  Gorączka”  :  0,59  ,  „  E”  :  0,01  },  }  {  „Zdrowy”  :  {  „normalny”  :  0,5  ,  „zimny”  :  0,4  ,  „zawroty głowy”  :  0,1  },  „Gorączka”  :  {  „normalny”  :  0,1  ,  „zimny”  :  0,3  ,  „zawroty głowy”  :  0,6  },  } 

Implementację algorytmu forward-backward możemy napisać w następujący sposób:

      
    
    
      
        
          
           
               0
                
                  
            
                        

                

        
          

            

    
      
          
          
           
               0
                
                  
            
                          

        0
          

        0      

    
      
       
                 

       
        def  fwd_bkw  (  obserwacje  ,  stany  ,  próba_początkowa  ,  trans_prob  ,  próba_emm  ,  końcówka  ):  """Algorytm przód-tył."""  # Część naprzód algorytmu  fwd  =  []  dla  i  ,  obserwacja_i  in  enumerate  (  obserwacje  ):  f_bieżąca  =  { }  dla  st  w  stanach  :  if  i  ==  :  # przypadek bazowy dla części forward  prev_f_sum  =  start_prob  [  st  ]  else  :  prev_f_sum  =  sum  (  f_prev  [  k  ]  *  trans_prob  [  k  ][  st  ]  dla  k  w  stanach  )  f_curr  [  st  ]  =  emm_prob  [  st  ][  obserwacja_i  ]  *  prev_f_sum  fwd  .  append  (  f_curr  )  f_prev  =  f_curr  p_fwd  =  sum  (  f_curr  [  k  ]  *  trans_prob  [  k  ][  end_st  ]  dla  k  w  stanach  )  # Część wsteczna algorytmu  bkw  =  [ ]  dla  i  ,  obserwacja_i_plus  w  wyliczeniu  (  odwrócona  (  obserwacje  [  1  :]  +  (  Brak  ,))):  b_curr  =  {}  dla  st  w  stanach  :  if  i  ==  :  # przypadek bazowy dla części wstecz  b_curr  [  st  ]  =  trans_prob  [  st  ][  end_st  ]  else  :  b_curr  [  st  ]  =  suma  (  trans_prob  [  st  ][  l  ]  *  emm_prob  [  l  ][  obserwacja_i_plus  ]  *  b_prev  [  l  ]  dla  l  w  stanach  )  bkw  .  insert  (  ,  b_curr  )  b_prev  =  b_curr  p_bkw  =  sum  (  start_prob  [  l  ]  *  emm_prob  [  l  ][  obserwacje  [  ]]  *  b_curr  [  l  ]  dla  l  w  stanach  )  # Scalanie dwóch części  posterior  =  []  dla  i  w  zakresie  (  len  (  obserwacje  )):  tylne  .  dołącz  ({  st  :  fwd  [  i  ][  st  ]  *  bkw  [  i  ][  st  ]  /  p_fwd  dla  st  w  stanach  })  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'] ; stany to zbiór stanów ukrytych; a_0 jest prawdopodobieństwem startu; a to prawdopodobieństwa przejścia; a e to prawdopodobieństwa emisji.

Dla uproszczenia kodu zakładamy, że sekwencja obserwacji x nie jest pusta oraz że a[i][j] oraz e[i][j] są zdefiniowane dla wszystkich stanów i,j.

W poniższym przykładzie algorytm do przodu i do tyłu jest używany w następujący sposób:

 
     
                   
                   
                   
                   
                    def  przykład  ():  return  fwd_bkw  (  obserwacje  ,  stany  ,  prawdopodobieństwo_początku  ,  prawdopodobieństwo_przejściowe  ,  prawdopodobieństwo_emisji  ,  stan_końcowy  ) 

   
    



 >>>  dla  linii  w  przykładzie  ():  ...  print  (  *  line  )  ...  {'Zdrowy': 0,3, 'Gorączka': 0,04000000000000001} {'Zdrowy': 0,0892, 'Gorączka': 0,03408} {'Zdrowy ': 0,007518, 'Gorączka': 0,0281203199999999997}  {'Zdrowy': 0,0010418399999999998, 'Gorączka': 0,00109578} {'Zdrowy': 0,00249, 'Gorączka': 0,00394} {'Wyzdrowienie twój': 0,01, 'Gorączka': 0,01}  { 'Zdrowy': 0,8770110375573259, 'Gorączka': 0,1229889624426741} {'Zdrowy': 0,623228030950954, 'Gorączka': 0,3767719690490461} {'Zdrowy': 0,2109527 048413057, „Gorączka”: 0,7890472951586943} 

Zobacz też

• Algorytm Bauma-Welcha
• Algorytm Viterbiego
• Algorytm BCJR

• Lawrence R. Rabiner , Samouczek dotyczący ukrytych modeli Markowa i wybranych zastosowań w rozpoznawaniu mowy. Proceedings of the 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.
•   Eugeniusza Charniaka (1993). Statystyczna nauka języków . Cambridge, Massachusetts: MIT Press. ISBN 978-0-262-53141-2 .
•   Stuarta Russella i Petera Norviga (2010). Sztuczna inteligencja Nowoczesne podejście 3. wydanie . Upper Saddle River, New Jersey: Pearson Education/Prentice-Hall. ISBN 978-0-13-604259-4 .

Linki zewnętrzne

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