Viterbi

Viterbi

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

Er wurde von Andrew J. Viterbi (* 9. März 1935 in Bergamo, Italien, eigentlich Andrea 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 Entzerrung oder Fehlerkorrektur der Funkübertragung verwendet. Ebenso in Festplatten, da bei der Aufzeichnung auf die Magnetplatten ebenfalls Verzerrungen entstehen.

Der Algorithmus ist in der Nachrichtentechnik und Informatik weit verbreitet: Die Informationstheorie, Spracherkennung, Bioinformatik und Computerlinguistik verwenden gerne den Viterbi-Algorithmus. Spracherkennung ohne diesen Algorithmus wäre schwer zu realisieren.

Inhaltsverzeichnis

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.

Algorithmus

Gegeben ist ein HMM M = (Σ,Q,A,E,π), wobei

  • Σ das Alphabet der beobachtbaren Symbole bezeichnet
  • Q die Menge der verborgenen Zustände bezeichnet
  • A die Matrix der Zustandsübergangswahrscheinlichkeiten bezeichnet. Für i,j\in Q ist in der Zelle aij die Wahrscheinlichkeit für den Übergang von Zustand i nach j gespeichert.
  • E die Matrix der Emissionswahrscheinlichkeiten bezeichnet. In der Zelle e_{ix},\, i\in Q,\, x\in\Sigma ist die Wahrscheinlichkeit gespeichert, dass im Zustand i das beobachtete Zeichen x ausgegeben wird.
  • Der Vektor π, der für jeden Zustand die Wahrscheinlichkeit, dass in diesem Zustand gestartet wird, enthält.

u ist die gesuchte Sequenz von verborgenen Zuständen. Die Eingabe ist die beobachtete Sequenz von Symbolen m.

Initialisierung

V[s, 1] = e_{s m[1]} \pi_s,\qquad s\in Q

Rekursion

V[s, i] = e_{s m[i]} \max_{t\in Q} a_{ts} V[t,i-1],\qquad s\in Q, 1<i\le |m|

Terminierung

P(u|m) = \max_{s\in Q} V[s, |m|]

Pfadermittlung

Der Pfad u kann durch Backtracking in der Matrix V ermittelt werden. Z.B. kann während der Berechnung von V für jede Zelle vermerkt werden, welche Zellen an dem Maximum beteiligt sind. In einer Backtracking-Phase kann diese Information von argmax_{s\in Q} V[s, |m|] aus verfolgt werden.

Komplexität

Die Tabelle V benötigt O( | m | | Q | ) Speicher. Für jede Zelle wird über | Q | Alternativen optimiert. Also ist die Laufzeit in O( | m | | Q | 2).

Veranschaulichung

Markowkette

Es bedeuten:

x – (versteckte) Zustände des Markov-Modells
a – Übergangswahrscheinlichkeiten
b – Emissionswahrscheinlichkeiten
y – (sichtbare) Ausgabesymbole

Siehe auch

Weblinks

Literatur

  • 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). 

Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Viterbi — can mean:*Viterbi algorithm, an algorithm in signal processing. *Viterbi decoder, a device implementing the above algorithm. *Andrew Viterbi, the inventor of the above algorithm. *Viterbi School of Engineering, located at the University of… …   Wikipedia

  • Viterbi — puede hacer referencia a: Algoritmo de Viterbi, un algoritmo en procesado de señales. Andrew Viterbi, ingeniero italiano, inventor del algoritmo mencionado. Esta página de desambiguación cataloga artículos relacionados con el mismo título. Si… …   Wikipedia Español

  • Viterbi algorithm — The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states ndash; called the Viterbi path ndash; that results in a sequence of observed events, especially in the context of Markov information… …   Wikipedia

  • Viterbi decoder — A Viterbi decoder uses the Viterbi algorithm for decoding a bitstream that has been encoded using forward error correction based on a convolutional code. There are other algorithms for decoding a convolutionally encoded stream (for example, the… …   Wikipedia

  • Viterbi-Algorithmus — Der Viterbi Algorithmus ist ein Algorithmus der Dynamischen Programmierung zur Bestimmung der wahrscheinlichsten Sequenz von versteckten Zuständen bei einem gegebenen Hidden Markov Model und einer beobachteten Sequenz von Symbolen. Diese… …   Deutsch Wikipedia

  • Viterbi School of Engineering — The Viterbi School of Engineering (formerly the USC School of Engineering) is located at the University of Southern California in the United States. It was renamed following a $52 million donation by Andrew Viterbi. The USC Viterbi School of… …   Wikipedia

  • Viterbi decoder chip — Viterbio dekoderio lustas statusas T sritis radioelektronika atitikmenys: angl. Viterbi decoder chip vok. Viterbi Dekoder Chip, n rus. кристалл ИС декодера Витерби, m pranc. décodeur Viterbi, m …   Radioelektronikos terminų žodynas

  • Viterbi-Dekoder-Chip — Viterbio dekoderio lustas statusas T sritis radioelektronika atitikmenys: angl. Viterbi decoder chip vok. Viterbi Dekoder Chip, n rus. кристалл ИС декодера Витерби, m pranc. décodeur Viterbi, m …   Radioelektronikos terminų žodynas

  • Viterbi encoder chip — Viterbio koduotuvo lustas statusas T sritis radioelektronika atitikmenys: angl. Viterbi encoder chip vok. Viterbi Koder Chip, n rus. кристалл ИС кодера Витерби, m pranc. puce de codeur Viterbi, f …   Radioelektronikos terminų žodynas

  • Viterbi-Koder-Chip — Viterbio koduotuvo lustas statusas T sritis radioelektronika atitikmenys: angl. Viterbi encoder chip vok. Viterbi Koder Chip, n rus. кристалл ИС кодера Витерби, m pranc. puce de codeur Viterbi, f …   Radioelektronikos terminų žodynas

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”