Modelul Markov ascuns

Tranziții de stat într-un model ascuns Markov (exemplu)
x - a fost ascuns
y - ieșire observabilă
a - probabilitatea de tranziție
b - probabilitatea de ieșire

Un model Markov ascuns (Hidden Markov Model - HMM) este un lanț Markov în care statele nu sunt direct observabile. Mai precis:

lanțul are o serie de stări
statele evoluează după un lanț Markov
fiecare stat generează un eveniment cu o anumită distribuție de probabilitate care depinde doar de stat
evenimentul este observabil, dar statul nu

Modelele ascunse Markov sunt cunoscute în special pentru aplicațiile lor în recunoașterea tiparului temporal al vorbirii vorbite, scrisului de mână, recunoașterii texturii și bioinformaticii (de exemplu, HMMer).

Cum se folosește modelul ascuns Markov

Există 3 probleme canonice asociate HMM-urilor:

Având în vedere parametrii modelului, calculați probabilitatea unei anumite secvențe a ieșirii. Această problemă este rezolvată de algoritmul forward .
Având în vedere parametrii modelului, găsiți cea mai probabilă secvență care ar putea genera o secvență de ieșire dată. Această problemă este rezolvată de algoritmul Viterbi ( Andrea Viterbi ).
Având în vedere o secvență de ieșire sau un set de astfel de secvențe, găsiți cel mai probabil set pentru care pot fi declarate probabilitățile de ieșire și tranziție. Aceasta înseamnă „antrenarea” parametrilor HMM-ului dat prin intermediul grupului de date de secvență. Această problemă este rezolvată de algoritmul Baum-Welch .

Exemplu concret

Luați în considerare doi prieteni, Alice și Bob, care locuiesc departe și vorbesc la telefon în fiecare zi despre ceea ce au făcut în timpul zilei. Bob face doar trei activități: plimbări în parc, merge la cumpărături și își curăță apartamentul. Alegerea a ce se face este determinată exclusiv de vreme. Alice nu știe cum este vremea la Bob când îl cheamă, dar știe ce face Bob în fiecare zi. Pe baza a ceea ce face Bob, Alice încearcă să ghicească la ce oră a trăit Bob.

Există două stări, „ploaie” și „soare”, dar Alice nu le poate observa direct, adică sunt ascunse. În fiecare zi, există o anumită șansă ca Bob să facă una dintre următoarele activități, în funcție de vreme: mers pe jos, cumpărături sau curățenie. Întrucât Bob vorbește cu Alice despre activitățile sale, acestea sunt observațiile. Întregul sistem este cel al unui model Markov ascuns.

Alice cunoaște tendința generală a timpului în care locuiește Bob și ce îi place lui Bob să facă în medie. Cu alte cuvinte, parametrii HMM sunt cunoscuți, care pot fi reprezentați după cum urmează în limbajul de programare Python:

 states = ( 'Ploaie' , 'Soare' )
 
remarci = ( „plimbare” , „cumpărături” , „curat” )
 
initial_ probability = { 'Rain' : 0.6 , 'Sun' : 0.4 }
 
tranzitie_probabilitate = {
   „Ploaie” : { „Ploaie” : 0,7 , „Soare” : 0,3 },
   „Soare” : { „Ploaie” : 0,4 , „Soare” : 0,6 },
   }
 
emisiune_probabilitate = {
   „Ploaie” : { „mers” : 0,1 , „cumpărături” : 0,4 , „curat” : 0,5 },
   „Soare” : { „mers” : 0,6 , „cumpărături” : 0,3 , „curățare” : 0,1 },
   }

unde probabilità_iniziale inițială reprezintă probabilitatea fiecăreia dintre cele două stări ale ploii / soarelui HMM, când Bob îl numește (știe, în esență, că acolo unde locuiește Bob, clima este ploioasă: 60%). probabilità_di_transizione reprezintă probabilitatea ca mâine să plouă / există soarele condiționat de faptul că astăzi plouă / există soarele. În acest exemplu, există 30% șanse ca ziua următoare să fie soare dacă plouă astăzi. probabilità_di_emissione reprezintă probabilitatea ca Bob să facă o anumită activitate dintre cele trei posibile. Dacă plouă, există o șansă de 50% ca el să-și curețe apartamentul; dacă e soare, există șanse de 60% să plece.

