Ist eine Markov-Kette dasselbe wie eine Finite-State-Maschine?

80

Ist eine endliche Zustandsmaschine nur eine Implementierung einer Markov-Kette? Was sind die Unterschiede zwischen den beiden?

math statistics state-machine fsm markov-chains Carson
quelle
24
Sie können sich eine Markov-Kette als FSM
vorstellen,

Antworten:

61

Markov-Ketten können durch endliche Zustandsmaschinen dargestellt werden. Die Idee ist, dass eine Markov-Kette einen Prozess beschreibt, bei dem der Übergang in einen Zustand zum Zeitpunkt t + 1 nur vom Zustand zum Zeitpunkt t abhängt. Die Hauptsache ist, dass die Übergänge in einer Markov-Kette eher probabilistisch als deterministisch sind, was bedeutet, dass Sie nicht immer mit absoluter Sicherheit sagen können, was zum Zeitpunkt t + 1 passieren wird.

Die Wikipedia-Artikel über Maschinen mit endlichen Zuständen enthalten einen Unterabschnitt über Prozesse der endlichen Markov-Kette . Ich würde empfehlen, diesen für weitere Informationen zu lesen. Der Wikipedia-Artikel über Markov-Ketten enthält einen kurzen Satz, der die Verwendung von Finite-State-Maschinen zur Darstellung einer Markov-Kette beschreibt. Das heißt:

Eine endliche Zustandsmaschine kann als Darstellung einer Markov-Kette verwendet werden. Unter der Annahme einer Folge unabhängiger und identisch verteilter Eingangssignale (z. B. Symbole aus einem durch Münzwürfe ausgewählten binären Alphabet) ist die Wahrscheinlichkeit, dass sich die Maschine zum Zeitpunkt n + 1 in den Zustand x bewegt, wenn sie sich zum Zeitpunkt n im Zustand y befindet hängt nur vom aktuellen Zustand ab.

James Thompson
quelle
2
Eigentlich ist das, was Sie hier über eine Markov-Kette behaupten, nicht 100% korrekt. Was Sie hier erwähnt haben, ist der "Markov-Prozess erster Ordnung". Bei einem Markov-Prozess zweiter Ordnung hängt der nächste Zustand von den Zuständen der letzten zwei Zeitschritte ab. Eine Zustandsmaschine ist ein Sonderfall einer Markov-Kette. da eine Markov-Kette stochastischer Natur ist. Eine Zustandsmaschine ist meines Wissens deterministisch.
A. Isaac
5
Unqualifiziert bedeutet der Begriff Markov-Kette einen zeitdiskreten stochastischen Prozess mit der Markov-Eigenschaft, was bedeutet, dass er nicht von früheren Zuständen abhängt. Das Originalplakat fragte nicht nach Markov-Prozessen höherer Ordnung, daher sind sie nicht wirklich relevant. Die endliche Zustandsmaschine ist im Allgemeinen ein Sammelbegriff für einen endlichen Automaten. Diese können entweder deterministischer oder nicht deterministischer Natur sein.
Tim Seguine
28

Während eine Markov-Kette eine endliche Zustandsmaschine ist, zeichnet sie sich dadurch aus, dass ihre Übergänge stochastisch, dh zufällig sind und durch Wahrscheinlichkeiten beschrieben werden.

Oliver Charlesworth
quelle
3
Danke dafür, genau das, wonach ich gesucht habe.
Stefan Mai
4
Kann ich sagen, stochastische endliche Automaten?
Souradeep Nanda
19

Die beiden sind ähnlich, aber die anderen Erklärungen hier sind etwas falsch. Nur FINITE Markov-Ketten können durch ein FSM dargestellt werden. Markov-Ketten ermöglichen einen unendlichen Zustandsraum. Wie bereits erwähnt, werden die Übergänge einer Markov-Kette durch Wahrscheinlichkeiten beschrieben, es ist jedoch auch wichtig zu erwähnen, dass die Übergangswahrscheinlichkeiten nur vom aktuellen Zustand abhängen können. Ohne diese Einschränkung würde es als "zeitdiskreter stochastischer Prozess" bezeichnet.

