Der Viterbi Algorithmus ist ein dynamischer Programmieralgorithmus für zu finden, dass die wahrscheinlichste Folge von verborgenen Staaten - den Pfad von Viterbi genannt hat - der auf eine Folge von beobachteten Ereignissen, besonders im Zusammenhang von Informationsquellen von Markov und verborgenen Modellen von Markov hinausläuft.

Die Begriffe "Pfad von Viterbi" und "Algorithmus von Viterbi" werden auch auf zusammenhängende dynamische Programmieralgorithmen angewandt, die die einzelne wahrscheinlichste Erklärung für eine Beobachtung entdecken. Zum Beispiel, in der statistischen Syntaxanalyse eines dynamischen Programmieralgorithmus kann verwendet werden, um die einzelne wahrscheinlichste Abstammung ohne Zusammenhänge (Syntaxanalyse) einer Schnur zu entdecken, die manchmal die "Syntaxanalyse von Viterbi" genannt wird.

Der Algorithmus von Viterbi wurde von Andrew Viterbi 1967 als ein Entzifferungsalgorithmus für Convolutional-Codes über laute Digitalnachrichtenverbindungen vorgeschlagen. Der Algorithmus hat universale Anwendung in der Entzifferung der Convolutional-Codes verwendet sowohl in CDMA als auch in GSM digital zellular, Verbindungsaufbau-Modems, Satellit, Tief-Raumkommunikationen und 802.11 drahtlose LANs gefunden. Es wird jetzt auch in Spracherkennung, dem Schlüsselwort-Entdecken, der linguistischen Datenverarbeitung und bioinformatics allgemein verwendet. Zum Beispiel, in der Rede zum Text (Spracherkennung), wird das akustische Signal als die beobachtete Folge von Ereignissen behandelt, und, wie man betrachtet, ist eine Schnur des Textes die "verborgene Ursache" des akustischen Signals. Der Algorithmus von Viterbi findet die wahrscheinlichste Schnur des Textes gegeben das akustische Signal.

Algorithmus

Nehmen Sie an, dass uns Hidden Markov Model (HMM) mit dem Zustandraum, den anfänglichen Wahrscheinlichkeiten gegeben wird, im Staat und den Übergangswahrscheinlichkeiten des Wechselns vom Staat bis Staat zu sein. Sagen Sie, dass wir Produktionen beobachten. Die Zustandfolge, um am wahrscheinlichsten die Beobachtungen erzeugt zu haben, wird durch die Wiederauftreten-Beziehungen gegeben:

:

\begin {Reihe} {rcl }\

V_ {0, k} &=& \mathrm {P }\\groß (y_0 \| \k \big) \cdot \pi_k \\

V_ {t, k} &=& \mathrm {P }\\groß (y_t \| \k \big) \cdot \max_ {x \in S} \left (a_ {x, k} \cdot V_ {t-1, x }\\Recht)

\end {ordnen }\

</Mathematik>

Hier ist die Wahrscheinlichkeit der wahrscheinlichsten Zustandfolge, die für die ersten Beobachtungen verantwortlich ist (wir fügen denjenigen hinzu, weil das Indexieren an 0 angefangen hat), der als sein Endstaat hat. Der Viterbi Pfad kann durch das Sparen zurück von Zeigestöcken wiederbekommen werden, die sich erinnern, welcher Staat in der zweiten Gleichung verwendet wurde. Lassen Sie, die Funktion zu sein, die den Wert von verwendeten zurückgibt, um wenn, oder wenn zu rechnen. Dann:

:\begin {Reihe} {rcl }\

x_T &=& \arg\max_ {x \in S} (V_ {T, x}) \\

x_ {t-1} &=& \mathrm {Ptr} (x_t, t)

\end {ordnen }\</Mathematik>

Die Kompliziertheit dieses Algorithmus ist.

Pseudocode

