bayers u. kalman filter, hidden markov model

[Chris2]

hi,
kann mir jemand die den bayers, kalman filter und das hidden markov model auf einfache art erklären? vielleicht anhand eines beispieles.

lg

[knivil]

Das wuerde den Umfang dieses Forums sprengen. Stelle bitte konkrete (am besten Ja/Nein)Fragen anstatt Allgemeines zu erbitten. Dann kann ich versuchen, sie zumindestens im Bereich HMM zu antworten. Ansonsten empfehle ich dir, ein Buch/Tutorial zu lesen.

[otze]

Hidden Markov Model:

Ausgangspunkt ist ein normales Markov Model. Das heißt du befindest dich in einem vollständig bekannten Zustand und kannst von diesem über bestimmte Übergänge andere Folgezustände erreichen. Ich gehe einfach mal davon aus, dass du das kennst.

Nun stell dir vor, dass du kein perfekter Beobachter bist. Das heißt der Zustand, der eventuell ein Vektor aus vielen unterschiedlichen Werten (Position im Raum, Geschwindigkeit, Rotationswinkel, was auch immer) besteht, ist dir nicht vollständig bekannt. Zum Beispiel könnte dir deine aktuelle Geschwindigkeit fehlen. In dem Fall kannst du nicht sagen, wie weit du dich zwischen 2 Zeitschritten fortbewegst und somit ist dein nächster Zustand immer eine kleine Überraschung.

Das heißt, ein Hidden Markov Model (HMM) besteht aus 2 Teilen: Einem echten Markov Model und die Beobachtungen die du machst. Du kennst natürlich nur deine Beobachtungen. Das Ziel ist also, von den Beobachtungen wieder auf den echten Zustand im Markov Model zu schließen. Wenn dir also die Geschwindigkeit fehlt, kannst du über mehrere Zeitschritte die Differenzen zwischen deinen Positionen messen und daraus deine Geschwindigkeit schätzen.
Natürlich ist der Fall, dass du nur einen Teil des echten Zustands siehst, ein ganz einfacher. Generell kann deine Beobachtung beliebig verrauscht sein und in irgendeiner Art und Weise verändert.

Beim Kalman Filter kann ich dir nur die Idee vermitteln:
Der Kalman Filter löst ein einfaches HMM: Wir haben einen nicht deterministischen Markov Prozess. Das heißt, eine einfache Folge von Zuständen, deren Übergänge allerdings zufällig ist. Das was du aber siehst, ist nicht der Zustand, sondern eine verrauschte Beobachtung.
Dieser Aufbau ist häufig bei Experimenten gegeben. Wir können nicht genau sagen, welcher Zustand exakt auf einen bestimmten vorhergehenden Zustand folgt und das was wir messen ist verrauscht. Aufgabe des Kalman Filters ist somit, das Rauschen durch Messfehler zu entfernen, ohne dass die nichtdeterministische Komponente des Experimentes verloren geht.

En bissl mathemtaischer: seien x(t) die zustände des Markovprozesses und z(t) unsere Beobachtungen zum Zeitpunkt t.

dann schätzt der Kalmanfilter p(x(t+1)|x(t)) und p(z(t)|x(t+1)). Also die Verteilung der Folgezustände gegeben einen Zustand sowie das Rauschen auf der Beobachtung. Hierbei geht der Kalman Filter davon aus, dass beide Zufallsverteilungen eine Gaussverteilung sind.

Wichtig ist in diesem Zusammenhang: Der Kalman Filter entfernt nur Messfehler. Was er nicht macht, ist die Zustandsübergänge selbst zu schätzen. Er misst nur, wie stark die Abweichungen sind, und korrigiert die Differenzen.

Man braucht also 3 Dinge:
1. eine Zustandsübergangsmatrix F für die gilt x(t+1)=Fx(t).
2. eine Projektionsmatrix H für die gilt: z(t)=Hx(t). Diese Matrix bildet den internen Zustand auf die Beobachtung ab.
3. eine Rauschmatrix die die Art und stärke deines Rauschens möglichst genau beschreibt. Die muss man leider ziemlich oft raten.

Was der Kalman Filter schätzt (vereinfacht!):
1. den erwarteten nächsten Zustand x'(t) und daraus eine geschätzte Beobachtung z'(t)=H*x'(t)
2. eine Kovarianzmatrix P, die die zufällige Verteilung der Zustände im Markov Model beschreibt (sie schätzt also den nicht-determinismus des Prozesses)
3. eine Korrekturmatrix K die aus der Differenz der erwateten Beobachtung und der echten Beobachtung eine Korrektur für den internen Zustand schätzt. Dies korrigiert den Fakt, dass bereits die alte Schätzung fehlerhaft war und somit korrigiert werden muss.

das mal als grober Überblick über 2 der Fragen. Keine Garantie auf Richtigkeit.

[Chris2]

otze schrieb:

Hidden Markov Model:

