Versteckte Markov-Modelle und Erwartungsmaximierungsalgorithmus

10

Kann jemand klären, wie versteckte Markov-Modelle mit der Maximierung der Erwartungen zusammenhängen? Ich habe viele Links durchgesehen, konnte aber keine klare Sicht finden.

Vielen Dank!

thchand
quelle

Antworten:

12

Der EM-Algorithmus (Erwartungsmaximierung) ist ein allgemeiner Algorithmus zur Optimierung der Wahrscheinlichkeitsfunktion in Fällen, in denen das Modell probabilistisch in Bezug auf eine beobachtete und eine nicht beobachtete (latente) Komponente spezifiziert wird. HMMs (Hidden-Markov-Modelle) sind Modelle dieser Form, da sie eine nicht beobachtete Komponente haben, die Hidden-States und die tatsächlichen Beobachtungen werden in der HMM-Terminologie häufig als Emissionen bezeichnet . Daher bilden HMMs eine Klasse von Modellen, für die der EM-Algorithmus nützlich sein kann.

Im Allgemeinen, wenn das Modell aus zwei Komponenten , von denen wir der Einfachheit halber annehmen, dass sie Werte in einem endlichen Raum annehmen, und wenn die Wahrscheinlichkeitsmodellspezifikation aus den Gelenkpunktwahrscheinlichkeiten , parametrisiert durch , dann ist die Wahrscheinlichkeit, wenn nur wird, (X,Y)pθ(x,y)θX=x

Lx(θ)=ypθ(x,y).
Obwohl die Summe unschuldig aussieht, ist es nicht. Bei HMMs wird die Summe über alle möglichen Übergänge zwischen den verborgenen Zuständen verteilt, was schnell zu einer beeindruckenden Zahl wird, wenn die Länge der beobachteten Sequenz zunimmt. Glücklicherweise gibt es Algorithmen für HMMs (vorwärts-rückwärts) zur schnellen Berechnung der Wahrscheinlichkeit, und die Wahrscheinlichkeit könnte dann im Prinzip in jeden allgemeinen Optimierungsalgorithmus für die Schätzung der maximalen Wahrscheinlichkeit von . Die Alternative ist der EM-Algorithmus. Dies ist ein Algorithmus, der iterativ wechseltθ
  • der E-Schritt , der eine Berechnung einer bedingten Erwartung unter Berücksichtigung des beobachteten unter der aktuellen Schätzung vonxθ
  • der M-Schritt , der eine Maximierung ist

Der EM-Algorithmus ist am sinnvollsten, wenn die beiden obigen Schritte rechnerisch effizient implementiert werden können, z. B. wenn wir geschlossene Formausdrücke für die bedingte Erwartung und die Maximierung haben.

Historisch gesehen wird der allgemeine EM-Algorithmus Dempster, Laird und Rubin zugeschrieben , die in ihrer Arbeit von 1977 unter anderem bewiesen haben, dass der Algorithmus zu einer Folge von Parametern mit monoton ansteigenden Wahrscheinlichkeitswerten führt. Sie prägten auch den Begriff "EM-Algorithmus". Interessanterweise wurde der EM-Algorithmus für HMMs bereits 1970 von Baum et al. und wird in der HMM-Literatur auch oft als Baum-Welch- Algorithmus bezeichnet (ich weiß nicht genau, was Welch getan hat ...).

NRH
quelle
3
Welch erfand den heutigen Baum-Welch-Algorithmus (er nennt ihn "den einfachen Teil"); Baum beweist mathematisch, dass der Algorithmus funktioniert ("der schwierige Teil"). Weitere Informationen finden Sie unter Kurse.cs.tamu.edu/rgutier/cpsc689_s07/welch2003baumWelch.pdf .
Mikhail Korobov
@MikhailKorobov, danke für diese informative Referenz.
NRH
2

Die Erwartungsmaximierung ist eine iterative Methode, mit der statistische Inferenzen für eine Vielzahl verschiedener generativer statistischer Modelle durchgeführt werden, z. B. eine Mischung aus Gaußschen und anderen Bayes'schen Netzwerktypmodellen. Die einzige Verbindung besteht darin, dass HMMs auch Bayes'sche Netzwerke sind. Aber man würde EM wahrscheinlich nicht auf HMMs verwenden, da es einen genauen Inferenzalgorithmus innerhalb von HMMs gibt, der als Viterbi-Algorithmus bezeichnet wird. Obwohl man EM verwenden könnte, um Inferenzen auf einem HMM durchzuführen, würden Sie dies nicht tun, weil es keinen Grund dafür gibt.

Wilhelm
quelle
4
Dies ist nicht ganz richtig, da Sie zwei verschiedene Arten von "Inferenz" verwechseln. EM ist ein Algorithmus zur Schätzung unbekannter Parameter, Viterbi ist der Algorithmus zur Berechnung der wahrscheinlichsten Folge versteckter Zustände. Sie würden in der Tat EM für HMMs zur Parameterschätzung verwenden. Ich habe in meiner Antwort weitere Details zum EM-Algorithmus mit historischen Referenzen angegeben, die die Beziehung zwischen HMMs und EM erläutern.
NRH
0

In HMM versuchen wir hauptsächlich drei Parameter zu schätzen:

  1. Die Anfangszustandswahrscheinlichkeiten. Dies ist ein Vektor mit Elementen, wobei die Anzahl der Zustände ist.K.KK

  2. Die Übergangsmatrix. Dies ist eine quadratische Matrix der Größe .K×K

  3. Die bedingten Wahrscheinlichkeiten der Beobachtung eines Gegenstandes, bedingt durch einen bestimmten Zustand. Dies ist auch eine Matrix der Größe , wobei die Anzahl der Beobachtungen ist.N.K×NN

Jetzt kommt der EM-Teil, wenn Sie versuchen, die oben angegebenen Mengen / Parameter zu schätzen. Ausgehend von einer zufälligen Vermutung wird die Wahrscheinlichkeit der Beobachtungen bewertet und die Parameter iterativ angepasst, bis die maximale Wahrscheinlichkeit erreicht ist. Durch HMM modellieren wir also einen Prozess und dafür müssen wir einige Parameter einführen. Um die Parameter abzuschätzen, wird EM gerendert.

Dies ist eine sehr kurze Antwort. Die Implementierung von EM erfordert eine Reihe anderer Unterprobleme, die mithilfe einer Reihe von Techniken gelöst werden müssen. Für ein gründliches Verständnis wird das klassische Tutorial-Papier von Rabiner dringend empfohlen.

Riaz Khan
quelle