Was sind Markov-Ketten, wann verwendet man sie, und wie sie funktionieren
Markov-Ketten sind eine recht verbreitete und relativ einfache Methode zur statistischen Modellierung von Zufallsprozessen. Sie wurden in vielen verschiedenen Bereichen eingesetzt, von der Texterstellung bis zur Finanzmodellierung. Ein beliebtes Beispiel ist r/SubredditSimulator, das Markov-Ketten zur automatischen Erstellung von Inhalten für einen ganzen Subreddit verwendet. Insgesamt sind Markov-Ketten konzeptionell recht intuitiv und sehr zugänglich, da sie ohne fortgeschrittene statistische oder mathematische Konzepte implementiert werden können. Sie eignen sich hervorragend für den Einstieg in die probabilistische Modellierung und in datenwissenschaftliche Techniken.
Szenario
Zu Beginn beschreibe ich sie anhand eines sehr allgemeinen Beispiels:
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.
Dieses Beispiel veranschaulicht viele der Schlüsselkonzepte einer Markov-Kette. Eine Markov-Kette besteht im Wesentlichen aus einer Reihe von Übergängen, die durch eine Wahrscheinlichkeitsverteilung bestimmt werden, die die Markov-Eigenschaft erfüllt.
Beobachten Sie, wie im Beispiel die Wahrscheinlichkeitsverteilung allein durch die Beobachtung der Übergänge vom aktuellen Tag zum nächsten Tag erhalten wird. Dies veranschaulicht die Markov-Eigenschaft, das einzigartige Merkmal von Markov-Prozessen, das sie gedächtnislos macht. Dadurch sind sie in der Regel nicht in der Lage, erfolgreich Sequenzen zu erzeugen, in denen ein zugrunde liegender Trend zu erwarten ist. So kann eine Markov-Kette zwar den Schreibstil eines Autors auf der Grundlage von Worthäufigkeiten nachahmen, ist aber nicht in der Lage, Texte mit tiefer Bedeutung oder thematischer Aussagekraft zu produzieren, da sich diese über viel längere Textabschnitte entwickeln. Ihnen fehlt daher die Fähigkeit, kontextabhängige Inhalte zu produzieren, da sie nicht die gesamte Kette der vorherigen Zustände berücksichtigen können.
Das Modell
Formalerweise ist eine Markov-Kette ein probabilistischer Automat. Die Wahrscheinlichkeitsverteilung der Zustandsübergänge wird üblicherweise als Übergangsmatrix der Markov-Kette dargestellt. Wenn die Markov-Kette N mögliche Zustände hat, ist die Matrix eine N x N-Matrix, so dass der Eintrag (I, J) die Wahrscheinlichkeit des Übergangs vom Zustand I zum Zustand J ist. Außerdem muss die Übergangsmatrix eine stochastische Matrix sein, eine Matrix, deren Einträge in jeder Zeile genau 1 ergeben müssen. Das ist völlig sinnvoll, da jede Zeile ihre eigene Wahrscheinlichkeitsverteilung darstellt.
Zusätzlich, hat eine Markov-Kette auch einen Anfangszustandsvektor, der als eine N x 1-Matrix (ein Vektor) dargestellt wird und die Wahrscheinlichkeitsverteilung für den Start bei jedem der N möglichen Zustände beschreibt. Der Eintrag I des Vektors beschreibt die Wahrscheinlichkeit, dass die Kette im Zustand I beginnt.
Diese beiden Einheiten sind typischerweise alles, was zur Darstellung einer Markov-Kette benötigt wird.
Wir wissen jetzt, wie man die Wahrscheinlichkeit des Übergangs von einem Zustand in einen anderen erhält, aber wie sieht es mit der Wahrscheinlichkeit aus, dass dieser Übergang über mehrere Schritte erfolgt? Um dies zu formalisieren, wollen wir nun die Wahrscheinlichkeit des Übergangs vom Zustand I zum Zustand J über M Schritte bestimmen. Wie sich herausstellt, ist dies eigentlich sehr einfach herauszufinden. Bei einer Übergangsmatrix P kann dies durch Berechnung des Wertes des Eintrags (I, J) der Matrix bestimmt werden, den man erhält, wenn man P mit M potenziert. Für kleine Werte von M kann dies leicht von Hand durch wiederholte Multiplikation geschehen. Für große Werte von M, wenn Sie mit einfacher Linearer Algebra vertraut sind, ist es jedoch effizienter, eine Matrix zunächst zu diagonalisieren.
Abschluss
Nachdem Sie nun die Grundlagen der Markov-Ketten kennen, sollten Sie in der Lage sein, sie in einer Sprache Ihrer Wahl zu implementieren. Wenn Programmieren nicht Ihre Stärke ist, gibt es auch viele fortgeschrittenere Eigenschaften von Markov-Ketten und Markov-Prozessen, in die Sie eintauchen können. Meiner Meinung nach wäre die natürliche Weiterentwicklung der Theorie in Richtung Hidden Markov Processes oder MCMC. Einfache Markov-Ketten sind die Bausteine für andere, anspruchsvollere Modellierungstechniken. Mit diesem Wissen können Sie nun zu verschiedenen Techniken innerhalb von Themen wie Glaubensmodellierung und Stichprobenverfahren übergehen.