Algoritm înainte

Algoritmul înainte ( de asemenea , transmite algoritm , procedura înainte ) utilizează așa-numitele variabile forward pentru a calcula probabilitatea unei observații specifice pentru un anumit model de Markov ascuns . El folosește metoda de programare a programării dinamice .

Modelul Markov

Modelul Markov este definit ca , unde ${\ displaystyle \ lambda = (S; V; A; B; \ pi)}$

${\ displaystyle S}$ setul de stări ascunse,
${\ displaystyle V}$ alfabetul simbolurilor observabile,
${\ displaystyle A}$ matricea probabilităților de tranziție ,
${\ displaystyle B}$ matricea probabilităților de emisie,
${\ displaystyle \ pi}$ distribuția inițială pentru stările inițiale posibile,

desemnat.

Variabile de sarcină și redirecționare

Având un cuvânt . Algoritmul direct calculează acum probabilitatea de a efectua efectiv observația în modelul existent . ${\ displaystyle {\ boldsymbol {o}} = o_ {1} o_ {2} \ dots o_ {T} \ în V ^ {*}}$ ${\ displaystyle P ({\ boldsymbol {o}} | \ lambda)}$ ${\ displaystyle \ lambda}$ ${\ displaystyle {\ boldsymbol {o}}}$

Pentru aceasta sunt utilizate variabilele directe . Aceasta stochează probabilitatea de care au observat prefixul la momentul respectiv și de a fi în stare : ${\ displaystyle \ alpha _ {t} (i)}$ ${\ displaystyle 1 \ leq t \ leq T}$ ${\ displaystyle o_ {1} o_ {2} \ ldots o_ {t}}$ ${\ displaystyle s_ {i} \ în S}$

{\ displaystyle \ alpha _ {t} (i) = P (o_ {1} o_ {2} \ ldots o_ {t}; q_ {t} = s_ {i} | \ lambda)}

funcționalitate

Variabilele directe, și deci și probabilitatea generală, pot fi calculate recursiv:

initializare: ${\ displaystyle \ alpha _ {1} (i) = \ pi _ {i} \ cdot b_ {i} (o_ {1}), \ qquad 1 \ leq i \ leq \ left | S \ right |}$

Recursivitate: ${\ displaystyle \ alpha _ {t} (i) = \ left (\ sum _ {j = 1} ^ {| S |} \ alpha _ {t-1} (j) a_ {ji} \ right) \ cdot b_ {i} (o_ {t}); \ qquad 1 <t \ leq T, \ 1 \ leq i \ leq \ left | S \ right |}$

Rezilierea: ${\ displaystyle P ({\ varvec {o}} | \ lambda) = \ sum _ {j = 1} ^ {| S |} \ alpha _ {T} (j)}$

complexitate

Algoritmul necesită operații și oferă o metodă eficientă pentru calcularea probabilității căutate. Cerința de memorie este disponibilă , deoarece toate sunt stocate într-o matrice pentru a realiza timpul de rulare polinomial . ${\ displaystyle O (| S | ^ {2} \ cdot T)}$ ${\ displaystyle O (| S | \ cdot T)}$ ${\ displaystyle \ alpha _ {t} (i)}$ ${\ displaystyle | S | \ times T}$

Dacă rezultatele intermediare pentru for nu sunt necesare după sfârșitul recursiunii, atunci cerința de memorie este redusă la , deoarece doi vectori de coloană de lungime sunt suficiente pentru a stoca și în fiecare etapă de recursie. ${\ displaystyle \ alpha _ {t} (i)}$ ${\ displaystyle t <T}$ ${\ displaystyle O (| S |)}$ ${\ displaystyle | S |}$ ${\ displaystyle \ alpha _ {t-1} (i)}$ ${\ displaystyle \ alpha _ {t} (i)}$

Alte utilizări

Variabilele directe sunt necesare împreună cu variabilele înapoi pentru algoritmul Baum-Welch pentru a rezolva problema de învățare dată cu modelele ascunse Markov. ${\ displaystyle \ alpha _ {t} (i)}$ ${\ displaystyle \ beta _ {t} (i) = P (o_ {t + 1} \ dots o_ {T} | q_ {t} = s_ {i}; \ lambda)}$

În plus, cunoașterea acestui lucru permite determinarea probabilității de a fi fost în stare atunci când observăm într-un moment fix , deoarece, conform teoremei lui Bayes : ${\ displaystyle {\ boldsymbol {o}}}$ ${\ displaystyle t}$ ${\ displaystyle s_ {i}}$

{\ displaystyle P (q_ {t} = s_ {i} | {\ boldsymbol {o}}; \ lambda) = {\ frac {\ alpha _ {t} (i) \ cdot \ beta _ {t} (i )} {P ({\ boldsymbol {o}} | \ lambda)}}}

Vezi si

literatură

R. Durbin și colab.: Analiza secvenței biologice. Modele probabiliste de proteine și acizi nucleici. A 11-a tipărire, corectată 10. reimprimare . Cambridge University Press, Cambridge și colab. 2006, ISBN 0-521-62971-3 , pp. 59 .

Link-uri web

EG Schukat-Talamazzini: Sisteme speciale de analiză a modelelor (PDF, 1,3 MB) Curs în WS 2012/13 la Universitatea din Jena. Capitolul 5 Slide 32ff.

Languages