imported>Invisigoth67: typo

2024-08-16T15:24:46Z

typo

Neue Seite

Der '''Viterbi-Algorithmus''' ist ein [[Algorithmus]] der [[Dynamische Programmierung|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 [[Faltungscode]]s entwickelt, er fiel quasi als Nebenprodukt bei der Analyse der Fehlerwahrscheinlichkeit von Faltungscodes ab. G. D. Forney leitete daraus 1972 den [[Optimalfilter|Optimalempfänger]] für verzerrte und gestörte Kanäle her. Der Viterbi-Algorithmus wird heutzutage zum Beispiel in [[Mobiltelefon]]en oder [[Wireless LAN]]s zur [[Fehlerkorrektur]] der [[Funkübertragung]] verwendet, ebenso in [[Festplatte]]n, 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 <math>\lambda=(S;V;A;B;\pi)</math> mit
*<math>S</math> – Menge der verborgenen Zustände
*<math>V</math> – [[Alphabet (Informatik)|Alphabet]] der beobachtbaren Symbole (Emissionen)
*<math>A</math> – [[Übergangsmatrix|Zustandsübergangsmatrix]]
*<math>B</math> – Beobachtungsmatrix
*<math>\pi</math> – Anfangswahrscheinlichkeitsverteilung

== Aufgabenstellung ==
Sei <math>\boldsymbol o = o_1 o_2 \ldots o_T \in V^*</math> die beobachtete Sequenz von Symbolen.
Es soll die wahrscheinlichste Zustandsfolge <math>\boldsymbol q^* = q^*_1 q^*_2 \ldots q^*_T \in S^T</math> berechnet werden.
Also diejenige Sequenz von verborgenen Zuständen, die unter allen Folgen <math>\boldsymbol q</math> der Länge <math>T</math> den Wert von <math>P(\boldsymbol q|\boldsymbol o; \lambda)</math> maximiert, das ist die Wahrscheinlichkeit, dass das Modell <math>\lambda</math> bei Erzeugung der Ausgabe <math>\boldsymbol o</math> durch die Zustände <math>\boldsymbol q</math> gelaufen ist.

Nach den Rechenregeln für [[bedingte Wahrscheinlichkeit]]en gilt:
:<math>P(\boldsymbol q|\boldsymbol o;\lambda) = \frac{P(\boldsymbol o;\boldsymbol q|\lambda)}{P(\boldsymbol o|\lambda)} </math>
Da außerdem <math>P(\boldsymbol o|\lambda)</math> nicht von <math>\boldsymbol q</math> abhängt, ergibt sich folgender Zusammenhang:
:<math>P(\boldsymbol o;\boldsymbol q^*|\lambda) = \max_{\boldsymbol q \in S^T} P(\boldsymbol o;\boldsymbol q|\lambda)</math>

Für die eigentliche Berechnung werden nun zwei verschiedene Arten von Variablen – <math>\vartheta_t(i)</math> und <math>\psi_t(i)</math> – verwendet:

In <math>\vartheta_t(i)</math> ist die maximale [[Multivariate Verteilung|Verbundwahrscheinlichkeit]] gespeichert zum Zeitpunkt <math>1 \le t \le T</math> bei der Beobachtung des [[Wort (Theoretische Informatik)#Präfix|Präfixes]] <math>o_1 o_2 \ldots o_t</math> durch eine Zustandsfolge der Länge <math>t</math> gelaufen zu sein und im Zustand <math>s_i \in S</math> zu enden:
:<math>\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)</math>
Die Variable <math>\psi_t(i)</math> dagegen merkt sich für jeden Zeitpunkt und jeden Zustand, welcher Vorgängerzustand an der Maximumsbildung beteiligt war.

== Algorithmus ==
Die Variablen <math>\vartheta_t(i)</math> sowie <math>\psi_t(i)</math> lassen sich rekursiv bestimmen:

;Initialisierung
:<math>\vartheta_1(i) = \pi_i \cdot b_i(o_1),\ \psi_1(i) = 0, \qquad 1 \le i \le \left| S \right|</math>

;Rekursion
Für <math>\ 1 < t \le T</math> berechne
:<math>
\begin{align}
\vartheta_t(i) &= b_i(o_t)\ \cdot\ \max_{1 \le j \le \left|S\right|} (a_{ji}\ \cdot\ \vartheta_{t-1}(j)), \qquad 1 \le i \le \left| S \right|\\
\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|
\end{align}
</math>

;Terminierung
:<math>
\begin{align}
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)
\end{align}
</math>

;Pfadermittlung
:<math>q^*_t = \psi_{t+1}(q^*_{t+1}), \qquad 1 \le t < T</math>

== Komplexität ==
Die Tabelle der <math>\vartheta_t(i)</math> benötigt <math>O(\left| S \right| \cdot T)</math> Speicher, die Matrix der <math>\psi_t(i)</math> ist von gleichem Umfang.
Für jede Zelle der beiden Matrizen wird über <math>\left| S \right|</math> Alternativen optimiert, also ist die Laufzeit in <math>O(\left| S \right|^2 T)</math>.

Um den Speicherplatz zu halbieren, kann der Pfad <math>\boldsymbol q^*</math> alternativ auch nach der Terminierung durch [[Backtracking]] in der Matrix aller <math>\vartheta_t(i)</math> – also ohne die zusätzlichen Variablen <math>\psi_t(i)</math> – ermittelt werden.
Da aber in der Praxis die Berechnung von <math>\psi_t(i)</math> 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 [[Mustererkennung|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ünstliche Intelligenz|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 (Genetik)|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 ==
* [[Forward-Algorithmus]]
* [[Backward-Algorithmus]]
* [[Baum-Welch-Algorithmus]]

== Literatur ==
* {{Literatur
|Autor=A. Viterbi
|Titel=Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
|Sammelwerk=IEEE Transactions on Information Theory
|Jahr=1967
|ISSN=0018-9448
|Seiten=260–269
|Band=13
|Nummer=2
|Online=[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?isnumber=22634&arnumber=1054010 IEEE Xplore]
|DOI=10.1109/TIT.1967.1054010
}}
* {{Literatur
|Autor=Durbin et al.
|Titel=Biological sequence analysis
|Verlag=Cambridge
|Jahr=2006
|ISBN=0-521-62971-3
|Seiten=56
}}
* {{Literatur
|Autor=Forney Jr., G. D.
|Titel=The Viterbi Algorithm.
|Sammelwerk=In Proceedings of the IEEE
|Jahr=1973
|Seiten=268–278
|Band=61
|Nummer=3
|Online=[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1450960 IEEE Xplore]
|DOI=10.1109/PROC.1973.9030
}}

== Weblinks ==
* [http://home.netcom.com/~chip.f/Viterbi.html Erklärung des Viterbi-Algorithmus für Faltungscodes] (englisch)
* {{Scholarpedia|http://www.scholarpedia.org/article/Viterbi_algorithm|Viterbi algorithm|Andrew J. Viterbi}}
* E.G. Schukat-Talamazzini: [http://www.minet.uni-jena.de/fakultaet/schukat/MAS/Scriptum/lect05-HMM.pdf ''Spezielle Musteranalysesysteme''] (PDF, 1,3 MB) Vorlesung im WS 2012/13 an der Universität Jena. Kapitel 5 Folie 39 ff.

[[Kategorie:Computerlinguistik]]
[[Kategorie:Dynamische Programmierung]]
[[Kategorie:Künstliche Intelligenz]]
[[Kategorie:Nachrichtentechnik]]
[[Kategorie:Optimierungsalgorithmus]]

Viterbi-Algorithmus - Versionsgeschichte

imported>Invisigoth67: typo