Eine Einführung in zeit-diskrete homogene Markov-Ketten


Forschungsarbeit, 2010

16 Seiten, Note: 1.0


Leseprobe

Inhaltsverzeichnis

1 Informationen
1.1 Abstract und Motivation
1.2 Abgrenzung
1.3 Claim: Anspruch dieses Papers
1.4 Konventionen

2 Markov-Ketten: Beispiele und Lösung
2.1 Grundlagen
2.1.1 Generelle Stochastische Petrinetze
2.1.2 Rankings und Empfehlungen
2.2 Markov-Eigenschaft
2.3 Allgemeine Lösung von Markov-Ketten
2.4 Zukünftige Marktanteile mit Markov-Ketten bestimmen
2.5 Ein Beispiel für Markov-Ketten

3 Anwendungsgebiete
3.1 Anwendung von Markov-Ketten
3.2 Wo kann man Markov-Ketten einsetzen?
3.3 Vor- und Nachteile

4 Resumée

5 Danksagungen

6 Quellenverzeichnis

1 Informationen

1.1 Abstract und Motivation

Markov-Ketten sind ein einfaches und anschauliches Modell um realweltliche Vorgänge mathematisch abzubilden. Bei bekannten und als konstant angenommenen Wahrscheinlichkeiten (siehe Abgrenzung) ist es möglich den wahrscheinlichen Zustand eines Systems in beliebiger Zukunft vorherzusagen. Markov-Ketten sind häufig die Grundlage für stochastische Prozesse, die

1. auf gedächtnislosem Zufall basieren [1, S.218-219] [9, S.1] [18, S.4] und
2. bei welchen Zustandsübergänge zu jeweils gegebenen Wahrscheinlichkeiten [9, S.2] [13, 14]

möglich sind. Liegen realweltliche Modelle vor, die sich mit den beiden oben genannten Eigenschaften modellieren lassen so ist die Anwendung von Markov-Ketten möglich [3, S.9-16] [3, S.22][6][14]. Zudem sind Markov- Ketten geeignet um subjektive Bewertungen unter Objekten in einem System objektiv auszuwerten. Ein Beispiel dafür ist Google’sTM PageRankTM Algorithmus. Ein Beispiel dazu folgt bei den Anwendungen für Markov-Ketten. [7, S.1-2]

Markov-Ketten sind eine Reihe von Zuständen. Das System beinhaltet mögliche Zustände, die mit gewissen Wahr- scheinlichkeiten erreicht werden können. Dieses System lässt sich als (n × n)-Matrix darstellen. Die Zeile gibt den aktuellen Zustand an. Die Spalten alle erreichbaren. Die Einträge in der Matrix sind dabei die Wahrscheinlichkeiten gegeben einen bestimmten Zustand in einen anderen zu kommen oder in diesem zu verbleiben. Die Lösung der Markov-Kette zu einer Zeit t k gibt die Wahrscheinlichkeit an, mit welcher ich mich nach insgesamt k Schritten in einem anderen Zustand befinde. Für k → + gibt sie die allgemeine Aufenthaltswahrscheinlichkeit in jedem Zustand an.

Anwendungsgebiete

Mit fortgeschrittenen Methoden ist es auch möglich Spamfilter, welche weitaus effektiver als der bekannte Bayesfilter sind, mittels Markov-Ketten zu implementieren.[19] Weiter kann man mit Markov-Ketten unter Anderem Warteschlangenprozesse, Geburts- und Todesprozesse sowie Wahrscheinlichkeitsverteilungen von Objekten in bewegten Systemen berechnen. [1, S.245-246] [21, S.7]

Zusätzlich ist es möglich anhand vieler subjektiver Empfehlungen ein objektives Ranking für das gesamte System anzulegen. Dafür reichen einige wenige fragmentierte und möglicherweise geclusterte Entscheidungen aus. Die Güte des gesamten Rankings steigt jedoch mit der Anzahl der Bewertungen. [2, 7, 8, 17]

1.2 Abgrenzung

Markov-Ketten können Systeme abbilden und mathematisch modellieren. Daraus lassen sich einfach Wahrschein- lichkeiten für das Eintreten von Zuständen errechnen. Das System muss sich hierfür modelliert immer in genau einem solchen Zustand befinden. Die Zeit der Übergänge zwischen Zuständen werden als infinitisimal klein ange- nommen. [12]

