Algoritm înainte-înapoi

Algoritmul înainte-înapoi este un algoritm inferențial pentru modelele ascunse de Markov care calculează probabilitatea posterioară marginală a tuturor variabilelor de stare ascunse, având în vedere o succesiune de observații. $o_{1:t}:=o_{1},\dots ,o_{t}$ ${\ displaystyle o_ {1: t}: = o_ {1}, \ dots, o_ {t}}$ ${\ displaystyle o_ {1: t}: = o_ {1}, \ dots, o_ {t}}$ , adică calculează, pentru toate variabilele de stare ascunse $X_{k}\in \{X_{1},\dots ,X_{t}\}$ ${\ displaystyle X_ {k} \ in \ {X_ {1}, \ dots, X_ {t} \}}$ ${\ displaystyle X_ {k} \ in \ {X_ {1}, \ dots, X_ {t} \}}$ , distributia $P(X_{k}\ |\ o_{1:t})$ ${\ displaystyle P (X_ {k} \ | \ o_ {1: t})}$ ${\ displaystyle P (X_ {k} \ | \ o_ {1: t})}$ . Această sarcină inferențială se numește de obicei netezire . Algoritmul folosește principiul de programare dinamică în doi pași pentru a calcula în mod eficient valorile necesare pentru a obține distribuții marginale posterioare. Primul pas merge înainte în timp, în timp ce al doilea merge înapoi; de aici și numele înainte-înapoi , înainte-înapoi, al algoritmului.

Termenul algoritm înainte - înapoi este folosit ca referință la un algoritm aparținând clasei generice de algoritmi care operează pe secvențe de modele într-o manieră alternativă față de parametrul adoptat pentru evoluție, în general timp. În acest sens, restul acestei intrări se referă la algoritmul în forma sa generică și nu la un exemplu particular al acestei clase.

Prezentare generală

Ca prim pas, algoritmul înainte - înapoi calculează un set de probabilități "înainte" care oferă, pentru toți $k\in \{1,\dots ,t\}$ ${\ displaystyle k \ in \ {1, \ dots, t \}}$ ${\ displaystyle k \ in \ {1, \ dots, t \}}$ , probabilitatea de a ajunge într-o anumită stare, dată fiind prima $k$ ${\ displaystyle k}$ $k$ observații în secvență, adică $P(X_{k}\ |\ o_{1:k})$ ${\ displaystyle P (X_ {k} \ | \ o_ {1: k})}$ ${\ displaystyle P (X_ {k} \ | \ o_ {1: k})}$ . Ca un al doilea pas, algoritmul calculează un set de probabilități „înapoi” care oferă probabilitatea de a observa observațiile rămase date de un anumit punct de plecare. $k$ ${\ displaystyle k}$ $k$ , sau $P(o_{k+1:t}\ |\ X_{k})$ ${\ displaystyle P (o_ {k + 1: t} \ | \ X_ {k})}$ ${\ displaystyle P (o_ {k + 1: t} \ | \ X_ {k})}$ . Aceste două seturi de distribuții de probabilitate pot fi apoi combinate pentru a obține distribuția peste stări într-un anumit moment specific, având în vedere întreaga succesiune de observații:

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

{\ displaystyle P (X_ {k} \ | \ o_ {1: t}) = P (X_ {k} \ | \ o_ {1: k}, o_ {k + 1: t}) \ propto P (o_ {k + 1: t} \ | \ X_ {k}) P (X_ {k} \ | \ o_ {1: k})}

{\ displaystyle P (X_ {k} \ | \ o_ {1: t}) = P (X_ {k} \ | \ o_ {1: k}, o_ {k + 1: t}) \ propto P (o_ {k + 1: t} \ | \ X_ {k}) P (X_ {k} \ | \ o_ {1: k})}

unde ultimul pas rezultă din aplicarea regulii lui Bayes și din independența condiționată a $o_{k+1:t}$ ${\ displaystyle o_ {k + 1: t}}$ ${\ displaystyle o_ {k + 1: t}}$ și de $o_{1:k}$ ${\ displaystyle o_ {1: k}}$ ${\ displaystyle o_ {1: k}}$ dat $X_{k}$ ${\ displaystyle X_ {k}}$ $X_ {k}$ .

După cum sa subliniat mai sus, algoritmul implică trei pași:

calculul probabilității „înainte”
calculul probabilității înapoi
calculul valorilor esențiale sau a valorilor uniformizate , adică valori care rezumă tendința principală sau generală a setului de valori sau a unei părți a acestuia.

Pașii înainte și înapoi pot fi, de asemenea, numiți „treceți mesajul înainte” și „mesajul pas înapoi) - acești termeni sunt în general legați de trecerea mesajului utilizat în abordările de propagare a credințelor (propagarea credințelor). La fiecare observație unică în secvență, sunt calculate probabilitățile utilizate pentru calcularea următoarei observații. În timpul pasajului înapoi, se poate efectua și calculul valorilor esențiale ( pas de netezire ). Acest pas permite algoritmului să țină cont de rezultatele anterioare pentru a calcula mai precis altele noi.