Ausgangspunkt ist ein normales Markov Model. Das heißt du befindest dich in einem vollständig bekannten Zustand und kannst von diesem über bestimmte Übergänge andere Folgezustände erreichen. Ich gehe einfach mal davon aus, dass du das kennst.

Nun stell dir vor, dass du kein perfekter Beobachter bist. Das heißt der Zustand, der eventuell ein Vektor aus vielen unterschiedlichen Werten (Position im Raum, Geschwindigkeit, Rotationswinkel, was auch immer) besteht, ist dir nicht vollständig bekannt. Zum Beispiel könnte dir deine aktuelle Geschwindigkeit fehlen. In dem Fall kannst du nicht sagen, wie weit du dich zwischen 2 Zeitschritten fortbewegst und somit ist dein nächster Zustand immer eine kleine Überraschung.

Das heißt, ein Hidden Markov Model (HMM) besteht aus 2 Teilen: Einem echten Markov Model und die Beobachtungen die du machst. Du kennst natürlich nur deine Beobachtungen. Das Ziel ist also, von den Beobachtungen wieder auf den echten Zustand im Markov Model zu schließen. Wenn dir also die Geschwindigkeit fehlt, kannst du über mehrere Zeitschritte die Differenzen zwischen deinen Positionen messen und daraus deine Geschwindigkeit schätzen.
Natürlich ist der Fall, dass du nur einen Teil des echten Zustands siehst, ein ganz einfacher. Generell kann deine Beobachtung beliebig verrauscht sein und in irgendeiner Art und Weise verändert.

ein Markov Model ist doch sowas wie ne moore final state machine, wo die zustandsübergänge mit wahrscheinlichkeiten beschrieben werden oder?
wie hängt der zustandsübergangsvektor (Position im Raum, Geschwindigkeit, Rotationswinkel, was auch immer) mit den wahrscheinlichkeiten zusammen?
wenn mir die geschwindigkeit fehlt, kann ich ja die letzen 2 geschwindigkeitswerte nehmen und z.b. linear approximieren?
Beobachtungen sind einfach nur irgendwelche erfahrungswerte der vergangenheit?

otze schrieb:

Beim Kalman Filter kann ich dir nur die Idee vermitteln:
Der Kalman Filter löst ein einfaches HMM: Wir haben einen nicht deterministischen Markov Prozess. Das heißt, eine einfache Folge von Zuständen, deren Übergänge allerdings zufällig ist. Das was du aber siehst, ist nicht der Zustand, sondern eine verrauschte Beobachtung.
Dieser Aufbau ist häufig bei Experimenten gegeben. Wir können nicht genau sagen, welcher Zustand exakt auf einen bestimmten vorhergehenden Zustand folgt und das was wir messen ist verrauscht. Aufgabe des Kalman Filters ist somit, das Rauschen durch Messfehler zu entfernen, ohne dass die nichtdeterministische Komponente des Experimentes verloren geht.

En bissl mathemtaischer: seien x(t) die zustände des Markovprozesses und z(t) unsere Beobachtungen zum Zeitpunkt t.

dann schätzt der Kalmanfilter p(x(t+1)|x(t)) und p(z(t)|x(t+1)). Also die Verteilung der Folgezustände gegeben einen Zustand sowie das Rauschen auf der Beobachtung. Hierbei geht der Kalman Filter davon aus, dass beide Zufallsverteilungen eine Gaussverteilung sind.

Wichtig ist in diesem Zusammenhang: Der Kalman Filter entfernt nur Messfehler. Was er nicht macht, ist die Zustandsübergänge selbst zu schätzen. Er misst nur, wie stark die Abweichungen sind, und korrigiert die Differenzen.

Man braucht also 3 Dinge:
1. eine Zustandsübergangsmatrix F für die gilt x(t+1)=Fx(t).
2. eine Projektionsmatrix H für die gilt: z(t)=Hx(t). Diese Matrix bildet den internen Zustand auf die Beobachtung ab.
3. eine Rauschmatrix die die Art und stärke deines Rauschens möglichst genau beschreibt. Die muss man leider ziemlich oft raten.

Was der Kalman Filter schätzt (vereinfacht!):
1. den erwarteten nächsten Zustand x'(t) und daraus eine geschätzte Beobachtung z'(t)=H*x'(t)
2. eine Kovarianzmatrix P, die die zufällige Verteilung der Zustände im Markov Model beschreibt (sie schätzt also den nicht-determinismus des Prozesses)
3. eine Korrekturmatrix K die aus der Differenz der erwateten Beobachtung und der echten Beobachtung eine Korrektur für den internen Zustand schätzt. Dies korrigiert den Fakt, dass bereits die alte Schätzung fehlerhaft war und somit korrigiert werden muss.

das mal als grober Überblick über 2 der Fragen. Keine Garantie auf Richtigkeit.

braucht der kalman filter trainingsdaten? Wer schätzt man dann die Zustandsübergänge, wenns der Kalman filter nicht macht?
- die Zustandsübergangsmatrix ist eine matrix mit wahrscheinlichkeiten?
- die Projektionsmatrix wer erzeugt diese, was beinhaltet sie, auch wahrscheinlichkeiten?
- die Rauschmatrix ist eine stochastische funktion - gaussverteilt?