Hier sind einige notwendig aufgestellt für das Problem. In Anbetracht des Beobachtungsraums, des Zustandraums, einer Folge von Beobachtungen, der Übergang-Matrix der solcher Größe, der die Übergangswahrscheinlichkeit des Durchquerens vom Staat bis Staat versorgt, Emissionsmatrix der solcher Größe, der die Wahrscheinlichkeit des Beobachtens vom Staat versorgt, eine Reihe von anfänglichen Wahrscheinlichkeiten der solcher Größe, der die Wahrscheinlichkeit versorgt, dass.We sagen, ist ein Pfad eine Folge von Staaten, die die Beobachtungen erzeugen.

In diesem dynamischen Programmierproblem bauen wir zwei 2-dimensionale Tische der Größe. Jedes Element dessen versorgt die Wahrscheinlichkeit des wahrscheinlichsten Pfads bis jetzt damit erzeugt. Jedes Element, Läden des wahrscheinlichsten Pfads bis jetzt für

Wir füllen Einträge von zwei Tischen, indem wir Ordnung dessen vergrößern.

: und

:

EINGANG: Der Beobachtungsraum, der Zustandraum, eine Folge von Beobachtungen

solch das, wenn die Beobachtung in der Zeit, Übergang-Matrix der Größe solcher ist

das versorgt die Übergangswahrscheinlichkeit des Durchquerens vom Staat bis Staat, Emissionsmatrix der Größe

solch, der die Wahrscheinlichkeit des Beobachtens vom Staat, einer Reihe von anfänglichen Wahrscheinlichkeiten der Größe versorgt

solch, der die Wahrscheinlichkeit das versorgt

PRODUKTION: Die Annahme der verborgenen Zustandfolge

A01 fungieren VITERBI (O, S, π, Y, A, B): X

A02 für jeden Staat s tun

A03 T [ich, 1]  π*B

A04 T [ich, 1] 0

A05 enden für

A06 für i2,3..., T tun

A07 für jeden Staat s tun

A08 T [j, ich] 

A09 T [j, ich] 

A10 enden für

A11 enden für

A12 z

A13 xs

A14 für iT, t-1..., 2 tun

A15 z=T [ich, y] </U-Boot>

A16 x=s

A17 enden für

A18 geben X zurück

A19 beenden Funktion

Beispiel

Denken Sie eine sehr primitive kleine Klinik in einem sehr primitiven Dorf. Leute im Dorf haben ein sehr nettes Eigentum, dass sie entweder gesund oder ein Fieber habend sind. Wenn eine Person ein Fieber hat, (s) braucht er nicht in der Farm zu arbeiten. So werden Leute betroffen, ob sie ein Fieber oder nicht haben, und die einzige Weise, wie sie erzählen konnten, ob sie ein Fieber haben, zur Klinik gehen und einen sehr klugen Arzt dort fragen soll. Der kluge Arzt diagnostiziert Fieber, indem er Patienten fragt, wie tun, fühlen sie sich, und einem Patienten wird nur erlaubt zu antworten entweder (s) fühlt er sich normal, (s) fühlt er sich schwindlig, oder (s) er fühlt sich kalt.

Nehmen Sie an, dass ein Patient zur Klinik täglich kommt, und dem Arzt erzählt, wie (s) er sich fühlt. Der Arzt glaubt, dass die Gesundheitsbedingung dieses Patienten als eine getrennte Kette von Markov funktioniert. Es gibt zwei Staaten, "Gesund" und "Fieber", aber der Arzt kann sie direkt nicht beobachten, d. h. werden sie vor ihm verborgen. An jedem Tag gibt es eine bestimmte Chance, dass der Patient dem Arzt sagen wird, dass er eines der folgenden Gefühle abhängig von seiner Gesundheitsbedingung hat: "normal", "kalt", oder "schwindlig". Diejenigen sind die Beobachtungen. Das komplette System ist das eines verborgenen Modells von Markov (HMM).

