Hauptmenü öffnen

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

Inhaltsverzeichnis

Markov-ModellBearbeiten

Gegeben sei ein HMM   mit

  •   – Menge der verborgenen Zustände
  •  Alphabet der beobachtbaren Symbole (Emissionen)
  •  Zustandsübergangsmatrix
  •   – Beobachtungsmatrix
  •   – Anfangswahrscheinlichkeitsverteilung

AufgabenstellungBearbeiten

Sei   die beobachtete Sequenz von Symbolen. Es soll die wahrscheinlichste Zustandsfolge   berechnet werden. Also diejenige Sequenz von verborgenen Zuständen, die unter allen Folgen   der Länge   den Wert von   maximiert, das ist die Wahrscheinlichkeit, dass das Modell   bei Erzeugung der Ausgabe   durch die Zustände   gelaufen ist.

Nach den Rechenregeln für bedingte Wahrscheinlichkeiten gilt:

 

Da außerdem   nicht von   abhängt, ergibt sich folgender Zusammenhang:

 

Für die eigentliche Berechnung werden nun zwei verschiedene Arten von Variablen –   und   – verwendet:

In   ist die maximale Verbundwahrscheinlichkeit gespeichert zum Zeitpunkt   bei der Beobachtung des Präfixes   durch eine Zustandsfolge der Länge   gelaufen zu sein und im Zustand   zu enden:

 

Die Variable   dagegen merkt sich für jeden Zeitpunkt und jeden Zustand, welcher Vorgängerzustand an der Maximumsbildung beteiligt war.

AlgorithmusBearbeiten

Die Variablen   sowie   lassen sich rekursiv bestimmen:

Initialisierung
 
Rekursion
 
Terminierung
 
Pfadermittlung
 

KomplexitätBearbeiten

Die Tabelle der   benötigt   Speicher, die Matrix der   ist von gleichem Umfang. Für jede Zelle der beiden Matrizen wird über   Alternativen optimiert, also ist die Laufzeit in  .

Um den Speicherplatz zu halbieren kann der Pfad   alternativ auch nach der Terminierung durch Backtracking in der Matrix aller   – also ohne die zusätzlichen Variablen   – ermittelt werden. Da aber in der Praxis die Berechnung von   keinen Mehraufwand verursacht, verlängert sich die benötigte Rechenzeit bei dem Backtracking-Ansatz geringfügig.

AnwendungenBearbeiten

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 auchBearbeiten

LiteraturBearbeiten

WeblinksBearbeiten