In diesem Paper wird die Thematik der zeitdiskreten und homogenen Markov-Ketten eingeführt. Der Begriff homogen wird in diesem Zusammenhang auch synonym mit “zeitinvariant” gesetzt: die Wahrscheinlichkeiten einen anderen Zustand zugelangen sind also nicht von der Zeit, sondern nur vom aktuellen Zustand, abhängig. Der Begriff zeit-diskret beschreibt eine Eigenschaft, dass ein endlicher Zustandsraum vorliegt. Es existieren diskrete, abzählbare Zeitpunkte und keine Intervalle. Diese Zustände t k können voneinander verschiedene Abstände zum jeweiligen Nachfolger t k +1 haben. Der Zustand zum Zeitpunkt t k ist im Allgemeinen verschieden vom Zustand zum Zeitpunkt t k +1 , für k ∈ N0. [1, S.236-237] [3, S.12-13]

1.3 Claim: Anspruch dieses Papers

Dieser Artikel soll ihnen einen adäquaten Einstieg in das Thema Markov-Ketten liefern. Auch ohne explizite Vorkenntnisse von Stochastik, Modellierung, etc. sollten Sie den Texten folgen können. Grundlegende Kenntnisse in Matrix-Vektor- und Matrix-Matrix-Multiplikation werden benötigt. Das letzte Drittel bietet traditionell einen weiteren Ausblick.

1.4 Konventionen

In diesem Paper verwenden wir folgende Variablen und Ausdrü>1. Anzahl aller erreichbaren von einander verschiedenen Systemzustände n

2. k sei der aktuelle Zustand im System oder zukünftige Zustände darin

3. Funktion a (t k) gebe die Position an, in welchem sich das System zur Zeit t k befindet

4. Wahrscheinlichkeitsübergangsmatrix P ∈ R n × n

5. Schattenmatrix S ∈ R n × n liege “hinter” der Matrix P

6. Wahrscheinlichkeitsübergangsmatrix mit eingerechneter Schattenmatrix P S ∈ R n × n

7. mit jeweils den Einträgen p ij ∈ P bzw. p s ij ∈ P S

(a) die Zeilen i bezeichnen die Zustände im gesamten System, wobei

(b) die Spalten j die Wahrscheinlichkeiten abtragen um von i nach j zu gelangen

8. Irrtumswahrscheinlichkeit ε , dass es eine andere, bessere Alternative gibt

9. n verscheidene Zeilenvektoren r i für i = 1 , 2 , . . . , n, aus der Matrix P

10. aktuelle Wahrscheinlichkeitsverteilung π k im Zustand k des Systems

Der Unterschied zwischen k und i ist wie folgt anzusehen: ist k = x so befinden wir uns im x -ten Schritt der Markov-Kette. Es gab also keinen oder (x − 1) Schritte davor. Ist i = x so befinden wir uns an der Position a (x) in der Markov-Kette. Die Wahrscheinlichkeiten jetzt in den nächsten Zustand j zu gelangen werden durch den die Wahrscheinlichkeitsverteilung π i j = π k , j -tes Element im Vektor π i , oder den Wert in p ij aus P angegeben. j [5, S.1-9] [6, S.1-10]

Die Wahrscheinlichkeit ε, dass eine andere Lösung trotz dieser Bewertungen die beste ist. ε ∈ R ist für ge- wöhnlich ein sehr kleiner Wert 0 < ε ≪ 1, kann allerdings im Fall des GoogleTM PageRankTM auch 0 . 15 15% betragen. [8, S.1-7] [15, S.1-4]

Die Schattenmatrix S ist die vollverknüpfte Matrix mit den, für gegebenes ε und n, konstanten Einträgen [2, 8, 17]

Abbildung in dieser Leseprobe nicht enthalten

Die Schattenmatrix S wird auf die Matrix P addiert. Um die Eigenschaft, die Zeilensumme muss Eins ergeben, zu erfüllen wird die Matrix P mit dem Faktor (1 − ε) gewichtet. So ergibt sich folgender Zusammenhang: die Schattenmatrix S wird zusammen mit der “einfachen” Wahrscheinlichkeitsübergangsmatrix P, gewichtet zu P S . Es gilt: [2, 7, 8, 17]

Abbildung in dieser Leseprobe nicht enthalten