Der Arzt weiß die allgemeine Gesundheitsbedingung des Dorfbewohners, und wie sich Patienten mit oder ohne Fieber im Durchschnitt fühlen. Mit anderen Worten sind die Rahmen des HMM bekannt. Sie können wie folgt auf der Pythonschlange-Programmiersprache vertreten werden:

Staaten = ('Gesund', 'Fieber')

Beobachtungen = ('normal', 'kalt', 'schwindlig')

start_probability = {'Gesund': 0.6, 'Fieber': 0.4 }\

transition_probability = {\

'Gesund': {'Gesund': 0.7, 'Fieber': 0.3},

'Fieber': {'Gesund': 0.4, 'Fieber': 0.6},

}\

emission_probability = {\

'Gesund': {'Normal': 0.5, 'Kälte': 0.4, 'schwindlig': 0.1},

'Fieber': {'Normal': 0.1, 'Kälte': 0.3, 'schwindlig': 0.6},

}\

</Quelle>

In diesem Stück des Codes, vertritt den Glauben des Arztes, über den Staat der HMM darin ist, wenn der Patient zuerst besucht (alles, was er weiß, ist, dass der Patient dazu neigt, gesund zu sein). Der besondere Wahrscheinlichkeitsvertrieb verwendet hier ist nicht das Gleichgewicht ein, der (gegeben die Übergangswahrscheinlichkeiten) ungefähr ist. Das Vertreten der Änderung der Gesundheitsbedingung in der zu Grunde liegenden Kette von Markov. In diesem Beispiel gibt es nur eine 30-%-Chance, dass Morgen der Patient ein Fieber haben wird, wenn er heute gesund ist. Das Vertreten, wie sich wahrscheinlich der Patient an jedem Tag fühlen soll. Wenn er gesund ist, gibt es eine 50-%-Chance, dass er sich normal fühlt; wenn er ein Fieber hat, gibt es eine 60-%-Chance, dass er sich schwindlig fühlt.

Der Patient besucht drei Tage hintereinander, und der Arzt entdeckt, dass am ersten Tag er sich schwindlig am zweiten Tag fühlt, fühlt er sich kalt am dritten Tag er fühlt sich normal. Der Arzt hat eine Frage: Wie ist die wahrscheinlichste Folge der Gesundheitsbedingung des Patienten, würden diese Beobachtungen erklären? Darauf wird durch den Algorithmus von Viterbi geantwortet.

1. Hilft, sich die Schritte von Viterbi zu vergegenwärtigen.

def print_dptable (V):

drucken Sie "",

weil ich in der Reihe (len (V)): Drucken Sie "%7s" % (" %d" % i),

Druck

für y in V [0].keys :

drucken Sie "%.5s:" % y,

für t in der Reihe (len (V)):

drucken Sie "%.7s" % (" %f" % V [t] [y]),

Druck

def viterbi (obs, Staaten, start_p, trans_p, emit_p):

V = [{}]

Pfad = {}\

# Initialisieren Grundfälle (t == 0)

für y in Staaten:

V [0] [y] = start_p [y] * emit_p [y] [obs [0]]

Pfad [y] = [y]

# Lauf Viterbi für t> 0

für t in der Reihe (1, len (obs)):

V.append ({})

newpath = {}\

für y in Staaten:

(prob, Staat) = max ([(V [t-1] [y0] * trans_p [y0] [y] * emit_p [y] [obs [t]], y0) für y0 in Staaten])

V [t] [y] = prob

newpath [y] = Pfad [Staat] + [y]

# brauchen sich an die alten Pfade nicht zu erinnern

Pfad = newpath

print_dptable (V)

(prob, Staat) = max ([(V [len (obs) - 1] [y], y) für y in Staaten])

kehren Sie (prob, Pfad [Staat]) zurück

</Quelle>

