Viterbi Algorithm
Der Viterbi-Algorithmus nutzt dynamische Programmierung, um die wahrscheinlichste Folge verborgener Zustände eines HMM zu finden, ohne alle Pfade aufzuzählen.
Zweck
Den optimalen Zustandspfad eines HMM effizient dekodieren; verwendet in Spracherkennung und NLP.
Mechanismus
Vorwärtsrekursion δ_t(j)=max_i[δ_{t-1}(i)*a_{ij}]*b_j(o_t), wobei der beste Vorgänger ψ_t(j) notiert wird. Das Backtracking startet beim größten δ_T zum Zeitpunkt T und folgt ψ, um den optimalen Pfad zurückzugewinnen. Komplexität O(TN^2).
Anwendungsfälle
- Spracherkennung
- Wortartenerkennung
- Analyse biologischer Sequenzen