Introducere la lanțurile Markov

Lucrurile Markov sunt o modalitate destul de comună și relativ simplă de a modela statistic procesele aleatoare. Acestea au fost utilizate în multe domenii diferite, de la generarea de texte până la modelarea financiară. Un exemplu popular este r/SubredditSimulator, care utilizează lanțurile Markov pentru a automatiza crearea de conținut pentru un întreg subreddit. În general, lanțurile Markov sunt, din punct de vedere conceptual, destul de intuitive și sunt foarte accesibile, în sensul că pot fi implementate fără utilizarea unor concepte statistice sau matematice avansate. Ele reprezintă o modalitate excelentă de a începe să înveți despre tehnicile de modelare probabilistică și știința datelor.

Scenariu

Pentru a începe, le voi descrie cu un exemplu foarte comun:

Imagine that there were two possible states for weather: sunny or cloudy. You can always directly observe the current weather state, and it is guaranteed to always be one of the two aforementioned states.Now, you decide you want to be able to predict what the weather will be like tomorrow. Intuitively, you assume that there is an inherent transition in this process, in that the current weather has some bearing on what the next day's weather will be. So, being the dedicated person that you are, you collect weather data over several years, and calculate that the chance of a sunny day occurring after a cloudy day is 0.25. You also note that, by extension, the chance of a cloudy day occurring after a cloudy day must be 0.75, since there are only two possible states.You can now use this distribution to predict weather for days to come, based on what the current weather state is at the time.

Acest exemplu ilustrează multe dintre conceptele cheie ale unui lanț Markov. Un lanț Markov constă, în esență, dintr-un set de tranziții, care sunt determinate de o anumită distribuție de probabilitate, care satisface proprietatea Markov.

Observați cum, în exemplu, distribuția de probabilitate este obținută numai prin observarea tranzițiilor din ziua curentă în ziua următoare. Acest lucru ilustrează proprietatea Markov, caracteristica unică a proceselor Markov care le face să nu aibă memorie. Acest lucru le face, de obicei, incapabile să producă cu succes secvențe în care se așteaptă să apară o anumită tendință de bază. De exemplu, în timp ce un lanț Markov poate fi capabil să imite stilul de scriere al unui autor pe baza frecvenței cuvintelor, acesta nu ar fi capabil să producă un text care să conțină un înțeles profund sau o semnificație tematică, deoarece acestea se dezvoltă pe parcursul unor secvențe de text mult mai lungi. Prin urmare, le lipsește capacitatea de a produce conținut dependent de context, deoarece nu pot lua în considerare întregul lanț de stări anterioare.

Modelul

În mod normal, un lanț Markov este un automat probabilistic. Distribuția de probabilitate a tranzițiilor de stare este reprezentată de obicei ca matrice de tranziție a lanțului Markov. Dacă lanțul Markov are N stări posibile, matricea va fi o matrice N x N, astfel încât intrarea (I, J) este probabilitatea de a trece din starea I în starea J. În plus, matricea de tranziție trebuie să fie o matrice stocastică, o matrice ale cărei intrări din fiecare rând trebuie să însumeze exact 1. Acest lucru este complet logic, deoarece fiecare rând reprezintă propria sa distribuție de probabilitate.

Aditional, un lanț Markov are, de asemenea, un vector de stare inițială, reprezentat ca o matrice N x 1 (un vector), care descrie distribuția de probabilitate de a începe în fiecare dintre cele N stări posibile. Intrarea I a vectorului descrie probabilitatea ca lanțul să înceapă în starea I.

Aceste două entități sunt, de obicei, tot ceea ce este necesar pentru a reprezenta un lanț Markov.

Știm acum cum să obținem șansa de a trece de la o stare la alta, dar cum ar fi să găsim șansa ca această tranziție să aibă loc în mai multe etape? Pentru a formaliza acest lucru, dorim acum să determinăm probabilitatea de a trece din starea I în starea J pe parcursul a M pași. După cum se pare, acest lucru este de fapt foarte simplu de aflat. Dată fiind o matrice de tranziție P, aceasta poate fi determinată prin calcularea valorii intrării (I, J) din matricea obținută prin ridicarea lui P la puterea lui M. Pentru valori mici ale lui M, acest lucru poate fi realizat cu ușurință manual, prin înmulțiri repetate. Cu toate acestea, pentru valori mari ale lui M, dacă sunteți familiarizați cu algebra liniară simplă, o modalitate mai eficientă de a ridica o matrice la o putere este de a diagonaliza mai întâi matricea.

Concluzie

Acum că știți elementele de bază ale lanțurilor Markov, ar trebui să puteți acum să le implementați cu ușurință într-un limbaj la alegere. Dacă programarea nu este punctul dumneavoastră forte, există, de asemenea, multe alte proprietăți mai avansate ale lanțurilor Markov și ale proceselor Markov în care vă puteți scufunda. În opinia mea, progresia naturală de-a lungul traseului teoretic ar fi spre Procesele Markov ascunse sau MCMC. Lanțurile Markov simple sunt blocurile de construcție ale altor tehnici de modelare mai sofisticate, așa că, cu aceste cunoștințe, puteți trece acum la diverse tehnici din cadrul unor subiecte precum modelarea credinței și eșantionarea.

.