Automatische Spracherkennung: Hidden-Markov-Modell - Kapitel 10/11

Grundlagen der automatischen Spracherkennung

• Kapitel 10 behandelt Hidden-Markov-Modelle

Überblick

• Die Präsentation behandelt zunächst eine Wiederholung von DNNs (Deep Neural Networks).
• Es erfolgt eine Betrachtung des Einsatzes von DNNs zur Spracherkennung.
• Abschließend wird die Transkription von Zeitreihen behandelt.

Recap: Training von DNNs

• Tiefe neuronale Netze (DNNs) eignen sich hervorragend zur Approximation komplexer Funktionen.
• DNNs werden durch maschinelles Lernen an ihre Aufgaben angepasst.
• Bei der Klassifikation schätzen Netze am Ausgang typischerweise eine Verteilungsdichte über alle Klassen.
• Das Training von DNNs beinhaltet Feature Extraction, Verarbeitung durch ein neuronales Netz, Bewertung durch eine Kostenfunktion und Parameteradaption.
• Der Trainingsablauf wird anhand der Performance auf Trainings- und Validierungsdaten ("Development Data / dev set") verfolgt.
• Die Auswertung erfolgt erst am Schluss auf Testdaten.

Einzelworterkennung mit DNNs

• Einzelworterkennung kann wie eine normale Klassifikation implementiert werden.
• DNNs können wie zuvor benutzt werden.
• Die Struktur eines Klassifikationssystems umfasst Audio, Feature Extraction, Merkmale, DNN und Klassenwahrscheinlichkeiten
• Stattdessen wird eine Lösung zur Transkription einer Zeitreihe benötigt.

Transkription statt Klassifikation

• Klassifikation kann kaum direkt zur Transkription genutzt werden, da die unbekannten zeitlichen Grenzen der Ausgangssequenz nicht klar definiert sind.
• Dies führt zu einer kombinatorischen Explosion der Anzahl von Möglichkeiten.
• Eine Lösung hierfür sind hybride DNN/HMM-Modelle.

Hybride DNN/HMM-Modelle

• Es erfolgt ein Training eines DNN, das zu jeder Zeit die Wahrscheinlichkeit aller elementaren akustischen Einheiten (z.B. Phoneme) schätzt.
• Die wahrscheinlichste Abfolge akustischer Einheiten wird durch Pfadsuche mit dynamischer Programmierung gefunden.
  • Wobei es sich um einen zulässigen Satz handelt
  • Wobei es sich aus gültigen Worten ergibt.

Markov-Ketten

• Markov-Ketten erster Ordnung sind stochastische Zustandsraummodelle mit einer zeit- und wertdiskreten Zustandsgröße X.
• Der Zustand des Modells zur Zeit t wird als Zufallsvariable Xt notiert.
• Die Übergangswahrscheinlichkeit wird durch ajj = P(Xt+1 = j|Xt = i) beschrieben.
• Die Übergangsmatrix A enthält die Übergangswahrscheinlichkeiten zwischen den Zuständen
• Die initialen Wahrscheinlichkeiten werden durch P(X₁ = i) = π¡ beschrieben.

Wahrscheinlichkeit von Zustandssequenzen

• Die Wahrscheinlichkeit einer Zustandssequenz wird durch die Formel P(X₁ = i₁, X₂ = i2, ..., XT = iT) mit i₁, i2, ..., iT ∈ {1...N} ausgedrückt.
• Unter Anwendung der Markov-Annahme erster Ordnung ergibt sich P(i₁, i₂, ..., iT) = P(i₁)P(i₂|i₁)P(i₃|i₂, ..., iT-1).
• Durch die Definition des HMM wird diese Formel zu πi₁ · ai₁,i₂ · ai₂,i₃ · ... · aₑ-1i
• Was als -T-1 -πi₁· Π t=1 ait,it+1 geschrieben werden kann

Hidden Markov Model (HMM)

