Benannt nach Mathematiker Andrej Andreevič Markov.

Üblicherweise (aber nicht ganz trennscharf) bezeichnen Markov-Ketten Markov-Prozesse im diskreten Zustandsraum, die auch hier vorgestellt werden.

Auf Markov-Prozesse mit stetiger Zeit und/oder allgemeinem Zustandsraum wird in dieser Einführung nicht eingegangen.

Diskrete Markov-Kette (Discrete time markov-chain oder DTMC)

Voraussetzungen der DTMC:
- Konstante Wahrscheinlichkeiten
- diskreter (zählbarer) Zustandsraum
- wenn endlich viele Zustände: diskrete endliche Markov-Kette

Wichtigstes Merkmal: Die Markov-Eigenschaft

Eine Markov-Kette zielt darauf ab, basierend auf Wahrscheinlichkeiten für das Eintreten von zukünftigen Zuständen diese zu traversieren.

Besonders ist an diesem Ansatz, dass die Wahrscheinlichkeit des nächsten Zustandes ausschließlich an den direkt davor erfolgten Geschehnissen abhängt bzw. es für die Voraussage keinen Unterschied macht, wie weit in die Vergangenheit zurückgeblickt wird.

Somit ist die Markov-Kette als gedächtnislos zu bezeichnen. Im Grunde gibt es zu einem gewählten Zustand keine Informationen über die vergangenen Zustände.

“A DTMC is a stochastic process whose domain is a discrete set of states, \(\{s_{1} + s_{2} +s_{3} + \cdots + s_{k}\}\). The chain starts in a generic state at time zero and moves from a state to another by steps. Let \(p_{ij}\) be the probability that a chain currently in state \(s_{i}\) moves to state \(s_{j}\) at the next step. The key characteristic of DTMC processes is that \(p_{ij}\) does not depend upon the previous state in the chain. The probability \(p_{ij}\) for a (finite) DTMC is defined by a transition matrix […]”. (Spedicato 2017:85, The R journal)

Markov-Kette erster Ordnung

Die konsequenteste Ausführung dieses Prozesses ist die Markov-Kette erster Ordnung, wo nur ein einziger bzw. der aktuelle Zustand die Wahrscheinlichkeit des nachfolgenden Zustandes bedingt.

Eine einfache visuelle Erklärung liefern Victor Powell und Lewis Lehe hier.

Mathematische Formeln

Diskrete Markov Kette:

In Zustandsraum \(\{s_{1} + s_{2} +s_{3} + \cdots + s_{k}\}\)

gilt für die Markov-Kette:

