www.wikidata.de-de.nina.az

Viterbi Algorithmus Der ist ein Algorithmus der dynamischen Programmierung zur Bestimmung der wahrscheinlichsten Sequenz

Viterbi-Algorithmus

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.

Hidden Markov-Modell Bearbeiten

Gegeben sei ein HMM mit

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

Aufgabenstellung Bearbeiten

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.

Algorithmus Bearbeiten

Die Variablen sowie lassen sich rekursiv bestimmen:

Für berechne

Komplexität Bearbeiten

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.

Anwendungen Bearbeiten

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 auch Bearbeiten

Literatur Bearbeiten

  • A. Viterbi: Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. In: IEEE Transactions on Information Theory. Band 13, Nr. 2, 1967, ISSN 0018-9448, S. 260–269, doi:10.1109/TIT.1967.1054010 (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. Band 61, Nr. 3, 1973, S. 268–278, doi:10.1109/PROC.1973.9030 (IEEE Xplore).

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Viterbi Algorithmus ist ein Algorithmus der dynamischen Programmierung zur Bestimmung der wahrscheinlichsten Sequenz von verborgenen Zustanden 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 Optimalempfanger fur verzerrte und gestorte Kanale her Der Viterbi Algorithmus wird heutzutage zum Beispiel in Mobiltelefonen oder Wireless LANs zur Fehlerkorrektur der Funkubertragung verwendet ebenso in Festplatten da bei der Aufzeichnung auf die Magnetplatten ebenfalls Ubertragungsfehler entstehen Der Algorithmus ist in der Nachrichtentechnik und Informatik weit verbreitet Die Informationstheorie Bioinformatik Spracherkennung und Computerlinguistik verwenden haufig den Viterbi Algorithmus Inhaltsverzeichnis 1 Hidden Markov Modell 2 Aufgabenstellung 3 Algorithmus 4 Komplexitat 5 Anwendungen 6 Siehe auch 7 Literatur 8 WeblinksHidden Markov Modell BearbeitenGegeben sei ein HMM l S V A B p displaystyle lambda S V A B pi nbsp mit S displaystyle S nbsp Menge der verborgenen Zustande V displaystyle V nbsp Alphabet der beobachtbaren Symbole Emissionen A displaystyle A nbsp Zustandsubergangsmatrix B displaystyle B nbsp Beobachtungsmatrix p displaystyle pi nbsp AnfangswahrscheinlichkeitsverteilungAufgabenstellung BearbeitenSei o o 1 o 2 o T V displaystyle boldsymbol o o 1 o 2 ldots o T in V nbsp die beobachtete Sequenz von Symbolen Es soll die wahrscheinlichste Zustandsfolge q q 1 q 2 q T S T displaystyle boldsymbol q q 1 q 2 ldots q T in S T nbsp berechnet werden Also diejenige Sequenz von verborgenen Zustanden die unter allen Folgen q displaystyle boldsymbol q nbsp der Lange T displaystyle T nbsp den Wert von P q o l displaystyle P boldsymbol q boldsymbol o lambda nbsp maximiert das ist die Wahrscheinlichkeit dass das Modell l displaystyle lambda nbsp bei Erzeugung der Ausgabe o displaystyle boldsymbol o nbsp durch die Zustande q displaystyle boldsymbol q nbsp gelaufen ist Nach den Rechenregeln fur bedingte Wahrscheinlichkeiten gilt P q o l P o q l P o l displaystyle P boldsymbol q boldsymbol o lambda frac P boldsymbol o boldsymbol q lambda P boldsymbol o lambda nbsp Da ausserdem P o l displaystyle P boldsymbol o lambda nbsp nicht von q displaystyle boldsymbol q nbsp abhangt ergibt sich folgender Zusammenhang P o q l max q S T P o q l displaystyle P boldsymbol o boldsymbol q lambda max boldsymbol q in S T P boldsymbol o boldsymbol q lambda nbsp Fur die eigentliche Berechnung werden nun zwei verschiedene Arten von Variablen ϑ t i displaystyle vartheta t i nbsp und ps t i displaystyle psi t i nbsp verwendet In ϑ t i displaystyle vartheta t i nbsp ist die maximale Verbundwahrscheinlichkeit gespeichert zum Zeitpunkt 1 t T displaystyle 1 leq t leq T nbsp bei der Beobachtung des Prafixes o 1 o 2 o t displaystyle o 1 o 2 ldots o t nbsp durch eine Zustandsfolge der Lange t displaystyle t nbsp gelaufen zu sein und im Zustand s i S displaystyle s i in S nbsp zu enden ϑ t i max q S t q t s i P o 1 o 2 o t q 1 q 2 q t l displaystyle 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 nbsp Die Variable ps t i displaystyle psi t i nbsp dagegen merkt sich fur jeden Zeitpunkt und jeden Zustand welcher Vorgangerzustand an der Maximumsbildung beteiligt war Algorithmus BearbeitenDie Variablen ϑ t i displaystyle vartheta t i nbsp sowie ps t i displaystyle psi t i nbsp lassen sich rekursiv bestimmen Initialisierung ϑ 1 i p i b i o 1 ps 1 i 0 1 i S displaystyle vartheta 1 i pi i cdot b i o 1 psi 1 i 0 qquad 1 leq i leq left S right nbsp RekursionFur 1 lt t T displaystyle 1 lt t leq T nbsp berechne ϑ t i b i o t max 1 j S a j i ϑ t 1 j 1 i S ps t i argmax 1 j S a j i ϑ t 1 j 1 i S displaystyle begin aligned vartheta t i amp b i o t cdot max 1 leq j leq left S right a ji cdot vartheta t 1 j qquad 1 leq i leq left S right psi t i amp underset 1 leq j leq left S right operatorname argmax a ji cdot vartheta t 1 j qquad 1 leq i leq left S right end aligned nbsp Terminierung P o q l max 1 j S ϑ T j q T argmax 1 j S ϑ T j displaystyle begin aligned P boldsymbol o boldsymbol q lambda amp max 1 leq j leq left S right vartheta T j q T amp underset 1 leq j leq left S right operatorname argmax vartheta T j end aligned nbsp Pfadermittlung q t ps t 1 q t 1 1 t lt T displaystyle q t psi t 1 q t 1 qquad 1 leq t lt T nbsp Komplexitat BearbeitenDie Tabelle der ϑ t i displaystyle vartheta t i nbsp benotigt O S T displaystyle O left S right cdot T nbsp Speicher die Matrix der ps t i displaystyle psi t i nbsp ist von gleichem Umfang Fur jede Zelle der beiden Matrizen wird uber S displaystyle left S right nbsp Alternativen optimiert also ist die Laufzeit in O S 2 T displaystyle O left S right 2 T nbsp Um den Speicherplatz zu halbieren kann der Pfad q displaystyle boldsymbol q nbsp alternativ auch nach der Terminierung durch Backtracking in der Matrix aller ϑ t i displaystyle vartheta t i nbsp also ohne die zusatzlichen Variablen ps t i displaystyle psi t i nbsp ermittelt werden Da aber in der Praxis die Berechnung von ps t i displaystyle psi t i nbsp keinen Mehraufwand verursacht verlangert sich die benotigte Rechenzeit bei dem Backtracking Ansatz geringfugig Anwendungen BearbeitenDer 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 uberall eingesetzt werden um Muster zu erkennen Das ist ein weites Feld da Lebewesen standig Sinnesreize interpretieren mussen und aus dem bereits Gelernten diese Signale einordnen Der Viterbi Algorithmus tut genau das auch und ist somit ein wichtiger Baustein der Kunstlichen Intelligenz Einen wichtigen Stellenwert nimmt der Algorithmus in der Bioinformatik ein denn anhand des Viterbi Algorithmus kann unter anderem von der tatsachlichen Sequenz eines DNA Abschnitts auf eventuelle versteckte Zustande 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 Sequenzlange steigende Aufwand im Gegensatz zum exponentiellen Aufwand des zugrundeliegenden Hidden Markov Model Siehe auch BearbeitenForward Algorithmus Backward Algorithmus Baum Welch AlgorithmusLiteratur BearbeitenA Viterbi Error bounds for convolutional codes and an asymptotically optimum decoding algorithm In IEEE Transactions on Information Theory Band 13 Nr 2 1967 ISSN 0018 9448 S 260 269 doi 10 1109 TIT 1967 1054010 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 Band 61 Nr 3 1973 S 268 278 doi 10 1109 PROC 1973 9030 IEEE Xplore Weblinks BearbeitenErklarung des Viterbi Algorithmus fur Faltungscodes englisch Andrew J Viterbi Viterbi algorithm In Scholarpedia englisch inkl Literaturangaben E G Schukat Talamazzini Spezielle Musteranalysesysteme PDF 1 3 MB Vorlesung im WS 2012 13 an der Universitat Jena Kapitel 5 Folie 39 ff Abgerufen von https de wikipedia org w index php title Viterbi Algorithmus amp oldid 213887390