Viterbi-Algorithmus

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Der Viterbi-Algorithmus wurde von Dr. 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.

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.

[Bearbeiten] Funktionsweise

Der Viterbi-Algorithmus ist eine Methode aus dem Gebiet der Dynamischen Programmierung, die die wahrscheinlichste Abfolge von versteckten Zuständen findet, die zu einer Abfolge von beobachtbaren Ereignissen führt. Die Abfolge von versteckten Zuständen wird Viterbi-Pfad genannt. Näheres zur Nomenklatur siehe unter Hidden Markov Model, welches die Basis für den Viterbi-Algorithmus legte.

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 zugrunde liegenden Hidden Markov Model.

[Bearbeiten] Pseudocode

Initialisierung

v[0][0] = 1.0

for k = 1 to K
    v[k][0] = 0.0
end for

Iteration über die Zustände der Kette

for i = 1 to length do
    for j = 1 to number_states do
        maxIndex = -1;
        max = NEGATIVE_INFINITY;
           for k = 0 to number_states do
              result =  $e k (X i)$  * v[k][i-1] * t[k][j];
              if result > max
                 max = result;
                 maxIndex = k;
              endif
           endfor
     endfor
endfor