Algoritmus vpřed - vzad - Forward–backward algorithm

Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale její zdroje zůstávají nejasné, protože jí chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Dubna 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

The algoritmus dopředu-dozadu je odvození algoritmus pro skryté Markovovy modely který počítá zadní marginální ze všech proměnných skrytého stavu s posloupností pozorování / emisí ${displaystyle o_ {1: T}: = o_ {1}, tečky, o_ {T}}$, tj. počítá pro všechny skryté stavové proměnné ${displaystyle X_ {t} v {X_ {1}, tečky, X_ {T}}}$, distribuce ${displaystyle P (X_ {t} | o_ {1: T})}$. Tento úkol odvození se obvykle nazývá vyhlazení. Algoritmus využívá principu dynamické programování efektivně vypočítat hodnoty, které jsou nutné k získání zadního okrajového rozdělení ve dvou průchodech. První průchod jde vpřed v čase, zatímco druhý přejde zpět v čase; odtud název algoritmus dopředu-dozadu.

Termín algoritmus dopředu-dozadu se také používá k označení jakéhokoli algoritmu patřícího do obecné třídy algoritmů, které fungují na sekvenčních modelech dopředu a dozadu. V tomto smyslu popisy ve zbývající části tohoto článku odkazují, ale na jednu konkrétní instanci této třídy.

Přehled

V prvním průchodu algoritmus dopředu-dozadu vypočítá sadu pravděpodobností dopředu, která poskytuje pro všechny ${displaystyle tin {1, dots, T}}$, pravděpodobnost, že skončíte v kterémkoli konkrétním stavu vzhledem k prvnímu ${displaystyle t}$ pozorování v pořadí, tj. ${displaystyle P (X_ {t} | o_ {1: t})}$. Ve druhém průchodu algoritmus vypočítá sadu zpětných pravděpodobností, které poskytují pravděpodobnost pozorování zbývajících pozorování daného libovolného počátečního bodu ${displaystyle t}$, tj. ${displaystyle P (o_ {t + 1: T} | X_ {t})}$. Tyto dvě sady rozdělení pravděpodobnosti lze poté zkombinovat a získat rozdělení po stavech v jakémkoli konkrétním časovém okamžiku vzhledem k celé sledované posloupnosti:

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

Poslední krok vyplývá z aplikace Bayesovo pravidlo a podmíněná nezávislost z ${displaystyle o_ {t + 1: T}}$ a ${displaystyle o_ {1: t}}$ daný ${displaystyle X_ {t}}$.

Jak je uvedeno výše, algoritmus zahrnuje tři kroky:

1. výpočet pravděpodobností vpřed
2. výpočet zpětných pravděpodobností
3. výpočet vyhlazených hodnot.

Kroky vpřed a vzad lze také nazvat „předat předání zprávy“ a „předat zpětnou zprávu“ - tyto pojmy jsou způsobeny předávání zpráv používá se obecně šíření víry přístupy. Při každém jednotlivém pozorování v pořadí se počítají pravděpodobnosti, které se mají použít pro výpočty při příštím pozorování. Krok vyhlazení lze vypočítat současně během zpětného průchodu. Tento krok umožňuje algoritmu zohlednit veškerá minulá pozorování výstupu pro výpočet přesnějších výsledků.

Algoritmus dopředu-dozadu lze použít k nalezení nejpravděpodobnějšího stavu pro jakýkoli časový bod. Nelze jej však použít k nalezení nejpravděpodobnějšího sledu stavů (viz Viterbiho algoritmus ).

Pravděpodobnosti vpřed

Následující popis použije spíše matice hodnot pravděpodobnosti než rozdělení pravděpodobnosti, ačkoli obecně lze algoritmus dopředu-dozadu použít na spojité i diskrétní modely pravděpodobnosti.

Transformujeme rozdělení pravděpodobnosti související s daným skrytý Markovův model do maticového zápisu následovně. Pravděpodobnosti přechodu ${displaystyle mathbf {P} (X_ {t} střední X_ {t-1})}$ dané náhodné proměnné ${displaystyle X_ {t}}$ představující všechny možné stavy ve skrytém Markovově modelu bude reprezentováno maticí ${displaystyle mathbf {T}}$ kde index sloupce ${displaystyle j}$ bude představovat cílový stav a index řádku ${displaystyle i}$ představuje počáteční stav. Přechod ze stavu řádek-vektor ${displaystyle mathbf {pi _ {t}}}$ do stavu přírůstkového vektoru řádků ${displaystyle mathbf {pi _ {t + 1}}}$ je psán jako ${displaystyle mathbf {pi _ {t + 1}} = mathbf {pi _ {t}} mathbf {T}}$. Níže uvedený příklad představuje systém, kde je pravděpodobnost, že po každém kroku zůstanete ve stejném stavu, 70% a pravděpodobnost přechodu do jiného stavu je 30%. Matice přechodu je pak:

${displaystyle mathbf {T} = {egin {pmatrix} 0,7 & 0,3 0,3 & 0,7end {pmatrix}}}$

V typickém Markovově modelu bychom vynásobili stavový vektor touto maticí, abychom získali pravděpodobnosti pro následující stav. Ve skrytém Markovově modelu je stav neznámý a místo toho pozorujeme události spojené s možnými stavy. Matice událostí formuláře:

${displaystyle mathbf {B} = {egin {pmatrix} 0,9 & 0,1 0,2 & 0,8end {pmatrix}}}$

poskytuje pravděpodobnosti pro pozorování událostí daného stavu. Ve výše uvedeném příkladu bude událost 1 pozorována 90% času, pokud jsme ve stavu 1, zatímco událost 2 má 10% pravděpodobnost výskytu v tomto stavu. Naproti tomu událost 1 bude pozorována pouze 20% času, pokud jsme ve stavu 2 a událost 2 má 80% pravděpodobnost výskytu. Vzhledem k libovolnému řádkovému vektoru popisujícímu stav systému (${displaystyle mathbf {pi}}$), pravděpodobnost pozorování události j je pak:

${displaystyle mathbf {P} (O = j) = součet _ {i} pi _ {i} B_ {i, j}}$

Pravděpodobnost daného stavu vedoucího k pozorované události j lze vyjádřit v maticové podobě vynásobením stavového vektoru řádku (${displaystyle mathbf {pi}}$) s pozorovací maticí (${displaystyle mathbf {O_ {j}} = mathrm {diag} (B _ {*, o_ {j}})}$) obsahující pouze diagonální položky. Pokračováním výše uvedeného příkladu by pozorovací matice pro událost 1 byla:

${displaystyle mathbf {O_ {1}} = {egin {pmatrix} 0,9 & 0,0 0,0 & 0,2end {pmatrix}}}$

To nám umožňuje vypočítat nový vektor stavu nenormalizovaných pravděpodobností ${displaystyle mathbf {pi '}}$ podle Bayesova pravidla, váženo podle pravděpodobnosti, že každý prvek ${displaystyle mathbf {pi}}$ vygenerovaná událost 1 jako:

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

Nyní můžeme tento obecný postup učinit specifickým pro naši sérii pozorování. Za předpokladu vektoru počátečního stavu ${displaystyle mathbf {pi} _ {0}}$, (který lze optimalizovat jako parametr opakováním postupu vpřed-zpět), začneme s ${displaystyle mathbf {f_ {0: 0}} = mathbf {pi} _ {0}}$, poté aktualizaci rozdělení stavu a vážení podle pravděpodobnosti prvního pozorování:

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

Tento proces lze převést na další pozorování pomocí:

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

Tato hodnota je dopředný nenormalizovaný vektor pravděpodobnosti. I-ta položka tohoto vektoru poskytuje:

${displaystyle mathbf {f_ {0: t}} (i) = mathbf {P} (o_ {1}, o_ {2}, tečky, o_ {t}, X_ {t} = x_ {i} | mathbf {pi } _ {0})}$

Typicky budeme normalizovat vektor pravděpodobnosti v každém kroku tak, aby jeho položky součtu byly 1. Faktor měřítka je tedy zaveden v každém kroku tak, že:

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

kde ${displaystyle mathbf {{hat {f}} _ {0: t-1}}}$ představuje zmenšený vektor z předchozího kroku a ${displaystyle c_ {t}}$ představuje faktor měřítka, který způsobí, že výsledné vektorové položky se sečtou na 1. Produktem faktorů měřítka je celková pravděpodobnost pozorování daných událostí bez ohledu na konečné stavy:

${displaystyle mathbf {P} (o_ {1}, o_ {2}, tečky, o_ {t} | mathbf {pi} _ {0}) = prod _ {s = 1} ^ {t} c_ {s}}$

To nám umožňuje interpretovat zmenšený vektor pravděpodobnosti 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}, tečky, o_ {t}, X_ {t} = x_ {i} | mathbf {pi} _ {0}) } {mathbf {P} (o_ {1}, o_ {2}, tečky, o_ {t} | mathbf {pi} _ {0})}} = mathbf {P} (X_ {t} = x_ {i} | o_ {1}, o_ {2}, tečky, o_ {t}, mathbf {pi} _ {0})}$

