09 Hidden Markov Model

Question 1

Markov-Bedingung: Beschränkter Horizont

Answer 1

Die Wahrscheinlichkeit einen Zustand zu erreichen ist nur von seinem direkten Vorgängerzustand abhängig

P(q_{t+1} = S_j | q_t = S_i, q_{t-1} = S_k, … )
= P(q_{t+1} = S_j | q_t = S_i)

Question 2

Zeitinvarianz

Answer 2

Die Wahrscheinlichkeit eines Zustandsübergangs ist unabhängig von der Zeit

Question 3

Hidden Markov Modelle (HMM)

Answer 3

Bisherige Annahme:
Ereignisse (Zustände) sind direkt beobachtbar

Erweiterung (HMM):
Beobachtung ist eine stochastische Funktion des Zustands –> Zustände können nur indirekt beobachtet werden.

HMM beschreibt einen doppelt stochastischen Prozess:
Der zugrunde liegende stochastische Prozess kann nur indirekt durch eine andere Menge von stochasitschen Prozessen beobachtet werden, die eine Beobachtungssequenz produziert.

Question 4

3 grundlegende Probleme HMM

Answer 4

Evaluationsproblem:

• gegeben: Modell lamda = {S,V,A,B,π}
• gesucht: Wahrschienlichkeit P(O | lamda) für die Ausgabe O = o_1, o_2, …, o_T
• Bedeutung: Wie gut erklärt ein Modell eine Beobachtungssequenz?
• vorwärtsalgorithmus, rückwärtsalgorithmus

Dekodierungsproblem:

• Gegeben: Ausgabesequenz = und Modell lamda
• Gesucht: Wahrscheinlichste Zustandsfolge Q, die O erklärt
• Bedeutung: Finden der “korrekten” (verborgenen) Zustandssequenz
• Viterbi-Algorithmus

Lern- oder Optimierungsproblem

• geg.: Ausgabesequenz(en) O und ein Suchraum für Modelle
• Ges.: Anpassung der Parameter lamda, s.d. O besser erklärt wird
• Bedeutung: Optimierung der Modellparameter (Training)
• kein analytischer Lösungsweg bekannt –> baum-welch-algorithmus

Question 5

Baum-Welch-Algorithmus : Bewertung

Answer 5

Es gilt:
P(O | lamda-neu) ≥ P(O | lamda)

Damit verbessert sich das Modell auf der Menge der Trainingsdaten

Realisiert EM (Expectation Maximization) Ansatz

Training wird abgebrochen, wenn nur noch minimale Verbesserungen

Es kann kein globales Maximum garantiert werden

Question 6

Arten von HMM

Answer 6

Ergodisches Modell:
* jeder Zustand kann von jedem anderen Zustand aus in einer endlichen Anzahl von Schritten erreicht werden

Barkis-Modell (Links-nach-rechts-modell):

• der Zustandsindes wird mit der Zeit größer oder bleibt gleich
• auch mit parallelen Pfaden

Question 7

Einordnung HMM

Answer 7

Typ der Inferez: induktiv 
Ebene des Lernens: subsymbolisch 
Lernvorgang: überwacht 
Beispielgebung: nicht inkrementell 
Umfang der Beispiele: umfangreich 
Hintergrundwissen: empirisch

Question 8

Anwendungsbereiche HMM

Answer 8

überall dort, wo man zugrunde liegende stochastische Prozesse nur indirekt (zusätzliche stochasitsche Prozesse) beobachten (erfassen) kann …

• spracherkennung
• gestenerkennung zB Robotik
• autonome Fahrzeuge Ampelzustandsschätzung
• bioinformatik