[otze]

Chris2 schrieb:

ein Markov Model ist doch sowas wie ne moore final state machine, wo die zustandsübergänge mit wahrscheinlichkeiten beschrieben werden oder?

Nein, ein Markov Model kann überabzählbar viele Zustände haben(zum Beispiel reelwertig). Ein Markov Model kann deswegen im Allgemeinen nicht durch eine finite State machine abgebildet werden. Vom Prinzip her ist er aber ähnlich.

wie hängt der zustandsübergangsvektor (Position im Raum, Geschwindigkeit, Rotationswinkel, was auch immer) mit den wahrscheinlichkeiten zusammen?

Der Zusammenhang kann beliebig kompliziert sein und hängt rein von dem Problem ab. Zum Beispiel irgendwelche Zerfallsprozesse. Du beginnst dein Experiment und misst dann irgendwelche Messdaten und versuchst über diese Messdaten dann vielleicht zukünftige Messungen zu schätzen. Da der Zerfall ein rein stochastischer Prozess hast, wirst du nur sagen können: im Mittel wird die Zerfallsrate in der Zukunft um x% im nächsten Messwert fallen - das muss aber nicht. Es können auch mal ungewöhnlich viele oder wenige Teilchen zerfallen. In dem Fall hat dann dein Erwartungswert die höchste Wahrscheinlichkeit und je höher, bzw geringer die Zerfallsraten sind, desto geringer ist ihre Wahrscheinlichkeit.

Abstrakter kannst du als Zustandsübergang eine beliebige Funktion angeben die dann x'=f(x) berechnet. Das ist wirklich beliebig. Im Allgemeinen reicht aber eine Wahrscheinlichkeitsverteilung und die Bestimmung ihres Mittelwertes. Es hängt auch davon ab, was du machen willst. Wenn du zum Beispiel selber so einen Prozess berechnen willst, dann nimmst du die Wahrscheinlichkeitsverteilung deines Zustandes und würfelst dann den Folgezustand aus. Willst du aber messen, in welchem Zustand du dich befindest, dann musst du die Messwerte nehmen und abschätzen welche Zustandsfolge anhand ihrer Wahrscheinlichkeitsverteilung am wahrscheinlichsten ist.

wenn mir die geschwindigkeit fehlt, kann ich ja die letzen 2 geschwindigkeitswerte nehmen und z.b. linear approximieren? Beobachtungen sind einfach nur irgendwelche erfahrungswerte der vergangenheit?

Beobachtungen sind das, was du von deinem aktuellen Zustand überhaupt wahrnehmen kannst. Nehmen wir mal unsere Welt als Markov Model: Wir Menschen können von unserem aktuellen Zustand in der Welt immer nur einen sehr kleinen Teil wahrnehmen, nämlich das Sichtfeld was vor uns ist, unser Gehör, unser Geruchssinn usw. Der Zustandsraum ist natürlich viel komplexer, zum Beispiel können wir nicht sehen, was hinter uns ist, und unsere Ohren sind zu ungenau, dass wir alles hinter uns wahrnehmen können. Entscheidungen die wir also treffen müssen, zum Beispiel ob die Straße grad sicher zum überqueren ist, beruhen damit auf unvollständigen Zustandsinformationen: unserem Beobachtungsraum.

Damit wird klar, dass du die Geschwindigkeit nicht aus alten Geschwindigkeiten interpolieren kannst, weil du die Geschwindigkeiten gar nicht kennst, also gar nicht wahrnehmen kannst. Das einzige was du machen kannst, ist in die Vergangenheit schauen, und zurückzuverfolgen was du gemacht hast und wie es deinen Zustand verändert hat. Und mit diesem Erfahrungswert kannst du dann deine aktuelle Geschwindigkeit abschätzen.

braucht der kalman filter trainingsdaten?

Nein. Er liefert nur über die Zeit genauere Schätzungen weil er immer aus alten Messdaten auf die neuen schließt.

Wer schätzt man dann die Zustandsübergänge, wenns der Kalman filter nicht macht?
- die Zustandsübergangsmatrix ist eine matrix mit wahrscheinlichkeiten?
- die Projektionsmatrix wer erzeugt diese, was beinhaltet sie, auch
- die Rauschmatrix ist eine stochastische funktion - gaussverteilt?

das musst du alles irgendwie schätzen. Die ersten beiden Dinger sind irgendwelche linearen Funktionen (eine Matrix ist eine lineare Funktion), die deterministisch ist. Um den nichtdeterminismus kümmert sich ja der Kalman Filter. Die Matrizen schätzt du zum Beispiel mit einem Lernverfahren anhand von Simulationen. Die Rauschmatrix ist die Kovarianzmatrix der mehrdimensionalen Gaussfunktion. Die rätst du einfach anhand der Qualität deiner Sensoren.

Eventuell solltest du dir vor dem Kalmann Filter ein wenig mehr von den Grundlagen aneignen. So wird das nichts.