Also, wir hatten uns letztes Mal angeschaut, dass Dynamic Time Warping
als eine einfache Art und Weise, um einen Klassifikator zu bauen, der
Ähnlichkeit zwischen einer Aufnahme und einem Referenzmuster bestimmt,
sodass, wenn man mehrere Referenzmuster hat, man sich dann hinterher
für das nahegelegenste entscheiden kann.
Also sprich, wenn ich da einen Spracherkenner mitbauen will für
einzelne Wörter, brauche ich für jedes Wort, das ich hinterher
erkennen will, und die Menge der Worte, die wir erkennen wollen, die
nennen wir das Vokabular eines Spracherkenners, für jedes dieser Worte
im Vokabular brauche ich ein Referenzmuster.
Und wenn ich dann eine Aufnahme habe, berechne ich den Abstand
zwischen jedem Referenzmuster in meinem Vokabular und der Aufnahme und
entscheide mich dann für das nächstgelegene.
Das hat natürlich zum Beispiel den Nachteil, dass es extrem
sprecherabhängig ist, wie dieses Referenzmuster, das ich habe,
aussieht.
Zwar die Vorverarbeitung macht es leichter, Sprechernormalisierung
über diese Mehlfilterbank zum Beispiel, aber im Großen und Ganzen ist
es trotzdem so, dass wenn ich nur eine Aufnahme habe, dann ist die
typisch für diesen Sprecher, aber selbst wenn ja schon ein bisschen
die Geschwindigkeit variiert, sieht es anders aus.
Gut, das kriegen wir durch das Dynamic Time Warping hin.
Wenn ich aber jetzt einen anderen Sprecher habe, kann durchaus das
Muster durchaus komplett anders aussehen.
Das ist jetzt bei einigen Worten, die sich sehr stark unterscheiden,
vielleicht nicht so sehr ein Problem, wenn ich jetzt ein größeres
Vokabular habe und dann ja akustisch sehr ähnliche Wörter habe.
Einen, einen, eines und so weiter und so fort, dann können halt da
sprecherspezifische Aspekte plötzlich das alles überwiegen.
Möglicher Trick wäre jetzt, dass man halt versucht, nicht ein
Referenzmuster pro Wort zu haben, sondern zum Beispiel mehrere
Referenzmuster pro Wort von verschiedenen Sprechern.
Mein Mann, meine Frau, jemand Altes, jemand Junges, sodass ich da mehr
Variabilität in den Referenzmustern habe.
Was man auch versuchen kann, ist, dass wenn man mehrere
Referenzaufnahmen hat pro Wort, kann ich die zum Beispiel auch
zusammenmischen, dass ich sowas wie ein mittleres Referenzmuster
bekomme.
Heutzutage hat dieses Vorgehen inzwischen fast seine Bedeutung
verloren.
Bis vor ein paar Jahren war das sogar noch relativ relevant, nämlich
immer dann, wenn ich nur sehr wenig Speicher und nur sehr wenig
Rechenpower zur Verfügung habe, ich aber auch nur einzelne Wörter aus
einem sehr kleinen Vokabular erkennen wollte.
Also so frühe Telefone, Mobiltelefone, da konnte man praktisch so
Sprachbefehle einspeichern.
Wenn man da jemanden aus dem Adressbuch anrufen wollte, dann konnte
man zum Beispiel zu der Person halt ein Sprachmuster hinterlegen.
Dann sagte man halt Willi und wenn man dann hinterher sagte Willi
anrufen, dann konnte anhand dieses Referenzmusters das entsprechend
raussuchen.
Und das ist im Prinzip sowas wie mit dem DTW sowas entsprechend
rauszusuchen.
Dadurch, dass wir inzwischen viel mehr Rechenleistung in der
Hosentasche mit uns rumtragen, ist das Ganze nicht mehr so relevant.
Außer wir sind wirklich in Situationen, wo wir wirklich sehr wenig
Rechenleistung zur Verfügung haben.
Zum Beispiel so ein ganz billiger Raspberry Pi irgendwo im Embedded
-Bereich und wir wirklich nur einzelne Wörter, einzelne Muster
erkennen wollen, dann ist man mit sowas immer noch sehr gut bedient.
Jetzt ist das Problem beim DTW, dass er hier nur einzelne Wörter
erkennt.
Was wir aber letztendlich erkennen wollen, ist ganze Wortsequenzen,
Sätze, ohne dass wir jetzt vorher erstmal irgendwie eine Segmentierung
in Wörter vornehmen müssen.
Und um das zu machen, dass man diese Segmentierung sozusagen implizit
macht, während der Suche nach der besten Wortsequenz vorzugehen, hatte
man als Erweiterung des DTW das sogenannte One-Stage Dynamic
Programming erfunden.
Das hat halt, wie gesagt, den Vorteil, dass man nicht erst den Wörter
zerlegen muss und dann jedes Wort einzeln klassifizieren, sondern man
klassifiziert die gesamte Hypothese, bei der man davon ausgeht, dass
sie ein oder mehrere Worte enthält und hat trotzdem dem
gegenüberstehend nicht Referenzmuster, die den ganzen Satz umspannen,
sondern Referenzmuster, die nur für jeweils einzelne Worte sind, aus
denen sich dann hinterher die Wortsequenz zusammensetzen kann.
Und das macht man damit, dass man diese Matrix, die man beim DTW
ausrechnet, entsprechend erweitert.
Man kann sich das Ganze dann so vorstellen.
Wir haben auf der einen Achse wieder die Zeit und da ist die
Hypothesenaufnahme, die wir klassifizieren wollen.
Und letztendlich ist das diese Folge von Referenzvektoren.
Und auf der y-Achse schreiben wir wieder alle Referenzworte auf,
übereinander.
Wort 1, Wort 2 und so weiter und so fort.
Und diese Worte bestehen wieder aus Referenzvektoren in derselben
Vorverarbeitung.
Und was ich jetzt mache, ist, dass ich die Übergänge, die ich machen
darf, um einen erweitere, nämlich um einen Übergang zwischen Wörtern.
Sprich, am Anfang.
Normalerweise würde ich immer hier unten links anfangen, beim normalen
DTW.
Jetzt muss ich hier blockweise denken.
Das heißt, ich darf hier unten links anfangen, bei dem ersten Wort.
Ich darf aber auch hier anfangen, bei dem zweiten Wort.
Oder hier oben, bei dem dritten Wort.
Muss ich halt entsprechend ausrechnen, dass ich entweder hier anfange,
oder andersrum, dass ich hier anfange und dann innerhalb des Wortes
kann ich halt durch Auslassungen entsprechend da mich hinhocharbeiten.
Interessant wird es jetzt, wenn ich hier irgendwo später wieder
ausrechnen möchte den Wert von einer Anfangszelle, von einem Wort.
Was ich dann machen kann ist, dann kann ich natürlich auch wieder von
links gekommen sein, aber ich kann von jedem Ende eines anderen Wortes
gekommen sein.
Könnte also auch von da gekommen sein, oder von weiter oben.
Ich darf also in den Anfang eines Wortes reingehen von allen
Endzuständen aller anderen möglichen Worte.
Oder wenn man es umgekehrt machen will, wenn ich mal in so einem
Endzustand bin von einem Wort, dann darf ich von diesem Endzustand in
jeden Anfangszustand von anderen Worten wieder reingehen.
Darf ich also große Sprünge machen auf der Y-Achse.
Innerhalb eines Wortes, wenn ich so eine Zelle ausrechne, dann darf
ich nicht von zum Beispiel hier gekommen sein.
Also das wäre kein gültiger Übergang, weil ich fordere, dass ich immer
am Anfang eines Wortes anfange.
Hier dürfte ich nur so diese typischen DTW-Schritte gemacht haben.
Und wenn ich das so mache, kann ich wieder denselben DTW-Algorithmus
anwenden, um jetzt einen Pfad zu finden, der sich manchmal durch
Wörter schlingelt und manchmal von Worten zu Worten springen darf.
Nämlich immer dann, wenn er am Ende eines Wortes ist, darf er wieder
in die Anfänge neuer Wörter springen.
Und wenn man dann zum Beispiel sich aufzeichnet, wie der Pfad mit der
kleinsten Distanz aussieht, dann kann der so zum Beispiel so ausgehen,
dass ich hier am Anfang erstmal durch das Wort B durchgegangen bin.
Also habe ich das Wort B erkannt in dem Zeitraum und dann bin ich
hinterher gesprungen zum Wort D.
Dann habe ich das Wort D erkannt, dann bin ich wieder gesprungen und
dann war das Billigste, zum Anfang von D zu kommen und so weiter und
so fort.
Hier bin ich mal zu A gesprungen und dann bin ich vom Ende A nach Ende
B gesprungen.
Was man jetzt beachten muss, das was hier aufgetragen ist, ist nur der
Pfad mit der kleinsten Wahrscheinlichkeit.
Ich mache da auch keine Einschränkungen.
Wenn ich diese volle Matrix ausfülle, gemäß dynamischem Programmieren,
finde ich immer den Pfad mit der kleinsten kumulierten Distanz unter
allen Pfaden, die möglich sind.
Ich betrachte also implizit alle Pfade, die möglich sind, und das sind
sehr, sehr, sehr viele, und suche unter denen den Pfad mit der
kleinsten Distanz.
Ich bekomme da also die optimale Lösung raus.
Erst wenn ich dann anfange mit so Beam Search zu arbeiten und den
Suchraum irgendwie einzuschränken, wie ich das beim DTW gemacht habe,
erst dann fange ich an, suboptimale Lösungen zu bekommen.
Wenn man das Ganze jetzt halt entsprechend formalisieren will, dann
hat man bei so einer Zelle, die ich hier habe, noch eine dritte
Dimension K.
Und diese dritte Dimension K, die zu so einer Zelle gehört, das
entspricht dem Index des Wortes, zu dem diese Zelle gehört.
Und dann kann ich halt entsprechend diese neuen Übergänge zuordnen und
dann entsprechend nach der Zustandsfolge suchen, die hier L, Groß-L,
aus Groß-L Zuständen besteht und kann dann entsprechend anhand der
Zustände ablesen, anhand dieser dritten Dimension, in welchem Frame,
kleinen L, war ich denn hinterher in welchem Wort auf diesem kürzesten
Pfad.
Kurze Verständnisfrage, wenn ich das so formalisiere, dass ich sage,
ich habe hier unten Groß-L Vektoren in meiner Aufnahme und an, ich das
so formuliere, dass ich insgesamt Groß-N Mustervektoren habe, der auch
so Groß-N Mustervektoren habe, der Aufnahme, aber insgesamt L Punkte
auf dem Pfad.
Mein Pfad ist also L Schritte lang.
Warum ist logischerweise L immer nicht unbedingt gleich N, sondern
warum kann L ungleich N sein?
Warum ist also die Anzahl der Segmente auf dem Suchpfad kleiner als
die Anzahl der Hypothesenvektoren der Aufnahme?
Ich meine, ich muss ja für N Spalten ausfüllen und mache immer einen
Zeitschritt.
Warum muss das nicht unbedingt gleich sein, der Anzahl der Stationen
auf dem Suchpfad?
Naja, weil ich zum Beispiel auslöschen kann oder einfügen kann.
Wenn ich auslösche oder einfüge, dann gehe ich halt nicht diagonal
durch, sondern ich mache entweder weniger Schritte oder mehr Schritte,
als ich Hypothesenvektoren habe.
Okay, dementsprechend, wenn man jetzt halt diesen neuen Übergang
definiert, dann kann ich auch immer die akkumulierte Distanz, wie ich
sie beim Dynamic Programming berechnen muss, akkumulieren und muss
einfach nur eine Fallunterscheidung machen.
Die Zelle, die ich im Augenblick ausrechne bei J.
J sei immer der Index über die Referenzvektoren in dem Referenzwort K.
Wenn J gleich 1 ist, also wenn das der Anfang eines Wortes ist, dann
muss ich halt diesen anderen Schritt machen, als wenn ich mich
innerhalb eines Wortes befinde und damit, das ist die einzige
Modifikation beim Dynamic Programming und damit ist das One Stage
Dynamic Programming implementiert.
Das Ganze kann halt sehr aufwendig sein, weil was man letztendlich
hinterher macht, ist, dass man sehr viele so Dynamic Programming
Matrizen berechnet.
Man berechnet im Prinzip im allerschlimmsten Fall, wenn es also ganz
dumm läuft, ich mache jetzt keine Einschränkungen, was ich groß für
Übergangsschritte haben kann, dass ich den Suchraum eingreife.
Wenn es ganz dumm läuft, dann kann es sein, dass ich im O-Kalkül N
mal, also so viele Vektoren, wie ich in der Aufnahme habe, mal der
maximalen Länge eines der Worte, also wenn ich unter den K-Worten, die
ich habe, das längste raussuche und zähle, wie viele Vektoren die
Referenz hat und das sei M, K-max, dann habe ich also schon mal N mal
M und dann nochmal Anzahl der Worte, Matrizen, die ich ausfüllen muss.
Das ist halt relativ viel, was ich berechnen muss, plus die Matrix,
die dabei rauskommt, wird halt auch größer in Abhängigkeit davon, wie
viele Worte ich denn in meinem Vokabular habe.
In der Praxis ist es nicht ganz so schlimm, da man zum Beispiel, wenn
man jetzt so ein Verfahren zum Beispiel mit künstlichen Sprachen
kombinieren würde, nicht immer alle Wortübergänge als zulässig
erachten würde.
Dann müsste man weniger ausfüllen.
Plus, man kann jetzt was machen, um an dem Speicher zu drehen und die
Idee dahinter ist, dass, wenn ich die Übergänge, die ich so innerhalb
eines Wortes erlaube, geschickt wähle, zum Beispiel so eine typische,
einfache Editier-Distanz-Schritte zulasse, dann brauche ich nicht alle
Matrizen im Speicher zu halten.
Was ich dann machen kann ist, wenn ich so eine Spalte hier ausrechne,
dann muss ich nur auf Werte zurückgreifen, die einen Zeitschritt
weiter vorher lagen.
Das heißt, um diese Spalte auszurechnen, brauche ich nur die
vorhergehende Spalte im Speicher.
Das heißt, was ich im Speicher halten muss, sind im Prinzip nur zwei
Spalten und tausche die dann halt immer durch, schiebe die halt immer
durch.
Das heißt, ich brauche also nicht die ganzen Matrixen, sondern es
reichen zwei Spalten dieser Matrix, die muss ich immer gleichzeitig im
Speicher halten.
Und wenn ich es dann ganz auf die Spitze treibe, wenn ich also
wirklich nur so einen Minimalen Editier-Distanz-Schritt nehme, also
das sind die einzig zulässigen Schritte, dann brauche ich nie
irgendwas, was von oben unbedingt kommt, zumindest hier innerhalb,
wenn ich jetzt mal die Wortübergänge auslasse.
Und dann kann ich sogar auskommen mit letztendlich nur einer Spalte,
wenn ich die halt geschickt ausrechne, dass ich dann die Werte
überschreibe und immer nur Werte überschreibe, die ich dann später
entsprechend nicht mehr brauchen werde.
Das einzige K-Wert dabei ist, dass mich ja nicht nur die Distanzen
interessieren.
Das DTW, das Ausrechnen der Matrix, egal ob jetzt One-Stage-Dynamic
-Programming oder DTW für ein Wort, rechnet ja nur eine Distanz aus.
Das, was ich hinterher aus der letzten Spalte ablesen kann, wie bei
der Minimalen Editier-Distanz, ist, wie lang ist der kürzeste Pfad,
wenn ich die aufeinander warpe.
Bei der Editier-Distanz, was ist die kleinste Anzahl an Editier
-Schritten, die ich brauche, um die eine Sequenz in die andere Sequenz
zu überführen.
Das interessiert mich natürlich nicht.
Was mich interessiert, ist, was ist die Wortfolge.
Dafür brauche ich aber auch nur eine Spalte, in der ich dann aber
Arrays reintrage.
Was ich machen muss, ist, ich muss mir Rückzeiger abspeichern.
Ich muss mir sozusagen immer abspeichern, von wo bin ich gekommen.
Und das kann ich jetzt auf zwei Ebenen machen.
Das kann ich machen auf Ebene der Frames.
Für jeden Frame muss ich mir halt speichern, von wo bin ich denn
gekommen in dieser Zelle.
Aber das interessiert mich ja auch nicht.
Was mich interessiert, ist ja nur die Wortfolge.
Das heißt, eigentlich brauche ich mir die Rückzeiger nur dann zu
speichern, wenn ich in ein neues Wort reingehe.
Dann muss ich mir merken, von welchem Wort bin ich jetzt in welches
Wort reingegangen.
Und das kann man in so einer Spalte speichern, wo man dann so
dynamisch wachsende Listen hat, die einen dann immer nur noch die
Wortübergänge zu den jeweiligen Zeitpunkten abspeichern.
Und damit brauche ich also auch deutlich weniger Speicher, als wenn
ich die gesamte Matrix im Speicher halten will.
Ich hatte schon gesagt, meistens schränkt man die Wortfolgen, die
erkannt werden dürfen, irgendwie ein.
Zum Beispiel bei einer künstlichen Sprache, wenn ich so eine Grammatik
vorgebe von Sätzen, die valide sind und Sätzen, die nicht valide sind,
dann kann man immer sagen, dass bestimmte Wortfolgen zulässig sind und
andere Wortfolgen nicht zulässig.
Und aus den nicht zulässigen Wortfolgen kann ich ableiten, welche
Wortübergänge gar nicht zulässig sind.
Und diese nicht zulässigen Wortübergänge brauche ich dann entsprechend
beim Ausfüllen der DTW-Matrix auch nicht zu berechnen.
Und dann eine einfache Idee, um das schnell abprüfen zu können und
einschränken zu können, ist zum Beispiel, dass man sagt, für jedes
Wort definiere ich die Menge der erlaubten Vorgängerwörter.
Wenn ich dann also die Zeile ausfülle, wo es um den ersten Zustand
dieses Wortes geht, dann brauche ich nicht die Übergänge aus allen
möglichen Wörtern zu berücksichtigen, sondern nur die, die in dieser
Liste der erlaubten Vorgänger sind.
Das ist natürlich eine relativ primitive Einschränkung.
Sie wissen alle aus theoretischer Informatik, dass man das mit
kontextfreien Grammatiken zum Beispiel viel stärker einschränken kann.
Was man dann machen kann, ist, dass man entsprechend Zustände
einführt.
So wie man kontextfreie Grammatiken mit endlichen Automaten darstellen
kann, kann man auch anfangen, da Automat darzustellen für die Sprache,
die erlaubt ist und muss sich dann immer sozusagen ausrechnen, in
welchem aktuellen Zustand bin ich denn, was sind erlaubte
Vorgängerwörter.
Und dann muss ich halt entsprechend nur noch über die mein Maximum
bzw.
mein Minimum bilden, die überhaupt dann gemäß des aktuellen Zustands
erlaubt sind.
Das hatten wir schon gesagt, von hier mit, sagen wir mal, euklidischer
Distanz ist der Schritt zur Statistik nicht mehr weit.
Wir hatten schon die Mahler-Lobes-Distanz gesehen, die in so einer
multivariaten Gauss-Glocke drin ist.
Das heißt, von hier hat man dann in der Geschichte der Spracherkennung
als nächstes den Schritt hingemacht, statt mit Distanzmaßen, mit
Wahrscheinlichkeiten zu rechnen.
Und der Grund, warum man auf Wahrscheinlichkeiten rübergegangen ist,
statt mit so festen Mustern zu arbeiten und mit Distanzen, ist eben,
dass auch wenn ich mehrere Muster nehme und die Muster miteinander
mische, ich diese Varianz, die in der Sprache drin steckt, auf diesen
verschiedenen Ebenen, Sprecher, Signal, Kanal etc., Aussprache, dass
ich die damit nicht in den Griff bekomme.
Sondern, dass ich irgendetwas brauche, das besser damit umgehen kann,
dass etwas fassig ist, dass etwas unscharf ist und nicht so schön in
irgendwelche Muster reinfällt.
Und wenn immer in der Informatik man vor dem Problem steht, dass man
irgendwas fassig berechnen muss, irgendwas unscharf ist, man sich das
nicht scharf entscheiden will, ist das erste Werkzeug, zu dem man halt
greift, entsprechend die Stochastik.
Und da ist ein Werkzeug dessen, was man immer verwendet, entsprechend
die Gauss-Verteilung, die Multivariaten-Gauss-Verteilung und die Gauss
-Mixtur -Verteilung.
Deswegen nochmal ganz schnell ein Wiederholungsschritt durch die Gauss
-Verteilung.
Die Gauss-Verteilung selber ist so definiert, als p von x, 1 durch
Wurzel, 2p, Sigma-Quadrat, mit Sigma die Standardabweichung oder Sigma
-Quadrat die Varianz, mal e hoch, minus 1,5x minus µ zum Quadrat durch
Sigma -Quadrat.
Das ist, wenn x eindimensional ist.
Erste Frage, so eine Gauss-Verteilung, das ist ja jetzt erstmal nur
eine Funktion, die bildet x ab auf Werte aus den reellen Zahlen.
In der Wahrscheinlichkeitstheorie, als was interpretiere ich das?
Wenn Sie sich zurückerinnern an Ihre Wahrscheinlichkeitstheorie
-Vorlesung, Stochastik-Vorlesung, als was wird das interpretiert,
verwendet in der Stochastik?
Die Gauss-Verteilung.
Wie gesagt, das ist erstmal nur eine Funktion.
Die Funktion hat bestimmte Eigenschaften, zum Beispiel, wenn ich
darüber integriere, kommt das Integral 1 raus.
Das ist kontinuierlich und stetig.
Und als was wird es dann in der Wahrscheinlichkeitstheorie
entsprechend verwendet?
Wie hieß das nochmal?
Es wird verwendet als eine Wahrscheinlichkeitsdichte-Funktion.
Und das ist eine ganz wichtige Unterscheidung, die Sie auch hier
nochmal machen müssen, der Unterschied zwischen einer
Wahrscheinlichkeitsdichte -Funktion und einer
Wahrscheinlichkeitsverteilung.
Da müssen Sie sich nochmal dran erinnern.
Wahrscheinlichkeitsverteilungen waren definiert für Merkmalsräume, die
abzählbar waren.
Im Idealfall häufig abzählbar-endlich, aber es reicht auch abzählbar
-unendlich.
Geht es auch.
Wenn Sie aber mit kontinuierlichen Merkmalsräumen arbeiten, mit
kontinuierlichen Ereignissen, dann kommen Sie mit einer
Wahrscheinlichkeitsverteilung nicht weiter.
Angenommen, Sie haben ein kontinuierliches Ereignis und das, was Sie
messen, ist ein x aus den reellen Zahlen.
Was ist die Wahrscheinlichkeit dann für x gleich 3, zum Beispiel?
Was ist die Wahrscheinlichkeit?
0, genau.
Das ist aus der Wahrscheinlichkeitstheorie gesagt, dann hat die
Wahrscheinlichkeit 0.
Vielleicht gibt es irgendwo ein sicheres Ereignis, das könnte
Wahrscheinlichkeit 1 haben, aber im Prinzip alle bis auf 1 müssen 0
sein, meistens sind alle 0.
Das Einzige, was man machen kann, ist, dass man über einen kleinen
Bereich aus diesem Ereignisraum integriert und dann integriert man
über die Wahrscheinlichkeitsdichte-Funktion für diesen kleinen
Bereich, den man sich aus dem Ereignisraum rausschneidet und erst dann
bekommt man eine Wahrscheinlichkeit.
Das heißt, wenn ich über einen kleinen Bereich der reellen Zahlen
integriere, diese Wahrscheinlichkeitsdichte-Funktion, dann ist das
eben die Wahrscheinlichkeit für dieses Intervall, über das ich da
integriert habe.
Deswegen steht da auch ein kleines p von x, weil es eben keine
Wahrscheinlichkeit ist.
Wenn es eine echte Wahrscheinlichkeit wäre, stände ein großes p von x,
es ist nur eine dichte Funktion, deswegen steht da ein kleines p von
x.
Man verwendet diese Normalverteilung historisch deshalb so gerne, weil
viele natürliche Prozesse, die man so beobachtet in der Physik, in der
Biologie etc., mehr oder minder ungefähr normal verteilt sind.
Also wenn man sich so die Verteilung vieler natürlicher Prozesse
anschaut, dann sehen die so ungefähr aus wie eine Gaussglocke.
Deswegen ist das sehr schön beliebt und das Schöne bei so einer
Gaussglocke ist, die hat halt genau zwei Parameter.
Das ist einmal der Mittelwert µ, nennt man dann auch das erste Moment,
allgemein das erste Moment, bei der Gaussverteilung heißt es dann der
Mittelwert, und die Varianz, das zweite Moment.
Die Wurzel dann entsprechend aus der Varianz heißt die
Standardabweichung und wird halt auch über den Erwartungswert, sprich
das erste Moment, definiert.
Jetzt kann man das Ganze, ist natürlich die Frage, wo bekomme ich
diese Parameter her?
Ich muss ja irgendwie für irgendeinen Prozess, den ich beobachte,
jetzt diese Parameter irgendwo herbekommen.
Ich weiß also, der ist Gaussverteilt oder ich mache die Annahme, der
ist Gaussverteilt.
Das heißt noch lange nicht, dass der Gaussverteilt ist, aber weil mir
nichts besseres einfällt, mache ich halt die Annahme, der ist
Gaussverteilt.
Und jetzt möchte ich wissen, für diese spezielle Gaussverteilung
dieses Prozesses, den ich beobachte, was ist Mittelwert und Varianz.
Und dann bleibt mir nichts anderes übrig, als dass ich das auf
Trainingsdaten schätzen muss.
Das heißt, ich beobachte diesen Prozess eine ganze Weile lang und
schreibe mir in regelmäßigen Zeitabständen auf, was ist der Wert des
Prozesses.
Das ist also eine Folge wieder, x1 bis xn, das sind meine
Trainingsdaten.
Und aus diesen Trainingsdaten kann ich dann Mittelwert und Varianz
schätzen.
Der Mittelwert ist das arithmetische Mittel der Werte und
dementsprechend ist dann die Varianz das arithmetische Mittel von der
Abweichung der Werte vom Mittelwert zum Quadrat.
Wenn man sich die Verteilung anschaut, dann bestimmt halt der
Erwartungswert die Mitte der Verteilung, dann nimmt diese Verteilung
ihren höchsten Wert an und die Varianz bestimmt, wie breit oder wie
schmal so eine Glocke wird.
Und dann gibt es vorne vor halt noch diesen Normierungsfaktor, der
halt dafür sorgt, dass die Fläche unter der Glocke immer 1 ergibt.
Das Ganze erweitern wir jetzt entsprechend ins Mehrdimensionale.
Also angenommen, mein xi ist nicht mehr aus den reellen Zahlen,
sondern mein xi sei ein d-dimensionaler Vektor, xi1, xi2 bis xid.
Dann kann ich auch für solche mehrdimensionalen, sprich multivariaten
Größen, eine Wahrscheinlichkeitsdichte-Funktion basierend auf der e
-Funktion und der Gauss-Glocke definieren.
Und das ist dann entsprechend 1 durch Wurzel 2 pi hoch d mal Betrag
einer Matrix sigma e hoch minus 1 halb x minus µ transponiert mal
sigma hoch minus 1 mal x minus µ.
Auch für so eine Verteilung kann ich entsprechend die Parameter
schätzen und hier hat das µ wieder die gleiche Bedeutung wie im
eindimensionalen Fall, das ist der Mittelwert.
Kann ich einfach als arithmetisches Mittel der von beobachteten Werten
von Trainingsdaten schätzen.
Die Matrix selber hat eine etwas leicht andere Bedeutung.
Da hatten wir vorher die Varianz stehen, einen einzelnen Wert, jetzt
haben wir entsprechend eine Matrix stehen.
Und zwar eine d mal d-dimensionale Matrix.
Und diese Matrix heißt die Kovarianzmatrix.
Wer kann sich noch erinnern, was die Kovarianzmatrix ist, was das
bedeutet?
Welche Werte stehen in einer Kovarianzmatrix?
Überleg, überleg, ratta ratta.
Die Kovarianzmatrix bestimmt auch die Varianz zwischen zwei Werten und
zwar zwischen den Dimensionen.
In diesem Wert ij, in der Zelle ij der Matrix steht drin die Kovarianz
zwischen der Dimension i und der Dimension j in den Merkmalsvektoren.
Also die Kovarianz von x i und x j, wenn ich halt die i-te Dimension
und die j-te Dimension wieder als Zufallsvariable auffasse.
Und die ist genau, oder nicht genauso, die ist ähnlich definiert wie
die Varianz von einem einzelnen Ereignis x i.
Da stand ja x i minus Erwartungswert zum Quadrat.
Und jetzt macht das auch Sinn, warum da vielleicht Quadrat stand.
Weil was man jetzt macht ist, man multipliziert die Abweichung in der
einen Dimension, also die Abweichung in x i von seinem Erwartungswert
der Dimension i, mal die Abweichung in der anderen Dimension, also in
j minus x j.
Wenn man das entsprechend macht, diese Kovarianzmatrix so definiert,
dann ist das erste, dass für echte Normalverteilungen dieses x i i
größer gleich 0 ist.
Sprich, die Werte, die auf der Diagonalen liegen, die sind größer
gleich 0 und für eine richtige Normalverteilung müssen sie so echt
größer 0 sein.
Was heißt das denn?
Das ist immer die Varianz mit sich selber, sprich da steht für jede
Dimension, was ist da die Varianz in dieser Dimension.
Nicht die Kovarianz, sondern die Varianz in dieser Dimension der
Merkmale.
Dann ist das Ganze symmetrisch aufgrund der Kommutativität der
Multiplikation, macht keinen Unterschied, ob ich i mit j Kovarianz
ausrechne oder j mit i, kommt dasselbe heraus.
Und man kann zeigen, dass die Matrix positiv semidefinit ist und das
ist ganz sinnvoll, weil ich an dieser Stelle ja mit dem Inversen der
Kovarianzmatrix arbeite.
Und wenn Sie irgendwo ein Inversus einer Matrix sehen, ist die erste
Frage, die Sie sich immer in einer Formel stellen müssen, ist es denn
überhaupt garantiert, dass die Matrix, die ich da inventiere, auch
überhaupt invertierbar ist.
Und da das Ganze positiv semidefinit ist, weiß man wenigstens, dass
die Matrix auch garantiert interpretierbar ist.
Und wenn man sich jetzt so eine multivariate Gauss-Verteilung mit so
einer Kovarianzmatrix vorstellt, dann kann man die sich als eine Art
Ellipsoiden vorstellen.
Also wenn ich das Ganze zum Beispiel ins Zweidimensionale nehme, x1
und x2 habe, und der dritte Wert sei dann eben der Wert dieser
multivariaten Kovarianzmatrix, dann hat das Ganze die Form eines
Ellipsoiden.
Und die Varianzen in den einzelnen Dimensionen bestimmen ja sozusagen
den Radius des Ellipsoiden in dieser Dimension.
Und das findet man dann entsprechend auf der Diagonalen.
Und was die anderen Kästchen angeht, diese anderen Kovarianzkästchen,
die sorgen im Prinzip dafür, dass dieser Ellipsoid irgendwie im Raum
gedreht wird.
Die sorgen dafür, dass die Varianzen nicht immer parallel im
Koordinatensystem liegen, sondern die sorgen dafür, dass diese
Varianzachsen des Ellipsoiden irgendwie gedreht werden.
Andersrum, wenn jetzt auf der Diagonalenwerte echt ungleich 0 stehen
und alle anderen Werte in der Kovarianzmatrix 0 sind, dann liegen
diese Achsen des Ellipsoiden gerade parallel zu den Achsen des
Koordinatensystems.
Und die Verschiebung dieser Achsen, die wird bestimmt durch den
Mittelwert.
Der Mittelwert verschiebt diese Achsen dann entlang der Achsen des
Koordinatensystems.
Warum muss für eine echte Normalverteilung auf der Diagonalen immer
was stehen, was echt größer 0 ist?
Was würde denn passieren, wenn auf der Diagonalen irgendwo eine 0
steht?
Was würde das denn bedeuten?
Was würde rauskommen?
Was würde passieren?
Das heißt also, in dieser einen Dimension ist die Varianz der Daten 0.
Was heißt das, die Varianz der Daten ist 0?
Genau, da kommt immer ein und derselbe Wert raus.
Jetzt kann man sich vorstellen, was würde das denn bedeuten im
Eindimensionalen bei einer Gaussglocke.
Wenn immer ein und derselbe Wert rauskommt, dann müsste die
Gaussglocke immer kleiner, kleiner, kleiner, kleiner werden, weil die
Varianz ist ja die Breite der Gaussglocke.
Es darf aber immer nur ein Wert rauskommen, also die muss unendlich
klein werden.
Gleichzeitig muss das Integral über der Gaussglocke aber immer 1 sein.
Es darf es aber nicht sein, wenn die unendlich klein ist, diese
Varianz.
Ich also hinterher nur an einer Stelle einen Wert habe, der ungleich 0
ist und alle anderen Werte sind 0.
Ich habe so eine Funktion und darüber integriere ich.
Was ist das Integral, Riemann-Integral?
Ich habe eine Funktion, die hat an einer Stelle einen Wert ungleich 0
und an allen anderen Stellen 0.
Jetzt integriere ich über den gesamten Merkmalsraum, über alle reellen
Zahlen.
Was kommt für eine Fläche raus laut Riemann-Integral?
0.
Aber die Gaussglocke muss Integral 1 haben.
Da vorne ist ja so ein komischer Faktor.
Das heißt, der Faktor muss dann 1 durch, muss dann irgendwie ganz,
ganz groß werden.
Der muss dann gegen unendlich gehen.
Das heißt, da kommt etwas ganz, ganz Böses raus.
Es kommt dann idealerweise so etwas wie eine Distribution raus,
nämlich ein Dirac-Stoß.
Das heißt also, im Mehrdimensionalen muss also diese Kovarianz echt
größer 0 sein.
Ansonsten habe ich da in einer der Dimensionen so eine Art
Singularität stehen.
Jetzt heißt es, in der Natur sind viele Sachen Gauss verteilt, im
Mehrdimensionalen sind sie Multivariat-Gauss verteilt.
Und jetzt hatte ich schon gesagt, naja, eigentlich nimmt man das an.
Es gibt sicherlich genügend Prozesse, die nicht Gauss verteilt sind.
Und ein solcher Prozess, bei dem die Merkmalsvektoren nicht Gauss
verteilt sind, der ist eben die menschliche Sprache.
Wenn ich also mir die Merkmalsvektoren anschaue, die aus so einer
Vorverarbeitung rauskommen, und mir die Verteilung anschaue, dann ist
die eben nicht Gauss verteilt.
Jetzt will man das natürlich auch in den Griff bekommen.
Und deswegen greift man häufig zu Gauss-Mixturverteilung, Gauss
-Mischverteilung.
Was man da macht, ist, dass man halt mehrere multivariate Gauss
-Verteilungen nimmt und man die gewichtet aufsummiert.
Jede Gauss-Verteilung bekommt noch ein Gewicht, wird mit diesem
Gewicht, wird der Wert, der aus der Gauss-Glocke rauskommt,
multipliziert, dann werden die aufsummiert.
Und dann muss man natürlich dafür sorgen, dass die Gewichte sich auch
zu 1 aufsummieren, damit am Ende hinterher das Integral über diese
Summe auch entsprechend 1 ist.
Jetzt kann man sagen, ja, das ist ja prinzipiell eine schöne Idee,
gibt es da auch einen tieferen Sinn hinter?
Der eine Sinn ist, es leicht auszurechnen, aber der zweite Sinn ist
auch, dass man zeigen kann, dass man jede beliebige
Wahrscheinlichkeitsdichte -Funktion beliebig genau annähern kann.
Wenn man sich also einen Fehler vorgibt, den man maximal machen will,
dann kann man eine Annäherung finden, die maximal diesen Fehler hat
und nur eine endliche Anzahl an Gauss-Glocken verwendet.
Das heißt also, für jeden maximalen Fehler, den ich mir vorgebe, für
eine beliebige Wahrscheinlichkeitsdichte-Funktion finde ich eine
endliche Anzahl an Gauss-Glocken, die diese entsprechend meines mir
maximal vorgegebenen Fehlers annähert.
Das heißt, ich habe damit ein Werkzeug, mit dem ich beliebige
Wahrscheinlichkeitsdichte -Funktionen gut annähern kann.
Wenn man jetzt damit in der Praxis arbeitet, hat man wieder das
Problem, dass man Parameter schätzen muss.
Und jetzt muss ich halt, in der Covarianzmatrix muss ich ja immer
Dimensionen halber Parameter schätzen, plus nochmal Dimensionen
-Parameter für eine Gauss-Glocke.
Und jetzt habe ich nicht eine Gauss-Glocke, jetzt habe ich K-Glauss
-Glocken.
Das heißt, mit der Anzahl der Gauss-Glocken wächst natürlich die
Anzahl der Parameter auch noch linear.
Und meistens sind das mehr Parameter, als wir mit den begrenzten
Trainingsdaten, die wir haben, robust schätzen können.
Deswegen fängt man an, Parameter zu sparen.
Und ein Trick, Parameter zu sparen, und damit auch in Klammern
Rechenszeit, ist, wenn man nicht beliebige Covarianzmatrizen zulässt,
sondern zum Beispiel nur diagonale Covarianzmatrizen.
Damit kann ich dann natürlich wieder nicht alles schön beliebig genau
annähern.
Ich mache wieder eine Modellannahme, eine Vereinfachung, die mit der
Realität nichts zu tun hat.
Aber es spart mir jede Menge Parameter, wenn ich halt fordere, dass
diese Achsen der Ellipsoiden eben parallel zum Koordinatensystem
liegen müssen.
Dann muss man sich ein bisschen was überlegen, was man machen kann, um
das schneller zu berechnen.
Wenn ich jetzt so eine Gaussglocke, eine einfache einzelne Gaussglocke
ausrechne, dann habe ich da drin stehen eine E-Funktion.
Und eine E-Funktion im Rechner auszurechnen ist ekelhaft.
Wie kann ich im Rechner überhaupt eine E-Funktion ausrechnen?
Das habe ich da zur Verfügung.
Jetzt nicht sagen, da gibt es eine Taste E auf dem Taschenrechner.
Wie macht das?
Wie macht das der Taschenrechner?
Wie macht das ein Rechner, wenn er eine E-Funktion ausrechnen will?
Was kann man machen?
Welches Werkzeug aus der Mathematik haben Sie da?
Was gibt es da?
Sowas wie eine Tälereien-Expansion zum Beispiel.
Kann man halt als Summe von irgendwas so eine E-Funktion annähern.
Und wenn man das halt sehr genau machen will, muss man halt eine sehr
lange Tälerei ausrechnen.
Dass man dann hinterher in eine entsprechende Genauigkeit reinkommt,
die der Genauigkeit entspricht zum Beispiel des Datentyps, den man
verwendet.
Also das heißt, E-Funktion ausrechnen ist rechnerisch sehr, sehr, sehr
teuer.
Jetzt kann man natürlich noch so ein paar Tricks machen, dass man
vielleicht irgendwo Tabellen hinterlegt, aber die Tabellen können ja
auch nicht so groß, unendlich groß werden.
Das heißt also, E-Funktion ausrechnen kostet sehr viel Zeit.
Wenn ich das also im Rechner ausrechne, ist das blöd.
Manchmal reicht es auch aus, dass man nicht die E-Funktion ausrechnet,
sondern dass man im logarithmischen Bereich ausrechnet.
Wenn man nur den Logarithmus finden will.
Einfaches Beispiel, angenommen ich habe irgendeine Aufnahme gemacht.
Kann eine Sprachaufnahme sein, kann irgendeine Beobachtung eines
natürlichen Prozesses sein.
Und was ich jetzt wissen möchte, welcher natürliche Prozess war das
denn?
Angenommen, ich habe fünf zur Auswahl.
Dann könnte ich für alle fünf natürlichen Prozesse, die ich zur
Auswahl habe, eine Gauss-Glocke schätzen.
Und könnte mir dann überlegen, Bezier, Naiver, Bezier, Klassifikator,
Beobachtung, reinstecken in die Gauss-Glocke, mal Apriori
-Wahrscheinlichkeit, bekomme ich eine Posteriori-Wahrscheinlichkeit
raus.
Dann heißt es, ich bekomme eine Wahrscheinlichkeit dafür raus, dass
jeder Prozess diese eine Beobachtung hervorgebracht hat.
Und dann entscheide ich mich halt für den Prozess, für die Klasse, die
da die höchste Wahrscheinlichkeit hat.
Das heißt, mich interessiert ja in Wirklichkeit gar nicht, wie groß
jetzt genau die Wahrscheinlichkeit war.
Die Aposteriori-Wahrscheinlichkeit, mit der jetzt der Prozess diese
Beobachtung hervorgebracht hat.
Mich interessiert ja nur unter den Prozessen, die ich zur Auswahl
habe, unter den Klassen, die ich zur Auswahl habe, welches war die mit
der höchsten Wahrscheinlichkeit.
Und das heißt wiederum, ich brauche nicht den Gauss-Wert auszurechnen,
sondern ich kann der Wert, der da rauskommt, den kann ich erstmal
durch irgendeine beliebige monotone, streng monotone Funktion
durchjagen.
Und dann muss ich nur noch den Wert finden, der rauskommt, wenn ich
das Ganze durch so eine streng monotone Funktion rausjage.
Weil durch die strenge Monotonität, der Wert, der vorher am höchsten
war, der ist auch, nachdem ich diese Funktion angewendet habe, immer
noch der höchste Wert.
Und eine streng monotone Funktion ist zum Beispiel der Logarithmus
Naturalis.
Also, Logarithmus Naturalis angewandt auf so eine Gauss-Glocke, da
fällt die E-Funktion weg.
Juche!
Einziges Kaviat, ich muss natürlich dann Logarithmus Naturalis von dem
Normalisierungsfaktor ausrechnen.
Aber manchmal kann man den auch einfach ignorieren.
Oder, was man auch machen kann, wenn wir uns den Normalisierungsfaktor
anschauen, dann hat dieser Normalisierungsfaktor, nehmen wir eine
einfache Gauss-Glocke, eine schöne Eigenschaft.
Also angenommen, ich würde hiervon, ich würde sagen, also wenn ich
sowas ausrechne für den X, dann ist mir die E-Funktion zu teuer.
Also rechne ich den Logarithmus Naturalis davon aus, weil mich
interessiert nur das Maximum.
Dann fällt die E-Funktion weg, aber dafür muss ich ja den Logarithmus
Naturalis von dem Ding berechnen.
Warum ist das kein Problem?
Ja, aber ich brauche hier ja keinen Logarithmus zur Basis 2, sondern
ich muss ja den Logarithmus Naturalis von dem Ding hier ausrechnen.
Und da steht ja keiner.
Ich mache hier Logarithmus Naturalis von P von X.
Das heißt, Logarithmus Naturalis von dem Teil plus Logarithmus
Naturalis von dem Teil.
Das heißt, die E-Funktion ist weg, Logarithmus Naturalis von dem Teil,
bleibt nur noch der Exponent stehen, aber ich muss Logarithmus
Naturalis von dem Ding ausrechnen.
Das könnte man ja sagen, das ist ja doof.
Eine E-Funktion ist weg, dafür muss ich jetzt den Logarithmus
Naturalis ausrechnen.
Das kann ja wohl kaum schneller gehen, als eine E-Funktion
auszurechnen.
Aber warum ist das ein Scheinargument?
Was ist das Schöne, wenn ich den Logarithmus Naturalis von dem Ding
ausrechne?
Welches Symbol kommt hier nicht vor?
Dann kommt kein X vor.
Das heißt, den Logarithmus Naturalis muss ich genau einmal ausrechnen.
Der ist für alle X gleich.
Das heißt, für je beliebige X, wenn ich so eine Verteilung habe, muss
ich einmal hier den Logarithmus Naturalis von dem Teil ausrechnen, den
speichere ich mir irgendwo ab.
Und wenn ich dann P von X ausrechnen will, und davon den Logarithmus,
dann nehme ich das, was ich vorher ausgerechnet habe, plus diesen
Exponenten.
Und das geht natürlich deutlich, deutlich schneller, als wenn ich
immer diese E-Funktion komplett auswerten muss.
Das heißt, häufig rechnet man halt im Logarithmus Naturalis.
Und dann laufe ich in ein Problem bei Gauss' Mischverteilung.
Da funktioniert das Ganze leider nicht mehr.
Bei Gauss' Mischverteilung muss ich hier wieder den Logarithmus
Naturalis davor schreiben.
Und dann steht da Logarithmus Naturalis von einer Summe.
Und was ist der Logarithmus Naturalis von einer Summe?
Da nimmt man das Taschenbuch der Mathematik her und guckt nach.
Und was steht im Taschenbuch der Mathematik drin?
Da steht drin Logarithmus vom Produkt, das ist Logarithmus plus
Logarithmus.
Und was steht drin für ein Logarithmus einer Summe?
Da blättert man und blättert man und findet halt leider gar nichts.
Das ist doof.
Das heißt, dieser schöne Trick mit dem Logarithmus, um möglichst
schnell zu rechnen, um die E-Funktion nicht ausrechnen zu müssen, der
versagt bei Gauss' Mixturverteilung.
Gleichzeitig sind aber Gauss' Mixturverteilungen das, womit ich viele
Sachen gut approximieren kann.
Aber es dauert zu lange, sie auszurechnen.
Das ist ein Riesenaufwand.
Und da muss man sich jetzt was einfallen lassen, was man da machen
kann.
Und da kommen wir aber später zu.
Erstmal nur, bei Gauss' Mixturverteilung haben wir da ein Problem.
Was kann man machen?
Dann kann man zum Beispiel sich ein Instrument hernehmen, der
Vektorquantisierung.
Eine Idee wäre ja, gut, ich rechne halt so eine Gauss'
Mixturverteilung nicht für beliebige x aus, sondern ich quantisiere
mir meinen Merkmalsraum, so wie ich ein analoges Signal quantisiere.
Und dann habe ich nur noch eine endliche Menge an Punkten, für die ich
so eine Gauss' Mixtur ausrechnen muss.
Und dann rechne ich die irgendwann einmal in Ruhe aus und speichere
mir halt eine ganz große Tabelle ab, für jede Quantisierungsstufe den
Wert, und schlage das Ganze hinterher nur noch in der Tabelle nach.
Ich mache natürlich einen Fehler bei der Quantisierung.
Es kommt wieder ein Quantisierungsrauschen drauf.
Diesmal kommt das Quantisierungsrauschen halt nicht auf das analoge,
eindimensionale Signal, sondern das Quantisierungsrauschen kommt jetzt
auf den zweidimensionalen Merkmalsvektor, der bei mir aus der
Vorverarbeitung rausgefallen ist.
Das heißt, im allgemeinen Fall, was man machen will, ist, man will
irgendwelche Vektoren abbilden auf eine Menge von Indizes, und jeder
Indize steht für einen prototypischen Vektor aus diesem Merkmalsraum.
Und alles, was irgendwie in einen Intervall um diesen Vektor herum
reinfällt, wird auf diesen Prototypvektor drauf quantisiert.
Und dann kann man halt Sachen vorberechnen und zum Beispiel alle
möglichen Sachen für diese Menge der Indexvektoren dann hinterher nur
noch im Speicher nachschlagen und sparte durch jede Menge Rechenzeit.
Ich tausche halt Rechenzeit gegen Speicher, das kann man häufiger
machen, und ich verliere natürlich an Genauigkeit dadurch, dass ich
quantisiere.
Die Frage lautet natürlich, also die Quantisierung ist einfach, wenn
ich eine Menge von Referenzvektoren gegeben habe, dann kann ich
einfach quantisieren, indem ich den am nächsten gelegenen
Quantisierungsvektor hinzufüge.
Jetzt könnte man ja anfangen zu argumentieren, ja, da muss man sich
erstmal überlegen, ist das denn wirklich schneller, wenn ich erst
quantisiere?
Weil wenn ich quantisiere, muss ich ja den am nächsten gelegenen
Referenzvektor finden.
Das heißt, ich muss sehr, sehr, sehr viele Distanzen erstmal
raussuchen, um dann hinterher das Minimum der Distanz zu finden.
Plus, ich handle mir noch Quantisierungsfehler ein.
Gut, das erste, was man sich angucken kann, ist, dass man den
Quantisierungsfehler möglichst klein hält.
Das heißt, man sollte seine Referenzvektoren irgendwie geschickt
wählen.
Bei der Quantisierung von Sprachsignalen hat man gesagt, naja, machen
wir entweder gleich verteilt, oder wenn wir ein bisschen Platz sparen
wollen, wissen wir, dass das vom Höreindruck her, dieses A-Law, Mu-Law
ganz gut funktioniert.
Wenn ich jetzt hier irgendeinen beliebig strukturierten Vektorraum
habe, da muss ich gucken, wie ich diesen Vektorraum gut auflösen kann.
Und eine Möglichkeit wäre zum Beispiel, dass man euclidische Distanzen
verwendet zu den Referenzvektoren.
Und wenn man dann Referenzvektoren hat und die euclidische Distanz
ausrechnet, dann kommt man zum Voronoi-Diagramm.
Das Voronoi-Diagramm erhält immer solche Flächen und solche Flächen
stehen für die Menge all der Vektoren, die am nächsten zu dem
Referenzvektor liegen, dem diese Fläche zugeordnet wird.
Das sind diese Voronoi-Diagramme.
Sicherlich schon mal gesehen.
Und angenommen, ich habe jetzt hier irgendwie einen derartgeordneten
Merkmalsraum, wo ich halt so Referenzvektoren reingelegt habe, ich
habe so Voronoi-Regionen aufgezogen, und jetzt möchte ich das X
zuordnen.
Die Quantisierung aufgrund der euclidischen Distanz würde dieses X
entsprechend diesem Merkmalsraum zuordnen.
Das ist halt, der fällt halt in die Fläche rein, die am nächsten an
diesem Referenzvektor liegt.
Wenn ich mir das als Mensch anschaue, wäre ich aber unzufrieden damit.
Als Mensch würde man sich überlegen, dass das X doch vielleicht
irgendwie mehr in die rechte Hälfte reinholt.
Allein aufgrund der Tatsache, dass ja hier irgendwie die
Referenzvektoren alle schön kuschelig nah beieinander liegen, und der
hier liegt viel weiter weg als irgendein anderer Referenzvektor an den
anderen Referenzvektoren, während ich hier so Referenzvektoren habe,
die ja irgendwie weiter voneinander weg sind.
Also würde es doch eher mehr Sinn machen, dass dieses X ähnlich ist
einem derjenigen Referenzvektoren, die so weit voneinander zuliegen.
Und deswegen ist das Erste, was man macht, dass man erstmal die
euclidische Distanz wegwirft und man stattdessen die Mahanalobes
-Distanz nimmt, weil halt die Mahanalobes-Distanz diese Streuung der
Daten berücksichtigt mithilfe der Kovarianzmatrix in diesen einzelnen
Dimensionen.
Diese Streuung muss man entsprechend auf einer Trainingsmenge
natürlich lernen.
Das heißt, ich brauche irgendwie eine Trainingsmenge.
Dann gucke ich, wie sieht denn die Streuung aus.
Also ich habe meine Referenzvektoren schon irgendwie gegeben.
Ich habe jetzt Trainingsdaten.
Ich gucke mir an, wie groß ist jetzt die Streuung in den einzelnen
Dimensionen der Trainingsdaten und dann kann ich diese Streuung
entsprechend den einzelnen Referenzvektoren noch zuordnen.
Ich muss also wissen, welcher Trainingsvektor soll auf welchen
Referenzvektor quantisiert werden.
Kann mir dann für diese Menge, die zu dem Referenzvektor gehört, die
Streuung anschauen und damit die Kovarianzmatrix entsprechend
berechnen.
Und kann dann, wenn ich den Referenzvektor als Mittelwert nehme,
entsprechend diese Mahanaloges Distanz initialisieren.
Insgesamt steht natürlich die Frage, wo kriege ich überhaupt diese
Referenzvektoren her.
Die muss ich ja auch irgendwie lernen.
Und dann kann man sich diese Vektorkquantisierung auch wieder als
Klassifikationsproblem vorstellen.
Man kann sich vorstellen, ich habe eine Menge an Trainingsvektoren.
Ich weiß von diesen Trainingsvektoren, dass sie alle zu einem
Referenzvektor gehören sollen.
Welches wäre denn der passende Referenzvektor?
Kann man dann halt zum Beispiel mit dieser Mahanaloges Distanz machen,
dass ich Mittelwert ausrechne, Kovarianz, und dann hätte ich da
entsprechend eine, letztendlich eine Gaussglocke, die zu diesen Daten
gehört.
Ein Problem, das man dann hat, ist, dass man, wenn man Ausreißer in
den Trainingsdaten hat, die das Ergebnis verunreinigen können.
Wenn ich also ein Beispiel habe, dass irgendwie Messfehler,
irgendjemand, der einfach nicht sprechen kann, oder Annotationsfehler
bei den Trainingsdaten, also irgendwo habe ich so einen Ausreißer, der
zieht mir unter Umständen dann den Mittelwert in eine komplett falsche
Richtung, weil er übermäßig viel Einfluss hat.
Oder vielleicht habe ich auch Sachen in eine Klasse reingetan, die
eigentlich besser in zwei Klassen gehört hätten, weil sie zwar
irgendwie konzeptionell dazu zusammengehören, aber die Ausprägung der
Ereignisse sich in zwei verschiedene Klassen eigentlich zerlegt.
Was man da machen kann, ist, dass man halt versucht, nicht einen
Referenzvektor pro Klasse zu lernen, sondern mehrere Referenzvektoren
pro Klasse.
Hat dann den Vorteil, der eine Ausreißer würde halt den einen
Referenzvektor wegziehen auf seinen Ausreißer hin und der Rest würde
sich hoffentlich um einen anderen Referenzvektor kümmern.
Oder wenn ich halt so das Ganze zerlegt in mehrere kohärente
Unterregionen, dann würde man einen Referenzvektor pro Unterregion
bekommen.
Und wenn man dann hinter Quantisieren will, dann könnte man das
entsprechend mit dem k-Nächsten-Nachbar-Algorithmus haben.
Den hatten wir schon kennengelernt als ein überwachtes Verfahren und
man kann dann mit k-Nächsten-Nachbarn quantisieren, indem man sagt,
angenommen, ich habe hier Referenzvektoren.
Und hier habe ich Referenzvektoren für insgesamt drei Klassen.
Es gibt Kreise, es gibt Dreiecke und es gibt Quadrate.
Und das sind alles unterschiedliche Referenzvektoren für ihre
jeweilige Klasse.
Und jetzt habe ich einen neuen Datenpunkt X und möchte den jetzt
quantisieren.
Was ich dann hier mache, ist, dass ich mir zum Beispiel die sechs
nächsten Nachbarn anschaue.
Ich sage mir aus Erfahrung, weil ich das so will, k gleich sechs.
Ich schaue mir die sechs nächsten Nachbarn an.
Also gucke ich mir, welches sind die sechs Referenzvektoren, die am
nächsten dran liegen, bekomme dann so ein Bild und dann zähle ich.
Es gibt drei Dreiecke, zwei Kreise und ein Quadrat.
Also hat zum Beispiel die Dreiecke, haben die gewonnen.
Wäre eine Möglichkeit, das zu machen.
Und dann nehme ich halt den Index derjenigen, die am nächsten
reinpassen.
Jetzt kann ich natürlich anfangen, das Ganze zu variieren.
Jetzt könnte ich sagen, naja, angenommen diese zwei Kreise, der eine
Kreis wäre hier, der andere Kreis wäre da und die Dreiecke sind ja
relativ weit weg und das Quadrat auch, wäre es nicht vielleicht dann
doch sinnvoller, den Kreis zu nehmen.
Dann könnte ich auch zum Beispiel solche Sachen machen, ich kumuliere
die Distanzen, ich rechne Distanz zu den Kreisen im Durchschnitt
geteilt durch die Anzahl der Referenzvektoren zu Distanz zu den
Dreiecken, zu Distanz zu den Quadraten.
Wäre eine andere mögliche Variation, die man machen kann.
Jetzt ist das natürlich wieder so ein ähnliches Problem wie vorhin
schon.
Ich muss hier, wenn ich quantisiere, herausfinden, nicht nur welches
ist der nächste Nachbar, sondern welches sind die k-nächsten Nachbarn.
Und wenn ich jetzt so eine typische Quantisierungsprobleme habe, dann
kann es passieren, dass ich so etwas wie 16 bis 1024 Referenzvektoren
pro Klassen habe.
Es kann sein, dass ich sehr viele Klassen habe.
So in der Spracherkennung ist es nichts Ungewöhnliches, 16.000 oder
noch mehr Klassen zu haben.
Also so etwas wie 10 hoch 4 bis 10 hoch 5 Klassen ist nicht
ungewöhnlich.
Mein Merkmalsraum kann so etwas wie 42 dimensional sein, 16 bis 48
Dimensionen ist überhaupt nicht ungewöhnlich.
Das heißt, ich müsste jetzt für einen Merkmalsvektor zu 10 hoch 6
möglichen Referenzvektoren eine Distanz ausrechnen, indem ich in 48
Dimensionen immer die, zum Beispiel bei eurer klitschen Distanz, die
Distanz ausrechne und da die Distanz ausrechne.
Das ist ein ziemlich hoher Rechenaufwand.
Den will man wieder reduzieren, weil bei der Spracherkennung ist
Rechenzeit immer knapp und man will schneller sein.
Und dann gibt es zwei Möglichkeiten zu reduzieren.
Und das ist immer das allgemeine Vorgehen, wenn ich irgendwie etwas
beschleunigen will.
Dann stehe ich meistens vor der Möglichkeit, ich beschleunige in einer
Art und Weise, dass ich immer noch das korrekte Ergebnis finde, aber
dass mir unter Umständen die Beschleunigung nicht garantiert ist.
Weil wenn es was gäbe, dass die Beschleunigung garantiert und ich
finde das korrekte Ergebnis, dann würde ich es ja erstmal so machen.
Dann wäre das ja eigentlich der korrekte Algorithmus.
Oder die andere Möglichkeit ist, ich beschleunige und die
Beschleunigung ist garantiert, aber es kann halt sein, dass ich nicht
mehr das optimale Ergebnis finde, sondern ein suboptimales Ergebnis.
Wenn man die zweite Klasse nimmt, also ich wollte das hier
beschleunigen, aber nicht mehr garantieren, dass ich das optimale
Ergebnis finde, dann kann ich zum Beispiel ein einfaches Distanzmaß
nehmen.
Also statt Mahanalobes Distanz nehme ich Euclidische Distanz, nehme
ich Cityblockmetrik.
Schneller auszurechnen als zum Beispiel eine Mahanalobes Distanz.
Gibt aber auch noch eine Möglichkeit, wie ich beschleunigen kann, bei
garantiert korrektem Ergebnis.
Und das ist etwas, das werden wir auch, wenn man Gaussglocken oder
Gaussmixturen auswertet, gebrauchen können.
Das ist dieses Prinzip der Early Abortion.
Ich muss ja immer Distanzen ausrechnen.
Distanz zwischen meinem X und einem Referenzvektor.
Und wenn man sich die Distanzberechnung anschaut, zum Beispiel
Euclidische Norm, dann habe ich da immer eine Summe, wo ich über alle
Dimensionen gehe.
Und je mehr bei jeder neuen Dimension in meiner Summe, wird die
Distanz, die ich ausgerechnet habe, immer garantiert größer.
Wenn ich jetzt schon ein paar ausprobiert habe, dann habe ich schon
mal irgendeinen Vektor, der relativ nah dran liegt.
Ich habe irgendeinen Vektor, der unter allen Vektoren, die ich bisher
betrachtet habe, am nächsten dran liegt.
Und jetzt rechne ich die Distanz zu einem neuen Vektor aus.
Und ich gehe wieder über die Dimensionen rüber.
Erste Dimension, zweite Dimension, dritte Dimension.
Und dann kann es passieren, dass es zum Beispiel nach der hälften
Dimension die aufakkumulierte Distanz schon größer ist, als die
nächste Distanz von irgendeinem anderen Vektor, den ich schon
vollständig ausgerechnet habe.
Dann wäre ich ja blöd, jetzt noch weiter die Distanz genau
auszurechnen, weil ich weiß ja jetzt schon, dass sie nicht mehr
kleiner werden kann, als das, was ich bisher schon optimal gefunden
habe.
Und wenn mich nur der nächst Drangelegene interessiert, dann ist mir
das völlig egal, wie genau die Distanz von allen anderen zu dem ist.
Mich interessiert nur, dass ich den Nächsten gefunden habe.
Das heißt, an der Stelle kann man dann schon diese Distanzberechnung
abbrechen.
Nennt sich Early Abortion.
Das ist ein einfaches Verfahren.
Da braucht man jetzt nicht lange drüber nachzudenken, um auf die Idee
zu kommen.
Es gibt aber noch andere, kompliziertere Verfahren.
Man kann zum Beispiel anfangen, sich den Merkmalsraum und die
Referenzvektoren, die man hat, in einer Art Baumstruktur zu
definieren.
Und dann muss man, wenn man das geschickt macht und dann diese Ebenen
geschickt darstellt, dann muss man in jedem Knoten, macht man so eine
Frage, ist das aktuelle X, das ich suche, ist das links von einer
bestimmten Halbebene oder rechts von einer bestimmten Halbebene?
Ja, dann geh in den einen Zweig.
Nein, geh in den anderen Zweig.
Und wenn man das geschickt macht, kann man durch relativ wenig
Vergleiche auch dazu kommen, dass man den nächsten Vektor findet.
Wenn man Pech hat und der Raum nicht gut strukturiert ist, dann
braucht man am Ende genauso viel Rechenzeit, als wenn man das nicht
gemacht hätte.
Aber häufig hat man Glück, dass dann so ein Baum, wenn man den
geschickt aufbaut, so gestaltet ist, dass er schneller ist.
Was ist noch ein Problem bei der Early Abortion?
Bei dem ich aufpassen muss, dass ich nicht in die Falle reinlaufe,
dass ich am Ende nicht nur nicht garantieren kann, dass ich keine
Beschleunigung habe, sondern wo es sogar sein kann, dass das Ding
langsamer läuft, als wenn ich alles ausgerechnet hätte.
Wo ist da die kleine Denkfalle, auf die man aufpassen muss?
Wo handelt man sich da extra Rechenzeit ein?
Wenn ich sage, also okay, sobald ich merke, dass meine kumulierte
Distanz größer ist als die bisherige minimale Distanz, die ich schon
habe für irgendeinen Vektor, dann höre ich auf.
Da muss ich eine IF-Abfrage machen, da muss ich einen Vergleich
machen, da muss ich immer überprüfen, ist das denn jetzt schon ein
Fall, wo ich eine Early Abortion mache.
Und das kostet natürlich auch Rechenzeit.
Da muss ein Vergleich gemacht werden, da muss eine IF-Abfrage, ein
konditionaler Sprung im Quellcode gemacht werden, das kostet auch
Rechenzeit.
Und da muss man halt aufpassen, wenn man Pech hat und es ganz dumm
läuft und der man sozusagen die Vektoren in der Reihenfolge, in der
aufsteigenden Reihenfolge ihrer Distanz durchprobiert.
Wenn also der erste Vektor, den ich aus Versehen durchprobiere,
derjenige ist, der am weitesten wegliegt und der zweite Vektor,
derjenige ist, der am zweitweitesten wegliegt, dann werde ich nie ein
Early Abortion machen können, weil ich werde immer, der nächste ist
immer schon näher dran als der vorhergehende, plus ich mache auch noch
immer diese blöden Abfragen, die ich da habe.
Das heißt, ich rechne wirklich alle Distanzen aus, plus ich habe noch
den Overhead, den ich durch diese Abfragen habe.
Das ist dann wieder, dann ist es ganz dumm gelaufen, dass ich zum
Beispiel dann noch mehr Rechenzeit, viel mehr Rechenzeit benötige, als
ich eigentlich mit dem naiven Algorithmus benötige.
Und was man deshalb da häufig macht ist, bei diesem Early Abortion,
dass man zum Beispiel nicht nach jeder Dimension überprüft, mache ich
jetzt einen Abort, sondern dass man sagt, okay, vielleicht immer vier
aufsummieren und danach überprüfe ich mal, ob ich es sein lasse oder
nicht.
Und das muss man halt dann ausprobieren auf den Daten, die man jeweils
hat, wie die so typisch organisiert sind, was da das Schnellste am
Ende ist.
Hier ist nochmal die Idee dahinter, hinter dieser Baumorganisation.
Also angenommen, ich möchte zu einem X halt finden, den
nächstgelegenen Vektor.
Was man da häufig macht, ist die Idee, dass man sich anguckt, die
Varianz der Daten, und man guckt, in welche Richtung ist die höchste
Varianz, und in der Richtung spalte ich dann auf.
Und so spalte ich meinen Merkmalsraum immer weiter auf und bekomme
sozusagen solche Halbebenen, in denen Daten dann drin liegen.
Und kann dann entsprechend an jedem Knoten immer noch fragen, will ich
nach links oder nach rechts, so lange, bis ich die gewünschte Anzahl
an Blattknoten gefunden habe.
Und dann brauche ich nur noch in diesem Unterraum nach dem
nächstgelegenen Vektor zu suchen.
Und da kann man jetzt eine kleine Denkaufgabe machen, was das Ganze
vielleicht mit Gauss-Mixtur-Verteilungen zu tun haben könnte.
Wir hatten ja bei Gauss-Mixtur-Verteilungen das Problem, dass wir
diesen Trick mit logarithmieren nicht direkt anwenden können, weil
einen Logarithmus von einer Summe kann ich nicht ausrechnen.
Da komme ich nicht durch.
Aber angenommen, wir wollen jetzt, dass das Ergebnis, das herauskommt
bei der Auswertung der Gauss-Mixtur, nicht mehr exakt ist.
Und dass auch das Ergebnis, das rauskommt bei dem Logarithmus von der
Gauss -Mixtur, soll nicht mehr exakt sein.
Was könnte man jetzt machen, um die Auswertung der Beschleunigung von
so einer Gauss-Mixtur zu beschleunigen, wenn ich diese beiden
Werkzeuge, diese Early Abortion und zum Beispiel so eine
Strukturierung im Baum als Werkzeuge habe?
Was könnte ich da machen, um jetzt die Auswertung der Gauss-Mixtur
vielleicht zu beschleunigen, wenn ich jetzt den Logarithmus einer
Gauss -Mixtur ausrechnen will?
Wie könnte ich das machen?
Da mal so zwei, drei Minuten, vier Minuten Zeit, immer in
Zweiergruppen und mal drüber nachdenken.
Und was kann man machen?
Was ist denn jetzt das Analogon bei Gauss-Mixturen zu
Referenzvektoren?
Und was kann man damit machen, wenn man jetzt nicht mehr
hundertprozentig exakt rechnen will?
Wie gesagt, immer daran denken.
Man kann diesen Logarithmus und Summe, das kann man nicht knacken.
Den Logarithmus kriegt man nicht in die Summe rein, da muss man sich
jetzt irgendwas überlegen, wie man da drumherum kommt.
Dass man sich davon verabschieden muss, von dieser Summe.
Und da muss man eventuell eine etwas radikale Entscheidung treffen,
die dann zwar zu Fehlern führen wird, aber trotzdem noch
funktionieren, noch ein brauchbares, angenähertes Ergebnis finden
könnte.
Das ist der erste Hinweis.
Angenommen, diese unterschiedlich gefärbten Gauss-Glocken sollen die
Gauss -Glocken in dieser Mixtur repräsentieren, die aufsummiert
werden.
Wenn Sie sich überlegen, das hier ist jetzt eindimensionaler
Merkmalsraum, in Wirklichkeit haben Sie einen 42-dimensionalen
Vektorraum mit 16.000 Klassen.
Werden die Gauss-Glocken Ihrer Meinung nach eher so liegen, oder
werden die vielleicht eher so liegen?
Und was kann man ruhigensgewissens machen, wenn die Gauss-Glocken
vielleicht eher so liegen, als wenn sie so liegen in der Realität?
Ich kann ja zum Beispiel mal sagen, das hier sei das X, das ich
ausrechnen will.
Das liege da.
Dafür will ich die Gauss-Mixtur, die zusammengemischt wird,
ausrechnen.
Was sagt uns dieses kleine Bildchen denn?
Also viele Klassen, hohe Dimensionalitäten und die Wahrscheinlichkeit,
dass die Sachen sich dann alle da an einem Punkt zusammen tummeln, ist
eher unwahrscheinlich.
Eher wird es so sein, dass diese Gauss-Glocken relativ weit,
verhältnismäßig weit auseinanderliegen.
Das heißt, die, das ist jetzt mal extrem gezeichnet, die überlappen
sich nur wenig oder sehr viel.
Und angenommen, das sei jetzt eine Gauss-Mixtur, und Sie wollen jetzt
den Wert der Gauss-Mixtur für dieses X ausrechnen.
Was ist da wichtig und was ist anscheinend jetzt nicht so wichtig?
Naja, wichtig wird ja scheinbar der Wert dieser gelben Gauss-Glocke zu
sein.
Das scheint ja schon mal relativ wichtig zu sein.
Scheint relativ großen Wert in der Summe zu haben.
Wie sieht es mit dieser roten Gauss-Glocke aus?
Wie viel Beitrag wird die zu der Summe liefern, wenn ich das für das X
da ausrechne?
Sehr nah an Null.
Selbst wenn das Ding ein ganz, ganz, ganz, ganz großes Gewicht kriegen
würde, was sehr unwahrscheinlich ist.
Die Gewichte sind meistens relativ ähnlich.
Da kommt, de facto wird da Null drauf addiert.
Und selbst bei der grünen, der Anteil dieser grünen Gauss-Glocke wird
auch relativ klein sein.
Das heißt, der Wert von dieser grünen Glocke, der hat, die hat einen
Wert bei X.
Der ist irgendwie leicht, ganz klein über Null.
Und die rote Glocke hat auch einen Wert bei X.
Aber da werden ganz kleine Zahlen drauf addiert auf diesen Wert.
Das heißt, wenn ich wüsste, dass das X doch so schön nah an dieser
gelben Gauss-Glocke liegt, dann bräuchte ich nur den Wert der gelben
Gauss -Glocke auszurechnen.
Und den restlichen Werte, die würde ich einfach sagen, ok, nehmen wir
mal an, die seien Null.
Und wenn ich dann den Logarithmus ausrechne, dann habe ich die Summe
los.
Dann habe ich plötzlich nur noch einen Wert in der Summe.
Was muss ich jetzt machen?
Ich muss jetzt also rausfinden, welches ist die Gauss-Glocke, die am
nächsten dran liegt.
Und da könnte man natürlich jetzt ankommen, ja, da muss ich ja wieder
den Wert der Gauss-Glocke ausrechnen, damit ich weiß, welche Gauss
-Glocke den höchsten Wert hat.
Da muss ich ja E-Funktionen ausrechnen.
Muss ich nicht.
Was ich da machen muss?
Ich muss halt eine Distanz ausrechnen.
Und zwar welche Distanz?
Eine Euclidische Distanz?
Eine City-Block-Metrik?
Eine Mahana-Lobis-Distanz.
Das ist es nämlich gerade.
Die Gauss-Glocke, die am nächsten dran liegt, das ist die Gauss
-Glocke, die die geringste Mahana-Lobis-Distanz zu dem Mittelwert hat.
Das heißt, wenn ich für dieses X wissen will, welche Gauss-Glocke
liegt am nächsten dran, dann muss ich einfach nur die Mahana-Lobis
-Distanz ausrechnen.
Das heißt, ich muss nur den Exponenten ausrechnen.
Ich muss die E-Funktion nicht anfassen.
Nur dadurch, dass ich mir überlege, für welche der Gauss-Glocken habe
ich oben die kleinste Mahana-Lobis-Distanz, finde ich die Gauss
-Glocke, die am nächsten dran liegt.
Habe ich die E-Funktion nicht angefasst.
Das ist nochmal schneller, als wenn ich eine E-Funktion ausrechnen
muss.
Und was mache ich jetzt, wenn ich die Mahana-Lobis-Distanz ausrechne?
Das ist, ich quantisiere.
Letztendlich ist das nichts anderes, dass ich das X quantisiere auf
die Quantisierungsstufe, die halt durch die nächstgelegene Gauss
-Glocke drangegeben ist.
Und da ist halt meine Distanz eine Mahana-Lobis-Distanz.
Das ist eine Quantisierung.
Was mache ich also, wenn ich jetzt da die nächstgelegene Gauss-Glocke
suche?
Welche Technik werde ich sofort anwenden, wenn ich das mache?
Early Abortion.
Sehe ich halt dazu, dass ich eine Early Abortion mache.
Das heißt, ich habe hier kombiniert die Early Abortion mit einer
Technik, die mir eine Beschleunigung in der Regel garantiert, aber
halt nicht mehr garantiert, dass ich das 100% korrekte Ergebnis habe.
Und wie groß der Fehler ist, das hängt halt davon ab, wie stark die
Gauss -Glocken miteinander überlappen und wo jetzt dieses X gerade
liegt.
Und das ist etwas, das wird durchaus gemacht, wenn Sie sich heutzutage
noch, inzwischen werden es immer weniger, aber Spracherkenner
anschauen, die Gauss-Mixtur-Modelle verwenden hinterher, um
Wahrscheinlichkeiten auszuführen, dann ist das genau das Gleiche.
Wenn Sie jetzt im Praktikum sitzen, dann werden Sie davon in einer
gewissen Art und Weise verschont.
Wenn Sie da mit dem Spracherkenner arbeiten, da gibt es irgendwie dann
so ein Codebook und eine Distribution, da können Sie halt Gauss-Mixtur
-Modelle mit ausrechnen und hinterher, wenn der Spracherkenner was
erkennt, dann werden Sie ihm einfach sagen, hier erkennen wir das und
der muss dann ganz viele so Gauss-Mixtur-Modelle ausrechnen, aber der
macht genau das.
Die Standardfunktion, die da verwendet wird, damit es in erträglicher
Zeit läuft, macht eben genau das, dass es nur die nächstgelegene Gauss
-Glocke nimmt und dann noch eine Early Abortion macht bei der
Distanzberechnung.
Das einfach nur, das was wir machen, ist nicht nur theoretisch schön,
wir verwenden es tatsächlich.
Okay, das hatten wir schon eigentlich gemacht.
Uns interessiert noch als letztes das Finden der Referenzvektoren.
Die erste Idee wäre ja, man macht das wie bei der Quantisierung eines
analogen Signals, dass man den Merkmalsraum in gleich verteilte
Kästchen unterteilt und dann da in die Mitte eines jeden Kästchens ein
Referenzvektor liegt.
Wenn natürlich meine Daten so wie da dann hinterher strukturiert sind,
dann gibt es ganz viele Kästchen, wo nur sehr selten bis nie überhaupt
irgendein Wert reinfallen wird und dafür gibt es viele andere Werte,
die ich halt schlecht auflöse, weil sie nah beieinander liegen.
Wäre ja dann sinnvoller, dass wenn man in dicht besiedelte Regionen,
also da, wo häufig Merkmalsvektoren daraus erscheinen, mehr
Referenzvektoren macht, also mehr Quantisierungsstufen reinlegt, als
in solche dünn besiedelten Regionen, wo nur noch sehr selten ein x
quantisiert werden soll.
Und eine Möglichkeit das zu machen, bietet zum Beispiel der k
-Mittelwerte -Algorithmus.
Der k-Mittelwerte-Algorithmus ist ein überwachter Algorithmus.
In dem Sinne, dass...
Jetzt muss ich sagen gleich, wieso, k-Mittelwerte ist doch
unüberwacht.
Ja, aber jetzt, wenn wir damit Referenzvektoren wissen wollen, dann
brauchen wir folgende Überwachung.
Angenommen, ich habe Trainingsdaten und angenommen, ich weiß, welches
Trainingsdatum auf welche Quantisierungsstufe soll.
Jetzt hätte ich gerne den Referenzvektor für diese
Quantisierungsstufe.
Dann ist die Überwachung, dass ich weiß, für jede Quantisierungsstufe
diese Vektoren gehören dazu.
Und das werfe ich jetzt in k-Mittelwerte rein.
Was macht k-Mittelwerte?
Bei k-Mittelwerte sage ich, hier Menge von Daten, finde mir mal k
-Werte, die diese Daten irgendwie repräsentieren.
Und ich gebe das k fest vor.
Und das ist k-Mittelwerte, ist dann ein iterativer Algorithmus.
Ich nehme also meine Datenwolke, für die ich k-Repräsentanten suche
und lege erstmal zufällig Repräsentanten da rein.
Kann ich auch gleichverteilt da rein tun.
Dann mache ich einen Klassifikationsschritt.
Ich gucke jetzt mal die Trainingsdaten, die ich habe, zu welchem der k
-Repräsentanten, die ich da irgendwie zufällig gleichverteilt, sonst
wie reingelegt habe, zu welchem fallen die denn dazu.
Dann zerfällt also diese Trainingsmenge in k-Cluster.
Und für jedes dieser k-Cluster berechne ich jetzt den neuen
Mittelwert.
Was wäre der neue Mittelwert innerhalb dieses Clusters?
Das heißt, der ursprüngliche Referenzvektor, gegen den ich verglichen
habe, der wird verschoben.
Und dann fange ich das Spielchen wieder von vorne an.
Ich habe jetzt wieder neue k-Referenzvektoren, mache wieder einen
Klassifikationsschritt für alle Daten, wieder ihrem nächstgelegenen
Referenzvektor zuordnen.
Wieder zerfällt das alles in k-Cluster, ich rechne wieder die
Mittelwerte neu aus und so verschiebt sich das.
Und das iteriere ich so lange, bis ich halt irgendeine
Abbruchbedingung erreiche.
Zum Beispiel, ich will nur tausendmal iterieren.
Oder die Distanz, die ein Wert hat zu seinem Referenzvektor, fällt
unter einem Schwellwert.
Oder ich merke, dass die Referenzvektoren sich entweder überhaupt
nicht mehr verändern oder dass sie sich nicht mehr signifikant
verändern.
Das wären alles so mögliche Abbruchbedingungen.
Und auf diese Art und Weise kann ich mir also in so eine Wolke k
-Repräsentanten reintun.
Und letztendlich genau das macht auch dieses Learning Vector
Quantization.
Da weiß ich eben gerade, ich habe Trainingsdaten, die fallen auf eine
bestimmte Quantisierungsstufe und innerhalb dieser Quantisierungsstufe
suche ich halt k-Referenzvektoren und dann mache ich das im Prinzip so
ähnlich.
Bei k-Mittelwerte bestimme ich, nachdem ich den Klassifikationsschritt
gemacht habe, immer den echten Mittelwert dieses Clusters.
Bei Learning Vector Quantization ersetze ich das durch, ich bestimme
nicht den echten Mittelwert, sondern ich schiebe den Mittelwertvektor
so ein bisschen in die Richtung der Daten, die zu ihm gehören.
Und da macht man das bei Learning Vector Quantization eben so, dass
man die Trainingsdaten einzeln abarbeitet.
Erstes Trainingsdatum rein, klassifizieren, schauen, auf welchen
Referenzvektor fällt es und der Referenzvektor, der wird dann so ein
bisschen in die richtige Richtung geschoben.
Und alle anderen Referenzvektoren, die nicht am nächsten lagen, die
werden von diesem einen bis in Trainingsdatum eben ein bisschen
entweggeschoben.
Und dieses ein bisschen wegschieben, ein bisschen hinschieben, das ist
halt ein Parameter, den ich irgendwie von Hand bestimmen muss, den ich
als Mensch vorgeben muss, als Algorithmendesigner, um wie viel denn
der geschoben werden will.
Muss ich halt ausprobieren.
Und dann ist halt die Idee, dass man dieses um wie viel man
verschiebt, kann man zum Beispiel so sagen, dass man am Anfang halt
sehr viel verschiebt und im Laufe der Zeit halt immer weniger
verschiebt, weil man damit so im Kopf hat, dass sich das irgendwie
langsam einpegelt und einpendelt und langsam setzt diese
Referenzvektoren, dass sie sich irgendwie stabilisieren über die Zeit.
Davon kann man jetzt, da gibt es zig verschiedene Unterversionen, man
kann jetzt zum Beispiel sagen, dass ich nur neue Referenzvektoren
bestimme, wenn irgendwie die Klassen unterschiedlich sind.
Also angenommen, ich habe zwei Referenzvektoren, die beiden am
nächsten gelegenen an diesem Trainingsdatum, X, Y, seinen VJ und VK.
Und wenn die zu unterschiedlichen Klassen gehören, dann besteht da
sozusagen die Gefahr, dass falsch klassifiziert wird X, Y und dann
verschiebe ich die VJ und die VK.
Und wenn das nicht der Fall ist, wenn also die zwei nächstgelegenen
Referenzvektoren auch noch die richtige Klasse sind, dann ist das gut
so, dann lasse ich die so liegen.
Und dann können wir noch die Nebenbedingungen machen, ja, aber ich
verschiebe auch nur dann, wenn das X, Y irgendwie zwischen diesen
beiden Vektoren liegt.
Also bildlich gesprochen,
sei das hier X und das hier sei VI und VJ, dann liegt das X irgendwie
dazwischen, dann verschiebe ich es noch.
Wenn die Situation mehr so wäre, dann liegt das X nicht zwischen
diesen beiden Vektoren, dann lasse ich es ja auch in Ruhe.
Nennt sich dann LVQ2.
Dann kann man LVQ3 machen, macht man den Update auch, wenn die Klassen
gleich sind.
Dann gibt es LKVQ2.1, LVQ3.2 und so weiter und so fort.
Alles im Prinzip nur Spielereien und Heuristiken darüber, wann es
sinnvoll ist, diese Referenzvektoren hin und her zu schieben.
Und das wirklich Schöne ist, dass man dann das Ganze auch noch in ein
neuronales Netz gießen kann.
Wer also in der Vorlesung Neuronetze war, der durfte sich das alles in
Ausführlichkeit anhören.
Ich persönlich finde das nicht ein besonders spannendes Thema, aber
ist ganz nett.
Man kann das Ganze in ein schönes, simples neuronales Netz gießen,
indem man das wie folgt kodiert.
Ich habe einen Eingabevektor, der sei D-dimensional.
Das ist also mein Merkmalsraum.
Ich bekomme Trainingsdaten, die sind D langer Vektor.
Die Eingangsneuronen entsprechen halt gerade diesem D-dimensionalen
Eingangsvektor.
Ich habe Referenzvektoren, M Stück davon.
Die seien durchnummeriert von 1 bis M.
Dann steht jedes Ausgabeneuron für den Index des Referenzvektors, auf
den eine Eingabe dann hinterher abgebildet werden soll.
Und dann muss ich ja irgendwie noch die Referenzvektoren mit ihrer
Lage im Raum kodieren.
Das kodiere ich in den Gewichten, die an den Verbindungen zwischen der
Eingabedimension und dem jeweiligen Referenzvektor sind.
Hier ist das mal aufgetragen, beispielsweise die Verbindung für den
Referenzvektor mit dem Index j, also dem Vektor vj, für so eine
Eingabe x1 bis xd.
Und dieser Vektor vj, der ist auch wieder D-dimensional, der hat halt
entsprechend D-Gewichte, sind über j nochmal indiziert und hat dann D
-Gewichte wie 1 bis wn.
Und das soll halt der eigentliche Referenzvektor sein.
Die ganze Magie besteht dann darin, wie ich jetzt die Ausgabe, die
Aktivierung dieses Ausgabeneurons berechne.
Und hier in dieser Recheneinheit, da mache ich halt nicht so ein
Standardperzeptron, sondern was ich da ausrechnen lasse, ist eine
Distanzfunktion.
Da lasse ich einfach hier ausrechnen, was ist denn die Distanz
zwischen diesem Eingabevektor und dem Gewichtsvektor, der den
Eingabevektor mit der j-Ausgabe berechnet.
Und das lasse ich für alle m-Referenzvektoren machen und dann weiß
ich, wie weit jeder Referenzvektor wegliegt von dem Eingabevektor.
Dann kann ich entsprechend mir den nächsten oder die zwei nächsten
Referenzvektoren raussuchen und kann dann die Gewichte anpassen.
Indem ich die Gewichte halt entweder wegschiebe von x oder ein
bisschen in die Richtung von x schiebe oder die gesamten Sachen von
LVQ da durchprobiere und durchmache.
Und damit habe ich Learning Vector Quantization, das Finden dieser
Referenzvektoren, als ein Problem formuliert, wo ich Gewichte in einem
neuronalen Netz lerne.
Und wenn ich dann hinterher quantisieren will, dann nehme ich halt die
Eingabe her, stecke die in das neuronale Netz rein, gucke bei der
Ausgabeschicht, welcher Vektor ist denn derjenige, der am nächsten
dran liegt.
Und da muss ich dann auch wieder geschickt sein, dass ich nicht stur
einfach das neuronale Netz ausrechne, sondern dass ich da zum Beispiel
auch, wenn ich die einzelnen Neuronen der Reihe nach ausrechne, zum
Beispiel mit Early Abortion arbeite.
Damit ich nicht Sachen ausrechne, die mich eigentlich nicht
interessieren.
Heutzutage ist das manchmal gar nicht mehr so interessant, weil man
jetzt, wenn man so GPUs verwendet, das sind letztendlich auch nichts
anderes als Vektorrechner, was man früher so als Riesenschrank im
Rechenzentrum stehen hatte, halt jetzt auf einen kleinen Chip
gegossen, ursprünglich für Grafikkarten, deswegen Graphical Processing
Units, weil da halt viel lineare Algebra gemacht werden muss, also
sprich viele Matrizen mit Vektor multiplizieren und solche Sachen.
Und da kann man das halt schön parallelisieren, dass man sozusagen
diese M-Referenzvektoren und die Matrixmultiplikation oder was auch
immer man da ausrechnen muss, halt parallel auf so einer GPU in 1024
parallelen Pipelines ablaufen lässt.
Da hat man dann eine Hardwarebeschleunigung, indem man da in der
Hardware parallel rechnet.
Gut, das soll's gewesen sein zur Vektorquantisierung.
Nächste Woche fangen wir dann an und machen jetzt den Schritt hin mit
den Werkzeugen hin zur eigentlichen statistischen Spracherkennung.
Lösen uns dann also von diesem Mustervergleich und gucken, welches
Muster ist wo am nächsten dran und so weiter und so fort, sondern
machen dann den Schritt, den letztendlichen Schritt von der Manalobes
-Distanz hin zum eigentlichen, richtigen, echten Ausrechnen von Wahrscheinlichkeiten.