Die Funktion nimmt die folgenden Argumente: Ist die Folge von Beobachtungen z.B; ist der Satz von verborgenen Staaten; ist die Anfang-Wahrscheinlichkeit; sind die Übergangswahrscheinlichkeiten; und sind die Emissionswahrscheinlichkeiten. Für die Einfachheit des Codes nehmen wir an, dass die Beobachtungsfolge nichtleer ist, und dass und für alle Staaten i, j definiert wird.

Im laufenden Beispiel wird der forward/Viterbi Algorithmus wie folgt verwendet:

Def-Beispiel :

geben Sie viterbi zurück (Beobachtungen,

Staaten,

start_probability,

transition_probability,

emission_probability)

Druckbeispiel

</Quelle>

Das offenbart, dass die Beobachtungen am wahrscheinlichsten durch Staaten, mit der Kerbe 0.01344 erzeugt wurden (um normalisiert zu werden). Mit anderen Worten, in Anbetracht der beobachteten Tätigkeiten, konnte der Patient höchstwahrscheinlich ein Fieber haben, als er sich schwindlig gefühlt hat und dann er gesund der zweite Tag geworden ist und die Gesundheit den dritten Tag gehalten hat.

Die Operation des Algorithmus von Viterbi kann mittels eines vergegenwärtigt werden

Gitterwerk-Diagramm. Der Viterbi Pfad ist im Wesentlichen der kürzeste

Pfad durch dieses Gitterwerk. Das Gitterwerk für das Wetterbeispiel wird unten gezeigt; der entsprechende

Pfad von Viterbi ist im kühnen:

Wenn

man den Algorithmus von Viterbi durchführt, sollte es bemerkt werden, dass vieler Sprachgebrauch, der Punkt-Arithmetik - als p Schwimmen lässt, klein ist, kann das zu Unterlauf in den Ergebnissen führen. Eine allgemeine Technik, um das zu vermeiden, soll den Logarithmus der Wahrscheinlichkeiten nehmen und ihn während der Berechnung, dieselbe im Logarithmischen Zahl-System verwendete Technik verwenden. Sobald der Algorithmus geendet hat, kann ein genauer Wert durch das Durchführen des passenden exponentiation erhalten werden.

Javanische Durchführung

Import java.util. Hashtable;

öffentliche Klasse Viterbi

