Wir machen heute weiter mit der Frage, wie man jetzt Parameter eines
Modells, eines Hidden-Markov-Modells oder einer Gauss-Mixtur
-Verteilung trainieren kann.
Dafür gibt es auch eine separate Literaturempfehlung, die jeder sich
mal anschauen sollte.
Zum einen ist recht informativ die Wikipedia-Seite zum Thema Maximum
-Likelihood -Methode und zum zweiten gibt es da ein sehr schönes
Paper, ein Übersichtspaper.
Das nennt sich A Gentle Tutorial of the EM-Algorithm and its
Application to Parameter Estimation for Gaussian Mixtures and Hidden
-Markov -Models.
So sieht es aus.
Ist verlinkt auf der Webseite, kriegt man über IEEE-Explore, glaube
ich, also aus dem Internet problemlos raus.
Man sieht, das sind nicht sehr viele Seiten, das sind insgesamt 13
Seiten.
Ist aber eine extrem wichtige Sache und wahrscheinlich mit eines der
schwierigsten Themen in der Vorlesung, aber etwas, wovor die Leute
sich traditionell eher drücken.
Was aber problematisch ist, weil es ein sehr universeller Algorithmus
ist, der an vielen Ecken und Kanten gebraucht wird, um Parameter zu
schätzen.
Und überall in der Literatur, wenn man sich irgendwo andere Methoden
anschaut, wird immer häufiger mal ein EM-Algorithmus verwendet.
Auch für Sachen, die jetzt mit Spracherkennung nichts zu tun haben.
Es gibt ja genügend andere Probleme, wo man Parameter einer
Wahrscheinlichkeitsverteilung oder Dichtefunktion entsprechend
schätzen muss.
Dementsprechend wärmstens ans Herz gelegt, dass sich jeder das Ding
hier einmal in Ruhe durchliest, in gemütlichen zwei Stunden.
Wir waren letztes Mal stehen geblieben noch bei den Baum-Weltsch
-Regeln und hatten gesehen, wie man jetzt intuitiv, logisch, basierend
darauf, dass man weiß, was so Wahrscheinlichkeiten sind, wie man für
diskrete HMMs, HMMs mit diskretem Vokabular, die Parameter neu
schätzen kann.
Einmal die Anfangswahrscheinlichkeiten Pi, das sind gleich direkt die
Gamma 1 von I, weil Gamma T von I war die Wahrscheinlichkeit dafür,
zum Zeitpunkt T im Zustand I zu sein.
Und man konnte die Übergangswahrscheinlichkeiten entsprechend
herleiten aus diesen Wahrscheinlichkeiten dafür, wie häufig ich denn
einen Übergang machen werde von I nach J.
Normiert darüber, dass ich überhaupt in I bin und entsprechend für die
Ausgabewahrscheinlichkeiten, indem man zählt, wie häufig war ich denn,
unabhängig von der Zeit, im Zustand J und habe dabei auch noch das
Symbol Vk ausgegeben.
Normiert auf, wie häufig war ich insgesamt im Zustand J, unabhängig
davon, was ich ausgegeben habe.
Und das ist dann entsprechend die Ausgabewahrscheinlichkeit für das
Karte -Symbol vom J-Zustand.
Das ist jetzt erstmal nur intuitiv hergeleitet worden.
Es erklärt sich, weil man weiß, das sind halt so Wahrscheinlichkeiten,
da werden Ereignisse zueinander ins Verhältnis gesetzt.
Das Ganze hat aber eine zugrunde liegende, schöne mathematische
Struktur, mit der man das über diskrete HMMs hinaus schön
verallgemeinern kann.
Und diese Struktur, dieses Verfahren ist eben das Expectation
-Maximization -Verfahren, der Expectation-Maximization-Algorithmus.
Und der hat eine mathematisch sehr schöne Grundlage.
Bevor man Expectation-Maximization betreiben kann, muss man sich
erstmal darüber im Klaren werden, was Maximum-Likelihood ist und was
die Maximum-Likelihood-Methode ist.
Wir hatten schon gesagt, man kann sich anschauen, wenn man zum
Beispiel den Mittelwert einer eindimensionalen Gauss-Verteilung
schätzen will, dann nimmt man einfach das arithmetische Mittel von
möglichst vielen Trainingsdaten.
Und bei der Varianz schätzt man den Erwartungswert, und das ist dann
auch wieder das arithmetische Mittel, von der Abweichung der Werte vom
eigentlichen geschätzten Erwartungswert und das Ganze zum Quadrat.
Und da war jetzt die Frage natürlich, warum darf man das so?
Und der Grund dafür ist, dass man dann eben die Parameter gefunden
hat, die die Wahrscheinlichkeit, mit der die Trainingsdaten
hervorgebracht werden, maximiert wird.
Und das nennt man eben die Maximum-Likelihood-Methode.
Die kann man sowohl für Wahrscheinlichkeitsdichten als auch für
Wahrscheinlichkeitsverteilungen anwenden.
Nehmen wir jetzt mal an, wir hätten eine Wahrscheinlichkeitsdichte.
Die Wahrscheinlichkeitsdichte hätte irgendeinen Satz von Parameter
Theta.
Theta ist also ein Vektor, der sämtliche Parameter dieser
Wahrscheinlichkeitsdichte enthält.
Bei einer Gauss-Glocke wären es halt entsprechend Mittelwert und
Varianz.
Bei einer Multivariaten-Gauss-Glocke eben entsprechend
Mittelwertsvektor und Covarianzmatrix.
Bei einer Student-Verteilung wäre es halt, was auch immer die Student
-Verteilung parametrisiert ist, usw.
Und wir nehmen an, dass wir Trainingsdaten haben, N-Stück.
Und diese Trainingsdaten wurden von dem Prozess, den wir mithilfe
dieser Distribution modellieren wollen, und damit gehen wir davon aus,
dass sie entsprechend von dem Prozess selber hervorgebracht wurden,
dass der die produziert hat, dass die Datenpunkte gemäß dieser
Distribution entsprechend gezogen wurden.
Wir definieren uns jetzt, wenn wir das haben, diese Hilfsgröße der
Likelihood.
Und als Likelihood definieren wir uns einfach das Produkt der
Wahrscheinlichkeiten über alle Trainingsdaten, über jedes einzelne
Trainingsdatum, dass diese Dichte das Trainingsdatum hervorgebracht
hat.
Und darüber das Produkt ist damit dann die Wahrscheinlichkeit, dass
die Trainingsdaten X von dieser Wahrscheinlichkeitsdichte mit dem
Parametersatz Theta produziert wurden.
Oder anders ausgedrückt, die Wahrscheinlichkeit von X gegebenen
Parametersatz Theta.
Also P von X von Theta, Produkt über die einzelnen, und das ist dann
die Likelihood.
Und die Likelihood kann man jetzt variieren, indem man Theta variiert.
Das heißt, diese Likelihood hängt von den Thetas ab, weil die
Trainingsdaten, auf denen ich arbeite, fix gegeben werden.
Das heißt also, die Likelihood selber hängt ab von den Thetas, wie ich
die Thetas wähle, gegeben meine Trainingsdaten, die fest sind, die
nicht variiert werden.
Und man sucht jetzt halt eben den Satz Theta, der die höchste
Likelihood hat.
Also das Argument Maximum in den Parametersätzen Theta, der Likelihood
hervorbringt.
Nennen wir Theta Sternchen.
Wenn man sich das jetzt anschaut, man hat da eine Funktion stehen, da
hat man das Produkt von ganz vielen Sachen, von so einzelnen kleinen
Dichten, und diese einzelnen kleinen Dichten hängen halt davon ab.
Werten aus einer Dichtefunktion, die hängen halt davon ab, wie die
Dichte aussieht.
Und so ein Produkt zu maximieren, ist halt schwierig.
Schöner wäre es, wenn man eine Summe maximieren würde.
Dann kann man nämlich, wenn man dann ableitet, schön die Summenregel
anwenden, und dann braucht man nur die einzelnen Terme abzuleiten.
Und deswegen ist es halt schön, dass man sagen kann, man braucht nicht
direkt selber die Likelihood zu maximieren, sondern wenn ich die
Likelihood vorher in eine beliebige monotonische Funktion reinstecke,
dann reicht es auch, wenn ich diese monotone Funktion über die
Likelihood in den Parametern maximiere.
Und so eine typische streng monotone Funktion ist glücklicherweise der
Logarithmus.
So, dass ich also auch die logarithmierte Likelihood maximieren kann.
Und wenn ich halt den Logarithmus anwende auf die Likelihood, dann ist
das halt der Logarithmus von diesem Produkt.
Und daraus wird dann entsprechend die Summe über die Logarithmen der
einzelnen Wahrscheinlichkeiten der jeweils einzelnen Trainingsdaten.
Und das kann man jetzt halt entsprechend ableiten, Null setzen und
dann halt den Parametersatz Theta finden, wo das Ganze Null ist, noch
überprüfen, ob man wirklich ein Maximum und kein Minimum hat und kann
damit für unterschiedliche Verteilungsfunktionen,
Wahrscheinlichkeitsdichte -Funktionen oder auch für eine diskrete
Wahrscheinlichkeitsverteilung entsprechend dann den Parametersatz
angeben, der das entsprechend maximiert.
Dafür schauen wir uns einfach mal zwei Beispiele an.
Das erste Beispiel wird eine Wahrscheinlichkeitsverteilung sein, keine
Wahrscheinlichkeitsdichte -Funktion.
Was muss man beachten, wenn man jetzt eine
Wahrscheinlichkeitsverteilung hat, statt einer Dichte-Funktion und ich
will die Likelihood maximieren?
Funktioniert das dann da, was da steht?
Logarithmus nehmen, ableiten, Null setzen.
Hier steht es ja auf einem kleinen P für Wahrscheinlichkeitsdichte
-Funktion.
Funktioniert das genauso, wenn ich da ein Groß-P einsetze, eine echte
Wahrscheinlichkeit von der Wahrscheinlichkeitsverteilung?
Wer hier im Raum hat Operations Research als Nebenfach?
Niemand.
Schade, weil das ist so ein typisches Optimierungsproblem.
Es funktioniert nicht.
Warum kann es nicht funktionieren?
Kann ich bei einer diskreten Wahrscheinlichkeitsverteilung, wenn ich
so mit einer Menge von Trainingsdaten arbeite, kann ich da jeden
beliebigen Wert hinterher als Parameter schätzen?
Nee, kann ich nicht, weil das Ganze ist hinterher ja am Ende ein
ganzzahliges Optimierungsproblem.
Ich brauche hinterher ein ganzzahliges Ergebnis in irgendeiner Form
und dementsprechend kann ich das halt leider nicht so machen mit
Ableiten und Nullsetzen.
Ich kann zwar darauf vorgehen, dass ich diese logarithmierte
Wahrscheinlichkeit maximieren will, ich kann auch die nicht
-logarithmierte Likelihood maximieren wollen, nur mit Ableiten und
Nullsetzen, das funktioniert leider nicht.
Da muss man sich leider was anderes einfallen lassen.
Deswegen eine der wichtigsten Lektionen aus dem Studium, wenn man sich
mit Optimierungsproblemen beschäftigt, und Informatiker müssen sehr
häufig etwas optimieren, ganzzahlige Optimierungsprobleme sind des
Teufels und man hüte sich davor, man kommt da nur in Schwierigkeiten
mit.
Nehmen wir uns folgendes Szenario vor.
Wir hätten wieder eine Urne.
Und in dieser Urne seien insgesamt Kugeln, die entweder rot oder
schwarz sind.
Schwarze Kreide habe ich nicht, jetzt tun wir mal so, als sei blau
schwarz.
Also definiere, blau ist schwarz.
Wir haben also rote und schwarze Kugeln da drin stehen.
Das sind ganz viele rote und schwarze Kugeln.
Und wir haben keine Ahnung, in welchem Mischungsverhältnis die da drin
sind.
Das Einzige, was ich weiß, ist, dass hier drin M-Kugeln insgesamt
sind.
Also insgesamt sind M-Kugeln in der Urne, aber in unbekannten
Vermischungsverhältnissen.
Jetzt will ich schätzen das Mischungsverhältnis.
Sprich, ich will die Wahrscheinlichkeit dafür schätzen, wie hoch die
Wahrscheinlichkeit ist, wenn ich ziehe, dass ich eine rote Kugel oder
dass ich eine schwarze Kugel ziehe.
Also besorge ich mir Trainingsdaten.
Ich ziehe aus der Urne und lege zurück, ziehe und lege zurück und
schreibe mir auf, welche Farbe ich gezogen habe.
Und angenommen, ich mache vier Ziehungen insgesamt.
Diese Ziehungen nenne ich gemäß unserer Notation x1, x2, x3 und x4.
x1 sei gewesen rot.
x2 war auch rot.
x3 war schwarz.
Und x4 war entsprechend rot.
Jetzt ist das blöd, in der Mathematik rote und grüne Kugeln zu
schreiben.
Ich schreibe das jetzt anders.
Für rot schreibe ich einfach eine 1.
Und für schwarz schreibe ich eine 0.
Dann kriege ich keine Probleme mit meiner Sigma-Algebra und dem ganzen
Kram, den ich hinterher brauche für meinen Wahrscheinlichkeitsraum.
Gut, das seien meine Trainingsdaten.
Jetzt muss ich meine Likelihood ausrechnen.
Entschuldigung, mein Fehler.
Das muss hier n heißen.
Das sind insgesamt n Kugeln.
Und m bezeichne mir die Anzahl der roten Kugeln in der Urne.
Das sei also die Anzahl der roten Kugeln.
Die Wahrscheinlichkeit, dass ich jetzt rot ziehe aus so einer Urne,
wenn ich immer wieder zurücklege, die ist qua Definition entsprechend
m durch n.
Und was ich nicht weiß, ist halt das m.
Das ist der Parameter dieser Wahrscheinlichkeitsverteilung, den ich
suche.
Ich kenne meinen n.
Ich weiß, wie viele Kugeln ich drin habe.
Aber ich weiß nicht, wie viele rote Kugeln ich habe.
Sei jetzt n gleich 8.
Also angenommen, ich wüsste, ich habe 8 Kugeln da drin, dann kann ich
jetzt anfangen, meine Likelihood-Funktion auszufüllen.
Und da muss man jetzt entsprechend in die Kiste der Kombinatorik
greifen.
Wer weiß das noch?
Was ist die Wahrscheinlichkeit, wenn ich Kugeln ziehe mit Zurücklegen
aus einer Urne, dass ich x1 gleich 1, x2 gleich 1, x3 gleich 0 und x4
gleich 1 habe?
Wie hoch ist diese Wahrscheinlichkeit?
Das ist erstmal 4 über 3.
Möglichkeiten, dass ich mit der Wahrscheinlichkeit p, also p mal p mal
p mal p hoch 3, die roten Kugeln gezogen habe, mal 1 minus p.
Also das hier ist, dass ich dreimal rot ziehe, einmal schwarz.
Und wenn man sich dann die Reihenfolge anschaut, habe ich insgesamt 4
über 3 Möglichkeiten, dieses Muster dreimal rot, einmal schwarz zu
bekommen, daraus bekomme.
Und das Ganze, wenn man es halt ausrechnet, ist halt 4 über 3, p hoch
3 minus p hoch 4.
So, das ist die Likelihood, die ich maximieren muss.
Und jetzt funktioniert das leider nicht mit Ableiten und Nullsetzen,
weil dieses p nur diskrete Werte annehmen kann.
Ich habe halt insbesondere hier nur ganzzahlige Parameter.
Von dem weiß ich, der ist 8.
Und m kann jetzt halt nur ganzzahlige Werte annehmen.
Wenn ich da jetzt ableiten würde und Nullsetzen, dann könnte ich Pech
haben und es kommt zum Beispiel heraus, m muss gleich 0,75 sein.
Das ist halt blöd, weil ich keine 0,75 Kugeln in meiner Urne habe.
Ich habe immer nur ganze Kugeln.
Und da hilft es auch nicht, dass man dann guckt, welches ist der am
nächsten drangelegene ganzzahlige Punkt.
Das hängt nämlich dann hinterher immer von der Kurve bei so
ganzzahligen ab, welches dann wirklich das Maximum ist.
Das muss nicht unbedingt in der Nähe dessen sein, wenn man das
irgendwie interpoliert.
Das heißt, da bleibt jetzt bei ganzzahligen Optimierungsproblemen an
der Stelle leider nichts anderes übrig, dass wenn man es sicher
richtig machen will, dass man einfach alle Werte durchprobieren muss.
Das heißt, m, die Anzahl der roten Kugeln, können 0 bis maximal 8
sein.
Das heißt, kann also, wenn ich m habe, mir dann hinterher p angucke,
also 0, 1, 2, 3, 4, 5, 6, 7 und 8 haben.
Und p entsprechend kann dann sein 0,8, 1,8, 2,8, 3,8, 4,8, 5,8, 6,8, 7
,8, und muss das jetzt entsprechend einsetzen in meine Likelihood
-Funktion und für jeden dieser einzelnen Werte diese Likelihood
-Funktion ausrechnen.
Und wenn ich das mache, kommt entsprechend raus 0, beziehungsweise
auch nochmal 0 hier.
Meiner macht Sinn, dass das nicht sein kann, weil es wurde ja
mindestens einmal rot und mindestens einmal schwarz gezogen.
Das heißt, es kann logischerweise nicht sein, dass nur rote oder nur
schwarze Kugeln drin sind.
Das hätte man jetzt auch so erwartet.
Und ansonsten, wenn man das halt entsprechend einsetzt in die Formel,
kriegt man halt die Werte 0,02, 0,012,
0,033, 0,063, 0,09,
0,092, 0,105 und 0,084.
Jetzt interessiert uns also das Maximum hier.
Und das Maximum ist gerade hier die 0,105.
Das heißt, p ist 6,8.
Wenn m entsprechend 8 ist, muss p entsprechend 6 sein.
Und das ist auch das, was man jetzt erwartet hätte, dass man bei 8
Kugeln, wenn man halt 3 zieht, die rot sind und eine, die schwarz ist,
dass dann entsprechend 6 Kugeln rot sein müssen in dieser Urne und die
restlichen beiden Kugeln entsprechend blau.
Und das ist nichts anderes als die mathematische Begründung dafür.
Würde man übrigens das da ableiten und 0 setzen, dann käme man raus,
dass man halt p² mal 3-4p auf 0 setzen müsste und daraus würde p
gleich 3 Viertel werden.
Also das Ding abgeleitet ist 0, der Faktor fällt weg.
Wenn das abgeleitet 0 ist, das ist dann entsprechend 3p-3p²-4p³.
Entsprechend p ausgeklammert wäre man halt bei p² mal 3-4p soll gleich
0 sein.
Das heißt, 3-4p soll gleich 0 sein.
Daraus würde kommen p gleich 3 Viertel.
Hat man Glück, kommt man zufälligerweise genau auf dasselbe raus, weil
das Ganze hier schön strukturiert ist.
Aber nur weil das hier in dem einen Fall funktioniert, heißt das
nicht, dass es bei ganzzahligen Werten immer funktioniert.
Also das ist der ganzzahlige Fall.
Das gleiche kann man halt auch entsprechend machen, wenn man jetzt
richtige Wahrscheinlichkeitsdichte-Funktionen hernimmt und da anfängt
mit Ableitungen und 0-Sätzen zu arbeiten.
Und da nehmen wir uns den einfachen Fall einer eindimensionalen Gauss
-Glocke her.
Eine eindimensionale Gauss-Glocke war so definiert, dass wenn ich mir
so ein Trainingsdatum xi hernehme, dann hat die zwei Parameter, die
hat den Mittelwert µ und die Kovarianz σ² und entsprechend ist das
Ganze 1 durch Wurzel 2π σ² mal e hoch minus x minus µ² durch 2 σ².
Dementsprechend ist meine Likelihood, die abhängt von µ und σ²,
gegeben ein Set von Trainingsdaten x und x sei eben gerade x1 bis xN,
meine Trainingsdaten, dann ist das eben entsprechend gleich Produkt
aus i gleich 1 bis N, P von xi gegeben µ σ² gleich den konstanten
Faktor vorne, diese 2π σ² die werden insgesamt N mal aufmultipliziert,
das heißt also das ist hoch N und dann bleibt halt entsprechend übrig
das e hoch minus und wenn ich jetzt hier immer e-Funktionen
aufmultipliziere, dann addieren sich entsprechend oben die Exponenten.
Summe von i gleich 1 bis N und dann diese xi minus µ zum Quadrat und
wie gesagt, die Exponenten addieren sich hier oben, Entschuldigung, da
muss einer was sagen, muss das xi rein, hier oben diese xi addieren
sich halt auf über den gemeinsamen N immer 2 σ².
Das ist jetzt erstmal nichts anderes gemacht als eingesetzt und das
kann ich auch nochmal ein bisschen umformen.
Das ist wieder dieser konstante Faktor vorne, die Wurzel schreibe ich
jetzt in der anderen Schreibweise, dass ich das hoch ½ schreibe, dann
habe ich hier entsprechend stehen 1 auf 2π σ² hoch N½ und dann forme
ich mir den Zähler im Exponenten ein bisschen um, damit dir das
hinterher leichter zu handhaben ist.
Also machen wir hier noch ein 2 σ², der gemeinsame Nenner bleibt
gleich und die Summe hier oben, die zerlege ich in der Form, dass ich
sie laufen lasse von i gleich 1 bis N xi – x²
plus N mal x² – µ² und das Ganze ergibt natürlich jetzt nur Sinn, wenn
ich mir mein x² so geschickt definiere, dass entsprechend oben wieder
das Gleiche rauskommt, wie da oben war.
Das heißt, ich brauche also ein x², das entsprechend so definiert ist,
dass ich hier das arithmetische Mittel der Werte nehme.
Das hat jetzt erstmal bisher noch überhaupt keine Bedeutung, dass ich
hier das arithmetische Mittel nehme.
Das ist einfach erstmal nur so, wenn ich hier das x² einsetzen würde,
das Ganze aussummieren würde und die Summanden wieder zusammenfassen
würde, würde erstmal da oben wieder dasselbe rauskommen.
Das macht man natürlich deshalb, wenn man weiß, dass hinterher dieser
Mittelwert, dieses arithmetische Mittel, eine entsprechend wichtige
Rolle spielen wird.
Was wir jetzt machen ist, wir nehmen den Logarithmus von dem ganzen
Teil und da man hier eine E-Funktion hat, nimmt man logischerweise
oder sinnvollerweise für den Logarithmus Naturalis.
Das heißt, ich nehme jetzt die Ableitung von dem Logarithmus
Naturalis, von dem ganzen Teil und es sind ja zwei Parameter, die ich
optimieren muss.
Ich muss einmal den Mittelwert optimieren und einmal das σ²
optimieren.
Und wenn man jetzt Glück hat, oder was heißt, wenn man Glück hat, was
man jetzt halt entsprechend machen kann ist, dass man ableitet nach
dem ersten Parameter, zum Beispiel nach dem µ und Nullsetzt und dann
danach nochmal das hernimmt, nach dem zweiten Parameter absetzt und
auch entsprechend Nullsetzt, damit man für diese beiden Parameter halt
entsprechend das lokale Maximum der Funktion findet.
Also leiten wir das Ganze ab nach dem Mittelwert µ.
Dann haben wir also hier stehen, diesen konstanten Faktor 1 durch 2π
σ² hoch in halbe mal e hoch minus.
So, da ist erstmal noch nichts passiert.
Außer, dass wir den Logarithmus entsprechend haben.
Das wollen wir ableiten, also ist das erste, was wir sinnerweise
machen, dass wir den Logarithmus reinziehen.
Das ist dementsprechend gleich die Ableitung nach µ von dem
Logarithmus, von diesem konstanten Faktor.
Ich sage immer konstanter Faktor, der ist natürlich insofern nicht
konstant, weil er von den Sigmas natürlich abhängt.
Aber in diesem Fall kümmern wir uns nur um die µ´s, der ist insofern
der Konstant innerhalb der µ´s.
Und dann hier, Logarithmus Naturalis wird halt das e, kommt halt weg,
steht halt entsprechend dann nur noch hier das, was vorher im
Exponentenstand von der e-Funktion.
So,
wenn ich irgendwo was vergesse, laut schreien.
So, jetzt kommt die erste große Herausforderung.
Ich muss jetzt ableiten.
Den ersten Summanden abzuleiten, ist einfach.
Wenn ich den nach µ ableite, kommt schönerweise 0 raus, weil da kein µ
-Ton vorkommt.
Mal Platz auf der Tafel.
Das heißt also, dass Delta nach Delta µ ist dementsprechend 0, minus
dem Ding abgeleitet.
Ist auch schön einfach, weil das nur entsprechend Summanden sind.
Wenn ich das also ableite, muss ich aufpassen, das ist also Faktor mal
einer Funktion, da muss ich irgendwo implizit ein bisschen die
Kettenregel anwenden.
Das heißt, dieses 2 durch Sigma-Quadrat bleibt erstmal stehen.
Und dann das hier oben nach µ abgeleitet.
Die Summe ist sehr schön, weil hier kommt gar kein µ drin vor.
Das µ kommt nur noch hier drin vor.
Das ist dementsprechend dann 2,
hier wichtig, minus µ, ist dementsprechend dann mit der Kettenregel
angewendet, minus 2n x²-µ.
Und das hätten wir jetzt gerne auf 0 gesetzt.
Na gut, das Ganze ist 0, wenn der Zähler 0 ist.
Der Zähler ist 0, wenn x²-µ 0 ist.
Dementsprechend muss dann gelten µ gleich x².
Und x² war eben gerade so definiert, dass wir unser arithmetisches
Mittel haben.
Das heißt, nach der Maximum-Likelihood-Methode ist das, was wir schon
die ganze Zeit wussten, dass der Mittelwert bei der E-Funktion eben
gerade dem arithmetischen Mittel über den Daten entspricht, die da so
produziert werden.
Ist damit mathematisch gezeigt, dass das auch dafür sorgt, dass die
Likelihood mit der Trainingsdaten hervorgebracht werden, mit der die
Daten von so einem Prozess, die hervorgebracht wurden, auch wirklich
mit höchster Wahrscheinlichkeit hervorgebracht wurden.
Jetzt müssen wir wieder zurückspulen, weil diese erste Umformung, die
wir da oben gemacht haben mit dem x², die haben wir ja gemacht, weil
wir dann nach dem µ ableiten konnten.
Jetzt kümmern wir uns aber um das σ².
Das heißt, das interessiert uns schon gar nicht mehr, dieser
Umformungsschritt, sondern wir müssen wieder zurückspulen zu der
ursprünglichen Likelihood-Funktion, die wir optimieren wollten.
Und die sieht halt so aus.
Was wir jetzt machen wollen, jetzt wollen wir halt entsprechend nach
dem σ ableiten.
Wir nehmen wieder den Logarithmus von dem, was da oben steht.
Wir ziehen den Logarithmus wieder rein.
Das ist dann dementsprechend die Ableitung nach σ.
Logarithmus reingezogen für das Ding.
Hier steht ja dann das Ganze mit hoch in halbe, das heißt, das kommt
da vorne vor, ist dann entsprechend in halbe mal dem Logarithmus von 1
durch 2πσ².
Und wieder ein schönes Minus.
Übrig bleibt nur dieser Exponent der E-Funktion.
Und wenn man jetzt genau hinschaut, kann man schon ahnen, dass
wahrscheinlich passieren wird, dass, wenn man die Ableitung bildet,
irgendwo so ein µ übrig bleiben wird.
Weil, wenn man nach dem µ ableitet, dann verschwindet das σ schön
brav, aber wenn man jetzt nach dem σ ableitet, wird irgendwo das µ
stehen bleiben.
Deswegen ist es auch sinnvoll, dass man erst nach dem µ optimiert hat.
Also, wir leiten das Ganze hier ab nach σ², äh, nach σ,
Entschuldigung, und müssen uns jetzt um die beiden Summanden kümmern.
Erster Summand steht in halbe Logarithmus von irgendwas und das muss
abgeleitet werden.
Ähm...
Jetzt brauchen wir ein bisschen Rechenregeln, brauchen wir ein
bisschen Hilfe.
Wer weiß noch Ableitung vom Logarithmus?
Das weiß man nicht auswendig.
Was macht man, wenn man es nicht weiß?
Man muss wissen, wo man es nachgucken muss.
Wo kann man es gut nachgucken?
Man kann googeln oder rein klassisch nimmt man was und das ist ein
Werkzeug, das jeder Informatiker immer dabei haben sollte im Büro.
Das Taschenbuch der Mathematik.
Da steht sowas nämlich zum Beispiel auch drin und da steht dann zum
Beispiel drin, dass ich, wenn ich jetzt einen Logarithmus ableite,
dass das eins durch die ganze Sache ist.
Jetzt haben wir hier aber nicht einfach den Logarithmus von irgendwas,
sondern wir haben hier den Logarithmus von einer Funktion und da gilt
Logarithmus von einer Funktion in X.
Abgeleitet ist entsprechend die Ableitung der Funktion durch die
Funktion.
Also nichts mit eins durch Logarithmus X, der da stehen bleibt,
sondern äußere Leitung mit innere Ableitung.
Und jetzt aufgepasst, muss man immer aufpassen, was die Leute auf
Google schreiben, das Ganze funktioniert nur, wenn f von X auch echt
größer Null ist.
Nur dann kann man dieses Ableitungsgesetz sicher nehmen.
Da ist jetzt die Frage, haben wir Glück?
Ja, wir haben Glück, weil hier steht ein Sigma-Quadrat.
Das heißt, Sigma-Quadrat wird nie negativ werden, also ist hier das
eins durch zwei Pi Sigma-Quadrat immer garantiert echt größer Null.
Damit können wir das Gesetz entsprechend anwenden.
Eingesetzt bedeutet das nichts anderes als das 2Pi Sigma-Quadrat hoch
minus 1.
Abgeleitet rechnet man rum, kommt man raus zu minus 1 durch Pi mal 1
durch Sigma hoch 3.
Das ist die innere Ableitung, die oben hinter MC da stehen muss.
Und dann bleibt entsprechend noch das f von X da stehen.
Dementsprechend steht dann hier, wenn ich das reingebe, steht dann
hinterher f von Strich durch f von X.
Mit f von X sei das, was hier in den Klammern steht, steht dann
hinterher entsprechend minus 1 durch Pi Sigma hoch 3.
Der Zähler mal eins durch das hier, also mal 2Pi Sigma-Quadrat und
bleibt am Ende stehen minus 2 Sigma.
Und dann kommt halt noch entsprechend das N-Halbe davor, sodass wenn
ich rechne, N-Halbe mal minus 2 Sigma-Quadrat, die 2 kürzt sich weg,
sodass am Ende nur noch stehen bleibt minus N durch Sigma, sodass am
Ende übrig bleibt minus N durch Sigma als Ableitung.
Gut, das wäre der erste Teil.
Und dann der zweite Teil.
Wenn ich den ableite nach Sigma-Quadrat, dann ist das wieder hier was
hoch minus 1, das heißt mal minus 1, dann kommt da vorne also ein Plus
hin.
Dann aus dem 2 Sigma-Quadrat wird entsprechend ein 2 Sigma hoch 3
plus, man muss dann das Ganze noch haben, was man oben stehen hat.
Achso, die 2 ist ja durch die minus 2, das heißt die kürzt sich weg,
sodass nur noch das Sigma hoch 3 stehen bleibt, weil ich ja das 2 mal
auch noch ableiten muss bei der äußeren Ableitung, sodass dann unten
nur noch ein Sigma hoch 3 stehen bleibt, entsprechend oben nur der
Zähler.
So, und das müssen wir jetzt halt entsprechend wieder Null setzen.
Und wenn wir das auf Null setzen und das alles ausrechnen, also beide
schön auf einen gemeinsamen Nenner bringen und nach Null auflösen,
dann folgt daraus, dass Sigma-Quadrat entsprechend 1 durch N, Summe i
gleich 1 bis N von x minus µ-Quadrat sein muss.
Und auf die Art und Weise haben wir dann halt auch wieder hergeleitet,
nach der Maximum-Likelihood-Methode, das Gesetz, dass das Sigma
-Quadrat eben gerade das arithmetische Mittel von der Abweichung der
Trainingsdaten von den Mittelwerten entsprechend ist.
Jetzt habe ich natürlich hier das da noch stehen.
Das ist also das einfach mal nachgerechnet für eine einfache Gauss
-Glocke.
Und wenn man sich das jetzt anschaut, dann kann man sich schon
vorstellen, wo das Problem sein könnte, wenn man das hinterher für
eine Gauss-Mixtur machen möchte.
Man kann auch für eine Gauss-Mixtur so eine Likelihood-Funktion
aufstellen.
Dann hat man hier das Produkt über die Einzelnen.
Nur das einzelne Pi, das ist dann entsprechend eine Summe.
Das heißt, ich habe hier ein Produkt über eine Summe.
Das heißt, diese schöne Umformung da mit den Potenzgesetzen, dass ich
das alles auf einen schönen Exponenten ziehen kann, das funktioniert
schon mal nicht.
Ich habe dann also stehen, Produkt über eine Summe von irgendwelchen
Gauss -Glocken.
Und wenn ich dann den Logarithmus darauf anwende, dann kann ich zwar
das äußere Produkt über die einzelnen Trainingsbeispiele noch auflösen
in eine Summe.
Dann habe ich halt Log von Gauss-Mixtur vom ersten Trainingsbeispiel
plus Log von Gauss-Mixtur vom zweiten Trainingsbeispiel.
Nur den Log in die Gauss-Mixtur, den kann ich nicht mehr reinziehen,
weil dann steht dann Log von der Summe.
Und Log von der Summe gibt es halt keine Umformungsgesetze.
Das heißt, an der Stelle bleibe ich dann stehen und das entsprechend
abzuleiten, das funktioniert halt nicht vernünftig.
Also da eine analytische Methode zu finden, dass man das dann
analytisch auf Null setzt, gibt es halt nichts.
Das heißt, selbst da komme ich dann in offensichtliche Schwierigkeiten
rein.
Und wenn ich in solche Schwierigkeiten reinkomme, hilft mir häufig
dieser Expectation-Maximization-Algorithmus weiter.
Und dieser Expectation-Maximization-Algorithmus ist diese
Überkategorie der Baumwelschregeln.
Die Baumwelschregeln sind im Prinzip nichts anderes als der
Expectation -Maximization-Algorithmus angewandt auf diskrete HMMs.
Bei diesen Problemen, die man mit dem EM-Algorithmus behandelt, geht
man von folgendem Szenario aus.
Ich habe irgendeine Zufallsvariable X, deren Parameter kann ich
beobachten.
Ich weiß also, welchen Wert diese Zufallsvariable X für die einzelnen
Trainingsbeispiele annimmt.
Ich gehe aber auch aus, dass ich nicht beobachtbare Parameter habe.
Dass ich also irgendwo noch eine zweite Zufallsvariable habe, die ich
aber nicht beobachten kann, deren Werte ich für die einzelnen
Trainingsbeispiele nicht direkt anschauen kann.
Beim HMM bedeutet das halt, ich habe die eine Zufallsvariable X, das
ist sozusagen die Ausgabe des HMMs.
Aber ich weiß, da gibt es irgendwie noch einen drunterliegenden
stochastischen Prozess, dieser stochastische Prozess, der zwischen den
einzelnen Zuständen hin und her wechselt.
Und da kann ich nicht beobachten, welchen Wert diese Variable, in
welchem Zustand bin ich, annimmt.
Ich sehe nicht, in welchem Zustand ich bin.
Das ist sozusagen meine unbeobachten Parameter.
Dieses P von X, diese Zufallsvariable, die ich beobachten kann, die
haben eine Wahrscheinlichkeitsdichtefunktion, die parametrisch sein.
Und jetzt ist die Idee, dass ich erstmal irgendwie die unbekannten
Parameter schätzen muss.
Ich muss irgendwie schätzen, welche Werte haben die denn
wahrscheinlich angenommen.
Und das macht man mithilfe der Erwartungswertbildung.
Und damit ich das natürlich schätzen kann, damit ich einen
Erwartungswert berechnen kann, brauche ich schon irgendwie einen
initialen Satz Parameter.
Das heißt, ich gehe davon aus, dass ich für meine Zufallsvariablen X
und Y schon irgendwelche initialen Parameter da habe.
Zum Beispiel zufällig irgendwie initialisiert.
Und dann, basierend auf diesen Parametern, schätze ich dann für meine
Trainingsdaten, welche Werte hat Y angenommen.
Und wenn ich das geschätzt habe, dann kann ich die Parameter von P von
X und P von Y entsprechend Maximum-Likelihood-Methode schätzen.
Dann kann ich halt dann wieder versuchen, die zu maximieren, sodass
die Likelihood maximal wird.
Also die beobachtbaren Parameter werden von der
Wahrscheinlichkeitsverteilung X geschätzt.
Aber die sind halt unvollständig.
Es gibt irgendwo was anderes.
Es gibt noch dieses Y, die wir nicht beobachten können.
Das heißt, wir haben die vollständigen Daten, die nennen wir Z, die
bestehen aus X und Y.
Und wenn ich mir jetzt die Wahrscheinlichkeit von einem einzelnen Z
gegebenen Theta anschauen will, dann habe ich das Problem, dass ich Z
nicht kenne.
Ich kenne Z nicht.
Ich weiß, es ist P von X und Y passieren, gegebenen aktuellen
Parametersatz Theta.
Das kann ich noch umformen und kann sagen, das ist P von Y gegeben X
und Theta mal P von X gegeben Theta.
Und diese Umformung liegt mir halt dazu, dass ich hinterher diese Y in
Abhängigkeit von X und Theta per Erwartungswert schätzen kann.
Und wenn ich das entsprechend so umforme, kann ich wieder die
Likelihood -Funktion aufstellen.
Eine Likelihood-Funktion, die ich in den Parametersatz Theta
optimieren will, gegeben meine Trainingsdaten Z, die aus lauter XIs
und YIs bestehen.
Sprich, das ist also Logarithmus von Theta gegeben die Trainingsdaten
X und Y.
Das sei die Wahrscheinlichkeit, die Trainingsdaten X und Y zu sehen,
gegeben Theta.
Was wir jetzt machen ist, dass wir erstmal den Erwartungswert finden
dieser logarithmierten Likelihood.
Der vollständigen Daten in Bezug auf die unbekannten Daten.
Das heißt, aus dieser Likelihood-Funktion, die eigentlich erstmal nur
über die Theta gebildet wird, diese Likelihood-Funktion, der Wert der
Likelihood, hängt auch ab von dem Parametersatz Theta hoch I minus 1,
der benutzt wird, um den Erwartungswert der unbeobachtbaren Daten zu
schätzen.
Das heißt, aus dieser Q-Funktion wird jetzt eine Q-Funktion, die
parametrisiert ist über Theta und Theta hoch I minus 1.
Mithilfe der Theta hoch I minus 1 kann ich für beliebiges Theta das Q
entsprechend aussetzen.
Das heißt logischerweise Theta hoch minus 1, weil das der
Parametersatz der letzten Iteration ist.
Ich habe also den initialen Parametersatz, ich iteriere, indem ich
immer Erwartungswert schätze, Parameter maximiere, kriege neue
Parameter, mit denen schätze ich wieder den Erwartungswert und
maximiere danach wieder.
Das heißt, in dieser Likelihood-Funktion sind diese Theta hoch minus 1
irgendwie festgegeben, die habe ich irgendwo her.
Und ich kann diese Theta variieren, die aktuellen, die neuen Parameter
variieren, und möchte so variieren, dass diese Likelihood-Funktion
entsprechend maximal wird.
Also, statt der eigentlichen tatsächlichen Wahrscheinlichkeit muss ich
jetzt den Erwartungswert ausrechnen, mithilfe der beobachtbaren Daten
und mithilfe eines alten Parametersatzes Theta, damit ich halt
schätzen kann, welche Werte Y annimmt.
Daraus folgt also, dass wir dieses Y als eine Zufallsvariable ansehen,
die halt verteilt ist gemäß einer Funktion f von Y, basierend auf den
x und den Theta i minus 1, den alten Parametersatz, den ich verwende.
Wenn wir davon ausgehen, können wir das Ganze umschreiben.
Ich habe also hier Q von Theta und Theta hoch minus 1 ist der
Erwartungswert dieser logarithmierten Wahrscheinlichkeit, P von X und
Y gegeben Theta, die wiederum eine Funktion ist, die abhängig ist von
den beobachtbaren Daten X und dem vorhergehenden Datensatz Theta minus
1.
Und da sieht es so aus, die X sind konstant, die kann ich beobachten.
Der Datensatz Theta hoch minus 1 ist auch konstant.
Und bei dieser Erwartungswertberechnung erstmal nur beim Ausrechnen
des Qs.
Wir sind noch nicht dabei, das Q zu maximieren, sondern wir wollen
erstmal nur den Wert des Qs ausrechnen für einen festen gegebenen Satz
an neuen Parametern Theta.
Dementsprechend, wenn ich also nur das Ding ausrechne, ist das Theta
an sich auch konstant.
Das heißt, das Einzige, was variabel ist, ist dieses Y.
Und wenn ich da jetzt in der Wahrscheinlichkeitsdichte-Funktion den
Erwartungswert ausrechnen will, muss ich über das Y, das ist das, was
ich variieren kann, entsprechend das Ganze integrieren.
Und hier ist eben das, dass man davon ausgeht, dass dieses Y
entsprechend irgendeiner Wahrscheinlichkeitsdichte-Funktion F verteilt
ist.
Und davon, wie diese Wahrscheinlichkeitsdichte-Funktion F aussieht,
machen wir überhaupt keine Annahmen.
Das ist eine Wahrscheinlichkeitsdichte-Funktion F, die hängt ab von
den beobachtbaren Daten X und dem alten Parametersatz Theta hoch minus
1.
Aber ich mache jetzt über die Form und welche Parameter sie vielleicht
sonst noch hat, keine Annahmen.
Und das muss ich nicht machen, weil das Schöne ist, durch dieses
Integrieren über alle Y wird das hoffentlich irgendwie handhabbar
sein, hoffentlich irgendwie verschwinden.
Diese F von X, X und Theta hoch minus 1, nennt man eine Randdichte,
der Randverteilung von Y.
Weil der Trick ist, durch dieses Integrieren über Y verschwindet diese
Variable klein y.
Und wenn ich jetzt Glück habe, ist dieses F irgendwie eine einfache
analytische Funktion, die ich entsprechend integrieren kann.
Und wenn ich das habe, dann habe ich einen geschlossenen Ausdruck
gefunden, dieser Likelihood-Funktion Q, in der das Y nicht mehr
vorkommt.
Und wenn ich es schaffe, dieses Integral über das F von Y entsprechend
schön ausrechnen zu können, dann verschwindet das Y komplett und ich
habe dann eine Q-Funktion, die gegebenen alten Datensatz Theta hoch
minus 1 mir komplett die Likelihood nur in Abhängigkeit von den
beobachtbaren Daten X ausdrückt.
Und dann kann ich anfangen, diese Q-Funktion zu maximieren, indem ich
das Theta als Variable ansehe und die Thetas wähle, die dieses Q
maximieren.
Und diese beiden Schritte variiert man dann halt.
Man findet erst den Erwartungswert von der Likelihood-Funktion Q
mithilfe der alten Parameter und dann macht man diesen
Maximierungsschritt, bekommt einen neuen Parametersatz Theta heraus,
der wird zu meinem alten Parametersatz Theta, mit dem ich wieder den
Erwartungswert berechnen kann und mit dem ich dann die nächste
Iteration neuer Thetas wieder maximieren kann.
Und das Ganze iteriere ich halt und wenn ich das iteriere, dann kann
man zeigen, dass die Likelihood-Funktion sich in jeder Iteration
verbessert oder wenn sie sich nicht verbessert, bin ich in einem
lokalen Maximum und allgemein ist es garantiert, dass auch wenn ich
das lokale Maximum nicht garantiert erreiche, dass ich zumindest gegen
ein lokales Maximum der Likelihood-Funktion konvergiere.
Und manchmal ist es schwierig, dieses Theta direkt zu maximieren.
Deswegen gibt es eine Variation, die der generalisierte EM-Algorithmus
ist.
Da sorgt man dann dafür, dass man da nicht wirklich maximiert, sondern
dass man nur irgendwie geeignet Thetas findet, sodass die Likelihood
der neuen Thetas größer ist als die Likelihood der alten Thetas.
Und auch da kann man zeigen, dass das Ganze variiert.
Jetzt hängt es natürlich alles ab von der konkreten Verteilung, mit
der diese Ys verteilt sind.
Das hängt also ab von dieser Randdichte, dieser Funktion.
Wie die Ys in den X- und den Theta-1 verteilt sind.
Und da ist ein einfaches Beispiel, das man sich anschaut für
Mixturgewichte.
Einfaches Beispiel ist übertrieben, das ist ein bisschen fummelig.
Wir haben Gauss-Mixturen kennengelernt, aber prinzipiell kann man ja
Mixturverteilung für jede beliebige Form der Wahrscheinlichkeitsdichte
-Funktion nehmen.
Wenn also pI sei eine beliebige Wahrscheinlichkeitsdichte-Funktion und
jetzt summiere ich M von denen gewichtet auf.
Das heißt, ich habe einen Satz von M Summationsgewichten Alpha.
Ich habe einen Satz von M Wahrscheinlichkeitsdichte-Verteilung P von
diesen X auf den Theta I und will jetzt P von X Theta ausrechnen.
Wenn ich da jetzt mit der Maximum-Likelihood-Methode rangehe, laufe
ich halt in dieses Problem des Logarithmuses über eine Summe rein.
Wenn ich also die Likelihood-Funktion aufstelle, ist es halt das
Produkt über alle Trainingsdaten dieser Mixtur.
Dementsprechend kann ich den Log in das Produkt reinziehen.
Der Logarithmus über die Summe über alle Trainingsdaten des
Logarithmuses einer einzelnen Mixtur für ein bestimmtes
Trainingsdatum.
Aber dasselbe ist wiederum eine Summe.
Und an der Stelle stecke ich halt fest, wenn es darum geht, abgleiten
und Null setzen.
Deswegen greift man hier dann auf den Trick zurück, dass man eine Art
Modellannahme macht.
Ich mache jetzt die Annahme, dass wenn ich so ein Trainingsbeispiel
mit einer Mixtur hervorbringe, dass das nicht so ist, dass jede
einzelne Mixturkomponente das Trainingsdatum hervorbringt und dann die
Wahrscheinlichkeiten gewichtet aufsummiert werden.
Sondern ich mache die Modellannahme, dass so eine Gauss Mixtur das in
Wirklichkeit so macht, dass im ersten Schritt eine von den
Mixturkomponenten gewählt wird mit einer bestimmten
Wahrscheinlichkeit.
Diese einzelne Mixturkomponente bringt halt die Beobachtung, die ich
gemacht habe, hervor mit der Wahrscheinlichkeit, mit der sie als
Mixturkomponente das entsprechend hervorbringt.
Und da ist natürlich die Frage, na gut, das ist so ähnlich wie beim
HMM, da wechseln wir halt zwischen Zuständen hin und her.
Hier wähle ich halt jedes Mal neu eine bestimmte Mixtur, eine
bestimmte Distribution in dieser Mixtur aus, die die Trainingsdaten
hervorbringt.
Mit welcher Wahrscheinlichkeit wähle ich die denn aus?
Und dafür ziehe ich mir eben diese Mixturgewichte her.
Die Mixturgewichte liegen in der Regel auch zwischen 0 und 1 und
müssen sich zu 1 aufsummieren, damit halt hinterher das, was bei der
Mixtur herauskommt, auch wirklich eine
Wahrscheinlichkeitsdichtefunktion ist, dass sie sich über zu 1
integriert.
Gut, also wir postulieren, dass es diese unbeobachtbaren Parameter
gibt, die sagen, welche Mixtur ausgewählt wird.
Wenn es das gibt, und angenommen wir wüssten das, wir wüssten immer,
welche Mixturkomponente ausgewählt worden wäre, dann passiert was
Schönes.
Dann passiert bei dem Logarithmus der Likelihood-Funktion, dass ich
hier wieder die Summe habe, aber hier drinnen eben nicht den
Logarithmus über eine Summe, sondern es wird ja immer nur noch eine
einzelne Mixtur ausgewählt.
Das heißt, für jedes Trainingssample wurde eine Mixtur ausgewählt.
Für das ITE-Trainingssample sei das die Dichte mit dem Index yi in der
Mixtur gewesen und die wäre entsprechend mit dem Mixturgewicht
multipliziert worden, dieser Wert.
Wenn das so wäre, dann könnte man diesen Term relativ leicht ableiten
und nullsetzen.
Wie gesagt, y ist nicht bekannt.
Ich mache diese Annahme und jetzt das große K-Wert.
Die Annahme ist natürlich falsch.
Wenn ich mir eine Mixtur anschaue, die funktioniert ja gerade nicht
so, dass eine Komponente aus der Mixtur ausgewählt wird und das ist
die einzige, die das hervorbringt.
Ich habe ja immer eigentlich die komplette Summe über alle Komponenten
und das halt mit dem Gewicht aufmultipliziert.
Aber ich mache jetzt halt hier diese Modellierungsannahme, dass ich
irgendwie weiterkomme.
Also angenommen, das sei so, dann ist y ein Zufallsvektor, der uns
nicht bekannt ist, der uns nicht optimierbar ist.
Nehmen wir uns initiale Parameter her für die Mixtur.
Das heißt, wir haben initiale Gewichte und wir haben initiale
Parameter, Kleintäter für die jeweiligen einzelnen Mixturkomponenten,
die einzelnen Dichtefunktionen.
Diese Alphas sind dann entsprechend diese A priori
-Wahrscheinlichkeiten für jede Mixturkomponente.
Das ist die A priori-Wahrscheinlichkeit dafür, dass diese
Mixturkomponente gewählt wurde.
Dementsprechend kann man das Ganze dann auch ein bisschen umschreiben,
indem man sagt, das ist halt dieses Alpha, das ich in der Iteration G
aus diesem Datensatz Theta G herausgenommen habe, nehme, mal die
Wahrscheinlichkeit, dass ich halt diese Komponente yi jetzt ausgewählt
habe, gemäß der Verteilung durch diesen Wahrscheinlichkeitsvektor y.
Und das Ganze wird dann entsprechend nummiert darüber, dass ich über
die Wahrscheinlichkeit, dass ich das xi überhaupt hervorgebracht habe
mit dieser Komponente.
Und das heißt, auf diese Art und Weise habe ich hier meine Randdichte
konstruiert für diese yis, für die Auswahl dessen, dass ich jetzt hier
die Komponente yi gewählt habe, beim Hervorbringen der Trainingsdaten
xi.
Also auf diese Art und Weise kann ich mir hier modellhaft so eine
Verteilung, so ein f von y gegebenen xi und den alten Datensatz Theta
hermachen.
Und wenn ich das Ganze entsprechend ausrechne, das hier unten ist die
komplette Mixtur.
Und das hier oben ist eben gerade der Wert, der aus dieser einzelnen
Komponente, aus der gesamten Mixtur herauskommt.
Ferner ist es so, dass wenn ich über alle Trainingsdaten drübergehe,
dann entsprechend dieses f von y, gegeben alle Trainingsdaten x,
gegeben den alten Parametersatz Theta g, halt entsprechend das Produkt
ist über diese Einzelwahrscheinlichkeiten für jedes Trainingsdatum xi
und dementsprechend das yi, das für dieses Trainingsdatum xi
ausgewählt wurde.
Und damit baue ich mir jetzt halt entsprechend diese Q-Funktion
zusammen, das ist der vorhergehenden Formel, indem ich die Q, das
abhängig mache von den neuen Parameter Theta und von dem alten
Parametersatz Theta g, hier halt die Summe bilde über alle y.
Hier brauche ich also kein Integral zu nehmen, weil ich hier diskrete
Wahrscheinlichkeitsverteilung habe, keine Dichtefunktion.
Das, was früher das Integral über alle y war, um halt diese
Randdichte, diese Marginalisierung der Randdichte zu beschreiben, wird
jetzt halt hier im Diskreten zu einer Summe über alle y und dann
entsprechend der Logarithmus dieser Q-Funktion da reingesetzt, die mit
dieser Randdichte versehen ist.
Und wenn man das Ganze dann einsetzt und rumrechnet und lange
rumrechnet, kann man das darstellen als diese Summe.
Und diese Summe besteht aus zwei Summanden.
In dem ersten Summand kommen hier noch Alphas vor und in dem zweiten
Summand kommen hier keine Alphas mehr vor.
In diesem zweiten Summand kommen diese kleinen Theta ls vor.
In diesem hier kommt kein kleiner Theta l mehr vor, sondern nur der
alte Parametersatz Theta g. Das heißt, hier habe ich wieder so einen
Fall, ähnlich wie bei meiner Gauss Mixtur, wo ich da oben auch das
immer so schön hinschreiben konnte, dass ich zwei Summanden habe und
wenn ich dann einmal nach dem einen Parametersatz ableite, wird das
null dementsprechend.
Wenn ich das hier nach Alpha ableite, wird der Summand null, weil da
keine Alphas vorkommen.
Wenn ich das Ganze nach Theta klein l ableite, wird entsprechend das
hier null, weil da kein Theta l mehr vorkommt.
Zur Erinnerung, Theta l ist der Satz an Parametern, der neu zu
schätzende Satz an Parametern der alten Mixtur.
Während diese großen, dicken Theta gs, das sind die alten Parameter,
die initialen Parameter, die ich als gegeben annehme.
Und ich will jetzt halt neue Alpha ls bestimmen.
Hier stecken auch Alpha hoch gs drin.
Ich will aber neue Alpha ls für jede Mixturkomponente bestimmen und
ich will neue Theta ls für jede Mixturkomponente bestimmen.
Und da kann man jetzt wieder entsprechend ableiten und null setzen.
Hier, an dem Fall, funktioniert das aber nicht, weil wir wieder da so
etwas Diskretes haben.
Was man hier machen kann, ist, dass man das Ganze als
Optimierungsproblem mit der Lagrange-Methode berechnet.
Weil ich habe hier nämlich auch noch Nebenbedingungen.
Ich habe zum einen die Nebenbedingung, dass die Summe über die Alpha
ls, dass sie entsprechend immer eins sein soll.
Und jetzt sagt mir die Lagrange-Methode, dass wenn ich das als
Nebenbedingung habe, wenn ich also nach so einem einzelnen Alpha l
ableite, dann ist das dieser ursprüngliche Term, den es abzuleiten
gibt, plus eine Menge von Lagrange-Faktoren.
In diesem Fall ein Lagrange-Faktor, der, guckt mal nach in meinem
Taschenbuch der Mathematik, ich weiß das auch nie immer auswendig,
dann entsprechend diesen Lagrange-Faktor erfordert, der sich ableitet
aus der Nebenbedingung.
Und das Ganze muss dann entsprechend null gesetzt werden.
Und wenn man das macht, kann man das entsprechend umformen, hier aus
dieser Doppelsumme.
Wenn ich da nach einem Alpha l ableite, nach einem Konkreten, dann
fällt entsprechend diese Summe über die ls weg und es bleibt nur noch
die Summe über die is stehen.
Und hier bleibt halt das eine Alpha l, nach dem ich ableite, übrig.
Das soll plus diesem Lagrange-Faktor Gamma gleich 0 sein.
Und daraus folgt dann, wenn man das entsprechend umformt, dass das
Alpha l dann entsprechend 1 durch n, die Wahrscheinlichkeit der
einzelnen Trainingsdaten ist, dass es die älte Komponente war,
gegeben, meinen alten Datensatz Theta g.
Das hier ist jetzt erstmal nur für allgemeine
Wahrscheinlichkeitsdichte -Funktionen.
Hier habe ich jetzt noch keine Annahme darüber gemacht, welche Form
diese Wahrscheinlichkeitsdichte-Funktion hat.
Die Alpha ls kann ich allgemein bestimmen, wenn ich diese Werte kenne.
Und das funktioniert für jede beliebige Wahrscheinlichkeitsdichte
-Funktion, die ich da in der Mixtur reinsetze und die ich da zusammen
addiere.
Jetzt müssen wir natürlich auch diese Theta klein ls optimieren.
Es reicht nicht nur, dass wir die Alpha ls bestimmen, sondern wir
brauchen ja auch neue Parameter für die einzelnen Komponenten.
Und da hängt es natürlich dann davon ab, welche Form dieses Pl
entsprechend hat.
Also angenommen, das Ganze sei eine Gauss-Verteilung.
Angenommen, wir hätten also Mixturen von Gauss-Verteilungen.
Dann sieht halt dieses Pl entsprechend so aus, wie hier eine
multivariate, mehrdimensionale Gauss-Verteilung.
Das heißt, das müssen wir jetzt entsprechend in unsere Q-Funktion
einsetzen und dann müssen wir auch ableiten und Null setzen.
Was wir hier nicht mehr brauchen, sind die Lagrange-Multiplikatoren,
weil wir hier an der Stelle keine Nebenbedingungen haben.
Die Nebenbedingungen haben wir nur bei den Alphas, weil die halt in
der Summe 1 ergeben müssen.
Bei den Parametern der einzelnen Mixturkomponenten haben wir keine
Nebenbedingungen zu erfüllen.
Und wenn man jetzt sowas ableitet, dann sieht man schon, wird das ein
bisschen fummelig, weil ich hier eine Matrix drin stehen habe.
Und um das ableiten zu können, braucht man hilfsweise die Spur einer
Matrix und so ein paar Gesetze über die Spur einer Matrix.
Man muss mit der Determinante einer Matrix umrechnen können.
Die Spur einer Matrix, der Trace von einer Matrix A, war die Summe der
Diagonalelemente.
Und dementsprechend ist der Trace auch eine lineare, zumindest in der
Addition linear.
Das heißt, der Trace einer Matrix A plus der Trace einer Matrix B ist
gleich dem Trace der beiden vorher addierten Matrizen.
Und kommutativ ist der Trace glücklicherweise in der Multiplikation,
also der Trace von zwei multiplizierten Matrizen, ist gleich dem Trace
der beiden Matrizen andersherum multipliziert.
Und daraus kann man zum Beispiel ein paar Sachen folgern.
Zum Beispiel, dass so etwas wie Summe I über XI transponiert, mal A
mal XI, dass das gleich ist dem Trace der Matrix AB, wenn ich mir B
herleite als eine Matrix, bei der ich über alle I immer XI mal XI
transponiert summiere.
Wenn ich eine Determinante einer Matrix habe, dann ist die
Determinante der Invertierten der Matrix gerade der Kehrwert der
Determinante der ursprünglichen Matrix.
Außerdem muss man sich noch daran erinnern, was es bedeutet hat, eine
Matrix abzuleiten.
Also wenn ich eine Matrix A habe und eine Funktion über diese Matrix A
habe und diese Funktion in der Matrix A nach der Matrix A ableite,
dann brauche ich sowas wie Kofaktoren.
FIJ sei der IJ-Kofaktor einer Matrix.
Wer kann sich noch erinnern an lineare Algebra, was der Kofaktor einer
Matrix ist?
Lange her.
Ist aber was ganz Einfaches, wenn ich eine Matrix A hernehme und ich
will den I und den J Kofaktor der Matrix haben, dann ist das Ergebnis
wieder eine Matrix.
Und zwar diejenige Matrix, bei der ich die I-Zeile und die J-Spalte
weggestrichen habe.
Ich hoffe, ich habe es jetzt richtig herumgesagt.
Also wenn ich dann eine Funktion über eine Matrix in der Matrix
ableite, dann ist das die Matrix mit den Elementen IJ, die rauskommt,
wenn ich die Funktion über der Matrix komponentenweise in den
einzelnen Komponenten der Matrix ableite.
Und dann kann man halt so schöne Sachen hernehmen und zeigen, dass zum
Beispiel die Ableitung, also die Funktion der Logarithmus, über der
Determinanten einer Matrix ist, wenn ich das nach der Matrix ableite,
dass das Ganze eben für den Fall, dass ich mich auf der Diagonalen
befinde, eben gerade der Kofaktor der Matrix geteilt durch
Determinante A ist.
Entschuldigung, das ist die Determinante der Matrix, wenn ich die I
-Teile und die J-Spalte streiche.
Das ist also der Kofaktor IJ, geteilt durch Determinante A.
Und wenn ich mich außerhalb der Diagonalen bewege, ist es zweimal der
Kofaktor.
Und das kann man entsprechend darstellen als zweimal A hoch minus 1
und davon abgezogen die Diagonalen der Inversen von A.
Und man kann auch zeigen, dass wenn man jetzt für diese Funktion F die
Spur des Produktes einer Matrix mit einer anderen Matrix einsetzt, und
das Ganze nach A ableitet, dass dann am Ende herauskommt, B plus B
transponiert minus den Diagonalelementen von B.
Wenn ich jetzt also diesen EM-Algorithmus auf die Gauss-Mixturen
anwende und mir jetzt die kleinen Theta-Ls optimieren will.
Das hier war meine Q-Funktion, die gilt es zu optimieren.
Diese Q-Funktion konnte man zerlegen in so zwei Teile, wo einem kam
nur Alpha vor, dem anderen kamen nur Theta-Ls vor.
Jetzt, wenn man nach den Theta-Ls optimiert, ist es angenehmer,
geschickter, wenn man hier eine andere Umformung wählt.
Und die Umformung sieht dann entsprechend bei den Gauss-Mixturen dann
so aus, dass ich hier dann etwas drin stehen habe, wenn ich das
logarithmiere und das entsprechend in die Gauss-Mixtur einfüge, dass
ich vorne einen Minus-halb-Logarithmus der Determinanten von der
Kovarianz -Matrix habe.
Und wie bei der einzelnen Gauss-Glocke ist dieses aus der Wurzel,
diesem hochen Minus-halb, das wurde entsprechend da vorne vorgezogen.
Der Logarithmus wurde unten in den Nenner mehr oder weniger
reingezogen.
Der Nenner war dieses Minus-hoch-eins.
Dieses Eins-durch habe ich durch den Minus-Faktor da vorne
rausgezogen.
Es bleibt also übrig Logarithmus der Determinante von Sigma-L.
Und hier hinten, die E-Funktion ist halt weggefallen.
Und übrig bleibt der Exponent, der da stand.
Und das Ganze dann halt auch mal der Randdichte P von L gegeben XI,
den alten Parametersatz Theta.
Und jetzt habe ich da die Sigmas drin stehen und die Mus drin stehen.
Und das Schöne ist, dass ich hier wieder zwei Summanden habe.
In einem Summand kommt nur die Sigma-Ls vor, nur die Kovarianz
-Matrizen.
In dem anderen kommen die Sigma-Ls und die Mus vor.
Wenn ich jetzt das da hinten mal, wenn ich das Gesamte nach den Mus
ableite, dadurch, dass hier keine Mus mehr vorkommen, fliegt das weg,
bleibt das da nach den Mus abgeleitet übrig.
Und das ergibt sich dann entsprechend, wenn man es umrechnet, zu
dieser Summe über alle Trainingsdaten, zu der Summe über alle...
Also es ist nach einem MuL abgeleitet.
Summe über alle Trainingsdaten und dann eben diese Kovarianz der alten
Komponente hoch minus 1 mal XI minus MuL mal der Randdichte.
Und das Ganze soll entsprechend auf Null gesetzt werden.
Und wenn man das dann entsprechend nach Mu auflöst, kommt man dann
hinterher dahin, dass man dann den Mu als den Quotienten hat.
Einmal hier aus der Summe aller Wahrscheinlichkeiten der jeweils
einzelnen Trainingsdaten.
Und zwar der alten Komponente, wenn ich überhell habe.
Und oben im Zähler habe ich die Summe stehen aller Trainingsdaten XI
mal ihrer Wahrscheinlichkeit, dass sie von der alten Komponente
hervorgebracht wurden.
Und wenn man sich das jetzt anschaut, dann ist das gar nicht so viel
unterschiedlich als das eigentliche arithmetische Mittel, das ich bei
einer einzelnen Gauss-Glocke habe.
Bei einer einzelnen Gauss-Glocke hätte ich da oben einfach stehen
Summe über alle XI geteilt durch die Anzahl der Trainingsdaten, die
ich habe, in diesem Fall also N.
Jetzt ist hieraus ein klein bisschen was anderes geworden.
Wenn ich hier unten zum Beispiel N stehen haben wollte, könnte ich ja
schreiben Summe von I gleich 1 bis N über 1.
Das wäre Groß N.
Jetzt wird hier aber nicht über 1 summiert.
Das heißt, für jedes neue Trainingsdatum, das ich bekomme, wird die
Anzahl der Trainingsdaten nicht um 1 hochgezählt, sondern es wird
hochgezählt, gewichtet mit der Wahrscheinlichkeit, dass jetzt halt
diese eine Komponente diese Trainingsdaten hervorgebracht hat.
Man kann also sagen, das ist so eine Art gewichtetes Zählen der
Trainingsdaten, gewichtet mit ihrer Wahrscheinlichkeit, dass sie von
dieser einen speziellen Komponente überhaupt hervorgebracht wurden.
Im Zähler steht halt nicht einfach die Summe über alle Trainingsdaten,
sondern jedes einzelne Trainingsdatum wird halt nochmal gewichtet mit
seiner Wahrscheinlichkeit, dass es von dieser elten Komponente
hervorgebracht wurde.
Das heißt, das Ganze ist eigentlich der Maximum-Likelihood-Schätzung
sehr ähnlich, nur dass ich anders zähle und anders addiere.
Ich zähle jetzt halt gewichtet und ich addiere immer gewichtet mit der
Wahrscheinlichkeit der jeweiligen elten Komponente.
Und auf die Art und Weise kann ich halt den Mittelwert der elten
Komponente schätzen.
Und was Gleiches kann ich jetzt machen, wenn ich nach den
Kovarianzmatrizen optimieren will.
Dann schreibt man diese Summe, wo man vorher diese beiden schönen
Summanden hatte, um und wenn man diese ganzen Regeln für Spur und so
weiter anwendet, dann kann man das Ganze umschreiben als diesen Term,
wobei man sich hier noch Hilfsmatrizen N, L, I entsprechend definieren
muss.
Und diese N, L, I setzen sich gerade zusammen aus Vektorprodukten von
dem XI und der Abweichung von den µ´s.
Und das kann ich dann entsprechend nach Sigma hoch minus 1 ableiten
für die elte Komponente.
Dann fällt wieder die Summe über die einzelnen Komponenten weg.
Es bleibt nur noch die elte Komponente übrig.
Und dann kann ich das halt entsprechend der Regeln, die ich vorher
hatte, ein paar Mal umformen.
Und dann kommt am Ende raus, dass man da hat die Differenz aus zweimal
einer Matrix S minus ihrer Diagonalmatrix, der Matrix, die ich bilde,
indem ich nur die Diagonale der Matrix S nehme.
Und das funktioniert dann, wenn ich diese Matrix S entsprechend wähle.
Und wenn ich das Ganze auf Null setzen will, also wenn das Null werden
soll, dann wird das genau dann Null, wenn die Matrix S selber die
Nullmatrix ist.
Und wenn ich das dann entsprechend auflöse, bekomme ich halt wieder
hier so eine Schätzung für die Kovarianz Matrix Sigma L.
Und die sieht wieder im Prinzip analog genauso aus wie die Schätzung
der einzelnen Gauss-Glocke, wenn ich nur eine einzelne Gauss
-Multivariate -Gauss-Verteilung habe.
Wieder mit dem Unterschied, dass ich hier nicht zähle über die Anzahl
der Trainingsdaten, sondern Gewichte zähle.
Jedes einzelne Trainingsdatum wird beim Zählen gewichtet mit seiner
Wahrscheinlichkeit.
Und wenn ich hier oben diese Abweichung, die Kovarianz, die Abweichung
eines Trainingsdatums vom eigentlichen Mittelwert, bin ich auch das
entsprechend immer gewichte mit der Wahrscheinlichkeit dafür, dass
dieses spezielle Trainingsdatum jetzt gerade von dieser speziellen
Komponente hervorgebracht wird.
Gut, das ist jetzt ein bisschen erschlagend.
Aber wir sind jetzt schon in der Lage, für Gauss-Mixtur-Modelle
entsprechend die Parameter nach dem EM-Algorithmus zu schätzen.
Jetzt haben wir das gleiche Problem bei HMMs.
Zum Beispiel bei diskreten HMMs haben wir auch das Problem, dass wir
da nicht alles beobachten können, die Zustände, in denen ich mich
befinde, entsprechend nicht beobachten kann.
Das sind also meine beobachtbaren Parameter.
Jetzt kann ich für so ein HMM auch wieder eine Q-Funktion herstellen,
die halt basiert auf einem alten Parametersatz Lambda und auf einem
neuen Parametersatz.
Und da muss ich halt dann wieder den Erwartungswert dafür hernehmen.
Jetzt habe ich hier natürlich drinstecken, dass ich im Prinzip über
alle möglichen Zustandsfolgen so eine Wahrscheinlichkeit ausrechnen
kann.
Jetzt nimmt man sich halt mal eine mögliche Zustandsfolge her und
überlegt sich, was ist...
also hier ist die Summe über alle möglichen Zustandsfolgen.
Und dann habe ich halt entsprechend die logarithmierte
Wahrscheinlichkeit davon, dass ich jetzt gerade diese Zustandsfolge
gesehen habe, mal die Wahrscheinlichkeit von diesem OQ gegeben meinen
alten Parametern Lambda Strich.
Das hier ist relativ leicht auszudrücken.
Das ist gerade das generative Modell des HMMs, also so wie das HMM
halt Beobachtungen hervorbringt.
Das ist halt die Wahrscheinlichkeit dafür, dass ich am Anfang im
Zustand 0 bin und dann entsprechend immer die Übergänge mache von Qt-1
nach Qt, so wie es mir die Zustandsfolge Q vorgibt und dann
entsprechend im Zustand Qt auch immer das gewünschte Symbol OT
hervorbringe.
Das da oben eingesetzt und das Ganze ein bisschen umgeformt, ergibt
diese Summe.
Und diese Summe besteht halt auch wieder aus drei Teilen.
Und das Schöne ist, wenn man jetzt guckt, im ersten Teil dieser Summe
kommen hier nur die P's vor, hier kommen nur die
Übergangswahrscheinlichkeiten A vor und hier kommen nur die
Emissionswahrscheinlichkeiten BQT vor.
Und das sind ja wieder gerade die drei Parameter, nach denen ich
optimieren will.
Ich muss also nach den P's optimieren, nach den A's optimieren und
nach den B's optimieren.
Und jetzt also ableiten und Null setzen, sorgt dafür, dass sich immer
einer der Summanden jetzt jeweils übrig bleibt.
Das heißt, ich kann also jeden einzelnen Summanden separat optimieren,
um dann hinterher die Summe zu maximieren.
Wenn ich jetzt den ersten Summanden optimiere, ist das der mit den
PQ's.
Den kann ich mir entsprechend so hinschreiben.
Weil hier in dieser Summe über alle möglichen Zustandsfolgen das Q ja
eigentlich nur noch abhängt von dem Q Null.
Alle anderen Zustandsfolgen interessieren mich gar nicht mehr.
Das heißt, hier habe ich im Prinzip nur noch die Auswahl zwischen N
Zuständen, die ich für diesen ersten Zustand wähle.
Das heißt, hier habe ich jetzt nur noch die Summe von I bis N dieser
Log PIs, mal, dass ich halt die Ausgabe mache und am Anfang mich im
ersten Zustand Null, also zum Zeitpunkt Null im Zustand I befinde.
Das ist sozusagen, das nennt man dann, kann man sich anschauen als
eine Marginalisierung für den Zeitpunkt Null.
Weil wenn ich da über alle Q's rüber summiere, dann brauche ich hier
statt der Wahrscheinlichkeit der Ausgabe für ein bestimmtes Q, für
alle Q, nur noch die Ausgabe unter der Annahme, dass ich mich zum
Zeitpunkt Null im Zustand I befinde.
Und das ist wieder ein Ausdruck, den ich mit Hilfe von Lagrange
-Faktoren, Lagrange-Methode optimieren kann, Optimierung unter
Nebenbedingungen, weil die Summe über alle PIs muss halt wieder 1
ergeben.
Dementsprechend habe ich hier hinten wieder so Lagrange-Faktoren, die
zu dieser Nebenbedingung führen.
Ich muss das Ganze Null setzen und wenn ich das Ganze ableite und Null
setze, dann komme ich eben gerade wieder auf diese Schätzung, die ich
schon hatte bei den Baum-Weltsch-Regeln, dass halt die
Anfangswahrscheinlichkeit für einen Zustand I ist eben gerade die
Wahrscheinlichkeit, dass ich mich zum Zeitpunkt Null im Zustand I
befinde, geteilt durch die Wahrscheinlichkeit, dass das HMM sowieso
überhaupt die O's ausgegeben hat.
Dann kann ich mir den zweiten Teil hernehmen, der sich mit den
Übergangswahrscheinlichkeiten beschäftigt.
Hier habe ich wieder das Summe über alle Q, dann über alle Zeitpunkte
und gucke mir dann immer diesen Q-1 nach Qt an.
Und da interessiert mich ja jetzt im Prinzip nur noch nicht mehr, was
vor T-1 war und was nach T kommt, sondern mich interessiert nur dieser
Zeitpunkt T-1 nach T und wie die Zustandsfolge Q sonst aussieht,
interessiert mich nicht.
Das muss ich natürlich machen für alle möglichen Zustände T, deswegen
hier die Summe über die T, aber wie die Qs dann außerhalb dieses
Zeitpunktes T-1 nach T aussehen, interessiert mich nicht mehr.
Das ist also eine Marginalisierung dieser Wahrscheinlichkeit auf den
Zeitpunkt T hin.
Das heißt, bekachte hier nur noch alle Übergänge von Zustand I nach
Zustand J beim Zeitpunkt T-1 nach T.
Das kann man wieder optimieren mit der Lagrange-Methode, weil hier ist
die Nebenbedingung halt, dass für jedes I die Wahrscheinlichkeiten,
dass ich vom Zustand I nach Zustand J gehe, über alle möglichen
Nachfolgezustände J summiert, muss halt entsprechend eins sein, sonst
ist es keine Wahrscheinlichkeitsverteilung.
Und wenn man das Ganze wieder optimiert unter den Nebenbedingungen,
kommt man wieder genau zum gleichen Term, den man auch bei den Baum
-Weltsch -Regeln hat.
Das ist halt die Wahrscheinlichkeit, dass man vom Zustand I nach
Zustand J übergeht, unabhängig von der Zeit, also zu jedem Zeitpunkt,
geteilt durch die Wahrscheinlichkeit, dass ich mich überhaupt zum
Zeitpunkt T-1 im Zustand I befunden habe.
Und das Ganze halt entsprechend in der Abhängigkeit von den Lambda
-Strichs.
Und dann kann man sich halt noch den dritten Summanden vornehmen, der
die Ausgabewahrscheinlichkeiten, die Bi´s, enthält.
Hier habe ich jetzt wieder eine Marginalisierung zum Zeitpunkt T.
Mich interessiert ja nur noch zum Zeitpunkt T, wie sieht die
Zustandsfolge aus.
Also zum Zeitpunkt T muss ich im Zustand I sein, ansonsten sind alle
anderen Zustände beliebig.
Was heißt beliebig?
Sie müssen halt, dürfen alle anderen Zustände umfassen.
Und das Ganze wird halt auch wieder optimiert unter den
Nebenbedingungen, dass halt für jeden Zustand die Summe der
Ausgabewahrscheinlichkeiten sich zu eins ergibt.
Und wenn ich das entsprechend mache, komme ich halt auch wieder zu
dieser Schätzung, dass ich zum Zeitpunkt T im Zustand I bin und dass
ich dann auch wirklich zu dem Zeitpunkt T das Symbol Vk ausgegeben
habe.
Das ergibt sich zu meinem BiK.
Wir hatten letztes Mal das Ganze geschrieben mit dieser Schreibweise
subject to S.T., dass OT gleich Vk ist.
Hier ist es nur anders geschrieben mit dem Chroniker-Symbol Delta.
Delta, OT und Vk ist eben genau dann eins, wenn OT gleich Vk ist und
ansonsten Null.
Ist einfach nur eine andere Schreibweise.
Und das Ganze halt entsprechend geteilt durch die Wahrscheinlichkeit,
dass ich überhaupt die Gesamtausgabe hervorbringe und zum Zeitpunkt T
mich im Zustand I befinde.
Gut.
Damit können wir schon mal diskrete HMMs hervorbringen.
Interessant wird es jetzt natürlich, wenn ich statt diskreter HMMs mit
so diskreten Ausgabe-Wahrscheinlichkeitsverteilungen, BiKs, wenn ich
jetzt übergehe und da mit Wahrscheinlichkeitsdichte-Funktionen
arbeite.
Wenn es nur eine einzelne Gauss-Glocke ist, habe ich mehr oder weniger
kein Problem.
Aber ich will ja diese Parameter dann entsprechend auch optimieren.
Zum Beispiel möchte ich, dass ich da Gauss-Mixturen habe.
Und was ich dann machen kann, wie ich dann so einen doppelt
verschachtelten EM-Algorithmus machen kann, der mir gleichzeitig die
Parameter meines HMMs optimiert und zusätzlich noch die Parameter
meiner Gauss-Mixtur optimiert, das schauen wir uns dann nächstes Mal
noch kurz an.
Okay.