Der Forward-Algorithmus | QuantCraft Academy

Roadmaps Skills

+1,2 Tsd. Lernende

Anmelden Beitreten

Wie wahrscheinlich ist, was wir gesehen haben?

Angenommen, wir sahen die Bewegungen Klein, Groß, Groß. Wie wahrscheinlich ist diese Folge in unserem Modell? Wir könnten jeden verborgenen Pfad auflisten (Ruhig-Ruhig-Ruhig, Ruhig-Ruhig-Stürmisch usw.), die Wahrscheinlichkeit jedes Pfades berechnen und addieren. Bei $K$ Zuständen und $T$ Tagen sind das $K^{T}$ Pfade, viel zu viele. Der Forward-Algorithmus bildet dieselbe Summe in $T\cdot K^{2}$ Schritten, indem er Arbeit wiederverwendet. Er hält eine Zahl $\alpha_t(j)$ : die Wahrscheinlichkeit der ersten $t$ Beobachtungen und des Zustands $j$ an Tag $t$ .

\alpha_1(j)=\pi_jB_j(o_1),\qquad \alpha_t(j)=\Big[\sum_i\alpha_{t-1}(i)A_{ij}\Big]B_j(o_t),\qquad P(o_1,\dots,o_T)=\sum_j\alpha_T(j)

(1)

Lesen Sie die Rekursion in Worten: Um heute im Zustand $j$ zu sein, kam man gestern aus einem Zustand $i$ (Summe über $i$ mit der Übergangswahrscheinlichkeit), und dann erzeugte der heutige Zustand die heutige Beobachtung. Teilt man $\alpha_t$ durch seine Summe, erhält man die gefilterten Wahrscheinlichkeiten, Ihre Überzeugung über den heutigen Zustand bei Daten bis heute. Ein praktisches Problem: Das Multiplizieren vieler kleiner Zahlen lässt sie gegen null schrumpfen. Daher teilt man in jedem Schritt durch die Summe $c_t$ und merkt sie sich. Der Log der Datenwahrscheinlichkeit ist dann einfach die Summe der $\ln c_t$ .

Klein, Groß, GroßTag 1:

\alpha_1=(0{,}6\cdot0{,}9,\ 0{,}4\cdot0{,}3)=(0{,}54,\ 0{,}12)

, Summe

c_1=0{,}66

. Tag 2 (eine große Bewegung): Ruhig erhält

(0{,}54\cdot0{,}9+0{,}12\cdot0{,}2)\cdot0{,}1=0{,}051

und Stürmisch

(0{,}54\cdot0{,}1+0{,}12\cdot0{,}8)\cdot0{,}7=0{,}105

, Summe

0{,}156

, die gefilterte Wahrscheinlichkeit für Stürmisch ist also

0{,}105/0{,}156=0{,}673

. Tag 3 ergibt

\alpha_3=(0{,}00669,\ 0{,}06237)

. Die Wahrscheinlichkeit der ganzen Folge ist

0{,}00669+0{,}06237=0{,}0691

, ihr Log

-2{,}673

.

Forward-Algorithmus: Summe über alle verborgenen Pfade in $T\cdot K^{2}$ statt $K^{T}$ Schritten.
Gefilterte Wahrscheinlichkeiten: $\alpha_t$ normieren, um die Überzeugung über den heutigen Zustand aus Daten bis heute zu erhalten.
Skalierung: in jedem Schritt durch $c_t$ teilen und die $\ln c_t$ addieren, um Unterlauf zu vermeiden.

0/ 8 beantwortet

1Numerische Antwort15 Pkt.Nicht beantwortet

Tag 1 zeigt eine kleine Bewegung. Wie groß ist $\alpha_1(R)=\pi_R\,B_R(k)$ mit $\pi_R=0{,}6$ und $B_R(k)=0{,}9$ ?

a =

akzeptiert: ± 0.005

2Numerische Antwort10 Pkt.Nicht beantwortet

Wie groß ist mit $\alpha_1=(0{,}54,\ 0{,}12)$ die Summe $c_1$ , die Wahrscheinlichkeit der ersten Beobachtung?

c =

akzeptiert: ± 0.005

3Numerische Antwort15 Pkt.Nicht beantwortet

Nach den Beobachtungen Klein und Groß ist $\alpha_2=(0{,}051,\ 0{,}105)$ . Wie groß ist die gefilterte Wahrscheinlichkeit des stürmischen Zustands, $0{,}105/(0{,}051+0{,}105)$ ? Geben Sie drei Dezimalstellen an.

p =

akzeptiert: ± 0.003

4Numerische Antwort15 Pkt.Nicht beantwortet

An Tag 3 ist $\alpha_3=(0{,}00669,\ 0{,}06237)$ . Wie groß ist die Wahrscheinlichkeit der ganzen Folge Klein, Groß, Groß, die Summe von $\alpha_3$ ? Geben Sie vier Dezimalstellen an.

p =

akzeptiert: ± 0.0003

5Numerische Antwort10 Pkt.Nicht beantwortet

Wie groß ist der natürliche Logarithmus der Wahrscheinlichkeit $0{,}0691$ der Folge? Geben Sie zwei Dezimalstellen an.

l =

akzeptiert: ± 0.02

6Auswahl10 Pkt.Nicht beantwortet

Was erlaubt uns der Forward-Algorithmus zu vermeiden?

7Zuordnen10 Pkt.Nicht beantwortet

Ordnen Sie jedem Begriff seine Bedeutung zu.

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

\alpha_t(j)

Gefilterte Wahrscheinlichkeit

c_t

\sum_j\alpha_T(j)

8In Worten erklären15 Pkt.Nicht beantwortet

Erklären Sie in ein bis zwei Sätzen, warum eine echte Implementierung des Forward-Algorithmus in jedem Schritt durch $c_t$ teilt.

Bewertet nach:Das Multiplizieren vieler Wahrscheinlichkeiten lässt die Zahlen gegen null schrumpfenDaher wird jeder Schritt normiert und die Logarithmen der Skalierungsfaktoren werden addiert0 / 400 Zeichen

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