Die Verwendung von P und P S ist äquivalent. Der einzige Unterschied ist, dass in P S die Schattenmatrix einbezogen worden ist. Wird hierbei vereinfacht von P gesprochen so lässt sich das Vorgehen in der Regel eins zu eins auf die Matrix P S übertragen, sofern es nicht anders angezeigt worden ist. Der Umkehrschluss von P S zu P gilt im Allgemeinen aber nicht, da P S eine spezielle Ausprägung von P ist.

Zur Vereinfachung wird in den einführenden Beispielen ε:= 0 angenommen. Die Schattenmatrix wird also nicht in das Modell eingerechnet um die Komplexität am Anfang zu minimieren. Näheres zu der Schattenmatrix S und der aggregierten Matrix P S wird im Beispiel des PageRankTM-Algorithmus’ erklärt. Wir nehmen alle Wahrscheinlichkeiten innerhalb unserer Markov-Kette als positive, aber nicht notwendigerweise streng positive Werte an. Es gilt für gegebene Wahrscheinlichkeiten p ij: 0 ≤ p ij ≤ 1, p ij ∈ R. [20, S.5-10]

2 Markov-Ketten: Beispiele und Lösung

2.1 Grundlagen

Markov-Ketten können hauptsächlich zwei Arten von Systemen modellieren: generelle Stochastische Petrinetze und Rankings aufgrund von subjektiven Empfehlungen. [2, 17] [3, S.22]

2.1.1 Generelle Stochastische Petrinetze

Der Einsatz von Markov-Ketten bietet an, wenn Modelle vorliegen, die sich auch als Generelle Stochastische Petrinetze (GSPN) modellieren lassen. [3, S.22] Das System muss folglich aus einer festen Anzahl von Zuständen bestehen. Zusätzlich müssen für alle Zustände die jeweiligen Wahrscheinlichkeiten für den Übergang in alle anderen Zustände vorliegen. Sind diese Wahrscheinlichkeiten in jedem Punkt in der Summe eins so kann daraus eine Markov-Kette gebildet werden. Hierbei werden wir uns auf zeit-diskrete homogene Markov-Ketten beschränken. Das heißt, dass die Wahrscheinlichkeiten nicht mit der Zeit variieren.

Mittels der stochastischen Wahrscheinlichkeiten für den Übergang eines Zustandes in einen anderen können hierbei Verteilungen in naher bis weit entfernter Zukunft vorhergesagt werden. Die für weit entfernte Zeiten getroffenen Aussagen sind dabei die Verteilungen des Systems im Allgemeinen. [22, S.2-4]

Können die Markov-Ketten homogen oder inhomogen sein so spricht man hierbei kurz auch von DTMC für discrete time markov chains. [3, S.12-16]

2.1.2 Rankings und Empfehlungen

Eine zweite hauptsächliche Anwendung findet sich bei subjektiven Rankings. Gegeben einer Zahl von Bewertungen kann ein objektives Gesamtranking für ein System erstellt werden. Die Güte dieses Gesamtrankings nimmt mit der Anzahl der subjektiven Einzelentscheidungen zu.

Ein Beispiel hierzu: In einem sozialen Netzwerk bewertet jedes Mitglied unter einem bestimmten, gleichen Aspekt seine Freunde. Er vergibt hierbei die subjektiven Empfehlungen. Je stärker gewichtet man seine Empfeh- lungen einer anderen Person gibt, desto “wichtiger” wird sie im gesamten System. Vergibt sie wiederum Emp- fehlungen an eine dritte Person, so wird diese Empfehlung stärker durch das Gewicht und die “Wichtigkeit” der Person, die sie empfohlen hat. Dieses Verhalten setzt sich rekursiv durch die gesamte Markov-Kette fort. Somit müssen keine expliziten Gewichtungen der Empfehler verteilt werden. Sie ergeben sich implizit zur Laufzeit.

Stellt man hierzu eine Markov-Kette auf, so kann für den Aspekt ein Ranking des gesamten Netzwerkes gebil- det werden. Je mehr Bewertungen vorliegen und je mehr Freunde alle Mitglieder im Schnitt haben, also je näher das Netzwerk am vollvermaschten Netzwerk ist, desto besser wird des als objektiv anzusehende Ranking.