Algoritmul înainte - înapoi poate fi folosit pentru a găsi starea cea mai probabilă pentru orice moment din timp. Cu toate acestea, nu poate fi folosit pentru a găsi cea mai probabilă succesiune de stări ( cf. algoritmul lui Viterbi ).

Probabilitate înainte

Următoarea descriere va folosi mai multe matrici de valori de probabilitate decât distribuții de probabilitate, deși, în general, algoritmul înainte-înapoi poate fi aplicat atât modelelor de probabilitate continue, cât și discrete.

Transformăm distribuțiile de probabilitate legate de un model Markov ascuns dat în notație matricială după cum urmează. Probabilitățile de tranziție $\mathbf {P} (X_{t}\mid X_{t-1})$ ${\ displaystyle \ mathbf {P} (X_ {t} \ mid X_ {t-1})}$ ${\ displaystyle \ mathbf {P} (X_ {t} \ mid X_ {t-1})}$ a unei variabile aleatorii date $X_{t}$ ${\ displaystyle X_ {t}}$ $X_t$ , reprezentând toate stările posibile în modelul ascuns Markov, va fi reprezentat de matrice $\mathbf {T}$ ${\ displaystyle \ mathbf {T}}$ ${\ displaystyle \ mathbf {T}}$ unde indexul rândului, i, va reprezenta starea de pornire și indexul coloanei, j, starea de sosire. Exemplul de mai jos reprezintă un sistem în care probabilitatea de a rămâne în aceeași stare după fiecare pas este de 70% și cea de tranziție la o altă stare este de 30%. Matricea de tranziție este:

\mathbf {T} ={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}

{\ displaystyle \ mathbf {T} = {\ begin {pmatrix} 0.7 & 0.3 \\ 0.3 & 0.7 \ end {pmatrix}}}

{\ displaystyle \ mathbf {T} = {\ begin {pmatrix} 0.7 & 0.3 \\ 0.3 & 0.7 \ end {pmatrix}}}

Într-un model tipic Markov am înmulți un vector de stare cu matricea de mai sus pentru a obține probabilitățile pentru stările ulterioare. Într-un model ascuns Markov starea este necunoscută și ceea ce observăm sunt evenimente asociate cu stări posibile. O matrice de evenimente a formei:

\mathbf {B} ={\begin{pmatrix}0.9&0.1\\0.2&0.8\end{pmatrix}}

{\ displaystyle \ mathbf {B} = {\ begin {pmatrix} 0.9 & 0.1 \\ 0.2 & 0.8 \ end {pmatrix}}}

{\ displaystyle \ mathbf {B} = {\ begin {pmatrix} 0.9 & 0.1 \\ 0.2 & 0.8 \ end {pmatrix}}}

oferă probabilitățile de observare a evenimentelor pornind de la o anumită stare. În exemplul anterior, evenimentul 1 va fi observat 90% din timp dacă pornim de la starea 1 în timp ce evenimentul 2 are o probabilitate de 10% să apară întotdeauna începând de la starea 1. Dimpotrivă, evenimentul 1 va fi observat doar 20% din timpul dacă pornim de la starea 2 și evenimentul 2 are o șansă de 80% să apară. Având un vector de stare ( $\mathbf {\pi }$ ${\ displaystyle \ mathbf {\ pi}}$ ${\ displaystyle \ mathbf {\ pi}}$ ), probabilitatea de a observa evenimentul j este atunci:

\mathbf {P} (O=j)=\sum _{i}\pi _{i}b_{i,j}

{\ displaystyle \ mathbf {P} (O = j) = \ sum _ {i} \ pi _ {i} b_ {i, j}}

{\ displaystyle \ mathbf {P} (O = j) = \ sum _ {i} \ pi _ {i} b_ {i, j}}

Aceasta poate fi reprezentată sub formă de matrice prin multiplicarea vectorului de stare ( $\mathbf {\pi }$ ${\ displaystyle \ mathbf {\ pi}}$ ${\ displaystyle \ mathbf {\ pi}}$ ) pentru matricea de observare ( $\mathbf {O_{1}}$ ${\ displaystyle \ mathbf {O_ {1}}}$ ${\ displaystyle \ mathbf {O_ {1}}}$ ) conținând doar elemente de-a lungul diagonalei. Fiecare element este probabilitatea evenimentului observat dat de fiecare stare. Continuând exemplul anterior, o observație a evenimentului 1 ar fi:

\mathbf {O_{1}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}

{\ displaystyle \ mathbf {O_ {1}} = {\ begin {pmatrix} 0.9 & 0.0 \\ 0.0 & 0.2 \ end {pmatrix}}}

{\ displaystyle \ mathbf {O_ {1}} = {\ begin {pmatrix} 0.9 & 0.0 \\ 0.0 & 0.2 \ end {pmatrix}}}

Aceasta permite calcularea probabilităților asociate cu trecerea la o nouă stare și observarea unui eveniment dat ca:

