Introduktion till Markovkedjor

Markovkedjor är ett ganska vanligt och relativt enkelt sätt att statistiskt modellera slumpmässiga processer. De har använts inom många olika områden, allt från textgenerering till finansiell modellering. Ett populärt exempel är r/SubredditSimulator, som använder Markovkedjor för att automatisera skapandet av innehåll för en hel subreddit. På det hela taget är Markovkedjor konceptuellt sett ganska intuitiva och mycket lättillgängliga, eftersom de kan genomföras utan att man behöver använda avancerade statistiska eller matematiska begrepp. De är ett utmärkt sätt att börja lära sig om probabilistisk modellering och datavetenskapstekniker.

Scenario

För att börja kommer jag att beskriva dem med ett mycket vanligt exempel:

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.

Det här exemplet illustrerar många av de viktigaste begreppen i en Markovkedja. En Markovkedja består i huvudsak av en uppsättning övergångar, som bestäms av en viss sannolikhetsfördelning, som uppfyller Markov-egenskapen.

Observera hur sannolikhetsfördelningen i exemplet erhålls enbart genom att observera övergångar från den aktuella dagen till nästa. Detta illustrerar Markov-egenskapen, den unika egenskap hos Markov-processer som gör dem minneslösa. Detta gör att de vanligtvis inte kan producera sekvenser där någon underliggande trend förväntas uppstå. Även om en Markov-kedja till exempel kan efterlikna en författares skrivstil på grundval av ordfrekvenser, kan den inte producera text som innehåller djupa innebörder eller tematiska betydelser, eftersom dessa utvecklas under mycket längre textsekvenser. De saknar därför förmågan att producera kontextberoende innehåll eftersom de inte kan ta hänsyn till hela kedjan av tidigare tillstånd.

Modellen

Formellt sett är en Markov-kedja en probabilistisk automat. Sannolikhetsfördelningen för tillståndsövergångar representeras vanligtvis som Markovkedjans övergångsmatris. Om Markovkedjan har N möjliga tillstånd kommer matrisen att vara en N x N-matris, så att posten (I, J) är sannolikheten att övergå från tillstånd I till tillstånd J. Dessutom måste övergångsmatrisen vara en stokastisk matris, en matris vars poster i varje rad måste summera till exakt 1. Detta är helt logiskt, eftersom varje rad representerar sin egen sannolikhetsfördelning.

Tillfälligt, har en Markovkedja också en initial tillståndsvektor, representerad som en N x 1-matris (en vektor), som beskriver sannolikhetsfördelningen för att starta i vart och ett av de N möjliga tillstånden. Inträdet I i vektorn beskriver sannolikheten för att kedjan börjar i tillstånd I.

Dessa två entiteter är typiskt sett allt som behövs för att representera en Markovkedja.

Vi vet nu hur man får fram chansen att övergå från ett tillstånd till ett annat, men hur kan man hitta chansen att denna övergång sker över flera steg? För att formalisera detta vill vi nu bestämma sannolikheten för att gå från tillstånd I till tillstånd J över M steg. Det visar sig att detta faktiskt är mycket enkelt att ta reda på. Givet en övergångsmatris P kan detta bestämmas genom att beräkna värdet av posten (I, J) i matrisen som erhålls genom att höja P till potensen av M. För små värden på M kan detta lätt göras för hand med upprepad multiplikation. För stora värden av M, om du är bekant med enkel linjär algebra, är dock ett effektivare sätt att höja en matris till en potens att först diagonalisera matrisen.

Slutsats

Nu när du känner till grunderna för Markovkedjor bör du nu enkelt kunna implementera dem i ett språk som du väljer. Om kodning inte är din starka sida finns det också många mer avancerade egenskaper hos Markovkedjor och Markovprocesser att fördjupa sig i. Enligt min åsikt skulle den naturliga utvecklingen längs den teoretiska vägen vara mot dolda Markovprocesser eller MCMC. Enkla Markovkedjor är byggstenar för andra, mer sofistikerade modelleringstekniker, så med denna kunskap kan du nu gå vidare till olika tekniker inom ämnen som t.ex. trosmodellering och sampling.