Über die Güte des möglichen Ergebnisses kann aufgrund fehlender Erfahrung nur spekuliert werden. Der Clou ist, dass man nur transitiv alle Mitglieder als Freundes-Freunde kennen sollte. Somit bewertet man diese über Freunde von Freunden, oder Freunde von Freundes-Freunden, etc. Das einzige Problem sind abgeschlossene Cliquen ohne Kontakte zum Rest des Netzwerkes. [2, 17]

2.2 Markov-Eigenschaft

Gedächtnisloser Zufall bezieht sich auf eine Eigenschaft ähnlich dem Würfelwurf. Diese hängen, wie das Spielen eines Würfels, nicht vom vorhergehenden Zustand ab. Das ist die sogenannte Markov-Eigenschaft. Sie besagt, dass der nächste Zustand nur vom aktuellen abhängen darf. Alle früheren Zustände haben keinen Einfluss auf Änderungen und müssen folglich nicht betrachtet werden. [18, S.5]

2.3 Allgemeine Lösung von Markov-Ketten

Die Lösung für Markov-Ketten im Unendlichen lässt sich mittels dreier Verfahren ermitteln: die Matrix-Potenzierung, die rekursive Matrix-Vektor-Multiplikation und das direkte Lösen mit der Gauss’schen Eliminierung. Auf letztere soll allerdings hier nicht näher eingegangen werden. [9, 10] [22, S.2-32]

Matrix-Vektor-Multiplikation

Dieses Verfahren ist das Einfachste. Die Wahrscheinlichkeiten im k -ten Zustand werden ermittelt durch folgende rekursive Formel:

Abbildung in dieser Leseprobe nicht enthalten

Das heißt, dass sich die nächste Verteilung π k aus der Verteilung davor, π k − 1 und der Anfangsverteilung π 0 ergibt.

Die Anfangsverteilung π 0 wird mit steigendem k immer weniger relevant für die Lösung π k. Für lim k → + gilt auch π k = 1 0 ··· 0 * P k. Der stochastische Vektor auf der linken Seite extrahiert hierbei einen der n Zeilenvektoen aus P. Der Einfachheit halber nehmen wir den Obersten.

Es kann hierfür jeder beliebige stochastische Vektor genommen werden. Da alle Zeilen in P gleich sind muss nur die Summe der Einträge im extrahierenden Vektor eins ergeben.

Das Verfahren iteriert solange bis die Differenz aus π k und π (k − 1) hinreichend klein geworden ist. Der Computer kann aufhören, wenn die Genauigkeit im Speicher nicht durch weitere Berechnungsschritte erhöht werden kann. Die Berechnung von π k wird solange für eine Genauigkeitsschwelle λ durchgeführt bis die Zeilenweise summierte Differenz hinreichend genau gegen null konvergiert ist: [18, S.6-10]

Abbildung in dieser Leseprobe nicht enthalten

λ muss kleiner sein als die Länge des Vektors π (k − 1) − π k. Ob < oder ist in diesem Fall Definitionssache. [2, 6] Die Lösung nach Abbruch des Verfahrens ist gegeben durch π k. Üblicherweise sollte die Genauigkeitsschwelle λ im Bereich von 10 [6]oder kleiner liegen.

Die zueinander korrespondierenden Werte in π (k − 1) und π k konvergieren gegen denselben Grenzwert. Dieser Grenzwert z in π k, also π k z,istfür k → + diegenauemathematischeLösungfürdiesenEintrag π k z -alsoden damit beschriebenen Zustand z nach k Iterationen.

Die Methode der Matrix-Vektor-Multiplikation wird für lim k → + ∞ , solange der Lösungsvektor mittels der letzten Verteilung π (k − 1) neu berechnet bis sich der Lösungsvektor π k verglichen mit seinem Vorgänger π (k − 1) sich nicht mehr ändert. [2, 6, 17] [5, S.1-9]

Matrix-Potenzierung

Für die Matrix-Potenzierung wird die Matrix solange mit sich selbst potenziert bis alle Zeilenvektoren[Abbildung in dieser Leseprobe nicht enthalten] in P respektive P S gegen den gleichen, konstanten Wert konvergiert sind. [2, 6, 14, 17] [5, S.1-9] [22, S.2-9] Hier müssen alle Einträge p ij bzw. p S ij zeilenweise gleich sein oder müssen hinreichend genau gerundet als gleich angesehen werden können. Das heißt, die Werte sollten in der mathematischen ε - Umgebung, der Name (nicht das ε der Schattenmatrix), um den Grenzwert liegen.