\(P(X_{t+1}= s_{j_{t+1}} \mid X_{t} = s_{j_t},X_{t-1} = s_{j_{t-1}},\cdots,X_{0}=s_{j_{0}})\) \(=P(X_{t+1}= s_{j_{t+1}} \mid X_{t} = s_{j_{t}}\)

Formel für die Übergangswahrscheinlichkeiten:

\(p_{ij}(t):= P(X_{t+1} = s_{j} \mid X_t = s_i), i,j = 1, \cdots,m\)

Formel für die Übergangsmatrix:

\(M_t =(p_{ij}(t))_{s_i, s_j\in s}\)

Quelle: Markov chain

Visualization with markovchain package

Eine internatione Gruppe von Wissenschaftler*innen um Giorgio Alfredo Spedicato hat eigens ein markovchain-package entwickelt, das für Berechnungen und Visualisierungen mit und von Markov-Ketten gedacht ist.

Die Visualisierung kann allerdings als etwas altbacken bezeichnet werden. Hier ein Beispiel basierend auf einer möglichen verallgemeinerten Studierendenerfahrung.

Code:

# the "long approach" as defined by Spedicato et al. 
set.seed(42)
student_states <- c("studying", "tired", "sleeping")

student_matrix_base <- c(0.3, 0.6, 0.1,
                        0.1, 0.5, 0.4, 
                        0.1, 0.2, 0.7)

student_matrix <- matrix(data = student_matrix_base, 
                        byrow = TRUE,
                        nrow = 3,
                        dimnames = list(student_states, student_states))
to_study <- new("markovchain", 
                 states = student_states,
                 byrow = TRUE, 
                 transitionMatrix = student_matrix,
                 name = "Progress")

plot(to_study, main="student life")

Hinweis: Die in der Grafik angegebenen Wahrscheinlichkeiten sind zu lesen laut Schema: “vom näherstehenden zum weiter entfernten”. Reflexive Pfeile stehen für ein Verweilen im aktuellen Zustand.

Was die Grafik zeigt: Ist die studierende Person gerade am Lernen, besteht eine 30%-ige Chance, dass die Person weiterlernt (= der nächste Zustand). Mit 60% ist es aber wahrscheinlicher, dass Müdigkeit einsetzt. Nur mit 10%-iger Wahrscheinlichkeit legt die Person sich sofort aufs Ohr. Im wahrscheinlichsten, nämlich dem “müden” Zustand angekommen, besteht wiederum eine Wahrscheinlichkeit von 50%, dass die Person müde bleibt, ohne sich hinzulegen. Mit 10%-iger Wahrscheinlichkeit nimmt sie sich die Lernunterlagen noch einmal vor. Mit 40%iger Wahrscheinlichkeit aber legt sie sich hin usw.

Hier ist das Markov-Attribut der Gedächtnislosigkeit gut ersichtlich. Es hängt nur vom aktuellen Zustand ab, welche Entscheidung getroffen wird bzw. welche Wahrscheinlichkeiten dafür bestehen, dass der nächste Zustand eintritt.

Dieses simple Beispiel illustriert auch schon eine große Herausforderung in der tatsächlichen Implementierung von Markov-Chains. Denn um das Verhalten eines/einer Studierenden vorherzusagen wäre ein “Gedächtnis” hilfreich oder aber ein umfassendes Wissen über vielfältige weitere - vielleicht unerfahrbare - aktuelle Zustände notwendig (z.B. wie lange wurde geschlafen, wie spät ist es, hat die Person schon gegessen, steht morgen eine Prüfung an, usw.).

Beispiel für intuitivere Visualisierung

Victor Powell und Lewis Lehe liefern auch eine gute, anpassbare Visualisierung

Etwa lässt sich die unsere obige Studierenden-Matrix mit drei Zuständen dort leicht einfügen. Man beachte, die Spaltenwahrscheinlichkeiten summieren auf 1 bzw. 100 Prozent.

[[0.3,0.6,0.1], [0.1,0.5,0.4], [0.1,0.2,0.7]]

Hinweis: Für die Visualisierung gilt: A = studying, B = tired, C = sleeping

Fortsetzung des Studierenden-Beispiels

Es folgt die Visualisierung einer diskreten und endlichen Markov-Kette mit drei Zuständen für nicht nur eines, sondern 100 “Individuen”.

Die Code-Vorlage stammt von Will Hipson. Das Beispiel von oben wird fortgeführt: 100 Studierende sitzen entweder am Schreibtisch (studying), auf der Couch (tired), oder liegen im Bett (sleeping).

Es ist gut zu erkennen, dass von den Startwahrscheinlichkeiten bald abgewichen wird, weil die Übergangswahrscheinlichkeiten dementsprechend gegengleich verlaufen. Trotz Schwankungen ist eine klare Tendenz für jeden der Zustände erkennbar.

Die Animation verdeutlicht die Bewegung der Studierenden durch die drei Zustände noch einmal. Wie oben, starten die meisten Studierenden im Bett bzw. auf der Couch (tired).

Texvorhersage mittels Markov-Kette

Dasselbe Konzept kann auch für Textvorhersage verwendet werden. Für einen bestimmten Textkorpus kann ebenfalls eine Übergangsmatrix (bzw. Wahrscheinlichkeitsmatrix) aufgestellt werden, die für jedes Wort die Wahrscheinlichkeit angibt, dass ein bestimmtes anderes Wort darauffolgt. Die Ermittlung der Wahrscheinlichkeiten in der Matrix kann dabei einfach durch Frequenzzählung erfolgen.

Hinweis: Hieraus ergibt sich eine hochgradig sparse Matrix, weswegen in der Speicherung Schwierigkeiten auftreten bzw. man effizientere Lösungen finden muss.

Wird nun z.B. ein Wort eingegeben bzw. bildet es den aktuellen Zustand, so wird das nächste Wort anhand der gewichteten Wahrscheinlichkeiten ermittelt. Gilt etwa für das Wort „du“, dass darauf mit 60%iger-Wahrscheinlichkeit das Wort „hast“, und mit 40%iger Wahrscheinlichkeit das Wort „bist“ folgt, so wird durchschnittlich in 6 von 10 Fällen „hast“ und die übrigen Male „bist“ vorgeschlagen.

Also: \(P(hast|Du) = 0.6\)
\(P(bist|Du) = 0.4\)

Natürlich ist eine Vorhersage, die nur das jeweils vorangehende Wort mit einbezieht notgedrungen sehr simpel. Gerade bei längeren Sätzen und zusammenhängenden Texten wäre es wünschenswert, wenn der zugrundeliegende Algorithmus sehr wohl ein Gedächtnis hätte. Auch eine Markov-Kette n-ter Ordnung kann dieses Problem nicht vollständig lösen.

Du hast - Erstellung einer Übergangsmatrix auf Basis eines Texts

Man nehme irgendein Textbeispiel:
" (Du)
Du hast
Du hast mich
Du hast mich
Du hast mich gefragt
Du hast mich gefragt
Du hast mich gefragt (und ich hab nichts gesagt.)

Du bist rosa
Du bist grün
Du bist lila
Du bist blau
"

Zur Übertragung in eine Markov-Kette erstellen wir zuerst eine Zählung der Wörter, wobei gezählt wird, wie oft die Wörter jeweils aufeinander folgen.

wordslist Du hast bist mich gefragt rosa gruen lila blau
Du 0 0 0 0 0 0 0 0 0
hast 6 0 0 0 0 0 0 0 0
bist 4 0 0 0 0 0 0 0 0
mich 0 5 0 0 0 0 0 0 0
gefragt 0 0 0 3 0 0 0 0 0
rosa 0 0 1 0 0 0 0 0 0
grün 0 0 1 0 0 0 0 0 0
lila 0 0 1 0 0 0 0 0 0
blau 0 0 1 0 0 0 0 0 0

Jetzt normalisieren wir diese Tabelle, um die Wahrscheinlichkeiten in Form einer Übergangsmatrix zu erhalten:

##        Du hast bist mich gefragt rosa gruen lila blau
##  [1,] 0.0    0 0.00    0       0    0     0    0    0
##  [2,] 0.6    0 0.00    0       0    0     0    0    0
##  [3,] 0.4    0 0.00    0       0    0     0    0    0
##  [4,] 0.0    1 0.00    0       0    0     0    0    0
##  [5,] 0.0    0 0.00    1       0    0     0    0    0
##  [6,] 0.0    0 0.25    0       0    0     0    0    0
##  [7,] 0.0    0 0.25    0       0    0     0    0    0
##  [8,] 0.0    0 0.25    0       0    0     0    0    0
##  [9,] 0.0    0 0.25    0       0    0     0    0    0

Im nächsten Schritt kann man die Übergangsmatrix mit den festgestellten Wahrscheinlichkeiten analog zu oben einer Markov-Kette übergeben. Ich möchte das aber anhand eines interessanteren Beispiels zeigen, nämlich basierend auf dem orangen Mann, den die Welt schon jetzt so vermisst.

Textprädiktion basierend auf Trump-Reden

mittels Markov-Kette 2-ter Ordnung

Dasselbe Konzept findet in dem folgenden Beispiel Anwendung (basierend auf der Arbeit von Daniel Eubanks:

Allerdings wird hier mit einer Markov-Kette n-ter Ordnung gearbeitet, konkret: einer Markov-Kette zweiter Ordnung. Anstatt nur das letze Wort bzw. den aktuellen Zustand zu berücksichtigen, wird auch der Vorletzte Zustand berücksichtigt, also jeweils Wortpaare.

Außerdem wird hier nicht in Form einer Matrix abgespeichert, um dem bereits in einem Hinweis angesprochenen Speicher-Problem vorzubeugen. Stattdessen werden iterativ Wortpaare gesucht und festgehalten, auf Basis derer das dritte Wort in Form eines “Dictionaries” angelegt wird. Der key ist dabei das aktuelle Wort (hier eigentlich: die aktuellen beiden Worte/die vorausgehenden beiden Worte); die Wahrscheinlichkeiten für nachfolgende Worte sind wieder frequenziell ermittelt und angelegt.

Dazu gibt es zwei Parameter:
- stop_prob: Wahrscheinlichkeit, dass die Kette endet (hier wird berücksichtigt, dass das aktuelle “Wort” ein Satzzeichen ist)
- max_words: bestimmt einfach die maximale Länge der generierten Textkette.

Die Verschriftlichung der Trump-Reden wurden einem Dokument entnommen, das von Ryan McDermott zur Verfügung gestellt wurde.

Nach dem Einlesen des Dokuments, was bei einem Texfile von rund 569 KB schon reichlich Zeit beansprucht, werden die ermittelten Wahrscheinlichkeiten – der Logik einer Markov-Kette folgend – der entsprechenden Vorhersage-Funktion übergeben.

Hier einige Resultate:


Beispiel a): Output des Wortpaars “he has”:

##          a      small       been        one        got experience        the 
##          3          3          1          2          1          1          1

Zeigt die Frequenzen der auf “he has”, auf deren Basis die Wahrscheinlichkeiten errechnet werden (wie oben gezeigt).
Hier also mit den entpsrechenden Wahrscheinlichkeiten:

##          a      small       been        one        got experience        the 
## 0.25000000 0.25000000 0.08333333 0.16666667 0.08333333 0.08333333 0.08333333


Beispiel b): Output des Wortpaars “this is”:

##       such        how          a         an      going       what  something 
##          1          1          5          2          3          3          3 
##        the    serious   supposed      money       just     called        out 
##          5          1          1          1          1          1          1 
## terrible." Mar-a-Lago         my        one         me surprising       with 
##          1          1          1          2          1          1          1 
##     pretty          ,       hard      right 
##          1          1          1          1


Beispiel c): Output des Wortpaars “I am”:

##      doing    serious        the  skeptical    totally      proud officially 
##          2          1          1          1          2          1          1 
##          a      going         is  President         an         in          . 
##          7          2          1          1          1          3          4 
##       very 
##          1

generierter Text 1

## [1] "Show. They do negative ads on me. I'm no longer a silent majority? It's ridiculous....That's their choice. We have to be in jail for eight years, keep the oil."

generierter Text 2

## [1] "Supreme Court justices. You're going to be dying probably because of anybody else. Do you want. I killed the Applause. In fact, I've always heard if you're producing 7,000 jobs and people don't know. If anyone wants to overturn Syria. And remember this: She only got softballs. That's not a smart person like many, many years. And this is going to be America first. Both everybody is going to do the right thing by vetting these groups there. She will not hesitate to deploy military force, but it's"

generierter Text 3

## [1] "You cannot have a stock market that, frankly, I had one friend that came into strong second. In the end. Okay?"

generierter Text 4

## [1] "Okay. Are you not running and I met him and held him tight."

Fazit

Man sieht, dass die hier zur Anwendung gekommene simple Markov-Logik in diesem Fall bereits ausreicht, um zusammenhängende Sätze zu erzeugen. Das hat unter anderem damit zu tun, dass es sich um einen recht kleinen und homogenen Textkorpus handelt. Mehr Variation macht auch die Vorhersage weniger treffgenau - da auch mehr Möglichkeiten abgedeckt werden müssen. Es ist aber leicht vorstellbar, dass mit komplexeren Ketten höherer Ordnung und in Kombination anderer Methoden bzw. anderer Stochastiken ein gutes Ergebnis erzielt werden könnte.

Dass Markov-Chains besser performen können, wird auch deutlich, wenn man ein paar Einsatzgebiete betrachtet.

Einige Einsatzgebiete:

  • Versicherungsmathematik (biometrische Risiken, z.B. Sterbewahrscheinlichkeit)
  • Markov-Spamfilter
  • aber auch zur Generierung von “Spam” (online-Marketing)
  • PageRank (Google, schon im Unterricht besprochen)