Zjistili jsme tedy, že součin škálovacích faktorů nám poskytuje celkovou pravděpodobnost pozorování dané posloupnosti až do času t a že škálovaný pravděpodobnostní vektor nám poskytuje pravděpodobnost, že v tuto chvíli budeme v každém stavu.

Zpětné pravděpodobnosti

Podobný postup lze zkonstruovat k nalezení zpětných pravděpodobností. Jejich cílem je poskytnout pravděpodobnosti:

${displaystyle mathbf {b_ {t: T}} (i) = mathbf {P} (o_ {t + 1}, o_ {t + 2}, tečky, o_ {T} | X_ {t} = x_ {i} )}$

To znamená, že nyní chceme předpokládat, že začínáme v určitém stavu (${displaystyle X_ {t} = x_ {i}}$) a nyní nás zajímá pravděpodobnost pozorování všech budoucích událostí z tohoto stavu. Vzhledem k tomu, že počáteční stav je považován za daný (tj. Předchozí pravděpodobnost tohoto stavu = 100%), začneme s:

${displaystyle mathbf {b_ {T: T}} = [1 1 1 tečky] ^ {T}}$

Všimněte si, že nyní používáme vektor sloupce, zatímco pravděpodobnosti dopředu používají vektory řádků. Poté můžeme pracovat zpět pomocí:

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

I když bychom mohli tento vektor také normalizovat tak, aby jeho položky byly součtem jednoho, obvykle se to nedělá. Všimněte si, že každá položka obsahuje pravděpodobnost posloupnosti budoucích událostí daných konkrétním počátečním stavem, normalizace tohoto vektoru by byla ekvivalentní použití Bayesovy věty k nalezení pravděpodobnosti každého počátečního stavu vzhledem k budoucím událostem (za předpokladu jednotných priorit pro vektor konečného stavu ). Je však běžnější škálovat tento vektor pomocí stejného ${displaystyle c_ {t}}$ konstanty použité ve výpočtech pravděpodobnosti dopředu. ${displaystyle mathbf {b_ {T: T}}}$ není zmenšen, ale následné operace používají:

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

kde ${displaystyle mathbf {{hat {b}} _ {t: T}}}$ představuje předchozí, zmenšený vektor. Tento výsledek je ten, že zmenšený vektor pravděpodobnosti souvisí se zpětnými pravděpodobnostmi:

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

To je užitečné, protože nám umožňuje zjistit celkovou pravděpodobnost, že se v daném čase, t, ocitnete v každém stavu, vynásobením těchto hodnot:

${displaystyle mathbf {gamma _ {t}} (i) = mathbf {P} (X_ {t} = x_ {i} | o_ {1}, o_ {2}, tečky, o_ {T}, mathbf {pi} _ {0}) = {frac {mathbf {P} (o_ {1}, o_ {2}, tečky, o_ {T}, X_ {t} = x_ {i} | mathbf {pi} _ {0}) } {mathbf {P} (o_ {1}, o_ {2}, tečky, 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)}$

Abychom tomu porozuměli, poznamenáváme to ${displaystyle mathbf {f_ {0: t}} (i) cdot mathbf {b_ {t: T}} (i)}$ poskytuje pravděpodobnost pozorování daných událostí způsobem, který prochází stavem ${displaystyle x_ {i}}$ v čase t. Tato pravděpodobnost zahrnuje pravděpodobnosti dopředu pokrývající všechny události až do času t i zpětné pravděpodobnosti, které zahrnují všechny budoucí události. Toto je čitatel, který hledáme v naší rovnici, a vydělíme celkovou pravděpodobností sledované sekvence, abychom tuto hodnotu normalizovali a získali pouze pravděpodobnost, že ${displaystyle X_ {t} = x_ {i}}$. Tyto hodnoty se někdy nazývají „vyhlazené hodnoty“, protože kombinují pravděpodobnosti dopředu a dozadu a vypočítají konečnou pravděpodobnost.

Hodnoty ${displaystyle mathbf {gamma _ {t}} (i)}$ tak poskytněte pravděpodobnost, že budete v každém stavu v čase t. Jako takové jsou užitečné pro stanovení nejpravděpodobnějšího stavu kdykoli. Pojem „nejpravděpodobnější stav“ je poněkud nejednoznačný. I když je nejpravděpodobnější stav v daném bodě nejpravděpodobnější, sekvence jednotlivě pravděpodobných stavů pravděpodobně nebude nejpravděpodobnější posloupností. Je to proto, že pravděpodobnosti pro každý bod se počítají nezávisle na sobě. Nezohledňují pravděpodobnosti přechodu mezi stavy, a je tedy možné získat stavy ve dvou okamžicích (t at + 1), které jsou v těchto časových bodech nejpravděpodobnější, ale které mají velmi malou pravděpodobnost společného výskytu, tj. ${displaystyle mathbf {P} (X_ {t} = x_ {i}, X_ {t + 1} = x_ {j}) eq mathbf {P} (X_ {t} = x_ {i}) mathbf {P} ( X_ {t + 1} = x_ {j})}$. Nejpravděpodobnější posloupnost stavů, které vyprodukovaly sledovací sekvenci, lze najít pomocí Viterbiho algoritmus.

Příklad

Tento příklad vychází ze zastřešujícího světa Russell & Norvig 2010 Kapitola 15, str. 567 ve kterém bychom chtěli odvodit počasí dané pozorováním jiné osoby, která má nebo nemá deštník. Předpokládáme dva možné stavy počasí: stav 1 = déšť, stav 2 = žádný déšť. Předpokládáme, že počasí má každý den 70% šanci zůstat stejné a 30% šanci na změnu. Pravděpodobnosti přechodu jsou pak:

${displaystyle mathbf {T} = {egin {pmatrix} 0,7 & 0,3 0,3 & 0,7end {pmatrix}}}$

Předpokládáme také, že každý stát generuje jednu ze dvou možných událostí: událost 1 = deštník, událost 2 = žádný deštník. Podmíněné pravděpodobnosti pro tyto vyskytující se v každém stavu jsou dány maticí pravděpodobnosti:

${displaystyle mathbf {B} = {egin {pmatrix} 0,9 & 0,1 0,2 & 0,8end {pmatrix}}}$

Následně sledujeme následující sled událostí: {deštník, deštník, žádný deštník, deštník, deštník}, který ve svých výpočtech představíme jako:

${displaystyle mathbf {O_ {1}} = {egin {pmatrix} 0,9 & 0,0 0,0 & 0,2end {pmatrix}} ~~ mathbf {O_ {2}} = {egin {pmatrix} 0,9 & 0,0 0,0 & 0 .2end {pmatrix}} ~~ mathbf {O_ {3}} = {egin {pmatrix} 0,1 & 0,0 0,0 & 0,8end {pmatrix}} ~~ mathbf {O_ {4}} = {egin {pmatrix} 0,9 & 0,0 0,0 & 0,2end {pmatrix}} ~~ mathbf {O_ {5}} = {egin {pmatrix} 0,9 & 0,0 0,0 & 0,2end {pmatrix}}}$

Všimněte si, že ${displaystyle mathbf {O_ {3}}}$ se od ostatních liší pozorováním „bez deštníku“.

Při výpočtu pravděpodobností dopředu začínáme:

${displaystyle mathbf {f_ {0: 0}} = {egin {pmatrix} 0,5 & 0,5end {pmatrix}}}$

což je náš předchozí stavový vektor, který naznačuje, že před našimi pozorováními nevíme, ve kterém stavu je počasí. Zatímco stavový vektor by měl být dán jako vektor řádku, použijeme transpozici matice, aby bylo možné číst níže uvedené výpočty. Naše výpočty jsou poté psány ve formě:

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

namísto:

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

Všimněte si, že transformační matice je také transponována, ale v našem příkladu je transpozice stejná jako původní matice. Provedení těchto výpočtů a normalizace výsledků poskytuje:

${displaystyle (mathbf {{hat {f}} _ {0: 1}}) ^ {T} = c_ {1} ^ {- 1} {egin {pmatrix} 0,9 & 0,0 0,0 & 0,2end {pmatrix} } {egin {pmatrix} 0,7 & 0,3 0,3 & 0,7end {pmatrix}} {egin {pmatrix} 0,5000 0,5000end {pmatrix}} = c_ {1} ^ {- 1} {egin {pmatrix} 0,4500 0,1000 konec {pmatrix}} = {egin {pmatrix} 0,8182 0,1818end {pmatrix}}}$

${displaystyle (mathbf {{hat {f}} _ {0: 2}}) ^ {T} = c_ {2} ^ {- 1} {egin {pmatrix} 0,9 & 0,0 0,0 & 0,2end {pmatrix} } {egin {pmatrix} 0,7 & 0,3 0,3 & 0,7end {pmatrix}} {egin {pmatrix} 0,8182 0,1818end {pmatrix}} = c_ {2} ^ {- 1} {egin {pmatrix} 0,5645 0,0745 konec {pmatrix}} = {egin {pmatrix} 0,8834 0,1166end {pmatrix}}}$

${displaystyle (mathbf {{hat {f}} _ {0: 3}}) ^ {T} = c_ {3} ^ {- 1} {egin {pmatrix} 0,1 & 0,0 0,0 & 0,8end {pmatrix} } {egin {pmatrix} 0,7 & 0,3 0,3 & 0,7end {pmatrix}} {egin {pmatrix} 0,8834 0,1166end {pmatrix}} = c_ {3} ^ {- 1} {egin {pmatrix} 0,0653 0,2772 end {pmatrix}} = {egin {pmatrix} 0,1907 0,8093end {pmatrix}}}$

${displaystyle (mathbf {{hat {f}} _ {0: 4}}) ^ {T} = c_ {4} ^ {- 1} {egin {pmatrix} 0,9 & 0,0 0,0 & 0,2end {pmatrix} } {egin {pmatrix} 0,7 & 0,3 0,3 & 0,7end {pmatrix}} {egin {pmatrix} 0,1907 0,8093end {pmatrix}} = c_ {4} ^ {- 1} {egin {pmatrix} 0,3386 0,1247 end {pmatrix}} = {egin {pmatrix} 0,7308 0,2692end {pmatrix}}}$

${displaystyle (mathbf {{hat {f}} _ {0: 5}}) ^ {T} = c_ {5} ^ {- 1} {egin {pmatrix} 0,9 & 0,0 0,0 & 0,2end {pmatrix} } {egin {pmatrix} 0,7 & 0,3 0,3 & 0,7end {pmatrix}} {egin {pmatrix} 0,7308 0,2692end {pmatrix}} = c_ {5} ^ {- 1} {egin {pmatrix} 0,5331 0,0815 konec {pmatrix}} = {egin {pmatrix} 0,8673 0,1327end {pmatrix}}}$

Pro zpětné pravděpodobnosti začínáme:

${displaystyle mathbf {b_ {5: 5}} = {egin {pmatrix} 1,0 1.0end {pmatrix}}}$

Poté jsme schopni vypočítat (pomocí pozorování v opačném pořadí a normalizace s různými konstantami):

${displaystyle mathbf {{hat {b}} _ {4: 5}} = alpha {egin {pmatrix} 0,7 & 0,3 0,3 & 0,7end {pmatrix}} {egin {pmatrix} 0,9 & 0,0 0,0 & 0. 2end {pmatrix}} {egin {pmatrix} 1,0000 1,0000end {pmatrix}} = alfa {egin {pmatrix} 0,6900 0,4100end {pmatrix}} = {egin {pmatrix} 0,6273 0,3727end {pmatrix}}}$

${displaystyle mathbf {{hat {b}} _ {3: 5}} = alpha {egin {pmatrix} 0,7 & 0,3 0,3 & 0,7end {pmatrix}} {egin {pmatrix} 0,9 & 0,0 0,0 & 0. 2end {pmatrix}} {egin {pmatrix} 0,6273 0,3727end {pmatrix}} = alfa {egin {pmatrix} 0,4175 0,2215end {pmatrix}} = {egin {pmatrix} 0,6533 0,3467end {pmatrix}}}$

${displaystyle mathbf {{hat {b}} _ {2: 5}} = alpha {egin {pmatrix} 0,7 & 0,3 0,3 & 0,7end {pmatrix}} {egin {pmatrix} 0,1 & 0,0 0,0 & 0. 8end {pmatrix}} {egin {pmatrix} 0,6533 0,3467end {pmatrix}} = alfa {egin {pmatrix} 0,1289 0,2138end {pmatrix}} = {egin {pmatrix} 0,3763 0,6237end {pmatrix}}}$

${displaystyle mathbf {{hat {b}} _ {1: 5}} = alpha {egin {pmatrix} 0,7 & 0,3 0,3 & 0,7end {pmatrix}} {egin {pmatrix} 0,9 & 0,0 0,0 & 0. 2end {pmatrix}} {egin {pmatrix} 0,3763 0,6237end {pmatrix}} = alfa {egin {pmatrix} 0,2745 0,1889end {pmatrix}} = {egin {pmatrix} 0,5923 0,4077end {pmatrix}}}$

${displaystyle mathbf {{hat {b}} _ {0: 5}} = alpha {egin {pmatrix} 0,7 & 0,3 0,3 & 0,7end {pmatrix}} {egin {pmatrix} 0,9 & 0,0 0,0 & 0. 2end {pmatrix}} {egin {pmatrix} 0,5923 0,4077end {pmatrix}} = alfa {egin {pmatrix} 0,3976 0,2170end {pmatrix}} = {egin {pmatrix} 0,6469 0,3531end {pmatrix}}}$

Nakonec vypočítáme vyhlazené hodnoty pravděpodobnosti. Tyto výsledky musí být také upraveny tak, aby jeho položky součet 1, protože jsme neměli měřítko zpětných pravděpodobností s ${displaystyle c_ {t}}$je nalezen dříve. Výše uvedené vektory zpětné pravděpodobnosti tedy ve skutečnosti představují pravděpodobnost každého stavu v čase t vzhledem k budoucím pozorováním. Protože tyto vektory jsou úměrné skutečným zpětným pravděpodobnostem, musí být výsledek změněn o další čas.

${displaystyle (mathbf {gamma _ {0}}) ^ {T} = alpha {egin {pmatrix} 0,5000 0,5000end {pmatrix}} circ {egin {pmatrix} 0,6469 0,3531end {pmatrix}} = alfa {egin { pmatrix} 0,3235 0,1765end {pmatrix}} = {egin {pmatrix} 0,6469 0,3531end {pmatrix}}}$

${displaystyle (mathbf {gamma _ {1}}) ^ {T} = alfa {egin {pmatrix} 0,8182 0,1818end {pmatrix}} cir {egin {pmatrix} 0,5923 0,4077end {pmatrix}} = alfa {egin { pmatrix} 0,4846 0,0741end {pmatrix}} = {egin {pmatrix} 0,8673 0,1332end {pmatrix}}}$

${displaystyle (mathbf {gamma _ {2}}) ^ {T} = alfa {egin {pmatrix} 0,8834 0,1166end {pmatrix}} cir {egin {pmatrix} 0,3763 0,6237end {pmatrix}} = alfa {egin { pmatrix} 0,3324 0,0728end {pmatrix}} = {egin {pmatrix} 0,8204 0,1796end {pmatrix}}}$

${displaystyle (mathbf {gamma _ {3}}) ^ {T} = alfa {egin {pmatrix} 0,1907 0,8093end {pmatrix}} cir {egin {pmatrix} 0,6533 0,3467end {pmatrix}} = alfa {egin { pmatrix} 0,1246 0,2806end {pmatrix}} = {egin {pmatrix} 0,3075 0,6925end {pmatrix}}}$

${displaystyle (mathbf {gamma _ {4}}) ^ {T} = alfa {egin {pmatrix} 0,7308 0,2692end {pmatrix}} cirkus {egin {pmatrix} 0,6273 0,3727end {pmatrix}} = alfa {egin { pmatrix} 0,4584 0,1003end {pmatrix}} = {egin {pmatrix} 0,8204 0,1796end {pmatrix}}}$

${displaystyle (mathbf {gamma _ {5}}) ^ {T} = alfa {egin {pmatrix} 0,8673 0,1327end {pmatrix}} cir {egin {pmatrix} 1,0000 1,0000end {pmatrix}} = alfa {egin { pmatrix} 0,8673 0,1327end {pmatrix}} = {egin {pmatrix} 0,8673 0,1332end {pmatrix}}}$

Všimněte si, že hodnota ${displaystyle mathbf {gamma _ {0}}}$ je rovný ${displaystyle mathbf {{hat {b}} _ {0: 5}}}$ a to ${displaystyle mathbf {gamma _ {5}}}$ je rovný ${displaystyle mathbf {{hat {f}} _ {0: 5}}}$. To samozřejmě následuje, protože obojí ${displaystyle mathbf {{hat {f}} _ {0: 5}}}$ a ${displaystyle mathbf {{hat {b}} _ {0: 5}}}$ začít s uniformními prioritami nad vektory počátečního a konečného stavu (respektive) a vzít v úvahu všechna pozorování. Nicméně, ${displaystyle mathbf {gamma _ {0}}}$ se bude rovnat pouze ${displaystyle mathbf {{hat {b}} _ {0: 5}}}$ když náš vektor počátečního stavu představuje uniformní předchozí (tj. všechny položky jsou stejné). Pokud tomu tak není ${displaystyle mathbf {{hat {b}} _ {0: 5}}}$ je třeba kombinovat s vektorem počátečního stavu, abyste našli nejpravděpodobnější počáteční stav. Zjistili jsme tedy, že dopředné pravděpodobnosti samy o sobě jsou dostatečné pro výpočet nejpravděpodobnějšího konečného stavu. Podobně lze zpětné pravděpodobnosti kombinovat s vektorem počátečního stavu, aby poskytly nejpravděpodobnější počáteční stav daný pozorováním. Pravděpodobnosti dopředu a dozadu je třeba kombinovat pouze k odvození nejpravděpodobnějších stavů mezi počátečním a konečným bodem.

Výpočty výše ukazují, že nejpravděpodobnějším stavem počasí každý den kromě třetího byl „déšť“. Říkají nám víc než to, protože nyní poskytují způsob, jak kvantifikovat pravděpodobnosti každého státu v různých časech. Snad nejdůležitější je naše hodnota na ${displaystyle mathbf {gamma _ {5}}}$ kvantifikuje naše znalosti stavového vektoru na konci sledovací sekvence. To pak můžeme použít k předpovědi pravděpodobnosti různých povětrnostních stavů zítra i pravděpodobnosti pozorování deštníku.

Výkon

Algoritmus dopředu a dozadu běží s časovou složitostí ${displaystyle O (S ^ {2} T)}$ ve vesmíru ${displaystyle O (ST)}$, kde ${displaystyle T}$ je délka časové posloupnosti a ${displaystyle S}$ je počet symbolů ve státní abecedě.^[1] Algoritmus může také běžet v konstantním prostoru s časovou složitostí ${displaystyle O (S ^ {2} T ^ {2})}$ přepočítáním hodnot v každém kroku.^[2] Pro srovnání by postup hrubou silou vygeneroval vše možné ${displaystyle S ^ {T}}$ stavové posloupnosti a vypočítat společnou pravděpodobnost každé stavové posloupnosti s pozorovanou řadou událostí, které by měly časová složitost ${displaystyle O (Tcdot S ^ {T})}$. Hrubá síla je neřešitelná pro realistické problémy, protože počet možných skrytých sekvencí uzlů je obvykle extrémně vysoký.

Vylepšení obecného algoritmu dopředu-dozadu, zvaného Ostrovní algoritmus, vyměňuje menší využití paměti za delší dobu chodu ${displaystyle O (S ^ {2} Tlog T)}$ čas a ${displaystyle O (S ^ {2} log T)}$ Paměť. Dále je možné invertovat procesní model a získat tak ${displaystyle O (S)}$ prostor, ${displaystyle O (S ^ {2} T)}$ časový algoritmus, i když invertovaný proces nemusí existovat nebo být špatně podmíněný.^[3]

Kromě toho byly vyvinuty algoritmy pro výpočet ${displaystyle mathbf {f_ {0: t + 1}}}$ efektivně prostřednictvím online vyhlazování, jako je algoritmus vyhlazování s pevným zpožděním (FLS).^[4]

Pseudo kód

algoritmus dopředu Dozadu je    vstup: guessState int sequenceIndex    výstup: výsledek    -li sequenceIndex je za koncem sekvence pak        vrátit se 1    -li (guessState, sequenceIndex) byl již dříve viděn pak        vrátit se uložený výsledek výsledek := 0    pro každého sousední stát n: výsledek : = výsledek + (pravděpodobnost přechodu z guessState do n daného pozorovacího prvku v sequenceIndex) × zpět (n, sequenceIndex + 1) uložit výsledek pro (guessState, sequenceIndex)    vrátit se výsledek

Příklad Pythonu

Vzhledem k HMM (stejně jako v Viterbiho algoritmus ) zastoupené v Programovací jazyk Python:

státy = ('Zdravý', 'Horečka')konečný stav = 'E' pozorování = ('normální', 'Studený', ‚závratě ') start_probability = {'Zdravý': 0.6, 'Horečka': 0.4} pravděpodobnost přechodu = {   'Zdravý' : {'Zdravý': 0.69, 'Horečka': 0.3, 'E': 0.01},   'Horečka' : {'Zdravý': 0.4, 'Horečka': 0.59, 'E': 0.01},   } emisní_pravděpodobnost = {   'Zdravý' : {'normální': 0.5, 'Studený': 0.4, ‚závratě ': 0.1},   'Horečka' : {'normální': 0.1, 'Studený': 0.3, ‚závratě ': 0.6},   }

Můžeme napsat implementaci algoritmu dopředu a dozadu takto:

def fwd_bkw(pozorování, státy, start_prob, trans_prob, emm_prob, end_st):    "" "Algoritmus vpřed - vzad." ""    # Předaná část algoritmu    fwd = []    pro i, postřeh_i v vyjmenovat(pozorování):        f_curr = {}        pro Svatý v státy:            -li i == 0:                # základní případ pro přední část                předchozí_f_sum = start_prob[Svatý]            jiný:                předchozí_f_sum = součet(f_prev[k] * trans_prob[k][Svatý] pro k v státy)            f_curr[Svatý] = emm_prob[Svatý][postřeh_i] * předchozí_f_sum        fwd.připojit(f_curr)        f_prev = f_curr    p_fwd = součet(f_curr[k] * trans_prob[k][end_st] pro k v státy)    # Zpětná část algoritmu    bkw = []    pro i, pozorování_i_plus v vyjmenovat(obráceně(pozorování[1:] + (Žádný,))):        b_curr = {}        pro Svatý v státy:            -li i == 0:                # základní případ pro zadní část                b_curr[Svatý] = trans_prob[Svatý][end_st]            jiný:                b_curr[Svatý] = součet(trans_prob[Svatý][l] * emm_prob[l][pozorování_i_plus] * b_prev[l] pro l v státy)        bkw.vložit(0,b_curr)        b_prev = b_curr    p_bkw = součet(start_prob[l] * emm_prob[l][pozorování[0]] * b_curr[l] pro l v státy)    # Sloučení obou částí    zadní = []    pro i v rozsah(len(pozorování)):        zadní.připojit({Svatý: fwd[i][Svatý] * bkw[i][Svatý] / p_fwd pro Svatý v státy})    tvrdit p_fwd == p_bkw    vrátit se fwd, bkw, zadní

Funkce fwd_bkw trvá následující argumenty: X je sled pozorování, např. ['normální', 'studené', 'závratě']; státy je sada skrytých stavů; a_0 je pravděpodobnost spuštění; A jsou pravděpodobnosti přechodu; a E jsou emisní pravděpodobnosti.

Pro jednoduchost kódu předpokládáme, že sled pozorování X není prázdný a to a [i] [j] a e [i] [j] je definován pro všechny stavy i, j.

V běžícím příkladu se algoritmus dopředu-dozadu používá následovně:

def příklad():    vrátit se fwd_bkw(pozorování,                   státy,                   start_probability,                   pravděpodobnost přechodu,                   emisní_pravděpodobnost,                   konečný stav)

>>> pro čára v příklad():...     tisk(*čára)... {'Zdravé': 0,3, 'Horečka': 0,04000000000000001} {'Zdravé': 0,0892, 'Horečka': 0,03408} {'Zdravé': 0,007518, 'Horečka: 0,028120319999999997}{'Zdravé': 0,0010418399999999998, 'Horečka': 0,00109578} {'Zdravé': 0,00249, 'Horečka': 0,00394} {'Zdravé': 0,01, 'Horečka': 0,01}{'Zdravé': 0,8770110375573259, 'Horečka': 0,1229889624426741} {'Zdravé': 0,623228030950954, 'Horečka': 0,3767719690490461} {'Zdravé': 0,2109527048413057, 'Horečka': 0,7890472951586943}

Viz také

• Baum – Welchův algoritmus
• Viterbiho algoritmus
• Algoritmus BCJR

Reference

• Lawrence R. Rabiner, Výukový program ke skrytým Markovovým modelům a vybraným aplikacím v rozpoznávání řeči. Sborník řízení IEEE, 77 (2), str. 257–286, únor 1989. 10.1109/5.18626
• Lawrence R. Rabiner, B.H. Juang (leden 1986). "Úvod do skrytých Markovových modelů". Časopis IEEE ASSP: 4–15.
• Eugene Charniak (1993). Statistické studium jazyků. Cambridge, Massachusetts: MIT Press. ISBN  978-0-262-53141-2.
• Stuart Russell a Peter Norvig (2010). Umělá inteligence - moderní přístup, 3. vydání. Upper Saddle River, New Jersey: Pearson Education / Prentice-Hall. ISBN  978-0-13-604259-4.

externí odkazy

• Interaktivní tabulka pro výuku algoritmu dopředu a dozadu (tabulka a článek s podrobným návodem)
• Výukový program pro skryté modely Markov včetně algoritmu dopředu a dozadu
• Sbírka algoritmů AI implementovaných v Javě (včetně HMM a algoritmu dopředu-dozadu)