Alice poate calcula cea mai probabilă secvență de stări ascunse în zile succesive, cunoscând aceste trei date, înmulțind probabilitatea de tranziție cu probabilitatea de emisie a fiecărei zile și adăugând valorile.

P(Y)=\sum _{X}P(Y\mid X)P(X),\,

{\ displaystyle P (Y) = \ sum _ {X} P (Y \ mid X) P (X), \,}

{\ displaystyle P (Y) = \ sum _ {X} P (Y \ mid X) P (X), \,}

unde este $Y=y(0),y(1),\dots ,y(L-1)$ ${\ displaystyle Y = y (0), y (1), \ dots, y (L-1)}$ ${\ displaystyle Y = y (0), y (1), \ dots, y (L-1)}$ este ansamblul ordonat de evenimente și $X=x(0),x(1),\dots ,x(L-1)\,$ ${\ displaystyle X = x (0), x (1), \ dots, x (L-1) \,}$ ${\ displaystyle X = x (0), x (1), \ dots, x (L-1) \,}$ este ansamblul ordonat de stări ascunse.

Aplicații ale modelelor ascunse Markov

Recunoașterea vorbirii, textura și mișcarea corpului, citirea optică a personajelor
Sinteza vorbirii
Studiu de bioinformatică și genom
Predicția regiunilor de codificare în secvența genomului
Modelarea familiilor de proteine sau a familiilor de gene
Predicția elementelor structurii secundare din secvențele de proteine primare

Istorie

Modelele ascunse ale lui Markov au fost descrise pentru prima dată într-o serie de studii statistice realizate de Leonard E. Baum și alți autori în a doua jumătate a anilor 1960 . Una dintre primele aplicații ale HMM-urilor a fost recunoașterea vorbirii, începând din anii 1970 .

În a doua jumătate a anilor 1980 , HMM-urile au început să fie aplicate la analiza secvențelor biologice, în special a ADN-ului . De atunci, această metodologie a devenit de mare ajutor în domeniul bioinformaticii.

Bibliografie

Stuart J. Russell, Peter Norvig, Capitolul 15 Raționamentul probabilist în timp , în S. Gaburri (eds), Inteligența artificială. O abordare modernă (2) , ediția a II-a, Pearson Education Italia, 2005, ISBN 978-88-7192-229-4 . Adus la 1 februarie 2010 .
( EN ) Lawrence R. Rabiner , Un tutorial despre modelele ascunse Markov și aplicațiile selectate în recunoașterea vorbirii . Proceduri ale IEEE , 77 (2), p. 257-286, februarie 1989.
( EN ) Bartolucci F., Farcomeni A. și Pennoni F., Latent Markov Models for Longitudinal Data , Chapman and Hall / CRC, 2013, ISBN 978-14-3981-708-7 .

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere ascunse ale modelului Markov

Controlul autorității	LCCN (EN) sh2007000125 · GND (DE) 4352479-5

Portal IT

Portal de inginerie

Portalul de statistici

V · D · M Învățare automată
Probleme	Clasificarea · Regresie · asociere Reguli · Învățare nesupravegheați · Supravegheat de învățare · Reinforcement Learning · învățare profundă
Învățare nesupravegheată	Clustering · clustering Ierarhica · K mijloace · Așteptarea maximizare · DBSCAN · schimbare medie · antagonist generativă rețea (CGAN · cycleGAN VAE-GAN)
Învățare supravegheată	Arborele decizional · Pădure aleatorie · CRF · HMM · KNN · Clasificator bayesian · Rețea neuronală artificială · Regresie liniară · Regresie logistică · PGM · SVM
Consolidarea învățării	Q-learning · SARSA · TD
Reducerea dimensiunii	Analiza factorilor · CCA · ICA · LDA · PCA · Selecția caracteristicilor · Extragerea caracteristicilor · t-SNE
Rețele neuronale artificiale	Perceptron · RBF · N · FFN · Rețea Hopfield · MLP · RNN ( LSTM ) · RBM · SOM · CNN · TDNN · SNN
Software	Keras · Microsoft Cognitive Toolkit · scikit-learn · TensorFlow · Theano · Torch · Weka
Alte	Algoritm genetic · PSO · Caracteristic