• In Hidden-Markov-Modellen ist der Zustand selbst nicht sichtbar.
• Zusätzlich gibt es Beobachtungswahrscheinlichkeiten B = {bi} mit bi(o) = P(Ot = o|Xt = i).

Beobachtungswahrscheinlichkeiten in Hidden-Markov-Modellen

• Diskrete Verteilungsdichten: Die Menge möglicher Beobachtungen ist o ∈ {o¹... ok}, und die Wahrscheinlichkeiten sind bi(o) = P(Ot = o|Xt = i).
  • Die diskrete Verteilungsdichte ist recheneffizient
• Kontinuierliche Verteilungsdichten o ∈ RD: Gauß'sche Mischungsmodelle werden verwendet
  • bi(o) = P(Ot = o|Xt = i) = ΣMm=1 γmN(o; μim, Σim), wobei M typischerweise 16 bis 256 ist. Gauß'sche Mischungsmodelle sind geeignet zur Approximation beliebiger PDF

Neuronal geschätzte Verteilungsdichten

• Ot → DNN → P̂(Xt = 1|o) ... P̂(Xt = N|o)
• P(o|Xt = i) = P(Xt = i|o)P(o) / P(Xt = i) ≈ P̂(Xt = i|o)P(o) / P(Xt = i) α P̂(Xt = i|o) / P(Xt = i) = bi(0)
• Dies wird als "Hybrid-Modell" oder "DNN-HMM-Hybridmodell" bezeichnet.

Hidden-Markov-Modelle (Parameter)

• Der Parametersatz für ein HMM ist λ = {A, B, Π}, wobei A die Übergangsmatrix, B die Beobachtungswahrscheinlichkeiten und Π die initialen Wahrscheinlichkeiten sind.

HMM-Struktur für Wortmodelle

• Nur Links-Rechts-Topologien sind interessant, z.B.:
  • Lineares HMM
  • Links-Rechts-HMM
  • Bakis-Modell

Varianten zur Verbundworterkennung

• Klassisches Verbund-HMM: Transitionen direkt vom Wortende zum Wortanfang, was zu vielen Transitionen zwischen allen Wortpaaren führt
• Verbund-HMM mit Glue-State: Der Glue-State definiert keine Beobachtungswahrscheinlichkeiten.
  • Vorteile: Weniger Transitionen, aber Anpassung der Algorithmen ist nötig
  • Schleifen zwischen Glue-States sind verboten, und die Zeitzählung muss angepasst werden.

Kernprobleme bei Hidden-Markov-Modellen

• Es gibt 3 Hauptprobleme
  • Training von HMMs
    • Beim Modelltraining werden die Modellparameter gelernt λ = {А, П, В}
  • Evaluation von HMMs
    • Hierbei wird die Wahrscheinlichkeit einer Beobachtungssequenz berechnet P(o₁... oТ|λ).
    • Was nützlich im Training sein kann
  • "Decodierung" von HMMs
    • Hierbei geht es darum, zu ermitteln, die beste oder am wahrscheinlichste Zustandssequenz zu finden, wobei der Algorithmus zum Einsatz kommt
• Gesucht: [i1, i2, ..., i*T ]=argmax P(i₁i₂,...,iТ,o₁...,oТ|λ)
  • Dabei i₁, i₂, ..., iT

Dekodierproblem

• Gesucht: Wahrscheinlichste Sequenz von Zuständen [i₁*, i₂*, ..., iT*]
  • So dass [i₁*, i₂*, ..., iT*] = argmax P(i₁, i₂,..., iT, o₁..., oT|λ)
    • wobei i₁, i₂, ..., iT
• Der Sinn diese Problems ist nicht auf den ersten Blick offensichtlich

Gesucht: Optimale Zustandssequenz

• [i1, i2, ..., i*T ]=argmax P(i₁,...,iТ,o₁,...,oТ|λ)
  • Der argmaxP(i₁,i₂,...,iT|λ)P(o₁, o₂,...,oТ|i₁, i₂,...,iТ, λ)
    • Wobei P(i₁,i₂,...,iT|λ)= πi₁ai₁i₂ai₂i₃... aiТ‐₁i T
    • Und P(o₁, o₂,...,oТ|i₁, i₂,...,iТ, λ)= bi₁(o₁)bi₂(o₂)... biТ(oТ)
