Hidden-Markow- und Viterbi-Algorithmen |
| 06.07.2019, 10:04 | Fenrix | Auf diesen Beitrag antworten » | ||||||||
| Hidden-Markow- und Viterbi-Algorithmen Hallo zusammen, ich lerne gerade für eine Klausur und bearbeite folgende Aufgabe: Der Trainerstab von Joachim Löw analysiert zur Vorbereitung auf das kommende Spiel, wann der nächste Gegner intensiv Standard-Situationen, wie z.B. Freistöße, im Training vor einem Spiel einstudiert hat. Leider üben die Gegner die Standards nur in geheimen Trainingseinheiten. Über den nächsten Gegner, Brasilien, ist bekannt, dass im Training vor dem nächsten Spiel zu 25% Standards trainiert werden, falls vor dem vorherigen Spiel Standards trainiert wurden. Zu 75% werden vor dem nächsten Spiel dann also keine Standards trainiert. Anderseits werden vor dem nächsten Spiel Standards zu 50% trainiert, falls zuvor Standards nicht trainiert wurden. Ferner hat die "Seleção" Informationen veröffentlicht, nach denen zu 70% mindestens 1 Tor aus Standards fällt, falls diese zuvor trainiert wurden. Wurden keine Standards trainiert, fällt zu 60% kein Tor nach Standards bzw. nur zu 40% fällt dann mindestens ein Tor nach Standardsituationen. [1] ... [2] ... [3] Im vergangenen Spiel hat Brasilien ein Tor aus einer Standardsituation erzielt. Im Spiel zuvor wurde ebenfalls ein Tor aus einem Standard erzielt, davor wurde kein Tor aus einer Standardsituation geschossen. Skizzieren Sie den Viterbi-Suchraum und berechnen die Wahrscheinlichkeit für einen beliebig ausgewählten Pfad, wann Standards (nicht) trainiert wurden. Meine Ideen: Das Hidden-Markov-Model habe ich so skizziert: [attach]49462[/attach] Da ich die Anfangswahrscheinlichkeiten nicht kenne, war es bislang immer in Ordnung einfach von gleichverteilten Wahrscheinlichkeiten auszugehen, also im Folgenden jeweils 1/2. Nun wollte ich den Viterbi-Suchraum aufzeichnen. Wenn ich den Viterbi-Algorithmus richtig verstanden habe, merkt man sich für jeden Hidden-State nur den besten Vorgänger und rechnet damit weiter. Das sieht bei mir so aus: [attach]49463[/attach] Wenn ich jetzt die Frage beantworten würde, was die wahrscheinlichste Folge von Trainingseinheiten bei den gesehenen Toren wäre, würde ich also ausgehend von der höchsten "Endwahrscheinlichkeit" 63/200 den Pfad zurückverfolgen und würde entsprechend bei den Hidden-States "SN -> ST -> SN" landen. Passt das so? Oder habe ich hier schon einen ersten Denkfehler? Jetzt komme ich leider bei der Bearbeitung der eigentlichen Aufgabe nicht weiter, weil ich die Frage an sich nicht verstehe. Ich soll die Wahrscheinlichkeit berechnen, dass auf einem von mir ausgewählten Pfad Standards trainiert wurden oder nicht? Das macht für mich irgendwie keinen Sinn, da der Pfad doch festlegt, ob Standards trainiert wurden oder nicht. Die Wahrscheinlichkeit sollte bei der Formulierung ja immer 0 und 1 sein. Versteht die Frage vllt. jemand richtig? Desweiteren ist mir Folgendes aufgefallen, was mich etwas verwirrt. Angenommen ich möchte die Frage beantworten, auf welche Weise das/die Tor(e) am 2. Spieltag entstanden sind. Dann gibt es ja 4 Möglichkeiten: ST -> ST -> T+ => 1/4 * 7/10 = 7/40 SN -> ST -> T+ => 1/2 * 7/10 = 7/20 ST -> SN -> T+ => 3/4 * 2/5 = 3/10 SN -> SN -> T+ => 1/2 * 2/5 = 1/5 Wenn ich die Wahrscheinlichkeiten jetzt aufsummiere hätte ich erwartet, dass genau 1 rauskommt, weil es ja genau auf eine dieser Möglichkeiten passiert sein muss. Raus kommt aber 41/40, was ich mir nicht erklären kann. Sorry, alles etwas verwirrend geschrieben, ich hoffe jemand kennt sich mit dem Thema aus und kann mir vllt. weiterhelfen. Gruß und schönes WE |
||||||||||
| 06.07.2019, 17:20 | Huggy | Auf diesen Beitrag antworten » | ||||||||
RE: Hidden-Markow- und Viterbi-Algorithmen
Damit kenne ich mich überhaupt nicht aus. Bisher hatte ich von HMM und Viterbi-Algorithmus nie etwas gehört. Da aber ein Ahnungsloser alles kommentieren kann, gebe ich dir mal meine Gedanken kund, die du also mit größtem Misstrauen betrachten solltest. Sie sind in der folgenden Excel-Tabelle zusammengestellt. [attach]49465[/attach] Es gibt 8 Pfade für das Training vor den 3 Spielen. Die stehen in der B-Spalte. T steht für Standards trainiert, N für Standards nicht trainiert. Man beginnt mit einer Priori-Wahrscheinlichkeit für die 8 Pfade. Diese basiert auf einer Priori-Wahrscheinlichkeit von 0.5 für T und N beim ersten Training. So weit passt das zu deinen Ausführungen. Die bedingten Priori-Wahrscheinlichkeiten für das 2. und 3. Training ergeben sich dann für jeden Pfad aus dem Übergangsdiagramm. Diese Priori-Wahrscheinklichkeiten für das 1., 2, 3. Training stehen in in den Spalten C, D, E. Als Beispiel sei der Pfad 6 NTN betrachtet: Das erste N bekommt die Priori-Wahrscheinlichkeit 0.5. Gemäß Übergangsdiagramm hat man dann eine bedingte Wahrscheinlichkeit 0.5 für T im 2. Training und dann eine bedingte Wahrscheinlichkeit 0.75 für N im 3. Training gemäß Übergangsdiagramm. Die Priori-Wahrscheinlichkeit für den Pfad ergibt sich durch Multiplikation der Wahrscheinlichkeiten in den Spalten C, D, E und steht mit 32 multipliziert in der F-Spalte. In den Spalten G, H, I stehen stehen die einzelnen Torwahrscheinlichkeiten der beobachteten Torfolge (kein Tor Tor, Tor) der Pfade. In der J-Spalte steht mit 1000 multipliziert die Wahrscheinlichkeit der gesamten beobachteten Torfolge Tf. Sie ist mit bezeichnet. Mittels der beobachteten Torfolge kann man nun die Posteriori-Wahrscheinlichkeit aller Pfade bestimmen. Das ist bei 8 Pfaden kein besonderer Aufwand. Bei größeren Problemen kann das aber ein erheblicher Aufwand sein. Der Viterbi-Algorithmus soll nun nach meinem Verständnis dazu dienen, den Pfad mit der größten Posteriori-Wahrscheinlichkeit zu bestimmen, ohne dass man die Posteriori-Wahrscheinlichkeit aller Pfade ermttelt. Ich habe nicht versucht, den Algorithmus zu verstehen. Stattdessen habe ich die Posteriori-Wahrscheinlichkeiten aller Pfade Bestimmt. Sie ergeben sich nach der Bayes-Regel zu In der K-Spalte steht mit 32000 multipliziert der Zähler der rechten Seite, wobei der Faktor 32000 diesmal nicht in der Überschrift steht. In Spalte L steht dann . Die maximale Posteriori-Wahrscheinlichkeit hat nach meiner Rechnung der Pfad 6 mit gut 26 %. Deine Rechnung kommt zu zwar zu demselben Pfad, aber mit einer deutlich größeren Wahrscheinlichkeit. |
||||||||||
| 07.07.2019, 10:54 | Fenrix | Auf diesen Beitrag antworten » | ||||||||
Danke für die ausführliche Antwort und Respekt, dass du ein für dich unbekanntes Thema trotzdem in der Form bearbeiten kannst 
Die Darstellung in der Excel-Tabelle finde ich gut, das kann ich nachvollziehen. Dass bei uns der gleiche Pfad am wahrscheinlichsten ist, stimmt mich auch schonmal positiv 
Ich rede mir jetzt mal ein, dass das am Algorithmus liegt. Ich meine tatsächlich im Hinterkopf zu haben, dass der Professor mal was in die Richtung erwähnt hätte. Was ich mich noch frage ist, wie von meinen Ergebnisse analog zu deiner Excel-Tabelle auf die Pfad-Wahrscheinlichkeit komme. Wenn ich mir mein Ergebnis von "63/2000" für den "SN->ST->SN" Pfad angucke, ist das ja die umgangssprachlich die Wahrscheinlichkeit dafür dass "die Trainings in der Reihenfolge SN, ST, SN stattgefunden haben und daraus die Tore T0, T+, T+ entstanden sind". Vermutlich ist es echt einfach, aber wie bringe ich das so in Relation, dass die Tore gegeben sind und ich analog zu deinen 26% die Wahrscheinlichkeit für die 63/2000 berechne 
Darf man die Ergebnisse einfach in Relation zueinander setzen oder muss man hier mit bedingten Wahrscheinlichkeiten etc. rechnen? |
||||||||||
| 07.07.2019, 11:42 | Huggy | Auf diesen Beitrag antworten » | ||||||||
Na ja, ein paar allgemeine Statistikkenntnisse habe ich schon.
Die Sache ist noch besser. In deinem Eingangstext stand 63/200. Daher hatte ich vermutet, dass dieser Wert den Einträgen in der L-Spalte meiner Tabelle entspricht. Jetzt lese ich bei dir 63/2000, was auch schon in deiner handschriftlichen Rechnung stand. Das stimmt exakt mit 1008 in meiner K-Spalte überein, die ja noch durch 32000 zu teilen sind. Das ist die noch nicht normierte Posteriori-Wahrscheinlichkeit des Pfads 6.
Da fällt mir im Moment nichts ein. Bei mir ergibt sich das, in dem man auf der rechten Seite der Bayes-Regel durch den Nenner teilt. Dieser Nenner ist die Summe der nicht normierten Posteriori-Wahrscheinlichkeiten. Für die Summe braucht man aber die Ergebnisse alle Pfade. Ich wüsste nicht, wie man normieren soll, wenn man nicht die Ergebnisse für alle Pfade hat. |
||||||||||
| 07.07.2019, 12:59 | Fenrix | Auf diesen Beitrag antworten » | ||||||||
Dann formulier ich es anders und sag Respekt, dass du die Aufgabe auf eine andere Art lösen kannst, ohne den eigentlich vorgesehenen Algorithmus zu kennen
Mist, mit den 63/200 ist mir dann tatsächlich ein Tippfehler unterlaufen. Das in dem Fall dann tatsächlich das Gleiche rauskommt macht mir schonmal Mut für morgen
Zu "echter" Wahrscheinlichkeit und "Viterbi-Wahrscheinlichkeit" hatte ich in meinen Unterlagen auch noch folgendes gefunden:  http://i.epvpimg.com/ijWifab.pngDas ist dann vllt. ein Grund warum die Umrechnung so nicht geht. Danke dir auf jeden Fall für die Hilfe, für morgen sollte ich damit klarkommen 
|
||||||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
