27. Markow-Ketten

(1)

Holt euch von der Webseite zur Vorlesung das Skript markovmodel.py. Seht euch darin die Klasse DistFunc an – mit ihr werden wir nachher den jeweils nächsten Schritt ziehen. Sie wird mit einer Verteilung konstruiert (hier einfach eine Liste von Zahlen). Ruft man draw() oft genug auf, sollten die Ergebnisse auf Dauer entsprechend der übergebenen Verteilung verteilt sein. Könnt ihr sehen, wie das hier funktioniert? Probiert aus, ob das stimmt. Benutzt dafür Code, der etwa so aussieht:

for val in DistFunc([1,1,1]).sampleRandomly(1000):
  print val

Schickt die Ausgabe in einer Pipe durch sort | uniq -c – die Zahlen von 0 bis 2 sollten etwa gleich häufig vorkommen. Probiert das auch mit anderen Verteilungen.

(2)

Verschafft euch einen groben Überblick über MarkovModel. Der Konstruktor des MarkovModels bekommt ein Dictionary-Literal in einem String übergeben und baut daraus eine Listen von Listen, f, bei der in jeder Unterliste die Wahrscheinlichkeit für einen Übergang vom Zustand index-der-unterliste in den Zustand index-in-der-liste steht. Das brauchen wir z.B. in computePathProb, um die Wahrscheinlichkeit auszurechnen, dass eine bestimmte Zustandsfolge vom gegebenen Markov-Modell erzeugt wird. Daraus baut die Klasse anschließend eine Liste von DistFuncs, mit der wir z.B. in driveOn den nächsten Zustand ziehen können.

(3)

Seht euch an, wie das Markov-Modell einen (periodischen) Random Walk durchführt. Benutzt dafür das Modell

{
0: {1:0.5,-1:0.5},
1: {0:0.5,2:0.5},
2: {1:0.5,-2:0.5},
-1: {-2:0.5,0:0.5},
-2: {-1:0.5,2:0.5},
}

– ihr könnt das in eine Datei schreiben und ihren Inhalt dann beim Konstruieren an das MarkovModelübergeben. Seht euch zunächst ein paar kurze Zustandsfolgen an (vielleicht zehn Schritte lang), um ein Gefühl zu bekommen, was da so passiert. Erzeugt dann eine lange Zustandsfolge (vielleicht 1000 Schritte lang) und lasst euch die Verteilung der Zustände innerhalb dieser Folge ausgeben – am einfachsten geht das wieder mit den üblichen Unix-Tools durch

python markovmodel.py randomWalk.txt | sort | uniq -c

Verändert jetzt z.B. die 2 in der Zeile für den Zustand 1 in z.B. eine eins. Wie verändert sich die Verteilung der Zustände?

(4)

Lasst jetzt 100 Mal hintereinander ein zufällig aufgesetztes Markovmodell für zehn Schritte laufen und lasst euch die summierte Verteilung der Zustandsfolgen ausgeben. Das geht z.B. mit folgendem Code und der Kommandozeile oben

  for i in xrange(100):
    m.setUpUniform()
    print "\n".join(map(str, m.getAPath(10)))

Auch hier sollte wieder eine Gleichverteilung herauskommen. Dies ist ein Spezialfall eines wichtigen Begriffs, nämlich der Ergodizität. Im Groben sind Systeme ergodisch, wenn das Mittel einer Eigenschaft über ganz viele Kopien (Scharmittel) dem Mittel dieser Eigenschaft über einen ganz langen Lauf eines Systems entspricht (Zeitmittel). Kurz: Zeitmittel=Scharmittel.

Die Ergodizität eines Markov-Modells ist sehr kritisch für seine einfache Trainierbarkeit. Im Allgemeinen sind Markov-Modelle, in denen alle Zustände in alle übergehen können, ergodisch und damit harmlos.

(5)

Um ein einfaches Beispiel für nichtergodische Systeme zu haben, nehmt folgendes Markovmodell:

{
0: {1:0.5,-1:0.5},
1: {0:0.5,2:0.5},
2: {1:0.5,-2:0.5},
-1: {-2:0.5,0:0.5},
-2: {-2:1},
}

Wiederholt den Vergleich von Zeitmittel (eine lange Kette) zu Scharmittel (viele kurze Ketten) aus den letzten beiden Aufgaben. Woher kommt das nichtergodische Verhalten?

(6)

Die MarkovModel-Klasse kann auch Fälle, in denen Zustände wirklich ” absorbierend“ sind in dem Sinn, dass eine Exception ausgelöst wird, wenn das Modell in den betreffenden Zustand kommt. Nehmt folgende Übergangsverteilungen:

{
0: {0:0.5, 1:0.5,-1:0.5,-2:0.5,2:0.5},
1: {0:0.5, 1:0.5,-1:0.5,-2:0.5,2:0.5},
2: {0:0.5, 1:0.5,-1:0.5,-2:0.5,2:0.5},
-1: {0:0.5, 1:0.5,-1:0.5,-2:0.5,2:0.5},
-2: {},
}

– damit wir nachher leichter rechnen können, verlassen wir jetzt den Random Walk und lassen alles in alles übergehen (für die Normierung sorgt nachher MarkovModel selbst). Wir interessieren und jetzt für die Lauflänge eines Markow-Modells, bis es in den absorbierenden Zustand kommt. Das ist häufig eine interessante Frage (allerdings meines Wissens selten in der Sprachverarbeitung, ihre Untersuchung ist aber für das Verständnis von Markowprozessen trotzdem hilfreich).

Diese Lauflänge L ist eine Zufallsvariable (über welchem Ω?). E(L) kann ganz gewöhnlich als ∑ _l=1^∞lP(L= l) ausgerechnet werden. P(L= l) lässt sich am besten als Wahrscheinlichkeit auffassen, dass der Pfad bis l-1 nicht absorbiert wurde, das aber bei l passiert.

Woher bekommen wir P(L= l)? Wegen der Gleichverteilung, die wir ” erzwungen“ haben, ist das hier nicht schwer. Wir haben l-1 Schritte eine Wahrscheinlichkeit von 0.2 gehabt, absorbiert zu werden und haben das vermieden (mithin mit Wahrscheinlichkeit 0.8) und sind beim l-ten Mal in die Falle getappt (wofür die Wahrscheinlichkeit 0.2 war).

Wir haben damit P(L= l) = 0.8^l-1 ×0.2.

Im allgemeinen Fall ist das viel komplizierter – ihr könnt ja eine Weile grübeln, wie sowas mit dem Markovmodell aus der letzten Aufgabe aussehen würde. Aber grübelt nicht so lang.

Jetzt können wir die Summe oben als

Prüft dieses Ergebnis empirisch nach: Mit dem obigen Automaten wirft driveOn eine Exception, wenn es im absorbierenden Zustand landet. getAPath bricht dann die Generierung des Pfads ab, und die Länge des Pfades gibt gerade L. computeLExpect nutzt das aus. Interessant bei der Sache ist auch, das Gesetz der großen Zahlen in Aktion zu sehen, wenn ihr mit ” großen Zahlen“ in die Zahl der Experiment geht.

Wenn euch das näher interessiert: Man kann hier allerlei Statistiken darüber anstellen, welche Pfade wie häufig vorkommen. Das ist mit unserem vereinfachten Modell langweilig, mit den nicht vollständig durchverbundenen Modellen oben aber recht spannend.