Beispiele aus der Praxis für Markov-Entscheidungsprozesse

20

Ich habe viele Tutorial-Videos gesehen und sie sehen gleich aus. Dieses Beispiel: https://www.youtube.com/watch?v=ip4iSMRW5X4

Sie erklären Zustände, Handlungen und Wahrscheinlichkeiten, die in Ordnung sind. Die Person erklärt es ok, aber ich kann einfach nicht in den Griff bekommen, wofür es im wirklichen Leben verwendet werden würde. Bisher habe ich noch keine Listen gefunden. Das häufigste, das ich sehe, ist Schach.

Kann man damit Dinge vorhersagen? Wenn ja, welche Arten von Dingen? Kann es Muster in unendlich vielen Datenmengen finden? Was kann dieser Algorithmus für mich tun?

Bonus: Es fühlt sich auch so an, als ob es bei MDP darum geht, von einem Staat in einen anderen zu gelangen, stimmt das?

Karl Morrison
quelle

Antworten:

28

Ein markovianischer Entscheidungsprozess hat in der Tat mit dem Übergang von einem Staat in einen anderen zu tun und wird hauptsächlich für die Planung und Entscheidungsfindung verwendet .

Die Theorie

Nur die Theorie schnell zu wiederholen, ist ein MDP:

MDP=S,A,T,R,γ

SATPr(s|s,a)Rγ

Um es nutzen zu können, müssen Sie Folgendes vordefiniert haben:

  1. Zustände : Diese können sich zum Beispiel auf Grid Maps in der Robotik beziehen , oder zum Beispiel auf Tür offen und Tür geschlossen .
  2. Aktionen : Ein fester Satz von Aktionen, z. B. für einen Roboter nach Norden, Süden, Osten usw. oder zum Öffnen und Schließen einer Tür.
  3. Übergangswahrscheinlichkeiten : Die Wahrscheinlichkeit, bei einer bestimmten Aktion von einem Zustand in einen anderen überzugehen. Zum Beispiel, was die Wahrscheinlichkeit einer offenen Tür , wenn die Aktion ist offen . In einer perfekten Welt könnte die spätere Version 1.0 sein, aber wenn es sich um einen Roboter handelt, könnte es fehlgeschlagen sein, den Türknauf richtig zu handhaben. Ein anderes Beispiel im Fall eines sich bewegenden Roboters wäre die Aktion nach Norden , die ihn in den meisten Fällen in die Gitterzelle nördlich davon bringen würde, sich aber in einigen Fällen zu weit bewegen und beispielsweise die nächste Zelle erreichen könnte.
  4. Belohnungen : Diese dienen als Planungshilfe. Im Fall des Gitterbeispiels möchten wir vielleicht zu einer bestimmten Zelle gehen, und die Belohnung wird höher sein, wenn wir näher kommen. Im Fall des Türbeispiels kann eine offene Tür eine hohe Belohnung bieten.

Sobald der MDP definiert ist, kann eine Richtlinie durch Durchführen einer Wert- oder Richtlinieniteration gelernt werden, die die erwartete Belohnung für jeden Status berechnet. Die Richtlinie gibt dann pro Bundesstaat die beste Aktion (unter Berücksichtigung des MDP-Modells) an.

Zusammenfassend ist ein MDP hilfreich, wenn Sie eine effiziente Abfolge von Aktionen planen möchten, bei der Ihre Aktionen nicht immer zu 100% wirksam sein können.

Deine Fragen

Kann man damit Dinge vorhersagen?

Ich würde es Planung nennen und nicht etwa Regression vorhersagen .

Wenn ja, welche Arten von Dingen?

Siehe Beispiele .

Kann es Muster unter unendlichen Datenmengen finden?

|S|

Was kann dieser Algorithmus für mich tun?

Siehe Beispiele .

Anwendungsbeispiele für MDPs

Und es gibt noch einige andere Modelle. Ein noch interessanteres Modell ist der partiell beobachtbare Markovsche Entscheidungsprozess, bei dem Zustände nicht vollständig sichtbar sind und stattdessen Beobachtungen verwendet werden, um eine Vorstellung vom aktuellen Zustand zu erhalten, was jedoch nicht in den Rahmen dieser Frage fällt.

zusätzliche Information

Ein stochastischer Prozess ist Markovian (oder hat die Markov-Eigenschaft), wenn die bedingte Wahrscheinlichkeitsverteilung zukünftiger Zustände nur vom aktuellen Zustand und nicht von vorherigen Zuständen abhängt (dh nicht von einer Liste vorheriger Zustände).

ein Gold
quelle
2
Dies ist wahrscheinlich die klarste Antwort, die ich jemals bei Cross Validated gesehen habe.
Hidden Markov Model
Hast du eine Chance, die Links zu reparieren? Einige von ihnen scheinen kaputt oder veraltet zu sein.
ComputerScientist
So dass jeder Prozess, der das hat states, actions, transition probabilitiesund rewardsdefiniert als Markow bezeichnet werden würde?
Suhail Gupta