Der Viterbi-Algorithmus ist ein dynamischer Programmieralgorithmus, der die wahrscheinlichste Sequenz versteckter Zustände identifiziert, die eine gegebene Sequenz beobachteter Ereignisse erzeugt haben könnte. Die resultierende Sequenz wird oft als Viterbi-Pfad bezeichnet. Er wird am häufigsten auf Hidden-Markov-Modelle (HMMs) angewendet, bei denen die zugrunde liegenden Zustände nicht direkt beobachtbar sind, aber die Beobachtungen beeinflussen. Beispielsweise könnte ein Arzt, der über mehrere Tage die Symptome eines Patienten beobachtet, den Algorithmus verwenden, um die wahrscheinlichste Sequenz zugrunde liegender Gesundheitszustände abzuleiten, die diese Symptome verursacht haben.
Der Algorithmus hat universelle Anwendung bei der Decodierung von Faltungscodes gefunden, die in CDMA- und GSM-Digitalfunknetzen, DFÜ-Modems, Satelliten- und Tiefraumkommunikation sowie 802.11-WLANs verwendet werden. Er wird auch häufig in der Spracherkennung, Sprachsynthese, Sprecherdiarisierung, Stichworterkennung, Computerlinguistik und Bioinformatik eingesetzt. In Sprach-zu-Text-Systemen dient das akustische Signal als beobachtete Sequenz, und die Textzeichenfolge ist die versteckte Ursache; der Viterbi-Algorithmus findet den wahrscheinlichsten Text für das gegebene akustische Signal.
Geschichte
Der Viterbi-Algorithmus ist nach Andrew Viterbi benannt, der ihn 1967 als Decodierungsalgorithmus für Faltungscodes über verrauschte digitale Kommunikationsverbindungen vorschlug. Er hat eine Geschichte mehrfacher Erfindung, mit mindestens sieben unabhängigen Entdeckungen, darunter die von Viterbi, Needleman und Wunsch sowie Wagner und Fischer. Er wurde bereits 1987 als Methode zur Wortartenmarkierung in die Verarbeitung natürlicher Sprache eingeführt.
Die Begriffe "Viterbi-Pfad" und "Viterbi-Algorithmus" sind zu Standardbegriffen für dynamische Programmieransätze bei Maximierungsproblemen mit Wahrscheinlichkeiten geworden. In der statistischen Syntaxanalyse kann ein dynamischer Programmieralgorithmus die einzelne wahrscheinlichste kontextfreie Ableitung (Parse) einer Zeichenfolge entdecken, die allgemein als "Viterbi-Parse" bezeichnet wird. Eine weitere Anwendung ist die Zielverfolgung, bei der der Algorithmus die Spur berechnet, die einem Beobachtungsverlauf die maximale Wahrscheinlichkeit zuweist.
Algorithmus-Überblick
Gegeben sei ein Hidden-Markov-Modell mit einer Menge versteckter Zustände S, einer Menge möglicher Emissionen (Beobachtungen) M und einer Sequenz von T Beobachtungen o0, o1, ..., oT-1, findet der Viterbi-Algorithmus die wahrscheinlichste Sequenz versteckter Zustände, die diese Beobachtungen erzeugt haben könnte. Zu jedem Zeitschritt t löst der Algorithmus das Teilproblem, bei dem nur Beobachtungen bis ot berücksichtigt werden.
Es werden zwei Matrizen der Größe T × |S| konstruiert. Die Matrix Pt,s enthält die maximale Wahrscheinlichkeit, bei Beobachtung t im Zustand s zu enden, über alle möglichen Zustandssequenzen, die dorthin führen. Die Matrix Qt,s verfolgt den vorherigen Zustand, der vor s in dieser Zustandssequenz mit maximaler Wahrscheinlichkeit verwendet wurde.
Seien πs und ar,s die Anfangs- bzw. Übergangswahrscheinlichkeiten, und sei bs,o die Wahrscheinlichkeit, o im Zustand s zu beobachten. Dann sind die Werte von P durch eine Rekurrenzrelation gegeben. Zum Zeitpunkt t = 0 ist Pt,s gleich πs multipliziert mit bs,o0. Für t > 0 ist Pt,s gleich dem Maximum über alle vorherigen Zustände r von (Pt-1,r × ar,s × bs,ot). Nach dem Füllen der Matrizen verfolgt der Algorithmus vom Zustand mit der höchsten Wahrscheinlichkeit zum letzten Zeitschritt mithilfe der Q-Matrix zurück, um die wahrscheinlichste Zustandssequenz zu rekonstruieren.
Anwendungen in der Kommunikation
Der Algorithmus ist ein Eckpfeiler der modernen digitalen Kommunikation. Er decodiert Faltungscodes, die fehlerkorrigierende Codes sind, die in vielen drahtlosen und drahtgebundenen Systemen verwendet werden. In CDMA- und GSM-Zellularnetzen hilft der Viterbi-Algorithmus, übertragene Daten trotz Rauschen und Interferenzen wiederherzustellen. DFÜ-Modems, Satellitenverbindungen und Tiefraumkommunikationssysteme verlassen sich ebenfalls auf ihn. Der 802.11-WLAN-Standard integriert die Viterbi-Decodierung für eine zuverlässige Datenübertragung.
Die Effizienz des Algorithmus ergibt sich aus seiner dynamischen Programmiernatur: Er vermeidet die erschöpfende Aufzählung aller möglichen Zustandssequenzen, indem er Zwischenwahrscheinlichkeiten speichert und das Optimalitätsprinzip nutzt. Dies macht es machbar, lange Sequenzen in Echtzeit zu decodieren, selbst auf ressourcenbeschränkten Geräten.
Anwendungen in Sprache und Sprachverarbeitung
In der Spracherkennung richtet der Viterbi-Algorithmus akustische Merkmale an phonetischen oder Wortmodellen aus. Das akustische Signal ist die beobachtete Sequenz, und die Textzeichenfolge ist die versteckte Ursache. Der Algorithmus findet die wahrscheinlichste Textzeichenfolge für das gegebene akustische Signal, was eine genaue Transkription ermöglicht. Er wird auch in der Sprachsynthese verwendet, um die natürlichste Sequenz von Spracheinheiten auszuwählen, und in der Sprecherdiarisierung, um zu bestimmen, wer wann gesprochen hat.
In der Computerlinguistik wird der Algorithmus auf die Wortartenmarkierung angewendet, bei der versteckte Zustände grammatische Kategorien und Beobachtungen Wörter sind. Er unterstützt auch die statistische Syntaxanalyse, bei der er den wahrscheinlichsten Parse-Baum für einen Satz findet. In der Bioinformatik hilft er, biologische Sequenzen zu alignen und Genstrukturen vorherzusagen, wobei DNA- oder Proteinsequenzen als Beobachtungen und funktionale Elemente als versteckte Zustände behandelt werden.
Verwandte Techniken
Der Viterbi-Algorithmus ist eng mit anderen Methoden der dynamischen Programmierung verwandt, wie dem Vorwärts-Rückwärts-Algorithmus, der Wahrscheinlichkeiten über alle möglichen Zustandssequenzen berechnet, anstatt nur über die wahrscheinlichste. Er teilt auch konzeptionelle Grundlagen mit Beamsuche, einer heuristischen Suchtechnik, die in der Sequenzgenerierung verwendet wird. In modernen maschinellen Lern- und Systemen der künstlichen Intelligenz, insbesondere solchen mit Sequenz-zu-Sequenz-Modellen und großen Sprachmodellen, wird die Beamsuche oft der exakten Viterbi-Decodierung vorgezogen, da die Zustandsräume groß sind.
Trotz des Aufkommens von Neuronale-Netze-Ansätzen bleibt der Viterbi-Algorithmus in Hybridsystemen relevant. Beispielsweise kann er verwendet werden, um Ausgaben von Neuronale-Netze-akustischen Modellen in der Spracherkennung zu decodieren oder strukturelle Beschränkungen in Aufgaben der Verarbeitung natürlicher Sprache durchzusetzen. Seine mathematische Klarheit und Effizienz sichern seine fortgesetzte Verwendung in sowohl klassischen als auch zeitgenössischen Anwendungen.