{\

statische Endschnur GESUND = "Gesund";

statisches Endschnur-FIEBER = "Fieber";

statische Endschnur SCHWINDLIG = "schwindlig";

statische Endschnur-KÄLTE = "Kälte";

statische Endschnur NORMAL = "normal";

öffentliche statische leere Hauptsache (Schnur [] args)

{\

Schnur [] setzt = neue Schnur [] {GESUND, FIEBER} fest;

Schnur [] Beobachtungen = neue Schnur [] {SCHWINDLIG, KALT, NORMAL};

Hashtable

start_probability.put (GESUND, 0.6f);

start_probability.put (FIEBER, 0.4f);

//transition_probability

Hashtable

neuer Hashtable

Hashtable

t1.put (GESUND, 0.7f);

t1.put (FIEBER, 0.3f);

Hashtable

t2.put (GESUND, 0.4f);

t2.put (FIEBER, 0.6f);

transition_probability.put (GESUND, t1);

transition_probability.put (FIEBER, t2);

//emission_probability

Hashtable neuer Hashtable Hashtable

e1.put (SCHWINDLIG, 0.1f)

;

e1.put (KÄLTE, 0.4f);

e1.put (NORMAL, 0.5f);

Hashtable

e2.put (SCHWINDLIG, 0.6f)

;

e2.put (KÄLTE, 0.3f);

e2.put (NORMAL, 0.1f);

emission_probability.put (GESUND, e1);

emission_probability.put (FIEBER, e2);

Gegenstand [] röstet = forward_viterbi (Beobachtungen,

Staaten,

start_probability,

transition_probability,

emission_probability);

System.out.println (((Hin- und Herbewegung) rösten [0]).floatValue )

;

System.out.println ((Schnur) rösten [1]);

System.out.println (((Hin- und Herbewegung) rösten [2]).floatValue );

}\

öffentlicher statischer Gegenstand [] forward_viterbi (Schnur [] obs, Schnur [] Staaten,

Hashtable Hashtable Hashtable {\ Hashtable

für (Schnur-Staat: Staaten)

T.put (staatlicher, neuer Gegenstand [] {start_p.get (Staat), Staat, start_p.get (Staat)});

für (Schnur-Produktion: obs)

{\

Hashtable

dafür (Spannen next_state: Staaten)

{\

schwimmen Sie ganz = 0;

Spannen Sie argmax ="";

lassen Sie valmax = 0 schwimmen;

lassen Sie prob = 1 schwimmen;

Spannen Sie v_path ="";

lassen Sie v_prob = 1 schwimmen

;

dafür (Spannen source_state: Staaten)

{\

Gegenstand [] objs = T.get (source_state);

prob = ((Hin- und Herbewegung) objs [0]).floatValue ;

v_path = (Schnur) objs [1];

v_prob = ((Hin- und Herbewegung) objs [2]).floatValue ;

lassen Sie p = emit_p.get (source_state).get (Produktion) * schwimmen

trans_p.get (source_state).get (next_state);

prob * = p;

v_prob * = p;

ganz + = prob;

wenn (v_prob> valmax)

{\

argmax = v_path +"," + next_state;

valmax = v_prob;

}\

}\

U.put (next_state, neuer Gegenstand [] {ganz, argmax, valmax});

}\

T = U

;

}\

schwimmen Sie ganz = 0;

Spannen Sie argmax ="";

lassen Sie valmax = 0 schwimmen;

Hin- und Herbewegung prob;

Schnur v_path;

Hin- und Herbewegung v_prob;

für (Schnur-Staat: Staaten) {\

Gegenstand [] objs = T.get (Staat);

prob = ((Hin- und Herbewegung) objs [0]).floatValue ;

v_path = (Schnur) objs [1];

v_prob = ((Hin- und Herbewegung) objs [2]).floatValue ;

ganz + = prob;

wenn (v_prob> valmax)

{\

argmax = v_path;

valmax = v_prob;

}\

}\

geben Sie neuen Gegenstand [] {ganz, argmax, valmax} zurück

; }\}\</Quelle>

Durchführung von Clojure

(ns ident.viterbi

(: Verwenden Sie [clojure.pprint]))

(defstruct hmm: n: M: init-probs: Emission-probs: Zustandübergänge)

(defn machen [{-hmm: Schlüssel [Staaten, obs, init-probs, Emission-probs, Zustandübergänge]}]

(stellen Sie hmm struct-kartografisch-dar

:n (zählen Staaten auf)

:m (zählen obs auf)

:states setzt fest

:obs obs

:init-probs init-probs;; n verdunkeln

:emission-Probs-Emission-probs;; M x n

:State-Übergang-Zustandübergänge))

(defn hat [s] mit einem Inhaltsverzeichnis versehen

(Karte-Vektor (wiederholen inc 0) s))

(defn argmax [coll]

(Schleife [s (hat coll mit einem Inhaltsverzeichnis versehen)

max (der erste s)]

(wenn (leer? s)

max

(lassen Sie idx elt] (der erste s)

[max-indx max-elt] max]

(wenn (> elt max-elt)

(kehren Sie wieder (lassen Sie s ausruhen) (der erste s))

(kehren Sie wieder (lassen Sie s ausruhen) max))))))

(defn pprint-hmm [hmm]

(println "Zahl von Staaten:" (: n hmm) "Zahl von Beobachtungen:" (: M hmm))

(drucken Sie "init Wahrscheinlichkeiten:") (pprint (: init-probs hmm))

(drucken Sie "Emission probs:") (pprint (: Emission-probs hmm))

(Druck "Zustandübergänge:") (pprint (: Zustandübergänge hmm)))