• Was zu einer exponentiellen Komplexität führt(5100 × 199 Multiplikationen → 1,5 × 1072 !)
• Eine Reduktion dieser Komplexität, erfolgt durch dynamische Programmierung → Viterbi-Algorithmus (≈ N²T + NT → 3000 Multiplikationen)

Viterbi-Algorithmus

• Der Viterbi-Algorithmus nutzt dynamische Programmierung zur Ermittlung optimaler Zustandssequenzen.
• Kern des Algorithmus ist die Entwicklung einer Teillösungen durch sukzessive Berechnung von immer grösseren Teillösungen
• Hierbei sind die Teillösungen: Partiell beste Pfadwahrscheinlichkeiten
  • Φ₁(i) = max P(o₁...ot, i₁,..., it-1, X₁ = ilλ)
• Ablauf zur Berechnung der optimalen Zustandssequenz
  • Speicherung von Φτ(i)
  • Initialisierung
    • Φ₁(i) = P(X₁ = i, o₁λ) = πibi(o₁)
    • Der beste Vorgänger ist Ψ₁(i) = −1
  • Iteration Vt = [2,..., T]
    • Φ₁(i) = max [Φt-1 (j)aji] bi(ot)
    • Ψ₁(i) = argmax[Φt-1(j)aji]
  • Terminierung
    • i*T = argmax ΦT(i)
    • P* = P(i1, i2, ..., iT, o₁,..., oT|λ) = ΦT(iT)
  • Backtracking
    • it-1 = Ψt(it)
    • Vt = T...2

Überblick Viterbi-Algorithmus in logarithmischer Rechnung

• Φt(i) ist der maximale Pfadwahrscheinlichkeit bis Zeitpunkt t unter der Bedingung, dass der Zustand zu diesem Zeitpunkt i ist
• Initialisierung
  • Φ₁(i) = log(πi) + log(bi(01))
  • Ψ₁(i) = −1
    • (Backpointer)
• Iteration: Für jeden Zeitpunkt t von 2 bis T
  • Φt(i) = maxj=1...N[Φt-1(j) + log(aji)] + log(bi(ot))
  • Ψt(i) = argmaxj=1...N[Φt-1(j) + log(aji)]
    • wobei der Algorithmus sich auf die Backpointer bezieht
• Terminierung:
  • log (P*(o/λ)) = maxi=1...N ΦT(j)
  • Was i*/t = argmaxj=1...N ΦT(j) ergibt
• Backtracking
  • Was i*/t-1 = Ψt(i*/t1)
    • Die beste Zustandsfolge wird rekonstruiert

Effekte logarithmischer Rechnung

• Weniger numerische Probleme (bes. bezüglich Underflow).
• Neue Implementierungsfrage: log(0)
• Mögliche Lösungen:
  • Rechnen mit -Inf.
  • Eingabe in log limitieren: log(0) ≈ log(e) / Kandidat für e: sys.float_info.min.
  • Statt log(0) als Konstante logzero große negative Zahl wählen / Was darstellbar ist, erfährt man mit sys.float_info.max oder für numpy mit np.nextafter(-np.inf, 0).

Hybride DNN/HMM-Modelle (Zusammenfassung)

• In einer hybriden DNN/HMM Struktur erfolgt
  • Audio → 1. Feature Extraction → Ot → 2. DNN → P̂ → 3. HMM-Decoder → W1...WN
• Es eignet sich zur Erkennung fließend gesprochener Sprache & kombiniert die Vorteile beider "Welten" maschinellen Lernens:
  • DNNs sind flexibel und mittels Backprop so trainierbar, dass sie die jeweilige Aufgabenstellung optimal erfüllen
  • HMMs bieten Inferenzalgorithmen, die linear in der Sequenzlänge sind, und können die Struktur der Aufgabenstellung menschenlesbar beschreiben.