Tim Seguine
quelle
Eigentlich glaube ich, dass es "instationär" genannt werden würde.
Michael Tamillow
@Michael Ich könnte mich irren, weil ich eine Weile nicht mehr zum Thema gehörte, aber ich dachte, "stationär" sei zeitabhängig. Ich könnte mich irren, aber das scheint orthogonal.
Tim Seguine
"Prozess" wird typischerweise verwendet, um eine kontinuierliche zeitliche Version des Begriffs "Kette" (Referenz: Wahrscheinlichkeitstheorie: ein prägnanter Kurs, Rozanov) auszudrücken, und ein FSM kann unendlich oder ereignisgesteuert oder nicht deterministisch dargestellt werden . Die einzige andere Abhängigkeit, die ich mir neben dem Staat vorstellen kann, wäre die Zeit.
Michael Tamillow
@ Michael "Prozess" ist ein Oberbegriff. Es kann kontinuierliche Zeit oder diskrete Zeit sein. Ein FSM kann nicht unendlich dargestellt werden, es hat das Wort endlich im Namen. Der von Ihnen angegebene Link besagt sogar, dass es sich nicht um eine endliche Zustandsmaschine handelt. Sie haben die Zeitabhängigkeit nicht von mir angesprochen, aber in diskreten Zeitprozessen wird der Sequenzindex normalerweise als Zeit betrachtet. In diesem Sinne wäre ein zeitdiskreter stochastischer Prozess zwar nicht stationär, aber das ist nicht beschreibend genug, da es sich möglicherweise auch um eine kontinuierliche Zeit handeln könnte. Ich wollte eine Obermenge, nicht die Ergänzung in meiner Benennung.
Tim Seguine
7

Bitte lesen Sie diese Papiere:

Verknüpfungen zwischen probabilistischen Automaten und Hidden-Markov-Modellen (von Pierre Dupont) http://www.info.ucl.ac.be/~pdupont/pdupont/pdf/HMM_PA_pres_n4.pdf

[Das Handbuch der Gehirntheorie und neuronaler Netze] Versteckte Markov-Modelle und andere endliche Zustandsautomaten für die Sequenzverarbeitung http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.3344&rep=rep1&type=pdf

Juan Carlos Kuri Pinto
quelle
3

Ich glaube, das sollte Ihre Frage beantworten:

https://en.wikipedia.org/wiki/Probabilistic_automaton

Und Sie sind auf dem richtigen Weg - sie sind fast gleich, Teilmengen, Obermengen und Modifikationen, je nachdem, welches Adjektiv die Kette oder den Automaten beschreibt. Automaten nehmen normalerweise auch eine Eingabe entgegen, aber ich bin sicher, dass es Papiere gegeben hat, die 'Markov-Ketten' mit Eingaben verwenden.

Denken Sie an Gaußsche Verteilung vs. Normalverteilung - gleiche Ideen, verschiedene Bereiche. Automaten gehören zur Informatik, Markov zur Wahrscheinlichkeit und Statistik.

Michael Tamillow
quelle
1

Wenn Sie die inneren Arbeitsdetails beiseite lassen, ist die endliche Zustandsmaschine wie ein einfacher Wert, während die Markov-Kette wie eine Zufallsvariable ist (fügen Sie die Wahrscheinlichkeit über den einfachen Wert hinzu). Die Antwort auf die ursprüngliche Frage lautet also nein, sie sind nicht gleich. Im probabilistischen Sinne ist die Markov-Kette eine Erweiterung der Finite-State-Maschine.

liang
quelle
1

Ich denke, die meisten Antworten sind nicht angemessen. Ein Markov-Prozess wird von einer (probablistischen) endlichen Zustandsmaschine erzeugt, aber nicht jeder Prozess, der von einer probablistischen endlichen Zustandsmaschine erzeugt wird, ist ein Markov-Prozess. Beispielsweise sind Hidden-Markov-Prozesse im Grunde dieselben wie Prozesse, die von probabilistischen Finite-State-Maschinen erzeugt werden, aber nicht jeder Hidden-Markov-Prozess ist ein Markov-Prozess.

Radone
quelle