Inleiding tot Markovketens

Markovketens zijn een vrij gebruikelijke, en relatief eenvoudige, manier om willekeurige processen statistisch te modelleren. Ze zijn gebruikt in veel verschillende domeinen, variërend van tekstgeneratie tot financiële modellering. Een populair voorbeeld is r/SubredditSimulator, dat Markovketens gebruikt om de creatie van inhoud voor een volledige subreddit te automatiseren. Markov Chains zijn conceptueel vrij intuïtief en zeer toegankelijk, omdat ze kunnen worden geïmplementeerd zonder gebruik te maken van geavanceerde statistische of wiskundige concepten. Ze zijn een geweldige manier om te beginnen met het leren over probabilistische modellering en data science technieken.

Scenario

Om te beginnen, zal ik ze beschrijven met een zeer veel voorkomend voorbeeld:

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.

Dit voorbeeld illustreert veel van de belangrijkste concepten van een Markov-keten. Een Markovketen bestaat in wezen uit een reeks overgangen, die worden bepaald door een of andere waarschijnlijkheidsverdeling, die aan de Markov-eigenschap voldoen.

Zie hoe in het voorbeeld de waarschijnlijkheidsverdeling uitsluitend wordt verkregen door de overgangen van de huidige dag naar de volgende te observeren. Dit illustreert de Markov-eigenschap, de unieke eigenschap van Markov-processen die hen geheugenloos maakt. Hierdoor zijn zij doorgaans niet in staat om met succes reeksen te produceren waarin een onderliggende trend zou worden verwacht. Een Markov-keten kan bijvoorbeeld wel de schrijfstijl van een auteur nabootsen op basis van woordfrequenties, maar kan geen tekst produceren die een diepe betekenis of thematische betekenis heeft, aangezien die in veel langere reeksen tekst worden ontwikkeld. Zij missen derhalve het vermogen om context-afhankelijke inhoud te produceren, aangezien zij geen rekening kunnen houden met de volledige keten van voorafgaande toestanden.

Het model

Vormaal gesproken is een Markov-keten een probabilistische automaat. De kansverdeling van toestandsovergangen wordt typisch weergegeven als de overgangsmatrix van de Markovketen. Als de Markov-keten N mogelijke toestanden heeft, zal de matrix een N x N matrix zijn, met als invoer (I, J) de kans op overgang van toestand I naar toestand J. Bovendien moet de overgangsmatrix een stochastische matrix zijn, een matrix waarvan de waarden in elke rij precies 1 moeten zijn.

Extra, een Markov-keten ook een vector van de begintoestand, voorgesteld als een N x 1 matrix (een vector), die de kansverdeling beschrijft van de start in elk van de N mogelijke toestanden. Ingang I van de vector beschrijft de waarschijnlijkheid dat de keten in toestand I begint.

Deze twee entiteiten zijn gewoonlijk alles wat nodig is om een Markov-keten weer te geven.

We weten nu hoe we de kans op een overgang van de ene toestand naar de andere kunnen bepalen, maar hoe zit het met het bepalen van de kans dat die overgang zich in meerdere stappen voordoet? Om dit te formaliseren, willen we nu de kans bepalen om van toestand I naar toestand J te gaan over M stappen. Het blijkt dat dit eigenlijk heel eenvoudig te achterhalen is. Gegeven een transitiematrix P, kan dit bepaald worden door de waarde van ingang (I, J) van de matrix te berekenen, verkregen door P te verheffen tot de macht van M. Voor kleine waarden van M, kan dit gemakkelijk met de hand gedaan worden door herhaaldelijk te vermenigvuldigen. Echter, voor grote waarden van M, als u bekend bent met eenvoudige Lineaire Algebra, is een efficiëntere manier om een matrix tot een macht te verheffen door de matrix eerst te diagonaliseren.

Conclusie

Nu u de grondbeginselen van Markov ketens kent, zou u in staat moeten zijn om ze eenvoudig te implementeren in een taal naar keuze. Als coderen niet uw sterkste kant is, zijn er ook veel meer geavanceerde eigenschappen van Markov-ketens en Markov-processen om in te duiken. Naar mijn mening zou de natuurlijke progressie langs de theoretische route in de richting van verborgen Markovprocessen of MCMC gaan. Eenvoudige Markovketens zijn de bouwstenen van andere, meer geavanceerde modelleertechnieken, dus met deze kennis kunt u nu verder gaan met verschillende technieken binnen onderwerpen als belief modeling en sampling.