Herzlich willkommen zurück zu Grundlagen der automatischen
Spracherkennung.
Wir hatten letztes Mal schon angefangen, uns mit HMMs zu beschäftigen
und werden heute so die ganzen Themen, die rund um HMMs für uns
interessant sind, der Reihe nach abarbeiten.
Zur Erinnerung, wir befinden uns in der stochastischen
Spracherkennung, wo wir mithilfe der Fundamentalformeln nach der
wahrscheinlichsten Wortfolge suchen wollen.
Und eine der Wahrscheinlichkeiten, die wir berechnen wollen, ist
dieses P von Merkmalsvektor gegeben Klasse.
Und gerade das werden wir entsprechend mit Hidden-Markov-Modellen
realisieren.
Wir werden also dieses akustische Modell, wie wir es genannt haben,
mithilfe von Hidden-Markov-Modellen realisieren.
Jetzt haben wir uns letztes Mal schon angeschaut, was ist so ein
stochastischer Prozess, was ist ein Markov-Modell und hatten uns
überlegt, was ist anders bei Sprache, das ich nicht mit dem normalen
Markov -Modell einfangen kann.
Und das ist eben die Tatsache, dass von einem Merkmalsvektor, den ich
sehe, ich nicht direkt ableiten kann, aus welchem Zustand heraus wurde
der denn emittiert, sondern der Zustand ist mir verborgen.
Und das kann man zum Beispiel anschaulich machen mit Hilfe eines
kleinen Gedankenexperimentes, das wir uns vorstellen, ein einfaches
Münzwurfexperiment.
Das einfachste Münzwurfexperiment, das Sie kennen, ist, Sie nehmen
halt eine Münze her, die zu 50 Prozent der Fälle Kopf und zu 50
Prozent der Fälle Zahl zeigt, wenn sie geworfen wird und dann können
Sie die Münze werfen und lesen dann halt ab, ob jetzt Kopf oder Zahl
gekommen ist und dann haben Sie so einen zeitstochastischen Prozess.
Jeder Münzwurf ist ein Zeitschritt und das Ereignis, das halt passiert
zu jedem Zeitpunkt, ist halt entweder Kopf oder Zahl ist gefallen.
Jetzt mache ich es mir ein bisschen komplizierter.
Jetzt habe ich nicht mehr eine Münze, sondern jetzt habe ich zwei
Münzen.
Und diese Münzen sind jetzt keine idealen Münzen mehr, sondern sie
sind gezinkte Münzen.
Das heißt, Sie haben nicht mehr so eine 50-50-Prozent
-Wahrscheinlichkeit, sondern bei der einen Münze kommt Kopfhalt mit 30
Prozent und Zahl mit 70 Prozent und bei der anderen Münze kommt
Kopfhalt mit 55 Prozent und Zahlhalt mit 45 Prozent.
Und mein Münzwurfexperiment sieht jetzt so aus, dass ich beide Münzen
vor mir liegen habe.
Ich wähle eine von beiden Münzen aus.
Zufällig.
Ich habe einen Zufallsgenerator, der sagt mir, eine von beiden Münzen
wählst du aus.
Die werfe ich und bekomme wieder ein Ergebnis.
Jetzt sehe ich noch die Münzen.
Jetzt weiß ich, okay, ich habe mich entweder für diese Münze oder für
diese Münze entschieden.
Und jetzt mache ich da einen Vorhang davor.
Das heißt, Sie können jetzt nicht mehr direkt beobachten, für welche
Münze entscheidet sich denn der Werfer, sondern irgendwo hinter dem
Vorhang wählt der Münzwerfer eine von den beiden Münzen aus.
Nach irgendeiner Wahrscheinlichkeitsverteilung.
Er wirft diese Münze hinter dem Vorhang und sagt Ihnen jetzt, es war
entweder Kopf oder es war Zahl.
Das Einzige, was Sie jetzt also noch hören, ist, war es Kopf, war es
Zahl, aber der Zustand, die Münze, die jetzt Kopf oder Zahl erzeugt
hat, die kennen Sie nicht mehr.
Die ist hinter dem Vorhang verborgen.
Und jetzt muss man anfangen, wie kann man jetzt in so einem Fall diese
Wahrscheinlichkeiten dieser Ereignisfolgen, die man bekommt,
berechnen.
Angenommen, ich weiß, es gibt, ich weiß auch nicht, wie viele Münzen
es gibt.
Also angenommen, da hinten liegt eine unbekannte Anzahl an Münzen.
Die Münzen sind gezinkt.
Ich wähle zufällig eine aus, werfe, lege die hin und wähle dann wieder
zufällig eine aus.
Abhängig davon, welche Münze ich jetzt als letztes gewählt habe und
dann werfe ich wieder.
Ich kann das jetzt nicht mehr beobachten.
Ich weiß nicht mehr, wie viele Münzen es sind.
Ich weiß nicht, welche Münze wann gewählt wird.
So was kann man jetzt mit Hilfe von hinten Markov-Modellen versuchen
zu modellieren.
Angenommen, ich gehe davon aus, das Ganze wäre nur eine Münze.
Ich hätte eine Münze.
Dann kommt man mit einer Markov-Kette aus.
Dann habe ich zwei Zustände.
Der eine Zustand heißt Kopf.
Der andere Zustand heißt Zahl.
Und ich wechsel zwischen diesen beiden Zuständen hin und her bei einer
Münze.
Und die Wahrscheinlichkeit, mit der ich hin und her wechsle, kann ich
sogar genau angeben.
Wenn das eine ideale Münze ist, wenn das eine gezinkte Münze wäre,
könnte ich es immerhin versuchen zu schätzen aus diesen Folgen, die
ich da bekomme.
Also ein Zustand entspricht der Ausgabe.
Ein Zustand entspricht Kopf.
Ein Zustand entspricht Zahl.
Zustand gleich Ausgabe.
Und ich muss mich nur darum kümmern über die Wahrscheinlichkeiten, wie
ich zwischen diesen Zuständen hin und her wechsle.
Jetzt gehe ich dazu über und nehme mir nur noch zwei Münzen her.
Zwei unterschiedliche Münzen mit unterschiedlicher Verteilung,
zwischen denen ich irgendwie zufällig hin und her wechsle.
Jetzt kann ich immer noch zwei Zustände haben, aber diesmal
entsprechen die Zustände dann nicht mehr dem Ereignis Kopf oder Zahl,
sondern die Zustände entsprechen jetzt den Münzen.
Ich habe also einen zufälligen Prozess, der sorgt erst mal für den
Wechsel zwischen den einzelnen Münzen.
Wenn ich eine Münze ausgewählt habe, dann werfe ich und dann mit einer
bestimmten Wahrscheinlichkeit wähle ich entweder die andere Münze oder
ich bleibe bei meiner Münze.
Und wenn ich die Münze werfe, dann ist die Wahrscheinlichkeit, Kopf
oder Zahl zu bekommen, abhängig davon, welche der beiden Münzen ich
werfe.
Dementsprechend bekomme ich für den Zustand 1 eine Verteilung von Kopf
oder Zahl, die anders sein kann und meistens auch anders ist als die
Verteilung vom Zustand 2.
Und kann damit dann auch erst mal wieder solche Beobachtungssequenzen
zumindest schon mal immerhin generieren, indem ich jetzt einfach diese
beiden stochastischen Prozesse durchlaufen lasse.
Ich lasse erst den stochastischen Prozess für die Münzwahl laufen und
dann, je nachdem in welchem Zustand ich bin, lasse ich den
stochastischen Prozess für die Generierung von Kopf oder Zahl laufen.
Oder man kann sich überlegen, was ist, wenn er drei Münzen hat.
Angenommen, ich habe drei Münzen mit unterschiedlicher
Wahrscheinlichkeitsverteilung, dann brauche ich halt entsprechend drei
Zustände.
Jede Münze ein Zustand, dann brauche ich diese
Wechselwahrscheinlichkeiten, mit der ich vom, wenn ich als letztes die
Münze 3 geworfen habe, mit welcher Wahrscheinlichkeit wechsle ich
jetzt zur Münze 1, zur 2 oder behalte die Münze 3.
Und ich brauche die Wahrscheinlichkeitsverteilungen für jede Münze,
die mir sagen, wie weit ist sie denn jetzt beeinflusst, mit welcher
Wahrscheinlichkeit kommt Kopf oder Zahl bei welcher Münze.
Wenn ich jetzt nicht weiß, wie viele Münzen tatsächlich hinter dem
Vorhang lauern und wie viele Münzen tatsächlich geworfen werden, kann
ich mir jetzt überlegen, wie gut passt denn welches Modell für welche
Szenarien.
Erstmal haben die Modelle natürlich unterschiedliche Parameter.
Das erste Modell, wo ich ganz klar weiß, ich habe nur eine Münze, habe
ich genau zwei Parameter.
Ich habe die Wahrscheinlichkeit, habe ich genau einen Parameter.
Ich habe die Wahrscheinlichkeit für Kopf.
Und da Wahrscheinlichkeiten sich zu eins addieren, kommt daraus
automatisch die Wahrscheinlichkeit für Zahl ist halt 1 minus
Wahrscheinlichkeit von Kopf.
Für das nächste Modell mit den zwei Münzen habe ich schon deutlich
mehr Parameter.
Ich habe einmal einen Parameter hier, der mir sagt, wie hoch ist die
Wahrscheinlichkeit für die erste Münze für Kopf.
Dann habe ich einen Parameter hier, der sagt mir, wie hoch ist die
Wahrscheinlichkeit für die zweite Münze für Kopf.
Und dann brauche ich noch diese Wechselparameter.
Für jede Münze habe ich einen Parameter, mit dem er sagt, wie
wahrscheinlich ist es, dass ich die andere Münze nehme oder dass ich
die Münze beibehalte.
Und dann ist 1 minus die Wahrscheinlichkeit, halt die
Wahrscheinlichkeit dafür, so ich sich zur anderen Münze wechsel.
Das heißt, insgesamt habe ich also hier vier Parameter.
Und bei dem Modell habe ich entsprechend erstmal bei den Emissionen,
Kopf oder Zahl, hier drei Parameter.
Und dann brauche ich immer pro Zustand zwei Parameter und der dritte
Parameter ergibt sich von selbst.
Damit wären wir dann entsprechend bei neun Parametern.
Das heißt also, wenn man jetzt erstmal sich nur von den Parametern her
anschaut, dann ist natürlich das Modell 3 das mächtigste.
Und je mehr Parameter ich habe, desto flexibler bin ich allgemein in
dessen, was ich modellieren würde.
Wenn ich jetzt nur eine Münze hätte, eine Münze tatsächlich hätte
hinter diesem Vorhang, hinter den ich nicht blicken kann, dann wäre
das Modell 3 eigentlich schon viel zu mächtig, hätte viel zu viele
Parameter.
Aber wenn ich genügend Daten habe, könnte ich die Parameter so
schätzen, dass es trotzdem genau das, die Wahrscheinlichkeit berechnen
würde für den Prozess, wie er tatsächlich abläuft.
Das heißt, das Modell wäre zwar zu mächtig, aber es wäre in der Lage,
den tatsächlichen Prozess zu modellieren.
Hätte ich vier Münzen, dann wäre das Modell nicht mächtig genug,
sondern wäre fehlerhaft und könnte halt, auch egal wie viele
Trainingsdaten ich habe, könnte die Realität entsprechend nicht genau
genug abbilden.
Das heißt, das sind also erstmal so ein paar Überlegungen dazu.
Anzahl der Parameter, der Flexibilität des Ganzen.
Wenn man jetzt allgemein beschreiben will, was da passiert, dann
arbeitet man nicht mit Münzen, weil Münzen haben halt nur zwei
Ereignisse, Kopf oder Zahl, sondern man arbeitet allgemein mit diesem
Urne -Ball-Modell.
Man geht also davon aus, dass man irgendwie eine bestimmte Anzahl an N
unterschiedlichen Urnen hat.
Diese Urnen sind mit Bällen unterschiedlicher Farbe befüllt und das
Mischverhältnis in jeder Urne ist halt von Urne zu Urne
unterschiedlich.
Und der Prozess selber sieht jetzt so aus, dass ich mir eine
Anfangsurne zufällig auswähle.
Ich ziehe einen Ball heraus, schaue mir an, welche Farbe der hat, lege
den Ball wieder zurück und dann wähle ich eine neue Urne aus, in
Abhängigkeit davon, aus welcher Urne ich jetzt als letztes gezogen
habe.
Und dann führt man das halt so lange durch, wie man möchte und notiert
sich halt die Farbe der Bälle, die man so bei diesem Prozess gezogen
hat.
Und diesen Prozess, den modelliert man halt genau mit einem
Hindenmarkov -Modell.
So etwas kann man genau mit einem Hindenmarkov-Modell modellieren und
formal ist ein Hindenmarkov-Modell definiert als dieses Fünftupel,
bestehend aus einer Menge an Zuständen.
Ich habe halt N Zustände, so viele Zustände wie ich Urnen habe.
Zu jedem Zeitpunkt bin ich in einem dieser Zustände, habe ich also
eine Urne ausgewählt, notiert man dann meistens mit qt gleich sj, also
der Zustand q zum Zeitpunkt t ist sj.
Dann habe ich ein Alphabet, ein diskretes Alphabet mit m Symbolen.
Das sind die m verschiedenen Farben, die meine Bälle haben können.
Alternativ hat man dazu manchmal auch einen kontinuierlichen
Ausgaberaum, zum Beispiel die Menge der reellen Zahlen oder n
-dimensionale Vektoren über reelle Zahlen.
Ich habe eine Anfangswahrscheinlichkeitsverteilung.
Das ist die Verteilung, die mir sagt, am Anfang, welche Urne wähle ich
denn als erstes aus.
Kann man einfach als Vektor darstellen.
Und ich habe Übergangswahrscheinlichkeiten.
Das heißt, ich habe Wahrscheinlichkeiten, die sagen mir, wenn ich als
letztes aus einer Urne gezogen habe, wie groß ist die
Wahrscheinlichkeit, in irgendeine andere beliebige Urne überzugehen.
Und dann habe ich zum Schluss diese Emissionswahrscheinlichkeiten, die
mir das Mischverhältnis der Ballfarben in jeder Urne angeben.
Die mir also sagen, wenn ich zufällig aus dieser Urne, die zu diesem
Zustand gehört, ziehe, mit welcher Wahrscheinlichkeit wird welche
Farbe aus dieser Urne gezogen.
Das sind die Emissionswahrscheinlichkeiten b, bjk, k halt entsprechend
der Index eines Elements aus meinem Alphabet und gegeben, dass ich
mich zum Zeitpunkt qt halt in einem Zustand sj befinde.
Und das erste, was man halt wieder machen kann mit so einem HMM, ist
eine Beobachtungsgenerierung.
Ich kann Beobachtungen generieren, deswegen nennt man das Ganze ein
generatives Modell.
Initialen Zustand auswählen, Zeit auf 1 setzen.
Erste Ausgabe zum Zeitpunkt 1 ist halt das Symbol vk, das ich gemäß
seines bj von k halt entsprechend gezogen hätte.
Wird halt gewürfelt gemäß der Wahrscheinlichkeitsverteilung in der
Urne und dann entsprechend die Farbe ausgegeben.
Dann wird die Zeit, dann mache ich einen Übergang in die nächste Urne,
in Abhängigkeit davon, in welcher Urne ich bin.
Und dann erhöhe ich die Zeit.
Wird der Zeitindexzähler um 1 erhöht und solange ich halt noch ziehen
will, zähle ich halt.
Und wenn ich genug gezogen habe, zum Beispiel ein Zeitlimit T erreicht
habe, lasse ich das Ganze, beende ich den Prozess, diesen generativen
Prozess und bekomme heraus eine Folge von Beobachtungen.
Wenn man jetzt in die Literatur gibt, sieht man manchmal auch eine
alternative Definition von HMMs.
Das wäre die Definition nach IBM.
Die machen das so, dass die Beobachtungen nicht an die Zustände
drankommen, sondern dass die Beobachtungserzeugung beim
Zustandsübergang passiert.
Und jeder Zustandsübergang hat eine eigene
Wahrscheinlichkeitsverteilung.
Wenn Sie jetzt zurückdenken ans Grundstudium, da hatten Sie sowas
kennengelernt wie Miele und Moorautomaten.
Da war genauso ein ähnlicher Unterschied.
Die einen haben halt die Ausgabe an den Zuständen gehabt und die
anderen haben halt die Eingabe, Ausgabe an den Übergängen gehabt.
Und man konnte zeigen, dass beide Modelle gleichmächtig sind.
Genauso ist das hier, ob ich jetzt am Zustand die Ausgabe mache oder
ob ich die Ausgabe an den Übergang knüpfe, ist von der Mächtigkeit her
genau gleich.
Man muss halt hinterher nur ein bisschen anders rechnen.
Man kann auch das eine Modell immer in das andere Modell überführen.
Manchmal verwendet man zur Visualisierung der Ausgabe, die so ein HMM
macht, die sogenannte Trellis, auf gut Deutsch das Pflanzgitter, das
Pflanzgatter.
Das ist halt wie so ein Gatter, so ein Rechteckgatter, wo halt
Pflanzen dran landen können.
Die eine Dimension in der y-Achse entspricht den Zuständen.
Auf der x-Achse trage ich halt die Zeit ab und mit dieser Fieberkurve
da wird halt immer angedeutet, zu welchem Zeitpunkt bin ich in welchem
Zustand und dann schreibt man unter die Zeitachse für jeden Zeitpunkt
noch die Beobachtung, die ich gemacht habe.
Also zum Beispiel die Farbe der Kugel, die ich halt zu dem Zeitpunkt
aus dieser Zustandsurne gezogen habe.
Und jetzt neben diesem Generieren von Beobachtungssequenzen mithilfe
von HMMs gibt es insgesamt drei Fragestellungen, die ich mithilfe von
HMMs berechnen kann und für die ich effiziente Algorithmen habe, um
sie zu berechnen.
Und diese drei Dinger sind halt das Evaluierungsproblem, das
Dekodierungsproblem und das Trainingsproblem.
Das Evaluierungsproblem berechnet halt, angenommen ich habe ein HMM
Lambda, das vollständig parametrisiert ist, angenommen ich habe eine
Ausgabe, also eine Sequenz von Beobachtungen, die ich gemacht habe und
möchte jetzt die Wahrscheinlichkeit dafür berechnen, dass diese
Ausgabe wirklich von diesem HMM ausgegeben wurde.
Um das zu berechnen, hat man den Forward- oder auch alternativ den
Backward -Algorithmus.
Dann gibt es das Dekodierungsproblem und beim Dekodierungsproblem geht
es darum, dass ich für ein vollparametrisiertes HMM Lambda und eine
Ausgabe jetzt die Zustandsfolge finde, die mit der höchsten
Wahrscheinlichkeit durchlaufen würde, als wenn dieses HMM diese
Ausgabe macht.
Das ist sozusagen der Versuch, die mir versteckte Zustandssequenz
irgendwie sichtbar zu machen.
Streng genommen geht das nicht.
Also wenn ich eine Ausgabe sehe, kann sie von jeder beliebigen
Zustandssequenz mit unterschiedlichen Wahrscheinlichkeiten produziert
worden sein.
Aber da wir hier mit Wahrscheinlichkeiten arbeiten, solange nicht
irgendwo Nullwahrscheinlichkeiten drin vorkommen, kann prinzipiell
jetzt erstmal jede Zustandsfolge diese Ausgabe produziert haben.
Ich weiß nicht, in welcher es war, nur manchmal hätte ich gerne
irgendwie eine Zustandsfolge, um damit irgendwas zu berechnen.
Und dann sage ich halt, okay, ich entscheide mich halt für die
wahrscheinlichste Zustandsfolge und tue so, als wäre das die
Zustandsfolge gewesen, die jetzt zu diesen Emissionen geführt hat.
Und das dritte Problem ist dann das Trainingsproblem.
Und beim Trainingsproblem geht es halt darum, dass ich ja diese
Parameter des HMMs irgendwie schätzen möchte.
Ich baue mir ein HMM auf, ich lege fest, wie viele zuständig habe, ich
lege fest, was das Ausgabealphabet ist.
Aber was ich nicht weiß, ist halt, was sind die
Anfangswahrscheinlichkeiten, was sind die
Emissionswahrscheinlichkeiten und was sind die
Übergangswahrscheinlichkeiten.
Sondern meistens habe ich nur irgendwelche Trainingsdaten, von denen
ich annehme, dass dieses HMM diese Trainingsdaten hervorgebracht hat.
Und anhand dieser Trainingsdaten möchte ich jetzt die
Wahrscheinlichkeiten schätzen.
Und da gibt es für diskrete HMMs, wo ich also ein diskretes
Ausgabealphabet habe, zum Beispiel die Baumwelschregeln.
Und später, wenn ich ein kontinuierliches Alphabet habe, lernen wir
dann kennen, dass die Baumwelschregeln nichts anderes sind als ein
Sonderfall des Expectation-Maximization-Algorithmus.
Und das, was dieses Trainingsproblem macht, ist, dass es halt
Parameter findet für mein HMM Lambda.
Und dieses neu parametrisierte HMM nicht ein Lambda-Strich, so dass
dieser neue Satz Parameter die Trainingsdaten, die ich habe, mit einer
höheren Wahrscheinlichkeit hervorbringt, als der alte Satz an
Parametern.
Idealerweise größer, manchmal auch nur größer gleich.
Zu den Namen, also warum das Trainingsproblem Trainingsproblem heißt,
das erschließt sich einem noch gleich, relativ leicht.
Warum heißt das Evaluierungsproblem Evaluierungsproblem und das
Decodingproblem Decodingproblem?
Das Evaluierungsproblem kann ich nehmen, um damit zum Beispiel
Erkennung zu betreiben.
Wenn ich also drei Klassen habe, für jede Klasse habe ich ein HMM und
jetzt habe ich eine neue Beobachtungssequenz, die möchte ich jetzt
klassifizieren, dann kann ich halt mit einem Forward-Algorithmus
ausrechnen, wie hoch war die Wahrscheinlichkeit, dass es halt das
erste HMM war, wie hoch war die Wahrscheinlichkeit, dass es das zweite
HMM war, wie hoch war es die Wahrscheinlichkeit, das dritte HMM.
Und zwar immer unter der Annahme, dass ich halt in diesem HMM war,
also eine klassenbedingte Wahrscheinlichkeit.
Wenn ich das dann noch mit einer a priori Wahrscheinlichkeit der
Klassen multipliziere, dann kann ich damit relativ leicht so einen
naiven Base- Klassifikator realisieren, der mir dann gemäß a
posteriori Wahrscheinlichkeit das HMM und damit die zugehörige Klasse
raussucht, die ich jetzt klassifizieren möchte.
Das Decoding-Problem heißt Decoding-Problem zum einen, weil man halt
versucht, diese Folge von Zuständen, die man durchlaufen hat, zu
dekodieren, sichtbar zu machen.
Zum anderen muss man es auch im Hinterkopf behalten.
Wir werden später sehen, dass für kontinuierliche Spracherkennung der
erste Weg nicht gangbar ist, dass es nicht möglich ist, für jede
beliebige Wortfolge immer das jeweilige HMM auszurechnen und dann sich
für eine Aufnahme für das Wahrscheinlichste zu entscheiden, sondern
das wird zu rechenintensiv.
Und dann fällt man zurück auf einen kleinen Trick und dieser kleine
Trick ist, dass ich mich dann nicht mehr für die wahrscheinlichste
Wortfolge entscheide, sondern nur noch für die wahrscheinlichste
Zustandsfolge, dass ich die suche und dann sage, die Wortfolge, die
zur wahrscheinlichsten Zustandsfolge gehört, das ist halt die
Wortfolge, die ich erkenne.
Das ist dann nicht mehr die optimale Lösung, das ist dann eine
Approximation, aber wenigstens eine, die ich in erträglicher Zeit
durchrechnen kann.
Jetzt Forward-Algorithmus.
Wenn man sich überlegt, ich will also berechnen, die
Wahrscheinlichkeit, dass ein HMM diese Ausgabe O gemacht hat.
Normalerweise würde man das naiv so berechnen, dass ich alle möglichen
Zustandsfolgen der Reihe nach aufliste.
Für jede einzelne Zustandsfolge kann ich die Wahrscheinlichkeit für
die Ausgabe berechnen.
Ich kenne die Übergangswahrscheinlichkeiten, ich kenne die
Emissionswahrscheinlichkeiten, ich weiß, zu welcher Zeit war ich in
welchem Zustand und kann, wenn ich eine feste Folge habe, berechnen,
wie hoch ist die Wahrscheinlichkeit, dass diese Folge die Ausgabe
gemacht hat.
Dann berechne ich das halt für alle möglichen Zustandsfolgen und
summiere am Ende einmal über alle möglichen Zustandsfolgen auf.
Das wäre die naive Art und Weise.
Und jetzt kann man sich schon überlegen, es gibt halt sehr viele
mögliche kombinatorisch mögliche Zustandsfolgen.
Und wenn man dann hinguckt, stellt man halt fest, viele Zustandsfolgen
fangen halt gleich an.
Und das ist immer ein erster Blick darauf, dass kann man wohl
irgendwas mit Rekursion machen.
Und dann, wenn diese Rekursion derart gestaltet ist, dass es irgendwie
alle fängt immer mit demselben an und dann ändert es sich, dann ist
das wahrscheinlich etwas für dynamisches Programmieren.
Und das macht man eben gerade beim Forward-Algorithmus.
Beim Forward-Algorithmus definiert man sich solche Hilfsvariablen.
Die nennen wir die Alpha-Ts von J.
Und diese Alpha-Ts von J, die seien gerade die Wahrscheinlichkeit,
dass ich mich zum Zeitpunkt groß T im Zustand J befand und die Ausgabe
O1 bis groß O von T gemacht habe.
Das heißt also, dieses Alpha-T von J, das ist die Wahrscheinlichkeit,
dass ich die gesamte Ausgabe, die ich machen will, gemacht habe und
dass ich ganz zum Schluss im Zustand SJ gelandet bin.
Und jetzt gibt es insgesamt n solcher möglichen N-Zustände.
Und wenn ich also über alle möglichen N-Zustände diese Alpha-Groß-Ts
von J summiere, bekomme ich gerade die Wahrscheinlichkeit dafür, dass
ich dieses P von O gegebenen Lambda berechnen will.
Das ist gerade die gesuchte Wahrscheinlichkeit, dass dieses Lambda,
HMM Lambda, die Ausgabe gemacht hat.
Das ist natürlich die spannende Frage.
Gut, wie kann ich denn Alpha-Groß-T von J berechnen?
Gut, Alpha-T von Groß-T von J kann ich berechnen, indem ich es mit
Hilfe von Alpha-T-1 von J berechne.
Oder allgemein ein beliebiges Alpha-Klein-T von J, also für einen
beliebigen Zeitindex T, kann ich, also für den beliebigen Zeitindex T,
heißt Alpha-Klein-T von J, die Wahrscheinlichkeit, dass ich mich zum
Zeitpunkt Klein-T im Zustand J befinde und bisher die Ausgabe O von 1
bis O Klein-T gemacht habe.
Und das kann ich halt leicht zurückführen auf einen Alpha von T-1,
weil im Zeitpunkt Klein-T bin ich im Zustand J.
Ich habe die Ausgabe O1 bis O Klein-T gemacht.
Insbesondere habe ich also im Zustand J Klein-O von T die Ausgabe zum
Zeitpunkt Klein-T gemacht.
Das ist also gerade Bj von O von Klein-T.
Also die Ausgabewahrscheinlichkeit des Zustandes J.
Und dann die Beobachtung, die ich halt zum Zeitpunkt Klein-T gesehen
habe, gemacht.
Mal die Summe über alle vorhergehenden kürzeren, einen kürzeren
Sequenzen, also dass ich bis zum Zeitpunkt T-1 die Ausgabe O bis O
Klein -T-1 gemacht habe.
Und da mache ich dann OT.
Und dann am Ende diese Ausgabe von O1 bis OT-1 im Zustand I war.
Das ist dieses Alpha T-1.
Und jetzt kann ich da ja wieder in N unterschiedlichen Zuständen sein.
Und je nachdem, in welchem Zustand ich war, muss ich danach ja den
Übergang machen von diesem Zustand, in dem ich war, dem Zustand I, in
diesen Zustand J, von dem ich ausgehe, dass ich da im Zeitpunkt Klein
-T bin.
Das heißt, ich muss also diese Übergangswahrscheinlichkeit von I nach
J multiplizieren mit diesem Alpha T-1 von I und das über alle
möglichen I aufsummieren.
Oder bildlich ausgesprochen.
Also ich will dieses Alpha T von J ausrechnen.
Ich bin im Zeitpunkt SJ.
Ich mache diese Ausgabe O von T und muss dann noch zusätzlich gucken,
entweder war ich vorher in dem Zustand, in dem Zustand oder in dem
Zustand.
Gucke mir an, wie hoch war denn die Wahrscheinlichkeit, dass ich das,
was ich, das andere, was ich noch ausgeben muss, bis dahin ausgegeben
habe und dann im Zustand I war.
Und das mit der Wahrscheinlichkeit, dass ich den Übergang gemacht
habe, muss ich das Ganze noch multiplizieren und dann über alle
Vorgängermöglichkeiten aufsummieren.
Und die Rekursion hört halt auf beim Zeitpunkt A1 von J.
Das ist nämlich gerade die Wahrscheinlichkeit, dass ich zum Zeitpunkt
1 im Zustand J war und halt in diesem Zustand J, in dem ich mich zum
Zeitpunkt 1 befand, halt die Ausgabe O1 gemacht habe.
Das ist jetzt die Rekursionsformel.
Jetzt berechne ich das natürlich nicht rekursiv, sondern ich berechne
das wieder mit Hilfe dynamischem Programmierens.
Kleines Mini-Beispiel.
Angenommen, ich habe so ein HMM, das hätte drei Zustände.
Den Zustand nenne ich S, M und E.
Start, Mitte und Ende.
Und angenommen, ich habe drei mögliche Ausgaben A, B und C.
Die haben halt eine eigene Wahrscheinlichkeitsverteilung.
Im ersten Zustand wird A halt mit 0,5 ausgegeben, B mit 0,1 und C mit
0,4.
Dann muss ich da noch Übergänge machen.
Mit einer Wahrscheinlichkeit von 0,3 gehe ich in den nächsten Zustand
über.
Mit einer Wahrscheinlichkeit von 0,7 bleibe ich in meinem Zustand.
Und dieser Übergang bekommt dann entsprechend eine Wahrscheinlichkeit
von 0,0.
Und per Konvention Übergänge, die halt eine Wahrscheinlichkeit von 0,0
haben, die malen wir gar nicht erst ein.
Also Pfeile, die man nicht sieht, Übergangspfeile, die deuten halt an,
dass es da eine Wahrscheinlichkeit von 0,0 gibt.
Dann für den Zustand M habe ich auch wieder eine neue Verteilung.
Für den Zustand E habe ich eine eigene Verteilung.
Und dann halt entsprechende Übergänge.
Mit anderen Worten, wenn der eine Übergangswahrscheinlichkeit hat,
dass er in sich selber übergeht von 1,0, ist das sowas wie der
Endzustand.
Wenn man in dem einmal drin ist, kommt man aus dem nicht wieder raus.
Und jetzt kann ich einfach anfangen, da so einen Forward-Algorithmus
zum Beispiel zu berechnen.
Das macht man wieder mit dynamischem Programmieren sowie bei der
minimalen EDT-Distanz baut man sich halt so eine Matrix auf.
Unten schreibe ich hin die Ausgaben, die ich habe, zu den
unterschiedlichen Zeitpunkten.
So wie bei der Trellis.
Angenommen, ich hatte A, B, A als Ausgabe.
Jedes einzelne Symbol steht natürlich gleichzeitig auch für
irgendeinen Zeitschritt.
Also Zeitschritt 1, 2 und 3.
Hier habe ich meine Zustände.
Was ich jetzt noch brauche, ist eine Anfangszustandsverteilung.
Die sei 0
,5, 0,3 für Mitte und
0,2 für den letzten Zustand.
Und jetzt kann ich anfangen zu rechnen.
Ich brauche erstmal die Wahrscheinlichkeit für die Anfangszustände.
Also mit Wahrscheinlichkeit 0,5 bin ich in dem Zustand.
Mit Wahrscheinlichkeit 0,3 in diesem hier.
Mit Wahrscheinlichkeit 0,2 im Endzustand.
Und jetzt will ich die Wahrscheinlichkeit haben, dass ich hier A
ausgegeben habe.
Ich schiebe den Übergang
mit Wahrscheinlichkeit 0,7.
Und muss über alle möglichen Vorgängerzustände aufsummieren.
Da gibt es nur den einen.
Das heißt, wenn ich 0,5 mal 0,5 mal 0,7 ausrechne, komme ich zu etwas
wie 0,175.
Also ist klar, der Startzustand, der hat nur so eine Eigenschleife
oder kann in den nächsten übergehen.
Das heißt, ich kann von keinem der anderen Zustände in diesen
übergehen.
Das heißt, der kann weder von M noch von E herkommen.
Dieser Mittelzustand, wenn ich annehme, dass A wurde vom Mittelzustand
ausgegangen.
Dann kann ich entweder vom Startzustand her kommen.
Das hat eine Übergangswahrscheinlichkeit von 0,3.
Die Wahrscheinlichkeit, dass M ausgibt, ist auch 0,3.
Oder ich kann von hier her kommen.
Die Wahrscheinlichkeit, dass ich den Übergang mache, ist 0,3.
Und die Wahrscheinlichkeit, dass ich die Ausgabe mache, ist auch 0,3.
Und muss jetzt diese beiden, 0,3 mal 0,3 mal 0,3 und 0,5 mal 0,3 mal 0
,3, die beiden muss ich halt entsprechend aufsummieren, ist dann 0,027
plus 0,045 ist halt gleich 0,72.
Und dementsprechend hier oben kann ich auch von dem Zustand kommen.
Oder ich kann von dem Zustand kommen.
Der Übergang ist immer 1,0.
Mal die Wahrscheinlichkeit, dass ich A im Endzustand ausgebe, ist auch
0,3.
Und diese Übergangswahrscheinlichkeit ist 0,7.
Und die Wahrscheinlichkeit, dass ich das ausgebe im E, ist halt auch
mal 0,3.
Das heißt, die merken schon dieses 0,3.
Wenn man wollte, könnte man auch hier vorziehen.
Und dann habe ich halt hier entsprechend 0,06 plus 0,063 stehen.
Und das ist halt gleich 0,123.
Und so fülle ich das halt aus, meine Zahlen alle der Reihe nach aus,
wenn man das halt entsprechend nach dem Schema ausrechnet.
Und dann bis zur letzten Spalte, die ich dann immer auf Ausführer
rechnen kann, basierend auf der vorhergehenden Spalte.
Dann habe ich diese Matrix für das dynamische Programmieren
ausgefüllt.
Und dann fehlt als letzter Schritt noch diese Summenbildung.
Da muss ich also die Werte hier aus der letzten Spalte einmal
aufsummieren und bekomme dann mein endgültiges Ergebnis und weiß dann,
dass mit der Wahrscheinlichkeit von 0,035455 dieses HMM halt die
Ausgabe ABA erzeugt hat.
Was viele vergessen ist, dass man hier noch aufsummieren muss.
Viele sagen dann, ja, ich fülle die Tabelle aus.
Und dann, wie geht es weiter?
Ja, weiß ich nicht.
Ich nehme mir das Maximum.
Nein, da fehlt was.
Sondern alle sind wichtig.
Die müssen halt alle aufsummiert werden.
Was man sich halt klar machen muss, wenn man diese Matrix ausgerechnet
hat und dieses aufsummiert hat, dann hat man wirklich tatsächlich
ausgerechnet, was kommt denn raus, wenn ich jede einzelne
Zustandsfolge durchrechnen würde und dann aufsummieren würde.
Man hat dadurch wirklich implizit in relativ effizienter Zeit den Wert
jeder möglichen Zustandsfolge durchgerechnet und am Ende aufsummiert.
Man hat also keine Zustandsfolgen ausgelassen oder irgendwas, sondern
es wurde wirklich für jede Zustandsfolge implizit ausgerechnet, wie
wahrscheinlich war sie denn und das in die letzte Summe entsprechend
einfließen lassen.
Fragen dazu?
Wahrscheinlich noch bekannt aus Cox's so im Großen und Ganzen.
Das gleiche Spielchen gibt es auch in die umgekehrte Richtung.
Ist das Backward-Algorithmus auch noch aus Cox's bekannt?
Auch bekannt, okay.
Beim Backward-Algorithmus macht man halt das so, dass man sich eine
andere Hilfsvariable definiert.
Das ist dieses Beta-T von J.
Das sei eben die Wahrscheinlichkeit, dass ich jetzt und aufgepasst die
Ausgabe OT plus 1 bis O groß OT gemacht habe und am Ende im Zustand QT
gleich J bin für mein HMM.
Und das kann man halt so initialisieren.
Diese Beta-Groß-Ts für jeden beliebigen Zustand kann man halt sagen,
die sind 1, weil wenn ich schon alles ausgegeben habe, wenn ich also
nichts mehr ausgebe, dafür ist die Wahrscheinlichkeit dann halt immer
1, damit ich dann beim Rückwärtsrechnen das richtig rausbekomme.
Und dann habt ihr halt die Induktion, dass ich für ein beliebiges Beta
-T von I halt über alle Nachfolgerzustände J entsprechend summieren
muss.
Ich muss die Ausgabe BJ machen vom Zeitpunkt OT plus 1 nur, weil das
hier soll andeuten, dass ich nur die Ausgabe OT plus 1 gemacht habe,
dann den Übergang mache in den J und dann das Beta-T plus 1 von J
danach folgt.
Und zusammenfassend füge ich es dann halt, indem ich jetzt nicht über
die letzten, sondern über die ersten Betas summiere, über die Beta
-Null summiere.
Sowohl der Forward- als auch der Backward-Algorithmus laufen in sowas
wie ON-Quadrat mal T, also Produkt aus Quadrat der Zustände und Anzahl
der Zeitschritte.
Wenn man jetzt mal nur moderate Zahlen nimmt, also 5 Zustände, 100
Zeitschritte, dann braucht man da 3000 Berechnungen.
Wenn man es naiv machen würde und wirklich alle einzelnen möglichen
Zustandsfolgen ausrollen würde, hätte man sowas wie 10 hoch 72
Berechnungen benötigt.
Dann für das Decoding-Problem gibt es auch einen effizienten
Algorithmus.
Naiv würde man es halt wieder so machen, dass man für jede
Zustandsfolge ausrechnet.
Welche Wahrscheinlichkeit hat sie denn?
Und dann nehme ich das Maximum unter allen Zustandsfolgen.
Das ist genauso aufwendig, als würde ich halt jetzt auf naive Art und
Weise das Evaluierungsproblem lösen wollen.
Stattdessen macht man das Ganze auch wieder rekursiv und definiert
sich diese Deltas, Delta-Ts, so ähnlich wie man sich die Alpha-Ts
berechnet.
Das Alpha-T von I stand halt für die Wahrscheinlichkeit, zum Zeitpunkt
T im Zustand I zu sein und die Ausgabe O1 bis OT gemacht zu haben.
Das Delta-T ist die größte Wahrscheinlichkeit, oder ist die
Wahrscheinlichkeit der wahrscheinlichsten Zustandsfolge, die die
Ausgabe O1 bis OT macht und zum Zeitpunkt T im Zustand I ist.
Also unter allen möglichen Zustandsfolgen, die zum Zeitpunkt T im
Zustand I landen und die Ausgabe O1 bis OT gemacht haben, ist das
Delta -T entsprechend die Wahrscheinlichkeit der wahrscheinlichsten
solcher Zustandsfolgen.
Und dann rechne ich wieder genauso die Matrix aus, nur diesmal am Ende
summiere ich halt nicht auf, sondern ich suche halt hier unter allen
Delta -Wahrscheinlichkeiten mir das Maximum raus.
Und das sagt mir dann, das ist die Wahrscheinlichkeit der
Zustandsfolge, die am wahrscheinlichsten ist und zum Zeitpunkt T in
einem der Zustände gelandet ist und die gesamte Ausgabe gemacht hat.
Mit anderen Worten, die wahrscheinlichste Zustandsfolge, die diese
Ausgabe gemacht hat.
Wenn man jetzt noch mal sich anschaut, wie vergleicht sich das zum
Beispiel so ein Viterbi-Algorithmus gegen ein Dynamic Time Warping?
Beim Dynamic Time Warping haben wir halt auch so ähnlich wie eine
minimale Editierdistanz berechnet und was man jetzt auch noch machen
muss, ist beim... das muss man noch dazu sagen, das vergisst man auch
häufig zu erwähnen.
Diese Deltas, wenn ich die ausgerechnet habe, die Matrix, dann habe
ich hier hinten erstmal nur stehen, wie wahrscheinlich ist denn die
wahrscheinlichste Zustandsfolge, die es erzeugt hat.
Mich interessiert aber, welches ist die wahrscheinlichste
Zustandsfolge, nicht wie wahrscheinlich ist sie.
Und deshalb muss ich mir jetzt jedes Mal, wenn ich dieses Maximum
durchführe, wenn ich so einen neuen Zelleneintrag ausfülle, muss ich
mir abspeichern, welcher der Vorgänger...
von welchem der Vorgängerzustände bin ich denn gekommen?
Welcher der Vorgängerzustände hat denn dazu geführt, dass ich jetzt
hier den maximalen Wert habe?
Muss mir das in jeder Zeile speichern, von wo bin ich gekommen, von
welches war der maximale vorhergehende Zustand und muss dann von hier
hinten diese Rückzeiger rückverfolgen, um damit rückwärts die
Zustandssequenz, die ich eigentlich suche, aufzubauen.
Also DTW und Viterbi berechnen beide mit dynamischem Programmieren,
speichern sich beide diese Rückzeiger aus.
Nur beim Viterbi multipliziert man halt Wahrscheinlichkeiten, während
man beim DTW Distanzen zwischen Vektoren berechnet und diese
aufsummiert.
Und beim Viterbi habe ich halt solche
Zustandsübergangswahrscheinlichkeiten und die
Emissionswahrscheinlichkeiten, während ich beim DTW nur Distanzen
zwischen Mustern habe, mit denen ich arbeiten kann.
Und der Forward- und der Viterbi-Algorithmus unterscheiden sich halt
darin, dass der eine da eine Maximumsoperation macht in der Zelle,
während der andere eine Summe macht.
Und der Forward-Algorithmus berechnet wirklich die
Wahrscheinlichkeiten implizit für alle möglichen Zustandsfolgen.
Deswegen macht man die Summe.
Und hier versucht man unterschiedliche, versucht man, sich immer nur
auf eine Zustandsfolge zu beschränken und unter den Zustandsfolgen
dann immer die wahrscheinlichste rauszusuchen.
Das dritte Problem ist dann das Lernproblem.
Da ist die Frage, wie optimiere ich jetzt mein Modell?
Und da ist es so, es gibt kein Verfahren, das mir gleichzeitig sagt,
was ist die optimale Topologie, also wie viele Zustände brauche ich
und welche Zustandsübergänge kann ich zum Beispiel auf null setzen und
mir noch die Parameter der Anfangswahrscheinlichkeiten, der
Übergangswahrscheinlichkeiten und der Emissionswahrscheinlichkeiten
schätzt.
Das gibt es nicht.
Deswegen, der Mensch muss als Designer immer zumindest die Anzahl der
Zustände in meinem HMM per Hand festlegen, muss sich per Hand
definieren und dann kann ich versuchen, die restlichen Parameter,
Übergangswahrscheinlichkeiten, Emissionswahrscheinlichkeiten,
Anfangswahrscheinlichkeiten mit Hilfe von Trainingsdaten zu schätzen.
Und diese Trainingsdaten sind in der Form gelabelt, dass ich weiß,
diese Daten wurden von diesem HMM erzeugt, aber ich weiß nicht für
welchen, für jeden Zeitpunkt, in welchem Zustand war ich dann.
Um jetzt sozusagen neue Parameter zu finden, die diese Trainingsdaten
dann mit höherer Wahrscheinlichkeit hervorbringen als irgendwelche
alten Parameter, definiert man sich auch wieder ein paar Hilfsgrößen.
Zum einen ist interessant diese Gamma-Wahrscheinlichkeiten.
Gamma t von j sagt halt aus, wie hoch ist die Wahrscheinlichkeit, dass
ich mich zu einem bestimmten Zeitpunkt im Zustand j befinde, wenn die
Ausgabe und das HMM Lambda gegeben sind.
Eine andere interessante Hilfswahrscheinlichkeit ist diese Xi
-Wahrscheinlichkeit.
Die sagt mir aus, wie hoch ist die Wahrscheinlichkeit, dass ich beim
Übergang vom Zeitpunkt t zum Zeitpunkt t von t plus 1 vom Zustand i
zum Zustand j übergegangen bin.
Immer gegeben die Parameter meines HMMs Lambda und gegeben, dass diese
Ausgabe über die gesamte Zeit hinweg gemacht wurde.
Und wenn man sich das anschaut, dann kann man jetzt also hier so ein
paar Sachen zusammenrechnen.
Also nehmen wir uns hier die Situation an, zum Zeitpunkt t bin ich im
Zustand i, zum Zeitpunkt t plus 1 bin ich im Zustand j und die Ausgabe
soll gemacht werden.
Naja, die Wahrscheinlichkeit, dass ich zum Zeitpunkt t im Zustand i
bin, das ist gerade Gamma t von j.
Und die Wahrscheinlichkeit, dass ich im Zustand t plus 1 von j bin,
ist gerade Gamma t plus 1 von j.
Oder zurückführt auf die Alpha- und Beta-Wahrscheinlichkeiten heißt
das nichts anderes, als dass ich erst mal bis zum Zeitpunkt t die
Ausgabe u1 bis ut gemacht habe, t gemacht habe, mich im Zustand i
befinde.
Dann muss ich den Übergang machen in den Zustand j und dann noch die
Ausgabe machen für den Zeitpunkt t plus 1.
Und dann muss ich ja noch die gesamte restliche Ausgabe machen.
Ich gehe mal davon aus, dass die komplette Ausgabe gegeben ist.
Das heißt, ich muss jetzt auch noch die Ausgabe machen von ot plus 2
bis groß ot.
Und zwar ausgehend vom Zustand j.
Da ist ein Fehler, das muss j heißen.
Warum ist das da?
Ach, gibt's doch nicht.
Generationen von Studenten gehen da durch und keiner meckert.
Also das muss Beta t plus 1 von j eigentlich sein.
Und wenn ich also diese drei Wahrscheinlichkeiten aufmultipliziere,
dann bekomme ich gerade die Wahrscheinlichkeit dafür, dass ich im
Zeitpunkt t von i nach j im Zeitpunkt t plus 1 übergegangen bin.
Oder halt anders hingeschrieben, das ist dieses Alpha t von i mal aij
by von ot plus 1 mal Beta t plus 1 von j.
Aber unter der Annahme, dass diese Ausgabe o schon gegeben ist.
Ich habe das ja konditioniert über, dass o schon gegeben ist bei dem
xi t von ij.
Und deswegen muss ich das Ganze auch noch normalisieren über die
Wahrscheinlichkeit, dass dieses HamM Lambda überhaupt erst die Ausgabe
o im Allgemeinen gemacht hat.
Und wenn ich wissen will, wie groß ist die Wahrscheinlichkeit, dass
diese Ausgabe o überhaupt gemacht wurde, dann kann ich das entweder
mithilfe der Alpha-Wahrscheinlichkeiten machen oder ich kann das auch
zerlegen, indem ich sage, das ist die Wahrscheinlichkeit, dass ich zu
diesem Zeitpunkt von t nach t plus 1 einen beliebigen Übergang von i
nach j gemacht habe.
Und das kann ich dann halt normalisieren, indem ich sozusagen alle
möglichen Zustandsübergänge, die vom Zeitpunkt t zum Zeitpunkt t plus
1 gemacht wurden, möglich sind.
Und kann das dann auch hier mit den Alphas, den Betas und dieser
Übergangswahrscheinlichkeit entsprechend ausdrücken.
Mit diesen Xis kann man jetzt entsprechend die Gammas berechnen.
Bin mich also interessiert, wie hoch ist die Wahrscheinlichkeit, dass
ich zum Zeitpunkt t im Zustand i ware?
Dann heißt das ja nichts anderes als, ich habe aus dem Zustand i einen
Übergang herausgemacht vom Zeitpunkt t zum Zeitpunkt t plus 1.
Das heißt, das ist also die Summe über alle Wahrscheinlichkeiten, dass
ich halt zum Zustand i, dass ich zum Zeitpunkt t vom Zustand i nach
irgendeinem anderen Zustand einen Übergang gemacht habe, muss also
über alle möglichen Folgezustände aufsummieren und dann halt
entsprechend diese Xi-Wahrscheinlichkeiten aufsummieren.
Und wenn ich jetzt zum Beispiel noch diese Gammas, so ein Gamma klein
t von i, über das t aufsummiere, dann bekomme ich auch noch eine
Schätzung dafür, wie häufig ich überhaupt während der Generierung der
Ausgabe im Zustand i überhaupt war, unabhängig jetzt von dem
Zeitpunkt, wann das passiert ist.
Und wenn ich über die Xi's aufsummiere, dann über die Zeit hinweg,
wenn ich die Xi t's über die Zeit hinweg aufsummiere, dann gibt mir
das einen Erwartungswert dafür an, wie viele Übergänge ich von i nach
j allgemein machen werde, unabhängig davon, zu welchem Zeitpunkt das
jetzt geschehen wird.
Das heißt also, die erwarteten Anzahl der Übergänge von sj raus ist
halt die Summe von t bis t-1 über die Gamma t's und die erwarteten
Anzahl an Übergängen von si nach sj ist gerade die Xi t's von i nach j
aufsummiert über die Zeit.
Und daraus kann ich mir jetzt Regeln zusammenbauen, die mir neue
Parameter schätzen.
Am einfachsten ist das für die Anfangswahrscheinlichkeit.
Für die Anfangswahrscheinlichkeit, wenn ich also wissen möchte, was
ist eine Schätzung dafür, dass ich zum Zeitpunkt 1 im Zustand i bin,
dann ist das gerade Gamma 1 von i.
Also wie häufig, was ist zu erwarten, die Wahrscheinlichkeit, dass ich
zum Zeitpunkt 1 im Zustand i bin.
Wenn ich wissen will, eine neue Schätzung für meine
Übergangswahrscheinlichkeit von i, dass ich vom Zustand i in den
Zustand j übergehe, dann ist das eben gerade die Anzahl an zu
erwartenden Übergängen, die von i nach j passieren, geteilt durch die
Anzahl, wie häufig bin ich überhaupt in i.
Das heißt also, das ist, wie häufig mache ich den Übergang von i nach
j, ins Verhältnis gesetzt zu, wie häufig bin ich überhaupt in i.
Und das ist entsprechend dann eine Schätzung dafür, wie häufig mache
ich denn den Übergang von i nach j, wenn ich denn dann mal im Zustand
i bin.
Und das Gleiche kann man machen für die Ausgabewahrscheinlichkeiten,
also neue Schätzung dafür, das Karte-Symbol im Zustand j auszugeben.
Brauche ich erstmal als Normierungsfaktor, wie häufig bin ich
überhaupt im Zustand j, also diese Summe über die Zeit, über die Gamma
-Ts, und muss jetzt hinschreiben, wie häufig bin ich denn
erwartungsgemäß im Zustand j und mache dabei noch die Ausgabe des
Symbols k.
Und das ist so eine Schreibweise, die es da gibt.
Das kommt aus dem Angelsächsischen raus.
Dieses s.t.
ist halt subject to.
Das heißt, ich summiere alle Gamma-Ts von j auf über die Zeit hinweg,
aber nehme nur die Gamma-Ts von j, wenn halt das o von t gerade dem
Symbol k entsprach, wenn ich zu diesem Zeitpunkt kleinen t eben gerade
das Symbol k ausgegeben habe.
Das heißt, ich filter aus allen möglichen Gamma-Ts von j diejenigen
raus, bei denen ich überhaupt das Symbol k zu dieser Zeitpunkt t
ausgegeben habe.
Und auf diese Art und Weise habe ich jetzt so eine Art intuitive
Schätzung neuer Parameter für mein HMM.
Was ist jetzt das Problem?
Das erste Problem ist, ich brauche überhaupt erstmal initiale
Parameter.
Um diese Xis und Gammas und Alphas und Bettas überhaupt ausrechnen zu
können, brauche ich ja schon ein parametrisiertes HMM.
Das heißt, ich muss mir schon mal irgendwie ein paar HMM
initialisieren.
Zufällig initialisiert oder sonst wie anderweitig initialisiert und
kann dann halt diese Dinger ausrechnen und damit halt entsprechend
eine neue Schätzung durchführen.
Dann, was auch interessant ist, sind ja diese Sachen, dass ich über
die Zeit hinweg summiere.
Und das geht eben gerade deshalb, weil ich halt ein HMM habe als ein
homogenes HMM.
Auch als eine zu drunter liegende, also zum Beispiel
Zustandsübergangswahrscheinlichkeiten, sind eine homogene Markovkette.
Das heißt, diese Wahrscheinlichkeiten, diese Übergänge zu machen, die
sind gar nicht mehr von der Zeit überhaupt abhängig.
Und mit diesen Baum-Weltsch-Regeln und dieser intuitiven Erklärung der
Baum -Weltsch-Regeln war man lange Zeit sehr glücklich und hat dann
irgendwann festgestellt, dass die das Ganze doch nur ein Sonderfall
sind eines anderen Algorithmuses, des Expectation Maximization
Algorithmus.
Und diesen EM-Algorithmus braucht man dann jetzt zum Beispiel für mehr
diskreten HMMs, kontinuierliche HMMs haben, wenn wir einen
kontinuierlichen Ausgaberaum haben.
Nicht mehr so ein diskreter Ausgabealphabet, sondern einen
kontinuierlichen Ausgaberaum, zum Beispiel einen dimensionalen Vektor
der reellen Zahlen.
Und das Ganze kann man jetzt sehr schön nachlesen in so einem
Übersichtspaper.
Das heißt sinnigerweise auch a gentle tutorial of the EM-Algorithms
und then in its applications to parameter estimation and for Gaussian
Mixture and hidden Markov Models.
Der Name verrät uns schon, das kann ich also nicht nur für HMMs
verwenden, das kann ich auch für Gauss Mixturen verwenden.
Da komme ich wohl in so ein ähnliches Problem vielleicht rein.
Und damit man versteht, was der EM-Algorithmus macht, muss man sich
vorher noch mal klar werden, was machen wir überhaupt, wenn wir zum
Beispiel Wahrscheinlichkeiten schätzen.
Angenommen, wir haben einen Würfel, der ist irgendwie gezinkt.
Da sind nicht die Zahlen alle gleich verteilt.
Ich möchte jetzt wissen, welche Zahl ist wie verteilt.
Das Ganze mache ich experimentell, indem ich halt ganz häufig den
Würfel würfel.
Dann zähle ich auf, was vorkommt und dann sage ich halt, okay, die 1,
wie häufig habe ich die 1 gesehen?
Geteilt durch die Anzahl der Würfel ist die Wahrscheinlichkeit dafür,
die 1 zu sehen.
Für die 2, wie häufig habe ich die 2 gesehen?
Geteilt durch die Anzahl der Würfel ist die Wahrscheinlichkeit, meine
Schätzung für die Wahrscheinlichkeit, dass ich die 2 gesehen habe.
Das machen wir intuitiv.
Dem liegt aber eine Methode unter und das ist die sogenannte Maximum
-Likelihood -Methode.
Und dieser EM-Algorithmus, von dem der Baum-Welch-Regel ein Sonderfall
ist, ist halt eine schöne mathematische Grundlage und man kann damit
viele andere Sachen auch rechnen, wenn man da Wahrscheinlichkeiten
schätzen muss.
Und bevor wir das machen können, den EM-Algorithmus, müssen wir uns
nochmal die Maximum-Likelihood-Methode anschauen und dann sehen wir
auch, wo wir dann in Schwierigkeiten kommen und wo wir den EM
-Algorithmus brauchen.
Wenn wir also Parameter eines Wahrscheinlichkeits, einer
Wahrscheinlichkeitsvariable schätzen, diskrete
Wahrscheinlichkeitsvariable, und wir wollen schätzen, wie ist die
verteilt, dann macht man das ja mit, gucken wir an, die Anzahl der
Ereignisse, teile das durch die, für jedes einzelne Ereignis teile ich
das durch die Anzahl der Beobachtungen, die ich überhaupt gemacht habe
und habe eine Schätzung.
Das macht man so aus dem Bauchgefühl heraus.
Da gibt es aber auch eine mathematische Grundlage für.
Genauso ist das, wenn wir jetzt eine Wahrscheinlichkeitsdichte
-Funktion haben, dann funktioniert das halt nicht mehr so einfach,
weil ich jetzt irgendwie eine Wahrscheinlichkeitsdichte-Funktion habe,
die hat bestimmte Parameter.
Gauss-Glocke hat einen bestimmten Satz Parameter wie Mittelwert und
Varianz, Student-Verteilung, Chi-Quadrat-Verteilung, die haben alle
bestimmte Parameter und die muss ich jetzt schätzen für die
Wahrscheinlichkeitsdichte.
Und ich habe halt eine Menge an Trainingsdaten, nennen wir sie x, x1
bis x N, sind die Trainingsdaten, von denen wir annehmen, dass sie von
dieser Wahrscheinlichkeitsdichte-Funktion produziert wurden.
Und jetzt will ich diese Parameter schätzen.
Und dafür definiere ich mir die sogenannte Likelihood-Funktion.
Diese Likelihood-Funktion ist abhängig von den Parametern meiner
Wahrscheinlichkeitsdichte -Funktion und die sagt mir, meine
Wahrscheinlichkeitsdichte -Funktion, mit welcher Wahrscheinlichkeit
wurden denn die gesamten Trainingsdaten x1 bis x N hervorgebracht von
dieser Wahrscheinlichkeitsdichte-Funktion, wenn sie diesen Satz
Parameter Theta hat.
Und das Maximum-Likelihood-Kriterium sagt mir dann nichts anderes, als
ich entscheide mich für den Satz von Parametern von meiner
Wahrscheinlichkeitsdichte -Funktion, der halt dafür sorgt, dass diese
Likelihood -Funktion maximal wird, der also dafür sorgt, dass die
Trainingsdaten mit höchster Wahrscheinlichkeit hervorgebracht wurden.
Das ist nicht die einzige Art und Weise, wie man Parameter einer
Wahrscheinlichkeitsverteilung und einer Wahrscheinlichkeitsdichte
-Funktion schätzen kann.
Es gibt noch beliebig viele andere mögliche Verfahren.
Das ist nur, sagen wir mal, das populärste Verfahren.
Aber da gibt es zwar eine gewisse Intuition, warum man das so machen
sollte, aber es gibt jetzt keinen zwingenden Beweis, warum das die
einzig reine und wahre richtige Möglichkeit ist, um diese Parameter zu
schätzen.
Ich muss jetzt also irgendwie diese Funktion L maximieren über diesen
Satz Parameter Theta und diese Satz Parameter Theta sind in der Regel
kontinuierliche Parameter.
Wenn ich so eine Wahrscheinlichkeitsdichte-Funktion habe mit
Mittelwert und Varianz, dann ist das ein Tupel von kontinuierlichen
Parametern.
Das heißt, ich habe dann eine Funktion, die hängt von zwei
kontinuierlichen Variablen ab und die muss jetzt halt entsprechend
maximiert werden.
So mit den üblichen Methoden, die wir aus der Funktionen- nicht die
Likelihood -Funktion selber zu maximieren, sondern den Logarithmus der
Likelihood -Funktion.
Warum?
Was ich hier ja mache ist, ich multipliziere hier was für jedes
Trainingsdatum auf.
Für jedes Trainingsdatum, Trainingsbeispiel, das ich habe, wird hier
die Wahrscheinlichkeit aufmultipliziert.
Und wenn ich da jetzt den Logarithmus drauf rechne, dann wird halt aus
diesem Produkt eine Summe.
Und eine Summe abzuleiten ist halt deutlich einfacher als so ein
Produkt von 100.000 Faktoren abzuleiten.
Dann zerlegt mir die Summenregel diese Ableitung sehr schön und ich
muss nur noch... und es wird deutlich einfacher abzuleiten und Null zu
setzen.
Das kann man jetzt mal für zwei Beispiele mal durchexerzieren, was
dabei herauskommt.
Das erste Beispiel ist was Diskretes.
Da gehen wir davon aus, dass wir eine diskrete
Wahrscheinlichkeitsverteilung haben und wir wollen jetzt halt
schätzen, wie sind die unterschiedlichen Ergebnisse als Ereignisse
gesehen, wie sind die verteilt.
Also angenommen, ich weiß, ich habe wieder so eine Urne und in der
Urne sind eine bestimmte Anzahl an roten Kugeln und eine bestimmte
Anzahl an blauen Kugeln.
Ich habe also eine Urne,
da sind irgendwie blaue und rote Kugeln wild drin gemischt.
Ich weiß halt, es gibt irgendwie m rote Kugeln.
Das ist irgendwie die Anzahl der Kugeln, die rot sind, die sei halt m.
Ich weiß, ich kann das zum Beispiel so kodieren, rot soll halt 1 sein,
blau ist halt 0.
Und ich würde jetzt gerne die Wahrscheinlichkeit schätzen für die
Anzahl der roten Kugeln.
Ich kann gerade meine Notizen nicht lesen.
Wenn ich wüsste, wie viele Kugeln insgesamt drin wären, also seien n
Kugeln, dann würde ich normalerweise rechnen, dass p von rot halt m
durch n wäre.
Jetzt weiß ich aber nicht, wie viele rote Kugeln da drin sind in der
Urne.
Ich weiß halt nicht, wie viele Bälle insgesamt in der Urne drin sind.
Das Einzige, was ich weiß, ist, ich habe viermal aus dieser Urne
gezogen und wieder zurückgelegt und habe halt Trainingsbeispiele
bekommen, die sahen halt so aus.
Ich
habe also viermal gezogen und habe halt gezogen, rot, rot, blau, rot.
Jetzt kann ich mir die Likelihood-Funktion aufstellen von diesem
diskreten ziehen.
Und da greife ich dann halt zurück entsprechend auf die Methoden von
der Kombinatorik.
Und die sagen mir halt die Wahrscheinlichkeit, die Likelihood-Funktion
von diesem p mit dem Parameter, den ich habe, m.
Das ist eben gerade 4 über 3 mal p hoch 3 mal 1 minus p.
Ich habe halt dreimal rot gezogen, ich habe einmal schwarz gezogen und
dann habe ich da insgesamt 4 über 3 verschiedene Möglichkeiten und
kann halt sagen, das Ganze umgeformt ist dann entsprechend noch 4 über
3 mal p hoch 3 minus p hoch 4.
Angenommen, wir wüssten jetzt, es gibt insgesamt 8 Kugeln in dieser
Urne, dann kann ich für p nur eine bestimmte Anzahl an Werten haben.
p kann halt nur in diskreten Schritten sein.
Das kann 0 über 8, 1 durch 8, 2 durch 8, 3 Achtel, 4 Achtel, 5 Achtel,
6 Achtel oder 7 Achtel sein.
Und für jeden dieser 8 Werte kann ich jetzt halt die Likelihood
-Funktion ausrechnen und bekomme dann halt sowas raus wie 0,002, 0
,092, 0,033, 0,063, 0,012, 0,105, 0,082, 0,0002.
und irgendwo bin ich verrutscht, glaube ich.
0, 0, 0, 2, 0, 2, 0, 0, 3, 0, 0, 6, 3, 0, 0, 1, 2, 0, 1, 0, 5, 0, 0,
8, 4 und dann gibt es natürlich noch 8 von 8.
Da hat man auch entsprechend die Wahrscheinlichkeit, die Likelihood
-Funktion 0.
Das heißt also die Kette, die hervorgebracht wurde, bei der
Verteilung, ist halt entsprechend auch 0.
Jetzt gucke ich, wo finde ich hier unter allen Werten, die ich habe,
mein Maximum.
Und ich sehe, mein Maximum ist hier bei 6 Achtel.
Da ist die höchste Wahrscheinlichkeit.
Das heißt, ich schätze also mein M, die Anzahl an Bällen in der Urne,
schätze ich halt auf 6.
Und die Wahrscheinlichkeit von P von 1 ist dann dementsprechend 6
Achtel gleich 0,75.
Das Erste, was man daran sieht, ist, ganzzahlige Optimierungsprobleme
sind blöd.
Hier normalerweise würde man ja sagen, wenn es kontinuierlich wäre,
würde ich die Likelihood-Funktion ableiten, 0 setzen und dann
entsprechend mein Ergebnis rausbekommen.
Würde ich das hier an der Stelle machen, dann käme halt raus, sowas
wie L' ist 3p² minus 4p hoch 3.
Das ist eben p² mal 3 minus 4p.
Das Ganze soll 0 gesetzt werden und dann käme raus p gleich 3 Viertel.
An dieser Stelle habe ich Glück.
Das passt.
3 Viertel ist gleich 6 Achtel.
Das ist aber Zufall, weil das so gewählt wurde.
Weil es kann durchaus sein, dass hier hinterher was rauskommt.
Das ist irgendeine Zahl, die ist nicht durch 8 teilbar.
Das ist also kein rationaler Bruch über 8, wo oben auf dem dann eine
ganze Zahl stehen würde.
Wenn das der Fall wäre, dann müsste ich dann sagen, dass hier, also
welche Zahl geteilt durch 8 ergibt den Wert, dann würde ich da oben
plötzlich rauskommen mit irgendwie einer nicht ganzen Anzahl an
Kugeln.
Je nachdem, wie das Beispiel gewählt ist, könnte beim Ableiten
rauskommen, das sind dann 2,25 Kugeln.
Das geht natürlich nicht, weil ich kann keine halben Kugeln haben in
der Urne.
Bei so einem einfachen Beispiel könnte man dann noch anmerken, na ja,
dann muss ich nur noch die Umgebung des lokalen Optimums absuchen und
gucken, für die ganz zahligen Ergebnisse, die am nächsten dran liegen,
was ist denn das Beste.
Das ist auch nur bei so einem gutmütigen Beispiel der Fall, wo sagen
wir mal, man nur ein Optimum hat und das Ganze kontinuierlich anwächst
und wieder abfällt zu dem Optimum.
Aber wenn ich dann zum Beispiel so zwei, drei lokale Optima habe, die
dann noch zwischen ganz zahligen Werten liegen, dann kann es halt
ekelhaft werden.
Insofern, dadurch, dass es halt ganz zahlige Optimierung ist, ist das
sicherste, immer alle Sachen auszuprobieren.
Das Ganze kann man jetzt auch für den kontinuierlichen Fall weiter
treiben.
Angenommen, wir machen das für eine einfache Gaussglocke,
eindimensionale Gaussverteilung.
Also angenommen, wir haben so was, so eine wahrscheinlichkeitsdichte
Funktion, die sagt hat, px von i hat halt die Parameter Mittelwert und
Varianz, ist halt einfache Gaussglocke.
Wenn ich da jetzt wieder Trainingsdaten habe, n Stück und meine
Likelihood -Funktion aufstelle von den Parametern,
gegeben meine Trainingsdaten, ist das halt dementsprechend das Produkt
über alle diese xi.
Dieser Faktor wird n mal aufmultipliziert und dann kann ich dieses
Produkt oben in den Exponenten reinziehen,
kann also meine Likelihood-Funktion in der Art und Weise darstellen.
Das nächste, was ich mache, ist halt,
also ich will das jetzt jeweils nach den beiden Parametern µ und Sigma
ableiten.
Als erstes interessiere ich mich dafür, wie das bei µ aussieht und
damit das dann schön wird, kann ich das Ganze auch noch mal
umschreiben.
Also mein Faktor vorne bleibt erhalten,
einfach nur die Wurzel einmal anders geschrieben.
Und dann schreibe ich mir den Exponenten noch ein bisschen um.
Den Nenner lasse ich gleich und den Zähler ziehe ich auseinander.
Sagt, das ist einmal die Summe i gleich 1 bis n, xi minus x² zum
Quadrat plus n mal x² minus y zum Quadrat.
Und das x² definiere ich mir halt gerade so,
dass das die Summe i gleich 1 bis n, xi ist.
Wenn ich jetzt das x² entsprechend nach der Definition einsetze und
das Ganze wieder ausmultipliziere, komme ich wieder bei dieser
ursprünglichen Summe da oben raus.
Ich habe also einfach mal nur ein bisschen umgeschrieben.
Jetzt bilde ich davon den Logarithmus und leite dann entsprechend nach
dem Mittelwert ab, um zu schauen, ob ich eine schöne geschlossene
Formel für die Schätzung des Mittelwerts bekomme.
Wenn ich jetzt also ableite nach dem Logarithmus von dem Ganzen,
dann kann ich als erstes
den Logarithmus in das Produkt reinziehen und aus diesem Produkt, aus
dem ersten Faktor und dem zweiten Faktor eine Summe machen.
Das ist also dann die Ableitung nach µ.
Jetzt den Logarithmus von 1 durch 2pi Sigma² hoch ein halber Minus.
Ich ziehe also das Minuszeichen, das hier oben vom Exponenten steht,
entsprechend gleich runter und nehme den Logarithmus von der E
-Funktion.
Und wenn ich jetzt halt für den Logarithmus den Logarithmus Naturalis
nehme, fällt einfach das E weg.
Das heißt, es bleibt stehen, dieser ursprüngliche Quotient.
Wenn ich jetzt die Ableitung bilde, die Ableitung von dem hier nach µ
ist 0.
Da kommt gar kein µ mehr vor.
Das heißt also, das Ganze ist 0.
Wenn ich das Ding da hinten ableite, bleibt entsprechend stehen 2
Sigma².
Und jetzt muss man schauen, also das µ kommt nur noch hier hinten in
dem letzten Faktor vor.
Hier vorne in dem Summanden kommt es gar nicht mehr vor.
Das heißt, ich muss mich nur noch um das Hintere kümmern.
Einmal mit Kettenregel abgeleitet ist das dann entsprechend minus 2n
x² minus µ.
Das ist also die Ableitung nach µ und die setzen wir jetzt
entsprechend zu 0.
Und dann einfach nach dem µ aufgelöst, ergibt das halt, dass µ gleich
gerade dem x² sein muss.
Ist also gerade dem 1 durch n Summe i gleich 1 bis n x i.
Das ist die intuitive Schätzung, die Sie sowieso machen würden.
Wenn Sie einen Mittelwert schätzen würden, würden Sie auch einfach den
Mittelwert über alle Trainingsbeispiele, die Sie gesehen haben,
nehmen.
Das heißt, die Schätzung des Mittelwertes und auch die Bezeichnung von
Mittelwert kommt eben gerade daher, dass es halt der Mittelwert über
alle Daten ist und dass die Wahrscheinlichkeit, dass diese Gaussglocke
halt die Daten, die Trainingsdaten hervorbringt, genau dann maximal
wird, wenn ich halt für dieses µ gerade den Mittelwert über alle Daten
einsetze.
Das gleiche Spielchen kann man jetzt machen mit dem Sigma.
Damit ich das mit dem Sigma machen kann, fange ich wieder da an.
Das heißt, ich mache diesen Zwischenschritt, wo ich diese Summe
auseinandergezogen habe, wieder rückgängig und fange ab, halte
entsprechend die Ableitung nach dem Sigma zu machen, halt vom
Logarithmus wieder dieses 1 durch 2 Pi Sigma Quadrat hoch n halbe mal
e das
Ganze.
Logarithmus zieht man halt entsprechend wieder rein, also
dementsprechend die Ableitung nach Sigma von... und jetzt kann ich,
wenn ich den Logarithmus reinziehe, den Exponenten gleich
vorausziehen.
Das ist also n halbe mal Logarithmus von 1 durch 2 Pi Sigma Quadrat
und dann hinten entsprechend fällt die E-Funktion wieder weg.
Das Minus kann ich gleich entsprechend aus dem Exponenten
runterziehen, ist also dementsprechend hier
dieses da.
Jetzt haben wir hier wieder zwei Summanden, die kann ich dann
unabhängig voneinander ableiten, damit ich zum Ergebnis komme.
Und jetzt brauchen wir halt ein bisschen Wissen für den ersten
Summanden, für dieses Logarithmus von 1 durch 2 Pi Sigma Quadrat, wie
da bitte schön die Ableitung nach Sigma aussehen soll.
Da brauche ich ein bisschen Zwischenwissen.
Und zwar muss ich dafür wissen, wenn ich so eine Funktion f habe, f
von x, die sei immer echt größer 0.
Also die kann nicht negativ werden und die sei auch immer sogar, sagen
wir mal, größer gleich 0.
Wenn ich von so einer Funktion den Logarithmus nehme und dass das
entsprechend ableite, dann ist das eben gerade gleich f Strich von x
durch f von x.
Das haben Sie irgendwann mal in der Analysesvorlesung gesehen und wenn
Sie es nicht mehr wissen, schauen Sie nach im Taschenbuch der
Mathematik.
Ausgerechnet heute habe ich es nicht dabei.
Da steht es dann entsprechend drin.
Das heißt also, wenn ich hier mir meine Funktion f anschaue, da habe
ich eine Funktion f, die heißt 1 durch 2 Pi Sigma Quadrat.
Das heißt, die ist sogar echt größer als 0 die ganze Zeit, weil hier
habe ich ein Quadrat drinnen stehen.
Das kann also nie negativ werden und 0 kann es auch nicht werden, weil
der oben auf dem Bruch steht, das ist der... genau, im Zähler, im
Numerator, im Zähler steht halt eine 1 konstant, der
Divisor, auf deutsch Zähler und der Nenner ist immer positiv.
Das heißt, das ganze Ding ist dann entsprechend immer größer als 0.
Das heißt, wir können diese Regel anwenden.
Das heißt, wir können jetzt also für unser f von x entsprechend 2 Pi
Sigma Quadrat hoch minus 1 einsetzen.
Das Ganze wollen wir ableiten und ergibt sich dann entsprechend nach
der Regel zu 1 durch 2 Pi minus 2 durch 1 Sigma hoch 3 und noch ein
bisschen Kettenregel
angerechnet.
Also gleich minus 1 durch Pi mal 1 durch Sigma hoch 3.
Jetzt will ich aber nicht 2 Pi Sigma Quadrat minus 1 ableiten, sondern
ich will den Logarithmus von der ganzen ableiten.
Das heißt, wenn ich jetzt f Strich durch f von x mit f von x gleich
dem da einsetze, kriege ich dann halt raus entsprechend minus 1 durch
Pi Sigma hoch 3 mal 2 Pi Sigma Quadrat gleich minus 2 Sigma.
Das Ganze mal in halbe ist dann entsprechend gleich minus n durch
Sigma.
Das heißt, nach dieser Nebenrechnung kann ich für hier vorne n halbe
mal Ableitung gemäß der Regel kann ich halt entsprechend einsetzen
minus n durch Sigma, muss dann hinten noch den Quotienten ableiten
nach Sigma.
Das ist aber relativ einfach.
Das ist einfach Sigma hoch 3, weil diese 2 künstelt sich dann schön
aus.
Mit der 2 bleibt Sigma hoch 3 unten stehen und oben bleibt halt das
stehen, was wir vorher auch schon hatten.
x minus µ Quadrat.
Das Ganze soll 0 gesetzt werden.
Wenn man das jetzt halt entsprechend ausrechnet und nach Sigma Quadrat
auflöst, dann kommt man halt dahin, dass Sigma Quadrat eben gerade 1
durch n Summe i gleich 1 bis n Xi minus µ zum Quadrat ist.
Und das ist halt auch die Schätzung, die wir schon kennengelernt
hatten, als wir die Gauss-Glocke durchgesprochen haben.
Das ist im Prinzip dann nichts anderes als der Erwartungswert der
Abweichung der Trainingsdaten vom eigentlichen Mittelwert.
Und deswegen nennt man es halt auch die Varianz, weil das ist, wie
viel man erwartet, dass die Daten, die von der Gauss-Glocke emittiert
werden, halt von dem Mittelwert entsprechend abweichen.
Das ist das Ganze, wenn man es nach Maximum Likelihood ausrechnet.
Likelihood-Funktionen aufstellen, logarithmieren, 0 setzen.
Problem ist, manchmal kommt man mit dem Verfahren nicht weiter.
Manchmal bleibt man stecken.
Man kann sich jetzt zum Beispiel vorstellen, wir haben das jetzt hier
für eine Gauss-Glocke gemacht.
Wie sieht das denn aus, wenn man das für eine Gauss-Mixtur machen
würde?
Da habe ich also so eine Summe von gewichteten E-Funktionen, kann dann
meine Likelihood-Funktion aufstellen.
Das ist dann das Produkt von den Summen der gewichteten E-Funktionen
für jedes einzelne Trainingsdatum.
Das Ableiten direkt schaffe ich vernünftig.
Also werfe ich den Logarithmus drauf, habe dann den Logarithmus von
Summe der gewichteten Gauss-Funktionen für das erste Trainingsdatum
plus Logarithmus der gewichteten Summen der E-Funktionen für das
zweite Trainingsdatum und so weiter und so fort.
Und da bleibe ich dann auch stecken.
Wenn ich das jetzt ableiten will, komme ich halt auch nicht weiter,
weil ich kann diesen Logarithmus in die Summe nicht reinziehen und ich
kenne keine vernünftigen Rechenregeln für Ableitungen, die mir das
auflösen würden, sodass ich da eine geschlossene Formel herausfinden
kann durch Ableiten und Nullsetzen für die ganzen Mittelwerte der
einzelnen Gauss-Glocken und für die ganzen Kovarianzmatrizen.
An der Stelle komme ich also mit der Maximum-Likelihood-Methode nicht
weiter und muss dann auf die Expectation-Maximization-Methode
umschwenken, indem ich zum Beispiel entweder ein paar
Modellierungsannahmen mache oder tatsächlich so etwas habe, wo ich
immer unbeobachtbare Ereignisse habe.
Das ist dann der Fall bei den Hinden-Markov-Modellen.
Da habe ich dann als unbeobachtbare Variablen in meinem Zufallsprozess
halt die Zustände, die ich durchlaufe.
Wie man das dann macht, das schauen wir uns dann nächste Woche
entsprechend an.
Okay, damit soll es für heute sein.