\mathbf {f_{0:1}} =\mathbf {\pi } \mathbf {T} \mathbf {O_{1}}

{\ displaystyle \ mathbf {f_ {0: 1}} = \ mathbf {\ pi} \ mathbf {T} \ mathbf {O_ {1}}}

{\ displaystyle \ mathbf {f_ {0: 1}} = \ mathbf {\ pi} \ mathbf {T} \ mathbf {O_ {1}}}

Vectorul de probabilitate rezultat conține elemente care indică probabilitatea de tranziție la fiecare stare, adică observarea unui eveniment dat. Acest proces poate fi urmărit în continuare cu observații suplimentare utilizând:

\mathbf {f_{0:t}} =\mathbf {f_{0:t-1}} \mathbf {T} \mathbf {O_{t}}

{\ displaystyle \ mathbf {f_ {0: t}} = \ mathbf {f_ {0: t-1}} \ mathbf {T} \ mathbf {O_ {t}}}

{\ displaystyle \ mathbf {f_ {0: t}} = \ mathbf {f_ {0: t-1}} \ mathbf {T} \ mathbf {O_ {t}}}

Această valoare este vectorul de probabilitate directă. Componenta sa i-a asigură:

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

{\ displaystyle \ mathbf {f_ {0: t}} (i) = \ mathbf {P} (o_ {1}, o_ {2}, \ dots, o_ {t}, X_ {t} = x_ {i} | \ mathbf {\ pi})}

{\ displaystyle \ mathbf {f_ {0: t}} (i) = \ mathbf {P} (o_ {1}, o_ {2}, \ dots, o_ {t}, X_ {t} = x_ {i} | \ mathbf {\ pi})}

De obicei, vectorul de probabilitate nu rămâne normalizat la fiecare pas, astfel încât componentele sale se adaugă la 1. Un factor de scală este, prin urmare, introdus la fiecare pas, astfel încât:

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

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

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

unde este $\mathbf {{\hat {f}}_{0:t-1}}$ ${\ displaystyle \ mathbf {{\ hat {f}} _ {0: t-1}}}$ ${\ displaystyle \ mathbf {{\ hat {f}} _ {0: t-1}}}$ reprezintă vectorul scalat de la pasul anterior e $c_{t}$ ${\ displaystyle c_ {t}}$ ${\ displaystyle c_ {t}}$ reprezintă factorul de scală datorită căruia componentele vectorului rezultat se adună la 1. Produsul factorilor de scală este probabilitatea totală de a observa evenimentele date indiferent de stările finale:

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

{\ displaystyle \ mathbf {P} (o_ {1}, o_ {2}, \ dots, o_ {t} | \ mathbf {\ pi}) = \ prod _ {s = 1} ^ {t} c_ {s }}

{\ displaystyle \ mathbf {P} (o_ {1}, o_ {2}, \ dots, o_ {t} | \ mathbf {\ pi}) = \ prod _ {s = 1} ^ {t} c_ {s }}

Acest lucru ne permite să interpretăm vectorul de probabilitate scalat ca:

\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 } )}{\mathbf {P} (o_{1},o_{2},\dots ,o_{t}|\mathbf {\pi } )}}=\mathbf {P} (X_{t}=x_{i}|o_{1},o_{2},\dots ,o_{t},\mathbf {\pi } )

{\ 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})} {\ mathbf {P} (o_ {1}, o_ {2}, \ dots, o_ {t} | \ mathbf {\ pi})}} = \ mathbf {P} (X_ {t} = x_ {i} | o_ {1}, o_ {2}, \ dots, o_ {t}, \ mathbf {\ pi})}

{\ 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})} {\ mathbf {P} (o_ {1}, o_ {2}, \ dots, o_ {t} | \ mathbf {\ pi})}} = \ mathbf {P} (X_ {t} = x_ {i} | o_ {1}, o_ {2}, \ dots, o_ {t}, \ mathbf {\ pi})}

Prin urmare, constatăm că produsul factorilor de scară ne oferă probabilitatea totală de a observa o secvență dată până la timpul t și că vectorul de probabilitate scalat ne oferă probabilitatea de a fi în fiecare stare în acel moment.

Probabilitate înapoi

O procedură similară poate fi construită pentru a găsi probabilități înapoi. Acestea oferă probabilitățile:

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

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

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

Aceasta înseamnă că, presupunând că plecăm într-o anumită stare ( $X_{t}=x_{i}$ ${\ displaystyle X_ {t} = x_ {i}}$ ${\ displaystyle X_ {t} = x_ {i}}$ ), acum suntem interesați de probabilitatea de a observa toate evenimentele viitoare din această stare. Deoarece starea inițială este luată ca dată (adică probabilitatea a priori a acestei stări este egală cu 100%), începem cu:

\mathbf {b_{T:T}} =[1\ 1\ 1\ \dots ]^{T}

{\ displaystyle \ mathbf {b_ {T: T}} = [1 \ 1 \ 1 \ \ dots] ^ {T}}