Für n voneinander verschiedene Zustände ist die Wahrscheinlichkeitsmatrix P gegeben. Wir verwenden innerhalb der Matrix P Zeilenvektoren r i für die i -te Zeile. Von jedem Zustand k muss das System immer einen neuen Zustand k + 1 , wobei im Allgemeinen a (k) = a (k + 1) gilt, erreichen können. Folglich gilt, dass aus jedem beliebigen Zustand es einen genau definierten Nachfolger geben muss:

Abbildung in dieser Leseprobe nicht enthalten

Die Wahrscheinlichkeiten vom k -ten Zustand in den (k + 1)-ten Zustand überzugehen, wobei a (k) = a (k + 1) auch möglich sein kann, werden in jeder Matrix P auf der Hauptdiagonalen p ii , für[Abbildung in dieser Leseprobe nicht enthalten]abgetragen. Das heißt, dass ausgehend vom jetzigen Zustand k auf jeden Fall ein anderer oder eben derselbe Zustand erreich- bar sein muss. Die Wahrscheinlichkeiten r i j geben jeweils an wie hoch die Wahrscheinlichkeit ist von i nach j zu gelangen. Bei homogenen Markov-Ketten ist dieser Wert konstant, hängt also nur vom aktuellen Zustand, nicht aber von k oder t k, ab. Bei zeitvarianten, also inhomogenen Markov-Ketten hängen die Wahrscheinlichkeiten für die Übergänge vom k -ten zum (k + 1)-ten Zustand überzugehen von n ab. [6, 9, 10] Es gilt bei inhomogenen Markov-Ketten also P (k) bzw. P S (k) statt nur P bzw. P S, wie bei zeitinvarianten Markov-Ketten.

Dieses Verfahren lässt sich intuitiv aus der Matrix-Vektor-Multiplikation erkennen oder mittels struktureller Induktion herleiten bzw. beweisen. Man erhält daher eine Kette von Matrix-Multiplikationen à la P * P * · · · * P und den Initialzustand [18, S.8-9] . Äquivalent gilt das Vorgehen auch für P S. Die Matrizen P und P S sind hierbei nicht variabel. Wir errinnern uns, dass π 0 für k = 0 unsere Wahrscheinlichkeiten im Ausgangszustand ist. So ergibt sich für die Lösung der Markov-Kette für k → + folgende Gleichung. π k = π (k − 1) * P.

Mittels der Potenzierung der Wahrscheinlichkeitsmatrix P kann die Lösung wie folgt errechnet werden.

Abbildung in dieser Leseprobe nicht enthalten

Die Matrix P wird mit dem stochastischen Vektor (1 0 ··· 0 )multipliziert, um die erste Zeile aus P zu erhalten. Hierbei kann jeder beliebige stochastischer Vektor[Abbildung in dieser Leseprobe nicht enthalten], der die Eigenschaft[Abbildung in dieser Leseprobe nicht enthalten]erfüllt, verwendet werden. Der Grund hierfür ist, dass jeder Zeilenvektor[Abbildung in dieser Leseprobe nicht enthalten]der Matrix P gegen denselben Zeilenvektor r i konvergiert. Diese Zeilenvektoren sind die Lösung der Markov-Kette im Unendlichen. [18, S.6-10]

[...]

Ende der Leseprobe aus 16 Seiten

Details

Titel
Eine Einführung in zeit-diskrete homogene Markov-Ketten
Hochschule
Otto-von-Guericke-Universität Magdeburg  (Fakultät für Informatik)
Veranstaltung
Grundlegende und Fortgeschrittene Simulationsmethoden
Note
1.0
Autor
Jahr
2010
Seiten
16
Katalognummer
V164218
ISBN (eBook)
9783640797400
ISBN (Buch)
9783640797080
Dateigröße
3557 KB
Sprache
Deutsch
Schlagworte
Eine, Einführung, Markov-Ketten
Arbeit zitieren
Daniel Schulz (Autor), 2010, Eine Einführung in zeit-diskrete homogene Markov-Ketten, München, GRIN Verlag, https://www.grin.com/document/164218

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Eine Einführung in zeit-diskrete homogene Markov-Ketten



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden