Andrea 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 — 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

  • Andrew 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… …   Deutsch Wikipedia

  • Andrew Viterbi — Nombre Andrea James Viterbi Nacimiento 9 …   Wikipedia Español

  • Andrew Viterbi — Andrew James Viterbi, Ph.D. (Bergamo (Italy) March 9, 1935) is an Italian American electrical engineer and businessman.Viterbi was born in Bergamo, Italy to Jewish parents and emigrated with them in 1939 to the United States as a refugee. His… …   Wikipedia

  • Andrew J. Viterbi — Andrew James Viterbi (geboren als Andrea Viterbo, * 9. März 1935 in Bergamo) ist ein italienisch US amerikanischer Elektroingenieur und Informatiker. 1967 erfand er den Viterbi Algorithmus, den er sich damals auf Anraten eines Rechtsanwalts nicht …   Deutsch Wikipedia

  • Leyes raciales fascistas — Las leyes raciales fascistas son un conjunto de medidas legislativas y administrativas (leyes, decretos, circulares, etc.) que fueron lanzadas en Italia entre 1938 y los primeros cinco años de la década de 1940, inicialmente por el régimen… …   Wikipedia Español

  • Lois Raciales Fascistes — Les lois raciales, en italien Leggi razziali, précisent les mesures prises en Italie vers la fin des années 1930 pendant la période du régime fasciste contre les personnes de religion juive mais aussi d autres. Benito Mussolini en fait la… …   Wikipédia en Français

  • USC Shoah Foundation Institute for Visual History and Education — The USC Shoah Foundation Institute for Visual History and Education, formerly Survivors of the Shoah Visual History Foundation, is a nonprofit organization established by Steven Spielberg in 1994, one year after completing the Academy Award… …   Wikipedia

  • Mathematical diagram — This article is about general diagrams in mathematics. For diagrams in the category theoretical sense, see Diagram (category theory). Euclid s Elements, ms. from Lüneburg, A.D. 1200 Mathematical diagrams are diagrams in the field of mathematics,… …   Wikipedia

  • Fundación Shoah — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

Share the article and excerpts

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