{\ displaystyle \ mathbf {b_ {T: T}} = [1 \ 1 \ 1 \ \ dots] ^ {T}}

Observați că acum folosim un vector coloană, în timp ce probabilitățile de avansare profită de vectorii rând. Apoi putem lucra înapoi folosind:

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

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

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

Deși am putea normaliza acest vector astfel încât componentele sale să adauge 1, acest lucru nu se face de obicei. Observând că fiecare componentă conține probabilitatea succesiunii evenimentelor viitoare, având în vedere o anumită stare inițială, normalizarea acestui vector ar fi echivalentă cu aplicarea teoremei lui Bayes pentru a găsi probabilitatea fiecărei stări inițiale date evenimentelor viitoare (presupunând distribuții uniforme a priori pentru vector de stare finală). Cu toate acestea, este mai frecvent să scalați acest vector folosind aceleași constante $c_{t}$ ${\ displaystyle c_ {t}}$ ${\ displaystyle c_ {t}}$ utilizat în calculele probabilității directe. $\mathbf {b_{T:T}}$ ${\ displaystyle \ mathbf {b_ {T: T}}}$ ${\ displaystyle \ mathbf {b_ {T: T}}}$ nu este scalat, dar operațiile ulterioare utilizează:

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

{\ displaystyle \ mathbf {{\ hat {b}} _ {t-1: T}} = c_ {t} ^ {- 1} \ mathbf {T} \ mathbf {O_ {t}} \ mathbf {{\ pălărie {b}} _ {t: T}}}

{\ displaystyle \ mathbf {{\ hat {b}} _ {t-1: T}} = c_ {t} ^ {- 1} \ mathbf {T} \ mathbf {O_ {t}} \ mathbf {{\ pălărie {b}} _ {t: T}}}

unde este $\mathbf {{\hat {b}}_{t:T}}$ ${\ displaystyle \ mathbf {{\ hat {b}} _ {t: T}}}$ ${\ displaystyle \ mathbf {{\ hat {b}} _ {t: T}}}$ reprezintă vectorul scalat anterior. Acest rezultat înseamnă că vectorul de probabilitate a fost scalat și asociat cu probabilitățile înapoi prin:

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

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

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

Acest lucru este util deoarece ne permite să găsim probabilitatea totală de a fi în fiecare stare la un anumit moment, t, prin înmulțirea cu aceste valori:

\mathbf {\gamma _{t}} (i)=\mathbf {P} (X_{t}=x_{i}|o_{1},o_{2},\dots ,o_{T},\mathbf {\pi } )={\frac {\mathbf {P} (o_{1},o_{2},\dots ,o_{T},X_{t}=x_{i}|\mathbf {\pi } )}{\mathbf {P} (o_{1},o_{2},\dots ,o_{T}|\mathbf {\pi } )}}={\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)

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

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

Pentru a înțelege acest lucru, observăm că $\mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)$ ${\ displaystyle \ mathbf {f_ {0: t}} (i) \ cdot \ mathbf {b_ {t: T}} (i)}$ ${\ displaystyle \ mathbf {f_ {0: t}} (i) \ cdot \ mathbf {b_ {t: T}} (i)}$ oferă probabilitatea de a observa evenimentele date într-un mod care trece prin stat $x_{i}$ ${\ displaystyle x_ {i}}$ $x_i$ la ora t. Această probabilitate include probabilitățile directe care acoperă toate evenimentele până la momentul t, precum și probabilitățile înapoi care includ toate evenimentele viitoare. Acesta este numeratorul pe care l-am căutat pentru ecuația noastră și îl împărțim la probabilitatea totală a secvenței de observații pentru a o normaliza și a extrage doar probabilitatea pentru care $X_{t}=x_{i}$ ${\ displaystyle X_ {t} = x_ {i}}$ ${\ displaystyle X_ {t} = x_ {i}}$ . Aceste valori sunt uneori numite „ valori netezite” deoarece combină probabilitățile înainte și înapoi pentru a calcula o probabilitate finală.

Valori $\mathbf {\gamma _{t}} (i)$ ${\ displaystyle \ mathbf {\ gamma _ {t}} (i)}$ ${\ displaystyle \ mathbf {\ gamma _ {t}} (i)}$ prin urmare ele oferă probabilitatea de a fi în orice stare la momentul t. Ca atare, acestea sunt utile pentru a determina starea cea mai probabilă în orice moment al timpului. Trebuie menționat, totuși, că termenul „starea cea mai probabilă” este oarecum ambiguu. În timp ce starea cea mai probabilă este cea mai favorabilă pentru a fi cea corectă la un moment dat, succesiunea stărilor individuale probabile nu este neapărat cea mai probabilă succesiune. Acest lucru se datorează faptului că probabilitățile pentru fiecare punct sunt calculate independent una de cealaltă. Acestea nu iau în considerare probabilitățile de tranziție între stări și, prin urmare, este posibil să se obțină stări în două timpi (t și t + 1), care sunt ambele mai probabile în acele instanțe, dar care au o probabilitate foarte mică de a se produce împreună, că este $\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})$ ${\ 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})}$ ${\ 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})}$ . Cea mai probabilă succesiune de stări care produce o succesiune de observații poate fi găsită folosind algoritmul Viterbi .