(defn Init-Alphas [hmm obs]

(Karte (fn [x]

(* (aget (: init-probs hmm) x) (aget (: Emission-probs hmm) x obs)))

(Reihe (: n hmm))))

(defn vorwärts [hmm Alphas obs]

(Karte (fn [j]

(* (nehmen ab (fn [resümieren i]

(+ Summe (* (die n-ten Alphas i) (aget (: Zustandübergänge hmm) ich j))))

0

(Reihe (: n hmm)))

(aget (: Emission-probs hmm) j obs))) (Reihe (: n hmm))))

(defn Delta-max [hmm Deltas obs]

(Karte (fn [j]

(* (wenden max (Karte an (fn [ich]

(* (die n-ten Deltas i)

(aget (: Zustandübergänge hmm) ich j)))

(Reihe (: n hmm))))

(aget (: Emission-probs hmm) j obs)))

(Reihe (: n hmm))))

(defn Rückzug [Pfad-Deltas]

(Schleife [Pfad (kehren Pfade um)

Begriff (zuerst (argmax Deltas))

Rückzug []]

(wenn (leer? Pfad)

(Rückseite (conj verfolgen Begriff denselben Weg zurück))

(kehren Sie (Rest-Pfad) (n-t (der erste Pfad) Begriff) (conj Rückzug-Begriff) wieder))))

(defn Aktualisierungspfade [hmm Deltas]

(Karte (fn [j]

(zuerst (argmax (Karte (fn [ich]

(* (die n-ten Deltas i)

(aget (: Zustandübergänge hmm) ich j)))

(Reihe (: n hmm))))))

(Reihe (: n hmm))))

(defn viterbi [hmm observs]

(Schleife [obs (lassen observs ausruhen)

Alphas (Init-Alphas hmm (der erste observs))

Delta-Alphas

Pfade []]

(wenn (leer? obs)

[(Rückzug-Pfad-Deltas) (Hin- und Herbewegung (nehmen + Alphas ab)),]

(kehren Sie wieder (lassen Sie obs ausruhen)

(schicken Sie hmm Alphas (der erste obs)) nach

(Delta-max hmm Deltas (der erste obs))

(conj Pfade (Aktualisierungspfade hmm Deltas))))))

</Quelle>

C# Durchführung

das Verwenden des Systems;

das Verwenden des Systems. Sammlungen. Allgemein;

das Verwenden des Systems. Linq;

das Verwenden des Systems. Text;

namespace Viterbi

