Viterbi-Dekodierung

Position in der SkillModul 2 von 3 · Thema 2 von 4

2.2 Viterbi-Dekodierung

—Lab-Punkte— / 100XP gesamt—Serie—

Die eine wahrscheinlichste Geschichte

Der Forward-Algorithmus addiert alle verborgenen Pfade, um zu sagen, wie wahrscheinlich die Daten sind. Oft will man etwas anderes: die eine beste Geschichte, die einzelne Zustandsfolge, die die Daten mit der höchsten Wahrscheinlichkeit erklärt. Die Viterbi-Dekodierung findet sie. Die Idee ist der Forward-Algorithmus mit einer Änderung: Statt über die vorherigen Zustände zu summieren, nimmt man den besten. Man führt einen Wert $\delta_t(j)$ , die Wahrscheinlichkeit des besten Pfades, der an Tag $t$ in Zustand $j$ endet, und merkt sich, welcher Vorzustand ihn lieferte, den Rückzeiger.

\delta_1(j)=\pi_jB_j(o_1),\qquad \delta_t(j)=\Big[\max_i\delta_{t-1}(i)A_{ij}\Big]B_j(o_t),\qquad \psi_t(j)=\arg\max_i\delta_{t-1}(i)A_{ij}

(1)

Wählen Sie nach dem letzten Tag den Zustand mit dem größten $\delta_T$ und gehen Sie über die Rückzeiger $\psi$ zurück, um den ganzen Pfad abzulesen. Zwei praktische Punkte. Erstens: mit Logarithmen arbeiten. Produkte vieler Wahrscheinlichkeiten schrumpfen gegen null, Logarithmen machen daraus Summen, und weil der Log monoton wächst, bleibt der beste Pfad derselbe. Zweitens: Der beste Pfad ist nicht dasselbe, wie an jedem Tag einzeln den wahrscheinlichsten Zustand zu wählen. Der Pfad kann durch das Spätere erzwungen werden, wie das Beispiel zeigt.

Wieder Klein, Groß, GroßTag 1:

\delta_1=(0{,}54,\ 0{,}12)

. Tag 2 (groß): Ruhig kommt am besten von Ruhig,

0{,}54\cdot0{,}9\cdot0{,}1=0{,}0486

. Stürmisch kommt am besten von Stürmisch,

0{,}12\cdot0{,}8\cdot0{,}7=0{,}0672

, nicht von Ruhig (

0{,}54\cdot0{,}1\cdot0{,}7=0{,}0378

). Tag 3: Stürmisch kommt von Stürmisch,

0{,}0672\cdot0{,}8\cdot0{,}7=0{,}0376

, und Ruhig nur

0{,}0044

. Der beste Pfad ist Stürmisch, Stürmisch, Stürmisch mit Wahrscheinlichkeit

0{,}0376

. Dabei sah Tag eins allein mit

0{,}82

ruhig aus. Die späteren großen Bewegungen ziehen die ganze Geschichte Richtung Stürmisch. Dieser Pfad ist

1{,}78

-mal wahrscheinlicher als Ruhig, Stürmisch, Stürmisch (

0{,}0212

Viterbi ersetzt die Summe des Forward-Algorithmus durch ein Maximum und führt Rückzeiger.
Der beste Pfad kann sich vom wahrscheinlichsten Zustand jedes einzelnen Tages unterscheiden.
Logarithmen nutzen: Summen von Logs vermeiden Unterlauf und behalten denselben besten Pfad.

Lab: Was bewertet wird

Ein Viterbi-Wert an Tag zwei15 Pkt.
Die Wahrscheinlichkeit des besten Pfades15 Pkt.
Der Log des besten Pfades10 Pkt.
Gegenüber einem anderen Pfad10 Pkt.
Der erste Zustand des besten Pfades15 Pkt.
Die Schritte von Viterbi10 Pkt.
Begriffe zuordnen10 Pkt.
Warum Logarithmen nutzen15 Pkt.

0/ 8 beantwortet

1Numerische Antwort15 Pkt.Nicht beantwortet

Wie groß ist mit $\delta_1=(0{,}54,\ 0{,}12)$ und einer großen Bewegung an Tag 2 der Wert $\delta_2(S)=\max(0{,}54\cdot0{,}1,\ 0{,}12\cdot0{,}8)\cdot0{,}7$ ? Geben Sie vier Dezimalstellen an.

d =

akzeptiert: ± 0.0003

2Numerische Antwort15 Pkt.Nicht beantwortet

Wie groß ist mit $\delta_2=(0{,}0486,\ 0{,}0672)$ und einer großen Bewegung an Tag 3 der Wert $\delta_3(S)=\max(0{,}0486\cdot0{,}1,\ 0{,}0672\cdot0{,}8)\cdot0{,}7$ , die Wahrscheinlichkeit des besten Pfades? Geben Sie vier Dezimalstellen an.

d =

akzeptiert: ± 0.0003

3Numerische Antwort10 Pkt.Nicht beantwortet

Wie groß ist der natürliche Logarithmus der Wahrscheinlichkeit $0{,}0376$ des besten Pfades? Geben Sie zwei Dezimalstellen an.

l =

akzeptiert: ± 0.02

4Numerische Antwort10 Pkt.Nicht beantwortet

Wie viel Mal wahrscheinlicher ist der beste Pfad (Wahrscheinlichkeit $0{,}0376$ ) als der Pfad Ruhig, Stürmisch, Stürmisch (Wahrscheinlichkeit $0{,}0212$ )? Geben Sie zwei Dezimalstellen an.

r =

akzeptiert: ± 0.02

5Auswahl15 Pkt.Nicht beantwortet

Tag eins zeigt eine kleine Bewegung, was Ruhig allein zu 82 % wahrscheinlich macht. Was ist der erste Zustand des besten Pfades für Klein, Groß, Groß?

6Schritte ordnen10 Pkt.Nicht beantwortet

Bringen Sie die Schritte der Viterbi-Dekodierung in die richtige Reihenfolge.

Zum Umsortieren ziehen, oder ein Element fokussieren, mit Leertaste anheben, mit Pfeiltasten bewegen und mit Leertaste ablegen.

1Nach dem letzten Tag den Zustand mit dem größten Wert wählen
2Mit delta gleich Anfangswahrscheinlichkeit mal erster Emission beginnen
3Über die Rückzeiger zurückgehen, um den Pfad zu lesen
4Für jeden Tag und Zustand den besten Vorgänger behalten und merken

7Zuordnen10 Pkt.Nicht beantwortet

Ordnen Sie jedem Begriff seine Bedeutung zu.

Wähle den Partner für jedes Element links.

\delta_t(j)

\psi_t(j)

Forward-Algorithmus

Viterbi-Algorithmus

8In Worten erklären15 Pkt.Nicht beantwortet

Erklären Sie in ein bis zwei Sätzen, warum die Viterbi-Dekodierung meist mit Logarithmen der Wahrscheinlichkeiten geschrieben wird und warum das den besten Pfad nicht ändert.

Bewertet nach:Produkte vieler Wahrscheinlichkeiten schrumpfen gegen nullLogs machen Produkte zu Summen und der Log wächst monoton, der beste Pfad bleibt also derselbe0 / 400 Zeichen

Mathe-ModusEingabe per Tastatur oder LaTeXAufgabe 1 von 8 · Strg ⏎ zum Prüfen

Viterbi-Dekodierung

Position in der SkillModul 2 von 3 · Thema 2 von 4

2.2 Viterbi-Dekodierung

—Lab-Punkte— / 100XP gesamt—Serie—

Die eine wahrscheinlichste Geschichte

\delta_1(j)=\pi_jB_j(o_1),\qquad \delta_t(j)=\Big[\max_i\delta_{t-1}(i)A_{ij}\Big]B_j(o_t),\qquad \psi_t(j)=\arg\max_i\delta_{t-1}(i)A_{ij}

(1)

Wieder Klein, Groß, GroßTag 1:

\delta_1=(0{,}54,\ 0{,}12)

. Tag 2 (groß): Ruhig kommt am besten von Ruhig,

0{,}54\cdot0{,}9\cdot0{,}1=0{,}0486

. Stürmisch kommt am besten von Stürmisch,

0{,}12\cdot0{,}8\cdot0{,}7=0{,}0672

, nicht von Ruhig (

0{,}54\cdot0{,}1\cdot0{,}7=0{,}0378

). Tag 3: Stürmisch kommt von Stürmisch,

0{,}0672\cdot0{,}8\cdot0{,}7=0{,}0376

, und Ruhig nur

0{,}0044

. Der beste Pfad ist Stürmisch, Stürmisch, Stürmisch mit Wahrscheinlichkeit

0{,}0376

. Dabei sah Tag eins allein mit

0{,}82

ruhig aus. Die späteren großen Bewegungen ziehen die ganze Geschichte Richtung Stürmisch. Dieser Pfad ist

1{,}78

-mal wahrscheinlicher als Ruhig, Stürmisch, Stürmisch (

0{,}0212

Viterbi ersetzt die Summe des Forward-Algorithmus durch ein Maximum und führt Rückzeiger.
Der beste Pfad kann sich vom wahrscheinlichsten Zustand jedes einzelnen Tages unterscheiden.
Logarithmen nutzen: Summen von Logs vermeiden Unterlauf und behalten denselben besten Pfad.

Lab: Was bewertet wird

Ein Viterbi-Wert an Tag zwei15 Pkt.
Die Wahrscheinlichkeit des besten Pfades15 Pkt.
Der Log des besten Pfades10 Pkt.
Gegenüber einem anderen Pfad10 Pkt.
Der erste Zustand des besten Pfades15 Pkt.
Die Schritte von Viterbi10 Pkt.
Begriffe zuordnen10 Pkt.
Warum Logarithmen nutzen15 Pkt.

0/ 8 beantwortet

1Numerische Antwort15 Pkt.Nicht beantwortet

Wie groß ist mit $\delta_1=(0{,}54,\ 0{,}12)$ und einer großen Bewegung an Tag 2 der Wert $\delta_2(S)=\max(0{,}54\cdot0{,}1,\ 0{,}12\cdot0{,}8)\cdot0{,}7$ ? Geben Sie vier Dezimalstellen an.

d =

akzeptiert: ± 0.0003

2Numerische Antwort15 Pkt.Nicht beantwortet

d =

akzeptiert: ± 0.0003

3Numerische Antwort10 Pkt.Nicht beantwortet

Wie groß ist der natürliche Logarithmus der Wahrscheinlichkeit $0{,}0376$ des besten Pfades? Geben Sie zwei Dezimalstellen an.

l =

akzeptiert: ± 0.02

4Numerische Antwort10 Pkt.Nicht beantwortet

Wie viel Mal wahrscheinlicher ist der beste Pfad (Wahrscheinlichkeit $0{,}0376$ ) als der Pfad Ruhig, Stürmisch, Stürmisch (Wahrscheinlichkeit $0{,}0212$ )? Geben Sie zwei Dezimalstellen an.

r =

akzeptiert: ± 0.02

5Auswahl15 Pkt.Nicht beantwortet

Tag eins zeigt eine kleine Bewegung, was Ruhig allein zu 82 % wahrscheinlich macht. Was ist der erste Zustand des besten Pfades für Klein, Groß, Groß?

6Schritte ordnen10 Pkt.Nicht beantwortet

Bringen Sie die Schritte der Viterbi-Dekodierung in die richtige Reihenfolge.

Zum Umsortieren ziehen, oder ein Element fokussieren, mit Leertaste anheben, mit Pfeiltasten bewegen und mit Leertaste ablegen.

1Nach dem letzten Tag den Zustand mit dem größten Wert wählen
2Mit delta gleich Anfangswahrscheinlichkeit mal erster Emission beginnen
3Über die Rückzeiger zurückgehen, um den Pfad zu lesen
4Für jeden Tag und Zustand den besten Vorgänger behalten und merken

7Zuordnen10 Pkt.Nicht beantwortet

Ordnen Sie jedem Begriff seine Bedeutung zu.

Wähle den Partner für jedes Element links.

\delta_t(j)

\psi_t(j)

Forward-Algorithmus

Viterbi-Algorithmus

8In Worten erklären15 Pkt.Nicht beantwortet

Erklären Sie in ein bis zwei Sätzen, warum die Viterbi-Dekodierung meist mit Logarithmen der Wahrscheinlichkeiten geschrieben wird und warum das den besten Pfad nicht ändert.

Bewertet nach:Produkte vieler Wahrscheinlichkeiten schrumpfen gegen nullLogs machen Produkte zu Summen und der Log wächst monoton, der beste Pfad bleibt also derselbe0 / 400 Zeichen

Mathe-ModusEingabe per Tastatur oder LaTeXAufgabe 1 von 8 · Strg ⏎ zum Prüfen

Viterbi-Dekodierung

Die eine wahrscheinlichste Geschichte

Lab: Was bewertet wird

Melde dich an, um deinen Code auszuführen.

Viterbi-Dekodierung

Die eine wahrscheinlichste Geschichte

Lab: Was bewertet wird

Melde dich an, um deinen Code auszuführen.