Exemplu

Acest exemplu ia lumea umbrelelor ca referință în Russel & Norvig 2003 pp. 540 în care am dori să deducem condițiile atmosferice având în vedere observația unui om care poartă o umbrelă sau nu. Presupunem două stări posibile pentru condițiile atmosferice: starea 1 = ploaie, starea 2 = fără ploaie. Să presupunem că condițiile atmosferice au o șansă de 70% să rămână la fel în fiecare zi și o șansă de 30% să se schimbe. Probabilitățile de tranziție sunt apoi:

\mathbf {T} ={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}

{\ displaystyle \ mathbf {T} = {\ begin {pmatrix} 0.7 & 0.3 \\ 0.3 & 0.7 \ end {pmatrix}}}

{\ displaystyle \ mathbf {T} = {\ begin {pmatrix} 0.7 & 0.3 \\ 0.3 & 0.7 \ end {pmatrix}}}

De asemenea, presupunem că fiecare dintre cele două stări ale condițiilor atmosferice generează două evenimente: eveniment 1 = umbrelă, eveniment 2 = fără umbrelă. Probabilitățile condiționate ca aceste evenimente să apară în fiecare dintre stări sunt date de matricea probabilității:

\mathbf {B} ={\begin{pmatrix}0.9&0.1\\0.2&0.8\end{pmatrix}}

{\ displaystyle \ mathbf {B} = {\ begin {pmatrix} 0.9 & 0.1 \\ 0.2 & 0.8 \ end {pmatrix}}}

{\ displaystyle \ mathbf {B} = {\ begin {pmatrix} 0.9 & 0.1 \\ 0.2 & 0.8 \ end {pmatrix}}}

Să presupunem că observăm următoarea succesiune de evenimente: {umbrelă, umbrelă, fără umbrelă, umbrelă, umbrelă}. Acest lucru va fi reprezentat în calculele noastre ca:

\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}}

{\ displaystyle \ 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}}}

{\ displaystyle \ 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}}}

Observați că elementul $\mathbf {O_{3}}$ ${\ displaystyle \ mathbf {O_ {3}}}$ ${\ displaystyle \ mathbf {O_ {3}}}$ diferă de ceilalți datorită observației „fără umbrelă”.

Pentru a calcula probabilitățile directe, începem cu:

\mathbf {f_{0:0}} ={\begin{pmatrix}0.5&0.5\end{pmatrix}}

{\ displaystyle \ mathbf {f_ {0: 0}} = {\ begin {pmatrix} 0,5 & 0,5 \ end {pmatrix}}}

{\ displaystyle \ mathbf {f_ {0: 0}} = {\ begin {pmatrix} 0,5 & 0,5 \ end {pmatrix}}}

care este vectorul nostru de stare a priori care indică faptul că nu cunoaștem starea condițiilor atmosferice înainte de observațiile noastre. În timp ce vectorul de stare ar trebui dat ca vector de rând, vom folosi transpunerea matricei în așa fel încât următoarele calcule să fie mai lizibile. Calculele noastre sunt apoi scrise sub forma:

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

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

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

in loc de

\mathbf {{\hat {f}}_{0:t}} =c^{-1}\mathbf {{\hat {f}}_{0:t-1}} \mathbf {T} \mathbf {O_{t}}

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

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

Rețineți că și matricea de transformare este transpusă, dar în exemplul nostru transpunerea este egală cu matricea originală. Prin efectuarea acestor calcule și normalizarea rezultatelor obținem:

(\mathbf {{\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}{\begin{pmatrix}0.4500\\0.1000\end{pmatrix}}={\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}

{\ displaystyle (\ mathbf {{\ 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} {\ begin {pmatrix} 0.4500 \\ 0.1000 \ end {pmatrix}} = {\ begin {pmatrix} 0.8182 \\ 0.1818 \ end {pmatrix}}}

{\ displaystyle (\ mathbf {{\ 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} {\ begin {pmatrix} 0.4500 \\ 0.1000 \ end {pmatrix}} = {\ begin {pmatrix} 0.8182 \\ 0.1818 \ end {pmatrix}}}

(\mathbf {{\hat {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}0.8834\\0.1166\end{pmatrix}}

{\ displaystyle (\ mathbf {{\ hat {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} 0.8834 \\ 0.1166 \ end {pmatrix}}}

{\ displaystyle (\ mathbf {{\ hat {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} 0.8834 \\ 0.1166 \ end {pmatrix}}}

(\mathbf {{\hat {f}}_{0:3}} )^{T}=c_{3}^{-1}{\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.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: 3}}) ^ {T} = c_ {3} ^ {- 1} {\ 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.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: 3}}) ^ {T} = c_ {3} ^ {- 1} {\ 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.1166 \ end {pmatrix}} = c_ {3} ^ {- 1} {\ begin {pmatrix} 0.0653 \\ 0.2772 \ end {pmatrix}} = {\ begin {pmatrix} 0.1907 \\ 0.8093 \ end {pmatrix}}}

(\mathbf {{\hat {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{pmatrix}}={\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}

{\ displaystyle (\ mathbf {{\ hat {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 {pmatrix}} = {\ begin {pmatrix} 0.7308 \\ 0.2692 \ end {pmatrix}}}

{\ displaystyle (\ mathbf {{\ hat {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 {pmatrix}} = {\ begin {pmatrix} 0.7308 \\ 0.2692 \ end {pmatrix}}}

(\mathbf {{\hat {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{pmatrix}}

{\ displaystyle (\ mathbf {{\ hat {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 {pmatrix}}}

{\ displaystyle (\ mathbf {{\ hat {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 {pmatrix}}}

Pentru probabilitățile înapoi, începem cu:

\mathbf {b_{5:5}} ={\begin{pmatrix}1.0\\1.0\end{pmatrix}}

{\ displaystyle \ mathbf {b_ {5: 5}} = {\ begin {pmatrix} 1.0 \\ 1.0 \ end {pmatrix}}}

{\ displaystyle \ mathbf {b_ {5: 5}} = {\ begin {pmatrix} 1.0 \\ 1.0 \ end {pmatrix}}}

Prin urmare, putem calcula (folosind observațiile în ordine inversă și normalizând cu constante diferite):

\mathbf {{\hat {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 {{\ hat {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 {{\ hat {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}}}

\mathbf {{\hat {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{pmatrix}}

{\ displaystyle \ mathbf {{\ hat {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 {pmatrix}}}

{\ displaystyle \ mathbf {{\ hat {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 {pmatrix}}}

\mathbf {{\hat {b}}_{2:5}} =\alpha {\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.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}} _ {2: 5}} = \ alpha {\ 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.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}} _ {2: 5}} = \ alpha {\ 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.6533 \\ 0.3467 \ end {pmatrix}} = \ alpha {\ begin {pmatrix} 0.1289 \\ 0.2138 \ end {pmatrix}} = { \ begin {pmatrix} 0.3763 ​​\\ 0.6237 \ end {pmatrix}}}

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

\mathbf {{\hat {b}}_{0: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.5923\\0.4077\end{pmatrix}}=\alpha {\begin{pmatrix}0.3976\\0.2170\end{pmatrix}}={\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}

{\ displaystyle \ mathbf {{\ hat {b}} _ {0: 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.5923 \\ 0.4077 \ end {pmatrix}} = \ alpha {\ begin {pmatrix} 0.3976 \\ 0.2170 \ end {pmatrix}} = { \ begin {pmatrix} 0.6469 \\ 0.3531 \ end {pmatrix}}}

{\ displaystyle \ mathbf {{\ hat {b}} _ {0: 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.5923 \\ 0.4077 \ end {pmatrix}} = \ alpha {\ begin {pmatrix} 0.3976 \\ 0.2170 \ end {pmatrix}} = { \ begin {pmatrix} 0.6469 \\ 0.3531 \ end {pmatrix}}}

În cele din urmă, vom calcula valorile de probabilitate netezite . Acest rezultat trebuie, de asemenea, să fie scalat în așa fel încât componentele sale să se adauge la 1. Acest lucru se datorează faptului că nu scalăm probabilitățile înapoi cu $c_{t}$ ${\ displaystyle c_ {t}}$ ${\ displaystyle c_ {t}}$ găsit anterior. Astfel, vectorii de probabilitate înapoi anteriori reprezintă, de fapt, probabilitatea fiecărei stări în momentul în care s-au dat observații viitoare. Deoarece acești vectori sunt proporționali cu probabilitățile reale înapoi, rezultatul trebuie redimensionat din nou.

(\mathbf {\gamma _{0}} )^{T}=\alpha {\begin{pmatrix}0.5000\\0.5000\end{pmatrix}}\times {\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 _ {0}}) ^ {T} = \ alpha {\ begin {pmatrix} 0.5000 \\ 0.5000 \ end {pmatrix}} \ times {\ 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 _ {0}}) ^ {T} = \ alpha {\ begin {pmatrix} 0.5000 \\ 0.5000 \ end {pmatrix}} \ times {\ 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}}}

(\mathbf {\gamma _{1}} )^{T}=\alpha {\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}\times {\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 _ {1}}) ^ {T} = \ alpha {\ begin {pmatrix} 0.8182 \\ 0.1818 \ end {pmatrix}} \ times {\ 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 _ {1}}) ^ {T} = \ alpha {\ begin {pmatrix} 0.8182 \\ 0.1818 \ end {pmatrix}} \ times {\ 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}}}

(\mathbf {\gamma _{2}} )^{T}=\alpha {\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}\times {\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 _ {2}}) ^ {T} = \ alpha {\ begin {pmatrix} 0.8834 \\ 0.1166 \ end {pmatrix}} \ times {\ 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 _ {2}}) ^ {T} = \ alpha {\ begin {pmatrix} 0.8834 \\ 0.1166 \ end {pmatrix}} \ times {\ 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}}}

(\mathbf {\gamma _{3}} )^{T}=\alpha {\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}\times {\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 _ {3}}) ^ {T} = \ alpha {\ begin {pmatrix} 0.1907 \\ 0.8093 \ end {pmatrix}} \ times {\ 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 _ {3}}) ^ {T} = \ alpha {\ begin {pmatrix} 0.1907 \\ 0.8093 \ end {pmatrix}} \ times {\ 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}}}

(\mathbf {\gamma _{4}} )^{T}=\alpha {\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}\times {\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}}

(\mathbf {\gamma _{4}} )^{T}=\alpha {\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}\times {\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}}

(\mathbf {\gamma _{4}} )^{T}=\alpha {\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}\times {\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}}

(\mathbf {\gamma _{5}} )^{T}=\alpha {\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}\times {\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}}

(\mathbf {\gamma _{5}} )^{T}=\alpha {\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}\times {\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}}

(\mathbf {\gamma _{5}} )^{T}=\alpha {\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}\times {\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}}

Si noti che il valore di $\mathbf {\gamma _{0}}$ $\mathbf {\gamma _{0}}$ $\mathbf {\gamma _{0}}$ è uguale a $\mathbf {{\hat {b}}_{0:5}}$ $\mathbf {{\hat {b}}_{0:5}}$ $\mathbf {{\hat {b}}_{0:5}}$ e che $\mathbf {\gamma _{5}}$ $\mathbf {\gamma _{5}}$ $\mathbf {\gamma _{5}}$ è uguale a $\mathbf {{\hat {f}}_{0:5}}$ $\mathbf {{\hat {f}}_{0:5}}$ $\mathbf {{\hat {f}}_{0:5}}$ . Naturalmente questo consegue perché sia $\mathbf {{\hat {f}}_{0:5}}$ $\mathbf {{\hat {f}}_{0:5}}$ $\mathbf {{\hat {f}}_{0:5}}$ che $\mathbf {{\hat {b}}_{0:5}}$ $\mathbf {{\hat {b}}_{0:5}}$ $\mathbf {{\hat {b}}_{0:5}}$ iniziano con distribuzioni a priori uniformi sopra i vettori di stato iniziale e finale rispettivamente e tengono d'acconto di tutte le osservazioni. Tuttavia, $\mathbf {\gamma _{0}}$ $\mathbf {\gamma _{0}}$ $\mathbf {\gamma _{0}}$ sarà solo uguale a $\mathbf {{\hat {b}}_{0:5}}$ $\mathbf {{\hat {b}}_{0:5}}$ $\mathbf {{\hat {b}}_{0:5}}$ quando il nostro vettore di stato iniziale rappresenta una distribuzione a priori uniforme (cioè una con tutti gli elementi identici tra loro). Quando questo non è il caso, è necessario combinare $\mathbf {{\hat {b}}_{0:5}}$ $\mathbf {{\hat {b}}_{0:5}}$ $\mathbf {{\hat {b}}_{0:5}}$ con il vettore di stato iniziale per trovare lo stato iniziale più probabile. Perciò scopriamo che le probabilità in avanti per sé stesse sono sufficienti per calcolare lo stato finale più probabile. Analogamente, le probabilità all'indietro possono essere combinate con il vettore di stato iniziale per fornire lo stato iniziale più probabile date le osservazioni. Le probabilità in avanti e all'indietro richiedono solo di essere combinate per poter inferire gli stati più probabili tra i punti iniziale e finale.

I calcoli sopra rivelano che lo stato delle condizioni atmosferiche più probabile per ogni giorno, eccetto che per il terzo, è "pioggia". Inoltre ci dicono di più, in quanto tali calcoli ora ci forniscono un modo per quantificare le probabilità di ogni stato ad istanti differenti. Maggiormente importante, il nostro valore a $\mathbf {\gamma _{5}}$ $\mathbf {\gamma _{5}}$ $\mathbf {\gamma _{5}}$ quantifica la nostra conoscenza del vettore di stato alla fine della successione di osservazioni. Possiamo usarlo infatti per predire la probabilità dei vari stati delle condizioni atmosferiche di domani così come la probabilità di osservare un ombrello.

Prestazioni

La procedura più diretta per la soluzione di questo problema è la generazione di tutte le possibili successioni di stati $N^{T}$ $N^{T}$ $N^{T}$ e il calcolo della probabilità congiunta di ogni successione di stati con la serie osservata di eventi. Questo approccio ha complessità temporale $O(T\cdot N^{T})$ $O(T\cdot N^{T})$ $O(T\cdot N^{T})$ , dove $T$ ${\displaystyle T}$ $T$ è la lunghezza delle successioni e $N$ ${\displaystyle N}$ $N$ è il numero di simboli nell'alfabeto dello stato. Operando in questo modo i problemi reali diventano intrattabili in quanto il numero di possibili successioni di nodi nascosti tipicamente è estremamente elevato. Tuttavia, l'algoritmo di forward–backward ha complessità temporale $O(N^{2}T)\,$ $O(N^{2}T)\,$ $O(N^{2}T)\,$ .

Sono noti vari miglioramenti dell'algoritmo di forward–backward che permettono al calcolo di collocarsi in uno spazio costante. Inoltre, nel tempo sono stati sviluppati algoritmi per calcolare efficientemente $\mathbf {f_{0:t+1}}$ $\mathbf {f_{0:t+1}}$ $\mathbf {f_{0:t+1}}$ tramite uno smoothing in linea ( online smoothing ) dei dati come l'algoritmo FLS ( fixed-lag smoothing ) Russel & Norvig 2003 pp. 552 .

Pseudo-codice

 ForwardBackward(guessState, sequenceIndex):
    if sequenceIndex is past the end of the sequence, return 1
    if (guessState, sequenceIndex) has been seen before, return saved result
    result = 0
    for each neighboring state n:
        result = result + (transition probability from guessState to n given observation element at sequenceIndex)
                        * ForwardBackward(n, sequenceIndex+1)
    save result for (guessState, sequenceIndex)
    return result

Esempio in Python

Dato il modello di Markov nascosto (come nell' algoritmo di Viterbi ) qui rappresentato nel linguaggio di programmazione 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 },
   }

Possiamo scriverne un'implementazione tipo questa:

 def fwd_bkw ( x , states , a_0 , a , e , end_st ):
    L = len ( x )

    fwd = []
    # Run forward
    for i , x_i in enumerate ( x ):
        f_curr = {}
        for st in states :
            if i == 0 :
                # Initialize base fwd cases
                prev_f_sum = a_0 [ st ]
            else :
                prev_f_sum = sum ( f_prev [ k ] * a [ k ][ st ] for k in states )

            f_curr [ st ] = e [ st ][ x_i ] * prev_f_sum

        fwd . append ( f_curr )
        f_prev = f_curr

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

    bkw = []
    # Run bkw
    for i , x_i_plus in enumerate ( reversed ( x [ 1 :] + ( None ,))):
        b_curr = {}
        for st in states :
            if i == 0 :
                # Initialize base bkw cases
                b_curr [ st ] = a [ st ][ end_st ]
            else :
                b_curr [ st ] = sum ( a [ st ][ l ] * e [ l ][ x_i_plus ] * b_prev [ l ] for l in states )

        bkw . insert ( 0 , b_curr )
        b_prev = b_curr

    p_bkw = sum ( a_0 [ l ] * e [ l ][ x [ 0 ]] * b_curr [ l ] for l in states )

    posterior = {}
    for st in states :
        posterior [ st ] = [ fwd [ i ][ st ] * bkw [ i ][ st ] / p_fwd for i in xrange ( L )]

    assert p_fwd == p_bkw
    return fwd , bkw , posterior

La funzione fwd_bkw ammette i seguenti argomenti: x è la successione di osservazioni, ad esempio ['normal', 'cold', 'dizzy'] ; states è l'insieme degli stati nascosti; a_0 è la probabilità iniziale; a sono le probabilità di transizione; ed e sono le probabilità di emissione ossia di finire un certo stato.

Per mantenere semplice il codice, assumiamo che la successione di osservazioni x sia non vuota e che le componenti a[i][j] ed e[i][j] siano definite per tutti gli stati i,j .

Nell'esempio l'algoritmo forward-backward è impiegato come segue:

 def example ():
    return fwd_bkw ( observations ,
                   states ,
                   start_probability ,
                   transition_probability ,
                   emission_probability ,
                   end_state )
for line in example ():
    print ' ' . join ( map ( str , line ))

Bibliografia

Lawrence R. Rabiner , A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition . Proceedings of the IEEE , 77 (2), p. 257–286, February 1989. 10.1109/5.18626
Lawrence R. Rabiner, BH Juang, An introduction to hidden Markov models , in IEEE ASSP Magazine , gennaio 1986, pp. 4–15.
Eugene Charniak, Statistical Language Learning , Cambridge, Massachusetts, MIT Press, 1993, ISBN 978-0-262-53141-2 .
Stuart Russell and Peter Norvig, Artificial Intelligence A Modern Approach 2nd Edition , Upper Saddle River, New Jersey, Pearson Education, 2003, ISBN 0-13-080302-2 .

Voci correlate

Collegamenti esterni

An interactive spreadsheet for teaching the forward–backward algorithm (spreadsheet and article with step-by-step walk-through)
Tutorial of hidden Markov models including the forward–backward algorithm , su cs.brown.edu .
Collection of AI algorithms implemented in Java (including HMM and the forward–backward algorithm)

Portale Statistica : accedi alle voci di Wikipedia che trattano di statistica