Indledning til Markov-kæder

Markovkæder er en ret almindelig og relativt enkel måde at statistisk modellere tilfældige processer på. De er blevet anvendt inden for mange forskellige områder, lige fra tekstgenerering til finansiel modellering. Et populært eksempel er r/SubredditSimulator, som bruger Markov-kæder til at automatisere oprettelsen af indhold til en hel subreddit. Samlet set er Markov-kæder konceptuelt set ret intuitive og er meget tilgængelige, idet de kan implementeres uden brug af avancerede statistiske eller matematiske begreber. De er en fantastisk måde at begynde at lære om probabilistisk modellering og datavidenskabelige teknikker på.

Scenarie

Til at begynde med vil jeg beskrive dem med et meget almindeligt eksempel:

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.

Dette eksempel illustrerer mange af de vigtigste begreber i en Markov-kæde. En Markov-kæde består i det væsentlige af et sæt af overgange, som er bestemt af en vis sandsynlighedsfordeling, der opfylder Markov-egenskaben.

Opmærksomheden henledes på, hvordan sandsynlighedsfordelingen i eksemplet udelukkende opnås ved at observere overgange fra den aktuelle dag til den næste. Dette illustrerer Markov-egenskaben, som er den unikke egenskab ved Markov-processer, der gør dem hukommelsesløse. Dette gør dem typisk ude af stand til at producere sekvenser, hvor en eller anden underliggende tendens kan forventes at forekomme. Selv om en Markov-kæde f.eks. kan være i stand til at efterligne en forfatters skrivestil baseret på ordfrekvenser, vil den ikke være i stand til at producere tekst, der indeholder dyb mening eller tematisk betydning, da disse udvikles over meget længere sekvenser af tekst. De mangler derfor evnen til at producere kontekstafhængigt indhold, da de ikke kan tage højde for hele kæden af forudgående tilstande.

Modellen

Formelt set er en Markov-kæde en probabilistisk automat. Sandsynlighedsfordelingen af tilstandsovergange repræsenteres typisk som Markov-kædens overgangsmatrix. Hvis Markov-kæden har N mulige tilstande, vil matricen være en N x N-matrix, således at posten (I, J) er sandsynligheden for at overgå fra tilstand I til tilstand J. Desuden skal overgangsmatricen være en stokastisk matrix, dvs. en matrix, hvis poster i hver række skal summere til præcis 1. Dette giver fuldstændig mening, da hver række repræsenterer sin egen sandsynlighedsfordeling.

Og yderligere, har en Markov-kæde også en indledende tilstandsvektor, repræsenteret som en N x 1-matrix (en vektor), der beskriver sandsynlighedsfordelingen for at starte i hver af de N mulige tilstande. Entry I i vektoren beskriver sandsynligheden for, at kæden begynder i tilstand I.

Disse to enheder er typisk alt, hvad der er nødvendigt for at repræsentere en Markov-kæde.

Vi ved nu, hvordan vi kan få chancen for at opnå overgangen fra en tilstand til en anden, men hvad med at finde chancen for, at denne overgang sker over flere trin? For at formalisere dette ønsker vi nu at bestemme sandsynligheden for at gå fra tilstand I til tilstand J over M trin. Som det viser sig, er det faktisk meget enkelt at finde ud af dette. Givet en overgangsmatrix P kan dette bestemmes ved at beregne værdien af posten (I, J) i den matrix, der opnås ved at hæve P til potensen af M. For små værdier af M kan dette let gøres i hånden med gentagen multiplikation. For store værdier af M er det imidlertid, hvis du er fortrolig med simpel lineær algebra, en mere effektiv måde at hæve en matrix til en potens på, at du først diagonaliserer matricen.

Slutning

Nu, hvor du kender de grundlæggende principper for Markov-kæder, burde du nu være i stand til nemt at implementere dem i et sprog efter eget valg. Hvis kodning ikke er din stærke side, er der også mange mere avancerede egenskaber ved Markov-kæder og Markov-processer, som du kan dykke ned i. Efter min mening vil den naturlige progression langs den teoretiske vej være i retning af skjulte Markov-processer eller MCMC. Simple Markov-kæder er byggestenene i andre, mere sofistikerede modelleringsteknikker, så med denne viden kan du nu gå videre til forskellige teknikker inden for emner som trosmodellering og sampling.