Dann machen wir mal weiter da, wo wir letztes Mal aufgehört haben.
Also wir widmen uns jetzt dem letzten großen Thema der Vorlesung, das
da lautet Suche.
Letztes Mal aufgelegt hatte ich schon die Literaturempfehlung,
trotzdem noch mal wärmstens ans Herz gelegt.
Es gibt einmal die Kapitel 12 und 13 in dem Spoken Language Processing
Buch.
Das ist dieser dicke Wälzer, in dem alles Mögliche zum Thema
Sprachverarbeitung drinsteht und sehr viel zum Thema Spracherkennung.
Und ich orientiere mich auch so ein bisschen an dieser Aufteilung
dieser beiden Kapitel 12 und 13 in der Vorlesung selber.
Dann gibt es einen interessanten Konferenzartikel noch, der
beschreibt, wie das Spracherkennungssystem funktioniert, das wir
verwenden.
Das war auch noch mal ans Herz gelegt.
Und wir gehen jetzt halt so vor, dass wir uns Suche in zwei Schritten
anschauen.
Der erste Teil ist der, dass wir uns erstmal nur grundlegende
Begrifflichkeiten aneignen zum Thema Suche, so grundlegendes
Handwerkszeug und dann auch so grundlegende Aspekte, die interessant
sind für den Bereich der Spracherkennung.
Und dann im nächsten Schritt gehen wir dazu über, dass wir uns
schauen, wie wir dann die Suche so optimieren und umformulieren
können, dass wir effizient Suche in der Spracherkennung durchführen
können.
Nochmal als Erinnerung, wo wir uns befinden.
Wenn wir uns die Fundamentalformel der Spracherkennung anschauen, dann
kümmern wir uns jetzt um diesen Teil der Formel, dieses Argument
Maximum über alle möglichen Wortsequenzen.
Wir können das akustische Modell berechnen, wir können das
Sprachmodell berechnen, wir können den Merkmalsvektor X extrahieren
und müssen uns jetzt darum kümmern, dass wir dann ein W-Dach finden,
sodass das Produkt dieser beiden Wahrscheinlichkeiten, der akustischen
Modellwahrscheinlichkeit und der Sprachmodellwahrscheinlichkeit
maximiert wird.
Und es ist leicht einsehbar, der naive Ansatz, dass ich gehe halt alle
möglichen Wortfolgen, die es gibt, der Reihe nach durch, rechne das
Produkt aus, entscheide mich dann für die Wortfolge, wo das Produkt
maximal wird.
Der Ansatz funktioniert natürlich nicht, weil es einfach viel zu viele
mögliche Wortfolgen gibt.
Wenn wir uns die Menge aller möglichen Wortfolgen anschauen, dann
nennen wir das Ganze den Suchraum.
Wir sprechen dann von dem Suchraum und dann ein Algorithmus, der in
diesem Suchraum aller möglichen Wortfolgen entweder die optimale
findet oder zumindest eine relativ gute, eine hinreichend gute, so
einen Algorithmus nennen wir dann die Suche oder manchmal sprechen wir
auch dann von dem Decoder.
Bei der Einzelworterkennung ist das im Prinzip erstmal noch relativ
leicht.
Wenn wir das Sprachmodell außer Acht lassen und nur mit HMMs
Einzelworterkennung betreiben, dann können wir mit dem Forward
-Backward -Algorithmus für jedes Wort die akustische
Modellwahrscheinlichkeit ausrechnen und uns dann für das Maximum
entscheiden.
Wenn wir da jetzt Geschwindigkeit schon rausquetschen wollen, also
wenn wir nicht mehr sagen wollen, wir wollen alle Wörter der Reihe
nach durchprobieren, dann kann man sich das so vorstellen, dass man
sich ein neues HMM baut, das besteht aus allen Mörtern parallel, wobei
man da dann Anfänge, die gleich sind, zusammenfassen kann, sodass man
gleiche Phonemenpräfixe, gleiche Zustandspräfixe zusammenfassen kann.
Da hat man so eine Art Baum, den man bekommt und dann rechne ich nicht
ein, kann ich, habe ich schon ein bisschen Zeit gespart, wenn ich das
so baumartig strukturieren, dann kann ich über diesen neuen HMM wieder
ein Forward, kann ich, hilft mir ja nicht, wenn ich ein Forward
-Backward -Algorithmus durchsuche, weil dann ich nicht mehr in der
Lage bin zu entscheiden, welches Wort war es denn.
Aber dann kann ich zum Beispiel sowas machen, dass ich eine Viterbi
-Suche mache, dass ich mir dann die wahrscheinlichste Zustandsfolge
raussuche und überlege, gut, die wahrscheinlichste Zustandsfolge, das
ist zwar nicht dasselbe wie die wahrscheinlichste Wortfolge, aber
wahrscheinlich ist es ja so, dass die wahrscheinlichste Zustandsfolge
auch der wahrscheinlichsten Wortfolge dann entsprechen wird oder dass
in der wahrscheinlichsten Wortfolge auch die wahrscheinlichste
Zustandsfolge enthalten sein wird.
Und dann kann ich das Ganze noch mit optimieren, mithilfe von
Strahlsuche, dass ich also nicht immer die volle DP-Matrix, diese
volle Matrix beim dynamischen Programmieren ausrechne, sondern nur die
Sachen ausrechnen, die innerhalb eines gewissen Strahles sind, das
also nicht schlechter ist, zehn Prozent schlechter, 15 Prozent
schlechter, N Prozent schlechter als der aktuell beste Pfad, den ich
bisher expandiert habe.
In der kontinuierlichen Spracherkennung funktioniert das einfach nicht
mehr, weil dann, wenn ich jetzt noch beliebig lange, beliebige
Kombinationen von Wörtern aus einem großen Vokabular hernehme, ich so
einen riesigen Zustandsgrafen bekomme, dass ich dann da ein bisschen
in Laufzeitprobleme komme.
Wir können uns ein bisschen erinnern, wie das beim DTW und beim One
-Stage -Dynamic-Programming waren.
Da hatten wir auf der einen Seite die Zeitachsen, auf der Zeitachsen,
die in der Zeit geworbt wurden, um für unterschiedliche
Sprechgeschwindigkeiten zu kompensieren.
Und man hatte sich dann immer entschieden für die Wortfolge, für das
Wort, wo der Pfad mit der kleinsten Distanz gefunden wurde.
Und bei kontinuierlicher Sprache hatte man halt dieses One-Stage
-Dynamic - Programming, wo man dann auch immer diese Pfade
ausgerechnet hat und sich dann auch jeweils für den Pfad mit der
kleinsten Distanz entschieden hat.
Beim One-Stage-Dynamic-Programming, durch dieses Time Warping, hatte
man hinterher letztendlich eine, sich entschieden für eine Abbildung
von Referenzvektoren zu Aufnahmevektoren, sodass man so eine
eindeutige Abbildung hinterher hatte, die dann, wo man dann den
kürzesten Pfad genommen hat.
Bei den HMMs für das akustische Modell hat man diese Eindeutigkeit
halt nicht mehr.
Man weiß dann nicht mehr oder man entscheidet sich im Prinzip erst mal
nicht mehr dafür, zu welchem Zeitpunkt war ich in welchem Vornehmen,
zu welchem Zeitpunkt war ich in welchem HMM-Zustand, sondern ich
rechne zum Beispiel durch den Vorwartalgorithmus alle Möglichkeiten
durch, dass ich zu jedem möglichen Zeitpunkt, was ist, wenn ich in dem
Zustand gewesen wäre, mit welcher Wahrscheinlichkeit würde dann
entsprechend dieses Wort produziert worden sein.
Und das Ganze, dieses Konzept der Distanzen im Dynamic Programming,
wird halt ersetzt durch das Konzept der Wahrscheinlichkeiten bei den
HMMs.
Und obendrauf kommt dann hinterher noch die Sprachwahrscheinlichkeit,
die Sprachmodellwahrscheinlichkeit, die man zum Beispiel durch n-Gamma
ausrechnet und das ersetzt dieses Konzept zum Beispiel der gültigen
Vorgängerlisten, wie man es beim One-Stage Dynamic Programming hatte.
Wenn man sich jetzt Suche im Allgemeinen anschaut, da gibt es da ein
Paradigma, das man relativ häufig verwendet, um Suche zu beschreiben.
Das ist dieses sogenannte Zustandsraum-Suche-Paradigma.
Suche wird im Prinzip als die Suche durch einen Graphen definiert.
Man hat eine Menge von einem oder mehreren Startzuständen, man hat
eine Menge von einem oder mehreren Zielzuständen und man hat eine
Regel, eine Menge von Regeln von Operationsregeln, mit deren Hilfe ich
von Zuständen aus in neue Zustände kommen kann.
Die definieren mir, welche Übergänge zwischen Zuständen sind denn im
Prinzip möglich und jeden Zustandsübergang, den ich mache, verbinde
ich mit Kosten.
Zum Beispiel mit Wahrscheinlichkeiten dafür, wie wahrscheinlich es
war, jetzt folgenden Merkmalsvektor zu emittieren oder wie
wahrscheinlich es war, dass ich jetzt folgenden N-Gramm
-Wahrscheinlichkeit darauf multiplizieren muss.
Und im Prinzip in der Suche ist es erstmal allgemein so, dass man
erstmal einen Pfad sucht von einem beliebigen Startzustand zu einem
beliebigen Zivilzustand und dieser Pfad soll die minimalen Kosten
haben oder auch alternativ die maximalen Kosten.
Man kann durch einfache Umformung immer zwischen minimalen und
maximalen Kosten Problem, Suchproblem hin und her wechseln.
Bei uns insbesondere ist es so, dass wir letztendlich meistens nur
einen gültigen Startzustand haben und einen gültigen Endzustand.
Wir strecken das Problem soweit ein, dass wir so tun, dass würde am
Anfang jeder Wortfolge immer ein virtuelles Wortfolge Startes Symbol
stehen und am Ende jeder Wortfolge so ein virtuelles Wortfolge Ende
Symbol stehen.
Und jetzt sucht man halt in dem Graphen und bei uns ist es in der
Regel ein Kostenmaximierungsproblem.
Wir suchen ja die wahrscheinlichste Wortfolge.
Jetzt hatten wir das schon gesehen, zum Beispiel bei der akustischen
Modellsuche rechnet man häufig nicht im Wahrscheinlichkeitsraum,
sondern häufig logarithmiert man den Wahrscheinlichkeitsraum und dann
das Negative vom Logarithmus und je nachdem ob man dann negiert oder
nicht den Logarithmus, kommt man dann dazu, wenn man den Logarithmus
negiert, dass man dann zu einem Minimierungskosten,
Minimierungsproblem kommt.
Dass man also die minimalen logarithmierten Wahrscheinlichkeiten
sucht.
Beliebt bei der Suche ist, dass man halt mit Dynamic Programming
arbeitet und mit irgendwelchen Heuristiken.
Dynamisches Programmieren ist halt bei so Grafsuchen relativ häufig
sehr sinnvoll, wie man halt gesehen hat bei Viterbi oder Forward
Algorithmus, weil man halt Zwischenergebnisse zwischenspeichert, die
man dann halt nicht doppelt berechnen muss.
Und je nachdem wie das ist, kann so ein, mithilfe von dynamischer
Programmierung, ein an sich exponentielles Suchproblem, also ein
Suchproblem mit exponentieller Laufzeit in eins mit polynomieller
Laufzeit verwendet werden.
Und der Einsatz von dynamischer Programmierung sorgt dafür, dass wir
auch immer die optimale Lösung finden werden.
Aber das funktioniert leider nicht bei allen Suchproblemen so.
Es gibt immer noch viele Suchprobleme, die immer noch exponentiell in
der Zeit bleiben.
Also alles was NP-hart ist, Handlungsreisenden und andere NP-harte
Probleme können sich nicht oder wir wissen es zumindest noch nicht, ob
man sie in polynomiell Laufzeitprobleme umwandeln kann.
Und da verwendet dann man meistens irgendwelche Heuristiken, also
irgendwelche Annahmen, irgendwelche Vermutungen, irgendwelche Kniffe
und Tricks, die dafür sorgen, dass man die Laufzeit dann unter eine
bestimmte Schranke bringt.
Sorgt dafür, dass man unter Umständen dann nicht mehr die optimale
Lösung findet, sondern nur noch eine gute.
Aber in der Praxis reicht das meistens aus.
Und auch, wenn man jetzt sagen wir mal in der Lage wäre, ein in erster
Linie exponentielles Suchproblem mithilfe dynamischer Programmierung
umzuwandeln in ein polynomielles Suchproblem, kann das in der Praxis
trotzdem noch unschön lange laufen.
Also kann das trotzdem noch sein, dass das so so lange läuft, obwohl
es im O-Kalkül zum Beispiel polynomiell wäre, dass das zu lange läuft,
als dass man es in der Praxis vernünftig anwenden kann und dass man
dann auch für solche Probleme zurückgreifen muss auf die Anwendung
irgendwelcher Heuristiken.
Wenn ich jetzt beschreiben möchte, wie komplex ein Suchproblem ist,
dann gibt es dafür in der Regel zwei Kenngrößen.
Die eine Kenngröße ist die Anzahl der Zustände, die ich im Suchraum
habe.
Also wenn man sich den Suchraum als Graphen vorstellt, je mehr
Zustände ich habe, desto mehr mögliche Lösungen, mögliche Pfade von
Start zu Endzuständen kann ich haben oder muss ich Möglichkeiten muss
ich ausprobieren, um dann hinterher zu dem optimalen Pfad zu bekommen.
Das ist bei der Viterbi-Suche kann man das zum Beispiel schön sehen,
je mehr HMM zuständig habe und je mehr Zeitpunkte ich habe, mehr
Zeitschritte ich habe, desto mehr Zellen habe ich in meiner Matrix und
kann die als so eine Art Suchraum hinterher auch auffassen und desto
größer wird mein Suchraum.
Im Prinzip könnte ich ja zu jedem Zeitpunkt in jedem beliebigen
Zustand sein und müsste dann durch diesen Suchraum herausfinden,
welches ist der Pfad mit der geringsten, mit den geringsten Kosten.
Und das sind halt N mal T viele mögliche Zustände und dann muss ich
Pfade finden durch diesen N mal T großen Suchraum.
Aber das ist halt nicht die ganze Geschichte, weil beim HMM ist es
jetzt so, dass erstmal in der Theorie ich von jedem Zustand in jeden
anderen Zustand könnte übergehen.
In der Praxis haben wir dann gesehen, dass wir das insbesondere auch
zum Beispiel bei der Spracherkennung halt nicht zulassen.
Wir lassen in der Spracherkennung nicht jeden möglichen
Zustandsübergang zu.
Wir lassen zum Beispiel nicht zu, dass wir rückwärts gehen in der
Zeit.
Wir lassen nicht zu, dass wir zu viele Zustände überspringen, sondern
meistens haben wir ja eher so eine lineare, linear fortschreitenden
Topografie über diese HMMs.
Deswegen ist auch noch die Frage wichtig, wie viele Übergänge aus
einem Zustand heraus kann es denn geben.
Wenn ich sehr viele Zustände habe, aber nur ganz wenige mögliche
Übergänge, dann ist das unter Umständen halt nicht so schlimm, nicht
so rechenaufwendig, als wenn ich eher weniger Zustände hätte, aber
dafür ganz viele möglichen Übergänge.
Und damit haben wir also als zweite Kenngröße für die Komplexität
eines Suchproblems den sogenannten Verzweigungsfaktor.
Wie für jeden, für einen Zustand im Durchschnitt, wie viele Nachfolger
müssen wir im Durchschnitt als nächstes betrachten.
Hoher Verzweigungsfaktor, dann entsprechend ein schwieriges Problem.
Einfaches Beispiel ist da halt das Schachspiel.
Ein Zustand ist letztendlich eine mögliche Spielfeldbelegung und dann
habe ich von jeder Spielfeldverlegung ganz viele mögliche neue
Übergänge, die ich machen kann und dementsprechend da auch einen
relativ hohen Verzweigungsfaktor.
Dann kann man sich bei der Suche nach dem kürzesten Pfad generelle
Strategien überlegen.
Die eine Frage lautet zum Beispiel, wo fange ich denn an zu suchen?
Gehe ich von vorne von den Startzuständen los und möchte von den
Startzuständen aus in Richtung der Endzustände nach dem minimalen Pfad
suchen oder will ich vielleicht von hinten anfangen und nach vorne
langsam durchsuchen?
Das sollte ja jetzt erstmal prinzipiell egal sein, aber das hängt halt
unter Umständen von der Struktur des Suchraums an.
Wenn mein Suchraum zum Beispiel so strukturiert ist, dass ich ganz am
Anfang einen sehr hohen Verzweigungsgrad habe und gegen Ende einen
eher geringen Verzweigungsgrad, dann kann es vielleicht durchaus Sinn
machen, dass man erstmal von hinten aus anfängt zu suchen, wenn man
das Ganze zum Beispiel mit sowas wie einer Strahlsuche kombiniert und
mich von hinten nach vorne durch arbeite.
Also wie gesagt, man unterscheidet zwischen der Vorwärtssuche, der
Forward Search und der Backward Search und dann kann man natürlich
beide Sachen noch kombinieren, dass man zum Beispiel sagt, ich fange
sowohl parallel von vorne als auch von hinten an zu suchen und während
ich mich da so durch den Suchraum durchwühle, ist meine Hoffnung, dass
ich mich irgendwann in der Mitte treffe.
Das ist zum Beispiel dann ganz sinnvoll, wenn vorne Verzweigungsgrad
klein ist, hinten Verzweigungsgrad ist klein, aber irgendwo mittendrin
habe ich einen sehr hohen Verzweigungsgrad.
Dumm ist es gelaufen, ist es natürlich, wenn ich mich in der Mitte
nicht mehr treffe.
Dann habe ich sehr viel, unter Umständen sehr viel Rechenzeit
verschwendet.
Aber meistens haben ja die Suchprobleme in der Praxis irgendwie eine
gemeinsame Struktur, die dann entsprechend dafür sorgen, dass wenn
man, dass man da halt so Aussagen drüber treffen kann, ob man sich
dann erwartungsgemäß in der Mitte treffen wird oder nicht.
Eine Frage beschäftigt sich auch damit, wie ich diesen Suchraum im
Rechner darstelle und da unterscheidet man zwischen der expliziten und
der impliziten Darstellung.
Bei der expliziten Darstellung stellt man diesen Suchgraf irgendwie
statisch im Speicher dar.
Zum Beispiel als Tabelle, als mehrdimensionales Array.
Und wenn halt der Suchraum sehr, sehr groß ist, kann das halt sehr,
sehr, sehr unpraktisch werden, dass ich den gesamten Suchraum immer im
Speicher halten muss.
Und wenn ich dann so heuristische Suchen anschaue, die sich gar nicht
den gesamten Suchraum werden anschauen, sondern nur Teile des
Suchraumes durchsuchen werden nach diesem optimalen Pfad, weil ich ja
auch nicht alle möglichen Pfade mehr anschaue, kann es durchaus
sinnvoll sein, dass ich mir dann den Suchraum nur noch implizit
darstelle.
Dass ich nur noch die Suchraumteile im Speicher verfügbar mache, die
ich auch tatsächlich während meiner Suche besuchen will.
So was nennt man dann einen dynamischen Suchgrafen oder eine implizite
Darstellung des Suchraumes.
Und den Suchraum, den man dann hinterher oder die Teile des
Suchraumes, die man dann hinterher tatsächlich besucht bei der Suche
nach diesem kürzesten Pfad, von denen spricht man dann, dass man diese
Suchteile des Suchraums explizit macht, dass diese Teile, die dann im
Speicher gehalten werden, der aktive Teil des Suchraumes sei.
Und was ich aktiv mache und was ich nicht aktiv mache, oder da stimmt
mir halt meine Heuristik und aktiv machen, explizit machen den Teil
des Suchraums, mache ich halt dadurch, dass ich diese Regeln für die
Übergänge entsprechend anwende.
Erstmal von theoretischem grundsätzlichen Nutzen ist das Prinzip der
Blindensuche.
Bei uns bei der Suche gehen wir davon aus, dass wir einen Pfad finden
wollen, der irgendwie optimale Kosten hat.
Bei der Blindensuche macht man es sich jetzt erstmal einfacher.
Bei der Blindensuche ist man überhaupt erstmal damit zufrieden, wenn
man überhaupt irgendeinen Pfad hat, der von einem Anfangsknoten bis zu
irgendeinem Endeknoten führt.
Egal, welche Kosten der hat.
Das kann man dann zwei verschiedene Arten von Suchen sich hinterher
überlegen.
Zwei verschiedene Teile.
So wie beim Baum kommt man dann hinterher dazu, dass man entweder
sowas wie eine Tiefen- oder wie eine Breitensuche hat.
Was man halt macht ist, man fängt halt bei den, irgendwie wählt man
sich einen Startzustand an, expandiert den, macht dann Teile des neuen
Suchraumes aktiv und expandiert und expandiert so lange weiter, bis
man irgendwann bei einem Zielzustand angekommen ist und muss jetzt
halt diese Strategie, nachdem ich neue Teile des Suchraumes
expandiere, muss ich mir halt geschickt wählen, so dass ich, wenn ich
systematisch vorgehe, auch wirklich am Ende einen Pfad finden werde,
wenn er denn existiert.
Ist natürlich für künstliche Intelligenz, im Allgemeinen, maschinelles
Lernen, weniger interessant, weil wir immer unter Kosten optimieren.
Nichtsdestotrotz kann man da einige grundsätzliche Sachen dran sehen.
Und das ist im Prinzip, dass man diese zwei verschiedenen Strategien
bei der Suche haben kann.
Dass ich einmal sowas machen kann, wie eine Tiefensuche oder sowas wie
eine Breitensuche.
Das kennen alle von der Baumsuche.
Bei der Tiefensuche expandiere ich erst mal möglichst immer von einem
Knoten in den nächsten und dann wieder systematisch weiter und weiter,
so dass die Pfade, die ich überprüfe, erstmal sehr lang werden, bis
ich entweder in einem Ende ankomme oder bis ich entweder in einer
Sackgasse lande.
Wenn ich in einer Sackgasse lande, gehe ich halt einen Schritt zurück
und expandiere dann in die nächste Möglichkeit rein und mache soweit
weiter, bis ich entweder im Ziel ankomme oder in einer Sackgasse bin
und gehe wieder zurück und so weiter und so fort.
Oder alternativ bei der Breitensuche expandiere ich halt immer alle
Möglichkeiten von einem Knoten aus, bekomme neue Zustände und von
allen neuen Zuständen aus expandiere ich auch erst mal wieder alle
Möglichkeiten.
Das heißt, die Pfade, die ich dann während der Suche betrachte, haben
am Ende immer alle gleiche Länge.
Und dementsprechend sprechen wir bei der Spracherkennung von einer
Zeitsynchronen - oder einer Zeitasynchronensuche, weil bei uns die
Länge des Pfades durch den Suchraum entsprechend immer mit der
Zeitlänge des Pfades korrespondiert.
Man sagt also dann, ich expandiere also immer über die
Merkmalsvektoren hinweg, die ich in der Zeit bekommen habe, sodass die
Länge eines Pfades immer in Frames, in Vorverarbeitungsframes gemessen
werden kann.
Und dementsprechend ist so etwas wie eine Tiefensuche, nennt man dann
eine Zeitasynchronesuche, weil die Pfade, die man da expandiert hat,
unterschiedliche Länge haben, unterschiedlich in der Zeit lang sind
und bei der Breitensuche spricht man dann entsprechend von einer
Zeitsynchronesuche, weil die Pfade, die ich alle expandiert habe, alle
die gleiche Länge haben.
Jetzt ist die Frage, welche Strategie ist denn besser, sinnvoller,
Tiefensuche oder Breitensuche, wenn ich so eine blinde Suche mache?
Welcher sind beide, sind beide Strategien Garanten dafür, dass ich
einen Pfad finden werde, sofern er denn existiert?
Oder kann das passieren bei einer der beiden Strategien, dass ich
vielleicht nicht unbedingt notwendigerweise einen Pfad finden werde,
wenn er denn existiert?
Zwei Mann, zwei Mann, zwei Mann, da hinten drei.
Zwei Minuten diskutieren, wie das der Fall ist.
Wir gehen ja mit unserem, wir haben jetzt erstmal nur den Teil
betrachtet, dass wir immer Aufnahmen endlicher Länge betrachten.
Das heißt also, unsere Aufgabe, Aufnahme ist immer endlich.
Wir haben also nicht, dass wir unendlich tief gehen.
Wir haben letztendlich einen endlichen Sucher.
Wir haben eine endliche Länge, wir haben eine endliche Anzahl an
Zuständen, wir haben eine endliche Anzahl an Übergängen.
Jetzt ist nur die Frage, die Tiefensuche, so in dieser einfachsten,
billigsten Form, die da sagt, wenn ich in eine Sackkasse reinkomme,
also wenn ich nicht mehr weiter expandieren kann, dann gehe ich eine
Ebene zurück und nehme die nächste Möglichkeit.
Funktioniert die immer?
Und jetzt muss man aufpassen.
Ihr guckt alle auf das Bild.
Das ist kein allgemeiner Suchgraf, das ist ein Baum.
Wenn ich einen Baum habe, einen gerichteten Baum, wo ich sagen kann,
das ist der Vater, das sind die Söhne, dann funktioniert das mit der
Tiefensuche, weil ich dann nämlich in eine Sackgasse reinlaufe.
Was kann aber bei der Tiefensuche passieren, wo ich niemals in eine
Sackgasse reinlaufen werde, wenn ich nicht aufpasse, wenn ich einen
Zyklus habe?
So ein allgemeiner Suchraum kann durchaus einen Zyklus haben und wenn
ich jetzt in den Zyklus reinlaufe, dann läuft er ewig weiter.
Das heißt, spätestens da brauche ich dann als zusätzliches Hilfsmittel
einen Zyklusdetektor, der mir sagt, oh, pass mal auf, hier, du bist da
in den Zyklus reingelaufen, das hattest du schon mal.
Abbruch, Sackgasse, funktioniert nicht.
Und jetzt kann man sich überlegen, so ein Zyklusdetektor, der kann
unter Umständen sehr aufwendig sein, weil so ein Zyklus, der muss
nicht aus drei Knoten bestehen, der Zyklus, der kann, je nachdem,
welches Suchproblem ich habe, wenn wir uns jetzt mal von der
Spracherkennung lösen, da kann ja, keine Ahnung, 50.000 Knoten lang
sein.
So ein Pfad, der 50.000 Knoten durchläuft und dann läuft dann ein
Zyklus.
Und was ich jetzt machen muss bei der Zyklusdetektion, jedes Mal, wenn
ich einen Knoten in einen neuen Zustand expandiere, da muss ich erst
mal gucken, okay, hatte ich den Knoten schon mal?
Wenn ja, dann könnte das sein, dass das ein Zyklus ist.
Und dann muss ich sozusagen durchsuchen, hatte ich den Knoten noch
mal?
Habe ich dann den Knoten ein zweites Mal gesehen?
Und ist das beides Mal das gleiche Teilstück gewesen?
Also war es ein echter Zyklus?
Und wenn das 50.000 Knoten sind, dann muss ich überprüfen, ob
sozusagen die gleich sind.
Das kann also durchaus von der Rechenzeit her relativ aufwendig sein.
Das heißt also, bei der Tiefensuche, wenn man halt nicht aufpasst und
Zyklen in seinem Suchraum zulässt, kann das durchaus schief gehen.
Bei der Breitensuche passiert mir das halt nicht, weil ich halt auf
breiter Front extrahiere und wenn halt irgendein Teilsfahrt in den
Zyklus reinläuft, die anderen, wenn es zyklenfreie Fahrt gibt, der ins
Ende führt, dann ist das in Ordnung.
Da ist halt auch das Problem, kann natürlich auch sein, wenn alle
Pfade, die ich expandiere, Zyklen sind, dann kann das natürlich auch
blöd sein, dass der dann auch nie terminiert, aber immerhin terminiert
er nur dann nicht, wenn es auch keine Lösung gibt.
Das heißt also, wenn ich dann irgendwann alle Zeitpunkte abgearbeitet
habe, ohne dass ich zu einem Ziel gekommen bin, dann terminiert
immerhin der Algorithmus und ich zumindest bei der Spracherkennung, wo
ich halt weiß, wie viele Zeitschritte ich gehen muss, wie lang, also
die Länge des Pfades kenne, dann kann ich da wie bei der Tiefensuche
auch abbrechen, aber im Allgemeinen kann es auch passieren, dass wenn
es eine Lösung nicht gibt und alle Pfade in Zyklen reinlaufen, dass
ich auch da einen Zyklendetektor brauche, damit der Algorithmus
irgendwann mal abbricht.
Also so eine blinde Suche hat kein Wissen darüber, wo ich bin und in
welche Richtung ich weitersuchen muss.
Die macht einfach systematisch nach Schema F seine Suche durch.
Wenn ich jetzt mit Blindersuche die beste Lösung finden möchte,
irgendwas, was mir irgendwelche Kosten optimiert, dann muss ich
sozusagen alle möglichen Suchpfade durchprobieren, also die so lange
weiterlaufen lassen, die Suche, also angenommen Tiefensuche oder
Breitensuche.
Ich habe eine Tiefensuche, ich habe einen Pfad gefunden.
Alles super, das nehmen wir dann raus und suchen halt weiter, so lange
bis wir nicht mehr neue Pfade bilden können.
Immer wenn ich einen gefunden habe, nehme ich den raus aus dem
Suchraum.
Wenn ich also da Kosten optimieren will, muss ich so lange
weiterlaufen, bis ich alle möglichen Pfade durchgenommen habe und
entscheide mich dann für den geringsten.
Nennt man dann entsprechend Bootforce die Methode oder auch einfach
British Museum Suche.
Jetzt will ich natürlich den Suchraum einschränken.
Ich möchte nicht alle beliebigen Pfade betrachten, sondern nur welche,
die auch irgendwie sinnvoll zu sein scheinen, die also überhaupt
Kandidaten dafür sein können, dass sie vielleicht eine optimale Lösung
finden werden.
Und solche Kandidaten möchte ich eliminieren, von denen ich weiß, dass
sie ganz sicher nicht zu einer optimalen Lösung führen werden.
Und das kann ich mithilfe einer Heuristik.
Und eine Heuristik kann man formalisieren als eine Funktion, die
implizit Wissen darüber enthält, dass wenn ich in einem Zustand bin,
wie viel wird es noch minimal an Kosten kosten, um von hier bis zum
Ziel zu gelangen.
Mit so einer Abschätzung kann ich dann dahin kommen, dass ich für
jeden Knoten in meinem Zustand diese Zahl f von n ausrechnen kann.
Ich habe einmal eine geschätzte Distanz von hier, vom aktuellen
Zustand bis ins Ziel herein.
Ich weiß konkret die Distanz, wie weit bin ich denn schon gegangen,
wie viel Kosten habe ich bisher aufakkumuliert, um nach hier, nach n
zu kommen.
Und wenn ich die beiden zusammen addiere, dann ist das eine
Abschätzung dafür, wie gut der Pfad ist, der durch diesen aktuellen
Zustand läuft, in dem ich bin.
Und jetzt hängt alles davon ab, wie ich diese restliche verbleibende
Distanz schätze.
Und zwar kann ich da Unterscheidungen machen zwischen Heuristiken,
zwischen Abschätzungen, die mir garantieren werden, dass ich eine
optimale Lösung finden werde und zwischen Abschätzungen, die mir das
nicht mehr garantieren werden.
Und ein Beispiel so einer Heuristik kann man schön bei einer
zeitsynchronen Suche in einem Suchraum machen.
Und sowas nennt man dann die A-Sternchen-Suche.
Das ist eine Tiefensuche, eine zeitasynchrone Suche, die mit einer
Heuristik arbeitet, die dafür sorgt, dass ich immer zum Optimum kommen
werde.
Man spricht dann also hier von einer Best-First-Search, einer
Tiefensuche mit einer Admissible-Heuristik.
Diese restliche Distanz vom aktuellen Knoten bis zum Ziel ist bei
dieser A-Sternchen-Suche derart, dass sie die tatsächliche Distanz
immer unterschätzt.
Sie überschätzt also nie die verbleibende Distanz vom aktuellen Knoten
bis zum Ziel, sondern sie sagt entweder die tatsächliche Distanz
voraus oder etwas, was kleiner ist.
Und das sorgt dafür, dass ich am Ende in der Lage sein werde, eine
optimale Lösung zu finden.
Warum?
Wie muss man sich das vorstellen?
Naja, ich habe also eine Unterschätzung.
Das heißt, ich expandiere immer die Knoten, wo mir letztendlich
hinterher die aktuell aufkumulierte Distanz plus die Abschätzung
darüber, was Kleines vorhersagt, die expandiere ich.
Und je tiefer der Pfad wird, desto konkreter werden die Kosten, desto
weniger hängt er von dieser Heuristik ab und desto mehr hängt er davon
ab, wie viele tatsächliche Kosten er hat.
Und angenommen, ich habe jetzt irgendwo einen Pfad, der hätte die
optimalen Kosten, den würde ich aber noch nicht kennen.
Und ich habe zehn aktive Knoten, die ich bisher expandiert habe,
können unterschiedliche Längen haben, ist ja eine Tiefensuche, die ich
da durchführe.
Ich expandiere immer den Knoten, der mir die geringsten Kosten
vorhersagt.
Der wird immer vorausgesagt für jede, für jeden Knoten, den ich, jeden
Zustand, in dem ich schon expandiert habe, habe ich eine Voraussage
dafür, wie viel, wie teuer ist das, durch diesen Knoten zu gehen auf
diesem Pfad, wie ich ihn bisher hatte.
Also expandiere ich immer den, der mir voraussagt, ich habe am
wenigsten.
Und dann passiert Folgendes.
Angenommen, ich unterschätze halt die tatsächlichen Kosten, dann habe
ich irgendwann einen Pfad, der ist nur noch einen Schritt vom Ziel
entfernt und er unterschätzt mir die Kosten.
Er ist aber nicht der optimale Pfad.
Spätestens dann, wenn ich ihn expandiere, in den Zielknoten rein,
kenne ich die tatsächlichen Kosten dieses Pfades.
Ich weiß, wie tatsächlich, wie teuer ist es ja, vom Start zum
Endzustand zu kommen.
Alle anderen Knoten unterschätzen die tatsächlichen Kosten.
Das heißt, wenn das also jetzt nicht der optimale Pfad war auf dem ich
bin, dann gibt es irgendwo einen anderen aktiven Knoten, der mir sagt,
schätzt, dass er eine geringere, geringere Kosten hat, als dieser
aktuelle Pfad, den ich jetzt bisher gefunden habe, weil ich die
tatsächlichen Kosten immer unterschätze.
Und wenn es der Fall ist, dass die tatsächlichen Kosten von diesem
Pfad, den ich gefunden habe, unter allen anderen Schätzungen liegen,
die zurzeit aktiv sind, dann muss das der optimale Pfad sein, weil die
anderen ja immer unterschätzen.
Also insbesondere dann geringere Kosten angeben, als sie tatsächlich
hinterher verursachen werden.
Und deswegen sorgt mir eine, diese Schätzfunktion von Kosten noch bis
ins Ziel herein, wenn ich so eine Schätzfunktion habe, die die
tatsächlichen Kosten immer unterschätzt, dafür, dass ich bei so einer
Tiefensuche dann tatsächlich eine optimale, einen optimalen Pfad
finden werde.
Jetzt ist es natürlich so, damit diese Suche Effizienz läuft, muss
zwar diese Funktion h von n die tatsächlichen Kosten echt
unterschätzen, aber sie darf es natürlich auch nicht übertreiben,
sondern sie sollte möglichst nah an den tatsächlichen Kosten liegen.
Ich kann eine ganz einfache, billige Heuristik angeben, die mir immer
dafür sorgen wird, dass ich mit so einem Algorithmus die beste Lösung
finde.
Ich sage einfach h von n gleich 0.
Dann unterschätze ich meine tatsächlichen Kosten auf alle Fälle, aber
am Ende habe ich damit nichts wieder anderes als eine blinde
Tiefensuche, die ich damit durchführe und die mir alle Pfade
expandieren wird, die ins Ziel führen und danach unterscheide ich mich
unter denen für den besten Pfad.
Dann gibt es eine Alternative zu dieser formalen Heuristik und das ist
die der Strahlsuche.
Und das kombiniert man in der Regel immer mit so zeitsynchronen
Suchen.
Manchmal ist es halt nicht möglich, so eine Heuristik zu finden.
Man kann sich das ja schon relativ schwierig vorstellen.
Wie muss ich mir das denn vorstellen bei der Spracherkennung, wenn ich
irgendwo in einem Suchraum bin?
Das heißt, so ein Zustand in einem Suchraum sagt mir nichts anderes
als, ich bin in einem HMM-Zustand und habe schon jede Menge
Merkmalsvektoren ausgegeben und jetzt zu diesem Zeitpunkt bin ich in
dem Zustand und mit Sprachmodell bisher N-Gramme drauf multipliziert
und akustischem Modell habe ich die und die Kosten.
Und jetzt ist die Frage, wie viele Kosten sind es denn noch bis ins
Ziel?
Das weißt du nicht.
Ist schwer abzusagen.
Bei so topografischen Sachen kann man sich das vielleicht überlegen.
Wenn man sich überlegt, zum Beispiel, ich suche den kürzesten Weg, der
mir über so bestimmte Pfade, die ich auf einer Landkarte eingezeichnet
habe, von A nach B führen.
Dann könnte ich sagen, als eine einfache Heuristik, naja, nehme ich
halt die Distanz der Luftlinie.
Ich weiß ja, wo ich mich im kathesischen Produkt befinde.
Ich weiß, wo das Ziel ist.
Ich weiß halt nur nicht, welche Kombination aus Teilpfaden, so
Teilstrecken, Straßenabschnitten, Wegabschnitten jetzt die geringste
ist.
Dann nehme ich als Heuristik die Luftlinie.
Das wird auf alle Fälle die tatsächlichen Distanzkosten unterschätzen
und dürfte auch etwas sein, was, wenn jetzt nicht die Straßenbauer
komplett irgendwie komisch was gebaut haben oder was weiß ich,
aufgrund von Bergen oder sonstigen irgendwas, das halt nicht anders
ging.
Etwas, was relativ gut, relativ nahe an der tatsächlichen Distanz sein
wird.
Bei der Spracherkennung ist halt schwierig, wie ich so eine Heuristik
jetzt machen soll.
Deswegen findet man bei der Spracherkennung häufig so eine
zeitsynchrone Suche, wo man mit Hilfe von Strahlsuchen vorgeht.
Das heißt, ich gehe zeitsynchron vor, habe so eine Breitensuche und
habe eine Menge an Pfaden schon expandiert, bin in einer Menge von
Zuständen, aber ich verfolge jetzt nicht mehr alle Zustände weiter,
sondern was ich mache ist, ich verfolge jetzt nur noch die Zustände
weiter, die bisher schon eine relativ kleine Distanz und eine relativ
große Wahrscheinlichkeit aufakkumuliert haben.
Das ist insbesondere deshalb sinnvoll, weil ja Sprache so mehr oder
weniger linear in der Zeit verläuft.
Das heißt, zwar haben wir wechselnde Sprechgeschwindigkeiten, aber
diese Unterschiede in der Sprechgeschwindigkeit sind jetzt nicht so
extrem, dass ich die ersten 15 Phoneme, wenn ich 16 Phoneme gesprochen
habe, ganz schnell spreche und dann das restliche Phonem braucht 80
Prozent der verfügbaren Sprechzeit.
Wenn ich jetzt nicht gerade Ansager im Boxring bin oder so, wird das
eher nicht passieren, sondern so im Großen und Ganzen wird sich das ja
ungefähr in der Zeit halbwegs gleichmäßig aufeinander verteilen.
Insbesondere heißt das, wenn ich mir also anschaue, welche Phoneme
aktuell in der Aufnahme gegeben, welche Phonemesequenzen haben das
denn jetzt ausgeben können, welche Zustandssequenzen in dem HMM des
akustischen Modells haben das denn bisher ausgeben können, wenn die
schon am Anfang sehr, sehr schlecht sind, dann ist die
Wahrscheinlichkeit, dass sie das hinterher aufholen werden, dieses
schlechte Passen am Anfang, ja eher gering.
Und deswegen kann ich das halt machen, dass ich sage, okay, nach einer
gewissen Zeit, wenn die schon schlecht sind, dann brauche ich die
nicht weiter zu verfolgen.
Die werden nie und nimmer besser werden als die aktuell besten.
Und da arbeitet man dann mit solchen Pfaden, indem man sagt, okay, die
Anzahl der Zustände, die ich expandiere, beschränke ich ein zum
Beispiel auf die Zustände, die nicht mehr als zehn Prozent schlechter
sind, relativ schlechter sind als der aktuell beste Zustand.
Sowas nennt man dann einen relativen Beam.
Oder man kann einfach was nehmen wie einen absoluten Beam.
Die sind nicht mehr als Wahrscheinlichkeit 0,2 schlechter als der
aktuelle beste Zustand oder im Score, im Log
-Wahrscheinlichkeitsbereich, die dann nicht mehr als 1000 irgendwas
schlechter sind, 800 schlechter sind als der aktuelle.
Oder ich kann das Ganze, wenn ich will, auch noch kombinieren mit so
einem Cap, den ich drauf setze, dass ich sage, okay, relativer Beam,
die sollen nicht mehr als zehn Prozent schlechter sein als der
aktuelle Zustand.
Plus ich möchte maximal absolut gesehen 100 Zustände aktiv halten, von
denen ich aus expandiere, auch wenn es vielleicht noch einen 101.
und 102.
gäbe, der auch noch innerhalb dieses Beams fallen würde.
Ich schneide einfach die schlechtesten ab.
So eine Strahlsuche findet logischerweise nicht notwendigerweise die
optimale Lösung, aber für so praxisrelevante Probleme ist es in der
Regel so, dass man trotzdem, wenn nicht optimale, doch meistens sehr,
sehr gute Lösung findet.
Wenn man sich das jetzt in der Spracherkennung anschaut, dann hat man
häufig so das Bild, dass man da so eine Taschenlampe hat, die in den
dunklen Suchraum hinein leuchtet und einen Teil des Suchraums halt
ausleuchtet.
Und man hat so dieses Bild drin, dass man schaut, wie weit man nach
links oder nach rechts schaut.
Das ist natürlich nur ein Bild und das hat natürlich mit der Praxis
nichts zu tun.
Also wenn ich mir jetzt den Suchraum anschaue, hat das nichts damit zu
tun, dass die Zustände miteinander benachbart sind.
Diese Nachbarschaft bekommt man erst dann hin, wenn man anfängt, die
aktuellen Zustände sozusagen gemäß ihrer aktuell aufkumulierten
Wahrscheinlichkeit zu sortieren.
So macht man das meistens bei der Implementierung.
So sortiere ich dann gemäß der aktuell aufgenommenen
Wahrscheinlichkeit und dann gehe ich von oben nach unten durch, bis
ich entweder den relativen Beam abschneide oder die maximale Anzahl an
erwünschten Zuständen erreicht habe und da entsprechend abschneide.
Und wenn man sich das jetzt anschaut, bei der Anzahl Zustände muss ich
halt sortieren, damit ich weiß, wie viel ist der zehnbeste Zustand.
Beim relativen Beam brauche ich das nicht zu machen.
Da kann ich einfach alle durchgehen und jeden, der halt kleiner ist,
als der aus diesem Beam rausfällt, wird halt als markiert nicht weiter
expandieren.
Dafür hat halt dieses Brunnen nach der maximalen Anzahl an Zuständen
den Vorteil, dass ich sowas wie eine Laufzeit garantieren kann.
Dadurch, dass ich weiß, wie viele Zustände pro Zeiteinheit, die ich
absuchen muss, maximal konstant sind, kann ich damit garantieren, dass
hinter die Laufzeit der Suche darauf beschränkt wird.
Während bei so einem relativen Beam es durchaus sein kann, dass sehr,
sehr, sehr viele Zustände in den relativen Beam reinfallen und ich
dann halt längere Laufzeit habe.
Mal einfach als Beispiel, um mal zu schauen, wie sich das so in der
Praxis, bei der Spracherkennung verhalten würde.
Hier so ein Beispielplot, wo ich unten auf der Achse abgetragen habe,
die Länge der Suche, also die Laufzeit der Suche als sogenannter
Echtzeitfaktor, als Realtimefaktor.
Das heißt, dieser Faktor gibt an, für eine Sekunde Sprache, wie viele
Sekunden habe ich denn gebraucht, um die zu dekodieren.
Also beim Realtimefaktor von 1, wenn ich eine Aufnahme der Länge 20
Sekunden habe, dauert die Suche 20 Sekunden, bis sie das Ergebnis
gefunden hat und der ist halt hier variiert von Laufzeitfaktor 3 mal
Echtzeit bis hin Laufzeitfaktor 0,7 fach Echtzeit und auf der Y-Achse
ist halt aufgetragen die Wortfehlerrate.
Und es ist intuitiv klar, es sollte hoffentlich so sein, dass je mehr
ich vom Suchraum absuche, desto mehr Laufzeit brauche ich, aber desto
besser wird die Hypothese sein, die ich finde, diese Wortfolge, desto
besser wird die Wahrscheinlichkeit der Wortfolge sein, die ich finde,
desto geringer sollte seine Wortfehlerrate sein.
Und dann sieht man hier so ein typisches Verhalten.
Es gibt irgendwie sowas, so eine Art Abbruchkante.
Wenn ich also unter einem bestimmten Echtzeitfaktor gehe, wenn ich
meinen Beam irgendwie zu klein mache, dann stürzt die Wortfehlerrate
relativ schnell ab.
Dann macht es einen Unterschied.
Schon ein ganz kleines Zumachen des Beams sorgt dafür, dass die
Wortfehlerrate ganz schnell abstürzt.
Während ich irgendwo hier dann einen Punkt habe, wenn ich dann noch
mehr Rechenzeit dazu nehme, dann wird die Wortfehlerrate nur minimal
besser.
Das heißt also, wenn ich hier zum Beispiel von 1,8 nach 2,8 gehe, das
ist immerhin ein Echtzeitfaktor-Wortfehlerrate, dann gehe ich davon
sowas von 88 bis 88,5 Wortfehlerrate.
Das heißt, ich muss noch mal Länge der Aufnahme lang extra zusätzlich
rechnen, um noch mal 0,5 Prozent absolut Wortfehlerrate dazu zu
bekommen.
Das lohnt sich nicht.
Plus, ich habe dann plötzlich solche Effekte wie hier, dass ich zum
Beispiel an der Stelle zum Beispiel mit der Wortfehlerrate wieder ein
bisschen runtergehe.
Wie kann das denn passieren?
Hier größer der Beam wird, das Einzige, was ja passieren kann, ist die
Rechnelänge.
Plus, ich finde eine Wortfolge, deren Wahrscheinlichkeit höher ist,
als die Wortfolge, die ich finden würde, die ich halt vorher bei einem
kleineren Beam gefunden habe.
Aber trotzdem kann plötzlich die Wortfehlerrate leicht sinken.
Was ist denn da passiert?
Ihr Chef kommt zu Ihnen, hier, da, da, noch mal halben Echtzeitfaktor
gerechnet und die Wortfehlerrate sinkt um 0,3.
Dann bist du doof.
Nein, ich bin nicht doof, sondern was kann das sein?
Das sind zwei Effekte, zum Beispiel Modellierungsfehler.
Wir wissen halt, HMMs sind kein exaktes Modell vom
Sprachproduktionsprozess.
Das ist halt nur so ungefähr.
Das Sprachmodell ist ja auch nur geschätzt auf Trainingsdaten.
Das muss nicht unbedingt immer hundertprozentig richtig sein.
Da können schon mal so kleinere Variationen drin sein, die halt mit
der tatsächlichen Wortverteilung nichts zu tun haben.
Das heißt also, nur weil eine Wortfolge vielleicht eine etwas gleicht
höhere Wahrscheinlichkeit hat, als eine andere Wortfolge, heißt das
noch lange nicht, dass die garantiert in der Wortfehlerrate besser
sein muss.
Es ist wahrscheinlich so und erwartungsgemäß so, aber es nicht
garantiert.
Das ist der eine Effekt.
Und dann gibt es noch einen zweiten Effekt, den kennen Sie noch nicht,
aber da kann man sich jetzt schon mal ein bisschen was überlegen.
Wir haben da die Fundamentalformel der automatischen Spracherkennung,
die da lautet...
Das muss sitzen.
Die Fundamentalformel der automatischen Spracherkennung lautet...
Ja, los.
Nachts um drei, ich habe angerufen.
Gut, das ist erstmal nur eine Baseformel.
Und jetzt machen wir den Schritt zur Fundamentalformel.
Was kommt da noch dazu?
Genau, also die wahrscheinlichste Wortfolge w-dach ist gleich das
Argument Maximum über alle möglichen Wortfolgen w von p von w gegeben
x ist gleich dem Argument Maximum über alle möglichen Wortfolgen w, p
von x gegeben w mal p von w.
Und jetzt kann man sich überlegen, was messen wir da und was suchen
wir?
Wir messen hier die Wortfehlerrate oder in diesem Fall die
Wortakkuratheit, also 100 Prozent Minuswortfehlerrate.
Wir optimieren aber, indem wir die wahrscheinlichste Wortfolge suchen.
Und jetzt zurückdenken an Vorlesung Stochastik, Vorlesung kognitive
Systeme.
Wenn wir nach der wahrscheinlichsten Wortfolge suchen, was mache ich
dann im Hinblick auf Klassifizierungsfehler?
Warum ist das sinnvoll?
Warum ist dieses Ganze, warum ist ein naiver Base-Klassifizierer?
Das ist nichts anderes als ein naiver Base-Klassifizierer, den ich
mache.
In der Cox's haben sie kennengelernt, sie haben eine Klasse 1 und eine
Klasse 2 und rechnen die posteriore Wahrscheinlichkeit von Klasse 1
aus und von Klasse 2 und entscheiden sich für die höhere.
Und hier haben sie halt nicht zwei Klassen, hier ist halt
fortgeschrittene Vorlesung, hier haben sie halt 100 Trilliarden,
Milliarden, Billiarden, irgendwas Klassen mehr als Atome im Universum.
Aber am Ende entscheiden sie sich auch immer nur für die mit der
höchsten Posteriore Wahrscheinlichkeit.
Und wenn sie das machen, was minimieren sie?
Gehen wir mal zurück an Cox's.
Da mussten sie hier so schraffieren, Kurven zeichnen, Glockenkurven,
die sie unterscheiden und da mussten sie Fläche unter den Kurven
schraffieren und dann wurden sie gefragt, was bedeutet das
Schraffierte?
Was war das?
War die Fehlerwahrscheinlichkeit.
Das heißt also, wenn ich die Posteriore Wahrscheinlichkeit maximiere,
minimiere ich den Erwartungswert dafür, dass ich einen Fehler mache.
Was heißt das jetzt wieder bezogen auf die Fundamentalformel?
Wenn ich nach der wahrscheinlichsten Wortfolge suche, minimiere ich
die die Erwartungswert dafür oder minimiere ich die Wahrscheinlichkeit
dafür, dass ich einen Fehler mache.
Und was heißt ein Fehler machen auf eine Wortfolge als Klassifikation?
Das heißt, dass ich mich für eine Wortfolge entscheide, die nicht
gleich ist der tatsächlichen Wortfolge.
Und ob da jetzt zehn Fehler drin stecken oder nur ein Fehler drin
stecken, das ist egal.
Wortfolge ist ungleich.
Das heißt, dieses Kriterium, was ich, nachdem ich maximiere, die hat
nichts mit dem Wortfehler zu tun.
Ich messe hier was völlig anderes, als wonach ich optimiere.
Ich optimiere nach dem Satzfehler.
Ich optimiere hinterher, dass der Satzfehler minimal wird.
Also, dass ich mindestens einen, die Wahrscheinlichkeit dafür, dass
ich mindestens einen Fehler mache in dem erkannten Satz, dass der
minimal wird.
Dass also der Satz möglichst hundertprozentig eins zu eins zu
übereinstimmt.
Das heißt aber noch lange nicht, dass ich dieses Maß da minimiere.
Da müssen wir uns später noch überlegen, was das eigentlich bedeutet
und was man da machen kann.
Gut, also wir sind dabei, wir haben jetzt Zeit Asynchrone
kennengelernt mit einer Heuristik.
Das nennen wir die A-Sternchen-Suche.
Wir haben die Zeit-Synchrone-Suche kennengelernt mit einem Strahl.
Ist eine andere Art von Heuristik.
Die Zeit-Synchrone-Beam-Search.
Jetzt ist es in der Spracherkennung so gewesen, dass lange Zeit ein,
nennen wir es mal, Glaubenskrieg herrschte.
Was besser funktioniert, was besser geeignet ist.
Ist besser die Strahl-Suche geeignet oder ist besser die, so eine A
-Sternchen -Suche, so eine Zeit-Asynchrone-Tiefensuche geeignet.
Und am Ende, weil rausgekommen ist, wenn man fragt, sagen die Leute,
ja die Zeit-Synchrone-Suche hat gewonnen.
Man nimmt heute lieber so eine Zeit-Synchrone-Suche als so eine Zeit
-Asynchrone -Suche mit Heuristik.
Was unter anderem daran liegt, dass es natürlich für die
Spracherkennung schwierig ist, so eine vernünftige Heuristik
aufzustellen.
Das Ganze ist aber nur die halbe Wahrheit.
In Wirklichkeit verwendet man heutzutage immer noch beides.
Man verwendet sowohl eine Zeit-Synchrone-Suche als auch so eine A
-Sternchen -Suche.
Und zwar in der Art und Weise, dass man erstmal eine Zeit-Synchrone
-Strahlsuche durchführt und man aber nicht nur übrig behält die
wahrscheinlichste Wortfolge, den Pfad mit den geringsten Kosten,
sondern ich behalte den gesamten Suchraum übrig, den ich während
dieser Zeit-Synchrone-Suche aktiv gemacht habe.
Das ist nur ein Unterteil meines tatsächlichen Suchraumes.
Und danach gehe ich noch mal hin und suche diesen teilweise synchron
gemachten, teilweise aktiv gemachten Suchraum noch mal ab mit so einer
A -Sternchen-Suche.
Jetzt müssen Sie sagen, ihr Bekloppt.
War überhaupt kein Sinn.
Was soll denn das bringen?
Ihr habt doch damit eine Zeit-Synchrone-Suche.
Ich nehme das, was übrig geblieben ist, was aktiv gemacht wurde
während der Zeit-Synchrone-Suche.
Bei der Zeit-Synchrone-Suche ist ein, Strahlsuche ist ein optimaler
Pfad rausgekommen und jetzt nehme ich noch mal das, was übrig
geblieben ist und suche das noch mal mit der Breiten-Suche ab.
Da kann da nichts anderes bei rauskommen.
Weil unter dem, was aktiv gemacht wurde, hat man ja die Zeit-Synchrone
immerhin den kürzesten Weg rausgesucht.
Da kann man ja jetzt bitte schön so eine A-Sternchen-Suche nicht noch
was Neues rauskommen.
Ja, das stimmt.
Deswegen macht man folgenden Trick.
Man kann sich jetzt schon überlegen, so eine Zeit-Synchrone
-Strahlsuche, das kann relativ aufwendig sein.
Das kann relativ kompliziert zu berechnen sein.
Und deswegen kann man sich zum Beispiel folgendes Szenario vorstellen,
dass man so eine Zeit-Synchrone-Suche mit einem Modell bestimmter
Komplexität macht.
Zum Beispiel ein Trigrammsprachmodell mit einem Trifon-Akustischen
-Modell.
Dann bekomme ich so einen Ausschnitt aus dem Suchraum, der
Wortfolgenpfade enthält, die zumindest nicht ganz aussichtslos zu sein
scheinen, sondern gute Kandidaten für das Optimum zu sein scheinen.
Und das, was übrig geblieben ist, suche ich jetzt nochmal ab, aber mit
anderen Modellen.
Mit deutlich besseren, mit deutlich komplexeren Modellen.
Quintfone mit 5-Grammsprachmodell, die ich niemals hätte da für die
Zeit -Synchrone-Suche anwenden können, weil es viel zu lange gedauert
hätte.
Aber dadurch, dass jetzt nur noch wenig übrig geblieben ist, kann ich
jetzt diese komplexen Modelle auf dem wenigen, das übrig geblieben
ist, nochmal anwenden und da viel genauer die Kosten ausrechnen.
Und das, dieses Absuchen des Wenigen, was dann übrig geblieben ist,
das kann man dann gut mit so einer A-Sternchen-Suche machen.
Warum ist das Ganze denn so komplex?
Ja, warum ist das Ganze so komplex?
Jetzt muss ich gucken, dass ich das von Hand hinkriege, weil ich habe
das Buch vergessen.
Was uns da so ein bisschen in die Suppe reinspuckt, ist zum Beispiel
das Sprachmodell.
Das Sprachmodell macht diesen Suchraum teilweise sehr kompliziert.
Hätte ich nur das akustische Modell, naja, was hätte ich denn dann?
Dann hätte ich auf der einen Achse die Zeit, auf der anderen Achse
alle möglichen HMM-Zustände, die ich so habe, mit deren Hilfe ich mir
Wörter zusammenbasteln kann und dann irgendwie eine Topologie, die mir
durch das Aussprache-Wörterbuch gegeben wird, aller möglichen Wörter,
die ich erkennen will.
Und daraus könnte ich mir dann so ein HMM zusammenbauen, das ja alle
theoretisch möglichen erkennbaren Wortfolgen in irgendeiner Form
beinhaltet.
Da hätte ich dann halt so Zyklen drin, dass ich also vorne, wenn ich
hinten aus einem Wort rausfalle, vorne wieder ein neues Wort rein kann
und dann brauche ich irgendwie ein Wort, das sorgt noch dafür, dass
sei das Ende-Wort und wenn ich dann alle Eingabe-Vektoren abgearbeitet
habe, dann gültiger Fahrt muss dann irgendwie in einem Endzustand von
einem Wort aufgehört haben, dann hätte ich das gefunden und das könnte
ich schön mit so einer Such-, mit so einer Strahl-Suche absuchen.
Wenn man das jetzt darstellen will, könnte ich mir das ungefähr so
vorstellen.
Ich habe einen virtuellen Start-Zustand, ich habe einen virtuellen End
-Zustand, dazwischen habe ich diese Wort-HMMs
für alle Worte, die es so gibt.
Das sind mal mehr, mal weniger Zustände, je nachdem wie viele Phonemen
ich habe.
Und wenn ich mit so einem Wort fertig bin, dann kann ich halt entweder
in den Endzustand reingehen, Satz ist zu Ende, oder ich kann halt
vorne wieder von vorne anfangen.
Das wäre der Suchraum.
Ich habe so einen, was man jetzt noch machen kann, wenn man das will.
Man kann hier noch so einen virtuellen Start-Zustand anmachen und dann
habe ich hier an der Stelle so Y-Übergänge, die eigentlich nichts
produzieren, die ich nur machen muss und dann alles, was mir von hier
losgeht, dann da sich mal durchkreist und am Ende hier landet, ist ein
gültiger Pfad durch dieses HMM und entspricht einer Wortfolge.
Und da könnte ich jetzt halt über die Zeit hinweg anfangen
auszurechnen.
Und was bei rauskommt, ist letztendlich wieder so eine Trellis wie
beim Viterbi-Algorithmus oder wie beim Forward-Backward-Algorithmus.
Da könnte ich einen kompletten Forward-Backward-Algorithmus so in der
Art draufwerfen.
Ich könnte so was wie ein Viterbi-Algorithmus draufwerfen und das
kombiniere ich dann auch noch mit einer Strahl-Suche.
Und das ist relativ gutmütig noch.
Jetzt fangen wir bei uns an, auch noch das Sprachmodell mit
reinzubauen.
Weil das Problem ist, würde ich es wirklich so machen, dass ich ganz
am Ende einmal P von W drauf multiplizieren würde, dann wäre ich hier
schon den Hintern geknüpft.
Weil dann könnte ich die Sprachmodellwahrscheinlichkeit erst ganz am
Ende einmal komplett drauf multiplizieren und könnte nicht während der
Suche wegpunen.
Ich kann nur wegpunen aufgrund von akustischer Modellinformationen,
aber ich kann nicht wegpunen aufgrund davon, von Informationen der
Wahrscheinlichkeit der Wortfolge.
Glücklicherweise habe ich das hier bei den Sprachmodellen dann nicht
mehr gehabt.
Glücklicherweise hatte ich ja auch aus anderen Gründen dann sowas wie
N -Gramme, dass ich also nur ein Wort, gegeben seine Historie hernehme
und das drauf multipliziere.
Und die Wahrscheinlichkeit wird dann halt immer kleiner kleiner, wenn
ich halt die nächste, das nächste N-Gramm Wahrscheinlichkeit drauf
multipliziere, wenn ich das nächste Wort hinten an die Wortfolge dran
hänge.
Das ist ganz schön in so einem Modell, weil jedes Mal, wenn ich jetzt
also einen Übergang mache von einem Wort raus, wieder rein, irgendwo
rein, dann brauche ich ja nur die Sprachmodellwahrscheinlichkeit beim
Wortübergang mit drauf zu multiplizieren und kann schön meine
Strahlsuche anwenden.
Gut, bei einem Unigramm-Sprachmodell, weil relativ einfach.
Wenn ich hier so einen Übergang mache, dann muss ich diesen Zustand
auflösen und habe ich hier immer die Endzustände meiner Worte,
diesen Zustand muss ich auflösen und dann schleife ich vorne in die
Startzustände meiner Wörter wieder rein.
Und jetzt habe ich folgendes Phänomen.
Wenn ich ein Unigramm habe, die Wahrscheinlichkeit, hier reinzugehen,
hängt nur davon ab, in welches Wort ich denn vorne reingehe.
Das heißt, alle Pfade, die in dieses Wort reingehen, das sei das Wort
Groß WM, die kriegen eine Wahrscheinlichkeit von P WM drauf
multipliziert, die Unigrammwahrscheinlichkeit.
Dieser Pfeil genauso.
Das heißt, alle Pfeile, die hier vorne reingehen, die kriegen die
gleiche Sprachmodellwahrscheinlichkeit drauf.
Im Prinzip könnte ich hier sozusagen diesen Sammelzustand sogar
erhalten lassen und dann alle Pfeile und ganz viele Pfeile vorne in
die Startzustände reintun und der Pfeil und dann eine
Wahrscheinlichkeit reinschreiben in Abhängigkeit davon, in welches
Anfangswort ich reingehe.
Jetzt sind natürlich solche Unigrammsprachmodelle nicht sonderlich
mächtig.
Aber immerhin, das ist immerhin noch ein Netzwerk, das kann ich noch
einigermaßen im Griff haben.
Wenn ich da jetzt eine Strahlsuche drauf mache, solche Pfade, die ich
noch verfolge, die nenne ich dann eine Theorie.
Zum Beispiel, wenn ich hier vorne reingehe, dann kann ich mir ja schon
an der Stelle anschauen, Sprachmodellwahrscheinlichkeit drauf
multipliziert, wie sehen denn jetzt die Wahrscheinlichkeiten aus von
den Sachen, die ich noch verfolge und kann dann die Wörter sozusagen,
die jetzt schon gar nicht mehr sinnvoll sind, einfach
wegschneiden.
Und jetzt wird es kompliziert und jetzt muss ich aufpassen,
dass ich das hier sauber auf die Tafel bringe.
Weil ich jetzt nämlich hier, und wenn man sich das anschaut, das sind
ja nichts anderes als bestimmte Arten von Automaten, die wir hier
hinscheichnen.
Jetzt brauche ich ein Gedächtnis dafür, dass man nicht nur sagt, aus
welchem Wort komme ich denn raus, sondern in welchem Wort war ich denn
bitteschön vorher schon.
Ich fange also an
und brauche jetzt für jedes Wort einen Startzustand und einen
Endzustand.
Jetzt zeichnen wir nicht mehr die HMMs hin, sondern jedes Wort, das
eigentlich aus einem komplizierten HMM besteht, zeichnen wir nur noch
einen Kreis rein.
Wenn ich jetzt aus so einem Endzustand von so einem Wort rausgehe,
dann weiß ich, ich komme aus diesem Wort raus und gehe jetzt in ein
anderes Wort rein.
Das hier sei dieser Endzustand von Wort V1, das hier sei dieser
Startzustand von Wort V2.
Und was ich jetzt brauche ist, dass ich an der Stelle hinschreibe die
Wahrscheinlichkeit P von V2 gegeben V1.
Und hierzwischen ist wieder dieses HMM, das ich brauche.
Und dann muss ich halt ganz viele solche Pfeile machen.
Das hier ist das Wort WN und dann habe ich hier halt stehen P von WN
gegeben W1.
Wenn das hier das Wort WN ist und ich dann zum Beispiel nach da oben
reingehe, dann hätte ich hier halt die Sprachmodellwahrscheinlichkeit
von P von W1 kommt nach WN.
Das heißt, da wo ich mir vorher hier noch so einen Sammelzustand hätte
leisten können, weil viele Pfeile immer die gleiche
Unigrammwahrscheinlichkeit haben, kann ich das hier nicht mehr.
Sondern hier brauche ich wirklich so einen kollektiven Zustand, dass
ich diese quadratisch vielen möglichen Übergangspfeile hinzeichnen
kann.
Aber es geht noch einigermaßen.
Das kann man noch hinschreiben.
Das ist noch in Ordnung.
Also machen wir es noch schlimmer.
Wir gehen über auf Trigramme.
Und jetzt wird es richtig ekelhaft.
Was ich mir jetzt überlegen muss ist, dass ich mir ja merken muss, was
waren die zwei vorhergehenden Wörter.
Und jetzt brauche ich solche Hilfszustände.
Jetzt brauche ich so einen Hilfszustand, der mir sagt,
W1, W2 war mein vorhergehendes Wort.
Und jetzt gehe ich vorne wieder in Sozialstaatszustände ein.
Von W1, W2 bis WN.
Und an so einen Pfeil könnte ich dann zum Beispiel die
Wahrscheinlichkeit reinschreiben, dass jetzt W1 kommt.
Und vorher war ich in W1, W2.
Und das, diese Grammatikzustände, davon brauche ich jetzt n² viele.
Ich muss also, brauche W1, W1, brauche W1, W3 und so weiter bis W1,
WN.
Und dann geht das weiter los mit W2, W1, W2, W3 und so weiter, bis ich
ganz am Ende bei H, WN, WN bin.
Solche Zustände brauche ich.
Und jetzt muss ich halt entsprechend anfangen.
Ich gehe erstmal in das Wort W1 rein.
Dann gehe ich in ein zweites Wort rein.
Wenn ich den Übergang mache, habe ich erstmal nur eine
Unigrammwahrscheinlichkeit und eine Bigrammwahrscheinlichkeit.
Und dann kann ich in diesen Zustand W1, W2, W1, WN und so weiter
reingehen.
Und wenn ich dann, komme ich in dieses Ding rein.
Und wenn ich dann zum Beispiel hier in diesem Zustand W1 reingehe, ich
hatte W1 unter der Historie W1, W2 und gehe jetzt nach W1 ran, dann
wird ja hier die Historie abgeschnitten.
Dann muss der hinterher in diesem wieder übergehen, weil ich dann die
Historie W1, W1 habe und dann in irgendwas reingehe.
Wenn ich von W1, W2 gehe und jetzt nach W2 reingehe, dann habe ich
hinterher als Historie W2, W1.
Das wäre irgendwo hier unten und muss da reingehen.
Ich muss dann also dafür aufpassen, sozusagen mir dieses Gedächtnis
über die Bigrammhistorie in solchen Zuständen irgendwie
zwischenspeichern.
Und habe jetzt dann entsprechend N hoch 3 Übergänge.
Weil ich habe hier diese N Quadrat vielen Zustände und von jedem
Zustand dieser N Quadrat vielen brauche ich N Übergänge, weil ich N
mögliche Folgewörter habe.
Also N hoch 3 mögliche Übergänge aus von einem Wortende in ein neues
Wort hinein.
Und dabei darf man halt nicht vergessen, dass man zwischendurch ja
noch diese ganzen vielen Teilzustände hat, die den einzelnen HMM
-Zuständen der jeweiligen Wörter entsprechen.
Und wenn man halt hinreichend großes, einigermaßen vernünftig großes
Wörterbuch hat, größtes Vokabular für die Suche hat, dann wird dieser
Graph schon so groß, dass es schwierig wird, den überhaupt noch
explizit im Speicher zu halten.
Macht man dann meistens mit dynamischer Netzwerkgenerierung und dann
entsprechend mit einer Strahlsuche.
Oder man macht halt, wie gesagt, so eine Mehrpassstrategie, dass man
erstmal mit einem Bigrammsprachmodell eine Mehrpasssuche, eine
Strahlsuche laufen lässt, guckt, was bleibt übrig und das, was übrig
bleibt, wandle ich um, dann entsprechend in einen Suchgraphen, den ich
mit einem Trigramm- oder Viergrammmodell absuchen kann.
Und wenn man sich das jetzt anschaut, also so der Suchraum wird schon
ekelhaft, wenn ich also 100.000 Wörter habe, dann habe ich hier am
Ende 100.000 hoch drei mögliche Übergänge, die man da haben könnte.
Das ist schon verdammt viel.
Zwischendrin muss ich auch noch immer gucken, dass ich hier die
jeweiligen Zustände habe, die meinem HMM-Zustand entsprechen.
Das wird ekelhaft und das wird von der Suchzeit her schwierig, da in
halbwegs vernünftiger Zeit überhaupt zu etwas zu kommen, weil ich ja
für diese HMMs hier zwischendrin letztendlich sowas wie eine
Vorwärtssuche laufen lassen muss.
Und deswegen geht man hin und macht nochmal eine sehr radikale
Vereinfachung.
Wir verabschieden uns von der Fundamentalformel.
Wir sagen bei der Fundamentalformel jetzt nicht mehr, dass wir nach
der wahrscheinlichsten Wortfolge suchen, sondern wir sagen, das ist zu
aufwendig, das können wir nicht mehr, sondern wir suchen jetzt nur
noch nach der wahrscheinlichsten Zustandsfolge.
Muss man sich halt so vorstellen.
Da oben die Original-Fundamentalformel, Wdach, Agmax, p von W mal px
von W und das akustische Modell da oben geht über alle möglichen
Zustandsfolgen durch, die für so ein Wort möglich sind und summiert
für jede mögliche Zustandsfolge die Modellwahrscheinlichkeit für diese
Zustandsfolge auf, für alle möglichen Zustandsfolgen.
Dass das Ganze effizient geschieht, machen wir halt mit dem Forward
-Algorithmus, aber jetzt im Rahmen der allgemeinen Suche wird das zu
aufwendig und wir ersetzen diese Summe über alle möglichen
Zustandsfolgen nur noch dadurch, dass wir hier die Wahrscheinlichkeit
für die wahrscheinlichste Zustandsfolge stattdessen einsetzen.
Dementsprechend gilt halt dieses Gleichheitszeichen nicht mehr.
Das hier ist jetzt nur noch eine Approximation.
Ist ja klar, die Wahrscheinlichkeit ist ja kleiner als da oben die
Summe.
Da kommen ja immer noch zusätzliche Wahrscheinlichkeiten mit hinzu.
Nur unsere Hoffnung ist halt, dass die wahrscheinlichste Zustandsfolge
hoffentlich auch in der wahrscheinlichsten Wortfolge enthalten ist,
wenn ich sie tatsächlich richtig absuche.
Und da man jetzt halt dazu übergeht, nur noch die wahrscheinlichste
Zustandsfolge zu nehmen, nennt man das halt entsprechend dann die
Viterbi -Suche.
Was man sich jetzt halt hier spart, ist, dass man viel weniger
Informationen, viel weniger Zwischeninformationen abspeichern muss.
Vor allem, wenn man bedenkt, dass man ja hier zwischendrin das alles
machen muss.
Und wie gesagt, in der Praxis macht es meistens keinen Unterschied, da
halt die wahrscheinlichste Wortfolge auch die wahrscheinlichste
Zustandsfolge interessiert.
Jetzt macht man beim Viterbi-Decoding noch weitere kleinere
Optimierungen.
Die wahrscheinlichste Zustandsfolge interessiert uns ja gar nicht.
Uns interessiert ja nur die Wortfolge, die zu der wahrscheinlichsten
Zustandsfolge gehört.
Wenn ich den Viterbi-Algorithmus laufen lasse bei HMMs während des
Trainings oder wenn ich so Forster Lyman schreibe, dann brauche ich
Rückzeiger auf Zustandsebene.
Dann interessiert mich ja wirklich, zu welchem Zeitpunkt war ich, in
welchem Zustand.
Hier interessiert mich ja am Ende nur noch, welche Wortfolge gehört
denn zu dieser wahrscheinlichsten Zustandsfolge.
Deswegen brauche ich diese Rückzeiger auf Zustandsebene ja gar nicht
mehr zu speichern, sondern es reicht mir vollständig aus, wenn ich
diese Rückzeiger zum Beispiel auf Wortebene speichere.
Und wenn ich das mache, kann ich sehr viel Speicher sparen.
Dann kann ich umtricksen, je nachdem, welche Topologie ich habe, dass
ich wie beim One-Stage-Dynamic-Programming am Ende nur noch zwei
Frames, diesen Trellis-Ausschnitt von zwei Frames im Speicher halten
muss, plus noch eine zusätzliche Liste für die Rückzeiger auf
Wortebene.
Da, wie gesagt, Viterbi-Suche allgemein ist auch zu langsam, wenn man
sie komplett durchzieht.
Deswegen wird sie halt auch kombiniert mit einer Strahl-Suche, macht
man eine Viterbi-Suche mit Strahl.
Und so eine Viterbi-Suche ist halt auch Zeitsynchron, eignet sich
daher besonders gut für die Beschneidung mit dem Beam und ist
heutzutage der meistverwandte Algorithmus, Suchalgorithmus für den
ersten Suchlauf.
Noch ein Kommentar, wenn hier steht, Zeitsynchron eignet sich
besonders gut für Suchraumbeschneidung mit Beam, da muss man sich das
so vorstellen.
Wenn ich jetzt mit einem Beam arbeite, dann vergleiche ich ja immer
Wahrscheinlichkeit des besten aktuell expandierten Pfades mit
Wahrscheinlichkeit aller anderen bisher expandierten Pfade und
schneide die weg, die zu unwahrscheinlich sind.
Angenommen, ich würde das jetzt machen in einer Zeit-Asynchronen-Art
und Weise, also sowas wie Tiefensuche mit Beam, dann würde folgendes
passieren, je länger so ein Pfad wird, desto mehr Kosten akkumuliert
er ja auch auf, desto teurer wird er letztendlich.
Wenn ich also zum Beispiel im Log-Bereich rechne, mit jedem von dem
das hinzukommt, addiere ich ja irgendwas drauf.
Oder im Wahrscheinlichkeitsbereich, ich nehme eine Zahl und
multipliziere sie mit einer Zahl zwischen 0 und 1, also 0,8.
Das heißt, die Wahrscheinlichkeit, je mehr Phoneme, je mehr Wörter ich
drauf multipliziere, die absolute Wahrscheinlichkeit von dem Pfad wird
immer kleiner.
Das heißt, lange Pfade haben erstmal per se eine kleinere
Wahrscheinlichkeit als kurze Pfade.
Wenn ich jetzt also in der Zeit-Asynchronen-Suche mit einer
Strahlsuche arbeite, dann wird passieren, dass sich halt erstmal
irgendwelche Pfade werden wachsen und dann sind sie irgendwann zu
lang, auch wenn sie im Prinzip super passen, so ist dann doch ihre
absolute Wahrscheinlichkeit zugeklein im Vergleich zu irgendeinem
kurzen Pfad, den ich expandiert habe.
Dann werde ich erstmal die kürzeren Pfade wieder expandieren, bis die
auch zu lang sind, dann werden wieder die längeren Pfade expandiert,
aber dann werden die irgendwann wieder zu teurer, sodass ich wieder
die kürzeren Pfade expandiere.
Das Ganze krankt also daran, dass sich die Kosten von zwei Pfaden
wirklich nur fair gegeneinander vergleichen kann, wenn die Pfade die
gleiche Länge haben.
Die Heuristik, die man dann bei der Zeit-Asynchronen-Suche verwendet,
die hat das Problem nicht.
Die kompensiert diese unterschiedlichen Pfadlängen eben gerade durch
die Schätzung, wie viel kostet es denn noch von jetzt von hier nach
bis ans Ende zu kommen.
Also diesen Teil der unterschiedlichen Pfadlängen wird halt
ausgeglichen durch diese Schätzung, die ist bei der Strahlsuche nicht
vorhanden.
Deswegen eignet sich halt so eine Strahlsuche für eine Zeit-Synchrone
-Suche, weil da alle Pfade gleich lang sind.
Ich muss also nicht mehr für die für die unterschiedlichen Längen der
Pfade irgendwie kompensieren, sondern ich vergleiche Pfade
gegeneinander auf den Kosten, bei denen es auch fair ist, dass ich sie
gegeneinander vergleiche.
Wie gesagt, offiziell das am meisten verwendete für die erste Suche.
Meistens schaltet man hinterher dann noch eine zweite Suche dahinter,
zum Beispiel so eine Asternchen-Suche.
Und wenn man sich jetzt überlegt, wie man so eine Asternchen-Suche gut
implementieren kann, dann kann man so eine Asternchen-Suche ganz gut
implementieren mit etwas, das nennt sich ein Stack-Decoder.
Die Idee dabei ist halt, dass ich alle bisher expandierten Pfade, alle
partiellen Hypothesen, einfach sortiere entsprechend ihrer
akkumulierten Bewertung.
Also wie viele Kosten waren es bisher, wie viele geschätzten Kosten
sind es noch bis zum Ende.
Expandiere dann die Hypothese mit den geringsten Kosten und sortiere
die oben in diesen Stack wieder ein, an ihrer richtigen Stelle.
Entweder sie bleibt ganz oben oder sie rutscht halt in der Bewertung
dadurch, dass ich jetzt den Bereich, den ich abschätze, kleiner mache
und den Bereich, den ich tatsächlich weiß, wie viel er kostet, der
größer wird, rutscht vielleicht irgendwo im Stack weiter nach unten.
Und das mache ich halt so lange, bis ich dann irgendwann am Ende
angelangt bin.
Bis ich irgendwas aus dem Stack rausnehme, ich expandiere es, ich
komme in ein Ende rein und wenn ich das jetzt diesem vollständigen
Pfad wieder in den Stack rein sortieren würde, dann würde er oben drin
sein.
Oder anders algorithmisch ausgedrückt, wenn ich oben vom Stack einen
Pfad runternehme, den ich nicht weiter expandieren kann, weil er schon
im Ziel angekommen ist, dann ist es der Pfad mit der, mit den
geringsten Kosten, mit der höchsten Wahrscheinlichkeit.
Die Preisfrage, die wir bisher noch nicht beantwortet haben, ist
natürlich, ja was ist denn eine gute Heuristik bei der automatischen
Spracherkennung?
Also wir wollen eine Heuristik, die admissible ist, also die
tatsächlichen Kosten möglichst unterschätzt, damit sie zu einer
optimalen Lösung führt.
Was man da zum Beispiel machen kann, ist, man kann auf den
Trainingsdaten versuchen, sowas zu schätzen, wie viele Kosten, wie
viele Wahrscheinlichkeit pro Frame habe ich denn so.
Wenn ich mir also auf den Trainingsdaten das anschaue, die korrekten
Wortfolgen und die Audio Dateien, die dazugehören, die Audioaufnahmen,
dann kann ich ja ausrechnen, Wahrscheinlichkeit der gesamten Wortfolge
und kann das dann runterrechnen auf Wahrscheinlichkeit pro Frame.
Und dann gehe ich über alle Trainingsdaten drüber, die ich habe und
suche mir dann die, mit den Framen, mit den jemals geringsten Kosten
raus, mit der geringsten Wahrscheinlichkeit pro Frame.
Und wenn ich das nehme, dann kann ich davon ausgehen, dass, wenn meine
Trainingsdaten repräsentativ sind, dass ich auch dann hinterher beim
Testen die Wahrscheinlichkeiten, die Kosten auch tatsächlich
unterschätzen werde.
Kann natürlich eine sehr schlechte Heuristik sein.
Kann natürlich sein, dass die jemals gesehene, möglichst kleinste
Wahrscheinlichkeit pro Frame sehr gering war.
Und dann habe ich halt eine Heuristik, die sehr nah an dieser
schrecklichen Heuristik, restlichen Kosten gleich null dran sind.
Und dann muss ich sehr, sehr, sehr lange suchen, bin ich sehr nah dran
an der erschöpfenden Suche, an der Full-Breadth-Search.
Deswegen wäre eine andere mögliche Heuristik, dass man zum Beispiel
sagt, man nimmt halt die Durchschnittswahrscheinlichkeit pro Frame,
die ich in den Trainingsdaten gesehen habe.
Das wird dann in der Regel keine Admissible-Heuristik mehr sein.
Also die Wahrscheinlichkeit ist schon groß, dass ich dann hier und da
mal die tatsächlichen Kosten überschätze.
Ich werde also keine optimale Lösung mehr finden, nur noch hoffentlich
eine gute Lösung.
Aber kommt dann eine Laufzeit, die hoffentlich im Schnitt deutlich
schneller sein wird.
Oder eine andere Alternative, die ich haben kann, dass ich die
restlichen Kosten abschätze mit einem schwächeren, mit einem leicht zu
auszurechnenden Modell.
Sowas nennt man dann einen Fast-Match.
Was wir hier schon sehen, was wirklich, wirklich teuer ist bei N-Gramm
-Sprachmodellen mit N-Gramm höherer Ordnung.
Also sowas wie Trigramme oder Viergramme.
Also N-Gramm-Modelle, die wirklich gut funktionieren und nicht so
fürchterlich schlecht wie Bi-Gramm- oder Unigramm-Sprachmodelle.
Das wirklich Teure ist immer, wenn ich hier diesen Übergang raus mache
von einem Wort in den nächsten.
Dann habe ich hier meine N-Quadrat-Grammatik-Übergänge und an jedem
Grammatik -Übergang habe ich noch N-Folge-Übergänge dran.
Das ist also hier passiert die eigentlich wirklich große Explosion des
Suchraumes.
Und da kann man sich halt sowas überlegen, dass man zum Beispiel
schlechte Wörter möglichst schnell wegschneidet.
Dass man zum Beispiel mit Hilfe eines Unigramm-Modells versucht
abzuschätzen, was sind gute, was sind schlechte Wort-Übergänge und
dann die Anzahl der möglichen Wort-Übergänge nur noch einschränkt.
Sodass ich dann hier nicht N hoch 3 habe, sondern eine konstante Zahl.
Irgendwas, das was mir laut Unigramm... bei Unigramm muss ich halt
hier nicht N hoch 3-Übergänge berechnen, sondern nur N-Übergänge.
Dann behalte ich nur das übrig, was mir nach Unigramm sinnvoll
erscheint.
1000 Stück behalte ich übrig.
Da rechne ich hinterher, wenn ich sie mache, dann auch die Trigramm
-Wahrscheinlichkeit wieder drauf.
Aber für die Vorauswahl nehme ich nur ein Unigramm.
Oder meinem HMM kann ich auch sowas machen, wie statt mit einem
Trifon, Quinfon-Modell mit ganz vielen Gauss-Glocken zu arbeiten, habe
ich irgendwie ein kontextunabhängiges HMM, das auf vektorquantisierten
Eingabevektoren funktioniert, das ich ganz schnell ausrechnen kann.
Und kann damit eine vernünftige Abschätzung machen, wie viel Kosten
habe ich noch bis zum Ende.
Und das Ganze sehr schnell ausrechnen, als wenn ich jetzt hier mit
ganz vielen komplizierten Quinfon-Akustischen Modellen rechnen wollte.
Gut, das machen wir dann, fangen wir dann an, uns nächste Woche
anzuschauen, wie jetzt sich der A-Sternchen gegen so ein Beam-Search
dann hinterher in der Praxis schlägt.
Das machen wir dann am Mittwoch, schauen wir uns das an.