Viterbi-Algorithmus

Der Viterbi-Algorithmus ist ein Algorithmus der dynamischen Programmierung zur Bestimmung der wahrscheinlichsten Sequenz von verborgenen Zuständen bei einem gegebenen Hidden Markov Model (HMM) und einer beobachteten Sequenz von Symbolen. Diese Zustandssequenz wird auch als Viterbi-Pfad bezeichnet.

Er wurde von Andrew J. Viterbi 1967 zur Dekodierung von Faltungscodes entwickelt, er fiel quasi als Nebenprodukt bei der Analyse der Fehlerwahrscheinlichkeit von Faltungscodes ab. G. D. Forney leitete daraus 1972 den Optimalempfänger für verzerrte und gestörte Kanäle her. Der Viterbi-Algorithmus wird heutzutage zum Beispiel in Mobiltelefonen oder Wireless LANs zur Fehlerkorrektur der Funkübertragung verwendet, ebenso in Festplatten, da bei der Aufzeichnung auf die Magnetplatten ebenfalls Übertragungsfehler entstehen.

Der Algorithmus ist in der Nachrichtentechnik und Informatik weit verbreitet: Die Informationstheorie, Bioinformatik, Spracherkennung und Computerlinguistik verwenden häufig den Viterbi-Algorithmus.

Hidden Markov-Modell

Gegeben sei ein HMM $\lambda =(S;V;A;B;\pi )$ mit

$S$ – Menge der verborgenen Zustände
$V$ – Alphabet der beobachtbaren Symbole (Emissionen)
$A$ – Zustandsübergangsmatrix
$B$ – Beobachtungsmatrix
$\pi$ – Anfangswahrscheinlichkeitsverteilung

Aufgabenstellung

Sei ${\boldsymbol {o}}=o_{1}o_{2}\ldots o_{T}\in V^{*}$ die beobachtete Sequenz von Symbolen. Es soll die wahrscheinlichste Zustandsfolge ${\boldsymbol {q}}^{*}=q_{1}^{*}q_{2}^{*}\ldots q_{T}^{*}\in S^{T}$ berechnet werden. Also diejenige Sequenz von verborgenen Zuständen, die unter allen Folgen ${\boldsymbol {q}}$ der Länge $T$ den Wert von $P({\boldsymbol {q}}|{\boldsymbol {o}};\lambda )$ maximiert, das ist die Wahrscheinlichkeit, dass das Modell $\lambda$ bei Erzeugung der Ausgabe ${\boldsymbol {o}}$ durch die Zustände ${\boldsymbol {q}}$ gelaufen ist.

Nach den Rechenregeln für bedingte Wahrscheinlichkeiten gilt:

P({\boldsymbol {q}}|{\boldsymbol {o}};\lambda )={\frac {P({\boldsymbol {o}};{\boldsymbol {q}}|\lambda )}{P({\boldsymbol {o}}|\lambda )}}

Da außerdem $P({\boldsymbol {o}}|\lambda )$ nicht von ${\boldsymbol {q}}$ abhängt, ergibt sich folgender Zusammenhang:

P({\boldsymbol {o}};{\boldsymbol {q}}^{*}|\lambda )=\max _{{\boldsymbol {q}}\in S^{T}}P({\boldsymbol {o}};{\boldsymbol {q}}|\lambda )

Für die eigentliche Berechnung werden nun zwei verschiedene Arten von Variablen – $\vartheta _{t}(i)$ und $\psi _{t}(i)$ – verwendet:

In $\vartheta _{t}(i)$ ist die maximale Verbundwahrscheinlichkeit gespeichert zum Zeitpunkt $1\leq t\leq T$ bei der Beobachtung des Präfixes $o_{1}o_{2}\ldots o_{t}$ durch eine Zustandsfolge der Länge $t$ gelaufen zu sein und im Zustand $s_{i}\in S$ zu enden:

\vartheta _{t}(i)=\max _{{\boldsymbol {q}}\in S^{t} \atop q_{t}=s_{i}}P(o_{1}o_{2}\ldots o_{t};q_{1}q_{2}\ldots q_{t}|\lambda )

Die Variable $\psi _{t}(i)$ dagegen merkt sich für jeden Zeitpunkt und jeden Zustand, welcher Vorgängerzustand an der Maximumsbildung beteiligt war.

Algorithmus

Die Variablen $\vartheta _{t}(i)$ sowie $\psi _{t}(i)$ lassen sich rekursiv bestimmen:

Initialisierung: $\vartheta _{1}(i)=\pi _{i}\cdot b_{i}(o_{1}),\ \psi _{1}(i)=0,\qquad 1\leq i\leq \left|S\right|$

Rekursion

Für $\ 1<t\leq T$ berechne

{\begin{aligned}\vartheta _{t}(i)&=b_{i}(o_{t})\ \cdot \ \max _{1\leq j\leq \left|S\right|}(a_{ji}\ \cdot \ \vartheta _{t-1}(j)),\qquad 1\leq i\leq \left|S\right|\\\psi _{t}(i)&={\underset {1\leq j\leq \left|S\right|}{\operatorname {argmax} }}\ (a_{ji}\ \cdot \ \vartheta _{t-1}(j)),\qquad 1\leq i\leq \left|S\right|\end{aligned}}

Terminierung: ${\begin{aligned}P({\boldsymbol {o}};{\boldsymbol {q}}^{*}|\lambda )&=\max _{1\leq j\leq \left|S\right|}\vartheta _{T}(j)\\q_{T}^{*}&={\underset {1\leq j\leq \left|S\right|}{\operatorname {argmax} }}\ \vartheta _{T}(j)\end{aligned}}$

Pfadermittlung: $q_{t}^{*}=\psi _{t+1}(q_{t+1}^{*}),\qquad 1\leq t<T$

Komplexität

Die Tabelle der $\vartheta _{t}(i)$ benötigt $O(\left|S\right|\cdot T)$ Speicher, die Matrix der $\psi _{t}(i)$ ist von gleichem Umfang. Für jede Zelle der beiden Matrizen wird über $\left|S\right|$ Alternativen optimiert, also ist die Laufzeit in $O(\left|S\right|^{2}T)$ .

Um den Speicherplatz zu halbieren, kann der Pfad ${\boldsymbol {q}}^{*}$ alternativ auch nach der Terminierung durch Backtracking in der Matrix aller $\vartheta _{t}(i)$ – also ohne die zusätzlichen Variablen $\psi _{t}(i)$ – ermittelt werden. Da aber in der Praxis die Berechnung von $\psi _{t}(i)$ keinen Mehraufwand verursacht, verlängert sich die benötigte Rechenzeit bei dem Backtracking-Ansatz geringfügig.

Anwendungen

Der Viterbi-Algorithmus ist der optimale Algorithmus zur Dekodierung von Faltungscodes im Sinne der Blockfehlerrate (maximum likelihood sequence estimation). Der im Sinne der Symbolfehlerrate optimale Dekodieralgorithmus ist der BCJR-Algorithmus.

Wie man aus der Beschreibung des Algorithmus sieht, kann er fast überall eingesetzt werden, um Muster zu erkennen. Das ist ein weites Feld, da Lebewesen ständig Sinnesreize interpretieren müssen und aus dem bereits Gelernten diese Signale einordnen. Der Viterbi-Algorithmus tut genau das auch und ist somit ein wichtiger Baustein der Künstlichen Intelligenz.

Einen wichtigen Stellenwert nimmt der Algorithmus in der Bioinformatik ein, denn anhand des Viterbi-Algorithmus kann unter anderem von der tatsächlichen Sequenz eines DNA-Abschnitts auf eventuelle versteckte Zustände geschlossen werden. So kann zum Beispiel untersucht werden, ob es sich bei einer vorliegenden Sequenz wahrscheinlich um ein bestimmtes Strukturmotiv handelt (CpG-Insel, Promotor, …) oder nicht. Vorteil dieses rekursiven Algorithmus ist hierbei der linear mit der Sequenzlänge steigende Aufwand im Gegensatz zum exponentiellen Aufwand des zugrundeliegenden Hidden Markov Model.

Siehe auch

Literatur

A. Viterbi: Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. In: IEEE Transactions on Information Theory. Band 13, Nr. 2, 1967, ISSN 0018-9448, S. 260–269, doi:10.1109/TIT.1967.1054010 (IEEE Xplore).
Durbin et al.: Biological sequence analysis. Cambridge, 2006, ISBN 0-521-62971-3, S. 56.
Forney Jr., G. D.: The Viterbi Algorithm. In: In Proceedings of the IEEE. Band 61, Nr. 3, 1973, S. 268–278, doi:10.1109/PROC.1973.9030 (IEEE Xplore).

Weblinks

Erklärung des Viterbi-Algorithmus für Faltungscodes (englisch)
Andrew J. Viterbi: Viterbi algorithm. In: Scholarpedia. (englisch, inkl. Literaturangaben)
E.G. Schukat-Talamazzini: Spezielle Musteranalysesysteme (PDF, 1,3 MB) Vorlesung im WS 2012/13 an der Universität Jena. Kapitel 5 Folie 39 ff.