Baum-Welch und EM

Das Modell seine eigenen Zahlen lernen lassen

Bisher nahmen wir an, $\pi$, $A$ und $B$ zu kennen. In echten Daten tun wir das nicht: Wir haben nur die Beobachtungen. Der Baum-Welch-Algorithmus lernt die Zahlen aus den Daten. Er ist ein Beispiel für Expectation-Maximization (EM) und wiederholt zwei Schritte. Im E-Schritt berechnet man mit den aktuellen Zahlen und dem Forward-Backward-Algorithmus, wie wahrscheinlich jeder verborgene Zustand und jeder Zustandswechsel an jedem Tag war. Im M-Schritt schätzt man die Zahlen durch Zählen neu, aber mit diesen Wahrscheinlichkeiten statt ganzer Zählwerte.

Hier ist $\gamma_t(i)$ die geglättete Wahrscheinlichkeit von Zustand $i$ an Tag $t$ und $\xi_t(i,j)$ die geglättete Wahrscheinlichkeit des Wechsels von $i$ nach $j$ zwischen Tag $t$ und $t+1$. Das neue $A_{ij}$ ist also die erwartete Zahl der Wechsel $i\to j$ geteilt durch die erwartete Zahl der Tage in $i$. Zwei Fakten sind wichtig. Die Log-Likelihood der Daten sinkt von einer EM-Runde zur nächsten nie, man kann also aufhören, wenn sie sich nicht mehr verbessert. Aber EM steigt nur zum nächsten Gipfel, kann also in einem lokalen Maximum enden, und unterschiedliche Startwerte können verschiedene Antworten geben. In der Praxis probiert man mehrere Starts und behält den besten.

• E-Schritt: mit den aktuellen Zahlen $\gamma$ und $\xi$ per Forward-Backward berechnen.
• M-Schritt: $\pi$, $A$ und $B$ als erwartete Zählwerte geteilt durch erwartete Summen neu schätzen.
• Die Log-Likelihood fällt nie, aber EM kann in einem lokalen Maximum stehen bleiben: mehrere Starts probieren.

Lab: Was bewertet wird

• Erwartete ruhige Tage10 Pkt.
• Eine neue Emissionswahrscheinlichkeit15 Pkt.
• Eine neue Anfangswahrscheinlichkeit10 Pkt.
• Eine neue Übergangswahrscheinlichkeit15 Pkt.
• Was EM garantiert15 Pkt.
• Eine EM-Runde10 Pkt.
• Begriffe zuordnen10 Pkt.
• Warum Starts wichtig sind15 Pkt.