{\

Klassenprogramm

{\

//Wetter setzt fest

statische Schnur GESUND = "Gesund";

statisches Schnur-FIEBER = "Fieber";

//Zuverlässige Handlungen (Beobachtungen)

statische Schnur SCHWINDLIG = "schwindlig";

statische Schnur-KÄLTE = "Kälte";

statische Schnur NORMAL = "normal";

statische leere Hauptsache (Schnur [] args)

{\

//initialisieren Sie unsere Reihe von Staaten und Beobachtungen

Schnur [] setzt = {GESUND, FIEBER} fest;

Schnur [] Beobachtungen = {SCHWINDLIG, KALT, NORMAL};

var start_probability = neues Wörterbuch

start_probability. Tragen Sie (GESUND, 0.6f) bei;

start_probability. Tragen Sie (FIEBER, 0.4f) bei;

//Übergangswahrscheinlichkeit

var transition_probability = neues Wörterbuch

var t1 = neues Wörterbuch

t1. Tragen Sie (GESUND, 0.7f) bei;

t1. Tragen Sie (FIEBER, 0.3f) bei;

Wörterbuch

t2. Tragen Sie (GESUND, 0.4f) bei;

t2. Tragen Sie (FIEBER, 0.6f) bei;

transition_probability. Tragen Sie (GESUND, t1) bei;

transition_probability. Tragen Sie (FIEBER, t2) bei;

//emission_probability

var emission_probability = neues Wörterbuch

var e1 = neues Wörterbuch

e1. Tragen Sie (SCHWINDLIG, 0.1f) bei;

e1. Tragen Sie (KÄLTE, 0.4f) bei;

e1. Tragen Sie (NORMAL, 0.5f) bei;

Wörterbuch

e2. Tragen Sie (SCHWINDLIG, 0.6f) bei;

e2. Tragen Sie (KÄLTE, 0.3f) bei;

e2. Tragen Sie (NORMAL, 0.1f) bei;

emission_probability. Tragen Sie (GESUND, e1) bei;

emission_probability. Tragen Sie (FIEBER, e2) bei;

Gegenstand [] röstet = forward_viterbi (Beobachtungen, Staaten, start_probability, transition_probability, emission_probability);

Konsole. WriteLine ((Hin- und Herbewegung) rösten [0]);

Konsole. WriteLine ((Schnur) rösten [1]);

Konsole. WriteLine ((Hin- und Herbewegung) rösten [2]);

Konsole. ReadLine ;

}\

öffentlicher statischer Gegenstand [] forward_viterbi (Schnur [] obs, Schnur [] Staaten, Wörterbuch

{\

var T = neues Wörterbuch

foreach (Schnur setzen in Staaten fest)

{\

T.Add (staatlicher, neuer Gegenstand [] {start_p [Staat], Staat, start_p [Staat]});

}\

foreach (Schnur-Produktion in obs)

{\

var U = neues Wörterbuch

foreach (Spannen next_state in Staaten)

{\

schwimmen Sie ganz = 0;

Spannen Sie argmax ="";

lassen Sie valmax = 0 schwimmen;

lassen Sie prob = 1 schwimmen;

Spannen Sie v_path ="";

lassen Sie v_prob = 1 schwimmen;

foreach (Spannen source_state in Staaten)

{\

Gegenstand [] objs = T [source_state];

prob = ((Hin- und Herbewegung) objs [0]);

v_path = (Schnur) objs [1];

v_prob = ((Hin- und Herbewegung) objs [2]);

lassen Sie p = emit_p [source_state] [Produktion] * trans_p [source_state] [next_state] schwimmen;

prob * = p;

v_prob * = p;

ganz + = prob;

wenn (v_prob> valmax)

{\

argmax = v_path +"," + next_state;

valmax = v_prob;

}\

}\

U.Add (next_state, neuer Gegenstand [] {ganz, argmax, valmax});

}\

T = U;

}\

lassen Sie xtotal = 0 schwimmen;

Spannen Sie xargmax ="";

lassen Sie xvalmax = 0 schwimmen;

Hin- und Herbewegung xprob;

Schnur xv_path;

Hin- und Herbewegung xv_prob;

foreach (Schnur setzen in Staaten fest) {\

Gegenstand [] objs = [der Staat] T;

xprob = ((Hin- und Herbewegung) objs [0]);

xv_path = ((Schnur) objs [1]);

xv_prob = ((Hin- und Herbewegung) objs [2]);

xtotal + = xprob;

wenn (xv_prob> xvalmax)

{\

xargmax = xv_path;

xvalmax = xv_prob;

}\ }\

geben Sie neuen Gegenstand [] {xtotal, xargmax, xvalmax} zurück;

}\

}\

}\</Quelle>

Erweiterungen

Eine Generalisation des Algorithmus von Viterbi, genannt der Max-Summe-Algorithmus (oder Max-Produktalgorithmus) kann verwendet werden, um die wahrscheinlichste Anweisung von allen oder eine Teilmenge von latenten Variablen in einer Vielzahl von grafischen Modellen z.B zu finden. Netze von Bayesian, Markov zufällige Felder und bedingte zufällige Felder. Die latenten Variablen müssen im Allgemeinen in einem Weg verbunden werden, der einem HMM, mit einer begrenzten Zahl von Verbindungen zwischen Variablen und einem Typ der geradlinigen Struktur unter den Variablen etwas ähnlich ist. Der allgemeine Algorithmus schließt Nachrichtenübergang ein und ist dem Glaube-Fortpflanzungsalgorithmus wesentlich ähnlich (der die Generalisation des rückwärts gerichteten Algorithmus ist).

Mit dem Algorithmus genannt wiederholenden Viterbi, der decodiert, kann man die Subfolge einer Beobachtung finden, die am besten (durchschnittlich) zu einem gegebenen HMM zusammenpasst. Dieser Algorithmus wird von Qi Wang vorgeschlagen, um usw. sich mit Turbocode zu befassen. Wiederholender Viterbi decodierende Arbeiten durch das wiederholende Hervorrufen eines modifizierten Algorithmus von Viterbi, das Wiederschätzen der Kerbe für einen Füller bis zur Konvergenz.

Ein alternativer Algorithmus, der Faule Viterbi Algorithmus, ist kürzlich vorgeschlagen worden. Für viele Codes vom praktischen Interesse, unter angemessenen Geräuschbedingungen, dem faulen

Decoder (Faulen Viterbi Algorithmus verwendend), ist viel schneller als der ursprüngliche Decoder von Viterbi (Algorithmus von Viterbi verwendend). Dieser Algorithmus arbeitet, indem er irgendwelche Knoten nicht ausgebreitet wird, bis er wirklich muss, und gewöhnlich schafft, mit dem Tun von viel weniger Arbeit (in der Software) loszukommen, als der gewöhnliche Algorithmus von Viterbi für dasselbe Ergebnis - jedoch, ist es zu parallelize in der Hardware nicht so leicht.

Außerdem ist der Algorithmus von Viterbi erweitert worden, um mit einem deterministischen begrenzten Automaten zu funktionieren, um Geschwindigkeit für den Gebrauch in der stochastischen Konvertierung des Briefs zu das Phonem zu verbessern.

Siehe auch

• Baum-walisischer Algorithmus
• Rückwärts gerichteter Algorithmus
• Schicken Sie Algorithmus nach
• Fehlerkorrekturcode
• Weiche Produktion Algorithmus von Viterbi
• Decoder von Viterbi
• Verborgenes Modell von Markov
• Wortart, die markiert

Referenzen

• (Zeichen: Viterbi, der Algorithmus decodiert, wird im Abschnitt IV beschrieben) erforderliches Abonnement.

• Abonnement erforderlich.

• (Beschreibt den Vorwärtsalgorithmus und Algorithmus von Viterbi für HMMs).
• Shinghal, R. und Godfried T. Toussaint, "Experimente in der Textanerkennung mit dem modifizierten Algorithmus von Viterbi," IEEE Transaktionen auf der Muster-Analyse- und Maschinenintelligenz, Vol. PAMI-l, April 1979, Seiten 184-193.
• Shinghal, R. und Godfried T. Toussaint, "Die Empfindlichkeit des modifizierten Algorithmus von Viterbi zur Quellstatistik," IEEE Transaktionen auf der Muster-Analyse- und Maschinenintelligenz, vol. PAMI-2, März 1980, Seiten 181-185.

Durchführungen

• C und Zusammenbau
• C
• C ++
• C ++ und Zunahme durch Antonio Gulli
• C#
• Java
• Perl
• Einleitung
• VHDL

Links

• Tutorenkurs auf convolutional, der mit der Viterbi-Entzifferung, durch Chip Fleming codiert
• Die Geschichte des Viterbi Algorithmus, durch David Forney
• Eine sanfte Einführung in die dynamische Programmierung und den Viterbi Algorithmus
• Ein Tutorenkurs für ein Verborgenes Musterwerkzeug von Markov (durchgeführt in C), der eine Beschreibung des Algorithmus von Viterbi enthält