Forward-Reverse Algorithm

Dopředný-reverzní algoritmus je algoritmus pro výpočet zadních pravděpodobností sekvence stavů v přítomnosti sekvence pozorování. Jinými slovy, algoritmus, který počítá pravděpodobnost určité sekvence pozorování. Algoritmus je aplikován ve třech algoritmech skrytých Markovových modelů .

Přehled

Algoritmus zahrnuje tři kroky:

výpočet přímých pravděpodobností
výpočet inverzních pravděpodobností
výpočet vyhlazených hodnot

Kroky vpřed a vzad se často označují jako "přechod zprávy vpřed" a "přechod zpětné zprávy", kde zprávy jsou série po sobě jdoucích pozorování. Formulace vychází ze způsobu, jakým algoritmus zpracovává danou sekvenci pozorování. Nejprve algoritmus pokročí, počínaje prvním pozorováním v sekvenci a přejde k poslednímu a poté zpět k prvnímu. Při každém pozorování se vypočítávají pravděpodobnosti sekvencí, které se použijí pro výpočty při dalším pozorování. Během zpětného průchodu algoritmus současně provádí krok vyhlazování. Vyhlazování je proces výpočtu rozdělení pravděpodobnosti hodnot proměnných v minulých stavech, podle důkazů, až po současný stav. Tento krok umožňuje algoritmu vzít v úvahu všechna minulá pozorování za účelem výpočtu přesnějších výsledků.

Formální popis

Dále budeme za základní matici uvažovat empirickou matici pravděpodobnostních hodnot, nikoli rozdělení pravděpodobnosti. Distribuce pravděpodobnosti spojená s daným skrytým Markovovým modelem transformujeme do maticové formy následovně. Matice pravděpodobnosti přechodu (pro) danou náhodnou veličinu , reprezentující všechny možné stavy ve skrytém Markovově modelu, bude reprezentována maticí . V této matici index řádku i označuje počáteční stav a index sloupce j označuje konečný stav. Níže je například uveden systém, u kterého je pravděpodobnost setrvání ve stejném stavu po každém kroku 70 % a pravděpodobnost přechodu do jiného stavu 30 %. Potom matice pravděpodobnosti přechodu vypadá takto: $P({\mbox{X}}_{\mathrm {t} }|{\mbox{X}}_{\mathrm {t-1} })$ ${\mbox{X}}_{\mathrm {t}} }$ $T$ $T={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}$

Podobně budeme reprezentovat pravděpodobnosti nových stavů pro dané pozorované stavy uvedené jako důkaz v pozorovací matici , kde každý diagonální prvek obsahuje pravděpodobnost nového stavu daného pozorovaného stavu v čase t. Všimněte si, že t označuje konkrétní pozorování v posloupnosti pozorování. Všechny ostatní prvky v matici budou nulové. V níže uvedeném příkladu je prvním pozorovaným důkazem „deštník“. Proto by bylo definováno jako: ${\mbox{O}}_{\mathrm {t} }$ $(t=1)$ ${\mbox{O}}_{\mathrm {1} }$ $O_{1}={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}$

Na základě tohoto popisu můžeme vypočítat následující přímou pravděpodobnost. Nechť je množina přímých pravděpodobností uložena v jiné matici . Zde ukazuje, že vypočítané pravděpodobnosti závisí na všech přímých pravděpodobnostech od do , včetně aktuální maticové pravděpodobnosti, kterou popíšeme jako . Proto se rovná součinu transponované matice se současnými přímými pravděpodobnostmi a matice pozorování pro další důkazy v proudu pozorování. Poté se získá matice, která vyžaduje normalizaci, to znamená, že získané hodnoty musí být vyděleny součtem všech hodnot v matici. Normalizační faktor je specifikován pomocí α . Výpočet přímých pravděpodobností je popsán vzorcem: ${\mbox{f}}_{\mathrm {1:t+1}} }$ $1:t+1$ $jeden$ $t+1$ ${\mbox{f}}_{\mathrm {1:t} }$ ${\mbox{f}}_{\mathrm {1:t+1}} }$ ${\mbox{f}}_{\mathrm {1:t+1} }=\alpha {\mbox{O}}_{\mathrm {t+1} }T^{T}{\mbox {f}}_{\mathrm {1:t} }$

Můžeme si představit výpočet inverzní pravděpodobnosti , která začíná od konce posloupnosti podobným způsobem. Nechť je konec posloupnosti popsán indexem začínajícím na 0. Proto běh od do a výpočet každé reciproční pravděpodobnosti lze popsat následujícím vzorcem: ${\mbox{b}}_{\mathrm {k+1:t} }$ $k$ $k$ $t=0$ ${\mbox{b}}_{\mathrm {k+1:t} }=T{\mbox{O}}_{\mathrm {k+1} }{\mbox{b}}_{ \mathrm {k+2:t} }$

Všimněte si, že používáme netransponovanou matici a že se změnila hodnota prvků. Všimněte si také, že jako konečný výsledek nepoužíváme obvyklý matricový produkt, ale bodově. Tato operace vynásobí každou proměnnou v jedné matici odpovídající proměnnou v jiné. Třetím a posledním krokem je výpočet vyhlazených pravděpodobností . Vyhlazené pravděpodobnosti získané bodovým součinem Vzorec je definován jako Následující příklad je uveden níže. $T$ ${\displaystyle {\mbox{sv))_{\mathrm {k} ))$ ${\mbox{sv))_{\mathrm {k} }=\alpha {\mbox{b))_{\mathrm {k+1:t} }{\mbox{f))_{\ matematika {1:k} }$

Příklad

Na základě příkladu z Russel & Norvig 2003 strana 540. Uvažujme následující sled pozorování (deštník, deštník, bez deštníku, deštník, deštník). Předpokládejme, že pravděpodobnost deště je 90%, pokud je deštník pozorován, a 10%, pokud není pozorován deštník. Pravděpodobnost, že nebude pršet, je 20 % a 80 %. Předpokládejme také, že existuje 70% šance, že počasí zůstane stejné, a 30% šance, že se počasí změní. Následující matice převzaté ze „světa“ deštníků číselně popisují výše uvedená pozorování ${\mathbf {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{pmatrix}}~~{\mathbf {T}}={\begin{pmatrix}0.7&0.3\\0.3&0.7\ end{pmatrix}}~~{\mathbf {T^{T}}}={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}$

Než začneme počítat přímé pravděpodobnosti, musíme popsat dvě speciální proměnné, první přímou pravděpodobnost a k+2 inverzní pravděpodobnost. První dopředná pravděpodobnost v t=0 je určena antecedentem náhodné veličiny. k+2 inverzní pravděpodobnost je určena "skutečnou" maticí. Proto následuje:

${\mathbf {f_{{1:0}}}}={\begin{pmatrix}0,5\\0,5\end{pmatrix}}$

${\mathbf {b_{{k+2:t}}}}={\begin{pmatrix}1.0\\1.0\end{pmatrix}}$

Nyní budeme iterovat všechny hodnoty t a vypočítat dopředné pravděpodobnosti. Z výše popsaného přímého pravděpodobnostního vzorce získáme následující matice. Některé výpočty mohou být méně přesné kvůli omezenému počtu desetinných míst použitých v tomto příkladu.

${\mathbf {f_{{1:1}}}}=\alpha {\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}}=\alpha {\begin{pmatrix}0.4500\\0.1000\end{pmatrix}}={\begin {pmatrix}0,8182\\0,1818\end{pmatrix}}$

${\mathbf {f_{{1:2}}}}=\alpha {\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}}=\alpha {\begin{pmatrix}0.5645\\0.0745\end{pmatrix}}={\begin {pmatrix}0,8834\\0,1165\end{pmatrix}}$

${\mathbf {f_{{1:3}}}}=\alpha {\begin{pmatrix}0.1&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.1165\end{pmatrix}}=\alpha {\begin{pmatrix}0.0653\\0.2772\end{pmatrix}}={\begin {pmatrix}0.1906\\0.8093\end{pmatrix}}$

${\mathbf {f_{{1:4}}}}=\alpha {\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.1906\\0.8093\end{pmatrix}}=\alpha {\begin{pmatrix}0.3386\\0.1247\end{pmatrix}}={\begin {pmatrix}0,7308\\0,2691\end{pmatrix}}$

${\mathbf {f_{{1:5}}}}=\alpha {\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.2691\end{pmatrix}}=\alpha {\begin{pmatrix}0.5331\\0.0815\end{pmatrix}}={\begin {pmatrix}0,8673\\0,1326\end{pmatrix}}$

Nyní, když jsme určili přímé pravděpodobnosti, pokračujeme ve výpočtu inverzních pravděpodobností. Níže popsané matice získáme ze vzorce pro nalezení inverzní pravděpodobnosti, jak je popsáno výše.

${\mathbf {b_{{5:5}}}}={\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}}={\begin{pmatrix}0.5984\\0.0543\end{pmatrix}}={\begin{pmatrix}0.9168 \\0,0831\end{pmatrix}}$

${\mathbf {b_{{4:5}}}}={\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.9168\\0.0831\end{pmatrix}}={\begin{pmatrix}0.7308\\0.2691\end{pmatrix}}={\begin{pmatrix}0.8593 \\0,1407\end{pmatrix}}$

${\mathbf {b_{{3:5}}}}={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.1&0.0\\0.0 &0.8\end{pmatrix}}{\begin{pmatrix}0.8593\\0.1407\end{pmatrix}}={\begin{pmatrix}0.0178\\0.0845\end{pmatrix}}={\begin{pmatrix}0.1739 \\0,8260\end{pmatrix}}$

${\mathbf {b_{{2:5}}}}={\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.1739\\0.8260\end{pmatrix}}={\begin{pmatrix}0.1405\\0.0189\end{pmatrix}}={\begin{pmatrix}0.8814 \\0,1185\end{pmatrix}}$

${\mathbf {b_{{1:5}}}}={\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.8814\\0.1185\end{pmatrix}}={\begin{pmatrix}0.4600\\0.0462\end{pmatrix}}={\begin{pmatrix}0.9087 \\0,0912\end{pmatrix}}$

Nakonec vypočítáme vyhlazené hodnoty pravděpodobnosti. Uspořádání matic se řídí vzorcem pro výpočet vyhlazených hodnot výše.

${\mathbf {sv_{{5}}}}=\alpha {\begin{pmatrix}1.0000\\1.0000\end{pmatrix}}\times {\begin{pmatrix}0.8673\\0.1326\end{pmatrix}}= \alpha {\begin{pmatrix}0.8673\\0.1326\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1326\end{pmatrix}}$

$\mathbf {sv_{4}} =\alpha {\begin{pmatrix}0.9168\\0.0831\end{pmatrix}}\times {\begin{pmatrix}0.7308\\0.2691\end{pmatrix}}=\ alfa {\begin{pmatrix}0.6699\\0.0223\end{pmatrix}}={\begin{pmatrix}0.9677\\0.0322\end{pmatrix}}$

${\mathbf {sv_{{3}}}}=\alpha {\begin{pmatrix}0.8593\\0.1407\end{pmatrix}}\times {\begin{pmatrix}0.1906\\0.8093\end{pmatrix}}= \alpha {\begin{pmatrix}0.1637\\0.1138\end{pmatrix}}={\begin{pmatrix}0.5899\\0.4101\end{pmatrix}}$

${\mathbf {sv_{{2}}}}=\alpha {\begin{pmatrix}0.1739\\0.8260\end{pmatrix}}\times {\begin{pmatrix}0.8834\\0.1165\end{pmatrix}}= \alpha {\begin{pmatrix}0.1536\\0.0962\end{pmatrix}}={\begin{pmatrix}0.6148\\0.3852\end{pmatrix}}$

${\mathbf {sv_{{1}}}}=\alpha {\begin{pmatrix}0.8814\\0.1185\end{pmatrix}}\times {\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}= \alpha {\begin{pmatrix}0.7211\\0.0215\end{pmatrix}}={\begin{pmatrix}0.9710\\0.0289\end{pmatrix}}$

Jednodušším řešením tohoto problému je výčet všech možných sekvencí pozorovaných událostí a skrytých stavů s jejich pravděpodobnostmi pomocí dvou přechodových matic. Společná pravděpodobnost dvou sekvencí se vypočítá vynásobením příslušných pravděpodobností. Tento algoritmus má časovou složitost , kde T je délka sekvencí a N je počet symbolů v abecedě stavu. To je obtížné, protože počet možných skrytých sekvencí uzlů je obvykle extrémně vysoký. Algoritmus dopředu-dozadu má časovou složitost . Algoritmus má vylepšení, která umožňují provádět výpočty v oblasti paměti s konstantní velikostí. Kromě toho byly pro zvýšení t vyvinuty algoritmy pro efektivní výpočty pomocí online vyhlazování s pevným zpožděním, jako je vyhlazovací ( FLS ) algoritmus Russel & Norvig 2003 strana 552 $O(TN^{T})$ $O(N^{2}T)$ ${\mbox{f}}_{\mathrm {1:t+1}} }$

Aplikace

Algoritmus tam a zpět je základem výpočetních metod používaných v mnoha z těchto aplikací, které se zabývají sekvencemi hlučných pozorování od rozpoznávání řeči po radarové sledování letadel.

Pseudokód

ForwardBackward(guessState, sequenceIndex): pokud je sequenceIndex za koncem sekvence, vrátí 1 pokud (guessState, sequenceIndex) bylo vidět dříve, vrátí uložený výsledek výsledek = 0 pro každý sousední stát n: vysledek = vysledek + (pravdepodobnost prechodu ze stavu odhadu do n daného prvku pozorovani na sequenceIndex)*ForwardBackward(n, sequenceIndex+1) uložit výsledek pro (guessState, sequenceIndex) vrátit výsledek

Viz také

Odkazy

Interaktivní tabulka pro výuku dopředně-zpětného algoritmu (tabulka a článek s podrobným návodem)
Výuka skrytých Markovových modelů včetně dopředně-zpětného algoritmu
Kolekce algoritmů AI implementovaných v Javě (včetně HMM a dopředně-zpětného algoritmu)
Vyhlazení (downlink)
Skryté Markovovy modely