Modele Markov

Modele Markov

In teoria probabilitatilor, un model Markov reprezinta un model stocastic utilizat pentru a modela schimbarile aleatoare in sisteme in care se presupune ca starile viitoare depind doar de starea curenta, si nu de evenimente care au precedat starea curenta.

Exista patru tipuri de modele Markov, redate in Tabelul 1. Acestea difera prin observabilitatea starilor sistemului si de tipul sistemului.

Tabelul 1 – Tipuri de modele Markov [1]

–––-

Lanturi Markov

Pentru a intelege mai bine aplicabilitatea lanturilor Markov, aceasta sectiune incepe cu un exemplu [2].

O broasca relizeaza un salt pe una dintre cele 7 frunze (Figura 1). Numerele de langa sageti indica probabilitatea cu care, la urmatoarea saritura, broasca sare pe o frunza vecina.

Figura 1

Astfel, exista sapte stari (reprezentate de cele sapte frunze). In matricea definita mai jos, elementul pij reprezinta probabilitatea ca broasca sa sara de pe frunza I pe frunza j, intr-o singura saritura. Dorim sa stim care este destinatia (cunoscand frunza curenta), care este drumul parcurs pana la destinatie, ce se intampla pe un drum lung. De exemplu:

Pornind de la starea 1, care este probabilitatea de a fi tot in starea 1 dupa 3 sarituri? Dar dupa 5 sarituri? Dar dupa 2000 de sarituri?

Pornind din starea 4, care este probabilitatea de a ajunge vreodata in starea 7?

Pornind din starea 2…?

Raspunsurile la aceste intrebari sunt date de lanturile Markov.

Bibliografie

Markov Model, https://en.wikipedia.org/wiki/Markov_model

Richard Weber, Markov Chains, http://www.statslab.cam.ac.uk/~rrw1/markov/M.pdf

––

Un caz particular de model Markov este moddelul Markov cu stari ascunse. Acestea sunt utilizate in diferite arii de cercetare, precum sisteme de recunoastere a vorbirii, biologie computationala moleculara, compresia datelor si alte arii ale inteligentei artificiale si recunoasterea sabloanelor.

In continuare, vom prezenta un exemplu [1], in care este folosit modelul Markov cu stari ascunse.

Sa presupunem ca dorim sa calculam temperatura medie anuala pentru o anumita locatie de pe Pamant de-a lungul mai multor ani, intr-un trecut indepartat in care termomentrele nu existau inca. Deoarece nu putem calatori in timp, vom folosi dovezi indirecte ale temperaturii. Pentru inceput dorim sa intelegem modalitatea de lucru a modelelor Markov cu stari ascunse si simplificam exemplul considernad doua temperaturi anuale: “caldura” si “racoare”. Sa presupunem ca in standardele moderne probabilitatea ca un an calduros sa fie urmat tot de un an calduros este de 0.7 si probabilitatea ca un an racoros sa fie urmat tot de un an racoros este de 0.6. Consideram ca aceste probabilitati sunt valabile si pentru anii trecuti. Deci, informatiile pot fi sumarizate astfel:

De asemenea, cercetarile curente au stabilit o corelatie intre vreme si inelele dintr-o sectiune transversala a unui copac. Pentru simplitate consideram doar trei dimensiuni pentru inelele unui arbore, mic, mediu, mare. Relatia de probabilitate dintre temperatura anuala si dimensiunea inelelor (stabilita in urma cercetarilor moderne) este urmatoarea:

Pentru sistemul descris anterior, starea reprezinta temperatura media anuala – caldura sau racoare. Tranzitia dintr-o stare in urmatoarea stare este un proces Markov (de ordin intai), deoarece starea urmatoare depinde in totalitate de starea curenta si de probabilitatile definite in (1). In realitate, starile sunt ascunse, deoarece temperatura in trecut nu poate fi observata direct.

Desi starile din trecut nu pot fi observate, totusi pot fi observate inelele copacilor. In (2) gasim doar informatii probabiliste referitoare la temperatura. Deoarece starile sunt ascunse, tipul sistemului este model Markov cu stari ascunse (Hidden Markov Model – HMM). Scopul nostru este de a utiliza eficient informatiile obtinute in cadrul observarilor.

Din (1), gasim matricea de tranzitie:

A = … (3)

Din (2), gasim matricea observarilor:

B = … (4)

Pentru acest exemplu sa consideram ca starea initiala de distributie este:

Pi = [0.6 0.4] (5)

Fiecare linie din matricele A, B si Pi sunt stocastice, adica toate elementele de pe linie reprezinta probabilitati, deci suma elementelor de pe o linie este 1.

Acum sa consideram o anumita perioada de interes de 4 ani, pentru care am observat seriile de dimensiuni ale inelelor Mic, Mediu, Mic, Mare. Fie Mic = 0, Mediu = 1 si Mare = 2. Secventa mentionata devine:

O = (0, 1, 0, 2) (6)

Dorim sa determinam cea mai probabila secventa de stari care conduce la observatiile (6), cu alte cuvinte, dorim sa aflam cea mai probabila secventa de temperaturi medii anule pentru cei patru ani de interes. Obiectivul nu este usor de atins, deoarece nu avem o definitie concreta pentru “Cel mai probabil”. Pe de o parte putem defini secevnta de stari cu probabilitatile cele mai mari din toate secventele posibile de stari de lungime 4. Programarea dinamica poate fi utilizata eficient pentru a gasi aceasta solutie particulara. Pe de alta parte, putem defini “cel mai probabil” ca secventa de stari care maximizeaza numarul asteptat de stari corecte. Modelul Markov cu stari ascunse poate fi utilizat aici.

Solutia gasita aplicand programarea dinamica poate fi diferita de cea gasita aplicand modelul Markov.

Modelul Morkov cu stari ascunse este un procedeu pentru reprezentarea distributiilor de probabilitate peste secvente de observatii.

Notatii [1]:

T – lungimea secventei observate

N – numarul de stari din model

M – numarul de simboluri de observare

Q = {q0, …, q_(N-1)} – multimea de stari diferite ale procesului Markov

V = {0, 1, …, M-1} – multimea observarilor posibile

A – matricea de probabilitatilor de tranzitie intre stari

B – matricea ??

Pi = distributia starii initiale

O = {O0, …, O_(T-1)} – multimea observarilor

In Figura 1 este prezentat un model Markov cu stari ascunse generic, unde Xi reprezinta starea de la momentul i. procesul Markov, care este ascuns in spatele liniei punctate, este determinat de starea curenta si de matricea A. Se pot observa doar Oi, care sunt legate de starile (ascunse) ale procesului Markov prin matricea B.

Figura 1 – Modelul Markov cu stari ascunse [1]

Mark Stamp, A Revealing Introduction to Hidden Markov Models, Decembrie 2015, San Jose State University

Tipuri de probleme care pot fi rezolvate cu ajutorul modelului Markov cu stari ascunse.