Viterbi-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 Handys 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.

Markov-Modell[Bearbeiten]

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

  • S – Menge der verborgenen Zustände
  • VAlphabet der beobachtbaren Symbole (Emissionen)
  • AZustandsübergangsmatrix
  • B – Beobachtungsmatrix
  • \pi – Anfangswahrscheinlichkeitsverteilung

Aufgabenstellung[Bearbeiten]

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 \le t \le 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[Bearbeiten]

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 \le i \le \left| S \right|
Rekursion
\vartheta_t(i) = b_i(o_t)\ \cdot\ \max_{1 \le j \le \left|S\right|} (a_{ji}\ \cdot\ \vartheta_{t-1}(j)),\ \psi_t(i) = \underset{{1 \le j \le \left|S\right|}}{\operatorname{argmax}}\ (a_{ji}\ \cdot\ \vartheta_{t-1}(j)), \qquad 1 \le i \le \left| S \right|,\ 1 < t \le T
Terminierung
P(\boldsymbol o;\boldsymbol q^*|\lambda) = \max_{1 \le j \le \left|S\right|} \vartheta_T(j),\ q^*_T = \underset{{1 \le j \le \left|S\right|}}{\operatorname{argmax}}\ \vartheta_{T}(j)
Pfadermittlung
q^*_t = \psi_{t+1}(q^*_{t+1}), \qquad 1 \le t < T

Komplexität[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

Weblinks[Bearbeiten]

Literatur[Bearbeiten]

  •  A. Viterbi: Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. In: IEEE Transactions on Information Theory. 13, Nr. 2, 1967, ISSN 0018-9448, S. 260-269 (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. 61, Nr. 3, 1973, S. 268-278 (IEEE Xplore).